INTMIC9.jpg
Chapter 29
Game Theory

Game Theory
uGame theory helps to model strategic behavior by agents who understand that their actions affect
the actions of other agents.

Some Applications of Game Theory
uThe study of oligopolies (industries containing only a few firms)
uThe study of cartels; e.g. OPEC
uThe study of externalities; e.g. using a common resource such as a fishery.

Some Applications of Game Theory
uThe study of military strategies.
uBargaining.
uHow markets work.

What is a Game?
uA game consists of
–a set of players
–a set of strategies for each player
–the payoffs to each player for every possible choice of strategies by the players.

Two-Player Games
uA game with just two players is a two-player game.
uWe will study only games in which there are two players, each of whom can choose between only two
actions.

An Example of a Two-Player Game
uThe players are called A and B.
uPlayer A has two actions, called “Up” and “Down”.

An Example of a Two-Player Game
uPlayer B has two actions, called “Left” and “Right”.
uThe table showing the payoffs to both players for each of the four possible action combinations is
the game’s payoff matrix.

An Example of a Two-Player Game
This is the
game’s
payoff matrix.
Player B
Player A
Player A’s payoff is shown first.
Player B’s payoff is shown second.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)

An Example of a Two-Player Game
A play of the game is a pair such as (U,R) where the 1st element is the action chosen by Player A
and the 2nd is the action chosen by Player B.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Player B
Player A

An Example of a Two-Player Game
E.g. if A plays Up and B plays Right then A’s payoff is 1 and B’s payoff is 8.
This is the
game’s
payoff matrix.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Player B
Player A

An Example of a Two-Player Game
And if A plays Down and B plays Right then A’s payoff is 2 and B’s payoff is 1.
This is the
game’s
payoff matrix.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Player B
Player A

An Example of a Two-Player Game
What plays are we likely to see for this game?
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Player B
Player A

An Example of a Two-Player Game
Is (U,R) a likely play?
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Player B
Player A

An Example of a Two-Player Game
If B plays Right then A’s best reply is Down since this improves A’s payoff from 1 to 2.  So (U,R)
is not a likely play.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Is (U,R) a likely play?
Player B
Player A

An Example of a Two-Player Game
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Is (D,R) a likely play?
Player B
Player A

An Example of a Two-Player Game
If B plays Right then A’s best reply is Down.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Is (D,R) a likely play?
Player B
Player A

An Example of a Two-Player Game
If B plays Right then A’s best reply is Down.
If A plays Down then B’s best reply is Right.
So (D,R) is a likely play.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Is (D,R) a likely play?
Player B
Player A

An Example of a Two-Player Game
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Is (D,L) a likely play?
Player B
Player A

An Example of a Two-Player Game
If A plays Down then B’s best reply is Right,
so (D,L) is not a likely play.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Is (D,L) a likely play?
Player B
Player A

An Example of a Two-Player Game
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Is (U,L) a likely play?
Player B
Player A

An Example of a Two-Player Game
If A plays Up then B’s best reply is Left.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Is (U,L) a likely play?
Player B
Player A

An Example of a Two-Player Game
If A plays Up then B’s best reply is Left.
If B plays Left then A’s best reply is Up.
So (U,L) is a likely play.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Is (U,L) a likely play?
Player B
Player A

Nash Equilibrium
uA play of the game where each strategy is a best reply to the other is a
                 Nash equilibrium.
uOur example has two Nash equilibria; (U,L) and (D,R).

An Example of a Two-Player Game
(U,L) and (D,R) are both Nash equilibria for
the game.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Player B
Player A

An Example of a Two-Player Game
(U,L) and (D,R) are both Nash equilibria for the game.  But which will we see?  Notice that (U,L)
is preferred to (D,R) by both players.  Must we then see (U,L) only?
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Player B
Player A

The Prisoner’s Dilemma
uTo see if Pareto-preferred outcomes must be what we see in the play of a game, consider the famous
example called the Prisoner’s Dilemma game.

The Prisoner’s Dilemma
What plays are we likely to see for this game?
Clyde
Bonnie
(-5,-5)
(-30,-1)
(-1,-30)
(-10,-10)
S
C
S
C

The Prisoner’s Dilemma
If Bonnie plays Silence then Clyde’s best reply is Confess.
(-5,-5)
(-30,-1)
(-1,-30)
(-10,-10)
S
C
S
C
Clyde
Bonnie

