Extensive Form & Subgame Perfect Equilibrium
Extensive Form & Subgame Perfect Equilibrium
Many strategic situations unfold sequentially, with players observing (some of) past actions before choosing. Extensive-form games represent such dynamics via game trees: nodes are decision points, edges are actions, terminal nodes carry payoffs. Information sets group nodes a player cannot distinguish. Backward induction and subgame perfect equilibrium (SPE) refine Nash equilibrium to eliminate non-credible threats — threats that would not be carried out if the game actually reached the relevant subgame.
Subgame Perfect Equilibrium
A strategy profile is a subgame perfect equilibrium (SPE) if it induces a Nash equilibrium in every subgame. A subgame begins at any singleton information set (a node where the mover knows their location) and includes all successors. SPE is computed by backward induction in finite games of perfect information: solve each terminal subgame optimally and fold back, replacing each subgame with its equilibrium value. SPE eliminates Nash equilibria supported by non-credible threats off the equilibrium path.
Backward Induction Theorem (Zermelo 1913)
Every finite game of perfect information has at least one subgame perfect equilibrium in pure strategies, computable by backward induction. The algorithm: label each terminal node with its payoff vector; at each non-terminal node, the mover chooses the action maximizing their payoff given optimally computed continuation values. Ties can be broken arbitrarily. The backward-induction SPE may not be unique when ties exist, but all SPE payoffs coincide in two-player zero-sum games.
Example 1
Find the SPE of the Centipede game with 4 stages. At each stage, the mover can 'Take' (T) or 'Pass' (P). Payoffs grow: T at stage 1 gives (1,0); at stage 2 gives (0,2); at stage 3 gives (3,1); at stage 4 gives (2,4). Compute by backward induction.
Solution: Stage 4 (Player 2 moves): Take gives (2,4), Pass gives nothing after (game ends). Player 2 takes: payoff to P2=4. Stage 3 (Player 1): Take gives (3,1) vs Pass→(2,4). P1 prefers Take (3>2). Stage 2 (Player 2): Take gives (0,2) vs Pass→(3,1). P2 prefers Take (2>1). Stage 1 (Player 1): Take gives (1,0) vs Pass→(0,2). P1 prefers Take (1>0). SPE: every player Takes immediately. Outcome: (1,0). This backward-induction prediction contradicts experimental evidence — subjects often pass for mutual gain.
Example 2
In the Entry Deterrence game, an Entrant chooses Enter or Stay Out. If Enter, the Incumbent chooses Fight or Accommodate. Payoffs: (Stay Out)=(0,2); (Enter,Fight)=(-1,-1); (Enter,Accommodate)=(1,1). Find all Nash equilibria and identify the SPE.
Solution: Nash equilibria: (Enter, Accommodate) — SPE — since if Entrant enters, Incumbent prefers Accommodate (1>-1). Also (Stay Out, Fight) is a Nash equilibrium (Entrant gets 0 from staying out; Fight is Incumbent's strategy but never reached). However, Fight is non-credible: if actually asked to choose, Incumbent prefers Accommodate. SPE eliminates (Stay Out, Fight): the unique SPE is (Enter, Accommodate). This illustrates the essential role of credibility in strategic interaction.
Practice
- Find the SPE of a 3-stage alternating-offer bargaining game (Rubinstein model truncated at 3 periods) with discount factor $\delta=0.9$ and pie size 1.
- Show that every Nash equilibrium of a finite perfect-information game can be interpreted as a subgame perfect equilibrium of some perturbed game.
- In the Stackelberg duopoly, firm 1 chooses quantity $q_1$ first, then firm 2 chooses $q_2$. With inverse demand $P=a-Q$ and zero costs, find the SPE quantities and compare to Cournot (simultaneous).
- Prove that backward induction payoffs in a two-player zero-sum game equal the minimax value.
Show Answer Key
1. Backward induction with $\delta=0.9$: Period 3 (last): proposer offers 0 to responder, keeps 1. SPE share to proposer: 1. Period 2: proposer offers $\delta\cdot1=0.9$ kept, gives responder $\delta\cdot0=0$... Actually: P2 offers R the continuation $\delta\cdot0=0$; wait, let me redo. Period 3: P1 proposes (1,0), accepted. Period 2: P2 must offer P1 at least $\delta\cdot1=0.9$, so P2 proposes $(0.9,0.1)$. Period 1: P1 offers P2 at least $\delta\cdot0.1=0.09$, so P1 proposes $(0.91,0.09)$. SPE: P1 gets 0.91, P2 gets 0.09.
2. This is a consequence of Kuhn's theorem: in games of perfect recall, every mixed strategy NE payoff can be achieved by a behavioral strategy NE, which is an SPE of some perturbed game. More precisely, every NE of a finite extensive-form game with perfect information corresponds to an SPE when players cannot make non-credible threats.
3. Firm 2's best response: $q_2=(a-q_1)/2$. Firm 1 anticipates this: $\max_{q_1}q_1(a-q_1-(a-q_1)/2)=q_1(a-q_1)/2$, giving $q_1^*=a/2$, $q_2^*=a/4$. Cournot (simultaneous): $q_1=q_2=a/3$. Stackelberg leader produces more ($a/2>a/3$), total output is higher ($3a/4>2a/3$), price is lower.
4. In a two-player zero-sum game, backward induction gives each player their minimax value at every subgame. Since the game is zero-sum, player 1's BI payoff = maximin = minimax value, and similarly for player 2. This follows because the value of each subgame equals the minimax value of that subgame.