
Title:
15. Backward induction: chess, strategies, and credible threats

Description:
Game Theory (ECON 159)
We first discuss Zermelo's theorem: that games like tictactoe or chess have a solution. That is, either there is a way for player 1 to force a win, or there is a way for player 1 to force a tie, or there is a way for player 2 to force a win. The proof is by induction. Then we formally define and informally discuss both perfect information and strategies in such games. This allows us to find Nash equilibria in sequential games. But we find that some Nash equilibria are inconsistent with backward induction. In particular, we discuss an example that involves a threat that is believed in an equilibrium but does not seem credible.
00:00  Chapter 1. First and Second Mover Advantages: Zermelo's Theorem
10:17  Chapter 2. Zermelo's Theorem: Proof
17:06  Chapter 3. Zermelo's Theorem: Generalization
31:20  Chapter 4. Zermelo's Theorem: Games of Induction
40:27  Chapter 5. Games of Perfect Information: Definition
01:01:56  Chapter 6. Games of Perfect Information: Economic Example
Complete course materials are available at the Open Yale Courses website: http://open.yale.edu/courses
This course was recorded in Fall 2007.

Professor Ben Polak: So
last time we finished up by

playing the game of Nim and
you'll remember,

I hope, that the game of Nim
was a game where there was two

piles of stoneswe made do with
lines on the boardand the

winner was the person who picked
up the last stone.

Remember you had to pick piles.
I want to use the game of Nim

to make a transition here.
So what we had pointed out

about the game of Nim was it
illustrated very nicely for us

that games can have first mover
advantages or they can have

second mover advantages.
A very small change in the

game, essentially a very small
change in where we started from,

could switch a game from a game
with a first mover advantage to

a game with a second mover
advantage.

Now today, I want to just draw
a slightly grander lesson out of

that game.
So not only was it the case

that the game sometimes has
first mover advantages and

sometimes has second mover
advantages,

but moreover,
we could tell when it had a

first mover advantage and we
could tell when it had a second

mover advantage.
Is that right?

When we actually looked at the
initial set up of those stones,

we knew immediately that's a
game in which Player 1 is going

to win,
or alternatively,

we knew immediately that's a
game which Player 2 is going to

win.
Now it turns out that that idea

is very general and actually has
a name attached to it,

and that name is Zermelo.


So today we'll start off by
talking about a theorem due to a

guy called Zermelo,
and the idea of this theorem is

this.
We're going to look at games

more general than just Nim,
and we're going to ask the

question,
under what circumstances would

you know about a game either
that Player 1,

the person who goes first,
can force a win,

or that Player 2 can force a
win, or will allow a third

possibility,
which is it's going to be a tie.

So here's the theorem,
suppose there are two players

in this game,
like the games that we looked

at last time,
and supposeI won't define

this formally nowbut suppose
the game is a game of perfect

information.
So what do I mean by perfect

information?
I'll define this later on in

the class, but for now all I
mean is, that whenever a player

has his turn to move,
that player knows exactly what

has happened prior in the game.
So, for example,

all these sequential move games
we've been looking at are moves

of perfect information.
When I get to move I know

exactly what you did yesterday,
I know what I did the day

before yesterday and so on.
So it's a game of perfect

information.
I'm going to assume that the

game has a finite number of
nodes.

So two things here,
it can't go on forever,

this game, and also there's no
point in which it branches in an

infinite way.
So there's a finite number of

nodes, and we'll assume that the
game has three possible

outcomes.
Actually there's a more general

version of this theorem but this
will do for now.

The three possible outcomes are
either a win for Player 1,

so I'll call it W_1,
or a loss for Player 1,

which is obviously a win for
Player 2, or a tie.

So the gamelike Nim last
time, that only had two

outcomes.
So here we're going to look up

to three outcomes or three or
fewer outcomes I should say.

So these are the conditions and
here's the result.

So I said three,
it could be three but it could

also be two here,
I'm just allowing for three.

(One is trivial.) So under
these conditions the following

is true.
Either Player 1 can force a

win, so either it's the case
that this game is a game that if

Player 1 plays as well as they
can,

they're going to win the game
no matter what Player 2 does.

Or 1 can at least force a tie,
which means Player 1 can play

in such a way that they can
assure themselves of a tie

regardless of what Player 2
does.

Or it could be a game in which
2 can force a loss on 1,

so a win for 2.
So this theorem,

when you first look at it,
it doesn't seem to say very

much.
You're staring at this

thingyou might think,
we already knew that we're

looking at games that only have
three possible outcomes win,

loss, or tie so it doesn't seem
so surprising if you look at

this theorem,
it says,

well, you're going to end up
with a win, or a loss,

or a tie.
However, that's not quite what

the theorem says.
The theorem says,

not only are you going to end
up therewe knew that

alreadybut the games divide
themselves.

Games of these forms divide
themselves into those games in

which Player 1 has a way of
winning regardless of what

Player 2 does;
or games in which Player 1 has

a way of forcing a tie
regardless of what Player 2

does;
or Player 2 has a way of

winning regardless of what
Player 1 does,

so these games all have a
solution.

Let's just go back to Nim to
illustrate the point.

So in Nim actually there's no
tie so we can forget the middle

of these, and in Nim,
under certain circumstances it

is the case that Player 1 can
force a win.

Who remembers what the case
was, for when Player 1 can force

a win?
Anybody?

The people who played last time.
No, yes, Ale,

there's somebody here.
Shout it out.

Student: Insuring that
the piles are equal for the

other player.
Professor Ben Polak: All

right, so if the piles start
unequal, then Player 1 can

actually force a win.
So in Nim if the piles are

unequal at the start,
then 1 can force a win.

It really doesn't matter what 2
does, 2 is "toast."