The Prisoner’s Dilemma
If Bonnie plays Silence then Clyde’s best reply is Confess.
If Bonnie plays Confess then Clyde’s best reply is Confess.
(-5,-5)
(-30,-1)
(-1,-30)
(-10,-10)
S
C
S
C
Clyde
Bonnie

The Prisoner’s Dilemma
So no matter what Bonnie plays, Clyde’s best reply is always Confess.  Confess is a dominant
strategy for Clyde.
(-5,-5)
(-30,-1)
(-1,-30)
(-10,-10)
S
C
S
C
Clyde
Bonnie

The Prisoner’s Dilemma
Similarly, no matter what Clyde plays, Bonnie’s best reply is always Confess.  Confess is a
dominant strategy for Bonnie also.
(-5,-5)
(-30,-1)
(-1,-30)
(-10,-10)
S
C
S
C
Clyde
Bonnie

The Prisoner’s Dilemma
So the only Nash equilibrium for this game is (C,C), even though (S,S) gives both Bonnie and Clyde
better payoffs.  The only Nash equilibrium is inefficient.
(-5,-5)
(-30,-1)
(-1,-30)
(-10,-10)
S
C
S
C
Clyde
Bonnie

Who Plays When?
uIn both examples the players chose their strategies simultaneously.
uSuch games are simultaneous play games.

Who Plays When?
uBut there are other games in which one player plays before another player.
uSuch games are sequential play games.
uThe player who plays first is the leader.  The player who plays second is the follower.

A Sequential Game Example
uSometimes a game has more than one Nash equilibrium and it is hard to say which is more likely to
occur.
uWhen a game is sequential it is sometimes possible to argue that one of the Nash equilibria is
more likely to occur than the other.

A Sequential Game Example
Player B
Player A
(U,L) and (D,R) are both NE when this game is played simultaneously and we have no way of deciding
which equilibrium is more likely to occur.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)

A Sequential Game Example
Suppose instead that the game is played sequentially, with A leading and B following.  We can
rewrite the game in its extensive form.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Player B
Player A

A Sequential Game Example
U
D
L
L
R
R
(3,9)
(1,8)
(0,0)
(2,1)
A
B
B
A plays first.
B plays second.

A Sequential Game Example
(U,L) is a Nash equilibrium.
U
D
L
L
R
R
(3,9)
(1,8)
(0,0)
(2,1)
A
B
B
A plays first.
B plays second.

A Sequential Game Example
U
D
L
L
R
R
(3,9)
(1,8)
(0,0)
(2,1)
A
B
B
A plays first.
B plays second.
(U,L) is a Nash equilibrium.  So is (D,R).
Is one equilibrium more likely to occur?

A Sequential Game Example
If A plays U then B follows with L; A gets 3.
U
D
L
L
R
R
(3,9)
(1,8)
(0,0)
(2,1)
A
B
B
A plays first.
B plays second.

A Sequential Game Example
If A plays U then B follows with L; A gets 3.
If A plays D then B follows with R; A gets 2.
U
D
L
L
R
R
(3,9)
(1,8)
(0,0)
(2,1)
A
B
B
A plays first.
B plays second.

A Sequential Game Example
If A plays U then B follows with L; A gets 3.
If A plays D then B follows with R; A gets 2.
U
D
L
L
R
R
(3,9)
(1,8)
(0,0)
(2,1)
A
B
B
A plays first.
B plays second.
So (U,L) is the
likely NE.

A Sequential Game Example
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Player B
Player A
This is our original example once more.  Suppose again that play is simultaneous.  We discovered
that the game has two Nash equilibria; (U,L) and (D,R).

A Sequential Game Example
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Player B
Player A
Player A has been thought of as choosing to play either U or D, but no combination of both; i.e. as
playing purely U or D.  U and D are Player A’s
pure strategies.

A Sequential Game Example
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Player B
Player A
Similarly, L and R are Player B’s pure strategies.

A Sequential Game Example
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Player B
Player A
Consequently, (U,L) and (D,R) are pure strategy Nash equilibria.  Must every game have at least one
pure strategy Nash equilibrium?

Pure Strategies
Player B
Player A
Here is a new game.  Are there any pure strategy Nash equilibria?
(1,2)
(0,4)
(0,5)
(3,2)
U
D
L
R

Pure Strategies
Player B
Player A
Is (U,L) a Nash equilibrium?
(1,2)
(0,4)
(0,5)
(3,2)
U
D
L
R

