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.