Study Guide
Backward Induction and Subgame Perfection
-
University:
Washington State University -
Course:
F424 | Strategy and Game Theory Academic year:
2024
-
Views:
485
Pages:
48
Author:
Nicole Wang
EconS 424 - Backward Induction and Subgame
Perfection
Félix Muñoz-García (WSU)
EconS 424 - Recitation 5 Watson, Ch. 15 # 1
Consider the extensive-form game on the next slide. Solve the game
using backward induction.
EconS 424 - Recitation 5 Watson, Ch. 15 # 1
O
1
I
2
C
4, 3, 1
A
B
3
X
Y
X
Y
EconS 424 - Recitation 5
2, 2, 2
3, 2, 1
5, 0, 0
1, 2, 6
7, 5, 5 Watson, Ch. 15 # 1
Starting from the terminal nodes, the smallest proper subgame we
can identify is depicted below:
A
2
C
4, 3, 1
B
3
X
Y
X
Y
EconS 424 - Recitation 5
3, 2, 1
5, 0, 0
1, 2, 6
7, 5, 5 Watson, Ch. 15 # 1
In this subgame, player 3 chooses his action without observing player
2’s choice. In order to …nd the NE of this subgame, we must
represent it in its normal (matrix) form.
X
Player 3
Y
A
3, 2, 1
5, 0, 0
C
4, 3, 1
4, 3, 1
Player 2 B
1, 2, 6
7, 5, 5
Note that player 1’s payo¤s are only included for completeness and
have no bearing on the decisions made by players 2 and 3.
EconS 424 - Recitation 5 Watson, Ch. 15 # 1
Hence, the NE of this subgame predicts that players 2 and 3 choose
strategy pro…le (C , X ). We can now plug the payo¤ triple resulting
from the NE of this subgame, (4, 3, 1), at the end of the branch
indicating that player 1 chose action I , as follows.
O
1
I
2, 2, 2
From the subgame (C,X)
4, 3, 1
Then the SPNE is (I , C , X ).
EconS 424 - Recitation 5 Watson, Ch. 15 # 5
In the Envelope Game, there are two players and two envelopes. One
of the envelopes is marked "player 1," and the other is marked "player
2." At the beginning of the game, each envelope contains one dollar.
Player 1 is given the choice between stopping the game and
continuing. If he chooses to stop, then each player receives the money
in his own envelope and the game ends. If player 1 chooses to
continue, then a dollar is removed from his envelope and two dollars
are added to player 2’s envelope.
Player 2 then gets to make the same choices with the same outcomes.
EconS 424 - Recitation 5 Watson, Ch. 15 # 5
Play continues like this, alternating between the players, until either
one of them decides to stop or k rounds of play have elapsed. If
neither player chooses to stop by the end of the kth round, then both
players obtain zero. Assume players want to maximize the amount of
money they earn.
Draw this game’s extensive-form tree for k = 5.
EconS 424 - Recitation 5 Watson, Ch. 15 # 5
This game is similar to all of the centipede games we have done in
the past and follows the same form.
1
S
1, 1
C
2
S
C
1
S
0, 3
2
C
S
2, 2
C
1
S
1, 4
EconS 424 - Recitation 5
3, 3
C
0, 0 Watson, Ch. 15 # 5
Use backward induction to …nd the subgame perfect equilibrium.
EconS 424 - Recitation 5 Watson, Ch. 15 # 5
Working backward, it is easy to see that in round 5, player 1 will
choose S (3 > 0). Thus, in round 4, player 2 will choose S (4 > 3
and 4 > 0). Continuing in this fashion, we …nd that, in any
equilibrium, each player will choose S and time he is able to move.
1
S
1, 1
C
2
S
C
1
S
0, 3
2
C
S
2, 2
C
1
S
1, 4
EconS 424 - Recitation 5
3, 3
C
0, 0 Watson, Ch. 15 # 5
Describe the backward induction outcome of this game for any …nite
integer k.
EconS 424 - Recitation 5 Watson, Ch. 15 # 5
For any …nite k, the backward induction outcome is that player 1
chooses S in the …rst round and each player receives one dollar. This
is because if neither player chose to stop by the end of the kth round,
then both players obtain zero (1 > 0).
EconS 424 - Recitation 5 Watson, Ch. 15 # 8
Imagine a game in which players 1 and 2 simultaneously and
independently select A or B. If they both select A, then the game
ends and the payo¤ vector is (5, 5). If they both select B, then the
game ends with the payo¤ vector ( 1, 1).
If one of the players chooses A while the other selects B, then the
game continues and the players are required to simultaneously and
independently sleect positive numbers. After these decisions, the
game ends and each player receives the payo¤
x1 + x2
,
1 + x1 + x2
where x1 is the positive number chosen by player 1 and x2 is the
positive number chosen by player 2.
EconS 424 - Recitation 5 Watson, Ch. 15 # 8
Describe the strategy spaces of the players.
EconS 424 - Recitation 5 Watson, Ch. 15 # 8
Each player has to choose an initial move (A or B), and potentially a
positive number. We can thus describe each of their strategy spaces
as
Si = fA, B g (0, ∞) (0, ∞)
Why is the positive interval included in there twice? Because the
outcomes AB and BA are not considered the same, so each player has
to choose a positive number for each possible outcome!
EconS 424 - Recitation 5 Watson, Ch. 15 # 8
We can depict the outcomes of this game similar to that of an
extensive form. Note, however, that this is not an extensive form
representation of this game, rather just a simple visualization tool.
Players 1 and 2 simultaneously
choose A or B
5
5
AA
AB
x1 + x2
1 + x1 + x2
x1 + x2
1 + x1 + x2
BA
BB
x1 + x2
1 + x1 + x2
x1 + x2
1 + x1 + x2
EconS 424 - Recitation 5
-1
-1 Watson, Ch. 15 # 8
Compute the NE of this game.
EconS 424 - Recitation 5 Watson, Ch. 15 # 8
It is easy to see that when one of the players chooses A and the other
selects B, then
Both x1 and x2 are positive
0<
z }| {
x1 + x2
1 + x1 + x2
| {z }
<1
Donominator is always larger
than the numerator
and that
x1 + x2
! 1 as (x1 + x2 ) ! ∞
1 + x1 + x2
EconS 424 - Recitation 5 Watson, Ch. 15 # 8
Thus, each has a higher payo¤ when both choose A. Further, B
( 1, 1) will never be selected in equilibrium. The Nash Equilibria of
this game are given by (Ax1 , Ax2 ) where x1 and x2 are any positive
numbers.
EconS 424 - Recitation 5 Watson, Ch. 15 # 8
Determine the subgame perfect equilibria
EconS 424 - Recitation 5 Watson, Ch. 15 # 8
If the game proceeds through AB or BA, every player i maximizes his
payo¤ 1 +x1x+1 +x2x2 by optimally selecting xi .
max
xi
x1 + x2
1 + x1 + x2
Taking FOCs with respect to xi ,
1
=0
(1 + x1 + x2 )2
Unfortunately, we can’t use this to develop best response function for
the players since we have a corner solution.
Intuition: Both players are going to want to select the highest value of
xi possible in order to maximize their payo¤s. We can then assume
that xi ! ∞.
EconS 424 - Recitation 5 Watson, Ch. 15 # 8
Taking the limit of our payo¤ function, we …nd
x1 + x2
=1
xi !∞ 1 + x1 + x2
lim
Implying that both players will recieve a payo¤ of (1, 1) at either of
those nodes after selecting x1 = x2 = ∞.
EconS 424 - Recitation 5 Watson, Ch. 15 # 8
Substituting these payo¤s into our above …gure
Players 1 and 2 simultaneously
choose A or B
5
5
AA
AB
1
1
BA
BB
1
1
-1
-1
It is clear that the SPNE of this game is where both players select A in
the …rst round, and ∞ if they reach the second round, or (A∞, A∞).
EconS 424 - Recitation 5 Harrington, Ch. 8 # 1
Consider the game "Galileo and the Inquisition" on the next slide.
Find all Nash equilibria.
EconS 424 - Recitation 5 Harrington, Ch. 8 # 1
Do not
refer
3
5
3
Urban VIII
Refer
Confess
5
3
4
Do not
confess
Inquisitor
Do not
torture
Torture
Galileo
Confess
4
1
5
Galileo
Do not
confess
EconS 424 - Recitation 5
1
2
1
2
4
2 Harrington, Ch. 8 # 1
The strategic form games are shown below:
Urban
VIII
Urban
VIII
DNR
R
DNR
R
C/C
C/DNC
5, 3, 4
5, 3, 4
3, 5, 3
3, 5, 3
DNC/C
DNC/DNC
4, 1, 5
1, 2, 1
3, 5, 3
Inquisitor: T
C/C
C/DNC
5, 3, 4
5, 3, 4
3, 5, 3
Galileo
Galileo
3, 5, 3
DNC/C
DNC/DNC
2, 4, 2
2, 4, 2
3, 5, 3
Inquisitor: DNT
EconS 424 - Recitation 5
3, 5, 3
3, 5, 3 Harrington, Ch. 8 # 1
There are …ve psNE for this game: (DNR, DNC /DNC , T ),
(R, C /C , T ), (R, C /DNC , T ), (DNR, DNC /C , DNT ), and
(DNR/DNC /DNC /DNT ).
Note: Do all of these equilibria make sense? Look at the third one:
Galileo confesses before torture, but does not confess after. While this
would end the game early, this is actually the opposite result we would
expect.
EconS 424 - Recitation 5 Harrington, Ch. 8 # 1
Find all of the subgame perfect Nash equilibria.
EconS 424 - Recitation 5 Harrington, Ch. 8 # 1
In his last decision node (which is associated with the path Refer, Do
not confess, Torture), Galileo chooses Do not confess (2 > 1).
Given this choice, the Inquisitor chooses Do not torture (4 > 1).
At his …rst decision node (associated with Urban VIII having chosen
Refer), Galileo chooses Do not confess (4 > 3).
Finally, Urban VIII chooses Do not refer (3 > 2).
Hence, the unique subgame perfect Nash equilibrium is
(DNR, DNC /DNC , DNT ).
EconS 424 - Recitation 5 Harrington, Ch. 8 # 1
Do not
refer
3
5
3
Urban VIII
Refer
Confess
5
3
4
Do not
confess
Inquisitor
Do not
torture
Torture
Galileo
Confess
4
1
5
Galileo
Do not
confess
EconS 424 - Recitation 5
1
2
1
2
4
2 Harrington, Ch. 8 # 1
For each Nash equilibrium that is not a subgame perfect Nash
equilibrium, explain why it is not a subgame perfect Nash equilibrium.
EconS 424 - Recitation 5 Harrington, Ch. 8 # 1
There are four Nash equilibria that are no subgame perfect Nash
equilibriua.
In Nash equilibria (DNR, DNC /DNC .T ) and (R, C /DNC /T ), the
Inquisitor is making a nonoptimal decision by choosing to torture
Galileo given Galileo plays Do not confess in his last decision node.
In Nash equilibria (R, C /C , T ) and (DNR, DNC /C , DNT ), Galileo is
making a nonoptimal decision at his last decision node. He should
play Do not confess instead.
EconS 424 - Recitation 5 Harrington, Ch. 9 # 2
Consider the Revised OS/2 game on the next slide. Derive all
subgame perfect Nash Equilibria.
EconS 424 - Recitation 5 Harrington, Ch. 9 # 2
IBM
Company 1
Company 2
Company 3
0
0
0
0
Do not
develop OS/2
IBM
Develop
Company 1
Do not
develop
Develop OS/2
Company 2
Do not
develop
Develop OS/2
Company 3
Develop OS/2
5
2
2
2
Develop OS/2
Do not
develop
3
1
1
0
3
1
0
1
Do not
develop
-2
-1
0
0
Do not
develop
Develop OS/2
Develop OS/2
3
0
1
1
Company 2
Develop OS/2
Do not
develop
-2
0
-1
0
EconS 424 - Recitation 5
-2
0
0
-1
Company 3
Do not
develop
-3
0
0
0 Harrington, Ch. 9 # 2
Consider the proper subgame between companies 2 and 3 associated
with IBM having developed OS/2 and company having developed an
application.
Company 2
Do not
develop
Develop OS/2
Company 3
Develop OS/2
5
2
2
2
Develop OS/2
Do not
develop
3
1
1
0
3
1
0
1
EconS 424 - Recitation 5
Do not
develop
-2
-1
0
0 Harrington, Ch. 9 # 2
The strategic form of the game is shown in the …gure below:
Company 2
D
DND
Company 3
D
DND
5, 2, 2, 2
3, 1, 0, 1
3, 1, 1, 0
-2, -1, 0, 0
Develop is a dominant strategy for each company (Remember we’re
only looking at company 2 and 3’s payo¤s), so there is a unique Nash
equilibrium of (Develop, Develop ) for this subgame.
EconS 424 - Recitation 5 Harrington, Ch. 9 # 2
Next, consider the subgame associated with IBM having developed
OS/2 and company 1 having not developed an application.
Company 2
Do not
develop
Develop OS/2
Develop OS/2
3
0
1
1
Develop OS/2
Do not
develop
-2
0
-1
0
-2
0
0
-1
EconS 424 - Recitation 5
Company 3
Do not
develop
-3
0
0
0 Harrington, Ch. 9 # 2
The strategic form of the game is shown below:
Company 2
D
DND
D
Company 3
DND
3, 0, 1, 1
-2, 0, 0, -1
-2, 0, -1, 0
-3, 0, 0, 0
There are two psNE of this game: (Develop, Develop ) and (Do not
develop, Do not develop ).
EconS 424 - Recitation 5 Harrington, Ch. 9 # 2
Move up the tree to the subgame initiated by IBM having developed
OS/2, where company 1 has to decide whether or not to develop an
application.
Suppose that the Nash equilibrium for the subgame in which company
1 does not develop an application is (Develop, Develop ) (One of our
two choices).
Replacing the two …nal subgames with the Nash equilibrium payo¤s,
the situation is as depicted on the next slide.
EconS 424 - Recitation 5 Harrington, Ch. 9 # 2
IBM
Company 1
Company 2
Company 3
0
0
0
0
Do not
develop OS/2
IBM
Develop
Company 1
Develop OS/2
5
2
2
2
Do not
develop
3
0
1
1
As we can see, if company 1 develops an application, then its payo¤ is
2, while its payo¤ is 0 from not doing so. Hence, it chooses Develop.
EconS 424 - Recitation 5 Harrington, Ch. 9 # 2
Now suppose the Nash equilibrium when company 1 does not develop
an application is (Do not develop, Do not develop ).
Replacing the two …nal subgames with the Nash equilibrium payo¤s,
the situation is as depicted in the …gure on the next slide.
EconS 424 - Recitation 5 Harrington, Ch. 9 # 2
IBM
Company 1
Company 2
Company 3
0
0
0
0
Do not
develop OS/2
IBM
Develop
Company 1
Develop OS/2
5
2
2
2
Do not
develop
-3
0
0
0
Again, if company 1 develops an application, then its payo¤ is 2,
while its payo¤ is 0 from not doing so. Hence, it chooses Develop.
EconS 424 - Recitation 5 Harrington, Ch. 9 # 2
Thus, regardless of which Nash equilibrium is used in the subgame in
which company 1 chooses Do not develop, company 1 optimally
chooses Develop.
Now we go to the subgame that is the game itself. If IBM chooses to
develop OS/2 (5 > 0), then, as previously derived, company 1
develops an application and this induces both companies 2 and 3 to
do so as well.
Hence, IBM’s payo¤ is 5. It is then optimal for IBM to develop OS/2
EconS 424 - Recitation 5 Harrington, Ch. 9 # 2
There are then three subgame perfect Nash equilibria (where a
strategy for company 2, as well as for company 3, is an action in
response to company 1 choosing Develop and an action in response
to company 1 choosing Do not develop):
"Wait? Three? We only talked about two!" There is a third Nash
equilibrium of the second subgame we looked at using mixed strategies.
I will leave that for you to calculate on your own.
The two SPNE that we calculated are (Develop OS /2, Develop,
Develop/Develop, Develop/Develop ), and (Develop OS /2, Develop,
Develop/Do not develop, Develop/Do not develop )
Both equilibria result in the same outcome path of (5, 2, 2, 2).
EconS 424 - Recitation 5 Harrington, Ch. 9 # 2
Derive a Nash equilibrium that is not a subgame perfect Nash
equilibrium, and explain why it is not a subgame perfect Nash
equilibrium.
EconS 424 - Recitation 5 Harrington, Ch. 9 # 2
Consider any strategy pro…le in which IBM chooses Do not develop
OS /2 and the other three companies’strategies are such that at
most one of them develops an application if OS /2 were to be
developed. Given the latter, it is optimal not to develop OS/2 and,
given that OS/2 is not developed, a company’s payo¤ is 0 regardless
of its strategy.
We can show all of these by creating the normal form of the entire
game. We are not going to do that, but leave it as a challenge for you.
EconS 424 - Recitation 5 Harrington, Ch. 9 # 2
Thus, these are Nash equilibria, but they are not subgame perfect
Nash equilibria. There are 16 Nash equilibria (4 of each kind):
(Do not develop
not develop )
(Do not develop
/Develop )
(Do not develop
develop )
(Do not develop
develop/ )
OS /2, Do not develop, /Do not develop, /Do
OS /2, Do not develop, /Do not develop,
OS /2, Do not develop, /Develop, /Do not
OS /2, Do not develop, Do not develop/ , Do not
In the strategy pro…les just shown, you can put either Do not develop
or Develop as the placeholder .
EconS 424 - Recitation 5
Related Documents
- Marginal Propensity to Consume: Consumption and Income Relationship
- The Distribution of Income: The Economics of Poverty
- The Distribution of Income: Major Programs of Cash Assistance
- The Banking System: The Federal Funds Market
- Production Cost Estimation: Optimizing Profits
- Economies of Scale: Analyzing Minimum Production Inflation Points
- Economic Function Perspective: Elimination and Substitution
- Directional Constants in Linear Functions: Analyzing Changes
- Lagrange Multiplier Analysis in Economic Modeling
- Income Maximum Point Determinants: Discriminants in Economics
- Quadratic Curved Lines: Studying Parabolas that Open Upward and Downward
- The Banking System: The Evolution of Banking
- Linear Functions with Negative Directional Coefficients
- The Banking System: The Reserve Multiplier
- Banking System: Loans & Checkable Deposits
- The Banking System: Commercial Bank Balance Sheets
- The Banking System: Deposit Creation by a Single Bank
- The Banking System: Multiple Expansion of The Money Stock
- The Distribution of Income: Losses in Efficiency Caused
- Tax Function Analysis: Understanding the 'To' Constant
Backward Induction and Subgame Perfection
of 48
Report
Tell us what’s wrong with it:
Thanks, got it!
We will moderate it soon!
Free up your schedule!
Our EduBirdie Experts Are Here for You 24/7! Just fill out a form and let us know how we can assist you.
Take 5 seconds to unlock
Enter your email below and get instant access to your document