0:00

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,

Â 6:31

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

Â 9:27

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.

Â