Mixed Strategy Nash Equilibrium Explained (Game Theory 4) | Matching Pennies

[00:00:00]hello everyone welcome to our new episode in this episode we're going to talk about mixed strategy nash equilibrium it's not a new concept it's just we apply the idea of nash equilibrium in mixed strategies all right so what why do we do this i mean why do we need this um the reason is simple because not all games um have uh nash equilibrium in pure strategies the matching pennies is one example so uh remember there are two players each player has two strategies either head or tail and if the players simultaneously and independently choose their strategies once they you know after they choose their strategies if uh their choices match hat hat or tail tail player one wins player two loses and so assume that player two pays a dollar to player one otherwise player two wins player one loses so that means player one pays a dollar to player two all right so in this game let's try to find the nash equilibrium strategies uh nash equilibrium in pure strategies all right so what does that mean let's calculate the best responses so if the second player uh plays head what is the best response for the uh first player well clearly head because plus one is higher than minus one so i underline plus one indicated that indicating that had is the best response to hat well what if player two plays tail instead well in this case uh sort of tail is the best response because plus one is higher than minus one okay well what about player two's best responses so let's suppose player one plays hat what is the best response for play uh player two is it head or is it tail clearly tail because plus 1 is higher and what if player 1 selects strategy tail in this case the best response is not tail it's head so i underline plus 1.