Or the alternative case is the
piles are equal at the start,

and if they're equal at the
start then it's Player 1 who's

"toast."
Player 2 is going

toratherforce a loss on 1,
so 2 can force a loss on 1,

i.e.
a win for Player 2.

Does everyone remember that
from last time?

It's just before the weekend,
it shouldn't be so long ago.

So this theorem applies to all
games of this form.

So what games are of this form?
Let's try and think of some

other examples.
So one example is tictactoe.

Everyone know the rules of
tictactoe?

In England we call it Noughts
and Crosses, but you guys call

it tictactoe,
is that right?

Everyone know what tictactoe
is?

Yeah, which category is
tictactoe?

Is it a game which Player 1 can
force a win, or is it a category

in which Player 1 can only force
a tie,

or is it a category which you'd
rather go second and Player 2

can force a win for Player 2 or
a loss for Player 1?

Which is tictactoe?
Let's have a show of hands here.

Who thinks tictactoe is a
game in which Player 1 can force

a win?
Who thinks tictactoe is a

game in which Player 1 can only
force a tie?

Who thinks Player 2's going to
win?

Most of you are right.
It's a game in which if people

play correctly then it'll turn
out to be a tie.

So tictactoe is a game that
leads to a tie.

Player 1 can still make a
mistake, in which case they can

lose.
Player 2 can make a mistake in

which case they would lose,
but there is a way of playing

that forces a tie.
So these are fairly simple

games, let's talk about more
complicated games.

So what about the game of
checkers?

So the game of checkers meets
these conditions.

It's a two player game.
You always know all the moves

prior to your move.
It's finite:

there's some rules in checkers
that prevent it going on

forever.
And there are two or three

outcomes: I guess there's a
third outcome if you get into a

cycle you could tie.
So checkers fits all these

descriptions and what this
theorem tells us is that

checkers has a solution.
I'm not sure I know what that

solution is, or I think actually
somebody did compute it quite

recently,
even in the last few months,

I just forgot to Google it this
morning to remind myself.

But what this theorem tells us
even before those people that

computed it: checkers has a
solution.

Let's be a bit more ambitious.
What about chess?

So chess meets this description.
Chess is a two player game,

everybody knows all the moves
before them, it's sequential,

it has finite number of moves,
it's a very large number but it

is finite, and it has three
possible outcomes,

a win, a loss, or a tie.
So let's be careful,

the reason it's finite is that
if you cycleI forget what it

isthree times then the game is
declared a draw,

declared a tie.
So what's this theorem telling

us?
It's telling us that there is a

way to solve chess.
Chess has a solution.

We don't know what that
solution is.

It could be that solution is
that Player 1,

who's the player with the white
pieces can force a win.

It could be that Player 1 can
only force a tie,

and it could even be that
Player 2 can force a win.

We don't know which it is,
but there is a solution.

There's a catch to this theorem.
What's the catch?

The catch is it doesn't
actually tell usthis theorem

is not going to tell us what
that solution is.

It doesn't tell us how to play.
This theorem,

in and of itself,
doesn't tell us how to play

chess.
It just says there is a

way to play chess.
So we're going to try and prove

this.
We don't often do proofs in

class, but the reason I want to
prove this particular one is

because I think the proof is
instructive as part of sort of

QR at Yale.
So here's another example here,

and some other examples.
You could think of chess as

being the most dramatic example.


So the reason I want to spend
actually some time proving this

today is because we're going to
prove it by induction and I'm

going to sketch the proof.
I'm not going to go through

every possible step but I want
to give people here a feeling

for what a proof by induction
looks like.

The reason for this is,
my guess is,

well let's find out,
how many of you have seen a

proof by induction before?
How many have not?

So for those of you who haven't
I think it's a good thing in

life, at one point in your life
to see a proof by induction,

and for those who have,
my guess is you saw it in some

awful math class in high school
and it just went overit didn't

necessarily go over your head
but,

the excitement of it doesn't
catch on.

This is a context where it
might appeal.

So proof by induction.
We're going to prove this by

induction on the maximum length
of the game and we'll call that

N.
We'll call N the maximum length

of the game.
What do I mean by this?

If I write down a tree I can
always look at all the paths

from the beginning of the tree
all the way through to the end

of the tree.
And I'm going to look at the

path in that particular tree
that has the largest length,

and I'll call that the length
of the game, the maximum length

of the game.
So we're going to do induction

on the maximum length of the
game.

So how do we start a proof by
induction?

Let's just remind ourselves,
those people who have seen them

before.
We're going to prove that this

theorem this true,
the claim in the theorem is

true for the easy case when the
game is only 1 move long.

That's the first step,
and then we're going to try and

show that if it's true for all
games of length <

= N,
whatever N is,

then it must therefore be true
for games of length N+1.

That's the way you do a proof
by induction.

So let's just see how that
works in practice.

So let's start with the easy
step and we'll do it in some

detail, more detail than you
really need to in a math class.

So if N = 1,
what do these games look like?

Well let's look at some
examples here.

So I claim it's pretty trivial
if N = 1 but let's do it anyway.

So the game might look like
this.

Player 1 is going to
movehere's Player 1

movingthe game's only length
oneso Player 1's the only

player who ever gets to move.
So the game might look like

this.
Let's put in a fifth branch,

it might look like this.
And at the end of this game,

rather than putting payoffs let
me just put the outcomes.

So the outcome must either be a
win, or a tie,

or a loss, so suppose it looks
like this.

Suppose it's a win,
or here we could have a tie,

or here we could have a win
again, or here we could have a

loss, and here we could have a
tie.

So in this particular game I
claim it's pretty clear this

game has a solution.
It's pretty clear what 1 should

do.
What should 1 do?

1 should pick one of her
choices that leads to a win.

