In this video, we're going to look at how to compute the Mixed Nash Equilibria of a normal form game. And, in particular, we're going to go through the example of battle of the sexes. So, what you've seen so far about equilibria, kind of suggests that it's really easy to come up with an equilibrium, but in fact, as games get big and general, sometimes it can be pretty tricky to find the equilibria of a game. And Nash's theorom is kind of a funny theorom, because it tells us that something exists, but it doesn't tell us how to find it. It just tells us that it has to be there. It's a nonconstructive argument. So, what I'm going to tell you today is sort of a starting point to finding an equilibrium, which is enough that it works in small games. and, in fact, you can turn this into a general algorithm, but not necessarily the most efficient or, or insightful way of finding equilbria. So, what I want to tell you today is that it's easy to compute a Nash equilibrium if you can guess what the support of the equilibrium is. So, recall what a support is. A support is the set of pure strategies that receive positive probability under the mix strategy of the play, of the players. So, a an equilibrium support is a set of actions that occur with positive probability. For example, that might be the support of an equilibrium. So, for battle of the sexes, let's guess that the support, whoops, let's guess that the support of the equilibrium is all of the actions. So let's look and intuitively, that, if there's going to be a mixed strategy equilibrium of this game, that, that looks like what it should be. So let's guess that that's the support and then try to reason about what the equilibrium would have to be given that support. So let's just introduce some notation to make this work. Let's let player 2 play B with probability p, and F with probability 1 - p. Now, if player 1 is going to best respond to this mixed strategy whatever it is and be playing a mixed strategy in response, then we can reason that player 2 must have set p and 1-p in a way that makes player 1 indifferent between his own actions, B and F. So this is an important point in reasoning about how mixed strategies work, so I encourage you to stop the video at this point and just think about why that would be true before I tell you the answer. So the reason why player 1 needs to be in oh, I don't have the answer on this slide, I'll just tell you. the reason why player 1 needs to be indifferent is that he's playing himself a mixed strategy, which means some of the time he's playing B and some of the time he's playing F. Right? Because these are both in the support, they both get played with nonzero probability, and if this is an equilibrium, then this is the best response that player 1 is playing. Well, if player 1 can play B some of the time and F some of the time and be playing a best response, he must be indifferent between playing B and F. If he's not indifferent, if let's say B is better, then he could get even more utility by reducing the amount of probability he puts on F and increasing the amount of probability he puts on b. And in fact, he could get the most utility by putting absolutely no utility on F and just all of the utility on B. So the only way that he would actually want to play a mixed strategy is if it's just the same for him to play B and F. So that means that we can reason that player 2 has set his probabilities p and 1 - p in such a way that it makes player 1 indifferent. And the reason why we've bothered to think about this is we can actually write that down in math. So we can say the utility for player 1 of playing B, and here, I'm kind of abusing notation, you should really understand this to mean the utility for player 1 of playing B given that player 1 plays p, 1 - p is equal to the utility of player 1 for playing F, again, given that player 2 plays p, 1 - p. So, then we can, we can simply expand this out taking into account the actual payoffs of the game and learn something useful. So we can say, if it's the case given the same probabilities p and 1 - p, that player 1 is indifferent to playing B and playing F. Then, that means well when he plays B, then he gets 2 with probability p, and he gets 0 with probability 1 - p. So that's what we have written down here. And when he plays F, he gets 0 with probability p, and 1 with probability 1 - p, and that's what we have written down here. And now we just have a simple equation and one variable, so if we rearrange it, we end up concluding that the only way that player 1 can be indifferent between playing B and, B and F is if p = 1/3. In the same way, we can reason that if player 2 was randomizing which we had just assumed that he was, then player 1 must make him indifferent. And, why is player 1 willing to randomize? Because he's simultaneously being made indifferent by player 2. So, so now lets say that player 1 plays B with probability q and place F with probability 1 - q. So, now we can just do the same thing as before, where, again, you should understand this to mean q, 1 - q, and likewise here and we can say, we can just expand it out in the same way. So if player 2 plays B, then he gets 1 with probability q, and he gets 0 with probability 1 - q. And if he plays F, he gets 0 with probability q, and 2 with probability 1 - q We now again have an equation in one variable, and we can rearrange it, and find that q = to 1/3. And, the important thing to notice that happened is that player 1 and player 2 were both willing to randomize, so we ended up getting out numbers here that made sense. We ended up getting p's and q's that were probabilities, they were between 0 and 1, and that means it's actually possible to set them in such a way that player 1 and player 2 actually would be indifferent. If the payoffs were different, we might have gotten something out here, like 13, and if q is 13, it means that B would have to happen 13 times more often than F for player 1 to be indifferent. And because that's not a probability, what that would really be telling us is there's no way of making the, the other player indifferent, and that would tell us there can't be an equilibrium with this support. But what we got out was interpretable as a probability and that means there is an equilibrium with this support, because what we've seen is, if player 1 plays this way and player 2 plays this way, then they each make each other indifferent. And if they both make each other indifferent, then they're both willing to play these mix strategies. And so, in the end, this mixed strategy profile is a Nash equilibrium. And so what we've done then is to compute a Nash equilibrium after having guessed a support, which is what we set out to do. So the last thing I want to think about here is what does it mean to play a mixed strategy? Turns out there are different interpretations. And, and now that you can really see, kind of the mechanics of what's going on inside a mixed strategy, you, you're sort of better ready to understand some of these different interpretations. So the first and kind of most natural, is kind of the one that is going on in the matching pennies example and that is that you randomize to confuse your opponent. So, in matching pennies, we each want opposite things and the only way we can be in equilibrium with each other is if you have some kind of uncertainty about what I'm going to do. If you know for sure that I'm playing heads, you just know for sure what you're going to do and it's something that I don't like and so there's no pure strategy in this game. So the only way that we can be in equilibrium is if we're both a bit confused about each other, but, that doesn't really describe, what just happened in the matching penny sorry, the battle of the sexes example that we just played. Here, the other player and I kind of want to coordinate the situation where we both end up in different places, where one of us goes to the football game, and the other one of us goes to the ballet is kind of an unhappy thing for both of us. What we both prefer is that we're both in the same place. And, the, the only kind of strategic element of the game comes from the fact that we have different preferences about our most preferred activity. So, in the mixed strategy equilibrium here, it, it's kind of an unhappy thing, because, of course, when we played this 2/3, 1/3 equilibrium that we just looked at in battle of the sexes where we have 2,1, 0, 0, 1,2 if were mixing, there's some possibility that were actually going to end up in these uncoordinated outcomes that neither of us likes. That's just sort of an unhappy thing about the fact that we're playing a full support equilibrium. But and so it can't be that we're randomizing to deliberately to confuse each other, instead, we should really understand this randomization as reflecting uncertainty. So if I am uncertain about the other person's action, then, and then I best respond given that uncertainty and I do that in a way that leaves you kind of uncertain in a particular way. We can also find ourselves in balance. That's really the way that I understand the stability of the equilibrium in battle of the sexes, that if we make each other uncertain in a precise way, we can find ourselves, in balance. Even though we would really like it better if we were just to end up in the, in one of these pure equilibrium. There are two other interpretations that I'll mention here just to be complete. we can also think of mix strategies as a concise description of what would happen if really nobody randomizes but we just play the came repeatedly. So, you can think of a mix strategy as the count of the pure strategies that will occur in the limit. and you can see how that that might also describe what happens in the battle of the sexes game where if we're just sort of bouncing back and forth between the differnet strategies weighting ourselves in that 2/3, 1/3 kind of way, we would be in equilibrium and sometimes we would miscoordinate. The last interpretation is that mixed strategies describe a population dynamics. So, if it's the case that we have whole populations of player 1s and whole populations of players 2s and we sample player from the population each of them has a deterministic strategy. The mixed strategy can be an interpretation of those population proportions. So, if it's the case that the one population has 2/3 Bs and 1/3 Fs, the other population has 1/3 Bs and 2/3 Fs. If we were sampling those populations, those populations would be in equilibrium relative to each other. So, that's another story we can tell that explains what equilibria might mean, what it means to be playing a pure strategy sorry, mixed strategy and to be in equilibrium there. And that, that concludes our discussion of how to compute mixed strategy equilibria.
