1 of 32

Subgame Perfect Equilibrium�

Roman Sheremeta, Ph.D.

Professor, Weatherhead School of Management

Case Western Reserve University

2 of 32

Outline�

Review
Entry Game
Subgame
Subgame Perfect Nash Equilibrium
Backward induction

3 of 32

Review: �Extensive-Form Game

The extensive-form representation of a game specifies:

Who moves when and what action choices are available?
What do players know when they move?
What payoffs players receive for each combination of moves?

In the extensive-from game, a strategy for a player is a complete plan of actions. It specifies a feasible action for the player in every node in which the player might be called on to act.

4 of 32

Review: �Extensive-Form Game

DEFINITION: An extensive-form game consists of:

A set of players

{Player 1, Player 2, ... Player n}

A history of plays

A set of actions at each history of plays

S₁(H), S₂(H), ..., S_n(H)

For each player, payoffs (preferences) over the set of histories of plays

u_i(s₁,s₂,...s_n) for all s₁∈S₁(H), ..., s_n∈S_n(H)

5 of 32

Entry Game: �Extensive-Form

HP vs Dell:

HP is debating whether to enter (E) a new market or stay out (O), where the market is dominated by its rival, Dell
Both firms’ profitability depends on how Dell is going to react to HP coming into the market
Dell has two options: playing tough (T) by starting a big advertising campaign or accommodating (A)

Dell

0, 5

-2,-1

1, 2

6 of 32

Entry Game: �Normal-Form

We can also use normal-form to represent a dynamic game

		Dell
		A	T
HP	E	1 , 2	-2 , -1
HP	O	0 , 5	0 , 5

Dell

0, 5

-2,-1

1, 2

7 of 32

Nash Equilibrium�

The set of Nash equilibria in a dynamic extensive-form game of complete information is the set of Nash equilibria of its static normal-form representation

How to find the Nash equilibria in a dynamic game of complete information?

Construct the normal-form of the dynamic game of complete information
Find the Nash equilibria in the normal-form

8 of 32

Entry Game:�Nash Equilibrium

What are the Nash equilibria?

(E, A (if E))
(O, T (if E))

Does the second Nash equilibrium make sense?

How does HP know that Dell will choose T if HP chose E?
If Dell could commit, they would announce at the start of the game that they intend to play T, but such a threat is not credible, because after HP enters Dell’ s only incentive is to play A
Therefore, (O, T (if E)) is not a creditable equilibrium!

		Dell
		A	T
HP	E	1 , 2	-2 , -1
HP	O	0 , 5	0 , 5

9 of 32

Entry Game: �Nash Equilibrium

(O, T(if E)) is not a creditable equilibrium only under the assumption that the incumbent (Dell) cannot commit to fight if the challenger enters

If Dell can commit to fight after HP enters the market then the game is modified so that Dell can only play T

Dell

0, 5

-2,-1

10 of 32

Radio conversation released by the Chief of Naval Operations on 10/10/95

#1: Please divert your course 15 degrees to the North to avoid a collision
#2: Recommend you divert YOUR course 15 degrees to the South to avoid a collision

#1: This is the Captain of a US Navy ship. I say again, divert YOUR course
#2: No. I say again, YOU divert YOUR course

#1: THIS IS THE AIRCRAFT CARRIER ENTERPRISE, WE ARE A LARGE WARSHIP OF THE US NAVY. DIVERT YOUR COURSE NOW!
#2: This is a lighthouse. Your call

11 of 32

Subgame Perfect Equilibrium�

Nash Equilibrium: Each player must act optimally given the other players’ strategies, i.e., play a best response to the others’ strategies

The problem with extensive-form games is that some Nash equilibria of dynamic games involve non-credible threats

To avoid this problem we need to refine the equilibrium concept by a Subgame Perfect Nash Equilibrium

12 of 32

Subgame Perfect Equilibrium�

Reinhard Selten (1994 Nobel Memorial Prize in Economics). He received the prize with John Nash.

13 of 32

Subgame�

A subgame of a game tree begins at a nonterminal node and includes all the nodes and branchs following the nonterminal node

A subgame beginning at a nonterminal node x can be obtained by removing the branch connecting x and its predecessor

14 of 32

Subgame�

Player 1

Player 2

-1, 1

1, -1

Player 2

1, -1

-1, 1

H’

T’

Subgame 1

Subgame 2

Player 2

-1, 1

1, -1

Player 2

1, -1

-1, 1

H’

T’

Subgame 3

15 of 32

Subgame�

Player 2

Player 1

3, 1

1, 2

0, 0

Player 1

2, 0

Player 2

Player 1

3, 1

1, 2

0, 0

Player 1

1, 2

0, 0

Subgame 2

Subgame 1

Subgame 3

16 of 32

Subgame Perfect Nash Equilibrium�

A Subgame Perfect Nash Equilibrium (SPNE) of Γ is a strategy profile that induces a Nash Equilibrium in every subgame of Γ

In other words, the players act optimally at every point during the game
In order to solve for the SPNE, we use the process of backward induction

Existence Theorem (Selten, 1975): Every finite extensive game with perfect information has a Subgame Perfect Nash Equilibrium (SPNE) that can be found by backward induction

17 of 32

Entry Game: �Backward Induction

How to apply backward induction?

Start with the smallest subgame
Find the Nash equilibrium (best response) in that subgame game
Then refine the game, taking into account the results from the subgame and find the Nash equilibrium.
Continue until you cannot refine the game