Pure Strategies
Player B
Player A
Is (U,L) a Nash equilibrium?  No.
Is (U,R) a Nash equilibrium?
(1,2)
(0,4)
(0,5)
(3,2)
U
D
L
R

Pure Strategies
Player B
Player A
Is (U,L) a Nash equilibrium?  No.
Is (U,R) a Nash equilibrium?  No.
Is (D,L) a Nash equilibrium?
(1,2)
(0,4)
(0,5)
(3,2)
U
D
L
R

Pure Strategies
Player B
Player A
Is (U,L) a Nash equilibrium?  No.
Is (U,R) a Nash equilibrium?  No.
Is (D,L) a Nash equilibrium?  No.
Is (D,R) a Nash equilibrium?
(1,2)
(0,4)
(0,5)
(3,2)
U
D
L
R

Pure Strategies
Player B
Player A
Is (U,L) a Nash equilibrium?  No.
Is (U,R) a Nash equilibrium?  No.
Is (D,L) a Nash equilibrium?  No.
Is (D,R) a Nash equilibrium?  No.
(1,2)
(0,4)
(0,5)
(3,2)
U
D
L
R

Pure Strategies
Player B
Player A
So the game has no Nash equilibria in pure strategies.  Even so, the game does have a Nash
equilibrium, but in mixed strategies.
(1,2)
(0,4)
(0,5)
(3,2)
U
D
L
R

Mixed Strategies
uInstead of playing purely Up or Down, Player A selects a probability distribution (pU,1-pU),
meaning that with probability pU Player A will play Up and with probability 1-pU will play Down.
uPlayer A is mixing over the pure strategies Up and Down.
uThe probability distribution (pU,1-pU) is a mixed strategy for Player A.

Mixed Strategies
uSimilarly, Player B selects a probability distribution (pL,1-pL), meaning that with probability
pL Player B will play Left and with probability 1-pL will play Right.
uPlayer B is mixing over the pure strategies Left and Right.
uThe probability distribution (pL,1-pL) is a mixed strategy for Player B.

Mixed Strategies
Player B
Player A
This game has no Nash equilibrium in pure strategies, but it does have a Nash equilibrium in mixed
strategies.  How is it computed?
(1,2)
(0,4)
(0,5)
(3,2)
U
D
L
R

Mixed Strategies
Player B
Player A
(1,2)
(0,4)
(0,5)
(3,2)
U, pU
D, 1-pU
L, pL
R, 1-pL

Mixed Strategies
Player B
Player A
(1,2)
(0,4)
(0,5)
(3,2)
U, pU
D, 1-pU
L, pL
R, 1-pL
A’s expected value of choosing Up is ??

Mixed Strategies
Player B
Player A
(1,2)
(0,4)
(0,5)
(3,2)
U, pU
D, 1-pU
L, pL
R, 1-pL
A’s expected value of choosing Up is pL.
A’s expected value of choosing Down is ??

Mixed Strategies
Player B
Player A
(1,2)
(0,4)
(0,5)
(3,2)
U, pU
D, 1-pU
L, pL
R, 1-pL
A’s expected value of choosing Up is pL.
A’s expected value of choosing Down is 3(1 - pL).

A’s expected value of choosing Up is pL.
A’s expected value of choosing Down is 3(1 - pL).
If pL > 3(1 - pL) then A will choose only Up, but
there is no NE in which A plays only Up.
Mixed Strategies
Player B
Player A
(1,2)
(0,4)
(0,5)
(3,2)
U, pU
D, 1-pU
L, pL
R, 1-pL

Mixed Strategies
Player B
Player A
(1,2)
(0,4)
(0,5)
(3,2)
U, pU
D, 1-pU
L, pL
R, 1-pL
A’s expected value of choosing Up is pL.
A’s expected value of choosing Down is 3(1 - pL).
If pL < 3(1 - pL) then A will choose only Down, but there is no NE in which A plays only Down.

If there is a NE necessarily pL = 3(1 - pL)  Þ  pL = 3/4;
i.e. the way B mixes over Left and Right must make A
indifferent between choosing Up or Down.
Mixed Strategies
Player B
Player A
(1,2)
(0,4)
(0,5)
(3,2)
U, pU
D, 1-pU
L, pL
R, 1-pL

