2-5 Example: Mixed Strategy Nash

Loading...

From the course by Stanford University

Game Theory

1669 ratings

Stanford University

Game Theory

1669 ratings

Popularized by movies such as "A Beautiful Mind," game theory is the mathematical modeling of strategic interaction among rational (and irrational) agents. Beyond what we call `games' in common language, such as chess, poker, soccer, etc., it includes the modeling of conflict among nations, political campaigns, competition among firms, and trading behavior in markets such as the NYSE. How could you begin to model keyword auctions, and peer to peer file-sharing networks, without accounting for the incentives of the people using them? The course will provide the basics: representing games and strategies, the extensive form (which computer scientists call game trees), Bayesian games (modeling things like auctions), repeated and stochastic games, and more. We'll include a variety of examples including classic games and a few applications. You can find a full syllabus and description of the course here: http://web.stanford.edu/~jacksonm/GTOC-Syllabus.html There is also an advanced follow-up course to this one, for people already familiar with game theory: https://www.coursera.org/learn/gametheory2/ You can find an introductory video here: http://web.stanford.edu/~jacksonm/Intro_Networks.mp4

From the lesson

Week 2: Mixed-Strategy Nash Equilibrium

pure and mixed strategy Nash equilibria

2-1 Mixed Strategies and Nash Equilibrium (I) 2:34

2-2 Mixed Strategies and Nash Equilibrium (II)14:00

2-3 Computing Mixed Nash Equilibrium 11:45

2-4 Hardness Beyond 2x2 Games - Basic 5:12

2-4 Hardness Beyond 2x2 Games - Advanced 20:50

2-5 Example: Mixed Strategy Nash 10:33

2-6 Data: Professional Sports and Mixed Strategies 10:44

Meet the Instructors

Matthew O. Jackson
Professor
Economics
Kevin Leyton-Brown
Professor
Computer Science
Yoav Shoham
Professor
Computer Science

Hi folks. This is Matt Jackson again and so now let's take a look at Mixed

Strategy Nash Equilibrium in practice and try and understand a little bit about

what it should tell us about what we should expect to see.

So let's start with situation of soccer penalty kick.

Kicks, and this is a quite natural application of mixed strategy equilibria

because they're ubiquitous in sports and competitive games, so situations where it

actually pays to be unpredictable. So, by not knowing what the other, the

opposition is going to do. It makes it a little more difficult to

for you to pick it up the most strategy in these games where one player wins and

the other player looses. And, in particular in soccer penalty

kicks, were, looking at a situation where a kicker has to try and kick the ball

into a goal, the goalie can try to move to deflect the ball, and this happens

very quickly, so it's essentially a simultaneous move game.

The kicker is choosing to go either in, in their simplified version say to to the

right or the left. The goalie is then going to dive to the,

to one side or the other side and try to deflect the ball and if the goalie,

guesses correctly and ends up in the same.

Direction as the, the kicker, then they have a high chance of, higher chance of

saving it. If they go in the opposite direction,

they have a lower chance of saving it. Okay, so, how, how are equilibria going

to adjust to the skills of the players? So, let's suppose, for instance, as a

kicker That I might be biased. I might be able to kick the ball more

accurately in 1 direction than the other. So if you ask me to kick it towards the

left side of the goal, it might be that I hit there very accurately.

If you tell me I have to kick it towards the right side of the goal, it could be

that I'm less accurate. And I have a higher chance of just

missing the goal altogether. So is the equilibrium going to change

when we change one of the players, in terms of their skills.

So let's have a, a, a peek at this. Should a kicker who kicks penalty kicks,

worse to the right than the left, kick more often to the left than the right?

So, if I, if I'm worse in kicking towards the right, does that mean that I should

kick in the opposite direction more often? Well that's have a peak.

So, let's start with just a simple version just to get, our ideas fixed, so

imagine that the, setting is one where the kicker and the goalie, if they, so

let's have the kicker on this side. so the kicker is the role player, the

goalie is the column player and if they end up kicking, if the kicker goes left

and the goalie also happens to go to the left, then the goalie saves.

And the goalie gets a payoff of 1. The kicker gets a payoff of zero, if

instead we're in a situation where say the kicker goes left and the goalie goes

right, then the kicker scores and gets a path of 1, and, and so forth.

Okay. So this is just a simple variation on

matching pennies, and in this situation, what's the equilibrium going to be.

The equilibrium's going to be quite simple.

It's just going to be that the kicker randomizes equally between left and

right. The goal randomizes between left and

right. Each person has a probability of half to

win from kicking to the left or right, Goalie to the left or right.

So it's a very simple game, and we're have a good idea of how to solve that

one. Okay, so now what're we going to do?

Let's change things and now we've got a kicker that sometimes misses when they go

to the right. So imparticular if the goalie happens to

go to the left. And the goals wide open to the right.

The kicker scores 75% of the time, but actually misses completely 25% of the

time. Okay, so this is the, a, a kicker who's

still . does well if, if they go left and the

goalie goes to the opposite direction. But now they have a lower probability of

winning when their kicking right and they have a wide open goal.

Okay, so how should this adjust, whats, what Should the new equilibrium look

like? So let's suppose let's first of all try and keep the kicker indifferent.

So let's think of the goalie going left with probability P, right with

probability 1 - P. For the kicker to be indifferent what has

to be true? Well what's their payoff if they go left? Their payoff to going left.

Left is just 1 x 1 - P. There kick-off, there payoff to going

right is .75 x P. These 2 things have to be equal, in order

to have this, thee kicker being different.

So what do we end up with? We end up with .75P is equal to 1 - P.

so we end up with, 1 = 1.75p. or p is = to 1 over 1.75.

Which is = to, 4 over 7. Okay? So that tells us that the.

Goalie should be going left with probability 4/7, and right with

probability 3/7. Okay? So we know what the goalie's

supposed to be doing, so, so now the fact that we changed, the goalie's payoffs

haven't changed, but the fact that we changed the kicker's payoffs, meant that

the goalie actually had to adjust. Right? So even though the goalie's

payoffs haven't changed at all in this game, the new equilibrium has a different

set of, of probabilities for the goalie in order to keep the kicker at different

now. Okay? So now let's, let's see what the

kicker's going to do. So how are we see what's so, so let's

suppose that the kicker goes left with probability q, right with probability 1 -

q, and let's solve for q. Well, for the goalie to be indifferent,

what is their payoff if they go left? If they're going left, they're getting and

they're getting a q probability that they match.

So they get q + 0.25(1 - q) if they go left.

If they go right instead what are they getting? They're just getting 1 minus q.

Right? So these 2 things have to be equal so we end up with, q = .75 * (1 - q).

So q / (1 - q) = .75. What does this tell us about q? It tells

us that q = 3/7. Okay, so what's going to happen, when we

work out this? We get 3/7 for the probability that the kicker's going to go

left. And 4/7 for the probability that the

kicker is going to go right. So overall what do we have now? We have

the strategies looking like this as we made this adjustment.

And we notice two sort of interesting things about this.

one is that the goalie's pay-offs didn't change, but they still had to adjust

their strategies. And the second is that the kicker is

actually kicking more often to the weaker side, right? So the, the, the right foot

got worse than it was before and they are actually going in that direction more

often. and why is that? It's because the kicker,

the, the goalie has also made an adjustment in this game.

And so, the, the comparative statics in mixed strategy Nash equilibria are

actually quite subtle, and somewhat counter intuitive in terms of what you

might expect you're, you're, you get a bias so that this becomes a weaker

direction, and the equilibrium adjusts. So that the player goes in that direction

more often. So, let's have a, a look just through the

intuition here. Again the goalie strategy must have the

goalie indifferent and so when we went through those payoffs, the kicker, the

goalie goes left more often than right, and the kicker, actually, so sorry

there's a type here. The kicker, actually goes right More

frequently, right, goes right with probability now 4/7, so they've increased

their probability on that. And when we end up, what we see is the

goalie's strategy is adjusting, but we also see that the kicker adjusts to

kicking more toward their weak side. so the, the goalie now actually has a

slight advantage. So if you go through and calculate the

probability that the goalie's going to win, they're going to win 4/7, so the

time in this, in this match. And, and we can think what would happen

if the goalie Actually just stayed with our old strategy of still going 50 50.

Then the kicker could always go left, and win 1/2 the time instead of 3/7.

So the, the fact that the goalie has to make an adjustment is because they have

to de, defend more to the left side to defer because now the, the, the kickers

has a, a better Chance of winning on that side.

So the goalie goes more in that direction.

That pushes the kicker towards their weaker side.

In order to make sure that the goalie is willing to go to the left side with

higher frequency. So, by adjusting to strategy to keep the

kicker indifferent the goalie takes advantage of the kicker's weak right kick

and wins more often. Often.

Okay, so just in terms of summary and, and mixed strategy in soccer penalty

kicks, in general. Players must be indifferent between the

things that they're randomizing over. that produces very interesting and subtle

Comparative statics. and you know there, there's a question

that might come up in your mind, do people really do this? I mean, this is

fairly complicated, right? So the, you know, 50-50 we can figure out one we get

these, to these games where a player has an advantage The advantage 1 way or

another, then the actual mixture becomes fairly complicated.

And it's not so obvious that players will actually do that.

so we'll, we'll take a look at that and see if, if this actually bears out in, in

practice.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play