Backward Induction: 9.1 Definition
Backward Induction: 9.1 Definition
Backward Induction: 9.1 Definition
Backward Induction
We now start analyzing the dynamic games with complete information. These notes
focus on the perfect-information games, where each information set is singleton, and
apply the notion of backward induction to these games. We will assume that the game
has "finite horizon", i.e., there can only be finitely many moves in any history of moves.
9.1 Definition
The concept of backward induction corresponds to the assumption that it is common
knowledge that each player will act rationally at each future node where he moves — even
if his rationality would imply that such a node will not be reached.1 (The assumption
that the player moves rationally at each information set he moves is called sequential
rationality.)
Mechanically, backward induction corresponds to the following procedure, depicted in
Figure 9.1. Consider any node that comes just before terminal nodes, that is, after each
move stemming from this node, the game ends. (Such nodes are called pen-terminal.) If
the player who moves at this node acts rationally, he chooses the best move for himself
at that node. Hence, select one of the moves that give this player the highest payoff.
Assigning the payoff vector associated with this move to the node at hand, delete all the
1
More precisely: at each node the player is certain that all the players will act rationally at all
nodes that follow node ; and at each node the player is certain that at each node that follows
node the player who moves at will be certain that all the players will act rationally at all nodes
that follow node ,...ad infinitum.
131
132 CHAPTER 9. BACKWARD INDUCTION
moves stemming from this node so that we have a shorter game, where the above node
is a terminal node. Repeat this procedure until the origin is the only remaining node.
The outcome is the moves that are picked in the way. Since a move is picked at each
information set, the result is a strategy profile.
For an illustration of the procedure, consider the game in the following figure. This
game describes a situation where it is mutually beneficial for all players to stay in a
relationship, while a player would like to exit the relationship, if she knows that the
other player will exit in the next day.
1 2 1
• • • (2,5)
In the third day, Player 1 moves, choosing between going across () or down (). If
he goes across, he would get 2; if he goes down, he would get the higher payoff of 3.
Hence, according to the procedure, he goes down. Selecting the move for the node at
hand, one reduces the game as follows:
1 2
• • (3,3)
(1,1) (0,4)
Here, the part of the game that starts at the last decision node is replaced with the
payoff vector associated with the selected move, , of the player at this decision node.
In the second day, Player 2 moves, choosing between going across () or down ().
If she goes across, she get 3; if she goes down, she gets the higher payoff of 4. Hence,
according to the procedure, she goes down. Selecting the move for the node at hand,
one reduces the game further as follows:
1
•
(0,4)
(1,1)
Once again, the part of the game that starts with the node at hand is replaced with
the payoff vector associated with the selected move, . Now, Player 1 gets 0 if he goes
across (), and gets 1 if he goes down (). Therefore, he goes down. The procedure
results in the following strategy profile:
That is, at each node, the player who is to move goes down, exiting the relationship.
Let’s go over the assumptions that we have made in constructing this strategy profile.
134 CHAPTER 9. BACKWARD INDUCTION
1 2 1
• • • (2,5)
We assumed that Player 1 will act rationally at the last date, when we reckoned that he
goes down. When we reckoned that Player 2 goes down in the second day, we assumed
that Player 2 assumes that Player 1 will act rationally on the third day, and also assumed
that she is rational, too. On the first day, Player 1 anticipates all these. That is, he is
assumed to know that Player 2 is rational, and that she will keep believing that Player
1 will act rationally on the third day.
This example also illustrates another notion associated with backward induction —
commitment (or the lack of commitment). Note that the outcomes on the third day
(i.e., (3,3) and (2,5)) are both strictly better than the equilibrium outcome (1,0). But
they cannot reach these outcomes, because Player 2 cannot commit to go across, and
anticipating that Player 2 will go down, Player 1 exits the relationship in the first day.
There is also a further commitment problem in this example. If Player 1 where able
to commit to go across on the third day, then Player 2 would definitely go across on
the second day. In that case, Player 1 would go across on the first. Of course, Player 1
cannot commit to go across on the third day, and the game ends in the first day, yielding
the low payoffs (1,0).
Proposition 9.1 In a game with finitely many nodes, backward induction always results
9.2. BACKWARD INDUCTION AND NASH EQUILIBRIUM 135
in a Nash equilibrium.
Proof. Let ∗ = (∗1 ∗ ) be the outcome of Backward Induction. Consider any
player and any strategy . To show that ∗ is a Nash equilibrium, we need to show
that
¡ ¢
(∗ ) ≥ ∗−
¡ ¢
where ∗− = ∗ =
6
. Take any node
• ∗ and prescribe the same moves for player at every node that comes after this
node.
(There is always such a node; for example the last node player moves.) Consider
a new strategy 1 according to which plays everywhere according to except for the
¡ ¢ ¡ ¢
above node, where he plays according to ∗ .According to 1 −
∗ ∗
or − , after this
¡ ∗ ∗ ¢
node, the play is as in − , the outcome of the backward induction. Moreover,
in the construction of ∗ , we have had selected the best move for player given this
continuation play. Therefore, the change from to 1 , which follows the backward
induction recommendation, can only increase the payoff of :
¡ ¢ ¡ ¢
1 ∗− ≥ ∗−
Applying the same procedure to 1 , now construct a new strategy 2 that differs from
1 only at one node, where player plays according to ∗ , and
¡ ¢ ¡ ¢
2 ∗− ≥ 1 ∗−
¡ ¢ ¡ −1 ∗ ¢ ¡ ¢ ¡ ¢
(∗ ) = ∗
− ≥ − ≥ · · · ≥ 1 −
∗
≥ ∗−
Since one takes his future moves given and picks only a move for the node at hand,
chhosing the best moves at the given nodes does not necessarily lead to a best response
among all contingent plans in general.
Example 9.1 Consider a single player, who chooses between good and bad everyday
forever. If he chooses good at everyday, he gets 1, and he gets 0 otherwise. Clearly, the
optimal plan is to play good everyday, yielding 1. Now consider the strategy according to
which he plays bad everyday at all nodes. This gives him 0. But the strategy satisfies the
condition of backward induction (although bacward induction cannot be applied to this
game with no end node). At any node, according to the moves selected in the future, he
gets zero regardless of what he does at the current node.
The above pathological case is a counterexample to the idea that if one is playing a
best move at every node, his plan is a best response. The latter idea is a major principle
of dynamic optimization, called the Single-Deviation Principle. It applies in most cases
except for the pathological cases as above. The above proof shows that the principle
applies in games with finitely many moves. Single-Deviation Principle will be the main
tool in the analyses of the infinite-horizon games in upcoming chapters. Studying the
above proof is recommended.
But not all Nash equilibria can be obtained by backward induction. Consider the
following game of the Battle of the Sexes with perfect information, where Alice moves
first.
Alice
O F
Bob Bob
O F O F
In this game, backward induction leads to the strategy profile identified in the figure,
according to which Bob goes wherever Alice goes, and Alice goes to Opera. There is
another Nash equilibrium: Alice goes to Football game, and Bob goes to Football game
9.3. COMMITMENT 137
at both of his decision nodes. Let’s see why this is a Nash equilibrium. Alice plays a
best response to the strategy of Bob: if she goes to Football she gets 1, and if she goes
to Opera she gets 0 (as they do not meet). Bob’s strategy (FF) is also a best response
to Alice’s strategy: under this strategy he gets 2, which is the highest he can get in this
game.
One can, however, discredit the latter Nash equilibrium because it relies on an se-
quentially irrational move at the node after Alice goes to Opera. This node does not
happen according to Alice’s strategy, and it is therefore ignored in Nash equilibrium.
Nevertheless, if Alice goes to Opera, going to football game would be irrational for Bob,
and he would rationally go to Opera as well. And Alice should foresee this and go to
Opera. Sometimes, we say that this equilibrium is based on "an incredible threat", with
the obvious interpretation.
This example illustrates a shortcoming of the usual rationality condition, which re-
quires that one must play a best response (as a complete contingent plan) at the be-
ginning of the game. While this requires that the player plays a best response at the
nodes that he assigns positive probability, it leaves the player free to choose any move
at the nodes that he puts zero probability–because all the payoffs after those nodes are
multiplied by zero in the expected utility calculation. Since the likelihoods of the nodes
are determined as part of the solution, this may lead to somewhat erroneous solutions in
which a node is not reached because a player plays irrationally at the node, anticipating
that the node will not be reached, as in (Football, FF) equilibrium. Of course, this is
erroneous in that when that node is reached the player cannot pretend that the node
will not be reached as he will know that the is reached by the definition of information
set. Then, he must play a best response taking it given that the node is reached.
9.3 Commitment
In this game, Alice can commit to going to a place, but Bob cannot. If we trust the
outcome of backward induction, this commitment helps Alice and hurts Bob. (Although
the game is symmetric Alice gets a higher payoff.) It is tempting to conclude that ability
to commit is always good. While this is true in many games, in some games it is not the
case. For example, consider the Matching Pennies with Perfect Information, depicted
138 CHAPTER 9. BACKWARD INDUCTION
in Figure 3.4. Let us apply backward induction. If Player 1 chooses Head, Player 2 will
play Head; and if Player 1 chooses Tail, Player 2 will prefer Tail, too. Hence, the game
is reduced to
(-1,1)
Head
Tail (-1,1)
In that case, Player 1 will be indifferent between Head and Tail, choosing any of these
two option or any randomization between these two acts will give us an equilibrium with
backward induction. In either equilibrium, Player 2 beats Player 1.
This example shows that backward induction can lead to multiple equilibria. Here, in
one equilibrium, Player 1 chooses Head, in another one Player 1 chooses Tail, and yet in
another mixed strategy equilibrium, he mixes between the two strategies. Each mixture
probability corresponds to a different equilibrium. In all of these equilibria, the payoffs
are the same. In general, however, backwards induction can lead to multiple equilibria
with quite different outcomes.
1 A 2 x 1 a
(1,1)
y
D d
z (0,2)
(1,1) a (2,2)
1 (0,1)
(1,0)
1 A 2 x
(2,2)
y
D
z (0,2)
(1,1) (1,0)
Figure 9.3:
140 CHAPTER 9. BACKWARD INDUCTION
(1,1)
The strategy selected for Player 1 depends on the choice of . If some 12 is selected
for Player 2, Player 1 must choose . This results in the equilibrium in which Player
1 plays and Player 2 plays with probability and with probability 1 − . If
12, Player 1 must choose . In the resulting equilibrium, Player 1 plays and
Player 2 plays with probability and with probability 1 − . Finally, if = 12 is
selected, then Player 1 is indifferent, and we can select any randomization between
and , each resulting in a different equilibrium.
(1 2 ) = ( (1 + 2 ) − )
9.5. EXAMPLE–STACKELBERG DUOPOLY 141
• At the initial node, firm 1 chooses an action 1 ; the set of allowable actions is
[0 ∞).
• After each action of firm 1, firm 2 moves and chooses action 2 ; the set of allowable
actions now is again [0 ∞).
• Each of these action leads to a terminal node, at which the payoff vector is
(1 (1 2 ) 2 (1 2 )).
Notice that a strategy of firm 1 is a real number 1 from [0 ∞), and more importantly
a strategy of firm 2 is a function from [0 ∞) to [0 ∞), which assigns a production level
2 (1 ) to each 1 . These strategies with the utility function (1 2 ) = (1 2 (1 ))
gives us the normal form.
Let us apply bachwards induction. Given 1 ≤ 1 − , the best production level for
the Follower is
1 − 1 −
2∗ (1 ) =
2
yielding to the payoff vector2
à ! à !
1
1 (1 2∗ (1 )) (1 − 1 − )
2 1
= (9.1)
2 (1 2∗ (1 )) 1
4
(1 − 1 − )2
By replacing the moves of firm 2 with the associated payoffs we obtain a game in which
firm one chooses a quantity level 1 which leads to the payoff vector in (9.1). In this
game firm 1 maximizes 12 1 (1 − 1 − ), choosing
1∗ = (1 − ) 2,
X E
2
(2,1) L R
M
1
1
(1,2)
l r
(3,1)
(3,1) (1,3
1,3)) (1,3) (3,1)
(3,1)
Figure 9.4:
1
L R
2
2
l1 r1 r2
l2
1
1,2 2,1 0,3
l r
2,2 1,4
Figure 9.5:
L R
2
2
l1 r1 r2
l2
1
1,2 2,1 0,3
l r
2,2 1,4
Figure 9.6:
1 2 1 2 1 2 1 2
1 2 1 2 2 1 2 1
1 2 1 2 2 1 2 1
0 3 2 2 0 3 2 2
0 3 1 4 0 3 1 4
(c) Find all the rationalizable strategies in this game –use the normal form.
State the rationality/knowledge assumptions necessary for each elimination.
1 2 1 2 1 2
1 2 1 2 2 1
1 2 1 2 2 1
0 3 2 2 0 3
(If you found the pure strategy equilibria (namely, (L,1 2 ) and (Lr,1 2 )), you
will get most of the points.)
Assuming that 23 22 , use backward induction to compute a Nash equi-
librium of this game. (Note that Alice and Bob are the only players here because
146 CHAPTER 9. BACKWARD INDUCTION
the actions of the committee members are fixed already.) [Hint: Bob chooses not
to contribute when he is indifferent between contribution and not contributing at
all.]
Solution: Given any (1 2 3 ) by Alice, for each , write ( ) = + for
the "price" of member for Bob. If the total price of the cheapest two members
P
exceeds (i.e., ( ) − max ( ) ≥ ), then Bob needs to pay at least
to stop the bill, in which case, he contributes 0 to each member. If the total
price of the cheapest two members is lower than , then the only best response
for Bob is to pay exactly the cheapest two members their price and pay nothing
to the the remaining member, stopping the bill, which would have cost him . In
sum, Bob’s strategy is given by
( P
+ if 0 0 (0 ) − max0 0 (0 ) and 6= ∗
∗ (1 2 3 ) =
0 otherwise,
where ∗ is the most expensive member, which is chosen randomly when there is
a tie.3
Answer: First consider the case ≤ 23 . Then, Alice chooses a contribution vector
(1 2 0) such that 1 + 2 + 1 + 2 = , 1 + 1 ≤ 3 , and 2 + 2 ≤ 3 . Such
a vector is feasible because 23 and 3 2 1 0. Optimality of this
contribution is as before.
Now consider the case 23 . Now, Alice must contribute to all members in
order to pass the bill, and the optimality requires that the prices of all members
are 2 (as Bob buys the cheapest two). That is, she must contribute
Since this costs Alice 32 − (1 + 2 + 3 ), she makes such a contribution to pass
the bill if and only if 32 ≤ + (1 + 2 + 3 ). Otherwise, she contributes
(0 0 0) and the bill fails.
9.7 Exercises
1. In Stackelberg duopoly example, for every 1 ∈ (0 1), find a Nash equilibrium in
which Firm 1 plays 1 .
L R
1/2 1/2 l r
1 2 1
2
X Y A B 4 x y
4 0 4 1 0 10
0 4 0 1 10 2
148 CHAPTER 9. BACKWARD INDUCTION
L R
M
2 2
2
l1 l r a c
r1 b
1
1
0 1 2 1 0
x y w 2 0 10
z 0 1
2 1 2
2 1
1 1
2
Figure 9.7:
5. [Homework 2, 2002] Three gangsters armed with pistols, Al, Bob, and Curly, are
in a room with a suitcase of money. Al, Bob, and Curly have 20%, 40% and
70% chances of killing their target, respectively. Each has one bullet. First Al
shoots targeting one of the other two gangster. After Al, if alive, Bob shoots,
targeting one of the surviving gangsters. Finally, if alive, Curly shoots, targeting
again one of the surviving gangsters. The survivors split the money equally. Find
a subgame-perfect equilibrium.
6. [Midterm 1 Make Up, 2001] Find all pure-strategy Nash equilibria in Figure 9.8.
Which of these equilibria are can be obtained by backward induction?
7. [Final Make up, 2000] Find the subgame-perfect equilibrium of the following 2-
person game. First, player 1 picks an integer 0 with 1 ≤ 0 ≤ 10. Then, player 2
picks an integer 1 with 0 + 1 ≤ 1 ≤ 0 + 10. Then, player 1 picks an integer 2
with 1 + 1 ≤ 2 ≤ 1 + 10. In this fashion, they pick integers, alternatively. At
each time, the player moves picks an integer, by adding an integer between 1 and
10 to the number picked by the other player last time. Whoever picks 100 wins
the game and gets 100; the other loses the game and gets zero.
L
R
2
2
L L
R R
1
1
0,0 1,3
L
R R
L
2,2 -1,-1
4,2 3,3
Figure 9.8:
O I
2 2
2 L R
1
L R L R
3 0 0 1
1 0 0 3
Figure 9.9:
150 CHAPTER 9. BACKWARD INDUCTION
(d) Which strategies are consistent with all of the following assumptions?
(i) 1 is rational.
(ii) 2 is sequentially rational.
(iii) at the node she moves, 2 knows (i).
(iv) 1 knows (ii) and (iii).
9. [Final 2004] Use backward induction to find a Nash equilibrium for the following
game, which is a simplified version of a game called Weakest Link. There are 4
risk-neutral contestants, 1,2, 3, and 4, with "values" 1 , . . . , 4 where 1 2
3 4 0. Game has 3 rounds. At each round, an outside party adds the value
of each "surviving" contestant to a common account,4 and at the end of third
round one of the contestants wins and gets the amount collected in the common
account. We call a contestant surviving at a round if he was not eliminated at
a previous round. At the end of rounds 1 and 2, the surviving contestants vote
out one of the contestants. The contestants vote sequentially in the order of their
indices (i.e., 1 votes before 2; 2 votes before 3, and so on), observing the previous
votes. The contestant who gets the highest vote is eliminated; the ties are broken
at random. At the end of the third round, a contestant wins the contest with
probability ( + ), where and are the surviving contestants at the third
round. (Be sure to specify which player will be eliminated for each combination of
surviving contestants, but you need not necessarily specify how every contestant
will vote at all contingencies.)
a lobbyist named Alice, stands to gain from the passage of the bill, and the
file-sharing industry, represented by a lobbyist named Bob, stands to lose from
the passage of the bill where 0. Consider the following game.
Use backward induction to compute a Nash equilibrium of this game. (Note that
Alice and Bob are the only players here because the actions of the committee
members are fixed already.)
152 CHAPTER 9. BACKWARD INDUCTION
MIT OpenCourseWare
http://ocw.mit.edu
For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.