If there is a NE necessarily pL = 3(1 - pL)  Þ  pL = 3/4;
i.e. the way B mixes over Left and Right must make A
indifferent between choosing Up or Down.
Mixed Strategies
Player B
Player A
(1,2)
(0,4)
(0,5)
(3,2)
U, pU
D, 1-pU
L, 3/4
R, 1/4

Mixed Strategies
Player B
Player A
(1,2)
(0,4)
(0,5)
(3,2)
U, pU
D, 1-pU
L, 3/4
R, 1/4

Mixed Strategies
Player B
Player A
(1,2)
(0,4)
(0,5)
(3,2)
U, pU
D, 1-pU
B’s expected value of choosing Left is ??
L, 3/4
R, 1/4

Mixed Strategies
Player B
Player A
(1,2)
(0,4)
(0,5)
(3,2)
U, pU
D, 1-pU
B’s expected value of choosing Left is 2pU + 5(1 - pU).
B’s expected value of choosing Right is ??
L, 3/4
R, 1/4

Mixed Strategies
Player B
Player A
(1,2)
(0,4)
(0,5)
(3,2)
U, pU
D, 1-pU
B’s expected value of choosing Left is 2pU + 5(1 - pU).
B’s expected value of choosing Right is 4pU + 2(1 - pU).
L, 3/4
R, 1/4

B’s expected value of choosing Left is 2pU + 5(1 - pU).
B’s expected value of choosing Right is 4pU + 2(1 - pU).
If 2pU + 5(1 - pU) > 4pU + 2(1 - pU) then B will choose
only Left, but there is no NE in which B plays only Left.
Mixed Strategies
Player B
Player A
(1,2)
(0,4)
(0,5)
(3,2)
U, pU
D, 1-pU
L, 3/4
R, 1/4

B’s expected value of choosing Left is 2pU + 5(1 - pU).
B’s expected value of choosing Right is 4pU + 2(1 - pU).
If 2pU + 5(1 - pU) < 4pU + 2(1 - pU) then B plays only
Right, but there is no NE where B plays only Right.
Mixed Strategies
Player B
Player A
(1,2)
(0,4)
(0,5)
(3,2)
U, pU
D, 1-pU
L, 3/4
R, 1/4

If there is a NE then necessarily
2pU + 5(1 - pU) = 4pU + 2(1 - pU)  Þ  pU = 3/5;
i.e. the way A mixes over Up and Down must make B
indifferent between choosing Left or Right.
Mixed Strategies
Player B
Player A
(1,2)
(0,4)
(0,5)
(3,2)
U, 3/5
D, 2/5
L, 3/4
R, 1/4

The game’s only Nash equilibrium consists of A
playing the mixed strategy (3/5, 2/5) and B playing
the mixed strategy (3/4, 1/4).
Mixed Strategies
Player B
Player A
(1,2)
(0,4)
(0,5)
(3,2)
U, 3/5
D, 2/5
L, 3/4
R, 1/4

The payoff will be (1,2) with probability
                           3/5 × 3/4 = 9/20.
Mixed Strategies
Player B
Player A
(1,2)
 9/20
(0,4)
(0,5)
(3,2)
U, 3/5
D, 2/5
L, 3/4
R, 1/4

The payoff will be (0,4) with probability
                           3/5 × 1/4 = 3/20.
Mixed Strategies
Player B
Player A
(1,2)
 9/20
(0,4)
3/20
(0,5)
(3,2)
U, 3/5
D, 2/5
L, 3/4
R, 1/4

The payoff will be (0,5) with probability
                           2/5 × 3/4 = 6/20.
Mixed Strategies
Player B
Player A
(1,2)
 9/20
(0,4)
3/20
(0,5)
 6/20
U, 3/5
D, 2/5
L, 3/4
R, 1/4
(3,2)

The payoff will be (3,2) with probability
                           2/5 × 1/4 = 2/20.
Mixed Strategies
Player B
Player A
(1,2)
 9/20
(0,4)
3/20
(0,5)
 6/20
(3,2)
 2/20
U, 3/5
D, 2/5
L, 3/4
R, 1/4

A’s NE expected payoff is
                      1×9/20 + 3×2/20 = 3/4.
Mixed Strategies
Player B
Player A
(1,2)
 9/20
(0,4)
3/20
(0,5)
 6/20
(3,2)
 2/20
U, 3/5
D, 2/5
L, 3/4
R, 1/4