To be careful I'll put 1 in
here just to distinguish who it

is who's actually winning and
losing.

So in this game I claim that
this game has a pretty obvious

solution, either Player 1 is
going to choose this branch that

leads to a win or this branch
that leads to a win,

and either way Player 1 is
going to win.

Is that obvious?
It's so obvious,

it's kind of painful.
So I claim this game,

we could actually replace this
first node with what's going to

happen which is Player 1's going
to win.

Is that right?
That was easy.

Let's look at a different
example, we'll do three.

So here's another possible
example, and this again,

Player 1 is going to move here
and this time the possible

outcomes are tie,
or a loss, or a loss.

Once again it's a one player
game, this time he has three

choices and the three choices
lead to a tie or he loses,

so I claim once again this is
simple.

What Player 1 should do is what?
Choose the tie since there's no

way of winning.
But in that case he could

actually force it.
He could actually choose the

tie in which case he's going to
tie.

So this game has a solution
called choose the tie.

And again, we could replace the
first node of the game with

what's actually going to happen
which is a tie.

Everyone happy?
There's one other possibility I

guess.
The other possibility is that

here Player 1 has a lot of
choices, maybe four choices in

this case,
once again Player 1 is going to

move but in each
caseunfortunately for Player

1in each case the outcome is
that Player 1 loses.

So this is a game in which
Player 1 is going to lose no

matter what they do.
Once again it has a solution:

the solution is Player 1 is
toast and is going to lose.


So I claim this has really
captured all the possibilities

of games of length 1.
I mean you could imagine that

there could be more branches on
them, but basically there are

these three possibilities.
Either it's the case that one

of those branches leads to a
win, in which case the solution

is Player 1 wins;
or it's the case that none of

the branches have wins in them,
but one of them has a tie,

in which Player 1 is going to
tie;

or it's the case that all the
branches have loss in them,

in which Player 1's going to
lose.

So I claim I'm for done for
games of length one.

Everyone okay?
So that step is deceptively

easy but there it is.
All right, now we do the

inductive step,
the big step.

What we're going to do is we're
going to assume that the

statement of the theorem,
which I've now hidden

unfortunatelylet me unhide it
if I can, it's not going to be

easy.


This now visible?
So now let's assume that the

statement of this theorem is
true for all games length <

= N, suppose that's the case.
Suppose the claim is true for

all games of this type,
of length <= some N.

What we need to show iswhat
we're going to try and show is

therefore it will be true for
all games of length N + 1.

What we want to show iswe
claim, therefore,

it will be true for games of
length N + 1,

that's the key step in
inductive proofs.

All right, so how are we going
to do that?

Well let's have a look at a
game of length N + 1,

and obviously I can't use
thousands here so let me choose

from relatively small numbers,
but the idea will go through.

So let's have a look at a game.
So here's a game in which

Player 1 moves first,
Player 2 moves second.

Let's suppose that if Player 2
does this, then 1 only has

little choice here,
up here then one has a more

complicated choice,
and perhaps 2 could move again.

So this is quite a complicated
little game up here,

and down here let's make it a
little bit less complicated.

Here the game looks like this
and then comes to an end,

so the tree looks like this.
I haven't put the end,

I haven't put the outcomes on
it but the tree looks like this.

So how long is this tree first
of all?

Well I claim that the longest
path in this tree,

from the beginning to the end
has four steps.

Let's just check.
So one, two,

three, four that's what I claim
is the longest path.

Any path going down this way
only has three moves in it,

so this is a game of length
four.

So we can apply it to our
claim, let's assume that the

theorem holds for all trees
length three or fewer,

so that N + 1 is 4 for the
purpose of our example.

So in this exampleI don't
want to put it here,

let's put it herein this
example N = 3,

so that N + 1 = 4.
Everyone happy with this in the

example?
Now what I want to observe

about this is the following:
contained in this N + 1,

or the game of length 4 are
some smaller games.

You could think of them as
subgames.

They're games within the game,
is that right?

So let's have a look.
I claim, in particulardraw

around them in pinkthere's a
game here that follows Player 1

choosing Up and there's a game
here that follows Player 1

choosing Down,
is that right?

Okay, so these are both games,
and what do we have here?

So this little game in
herethe game in the top

circle, the game that follows
Player 1 moving upthat's a

game and it has a length.
So this little thing is a game

and I'm going to call it a
subgame, some jargon that we'll

be getting used to later on in
the semester.

It's a game within the game,
but it's basically just a game:

it's a subgame and this is a
subgame following 1 choosing

Uplet's put Up in
herefollowing up.

And I claim that this game has
a lengththis subgame has a

length.
So we knew that we started from

a game of length 4,
we've taken one of the moves,

and let's just make sure this
is actually a game of length 3.

So the game started here,
this would be a game of length

3 because you could go one,
two, three moves,

is that right?
So this is a game of length 3.

So this is a subgame following
1 choosing Up and it,

the subgame,
has length 3.

Down here, this is also a
subgame, it's a game that

follows Player 1 choosing Down
and this little subgame has

lengthnow here we have to be a
little bit carefulyou might

think that since we started from
a game of length 4,

after the first move we must be
in a game of length 3.

But actually that's not true,
and if we look carefully,

we'll notice that this game
down here, the game starting

here actually isn't of length 3.
It's of length 2.

Is that right?
So even though started from a

game of length 4,
by going this way we put

ourselves into a game of length
2.

Is that right?
So 1,2 or 1,2whateverit has

length 2.
Okay, all right so in this

example N is 3 and N + 1 is 4,
and our assumption,

our induction assumption is
what?

We've assumed that the claim of
the theorem holds for all games

<= N, which in this case
means <= 3.

So what does that tell us?
That tells us,

by our assumption,
this game, which I've put a