[00:02:06]so what does that mean that means you know in each uh entry uh there's only one number that is underlined that means for example for this strategy profile player one is best responding player two however player two is not best responding player 1. so therefore hh is not a nash equilibrium similarly with exactly the same reasoning tail tail or head tail or tail head so those four potential not potential uh pure strategy profiles and none of them are nash equilibrium because either only one player best response is the other but it's not the case that both players are best responding put differently if one of those outcomes realized one of the players is going to regret his or her choice all right so that means in this game there's no nash equilibrium in pure strategies but again we would like to come up with a theory a solution concept that recommends something some some outcomes some potential outcome in every possible reasonable games and this is quite a reasonable game because it's finite you know simple two-person game and with two uh strategies so uh one way of sort of dealing with this type of problems is to extend the idea of strategies without changing the game structure so what does that mean that means well what if the players are not allowed to choose a strategy from s1 s2 which is head tail right these are pure strategies but instead we let them choose from this set delta s1 delta s2 which is basically a simplex remember the definition of mixed strategies so it's basically uh some a probability distribution uh p 1 minus p so p is the probability of head 1 minus p is therefore probability of tail because there are two pure ac strategies uh the the any mixed strategy is going to look something like this p1 minus p such that p is in is in zero one interval all right so therefore this is uh what a mixed strategy the set of mixed strategies will look like and so we basically ask the same question well yes there is no nash equilibrium when we sort of restrict our attention to those strategy sets but what if we enlarge the idea of strategy to mix strategies then can we find nash equilibrium meaning a profile sigma 1 sigma 2 sigma 1 is for example just i'm just giving an example with one third probability player one is going to play head with uh two third probability he's gonna play tail and player two she's gonna play with one over four probability head and uh three over four probably tail for example is this a nash equilibrium what does that mean well what does that mean in mixed strategies we just extend the idea of nash equilibrium in mixed strategies how do we do that well let's do it more formally so here i'm going to give the definition so consider a strategy profile sigma and remember it's basically a vector of strategies for each player so uh n is some number greater than or equal to two where each sigma i is coming from this delta si set which is a simplex for each player i okay well the profile this profile sigma is called a mixed strategy nash equilibrium all right so in brief i'm just going to write n e it means it always means uh nash equilibrium if and only if the payoff of player i when he plays sigma i given that his opponents are playing according to this strategy profile this payoff must be greater than or equal to his payoff when he plays something else as i prime sigma minus i but don't forget the others are still playing the same strategy profile for all s i prime in s i and each player i all right so that's it well basically what i'm saying is that uh what i'm saying is that this sigma i is a best response for player i to sigma minus i and this is true for each i this is exactly the same definition for the nash equilibrium in pure strategies here the only difference is that this you know i don't have s i but it's i have sigma i all right well maybe um it's important to underline this thing uh you may say why don't i write this definition at least this inequality as such u i sigma i sigma minus i greater than or equal to u i sigma i prime sigma minus i for all sigma prime in delta s i right well that inequality clearly so you see what i mean so here what i'm saying is once i fix the other so what let's fix player i all right i have to do this for every player right because i have to check that profile in this profile each player is best responding his or her opponent so fix player i all right and then fix his opponent's strategy all right then i'm gonna compare two payoffs on the one hand i have the payoff of the player i when he plays sigma i which is what's prescribed in this strategy profile on the other hand on the other side of this inequality i have some strategy but this is as you see as i prime so it's a pure strategy so the question is is this mixed strategy gives player i the highest payoff in comparison to all the other pure strategies he could select it or he could select well alternatively you can say the same or similar not same similar comparison but this time i'm asking the question is sigma i giving player i the highest payoff in comparison to every other pure and mixed strategies available to player i well so clearly here i am making more comparisons right because uh all pure strategies are also mixed strategies but all not all mixed strategies are pure for example this is a mixed strategy and clearly it's not a pure strategy for example uh the following mixed strategy where player one uh plays uh head with probability one and tail with probability zero so one zero or zero one meaning uh he plays tail with probability one so these are actually just another way of representing a pure strategy where player one plays head right so therefore every pure strategy is a mixed strategy so therefore all of those comparisons are already included here however there are a bunch of other comparisons here which are not you know which we're not operating here so the question is are these two definitions i mean i'll just plug this here would this give me exactly the same definition the answer is i'm not going to formally prove it but the answer is yes it is true meaning whether you use this comparison or this comparison it makes no difference and the reason well i mean it may not sort of uh obvious to you but here is the intuition look if this payoff is greater than or equal to all the other payoffs i'm sorry all the payoffs of all the other pure strategies well then this payoff must be greater than or equal to all the uh all the payoffs i'm sorry oh payoffs from all the other mixed strategies why is that so uh mixed strategies are a convex combination of pure strategies therefore a mixed strategy payoff has to be convex combination of the pure strategy payoffs so that means if i am beating if sigma i is beating all my pure strategy payoffs well that means this payoff must be beating the convex combination the average of all those pure strategies you see what i mean so therefore this payoff must be beating you know all the payoffs of all the mixed strategies again um if it is not perfectly clear just fine i mean i just wanted to give you the sort of the intuition why they are equivalent um but the reason i mean some textbooks use this notation some textbooks use this notation um i think that's that's easier this one is easier to work with why is that well because it says you don't really have to make this comparison uh infinitely many times because remember there are infinitely many mixed strategies here all you have to do is just make this comparison twice uh i mean here for example uh there are two pure strategies right so that means you have to compare this expected payoff uh with uh this expected payoff under player one plays head versus if i is equal to one under player one plays tail because there are only two pure strategies alright so you have to do this comparison twice but if that was a mixed strategy you had to do it like infinitely many times which is not possible you know so therefore this is much more feasible and so therefore easier okay so that's it basically as i said mixed strategy nash equilibrium is nothing but the nash equilibrium uh where the strategies are uh are are are are in in mixed form okay um so let's solve an example all right the matching pennies so how do we find the nash equilibrium in mixed strategies uh well i mean simple what we do we find the best response of each player how do we do that well remember a strategy for player one is going to look something like this he's going to play head with probability p and he's going to play a play tell therefore with the remaining probability one minus p because there are two strategies if i had three strategies then i would have p1 p2 1 minus p1 minus p2 okay and similarly if player 2 plays head i'm sorry let's suppose player 2 plays head with probability q let's use a different letter and therefore she's going to play tail with probability oops 1 minus q all right so therefore a mixed strategy nash equilibrium sigma has has gone has has the following form p 1 minus p and q 1 minus q so once again that refers to player 1 first player and this refers to the second player strategy so that's basically sigma 1 that's sigma 2 and this p is the refers to the probability of playing head probability of playing tail same for the second player probability of playing head probably of playing tail so therefore i need to find the exact value of these p's and q's all right so what is p what is q don't forget p's and q's are a number between 0 and 1 because there are probabilities they can't be less than zero they can't be more than one so uh but what exactly so here's what we do we find again the expected i'm sorry the best response so finding best response for player one let's start with player one all right so how do we do that well first i'm going to calculate the utility the expected payoff of player 1 when he plays h and when his opponent plays sigma 2. so here the sigma 2 i mean q1 minus q all right so when player 1 plays head uh he's going to get plus one with probability q right because his opponent is uh playing a mixed strategy or let's assume i mean it's not a strategy but it's a belief so what belief is going to constitute a nash equilibrium all right so uh here player one believes that his opponent is going to play head with probability q so therefore he's going to get plus 1 with probability q and minus 1 with probability 1 minus q so it's plus 1 probability two minus one probability one minus two if you just sum them up you're gonna get uh uh two q minus one all right what about uh sorry it's the same player so what about the payoff of the first player when he plays tail instead still i'm keeping the second player strategy as sigma 2 which is q1 minus q well again this time it's minus one with probability q and plus one with probability one minus q so it's minus one q plus plus one one minus q so if you make this calculation uh what you're gonna see it's it's equal to one minus 2q all right ok so which one is the best response to q right well if u 1 h sigma 2 is greater than u1 h oh i'm sorry not h tail sigma 2. well then that means uh playing head gives higher strictly higher payoff than playing tail so therefore head is the best response had is a best response well what does hat curse so playing head meaning playing head with probability one right i mean you are not going to play tail because head is definitely better so head is the best response means playing hat with probability one is the best response that means p is equal to one is the best response okay be careful about this well however if payoff of playing head is strictly less than payoff of playing tail well then well as you see in these uh sort of comparisons remember i am keeping the other player's strategy fixed which is q one minus q so here this time tail gives strictly better payoff so the best response is playing tail for sure which means p is equal to zero is the best response so t is a best response or equivalently p equals zero right because tail corresponds p equals zero so this is probability one this is probably the zero okay well what if there's another uh uh scenario a possible scenario uh had the expected payoff of hat is equal to expected payoff of tail well what is in this case so player one gets exactly the same payoff between playing head and tail so he can play head so hat is the best response he can play tail tail is the best response right because they both give exactly the same payoff but you know what any combination of head and tail is also best response right why is that so if you play head and get payoff five and if you play tail and get pay off five so uh whatever whatever mixed strategy you play for example you play had uh 50 of the chance tail with 50 of the chance so what's going to be your expected payoff five times one half plus five times one half five again let's say you play had one third of the chance and two third probably you're gonna play tail what's gonna be your expected payoff five times one third plus five times two third again five so therefore any any p in between zero one is best response okay so it's not only head but also tail and also all the combinations all the mixture of head and tail our best response okay that part is probably the most important part of this question all right so pause for a minute or five and think about it all right so what i'm going to do next is i'm going to draw the best response function all right well it's not a function really it's a correspondence so let's put p here uh two here's all right so these are the strategies of player one and player two right play one strategy is p so here the best response of player one is a function of q remember okay so here what does this inequality mean u 1 h sigma 2 is greater than u 1 t sigma 2. it basically means 2q minus 1 greater than 1 minus 2q right so if you solve this inequality all right so this is if and only if so send q to the other side i have four q it's one to the other side two so q greater than one half so if q is greater than one half well then p equals one is the best response so let's say this is q equals one this is p equals one so my best response functions or or sets are are going to be in this uh square i mean if it doesn't look like square i'm sorry that's my bad so let's put one half here okay so when q is greater than one half the exact value doesn't matter as long as it's above one half all right so as long as q is in this range p is equal to b1 all right so therefore if you draw this function uh it's this all right so whenever q is higher than one half i have p equals one very good what about this inequality the payoff expected payoff of head less than expected payoff of tail once again the expected payoff of had is this expected pair of tail is 1 minus 2q which if you simplify it you're going to have 4q less than 2 meaning q strictly less than 2 obviously right so if this is greater this has to be less than because it's just i'm changing reverting the uh this uh the direction of this inequality so whenever q less than one half p equals zero is the best response so this is where my function is all right very good so it's a kind of a awkward function or graph well what is this well this means this inequality this equality i'm sorry means 2q minus 1 equals 1 minus 2q right again if you simplify this obviously it means q is equal to 1 half so when q is equal to one half exactly this point any p in between zero one is the best response so so it's not a function it's not just one specific p value so here for example just so for any queue just one specific p-value which was one here for any queue it was one specific p value which was zero but here for one specific q value any p is possible so that means all these points are best response so that then this sort of step uh kind of function is the again this is not really a function but anyway so uh this is the best this is a correspondence uh this is a best response function let's call it off player one okay all right well what i'm going to do next is i am going to find the best response of the second player right makes sense so payoff of expected payoff of player 1 when his opponent is playing sigma 1 which means the sigma 1 is p probability had one minus p probability tail um however player two plays uh head what's going to be his her expected payoff well here expected payoff of player two when she plays hat it's going to be minus one with probability p right because she believes that well again so if the mixed strategies or beliefs is not clear then calculating those expected payoffs will not be clear so for that reason to make that calculation clear please go back to our previous videos where i talk about beliefs and mixed strategies it's very very important okay you can't really understand one step without understanding a previous step okay so here she's going to get minus 1 with probability p and plus 1 with probability 1 minus p so therefore her expected path is going to be minus 1 times p plus plus 1 times 1 minus p so if you add them up what you're going to get is 1 minus 2p all right um the path of player two uh if uh again her opponent plays sigma one and then she however plays tail instead while this time she's gonna get plus one with probability p and minus one with probability one minus p so therefore it's plus one p plus minus one one minus p so if you do the math if you just sum them up what you're gonna get is uh 2p minus 1. very similar to the previous one right so instead of sorry q we have p so be careful when we calculate the second player's payoff her payoff her expected payoff depends on p which is reasonable because p is the second player's belief right so your expected payoff should depend on your beliefs so that makes sense it shouldn't depend on on cue because here i am calculating expected payoff of playing hat a pure action strategy i'm sorry all right so once again if uh the expected path of playing uh had is greater than expected payoff of playing tail for the second player well then so hat is better than tail so therefore she's going to play hat for sure had is best response what does that mean playing hat for sure it means playing uh q equals one all right all right is the best response um so let's leave some space if however u2 sigma 1 had less than u2 sigma uh one tail well then that means l is the best response which means q equals 0 is the best response and then finally if u2 sigma 1 had and u2 sigma 1 tail gives exactly the same expected payoff well that means she's going to be indifferent between p uh sorry head and tail while in fact any queue in between 0 1 is a best response exactly this sort of same analogy as the players won player one's uh uh sort of best response calculations so once again once i have all this so what does this inequality tells the second guy's expected payoff from playing head is 1 minus 2p greater than her expected pair of playing tail 2 minus 2p minus 1. so that's equivalent to saying p is less than uh one half all right so therefore again let's suppose this is one half so whenever p is less than one half her best response is q equals one so uh where's q equals one here's q equal well let's let's choose a different color because it's gonna uh mix up otherwise so this is q equals one as long as p is less than zero well do i have to rewrite those inequalities again and again not really i know that if that if this means p is less than one half this should mean p is greater than one half and this should mean p equals one half all right so whenever p is greater than one half the best response of the second player is uh zero q equals zero so that means this part and whenever uh p is equal to exactly equal to one-half all the cues are best response okay so this uh i know the the symbol uh does not resonate with good memories but i mean uh it has nothing to do with it um so this is exactly the the i mean i hope the cl the the colors are clear uh i well i do have red maybe i should have tried red okay so the so this one okay so this one is the best response of the second player all right so that's it uh in a sense why well because remember according to definition of nash equilibrium so let me clear some space here i mean this is not exactly the definition i gave you but they're identical so sigma i has to be best response for player i to sigma minus i uh for all i right so what does that mean that means sigma 1 sigma 2 is a nash equilibrium if and only if sigma 1 is the best response to sigma 2 and then sigma 2 is the best response to for player 2 to sigma 1. all right so that means the point of intersection of these two indifference curves are going to give me the nash equilibrium right always so here these two best response functions correspond only at one point which is this right otherwise they do not they do not cross one another so that means this point is the only nash equilibrium of this game so what does this point corresponds to this point corresponds to p equals one health q equals one-half so i actually found p equals one-half q equals one-half this is the nash equilibrium if you like you can write it this way sigma one is equal to this uh one half one half so meaning uh he's gonna play head and tail with equal probabilities and sigma two is gonna play uh one half one house so this is q this is 1 minus q so this sigma 1 sigma 2 profile is the nash equilibrium and the only nash equilibrium again y only again this is the only point that where the both best responses uh intersect all right so i want to say so that's it that's the end of our analysis and this is exactly how we find the mixed strategy nash equilibrium okay