across a new idea, although it wasn't very new for

a lot of you, and that was the idea of Nash

Equilibrium. What I want to do today is

discuss Nash Equilibrium, see how we find that

equilibrium into rather simple examples.

And then in the second half of the day I want to look at an

application where we actually have some fun and play a game.

At least I hope it's fun. But let's start by putting down

a formal definition. We only used a rather informal

one last week, so here's a formal one.

A strategy profile--remember a profile is one strategy for each

player, so it's going to be S_1*,

S_2*, all the way up to

S_M* if there are M players playing the game--so

this profile is a Nash Equilibrium (and I'm just going

to write NE in this class for Nash Equilibrium from now on)

if, for each i –so for each

player i, her choice--so her choice here is S_i*,

i is part of that profile is a best response to the other

players' choices. Of course, the other players'

choices here are S_--i* so everyone is

playing a best response to everyone else.

Now, this is by far the most commonly used solution concept

in Game Theory. So those of you who are

interviewing for McKenzie or something, you're going to find

that they're going to expect you to know what this is.

So one reason for knowing what it is, is because it's in the

textbooks, it's going to be used in lots of applications,

it's going to be used in your McKenzie interview.

That's not a very good reason and I certainly don't want you

to jump to the conclusion that now we've got to Nash

Equilibrium everything we've done up to know is in some sense

irrelevant. That's not the case.

It's not always going to be the case that people always play a

Nash Equilibrium. For example,

when we played the numbers game, the game when you chose a

number, we've already discussed last

week or last time, that the equilibrium in that

game is for everyone to choose one,

but when we actually played the game, the average was much

higher than that: the average was about 13.

It is true that when we played it repeatedly,

it seemed to converge towards 1,

but the play of the game when we played it just one shot first

time, wasn't a Nash Equilibrium. So we shouldn't form the

mistake of thinking people always play Nash Equilibrium or

people, "if they're rational," play Nash Equilibrium.

Neither of those statements are true.

Nevertheless, there are some good reasons for

thinking about Nash Equilibrium other than the fact it's used by

other people, and let's talk about those a

bit. So I want to put down some

motivations here--the first motivation we already discussed

last time. In fact, somebody in the

audience mentioned it, and it's the idea of "no

regrets." So what is this idea?

It says, suppose we're looking at a Nash Equilibrium.

If we hold the strategies of everyone else fixed,

no individual i has an incentive to deviate,

to move away. Alright, I'll say it again.

Holding everyone else's actions fixed, no individual has any

incentive to move away. Let me be a little more careful

here; no individual has any

strict incentive to move away.

We'll see if that actually matters.

So no individual can do strictly better by moving away.

No individual can do strictly better by deviating,

holding everyone else's actions.

So why I call that "no regret"? It means, having played the

game, suppose you did in fact play a Nash Equilibrium and then

you looked back at what you had done,

and now you know what everyone else has done and you say,

"Do I regret my actions?" And the answer is,

"No, I don't regret my actions because I did the best I could

given what they did." So that seems like a fairly

important sort of central idea for why we should care about

Nash Equilibrium. Here's a second idea,

and we'll see others arise in the course of today.

A second idea is that a Nash Equilibrium can be thought of as

self-fulfilling beliefs. So, in the last week or so

we've talked a fair amount about beliefs.

If I believe the goal keeper's going to dive this way I should

shoot that way and so on. But of course we didn't talk

about any beliefs in particular. These beliefs,

if I believe that--if everyone in the game believes that

everyone else is going to play their part of a particular Nash

Equilibrium then everyone, will in fact,

play their part of that Nash Equilibrium.

Now, why? Why is it the case if everyone

believes that everyone else is playing their part of this

particular Nash Equilibrium that that's so fulfilling and people

actually will play that way? Why is that the case?

Anybody? Can we get this guy in red?

Student: Because your Nash Equilibrium matches the

best response against both. Professor Ben Polak:

Exactly, so it's really--it's almost a repeat of the first

thing. If I think everyone else is

going to play their particular--if I think players 2

through N are going to play S_2* through

S_N*--then by definition my best response is

to play S_1* so I will in fact play my part in the Nash

Equilibrium. Good, so as part of the

definition, we can see these are self-fulfilling beliefs.

Let's just remind ourselves how that arose in the example we

looked at the end last time. I'm not going to go back and

re-analyze it, but I just want to sort of make

sure that we followed it. So, we had this picture last

time in the partnership game in which people were choosing

effort levels. And this line was the best

response for Player 1 as a function of Player 2's choice.

And this line was the best response of Player 2 as a

function of Player 1's choice. This is the picture we saw last

time. And let's just look at how

those--it's no secret here what the Nash Equilibrium is:

the Nash Equilibrium is where the lines cross--but let's just

see how it maps out to those two motivations we just said.

So, how about self-fulfilling beliefs?