pink circle around on the top,
this is a game of length 3,

this game has a solution.
It must have a solution because

it's of length 3 or less.
So by the induction hypothesis

as it's calledby the induction
hypothesisthis is a technical

term, but what's the induction
hypothesis?

It's this thing.
By the assumption that we made

this game has a solution.
So it's a game of length 3,3

<= N in this case.
So this game must have a

solution.
Now I don't immediately know by

staring at it what it is,
but let's suppose it was W,

say it was W.
And the game down below,

this is also a game,
and it's a game of length 2 but

2 is less than 3 as well,
2 <= 3.

So this game also has a
solution.

This game also,
by the same assumption,

has a solution,
so its solution is sayI don't

knowmaybe its L.
So what does that mean to say

that these games have solutions,
in this case we're going to

assume W is this one,
and L is this one,

what does it mean?
It means that,

just as we did with the games
up there, we could put the

solution at the beginning of the
game.

We know that if we get into
this game, we're going to get

the solution of this game;
and we know if we get into this

game, we're going to get the
solution of this game.

So we can replace this one with
its solution which by assumption

was W, and this one by its
solution which by assumption was

L.
And here I want to be really

careful, I need to keep track of
which person it is it's a win or

loss for.
So this was a win for Player 1,

hence it was a loss for Player
2, and this was a loss for

Player 1, hence it was a win for
Player 2.

So these games,
each of them have some

solution, and this case I've
written down the solutions as W

or L.
So now what could we do?

Let me just bring down this
board again.

I can translate this game into
a very simple game.

I'm going to translate it up
here, so this game can be

translated as follows.
Player 1 moves,

if he goes Up then he hits a W
and if he goes Down he hits a L.

So in this particular example,
Player 1 is effectively

choosing between going Up and
finding himself in a game which

has a solution,
and the solution is he wins it,

or going Down and finding
himself in a game which has a

solution,
and the solution is he's toast.

But that's what?
That's a one move game.

So we know this has a solution,
and in particular,

he's going to choose Up.
This one has a solution.

This has a solution,
it is a game of length 1.

So what do we do?
Somewhat schematically,

we took a game of length N + 1,
in this case that was 4;

and we pointed out that once
Player 1 has made her first move

in this game,
we are in a game,

or in a subgame if you like,
that has length less than 4,

it could be 3,
it could be 2,

whatever.
Whatever subgame we're in,

by assumption,
that game has a solution.

So it's really effectively,
Player 1 is choosing between

going into a game with solution
W or going into a game with

solution L.
And if there were 15 other

subgames here,
each one would have a solution,

and each one Player 1 would be
able to associate that solution

with what he's going to
getwhat she's going to get.

So I claim that,
if it in fact is true that each

of these subgames of length 3
or less had a solution,

then the game of length 4 must
have a solution,

which is what?
It's the solution which is:

Player 1 should pick the best
subgame.

Are people convinced by that
step?

People are looking slightly
"deer in the headlamps" now,

so let me just say it again.
We started by assuming that all

games of length 3 or less,
or N or less,

have a solution.
We pointed out that any game

that has length N + 1 can be
thought of as an initial move by

Player 1 followed by a game of
length N or less,

N or fewer I should say.
Each of those games of N or

fewer steps has a solution,
so Player 1 is just going to

choose the game that has the
best solution for her and we're

done.
In this particular example,

Player 1 is going to choose Up
and therefore the solution to

this parent game is Player 1
wins.

Now the hard step I think in
proofs by induction is realizing

that you're done.
So I claim we're now done,

why are we done?
Well we know that it was pretty

easy that all games of length 1
have a solution.

That was pretty trivial.
And we've shown that if any

game of length of N or fewer has
a solution, then games of N + 1

have a solution.
So now let's see how we can

proceed.
We know that games of length 1

have a solution,
so let's consider games of

length 2.
Games of length 2,

do games of length 2 have a
solution?

Well let's set N = 1.
We know that if games of length

1 have a solution,
then any game of length 2 could

be thought of as an initial step
followed by a game of length 1,

but that has a solution,
so therefore games of length 2

have a solution.
Now let's think of games with

length 3, we've shown that games
with length 1 have a solution

and games with length 2 have a
solution.

Any game of length 3 can be
thought of as a game in which

there's an initial step followed
by either a game of length 1 or

a game of length 2,
each of which have a solution,

so once again a game of length
3 has a solution and so on.

So games of induction,
they work by building up on the

length of the game,
and we're ending up knowing

that we're done.
For those people who have never

seen a proof by induction don't
worry I'm not going to test you

on a proof with induction on the
exam,

I just wanted you to see one
once.

Let's all take a deep breath
and try and digest this a little

bit by playing a game.
I'll leave it up there so you

can stare at it.
We'll want it down again later.


Let's try and actually play a
game and see if we can actually

throw any light on this.
So I'm going to pick out

volunteers like I did last time,
but first of all,

let me tell you what the game
is.

So once again I'm going to have
rocks in this game,

and once again I'm going to
approximate those rocks with

marks on the blackboard.
So here's an example.

The example is this.
The game involves an array of

rocks, so here the array has
five rows and three columns.

So the rocks are not arranged
as they were before in piles,

but rather in a sort of in a
pretty array.

I should have made it more even
but this is: one,

two, three, four,
five rows;

and one, two,
three columns,

at least in this example.
But in general there's an array

of rocks, N x M.
We're going to play

sequentially with the players.
And the way the game is going

to work is thisis when it's
your turn to move,

you have to point to one of
these rocks and whichever rock

you point to I will remove.
I will delete that rock and all

the rocks that lie above or to
the right of it:

all the rocks that lie to the
northeast of it.

So for example,
if you pointed to this rock,

then I will remove this rock
and also this one,

this one, and this one.
If the next person comes along