Dell

0, 5

-2,-1

1, 2

Subgame 1

0, 5

1, 2

Subgame 2

18 of 32

Entry Game: �Backward Induction

What are the Nash equilibria?

(E, A) with the payoff of (1, 2)
(O, T) with the payoff of (0, 5)

What are SPNE?

(E, A) with the payoff of (1, 2)

Dell

0, 5

-2,-1

1, 2

		Dell
		A	T
HP	E	1 , 2	-2 , -1
HP	O	0 , 5	0 , 5

19 of 32

Subgame Perfect Nash Equilibrium�

A SPNE is obtained by backward induction and it is used to rule out unreasonable NE

If sequential rationality is common knowledge between the players (at every information set), then each player will look ahead to consider what players will do in the future in response to his move at a particular information set

Assumptions:

Rationality: choose the best action available
Sequentiality: infer what the future is going to be, knowing that in the future players will reason in the same rational way

20 of 32

Subgame Perfect Nash Equilibrium:�Theoretical Limitations

Some theoretical limitations of SPNE:

(1) Games with infinitely long (indefinite) stages
(2) Extensive games that allow simultaneous moves
(3) Problems with equilibrium selection

21 of 32

Example�

Finding SPNE:

What is the equilibrium strategy in the three subgames?

Player 2 plays F if Player 1 plays C
Player 2 plays H if Player 1 plays D
Player 2 plays K if Player 1 plays E

What is the best response of Player 1 if he knows this?

Player 1 plays D

SPNE is (D, F(if C)H(if D)K(if E))

Player 1

Player 2

1, 0

0, 1

Player 2

1, 3

2, 2

Player 2

2, 1

1, 1

22 of 32

Example�

Finding SPNE:

What is the equilibrium strategy in the three subgames?

Player 2 plays F if Player 1 plays C
Player 2 plays H if Player 1 plays D
Player 2 plays K if Player 1 plays E

What is the best response of Player 1 if he knows this?

Player 1 plays E

SPNE is (E, F(if C)H(if D)K(if E))

Player 1

Player 2

1, 0

0, 1

Player 2

1, 3

2, 2

Player 2

2, 1

1, 1

23 of 32

Example�

Finding SPNE:

What is the equilibrium strategy in the three subgames?

Player 2 plays F if Player 1 plays C
Player 2 plays I if Player 1 plays D
Player 2 plays K if Player 1 plays E

What is the best response of Player 1 if he knows this?

Player 1 plays D

SPNE is (D, F(if C)I(if D)K(if E))

Player 1

Player 2

1, 0

0, 1

Player 2

1, 3

2, 2

Player 2

2, 1

1, 1

24 of 32

Subgame Perfect Nash Equilibrium:�Centipede Game

The centipede game introduced by Rosenthal (1981)

It is an extensive-form game in which two players take turns choosing either to take a larger share of a slowly increasing pot, or to pass the pot to the other player
The payoffs are arranged so that if one passes the pot to one's opponent and the opponent takes the pot on the next round, one receives less than if one had taken the pot on this round

25 of 32

Subgame Perfect Nash Equilibrium:�Centipede Game

We can illustrate the game in extensive-form
What is the subgame perfect Nash equilibrium?

Start analysis at the last subgame
SPNE is (S, S’) with payoffs of (2, 0): player 1 stops (S) at the first round and player 2 stops (S’) at the second round

S’

C’

2, 0

1, 3

4, 2

Subgame

26 of 32

Subgame Perfect Nash Equilibrium:�Centipede Game

What if the game is longer?
What is the subgame perfect Nash equilibrium?

Start analysis at the last subgame
SPNE is (SS’’S’’’’, S’S’’’S’’’’’) with payoffs of (2, 0): player 1 stops in each round and player 2 stops in each round

S’

C’’’

C’’

C’

2, 0

3, 5

1, 3

4, 2

C’’’’’

C’’’’

5, 7

8, 6

6, 4

Subgame

S’’’

S’’

S’’’’’

S’’’’

27 of 32

Experiment #6: �Results (2020 CWRU)

28 of 32

Centipede Game:�Research

What are the common findings?

Only about 5% of students choose to stop right away

How do chess players behave?

Palacios-Huerta and Volij (2009), Levitt et al. (2011)
70% of chess players and 100% of chess Grandmasters choose to stop
As a consequence, chess players earn less than students!

29 of 32

Subgame Perfect Nash Equilibrium:�Behavioral Limitations

Some behavioral limitations of SPNE:

(1) People behave irrationally (they don’t know how to backward induct)
(2) People are concerned about fairness
(3) People are expecting reciprocal behavior

30 of 32

Imperfect Information�

Next Time!

31 of 32

Thank you!

Roman Sheremeta, Ph.D.

Professor, Weatherhead School of Management

Case Western Reserve University

32 of 32

References�

Watson, J. (2013). Strategy: An Introduction to Game Theory (3rd Edition). Publisher: W. W. Norton & Company. (Chapters 15)
Levitt, S.D., & List, J.A., & Sadoff, S. (2011). Checkmate: Exploring Backward. Induction among Chess Players. American Economic Review, 101, 975-990.
Palacios-Huerta, I., & Volij, O. (2009). Field centipedes. American Economic Review, 99, 1619-1635.
Rosenthal, R.W. (1981). Games of perfect information, predatory pricing and the chain-store paradox. Journal of Economic Theory, 25, 92-100.