Lecture 4: Dynamic games with complete information I
1 Finite-stage games of complete and perfect information
1.1 Motivating story
Consider the following two-stage game:
1. Player 1 has $1000 and chooses between two options: keep the money, or give all the
money to player 2.
2. After observing player 1’s move: player 2 chooses whether to explode a grenade that
will kill both players
Assume that both players prefer having money to not having money if they are alive, and
both prefer to be alive.
• (give, not explode) can be a Nash equilibrium outcome, if player 2 chooses the strategy:
“I’ll explode the grenade unless you give me the money!” In this equilibrium, giving
the money is player 1’s best response to player 2’s strategy, and when player 1 indeed
gives the money, not to explode is player 2’s best response.
• However, this Nash equilibrium is based on a non-credible threat: If player 1 does not
give the money in stage 1, player 2, in fact, does not want to explode the grenade and
kill himself.
• In other words, player 2’s strategy is not a best response when player 1 does not play
the equilibrium strategy (give money). => Although (give, not explode) is a Nash
equilibrium, it is not a very likely prediction.
• We can make a better prediction using backward induction:
– Start from player 2. His best response is: regardless of player 1’s strategy, player
2 should never explode the grenade
– Go back to player 1: knowing that player 2 never explodes the grenade, player 1
should not give the money.
– This leads to (not give, not explode)
1
– It is not only a Nash equilibrium, but it is also a subgame perfect Nash equi-
librium: player 2’s strategy (never explode) is a best response to every possible
action that player 1 can take (each of player 1’s action leads to a subgame).
• Idea: in a dynamic game, many strategy profiles can be NE because players can make all
kinds of threats to induce their preferred outcome. However, many of those threats are
not credible and, therefore, the NE with non-credible threats are not good predictions
of the game. To get better prediction, we use backward induction to find subgame
perfect NE.
1.2 Extensive-form representation
1.2.1 Represent the motivating story in an extensive form (i.e. the game tree)
Definition 1. A proper subgame in an extensive-form game
(a) begins at a decision node n that is a singleton information set (defined later) but is
not the game’s first decision node
(b) includes all the decision and terminal nodes following n in the game tree
(c) does not cut any information sets
2
Find the subgame perfect equilibrium using backward induction:
Definition 2. A Nash equilibrium is subgame-perfect if the players’ strategies constitute
a Nash equilibrium in every subgame.
Remark 1. If an equilibrium involves non-credible threat, then some player’s strategy must
involve suboptimal response in a subgame that is not reached in the equilibrium.
3
1.2.2 Transform an extensive-form representation into a normal-form represen-
tation
Player 2
(Not exp, Not exp) (Not exp, Exp) (Exp, Not exp) (Exp, Exp)
Player 1
Give 0, 1000 0, 1000 -∞, -∞ -∞, -∞
Keep 1000, 0 -∞, -∞ 1000, 0 -∞, -∞
• Notation for Player 2’s strategies:
(X, Y) = “Do X if Player 1 chooses Give and Y if Player 1 chooses Keep”
Definition 3. A strategy for a player is a complete plan of action. It specifies a feasible
action for the player in every contingency in which the player might be called on to act.
• Distinguish equilibrium from equilibrium outcomes: when writing down a NE, we must
specify the full strategy for each player
Nash equilibria Equilibrium outcomes
(Give, (Not Exp, Explode) ) (Give, Not Exp)
(Keep, (Not Exp, Not Exp) ) (Keep, Not Exp)
(Keep, (Explode, Not Exp) ) (Keep, Not Explode)
1.2.3 Transform a normal-form representation into an extensive-form represen-
tation
• Recall: Prisoners’ dilemma in normal form
Prisoner 2
Confess Not Confess
Prisoner 1
Confess -1, -1 -9, 0
Not Confess 0, -9 -6, -6
• Transform into extensive form:
– Prisoner 1 moves first. Then, Prisoner 2 moves without knowing what was
Prisoner 1’s move.
4
Definition 4. An information set for a player is a collection of decision nodes satisfying:
(i) the player has the move at every node in the information set, and
(ii) when the play of the game reaches a node in the information set, the player with the
move does not know which node in the information set has been reached
• This game does not have any proper subgame because Prison 2’s information set is not
a singleton.
1.3 Stackelberg Model of Duopoly
1.3.1 Set Up
• Players: two firms, 1 and 2
• Stage 1: Firm 1 chooses quantity q1 ≥ 0
• Stage 2: After observing q1, Firm 2 chooses quantity q2 ≥ 0
• Payoffs: firms’ profits are determined in the following way
– Market demand has a downward slope: P (q1, q2) = 100− q1 − q2
– Total cost to product qi for each firm is Ci(qi) = 10qi for i = 1, 2
– Profit for each firm is Revenue – Cost, i.e.
π1(q1, q2) = q1 (100− q1 − q2)− 10q1
π2(q1, q2) = q2 (100− q1 − q2)− 10q2
• Set up similar to Cournot, except that the firms move sequentially
5
1.3.2 Solve the subgame-perfect equilibrium using backward induction
• Start with firm 2
max
q2
π2(q1, q2) = q2 (100− q1 − q2)− 10q2
qs2 (q1) =
1
2
(90− q1)
• Knowing firm 2’s best response function, firm 1 solves
max
q1
π1 (q1, q
s
2 (q1)) = q1 [100− q1 − q
s
2 (q1)]− 10q1
max
q1
q1
[
100− q1 −
1
2
(90− q1)
]
− 10q1
100− 2q1 − 45 + q1 − 10 = 0
qs1 = 45, q
s
2 =
1
2
(90− 45) = 22.5
πs1 = 1012.5, π
s
2 = 506.25
1.3.3 Recall: Cournot equilibrium
• Recall that in the Cournot model, qc1 = qc2 = 30, πc1 = πc2 = 900.
• The Cournot outcome can still be an equilibrium outcome in the Stackelberg model:
– if firm 2’s strategy is to choose q2 = 30 regardless of q1 , then firm 1 will choose
q1 = 30 as a best response.
– But this is not a subgame perfect equilibrium: firm 2’s strategy is a non-credible
threat because it will want to choose 22.5, not 30, when q1 = 45.
• Compare Cournot vs. Stackelberg:
– πs1 > π
c
1 “first mover advantage”
– πs2 < π c 2 – Note that firm 2 is better informed in the Stackelberg game than in the Cournot game, yet its profit is lower – One can be worse off with more information – Firm 2 can improve its profit by credibly staying ignorant of firm 1’s move 6 1.4 Sequential Bargaining 1.4.1 Three-period bargaing • Day 1: $10 to split – Player 1 proposes (player 1’s share, player 2’s share) = (s1, 1− s1) – Player 2 either accepts (game ends) or rejects (proceed to day 2) • Day 2: $9 to split – Player 2 proposes (player 1’s share, player 2’s share) = (s2, 1− s2) – Player 1 either accepts (game ends) or rejects (proceed to day 3) • Day 3: $8 in total, each player gets $4. Assume that a player accepts an offer when he is indifferent between acceptance and rejection. Use backward induction to find the SPE outcome: • Day 2 – Player 1 accepts if and only if 9s2 ≥ 4, s2 ≥ 49 . – Player 2 proposes (4 9 , 5 9 ) and player 1 accepts • Day 1 – Player 2 accepts if and only if 10(1− s1) ≥ 5, s1 ≤ 12 . – Player 1 proposes (1 2 , 1 2 ) and player 2 accepts 2 Practice problems 1. The money-grenade game with commitment Consider the money-grenade game covered in Lecture 4. Now, suppose that Player 2’s grenade is synced with a deposit machine that has the following four modes: (i) ignite the grenade in 30 seconds unless a deposit of $1000 is made to Player 2, (ii) ignite the grenade in 30 seconds if a deposit of $1000 is made to Player 2; otherwise, don’t ignite, (iii) always ignite the grenade in 30 seconds, and (iv) never ignite the grenade Before Player 1 decides whether to give $1000 to Player 2 or to keep the money, Player 2 switches the machine to one of these modes. Once switched, the mode cannot be changed. a. Write down the extensive-form representation of this game (i.e., the game tree). b. Find the subgame perfect equilibrium using backward induction. c. Is there any Nash equilibrium in which Player 1 keeps the money? 7 2. Consider the following entry deterrence game, where an entrant decides whether to enter a market or not, and the incumbent decides whether to fight or accommodate the entrant if he enters. When the entrant stays out, the payoff of the entrant is 0 and the payoff of the incument is 2. When the entrant enters the market, if the incumbent fights with a price war then both firms gets -1; if the incumbent accommodates then both get 1. a. How many proper subgames are there? Specify the proper subgame(s) of this game. b. Find the subgame perfect equilibrium using backward induction. c. Is there any other Nash equilibrium? 3. Three-period sequential bargaining (Gibbons 2.1.D) Player 1 and 2 are bargaining over one dollar. They alternate in making offers: (a) At the beginning of the first period, player 1 proposes to take a share s1 of the dollar, leaving 1− s1 for player 2. Player 2 either accepts the offer (in which case the game ends) or rejects the offer (in which case play continues to the second period). (b) At the beginning of the second period, player 2 proposes that player 1 take a share s2 of the dollar, leaving 1− s2 for player 2. Player 1 either accepts the offer (in which case the game ends) or rejects the offer (in which case play continues to the third period). 8 (c) In the third period, the dollar is split evenly between the players, i.e., each gets 50 cents and the game ends. In addition, assume that (i) a player accepts an offer when he is indifferent between acceptance and rejection, and (ii) the players are impatient and they discount payoffs received in later periods by a factor of 0.9 per period. E.g., at the beginning of period 1, player 1’s utility is 0.9 for the event “receiving one dollar in period 2” and 0.81 for the event “receiving one dollar in period 3”. Find the subgame perfect equilibrium by backward induction: a. If the players enter the second period, what offer should player 2 propose? Does player 1 accept the offer? b. What offer should player 1 propose in the first period? Does player 2 accept the offer? 9