Well, if Player--sorry, I put 1, that should be 2--if

Player 1 believes that Player 2 is going to choose this

strategy, then Player 1 should choose

this strategy. If Player 1 thinks Player 2

should take this strategy, then Player 1 should choose

this strategy. If Player 1 thinks Player 2 is

choosing this strategy, then Player I should choose

this strategy and so on; that's what it means to be best

response. But if Player 1 thinks that

Player 2 is playing exactly her Nash strategy then Player 1's

best response is to respond by playing his Nash strategy.

And conversely, if Player 2 thinks Player 1 is

playing his Nash strategy, then Player 2's best response

indeed is to play her Nash strategy.

So, you can that's a self-fulfilling belief.

If both people think that's what's going to happen,

that is indeed what's going to happen.

How about the idea of no regrets?

So here's Player 1; she wakes up the next

morning--oh I'm sorry it was a he wasn't it?

He wakes up the next morning and he says, "I chose

S_1*, do I regret this?"

Well, now he knows what Player 2 chose;

Player 2 chose S_2* and he says, "no that's the best

I could have done. Given that Player 2 did in fact

choose S_2*, I have no regrets about

choosing S_1*; that in fact was my best

response." Notice that wouldn't be true at

the other outcome. So, for example,

if Player 1 had chosen S_1* but Player 2 had

chosen some other strategy, let's say S_2 prime,

then Player I would have regrets.

Player I would wake up the next morning and say,

"oh I thought Player 1 was going to play S_2*;

in fact, she chose S_2 prime.

I regret having chosen S_1*;

I would have rather chosen S_1 prime.

So, only at the Nash Equilibrium are there no

regrets. Everyone okay with that?

This is just revisiting really what we did last time and

underlining these points. So, I want to spend quite a lot

of time today just getting used to the idea of Nash Equilibrium

and trying to find Nash Equilibrium.

(I got to turn off that projector that's in the way

there. Is that going to upset the

lights a lot?) So okay, so what I want to do is I want

to look at some very simple games with a small number of

players to start with, and a small number of

strategies, and I want us to get used to how we would find the

Nash Equilibria in those simple games.

We'll start slowly and then we'll get a little faster.

So, let's start with this game, very simple game with two

players. Each player has three

strategies and I'm not going to motivate this game.

It's just some random game. Player 1 can choose up,

middle, or down, and Player 2 can choose left,

center, and right and the payoffs are

as follows: (0,4) (4,0) (5,3) (4,0) (0,4) (5,3) again (3,5)

(3,5) and (6,6). So, we could discuss--if we had

more time, we could actually play this game--but isn't a very

exciting game, so let's leave our playing for

later, and instead, let's try and figure out what

are the Nash Equilibria in this game and how we're going to go

about finding it. The way we're going to go about

finding them is going to mimic what we did last time.

Last time, we had a more complicated game which was two

players with a continuum of strategies,

and what we did was we figured out Player 1's best responses

and Player 2's best responses: Player 1's best response to

what Player 2's doing and Player 2's best response to what Player

1 is doing; and then we looked where they

coincided and that was the Nash Equilibrium.

We're going to do exactly the same in this simple game here,

so we're going to start off by figuring out what Player 1's

best response looks like. So, in particular,

what would be Player 1's best response if Player 2 chooses

left? Let's get the mikes up so I can

sort of challenge people. Anybody?

Not such a hard question. Do you want to try the woman in

the middle? Who's closest to the woman in

the middle? Yeah.

Student: The middle. Professor Ben Polak:

Okay, so Player 1's best response in this case is middle,

because 4 is bigger than 0, and it's bigger than 3.

So, to mark that fact what we can do is--let's put a

circle--let's make it green--let's put a circle around

that 3. Not hard, so let's do it again.

What is Player 1's best response if Player 2 chooses

center? Let's get somebody on the other

side. (Somebody should feel free to

cold call somebody here.) How about cold calling the guy with

the Yale football shirt on? There we go.

Student: Up. Professor Ben Polak: All

right, so up is the correct answer.

(So, one triumph for Yale football).

So 4 is bigger than 3, bigger than 0,

so good, thank you. Ale why don't you do the same?

Why don't you cold call somebody who's going to tell me

what's the best response for Player 1 to right.

Shout it out. Student: Down.

Professor Ben Polak: Down, okay so best response is

down because 6 is bigger than 5, which is bigger than 5;

I mean 6 is bigger than 5. So what we've done here is

we've found Player 1's best response to left,

best response to center, and best response to right and

in passing notice that each of Player 1 strategies is the best

response to something, so nothing would be knocked out

by our domination arguments here, and nothing would be

knocked out by our never a best response arguments here for

Player 1. Let's do the same for Player 2;

so why don't I keep the mikes doing some cold calling,

so why don't we--you want to cold call somebody at the back