Extensive Form Games
Extensive Form Games
Extensive Form Games
Jonathan Levin
January 2002
1 Introduction
The models we have described so far can capture a wide range of strategic
environments, but they have an important limitation. In each game we have
looked at, each player moves once and strategies are chosen simultaneously.
This misses a common feature of many economic settings (and many classic
games such as chess or poker). Consider just a few examples of economic
environments where the timing of strategic decisions is important:
These notes take up the problem of representing and analyzing these dynamic strategic environments.
1
2.1 Examples
Firm 2
Out
In
Firm 1
2, 0
Fight
-1, 1
Accomodate
1, 1
P (q1 + q2) = 1 (q1 + q2). Lets assume that the two rms have constant marginal costs, c = 0. To keep the picture simple, we think of q
i
Firm 1
qH
qL
Firm 2
qL
qH
qL
qH
Player 1
Player 2
H
1,-1
-1,1
-1,1
1,-1
Player 2
H
1,-1
-1,1
-1,1
1,-1
Example We can also have more complicated games, where players move
multiple times, or select which player will move.
1
2
2.3
Strategies
Denition 3
Matching Pennies, cont. For our two versions of Matching Pennies, the
normal forms are:
HH HT TH TT
H 1, 1 1, 1 1, 1 1, 1
T 1, 1 1, 1 1, 1 1, 1
H
T
H 1, 1 1, 1
T 1, 1 1, 1
In the rst version, Player two has a winning strategy in the sense that
she can always create a mismatch if she adopts the strategy TH. Any
strategy for player one, coupled with this strategy for player two is a
Nash equilibrium. In the second version, the Nash equilibrium is for
both players to mix 12 H + 12 T .
Entry Game, cont. For the entry game above, the normal form is:
Out In
F 2, 0 1, 1
A 2, 0 1, 1
There are several Nash equilibria: (A, In), (F, Out) and (F + (1
)A, Out) for any 1/2.
Note that in the entry game, some of the Nash equilibria seem distinctly
less intuitive that others. For instance, in the (F, Out) equilibrium, it is the
threat of Fight that keeps Firm 2 from entering. However, if Firm 2 were to
enter, is it reasonable to think that Firm 1 will actually ght? At this point,
it is not in Firm 1s interest to ght, since it does better by accomodating.
Consider another example, where this problem of incredible threats arises
in way that is potentially even more objectionable.
s1 = q1
and
s2 =
1q1
2
1 q1
6
if q1 = q1
if q1 = q1
Lets check that these are all equilibria. First, given Firm 2s strategy,
Firm 1 can either set 1 = 1, or 1 = 1 . If it does the former, the
eventual price will be zero, and Firm 1 will make zero prots. If it
does the latter, then Firm 1 will make prots:
1
1
1
=
1 1 1
1 1 1 0.
2
2
Now, consider Firm 2. Does it have a strategy that yields strictly
higher payo. Clearly, changing its strategy in response to 1 = 1
will have no eect on its payo given Firm 1s strategy. On the other
hand, in response to 1 = 1, its best response solves:
q
max
q2
q2
1 1
q
q2
Entry Game, cont. In the entry game, there are two subgames. The entire
game (which is always a subgame) and the subgame after Firm 2 has
entered the market.
Example In game below, there are four subgames: (1) The entire game,
(2) the game after player one chooses R, (3) the game after player
one choose L, and (4) the game after Player 1 chooses L and player 2
chooses l.
1
L
Consider the model of Stackleberg Competition where Firm 1 moves rst and
chooses quantity q1, and then Firm 2 moves second and chooses quantity
q2 . Once both rms have chosen quantities, the price is determined by:
( ) = 1 , where = 1 + 2. So that we can compare this model
to Bertrand and Cournot competition, lets assume that both rms have
constant marginal cost equal to 0 1.
To solve for the subgame perfect equilibrium, we work backward. Suppose that Firm 1 has set some quantity 1. Then Firm 2s best response
solves:
max
2 (1 1 2 )
q2
P Q
c <
.
2 ( 1 ) = max 0
2
Now consider the problem facing Firm 1, knowing that if it chooses 1 ,
Firm 2 will respond with a quantity 2 ( 1 ). It solves
max
1 (1 1 2 ( 1 ) )
q1
c
q ,
= 1 2
and
q2
q1
dq2
dq1
= 1 4
The total quantity is 34 (1 ) and the price is S = (1 + 3 ) 4 In comparison, under Cournot competition, both rms set identical quantity 13 c , so
total quantity is 23 (1 ) and the price is C = (1 + 2 ) 3
c
c / .
c / .
q2
1-c
q1 = BR(q 2)
Cournot
Stackelberg
q2 = BR(q 1)
0
.
1-c
q1
Stackelberg Competition
Relative to Cournot, in Stackelberg Competition, the Leader (Firm 1)
can choose any point on the Followers (Firm 2s) best-response curve. Note
that this game has a rst-mover advantage in the sense that there is an
advantage to being the leader.
9
4.3
Backward Induction
Denition 6 An extensive form game is said to have perfect information if each information set contains a single node.
Proposition 7 (Zermelos Theorem) Any nite game of perfect information has a pure strategy subgame perfect equilibrium. For generic payos,
there is a unique SPE.
strategy SPE (and for generic payos, the unique SPE), we rst consider all
nodes x in stage K . Each node starts a subgame, so by NE the player who
moves must maximize his or her expected payo. Identify the optimal choice
(generically, it will be unique). Now move back to stage K 1, and consider
the problem facing a player who moves here. This player can assume that at
stage K , play will follow the choices just identied. Since each node starts a
subgame, we look for the payo-maximizing choice facing a player who gets
to move. Once these choices have been identied, we move back to stage
K 2. This process of continues until we reach the beginning of the game,
at which point we will have at least one (and typically no more than one).
Q.E.D.
10
1
L
R
2
0, 2
A
1, 1
0, 1
We can use backward induction even in games without perfect information as the next example demonstrates.
Example To use backward induction in the game below, we rst solve for
the subgame perfect equilibrium after Firm 2 has entered. We see that
the unique equilibrium in this subgame is for both Firm 1 and Firm
2 to play D. (Note that this subgame is a prisoners dilemma. Hence
Firm 2 will choose not to enter at the rst node.
Firm 2
In
Out
Firm 1
2,
D
Firm 2
C
1,1
-1,2 2,-1
D
0,0
Player 1
S
R
Player 2
80, 50
A
20, 68
90, 70
2
In
1, 0
1
In
0, 2
2
In
In
3, 1
2, 4
12
2
In
5, 3
7, 5
In
4, 6
m
p2 (p1) =
1 ifif 11 [ ] .
Thus, for any 1 , Firm 1 gets the entire market but loses money, which
for any 1 , Firm 1 gets no demand. It follows that any pair ( 1 2( 1))
with 1 is an SPE.
Note that compared to the Bertrand (simultaneous move) equilibrium,
the price may be higher. In particular, both Firms 1 and 2 set (weakly)
higher prices. Moreover, Firm 2 (the follower) does better than in the simultaneous game, while Firm 1 does the same. Thus we say the game has
a second mover advantage.
p
> p
c, p
< c
< c
p ,p
13
p2
p2 = BR(p 1)
Bertrand
Stackelberg
(1+c)/2
p1 = BR(p 2)
0
p1
(1+c)/2
ollower Games
General Leader-F
The Stackelberg models of imperfect competition are examples of what Gibbons calls Leader-Follower games. These games have the following structure:
1. Player 1 moves rst and chooses an action a1 A1.
2. Player 2 observes a1 and chooses an action a2 A2.
There is a simple algorithm to identify the subgame perfect equilibria
of this sort of game. We just apply backwards induction. We rst dene
player 2s best response to any action by Player 1:
(a , a ).
a2(a1) = arg amax
A 2 1 2
2
We then identity what player one should do, assuming that player two will
best respond. To do this, dene:
a1 = arg amax
(a , a(a )) .
A 1 1 2 1
1
6 Strategic Pre-Commitment
We now turn to a class of problems that arise frequently in industrial organization. These problems have the following structure. First, one player
(Firm 1) has the opportunity to take some sort of action or investment
for instance, installing capacity, investing in a cost-saving technology or in
product development, signing an exclusive contract with a key upstream
suppliers, building a relationship with customers, or so on. Then Firm 2 decides whether or not to enter the market. Finally, rms compete with Firm
1 either operating as a monopoly or the two rms competing as a duopoly.
By taking an action in advance of competition, Firm 1 has the opportunity to strategically pre-commit (just as the Stackelberg leader pre-commits
to a price or quantity). It turns out that it is possible to give a very intuitive
analysis of the economics of pre-commitment by using the idea of strategic
complements and substitutes.1 This analysis can then be used to shed light
on a range of problems in industrial organization and other elds.
1
This section is drawn from Tirole (1988, Chapter 8). See Fudenberg and Tirole (1984,
AER) or Bulow, Geanokoplos and Klemperer (1985, JPE) for the original analyses.
15
a2
a2
Strategic Complements
Strategic Substitutes
a 1 = BR2(a 2)
a2 = BR1(a 1)
a2 = BR1(a 1)
a1 = BR2(a 2)
a1
a1
We have already seen that in Cournot Competition, quantities are strategic substitutes, while in dierentiated products Bertrand Competition, prices
are strategic complements.
Proposition 9 Suppose for i = 1, 2,. is twice continuously dierentiable.
0 and strategic substitutes if
Then G has strategic complements if a2a
2
a a 0.
i
For those of you who took Econ 202, these conditions should look very
familiar from our study of Monotone Comparative Statics. A good exercise
is to try to prove this result using Topkis Theorem.
Note that Leader-Follower games are a special case of this setting. To get the LeaderFollower case, let A1 be a singleton, and think of k as Firm 1s action and a2 as Firm 2s
action.
2
16
We assume that for any choice k, the competition subgame has a unique
Nash Equilibrium, which we can denote ac1 (k), ac2(k). Payos in this game
are given by:
i (k, ac1 (k) , ac2 (k)) for i = 1, 2.
Thus given a choice of k, Firm 2 will choose to enter if
2 (k, ac1(k), ac2 (k)) > 0.
If Firm 2 does not enter, then Firm 1 sets chooses the monopoly strategy
am
1 . Payos are
for Firm 1 and zero for
investment.
We say that:
m
m
1 (k, a1 (k ))
Firm 2. Let k denote the
Entry Deterrence
Lets rst consider SPE in which entry is deterred. In this case, Firm 1
need to choose a level of k that makes Firm 2 less protable. Indeed, it will
choose an investment k such that:3
2 (k, ac1 (k), ac2(k)) = 0.
The fact that Firm 1 will choose k to make Firm 2s competition prots exactly zero
follows from the assumption that entry is not blockaded and that payos functions are
concave.
3
17
Hence:
d2
dk
2
k
direct eect
2 a1
a1 k
strategic eect
d 2 >
dk
0.
tough
if
d2 <
dk
0. Investment
Top Dog
Example: Reducing Own Costs Suppose that Firm 1 has the opportu-
q2
q1 = BR(q2;kH)
q1 = BR(q 2;kL)
0
0
q2 = BR(q 1)
q1
Figure 1:
2, making Firm 1 tough. However, there may be a second eect. If
Firm 1 cannot price discriminate, it may be tempted to set a high price
to take advantage of its locked in customers. This strategic eect can
work to make Firm 1 soft. The overall eect is ambiguous. Thus either
a top dog strategy or a lean and hungry look might work to deter
entry depending on the specics.
Suppose now that Firm 1 nds it too costly to deter entry. How should it
behave in order to make more prots once Firm 2 enters? In this case, Firm
1 is interested in choosing its investment to maximize:
1 (k, ac1 (k) , ac2 (k)) .
1
k
direct eect
1 da2
.
a2 dk
strategic eect
That is, the rst term is the direct eect. This would exist even if investment
was not observed by Firm 2. The strategic eect results from the fact that
Firm 1s investment can change the way Firm 2 will compete.
Lets investigate the strategic eect further. To do this, lets assume
that the second-period actions of the two rms have the same nature in the
19
sense that 1/a2 has the same sign as 2/a1. For instance, either both
rms choose quantities or both choose prices. Then:
Thus,
dac2
dk
dac2 da1
da1 dk
1 da2
dBR2 (a1 )
1 da2
= sign
sign
a2 dk
a2 dk
da1
Assuming that 2/k = 0, we can identify the sign of the strategic eect
sign
with two things: (1) whether investment makes Firm 1 Tough or Soft (the
rst term) and (2) whether there are strategic substitutes or complements
(the second term). We have four cases:
If investment makes Firm 1 tough and reaction curve slope down,
investment by Firm 1 softens Firm 2s action thus Firm 1 should
overinvest (top dog).
If investment makes Firm 1 tough and reaction curves slope up, Firm
1 should overinvest so as not to trigger an aggressive response by Firm
2 (puppy dog).
If invesmtnent makes Firm 1 soft and reaction curves slope down, Firm
1 should stay lean and hungry.
If invesment makes Firm 1 soft and reaction curves slope up, Firm 1
should overinvest to become a fat cat.
To summarize,
Investment makes Firm 1
Tough
Soft
Strategic Complements Puppy Dog
Fat Cat
Strategic Substitutes
Top Dog Lean and Hungry
Example: Reducing Costs Suppose Firm 1 can invest to reduce its costs
before competing. With Cournot competition, the strategic eect to
make Firm 1 more aggressive. The equilibrium changes so that Firm 2
ends up producing less. Thus Firm 1 wants to be a Top Dog and invest
heavily. On the other hand, if Firm 1 can reduce its costs before price
competition, the strategic eect is to make Firm 1 more aggressive
so that in equilibrium Firm 2 ends up pricing more aggressively as
well. Thus, Firm 2 might want to be a Puppy Dog to soften price
competition.
20
6.5
1. Product Dierentiation. Suppose Firm 1 can choose its products location prior to competing in price with Firm 2. Producing a
product that is close to Firm 2s will tend to make price competition
more intense, lowering prices and prots. To deter entry or to drive
Firm 2 from the market, Firm 1 might want to adopt a Top Dog
strategy. But to change the nature of competition in a favorable way,
Firm 1 might want to adopt a Puppy Dog ploy and dierentiate its
oering from Firm 2s.
2. Most-Favored Customer Clause. With price competition, if Firm
1 wants to accomodate Firm 2, it wants to look inoensive so as to
keep Firm 2 from cutting price. In particular, it would like to commit
itself to charging high prices (a Puppy Dog ploy). One way to do
this is most-favored customer clauses. Firm 1 can write contracts with
its customers promising that if it ever oers a low price to another
customer, the original customer can get the new low price. This makes
it very costly for Firm 1 to drop prices, eectively committing itself
to be unaggressive in competing with Firm 2.
3. Advertising. Suppose Firm 1 can invest in advertising that makes
customer more excited not just about its own product, but about
the whole market. This kind of advertising makes Firm 1 soft. To
deter entry, Firm 1 should not do much of this sort of advertising
rather it should run advertisements that increase the demand for its
own product and decrease the demand for other rms product. But
what if Firm 2 surely plans to enter. If competition is in prices, then
Firm 1 will want to advertise in a way that increases demand (direct
eect) and in a way that softens price competition (for example by
establishing separate niches for dierent products in the market). This
is a fat cat approach to advertising.
4. Leverage and Tying. An old story in IO is that a rm with monopoly
power in one market can leverage this power to monopolize a second.
(Think Microsoft and browsers.) One way to do this is to tie the two
products together. Suppose that there are two markets, that Firm 1
has a monopoly in the rst, and that Firms 1 and 2 may compete in
prices in the second. Firm 1 must decide whether to bundle or tie its
two products. The question is how this action will eect its pricing
behavior. This depends on how we model demand, but in many cases,
21
bundling will make demand more elastic. This leads Firm 1 to price
more aggressively in response to Firm 2s prices. It follows that from
a strategic point of view, bundling is a top dog strategy that works to
deter entry. But if entry is to be accomodated, it may be better to use
the puppy dog ploy of not bundling.
22