and chooses this one,
then I will remove this one,

and also that one.
Okay, everyone understand?

All right and the game is
lostthis is importantthe

game is lost by the person who
ends up taking the last rock.

The loser is the person who
ends up removing the last rock.

Could I have some volunteers?
Can I volunteer people then?

How about the guy with the
white tshirt with the yellow on

there?
Okay, come on up front,

and who else can I volunteer.
Everyone's looking away from

me, desperately looking away
from me.

How about the guy with the Yale
sweatshirt on,

the Yale football sweatshirt
on, okay.

So come on up.
Your name is?

I should get a mike,
let me get a mike up here,

thank you.
Great, your name is?

Student: Noah.
Professor Ben Polak:

Noah and your name is?
Student: Koran.

Professor Ben Polak:Say
it into the mike.

Student: Koran.
Professor Ben Polak:

Koran okay.
So Noah and Koran are our

players.
Everyone understand the rules?

Do you understand the rules?
Yeah?

So why don't we make Noah go
first.

So Noah which rock are you
going to remove?

Remember the last rock loses.
Student: That one.

Professor Ben Polak:
That one.

Okay, so Noah chose this one.
So I'm going to remove this one

and the one above it.
Student: So all the

rocks to the north and east are
deleted, right?

Professor Ben Polak: All
the rocks to the north and east

of it are deleted.
That means youlast rock loses.

Okay good.
Student: That one.

Professor Ben Polak:
That one okay.

So now we have an L shape.
Student: That one.

Professor Ben Polak:
That one, all right.

Student: That one.
Professor Ben Polak:

That one okay,
okay.

All right so we're done.
Okay, everyone understand how

that worked?
Round of applause for our

players please,
thank you.

Let me get two more volunteers
now that everyone has seen it.

These guys had the hard job,
they had to figure it out cold.

Two more volunteers?
Oh I don't have to pick

volunteersthis is Yale,
somebody volunteer.

Are you volunteering?
Great.

I have one volunteer.
You can pick an opponent if you

like.
There you go thank you.

Your name is,
let's just wait until the mikes

are here.
So your name is?

Student: Peter.
Professor Ben Polak:

Peter and your name is Justin.
Student: Justin.

Professor Ben Polak: Let
me put a new array up here.

So let's put a new array up
here and this time let's make

itit doesn't have to be odd.
So let's make it this time a

little bit more complicated.
So we'll have fivelet's have

four rows and five columns this
time.

Okay so last time I had five
rows and three columns,

and this time I have four rows
and five columns.

Away you go,
let me move out of the way.

Why don't you stand a bit
nearer to the boardmake it a

little easier for people to see
what's going on,

there you go.
So Peter you want to go first?

Student: Sure, that one.
Professor Ben Polak:

That one okay.
So this one goes,

which means all of these go as
well.

Anyone got any advice from the
floor?

Shout things out, not too loud.


Student: I'll try going
here.

Professor Ben Polak:
There.

Okay we're back to our L shape
again here.

Now people can see what's going
on all right.

Student: I'll go here
and speed it up.

Professor Ben Polak: All
right thank you.

So a round of applause again.
Thank you guys.

So here's what I claim about
this game.

First, and this isn't a formal
claim, this is a lot harder than

the game we played last time,
right?

Everyone is convinced by that
all right.

So here's going to be an
exercise, or something that's a

challenge.
I may even put it formally on

the problem set this week,
but let me just say if I do put

this on the problem set this
week,

I don't expect you all to solve
it.

So if I do put it on the
problem set, it's an optional

problem.
But here's the challenge,

the challenge is,
I know from Zermelo's theorem

that no matter what N is,
and no matter what M is,

this game has a solution.
So Zermelo's theorem tells us

this game has a solution.
Now, notice it could have a

different solution depending on
the N and the M,

depending on how many rows and
how many columns,

is that right?.
So depending on N and M,

each such game has a
solutionis that rightwhich

could depend on N and on M,
on the number of rows and

columns.
So just as in Nim,

it depended on how those piles
started out.

So what's going to be the
homework assignment?

Find the solution.
Homework what is the solution?

So I claim, let me give you a
hint, I claim it is useful to

remember that there is a
solution.

It turns out to be useful to
remember that.

That wasn't much of a hint.
You knew that already,

but let me just emphasize that.
Okay, so I want to do a bit of

a transition now away from these
games like chess and like

checkers,
and like this game with the

rocks or Nim,
and I want to be a little bit

formal for a while.
So one thing that we haven't

done for a while,
actually since the midterm,

is write down some formal
definitions.

So I'm going to do that now.
I want at least one of these

boards back.


So as I warned very early in
the class, there are some points

of the day when we have to stop
and do some work and the next

twenty minutes or so is such a
point.


So what is this?
This is formal stuff.

The first thing I want to do is
I want to give you a formal

definition of something I've
already mentioned today and

that's the idea of perfect
information.

What we've been looking at,
or at least since the midterm,

are games of perfect
information.

So a game of perfect
information is one in which at

every node, or at each node in
the game the player whose turn

it is to move at that node knows
which node she is at.

So it's a very simple idea.
Every game we've seen since the

midterm has this property.
When you're playing this game

you know where you are.
So you know which node you're

at, you know what your choices
are and what that means

implicitly is she must know how
she got there.

So the whole history of the
game is observed by everybody.

When I get to move I know what
you did yesterday,

I know what I did the day
before yesterday,

and if I'm playing with a third
person I know what they did the

day before that.
So a very simple idea but it

turns out to be an idea that
actually allows us to use things

like backward induction very
simply.

Now so far all we've been doing
is thinking about such games,

games like perfect competition,
sorry games like quantity

competition between firms or
games like the games where we

were setting up incentives or
games like Nim,