A’s NE expected payoff is
                      1×9/20 + 3×2/20 = 3/4.
B’s NE expected payoff is
      2×9/20 + 4×3/20 + 5×6/20 + 2×2/20 = 16/5.
Mixed Strategies
Player B
Player A
(1,2)
 9/20
(0,4)
3/20
(0,5)
 6/20
(3,2)
 2/20
U, 3/5
D, 2/5
L, 3/4
R, 1/4

How Many Nash Equilibria?
uA game with a finite number of players, each with a finite number of pure strategies, has at least
one Nash equilibrium.
uSo if the game has no pure strategy Nash equilibrium then it must have at least one mixed strategy
Nash equilibrium.

Repeated Games
uA strategic game that is repeated by being played once in each of a number of periods.
uWhat strategies are sensible for the players depends greatly on whether or not the game
–is repeated over only a finite number of periods
–is repeated over an infinite number of periods.

Repeated Games
uAn important example is the repeated Prisoner’s Dilemma game.  Here is the one-period version of
it that we considered before.

The Prisoner’s Dilemma
Suppose that this game will be played in each of only 3 periods; t = 1, 2, 3.  What is the likely
outcome?
(-5,-5)
(-30,-1)
(-1,-30)
(-10,-10)
S
C
S
C
Clyde
Bonnie

The Prisoner’s Dilemma
Suppose the start of period t = 3 has been reached (i.e. the game has already been played twice).
What should Clyde do?  What should Bonnie do?
(-5,-5)
(-30,-1)
(-1,-30)
(-10,-10)
S
C
S
C
Clyde
Bonnie

The Prisoner’s Dilemma
Suppose the start of period t = 3 has been reached (i.e. the game has already been played twice).
What should Clyde do?  What should Bonnie do?  Both should choose Confess.
(-5,-5)
(-30,-1)
(-1,-30)
(-10,-10)
S
C
S
C
Clyde
Bonnie

The Prisoner’s Dilemma
Now suppose the start of period t = 2 has been reached.  Clyde and Bonnie expect each will choose
Confess next period.  What should Clyde do?  What should Bonnie do?
(-5,-5)
(-30,-1)
(-1,-30)
(-10,-10)
S
C
S
C
Clyde
Bonnie

The Prisoner’s Dilemma
Now suppose the start of period t = 2 has been reached.  Clyde and Bonnie expect each will choose
Confess next period.  What should Clyde do?  What should Bonnie do?  Both should choose Confess.
(-5,-5)
(-30,-1)
(-1,-30)
(-10,-10)
S
C
S
C
Clyde
Bonnie

The Prisoner’s Dilemma
At the start of period t = 1 Clyde and Bonnie both expect that each will choose Confess in each of
the next two periods.  What should Clyde do?  What should Bonnie do?
(-5,-5)
(-30,-1)
(-1,-30)
(-10,-10)
S
C
S
C
Clyde
Bonnie

The Prisoner’s Dilemma
At the start of period t = 1 Clyde and Bonnie both expect that each will choose Confess in each of
the next two periods.  What should Clyde do?  What should Bonnie do?  Both should choose Confess.
(-5,-5)
(-30,-1)
(-1,-30)
(-10,-10)
S
C
S
C
Clyde
Bonnie

The Prisoner’s Dilemma
The only credible (subgame perfect) NE for this game is where both Clyde and Bonnie choose Confess
in every period.
(-5,-5)
(-30,-1)
(-1,-30)
(-10,-10)
S
C
S
C
Clyde
Bonnie

The Prisoner’s Dilemma
The only credible (subgame perfect) NE for this game is where both Clyde and Bonnie choose Confess
in every period.  This is true even if the game is repeated for a large, still finite, number of
periods.
(-5,-5)
(-30,-1)
(-1,-30)
(-10,-10)
S
C
S
C
Clyde
Bonnie

The Prisoner’s Dilemma
However, if the game is repeated for an infinite number of periods then the game has a huge number
of credible NE.
(-5,-5)
(-30,-1)
(-1,-30)
(-10,-10)
S
C
S
C
Clyde
Bonnie

The Prisoner’s Dilemma
(C,C) forever is one such NE.  But (S,S) can also be a NE because a player can punish the other for
not cooperating (i.e. for choosing Confess).
(-5,-5)
(-30,-1)
(-1,-30)
(-10,-10)
S
C
S
C
Clyde
Bonnie