Subgame Perfection

Motivating Example¶

We will motivate this chapter using a special case of Selten’s Chain Store Paradox Selten, 1978 which models an incumbent chain of stores that is well established and an entrant to the market.

Campus Caffeine, a mobile coffee van, is considering parking near a university where Latte Lords, a well-established bricks-and-mortar café, has been operating unchallenged. If Campus Caffeine enters, Latte Lords can slash prices for students (Fight) or maintain their premium pricing (Accommodate). If Campus Caffeine stays out, Latte Lords keeps enjoying high margins.

There are three outcomes which are shown as an extensive form game in Figure 1:

• Campus Caffeine chooses to withdraw and does not enter the market: they receive a utility of 1 and Latte Lords continues to have a monopoly with which corresponds to a utility of 5.
• Campus Caffeine enters the market and Latte Lords competes: this leads to low prices that give neither company a profit. They both obtain a utility of 0.
• Campus Caffeine enters and Latte Lords accommodates: they both share the market obtaining a utility of 2.

As described in Mapping Extensive Form Games to Normal Form it is possible to map an extensive form game to a normal form game. In this case we have:

giving:

The incumbent can threaten to fight the entrant however the entrant knows that this threat if carried out would be harmful to both of them. Thus the threat is in essence an empty threat: the entrant will enter and the incumbent will use their best response which is to accommodate.

This is an example of a degenerate game, the Nash equilibria was considered in Example: Support Enumeration for a degenerate game showing that there are in fact 3 of them:

• $((1, 0), (1, 0))$: the entrant enters the market and the incumbent accommodates.
• $((0, 1), (0, 1))$: the entrant withdraws and the incumbent fights.
• $((\frac{3}{4}, \frac{1}{4}), (\frac{1}{4}, \frac{3}{4}))$: a mixture between the two.

This chapter will give the mathematical vocabulary to describe the difference between these equilibria.

Theory¶

To identify emergent behaviour in extensive form games we assume that players not only attempt to optimize their overall utility but optimize their utility conditional on any information set.

Definition: Sequential rationality¶

Sequential rationality: An optimal strategy for a player should maximise that player’s expected payoff, conditional on every information set at which that player has a decision.

With this notion in mind we can now define an analysis technique for extensive form games:

Definition: Backward induction¶

Backward induction: This is the process of analysing a game from back to front. At each information set we remove strategies that are dominated.

Example¶

Let us consider the game shown in Figure 2

We see that at node $(d)$ that Z is a dominated action. So the game reduces as shown in Figure 3.

Player 1s strategy profile is (Y). At node $(c)$ A is a dominated action so that the game reduces as shown in Figure 4.

Player 2s strategy profile is (B). At node $(b)$ D is a dominated action so that the game reduces as shown.

Player 2s strategy profile is thus (C,B) and finally strategy W is dominated for player 1 whose strategy profile is (X,Y). This pair of strategies form a Nash equilibrium.

Theorem of existence of Nash equilibrium in games of perfect information.¶

Every finite game with perfect information has a Nash equilibrium in pure strategies. Backward induction identifies an equilibrium.

Proof:

Recalling the properties of sequential rationality we see that no player will have an incentive to deviate from the strategy profile found through backward induction. Secondly every finite game with perfect information can be solved using backward inductions which gives the result.

Definition: Subgame¶

In an extensive form game, a node $x$ is said to initiate a subgame if and only if $x$ and all successors of $x$ are in information sets containing only successors of $x$.

Example: a game where all nodes initiate subgames¶

A game where all nodes initiate a subgame is given in Figure 6.

Example: a game where all nodes do not initiate subgames¶

A game that does not have perfect information nodes $c$, $f$ and $b$ initiate subgames but all of $b$’s successors do not is shown in Figure 7

The notion of a subgame leads us to define a specific property of some Nash equilibrium.

Definition: Subgame perfect equilibrium¶

A subgame perfect Nash equilibrium is a Nash equilibrium in which the strategy profiles specify Nash equilibria for every subgame of the game.

Let us consider the example in Figure 8.

Let us build the corresponding normal form game:

and

using the above ordering we have:

The Nash equilibria for the above game (found by inspecting best responses in action space) are:

If we take a look at the normal form game representation of the subgame initiated at node b with action sets:

we have:

We see that the (unique) Nash equilibria for the above game is $(D,X)$. Thus the only subgame perfect equilibria of the entire game is $\{AD,X\}$.

Exercises¶

Exercise: Backward induction practice¶

Obtain the Nash equilibrium for the following games using backward induction:

Exercise: Entry, signals, and continuous action¶

Player 1 chooses a number $x \geq 0$, which Player 2 observes. Then, both players simultaneously and independently choose real numbers $y_1, y_2 \in \mathbb{R}$. The utility functions are:

• Player 1: $2y_2y_1 + xy_1 - y_1^2 - \frac{x^3}{3}$
• Player 2: $-(y_1 - 2y_2)^2$

Find the subgame perfect equilibrium of this game.

Exercise: Subgame identification and refinement¶

For each of the following extensive form games:

• Identify all subgames.
• Derive the corresponding normal form representations.
• Find all Nash equilibria.
• Identify which are subgame perfect.

Exercise: Stackelberg ice cream sellers¶

Two ice cream sellers choose locations along a beach represented by $[0,1]$. Customers are uniformly distributed and always go to the nearest seller.

• Player 1 chooses $x_1 \in [0,1]$
• Player 2 observes $x_1$, then chooses $x_2 \in [0,1]$

Each seller’s payoff is the proportion of customers they serve. Assume:

• If $x_1 = x_2$, each serves 50%.
• If $x_1 < x_2$, Player 1 serves $[0, \frac{x_1 + x_2}{2}]$, and Player 2 the rest.
• If $x_2 < x_1$, the roles reverse.

Tasks:

1. Write the payoff functions of each player.
2. Derive Player 2’s best response function $x_2^*(x_1)$.
3. Use backward induction to find the subgame perfect equilibrium.
4. Compare this to the simultaneous move version of the game.

Hint: Think geometrically about the midpoint between locations.

Programming¶

Using Gambit to study an extensive form game¶

The pygambit library can compute equilibria of extensive form games. We define Selten’s Chain Store Paradox as follows:

import pygambit as gbt

g = gbt.Game.new_tree(players=["Incumbent", "Entrant"],
                      title="1 stage Selten's Chain Store Paradox")
g.append_move(g.root, "Entrant", ["Enter", "Withdraw"])
g.append_move(g.root.children[0], "Incumbent", ["Accomodate", "Fight"])
g.set_outcome(g.root.children[1], g.add_outcome([5, 1], label="No entry"))
g.set_outcome(g.root.children[0].children[0], g.add_outcome([2, 2], label="Shared Market"))
g.set_outcome(g.root.children[0].children[1], g.add_outcome([0, 0], label="Competition"))
g

This creates the extensive form game. To convert it to a normal form:

g.to_arrays(dtype=float)

To compute the pure-strategy Nash equilibria:

result = gbt.nash.enumpure_solve(g)
result.equilibria

Notable Research¶

The concept of subgame perfection was first introduced in Selten, 1965 and later reformulated in English in Selten & Bielefeld, 1988, both by Reinhard Selten. The motivating example for this chapter—the Chain Store Paradox—appears in Selten, 1978, where Selten considers multiple sequential market entrants and examines the credibility of entry-deterrence strategies.

The framework was extended in Milgrom & Roberts, 1982, which introduced asymmetric information and reputation effects. These additions showed how players might sustain seemingly irrational threats (such as fighting entry) by considering the beliefs and inferences of future opponents.

The idea of subgame perfection was further refined in Kreps & Wilson, 1982, which introduced the concept of sequential equilibrium, and in Grossman & Perry, 1986, which developed perfect sequential equilibrium. These refinements allow for the analysis of games where off-equilibrium beliefs matter, providing stronger predictions in extensive form games with imperfect information.

Conclusion¶

Subgame perfection refines the concept of Nash equilibrium by requiring that players’ strategies form a Nash equilibrium not just in the game as a whole, but in every subgame—including those off the equilibrium path. This refinement eliminates non-credible threats and ensures sequential rationality at every decision point. Table Table 1 summaries the main concepts of this chapter.

We illustrated these ideas with Selten’s Chain Store Paradox, which highlights how subgame perfection rules out the incumbent’s non-credible threat to fight.