and we've basically been
solving these games by backward

induction, rather informally.
What I want to add in now is

the notion of a strategy in
these games.

So when we had simultaneous
move games, strategies were

really unproblematic.
It was obvious what strategies

were.
But when we have games which

are sequential,
that go on over a period of

time,
and information is emerging

over a period of time,
we need to be a little careful

what we mean by a strategy.
So what I want to do is I want

to define a pure strategy at
least as follows.

So a pure strategy for Player i
in a game of perfect

informationso in the games
we've been talking about,

games which we can represent by
trees is what?

It's a complete plan of action.
So in other words,

what it does is it specifies
which action I should

takelet's not make it should
takelet's say will

take,
at each of i's nodes,

each of i's decision nodes.
So when you first read this

definition it seems completely
uninteresting and unproblematic.

A pure strategy for Player i
just tells you in this game

whenever you might be called
upon to move,

it tells you how you're going
to move.

So if you're going to move
three times in the game,

it tells you how you're going
to move the first time;

it tells you how you're going
to move the second time;

and it tells you how you're
going to move the third time.

So, so far none of this seems
difficult but actually it's a

bit more difficult than it
looks.

So let's have a look.


What I want to do is I want to
look at an example,

and this example I'm hoping is
going to illustrate some

subtleties about this
definition.


So here's an example.


In this example Player 1 moves
first and they can choose in or

out, or if you like let's call
it up or down since that's the

way we've drawn it.
So they can choose down or

upand I'll use capital letters
U and D.

If Player chooses U then Player
2 gets to move and Player 2 can

choose L or R.
If Player 1 moves U followed by

Player 2 choosing L,
then Player 1 gets to move,

in which case Player 1 could
move up or down and I'll use

little letters this time,
u and d.

Let's put some payoffs in this
game.

So the payoffs are 1,0 here,
0,2 here, 3,1 here and 2,4

here.
So on paperit's on the

boardwhen you first look at
it, this is a perfectly simple

game.
It's just like many of the

games we've been looking at
since the midterm.

It has a tree.
We could analyze it by backward

induction, and in a moment we
will analyze it by backward

induction.
But what I want to do first is

I want to say what are the
strategies in this game?

So let's start with Player 2
since it's easier.

Player 2's strategies here are
what?

Pretty simple:
player 2 only has one decision

nodehere's Player 2's decision
nodeand the strategy has to

tell Player 2 what he's going to
do at that decision node.

So there's only two choices,
L or R.

So Player 2's strategies are
either L or R.

Notice, however,
already one slight subtlety

here.
Player 2 may never get to make

this choice.
So Player 2 is choosing L or R,

but Player 2 may not ever get
to make this choice.

In particular,
if 1 chose D it's really

irrelevant whether Player 2 has
chosen L or R.

Nevertheless,
the strategy has to specify

what Player 2 would do were he
called upon to make that move.

Now let's look at Player 1's
strategies.


So what are Player 1's
strategies in this game?

Any takers?
Anyone want to guess?

So I claim it's tempting,
but it turns out to be wrong,

to say that Player 1 has three
strategies here.

It's tempting to say either
Player 1 moves D,

in which case we're done,
or Player 1 moves U,

in which case at some later
date she may be called upon to

choose u or d again.
So it's very tempting to think

that Player 1 has just three
strategies here,

D in which case we're done,
or U followed by either u or d,

if she's reached that point.
But actually,

if we follow this definition
carefully, we notice that Player

1 actually has four strategies
here.

So let me say what they are and
you'll see why it's a little

odd.
So here's one of the strategies

we talked about,
U followed by u,

and here's another one we
talked about,

U followed by d,
but I claim there are two

others, D followed by u and D
followed by d.

So what's a little weird about
this?

What's weird is we know
perfectly well that if Player 1

chooses D she's not going to get
to make the choice,

the second choice u or d.
But nevertheless the strategy

has to tell us what she would do
at every node,

regardless of whether that node
actually is reached by that

strategy.
Let me say it again,

the strategy has to tell you
what Player 1 would do at that

node,
regardless of whether that node

is actually reached by playing
that strategy.

So a little weird.
There's a bit of redundancy

here.
It's a bit redundant.

Now why?
Well we'll see why in a second.

Let's first of all consider how
this game will be played

according to backward induction.
So how do we play this game

according to backward induction?
Where do we start?

Shouldn't be a trick question,
where do we start the game

according to backward induction?
At the end okay.

So the end here is Player 1 and
Player 1 will choose here to go

d, is that right?
Because 3 is bigger than 2.

So if we roll back to Player
2's move, Player 2 if she

chooses L she knows that she'll
be followed by Player 1 going d,

in which case she'll get 1,
but if she chooses R she'll get

2.
So Player 2 will choose R.

So Player 1 here,
if she chooses U then Player 2

will choose R and Player 1 will
get 0, and if she chooses D

she'll get 1,
so Player 1 will choose D.

So, backward induction suggests
that Player 1 will choose D;

and followed by Player 2if
Player 2 did get to moveshe'd

choose R;
followed by Player 1if she

did get to move againchoosing
d again.

Notice that backward induction
had to tell us what Player 2

would have done had she got to
move.

Backward induction had to
consider what Player 2 would

think that Player 1 would have
done were Player 1 to get to

move again.
So to do backward induction,

Player 1 has to ask herself
what Player 2 is going to do;

and Player 2 has to therefore
ask herself what Player 1 would

have done;
which means Player 1 has to ask

herself what Player 2 thinks
Player 1 would have done;

which means we actually needed
to say what Player 1 did over

here.
Let me say that again.

So backward induction here
tells us that Player 1 chooses D

in which case the game is over.
But to do backward induction,

to think through backward
induction, we really needed to

consider not just what Player 2
was going to do were he to get

to move,
but also what Player 2 would

think Player 1 would do were
Player 2 to get to move and were

to do choose L.
So all of these redundant moves

were actually part of our
backward induction.

We need them there so we can
think about what people are

thinking.
So backward induction tells us

that the outcome of the game is
D, but it tells in terms of

strategies,
Player 1 chooses D and,

were she to get to move again,
would choose D again.

And Player 2 chooses R.
Now let's analyze this game a

totally different way.
We now know what the strategies

are in the game:
Player 2 has two strategies,

L and R;
and Player 1 has four

strategies: U/u,
U/d, D/u and D/d.

So let's write up the matrix
for this game,

so here it is.
It must be a 4 x 2 matrix,

Player 2 is choosing between L
and R and Player 1 is choosing

between her four strategies Uu,
Ud, Du and Dd and we can put

all the payoffs in.
So (Uu,L) gets us here which is

(2,4).
(Uu,R) gets us here which is

(0,2).
(Ud,L) gets us here which is

(3,1).
(Ud,R) gets us here again which

is (0,2).
And Du gets us,

going right out of the game
immediately, so we're going to

go to (1,0).
And in fact that's also true

for (Du,R), and it's also true
for (Dd,L) and it's also true

for (D/d,R).
So all of these four strategies

at the bottom started off by
Player 1 choosing D,

in which case the game is over.
So once again in this matrix

you can kind of see the
redundancy I was talking about.

In this matrix,
the third row,

the Du row looks the same as
the Dd row.

Everyone happy with that?
So when we've had matrices in

the past how have we solved the
game?

Well we've been doing this
backward induction stuff for a

couple of weeks,
but,

prior to the midtermif I had
given you this on the midterm

what would you have done?
You'd look for a Nash

Equilibrium right?
So let's do that:

let's look for Nash
Equilibrium.

So if Player 2 chooses L then
Player 1's best response is Uu;

and if Player 2 chooses R,
then Player 1's best response

is either Du or Dd.
Conversely, if Player 1 chooses

Uu then Player 2's best response
is L.

If Player 1 chooses Ud then
Player 2's best response is R.

If Player 1 chooses Du then
Player 2 doesn't care because

they're getting 0 anyway;
and if Player 1 chooses Dd then

again Player 2 doesn't care
because they're getting 0

anyway.
So the Nash Equilibria in this

game are what?
So one of them is here,

so that's one Nash Equilibrium.
One of them is Dd followed by

R, and that's a Nash Equilibrium
we actually found by backward

induction.
The Nash Equilibrium (Dd,R)

corresponds to the one we found
by backward induction.

But there's another Nash
Equilibrium in this game.

The other Nash Equilibrium in
this game is this one.

That's also a Nash Equilibrium.
What does it involve?

It involves Du and Rsorry Du
and R.

So what happened in that
equilibrium?

Player 1 went down which made
everything else kind of

irrelevant.
Player 2 played R and Player 1

in their plan of action was
actually going to choose u.

Say it again,
Player 1 in fact went D,

Player 2 had they got to move
would have chosen R and Player 1

had they got to move at this
second time would have chosen u.

So how can that be a Nash
Equilibrium?

It doesn't correspond to
backward induction.

In particular,
Player 1 up here is choosing a

strategy that seems silly.
They're choosing u rather than

d which gets them 2 rather than
3.

So how could it possibly be
that that's an equilibrium

strategy?
The reason isthe reason it

can be an equilibrium strategy
is it doesn't really matter what

Player 1 chooses up here from
Player 1's point of view because

it's never going to be reached
anyway.

As long as Player 2 is going to
choose R here,

it really doesn't matter what
Player 1 decides to do up there.

From Player 1's point of view,
it doesn't make a difference.

It isn't reached anyway.
So we're highlighting here a

danger, and the danger is this.
If you just mechanically find

the Nash Equilibria in a game,
you're going to find people

choosing actions that,
if they ever were called upon

to make them,
are silly.

Say it again,
if you just mechanically find

the Nash Equilibria in the game,
just as we did here,

you're going to select some
actions, in this case an action

by Player 1,
that were she called upon to

take that action would be a
silly action.

The reason it's surviving our
analysis is because in fact she

isn't called upon to make it.
Now to make that more concrete,

let's take this to an economic
example, this same idea.


So what I want you to imagine
is a market, and in this market

there is a monopolist who
controls the market,

but there's an entrant who is
thinking of entering into this

market.
So right now this market has a

monopoly in it,
and the monopolist is an

incumbentlet's call him
Incand an entrant who is

trying to decide whether or not
to enter the market or whether

to stay out.
If they stay out then the

entrant gets nothing and the
incumbent continues to get

monopoly profits.
So think of this as 3 million a

year.
If the entrant enters then the

incumbent can do one of two
things.

The incumbent could choose to
fight the entrant,

by which I mean charge low
prices, advertise a lot,

try and drive him out of the
market.

He could play very
competitively,

in which case the entrant will
actually make losses,

and the incumbent will drive
her profits down to zero.

Conversely, the incumbent could
choose not to fight.

If they don't fight then
they'll simply share the market

and they'll both make,
let's say Cournot profits or

duopoly profits of a million
each.

So in this game,
let's just say again,

there's a market there.
The monopolist is in the market

and the monopolist is making 3
million a year which seems

pretty nice for the monopolist.
The entrant is trying to decide

whether to invade this market.
If she invades this market,

if she's fought she's in
trouble, but if the monopolist

accommodates her,
then they just go to duopoly

profits and the entrant does
very well, gets a million

dollars in profit.
Let's have a look at this game.

Analyzefirst of all this
time, let's analyze it by Nash

Equilibrium.
So I claim in this game,

this is pretty simple:
the entrant has two strategies.

I'll put it straight into the
matrix.

The entrant has two strategies,
they're either to go in or to

stay out;
and the incumbent has two

strategies, they are either to
fight the entrant or not to

fight.
The payoffs of this game are as

followslet's put them in.
In and fight was (1,0),

in and not fight was (1,1) and
out led to the incumbents

maintaining the monopoly
profits.

Let's have a look at the Nash
Equilibria of this game.

So the first thing to do is to
look at the best responses for

the entrant.
So if the incumbent chooses

fight, then the entrant's best
response is to stay out.

If the incumbent chooses not
fight, then the entrant's best

response is to enter.
How about for the incumbent?

If the entrant chooses to come
in then the incumbent's best

response is not to fight because
1 is bigger than 0.

But if the entrant stays out it
really doesn't matter what the

incumbent does,
they'll get 3 either way.

So the Nash Equilibria here are
either in followed by not

fighting, you end up with a
duopoly, or out followed by

fighting.
Of course the fight doesn't

take place: out followed by "we
would have fought had you

entered."
So these are the Nash

Equilibria.
Let's analyze this game by

backward induction.
From the incumbent's point of

view, if the incumbent gets to
move then is she going to choose

fight or not fight?
She's going to choose not

fight, so the entrant should do
what?

Somebody?
The entrant should enter,

because if she enters she gets
1, if she stays out she gets 0.

So backward induction just
gives us this equilibrium.

Now the question is what do we
think is going on with this

other equilibrium?
Let's talk it through.

So here you are,
you're about to enter the

market, you leave Yale,
you set up your business,

and your business is
challenging some monopolist or

quasimonopolist like Microsoft
say.,

And you go out there and you're
about to put out your new

operating system.
And you know that your new

operating system will make
plenty of money provided

Microsoft doesn't retaliate and
drop its prices by half and

advertise you out of the market.
So what does Bill Gates do?

Bill Gates is the head of
Microsoft.

He says, wait a second before
you graduate from Yale and go

set up this company,
let me just tell you I'm going

to fight.
If you enter I'm going to fight.

And if you believe him,
if you believe that he's going

to fight, what should you do?
You're not going to bother to

enter his market.
And if you believe that you're

going to get fought by Bill
Gates then you believe that if

you enter you're going to make
losses,

so you choose to stay out.
And this threat that Bill Gates

makes here it doesn't cost him
anything, provided you go out,

he doesn't actually have to
fight at all.

That's why it is in fact an
equilibrium to imagine you

staying out believing that
you're going to get fought if

you enter,
and it is a best response for

the guy to fight knowing that
you're going to stay out.

But this doesn't sound right.
Why doesn't this sound right?

It doesn't sound right because
you really shouldn't believe the

guy who says he's going to fight
you when you know that if you

did enter fighting would cost
the incumbent money.

If you did enter,
if he fights you he gets 0,

if he doesn't fight he gets a
million dollars.

So this threat that the guy is
going to fight you,

this threat is not credible.
This is an equilibrium but it

relies on believing an
incredible threat.


It's true that if you think
about entering the market that

Microsoft is in,
you're very likely to get a

little email from Bill Gates.
(But it won't be an email

because that can be taken to
Court, but some little

threatening remark in your ear
from Bill Gates.) It's true if

you entered into the market that
the people who build aircraft

in,
the head of Boeing might pay

you a call one day or send
someone round,

but these threats are not
credible threats.

Is that right?
They're not credible threats

because we know that if you did
enter, it isn't in their

interest to fight.
They're making a lot of noise

about it but you know that if
you did enter,

backward induction tells us
they're not going to fight.

But now we're in slightly an
odd situation,

why are we in an odd situation?
Two things.

One, we seem to be finding that
there are Nash Equilibria in

gameswe found one here and one
up herethere are Nash

Equilibria that are not
supported by backward induction.

That's the first reason we're a
little worried here,

and the second reason we're
worried is even the economics of

this doesn't quite smell right.
For example,

if you in fact did
entersorry,

if you did in fact announce you
were going to operate,

you were going to build a new
operating system and got a

threatening phone call from Bill
Gatesthere might be a reason

why you might actually believe
that call.

Why might you believe that call?
Can we get a mike out,

I'll do it.
So why might you believe a call

from Bill Gates saying he's
going to beat you upnot beat

you up but he's going to charge
low prices if you produce an

operating system?
Student: If you look at

the future revenue streams,
like for the next ten years and

he consistently gets 1 million
dollars for the next ten years,

he would be better off if he
just drove you out of the market

for the first year and then get
3 million dollars for the next

nine years.
Professor Ben Polak:

That wasn't quite what I wasn't
thinking of.

Okay, it's true if we cheat a
bit and make one of theOkay,

so what you're saying is I
could get 3 forever versus 1

forever,
assume these are both present

discounted values of future cash
earnings.

So we've done the future cash
flow analysis of this.

So this isn't an accounting
mistake, not for accounting

reasons.
There's some other reason when

Gates threatens you,
you might want to believe it.

Let's try up here first.
Student: He can afford

to make an example of you so no
other people will invade.

Professor Ben Polak:
Right, so one thing that's in

Bill Gates' mind is right now,
he's thinking about competing

with you but down the road
there's a lot more of you guys

comingwhatever it is,
280 of you in this room and

there's another 280 in next
year's class and so on.

And Bill Gates knows that each
of you might come out and

threaten his monopoly,
his Microsoft monopoly.

And he might think that by
setting an example to one of you

he might be able to keep the
others out.

And somewhere that kind of
argument, the argument of making

an example of somebody is
missing here:

missing completely.
But it's got to be important,

it's got to be an important
idea.

So we're going to come back and
spend the first half of

Wednesday's class picking up
just precisely that idea.
