Subgame Perfect Equilibrium

A subgame perfect equilibrium (SPE) is a strategy profile that is a Nash equilibrium not only of the whole game but of every subgame of it, reached or not. Reinhard Selten introduced the idea in 1965 to solve a specific defect of Nash equilibrium in games that unfold over time: Nash is blind to what happens off the path of play, and so it certifies as “equilibrium” plans that rest on threats the threatener would never carry out. The Nobel committee’s 1994 citation puts the motivating example in three sentences: “Imagine a monopoly market where a potential competitor is deterred by threats of a price war. This may well be a Nash equilibrium … and the threat is of no cost to the monopolist because it is not carried out. But the threat is not credible if the monopolist faces high costs in a price war” (Nobel press release, 11 October 1994). Subgame perfection is the “systematic formalization of the requirement that only credible threats should be taken into account,” and the committee calls it “the most fundamental refinement of Nash equilibrium.” In games of perfect information it is exactly Backward Induction; its real content is that it keeps working when parts of the game are simultaneous, and its real limitation is that it goes silent exactly when the game has no proper subgames — which is where sequential equilibrium and Imperfect Information and Information Sets take over.

Mental Model

Nash equilibrium asks a single question about a whole strategy profile: given what everyone else is doing, can any one player do better by switching to a different complete plan? The question is asked once, from the root, about the outcome that actually occurs. Everything that would have happened elsewhere is invisible, because it does not affect the payoff.

That blindness is fine in a one-shot simultaneous game, where “elsewhere” does not exist. In a game that unfolds over time it is a disaster, because in an extensive-form game a strategy is not a move — it is a complete contingent plan, a specification of what you would do at every decision point you own, including decision points your own earlier choices make unreachable. Nash equilibrium never audits the unreachable parts of the plan. And the unreachable parts of the plan are precisely what the other player is responding to.

The Stanford Encyclopedia states the diagnosis exactly: “Mere NE analysis doesn’t notice this because NE is insensitive to what happens off the path of play. … In analyzing extensive-form games, however, we should care what happens off the path of play, because consideration of this is crucial to what happens on the path” (SEP, Game Theory, §2.6).

Subgame perfection fixes it by asking the Nash question once per subgame instead of once per game.

flowchart TB
    subgraph nash["Nash equilibrium: one audit"]
        NR["root"]
        NP["realised path"]
        NX["everything off the path<br/>NEVER CHECKED"]
        NR --> NP
        NR -.-> NX
    end
    subgraph spe["Subgame perfection: one audit per subgame"]
        SR["root - audited"]
        S1["subgame at node A<br/>audited"]
        S2["subgame at node B<br/>audited"]
        S3["subgame at node C<br/>audited"]
        SR --> S1
        SR --> S2
        S1 --> S3
    end

    style NX fill:#ffd0d0
    style S1 fill:#d9f2d9
    style S2 fill:#d9f2d9
    style S3 fill:#d9f2d9

What this diagram shows. The structural difference between the two solution concepts. Nash checks the profile once, against the outcome it produces; every branch that is not taken is untested, so a plan may contain arbitrary nonsense there and still pass. Subgame perfection re-runs the same test inside each subgame, so a plan must be sensible everywhere. The insight to take away: SPE adds no new idea about rationality — it applies the same Nash test more often. That is why the Encyclopedia calls it “persuasive … it does not demand ‘extra’ rationality of agents in the sense of expecting them to have and use philosophical intuitions about ‘what makes sense’.”

What a Subgame Is, Precisely

The word “subgame” is more restrictive than “subtree”, and getting the restriction wrong is the most common error in applying the concept. Bonanno’s definition is the crisp one (Bonanno, Game Theory, Definition 3.3):

Definition. A proper subgame of an extensive-form game is obtained as follows:

1. start from a decision node x, different from the root, whose information set consists of node x only, and enclose in an oval node x itself and all its successors;
2. if the oval does not “cut” any information sets (that is, there is no information set S and two nodes y, z ∈ S such that y is a successor of x while z is not) then what is included in the oval is a proper subgame, otherwise it is not.

Three requirements, and each one exists for a reason.

• The starting node must be a singleton information set. If a player does not know which of two nodes she is at, you cannot ask “what is the equilibrium of the game starting here” — “here” is not well-defined for her. Kreps and Wilson make the point in payoff terms: at a node inside a non-singleton information set “player 3 is unable to compute his expected utility in this subgame” (Kreps & Wilson 1982, Sequential Equilibria, §4).
• The oval must contain all successors. A subgame is a whole tail of the game, not a slice of it.
• The oval must not cut any information set. If it did, some player inside the subgame would be uncertain about something that happened outside it, and the subgame would not be a game in its own right.

The qualifier proper excludes the whole game, which is trivially a subgame of itself — Bonanno’s analogy: “a proper subgame is analogous to a proper subset.” A subgame with no proper subgame strictly inside it is called minimal, and minimal subgames are where the solving algorithm starts.

flowchart TB
    R(("root<br/>P1"))
    X(("x<br/>P2 - singleton"))
    Y(("y<br/>P3 - in a<br/>two-node info set"))
    Z(("z<br/>P3 - other node<br/>of that info set"))
    LX1["leaf"]
    LX2["leaf"]
    LY["leaf"]
    LZ["leaf"]

    R -->|a| X
    R -->|b| Y
    R -->|c| Z
    X --> LX1
    X --> LX2
    Y --> LY
    Z --> LZ

    Y -. same information set .- Z

    OK["subgame at x: VALID<br/>singleton, all successors, cuts nothing"]
    BAD["subgame at y: INVALID<br/>the oval would cut P3's information set,<br/>leaving z outside"]

    X -.-> OK
    Y -.-> BAD

    style OK fill:#d9f2d9
    style BAD fill:#ffd0d0

What this diagram shows. The two ways a candidate subgame can fail. Node x starts a valid proper subgame: it is a singleton information set and everything below it is self-contained. Node y does not: y and z are in the same information set for player 3, so enclosing y and its successors would separate two nodes that player 3 cannot distinguish. The insight to take away: the number of proper subgames in a game is a structural property, and it can be as low as zero. When it is zero, SPE and Nash are the same concept — which is the failure mode this note builds toward.

The Definition, and Why Every SPE Is Nash but Not Conversely

Bonanno’s Definition 3.5, stated exactly: given an extensive-form game and a strategy profile s for the entire game, s is a subgame-perfect equilibrium if (1) s is a Nash equilibrium of the entire game, and (2) for every proper subgame G, the restriction s|G — “that part of s which prescribes choices at every information set of G and only at those information sets” — is a Nash equilibrium of G.

Levin’s phrasing collapses the two clauses into one by exploiting the fact that the whole game is a subgame of itself: “A strategy profile s is a subgame perfect equilibrium of G if it induces a Nash equilibrium in every subgame of G. Note that since the entire game is always a subgame, any SPE must also be a NE” (Levin, Extensive Form Games, Definition 5).

So the inclusion SPE ⊆ Nash is immediate and definitional. The interesting direction is the strictness, and it is worth having a number rather than an assertion. I enumerated every pure strategy profile of the n-node centipede game and classified each one both ways (code and method below):

n (decision nodes)	pure strategy profiles	pure Nash equilibria	subgame perfect
2	4	1	1
4	16	4	1
6	64	16	1
8	256	64	1
10	1,024	256	1
12	4,096	1,024	1
14	16,384	4,096	1
16	65,536	16,384	1

The Nash count is exactly 2^(n−2) and grows without bound; the subgame-perfect count is 1 for every n. At n = 16 the refinement discards 16,383 of 16,384 equilibria. Every one of the discarded profiles produces the same observable outcome — the first mover takes at node 1 — and differs only in what the players plan to do at nodes that are never reached. That is precisely what a refinement of Nash equilibrium is for: it prunes plans, not outcomes, and it prunes them on the grounds that the unreached parts of the plan are not credible.

Uncertain

Verify: whether every pure Nash equilibrium of every centipede specification shares the backward-induction outcome, or only of the doubling-pot specification measured here. Reason: I verified the “all Nash equilibria stop at node 1” claim computationally for n ≤ 16 on the McKelvey–Palfrey doubling-pot payoffs only, and the SEP states it for Sobel’s take-one-or-two-bills variant. Reason for doubt: the result depends on the payoff inequality large_pile[i] > small_pile[i+1] holding at every node, which is a property of the specification and not of centipedes in general. To resolve: state the inequality as a hypothesis and check whether published centipede variants (constant-sum versions in particular) satisfy it.

The Incredible Threat, Worked Concretely

The canonical application is entry deterrence, and the reason it is canonical is that the incredible equilibrium is the interesting-looking one: it is the equilibrium in which the monopolist keeps the market.

Take Selten’s chain-store stage game exactly as Kreps and Wilson reproduce it (Kreps & Wilson, Reputation and Imperfect Information, JET 27 (1982), Fig. 1). The entrant moves first, choosing to enter or stay out. Following entry, the monopolist chooses to acquiesce or to fight. The payoffs, with a > 1 and 0 < b < 1:

Outcome	Entrant	Monopolist
Entrant stays out	0	a
Enter, monopolist acquiesces	b	0
Enter, monopolist fights	b − 1	−1

Fix a = 4 and b = 1, and shift the “acquiesce” payoffs so the arithmetic is legible in integers: Out → (0, 4), Enter + Accommodate → (2, 2), Enter + Fight → (−1, −1). The strategic content is unchanged: entry is profitable if accommodated, fighting hurts the monopolist, and the monopolist would rather have the market to himself than share it.

flowchart LR
    E(("Entrant"))
    OUT["stay out<br/>(0, 4)"]
    I(("Incumbent"))
    F["FIGHT<br/>(-1, -1)"]
    A["ACCOMMODATE<br/>(2, 2)"]

    E -->|stay out| OUT
    E -->|enter| I
    I -->|fight| F
    I -->|accommodate| A

    style E fill:#ffd9d9
    style I fill:#d9e2ff
    style A fill:#d9f2d9

What this diagram shows. The entry-deterrence game, one entrant and one incumbent. Pink is the entrant’s node, blue the incumbent’s; the green leaf is the unique subgame-perfect outcome. The insight to take away: the incumbent’s node roots a proper subgame all by itself, and inside that subgame the incumbent’s choice is between −1 and 2 with nothing else at stake. There is no belief, no uncertainty, and no strategic subtlety — accommodating is simply better. Any equilibrium that has the incumbent fighting is relying on the incumbent never having to act on it.

The strategic form is 2×2 (the entrant has two strategies, the incumbent two), so it is small enough to enumerate exhaustively. My solver does:

entrant=STAY OUT incumbent=FIGHT        payoff=( 0, 4)  Nash=yes  SPE=no
entrant=STAY OUT incumbent=ACCOMMODATE  payoff=( 0, 4)  Nash=no   SPE=no
entrant=ENTER    incumbent=FIGHT        payoff=(-1,-1)  Nash=no   SPE=no
entrant=ENTER    incumbent=ACCOMMODATE  payoff=( 2, 2)  Nash=yes  SPE=yes
  -> 2 pure Nash equilibria, 1 subgame perfect

Walk the two Nash equilibria.

(Enter, Accommodate) is Nash: the entrant gets 2 and would get 0 by staying out; the incumbent gets 2 and would get −1 by fighting. It is also subgame perfect, because in the one proper subgame — the incumbent’s node — accommodating is the Nash equilibrium of that one-player subgame.

(Stay out, Fight) is also Nash, and this is the equilibrium that matters. The entrant gets 0; if she deviated to entering she would face the incumbent’s announced Fight and get −1, so staying out is a best response. The incumbent gets 4; his strategy specifies Fight, but since the entrant stays out his node is never reached, so his payoff does not depend on what his strategy says there. Every strategy is a best response when your information set is unreached. Kreps and Wilson state the mechanism in one line: “it costs the monopolist nothing to adopt the strategy ‘fight if entry’ if no entry occurs.”

That is the whole trick, and it is why Nash equilibrium alone is not enough for sequential games. The threat is free precisely because it works. Subgame perfection breaks the circle by testing the threat in the subgame where it would have to be executed: restricted to the incumbent’s node, the profile prescribes Fight, which yields −1 against 2 for Accommodate, so it is not a Nash equilibrium of that subgame, and the profile fails clause (2).

Second Nash equilibrium … “depends on an expectation by the entrant of the monopolist’s behavior that, faced with the fait accompli of entry, would be irrational behavior for the monopolist. In the parlance of game theory, the second equilibrium is imperfect.” — Kreps & Wilson, JET 27 (1982), §2

The generalisation to a chain of markets is Selten’s chain-store paradox, and it is Backward Induction applied to the whole sequence: with N entrants in sequence and everything observed, “in the last stage the monopolist will not fight because there are no later entrants to demonstrate for. … This logic can be repeated, unraveling from the back: In each stage entry and acquiescence will occur. To be precise, this is the unique perfect Nash equilibrium of the game.” The paradox is that this is not what firms are observed to do — which is the same empirical failure the centipede exhibits, and it was resolved the same way, by adding a small amount of incomplete information about the incumbent’s payoffs.

SPE Is Backward Induction Generalised

The relationship between the two concepts is often stated loosely (“SPE is backward induction”). The precise statement has two halves, and the second half is where SPE earns its own name.

Half one: in a finite game of perfect information, they coincide. Every node is a singleton information set, so every non-root node starts a proper subgame, so “Nash in every subgame” is “optimal at every node,” which is the marking procedure. The SEP puts it directly: applying Zermelo’s algorithm to an extensive form “is generating the game’s subgame perfect equilibrium (SPE). It gives an outcome that yields a NE not just in the whole game but in every subgame as well.” Levin’s Proposition 7 is the existence result: “Any finite game of perfect information has a pure strategy subgame perfect equilibrium. For generic payoffs, there is a unique SPE.”

Half two: SPE keeps working when a subgame is not a one-player decision. A subgame need not be a single node. It can be an entire simultaneous-move game, or a repeated game, or anything else — the only requirement is that it be self-contained. Bonanno’s Definition 3.6 gives the algorithm (Bonanno, Definition 3.6):

The subgame-perfect equilibrium algorithm.

1. Start with a minimal proper subgame and select a Nash equilibrium of it.
2. Delete the selected proper subgame and replace it with the payoff vector associated with the selected Nash equilibrium, making a note of the strategies that constitute the Nash equilibrium. This yields a smaller extensive-form game.
3. Repeat steps 1 and 2 in the smaller game so obtained.

Compare that to backward induction’s step: select the successor the mover most prefers. It is the same fold, with “pick the mover’s best successor” replaced by “solve this subgame and fold in its value.” When every subgame happens to be a single decision node, “solve this subgame” degenerates to “pick the best successor” and you are back to backward induction. Bonanno is explicit that this “generalizes the backward-induction algorithm for games with perfect information (Definition 2.3, Chapter 2).”

flowchart TB
    G0["full extensive-form game"]
    M["find a MINIMAL proper subgame"]
    S["solve it - Nash equilibrium of that subgame<br/>may need MIXED strategies"]
    R["replace the subgame with<br/>its equilibrium payoff vector"]
    G1["smaller game"]
    D{"any proper<br/>subgames left?"}
    OUT["the recorded choices form an SPE"]

    G0 --> M --> S --> R --> G1 --> D
    D -->|yes| M
    D -->|no| OUT

    BI["Backward induction is this loop<br/>when every minimal subgame<br/>is a single decision node:<br/>solving it means picking the<br/>mover's best successor"]
    S -.-> BI

    style S fill:#ffe9cc
    style OUT fill:#d9f2d9

What this diagram shows. The fold that defines subgame perfection, with the point at which it strictly extends backward induction highlighted. The insight to take away: the only difference is the box labelled “solve it.” Backward induction can always solve its box by inspection because the box holds one player’s choice. The SPE algorithm’s box may hold a genuine simultaneous game with no pure equilibrium at all — and then solving it requires mixed strategies, and the folded-in value is an expectation, not a payoff at any leaf.

Here is a concrete instance. Suppose entry leads to a post-entry stage in which both firms choose simultaneously whether to fight a price war, with payoffs (entrant first):

	Incumbent: price war	Incumbent: peace
Entrant: fight	(2, −2)	(−3, 3)
Entrant: yield	(−1, 1)	(1, −1)

This subgame is strictly competitive and has no pure Nash equilibrium — it is a scaled Matching Pennies. Backward induction has nothing to say, because there is no “best successor” to pick. The SPE algorithm proceeds anyway: solve the subgame in mixed strategies by the indifference conditions, fold in the value.

Making the incumbent indifferent requires the entrant to fight with probability p such that −2p + 1(1−p) = 3p + (−1)(1−p), giving 1 − 3p = 4p − 1, so p = 2/7. Making the entrant indifferent requires the incumbent to wage a price war with probability q such that 2q − 3(1−q) = −1q + 1(1−q), giving 5q − 3 = 1 − 2q, so q = 4/7. Computed in exact rational arithmetic with Python’s fractions.Fraction — no floating point anywhere, so a mismatch would be a bug and not rounding:

entrant mixes Fight with probability p = 2/7
incumbent mixes Price war with probability q = 4/7
entrant's exact subgame value = -1/7  (= -0.14285714285714285)
indifference check (exact): incumbent 1/7 == 1/7 -> True
indifference check (exact): entrant   -1/7 == -1/7 -> True

The value −1/7 is what gets folded back into the entry decision: the entrant enters iff −1/7 beats her stay-out payoff. That number is not the payoff at any terminal node of the game — it exists only as the value of a mixed equilibrium — which is exactly why the SPE algorithm is a strict generalisation of backward induction and not a restatement of it. (This is also the reason the Games and Strategic Systems in C MOC insists on exact rational arithmetic for equilibrium cross-checks: 2/7 and 4/7 are not representable in binary floating point, so a float solver cannot tell you whether the indifference condition holds exactly or nearly.)

When There Are No Proper Subgames

Subgame perfection’s power comes entirely from the supply of proper subgames. When a game has none, clause (2) of the definition is vacuous, SPE collapses to Nash, and the refinement does nothing at all.

This is not a pathological corner. It is the normal situation in any game where a player must act without observing what just happened — which is to say, most interesting games. Selten noticed it himself, and Kreps and Wilson open their sequential-equilibrium paper with his example: “Selten has gone on to observe that the intuitive motivation for the subgame perfection criterion can be applied to games that lack proper subgames. … One Nash equilibrium for this game has player 1 choosing D, player 2 choosing a, and player 3 choosing 1. This equilibrium is subgame perfect, as the only proper subgame here is the game itself. But, as Selten argues, this equilibrium is not sensible.”

Rather than reproduce Selten’s three-player figure from a scanned OCR I cannot fully trust, here is a two-player entry game with the same structure, built and checked here. The entrant has three actions: stay out, or enter in one of two ways. The incumbent observes that entry occurred but not which kind, so his two nodes lie in a single information set.

Entrant action	Incumbent: Fight	Incumbent: Accommodate
Stay out	(2, 5)	(2, 5)
Enter type 1	(0, 0)	(3, 2)
Enter type 2	(−1, 0)	(1, 2)

flowchart LR
    E(("Entrant"))
    OUT["stay out<br/>(2, 5)"]
    N1(("node after<br/>Enter type 1"))
    N2(("node after<br/>Enter type 2"))
    A1["(0,0) fight"]
    B1["(3,2) accommodate"]
    A2["(-1,0) fight"]
    B2["(1,2) accommodate"]

    E -->|stay out| OUT
    E -->|enter 1| N1
    E -->|enter 2| N2
    N1 -->|fight| A1
    N1 -->|accommodate| B1
    N2 -->|fight| A2
    N2 -->|accommodate| B2

    N1 -. one information set for the incumbent .- N2

    style E fill:#ffd9d9
    style N1 fill:#d9e2ff
    style N2 fill:#d9e2ff

What this diagram shows. An entry game in which the incumbent cannot tell which kind of entry occurred. The dotted link marks the information set. The insight to take away: because neither of the incumbent’s nodes is a singleton, neither starts a proper subgame, and the whole game is the only subgame there is. Subgame perfection therefore has exactly the same content as Nash equilibrium in this game — it cannot rule anything out.

Enumerating all six profiles:

  entr   incumbent    payoff   Nash   SPE    sequentially rational?
  Out    Fight        ( 2, 5)  yes    yes    NO - Fight is never optimal
  Out    Accommodate  ( 2, 5)  no     no     yes
  In1    Fight        ( 0, 0)  no     no     NO - Fight is never optimal
  In1    Accommodate  ( 3, 2)  yes    yes    yes
  In2    Fight        (-1, 0)  no     no     NO - Fight is never optimal
  In2    Accommodate  ( 1, 2)  no     no     yes

(Stay out, Fight) survives subgame perfection. It should not. Accommodating pays the incumbent 2 and fighting pays 0 whichever node he is at, so Fight is not optimal under any belief about which node he is at — not merely under the correct belief, but under every belief whatsoever. Subgame perfection cannot see this, because the test it applies is “is this a Nash equilibrium of some subgame,” and there is no subgame to apply it to.

The fix is to stop testing subgames and start testing information sets, which requires attaching beliefs to them. Kreps and Wilson’s construction:

To formalize this, as part of the description of an equilibrium we specify for each information set h the assessment made by player t(h) over the nodes in h if h is reached. A system of beliefs is defined as a function μ: X → [0,1] such that Σ_{x∈h} μ(x) = 1 for each h ∈ H. … An assessment is a pair (μ, π) consisting of a system of beliefs μ and a strategy π.

An assessment is sequentially rational if, taking the beliefs as fixed, “no player prefers at any point to change his part of the strategy π.” A sequential equilibrium is a sequentially rational assessment that additionally satisfies a consistency requirement — beliefs must obey Bayes’ rule where it applies, and off the equilibrium path must be limits of beliefs generated by strictly positive strategies. The authors are careful about what changes: “The point to be stressed here is that an assessment (and not simply a strategy) will or will not be a sequential equilibrium. We require that an equilibrium specify beliefs as well as strategies.”

Their own summary of the relationship to Selten: “Our definition of a sequential equilibrium recasts and slightly weakens Selten’s [1975 trembling-hand perfection]. … It implicitly generates beliefs at information sets off the equilibrium path, and then requires that strategies be optimal given these beliefs. In addition, it eliminates from consideration strategies that are otherwise weakly dominated. In a sequential equilibrium, the former is explicitly done.” And the payoff for making beliefs explicit: “explicit construction of beliefs off the equilibrium path enables discussion of which beliefs are ‘plausible’ and which are not. Such discussion is difficult in the context of Selten’s mechanical and indirect procedure for generating beliefs.”

flowchart TB
    N["Nash equilibrium<br/>no profitable deviation from the root"]
    S["Subgame perfect equilibrium<br/>Nash in every PROPER SUBGAME"]
    Q["Sequential equilibrium<br/>optimal at every INFORMATION SET<br/>given consistent beliefs"]
    T["Trembling-hand perfect<br/>robust to vanishing execution errors"]

    N --> S --> Q --> T

    G1["gains: rules out incredible threats"]
    G2["gains: bites when there are<br/>NO proper subgames"]
    G3["gains: also eliminates<br/>weakly dominated strategies"]

    S -.- G1
    Q -.- G2
    T -.- G3

    style S fill:#d9e2ff
    style Q fill:#ffe9cc

What this diagram shows. The refinement ladder, each rung ruling out strictly more profiles than the one below. The insight to take away: each rung exists because of a specific defect in the rung below, demonstrable on a specific small game. SPE exists because Nash certifies incredible threats; sequential equilibrium exists because SPE is silent when there are no proper subgames; trembling-hand perfection exists because even sequential rationality tolerates some weakly dominated play. Kreps and Wilson note that the two top rungs are close but not identical, and that Selten’s version arrives at the same intuition “by a mechanical and indirect procedure.” This ladder is the direct setup for the imperfect-information rung of the Games and Strategic Systems in C MOC, where Counterfactual Regret Minimization operates on information sets rather than nodes for exactly this reason.

The One-Shot Deviation Principle

Verifying that a profile is subgame perfect straight from the definition means, for every subgame, checking that no player gains from any alternative complete strategy in that subgame. The alternative strategy space is exponential in the number of decision nodes, so this is hopeless for anything but toy games — and completely hopeless for infinite-horizon games, where a strategy is an infinite object.

The one-shot deviation principle (also one-stage or one-deviation property) says you never need to consider more than one changed action at a time. Weibull’s statement (Weibull, SF2972 lecture notes, Proposition 4.1):

Definition. A one-shot deviation from a strategy σ is a strategy σ' ≠ σ that agrees with σ at all histories but one. Such a deviation is profitable if it raises the deviator’s continuation payoff at that history.

Proposition (One-shot deviation principle). A strategy profile σ is an SPE of Γ if and only if there is no profitable one-shot deviation.

The delimitation matters and is easy to miss: “Nash equilibria have no profitable one-shot deviations on their paths, but may have profitable one-shot deviations off their paths. But not so for subgame perfect equilibria.” The principle is a characterisation of subgame perfection specifically, and it is false for Nash equilibrium.

The proof has an easy direction and a hard one. SPE ⇒ no profitable one-shot deviation is immediate, since a one-shot deviation is a particular deviation. The converse — not SPE ⇒ some profitable one-shot deviation — requires a limiting argument: you take a profitable multi-stage deviation, truncate it, and argue the truncation is still profitable. That step needs the game to be continuous at infinity, meaning distant-future payoffs matter arbitrarily little, which holds automatically for a discounted sum of bounded stage payoffs and for any finite game. Without it the principle can fail.

Weibull’s aside is the sharpest connection this note has to the algorithms literature: “In dynamic programming: this principle is called unimprovability.” A policy that cannot be improved by changing a single action is optimal — which is Bellman’s principle of optimality in equilibrium clothing, and is exactly the property that makes the memoised recurrences in Game Theory DP correct.

How much does it actually buy? A measurement

I implemented both tests over the same game trees and compared them on every pure strategy profile. Test (a) is the definition: for each decision node, is the restricted profile a Nash equilibrium of the subgame rooted there, checked by enumerating every alternative complete strategy? Test (b) is the principle: for each decision node, flip only that node’s action, hold everything else fixed, and see whether the mover’s continuation payoff rises.

/* (a) the definition: Nash in every subgame */
static int is_spe_by_subgames(const Game *g, uint32_t s0, uint32_t s1) {
    for (int x = 0; x < g->count; x++) {
        if (g->n[x].player < 0) continue;
        if (!is_nash_at(g, x, s0, s1)) return 0;   /* enumerates 2^n0 + 2^n1 */
    }
    return 1;
}
 
/* (b) the one-shot deviation principle: flip exactly one node's action */
static int is_spe_by_one_shot(const Game *g, uint32_t s0, uint32_t s1) {
    int base[NPLAYERS], alt[NPLAYERS];
    for (int x = 0; x < g->count; x++) {
        const Node *nd = &g->n[x];
        if (nd->player < 0) continue;
        play(g, x, s0, s1, base);                  /* continuation from x    */
        uint32_t f0 = s0, f1 = s1;
        if (nd->player == 0) f0 ^= (1u << nd->dindex);   /* one bit flipped  */
        else                 f1 ^= (1u << nd->dindex);
        play(g, x, f0, f1, alt);
        if (alt[nd->player] > base[nd->player]) return 0;
    }
    return 1;
}

The structural difference is one line: is_nash_at loops over 2^{ndec[0]} + 2^{ndec[1]} alternative strategies, while the one-shot version evaluates exactly one alternative per node. Measured on n-node centipede games, classifying every profile with both tests (gcc 16.1.1 -O2, Fedora, Linux 7.1.8, 32 logical cores; /proc/loadavg read 3.63 3.80 2.87 at the start of the run on 2026-08-28, so the machine was busy and these are upper bounds):

n	profiles classified	verdicts agree?	subgame checks	one-shot checks	t (definition)	t (one-shot)	speedup
2	4	yes	6	6	0.000002 s	0.000000 s	—
4	16	yes	30	30	0.000001 s	0.000001 s	—
6	64	yes	126	126	0.000005 s	0.000001 s	5×
8	256	yes	510	510	0.000023 s	0.000003 s	8×
10	1,024	yes	2,046	2,046	0.000143 s	0.000010 s	14×
12	4,096	yes	8,190	8,190	0.001001 s	0.000037 s	27×
14	16,384	yes	32,766	32,766	0.007829 s	0.000139 s	56×
16	65,536	yes	131,070	131,070	0.059188 s	0.000561 s	106×

Two things to read off. The verdicts agree on every one of the 87,376 profiles tested across all eight tree sizes — an empirical confirmation of the principle on finite perfect-information games, which is the case where it holds unconditionally. And the node-visit counts are identical between the two tests (both columns read 131,070 at n = 16), because both loops early-exit at the same node; the entire speedup comes from the cost per node, which is O(2^n) for the definition and O(depth) for the principle. The ratio doubles with each two extra nodes, which is what an exponential-versus-linear gap looks like.

Why it matters more than the benchmark suggests

Finite centipedes are small enough that either test finishes. The principle’s real payoff is in repeated games, where the strategy space is not merely large but astronomically so. For a k-round Prisoner’s Dilemma with perfect monitoring, a player’s strategy must specify an action after every history, and there are (4^k − 1)/3 such histories:

rounds k	decision points per player	log₁₀(pure strategies per player)	log₁₀(profiles)
1	1	0.3	0.6
2	5	1.5	3.0
3	21	6.3	12.6
4	85	25.6	51.2
5	341	102.7	205.3
10	349,525	105,217.5	210,435.0

At k = 5 there are about 10^205 strategy profiles — more than the number of atoms in the observable universe squared, several times over. Checking Nash by enumeration is not slow, it is impossible. The one-shot deviation principle reduces the check to 341 comparisons, one per decision point, and for an infinite-horizon discounted game with a stationary strategy it reduces to a handful of algebraic inequalities — which is exactly how the standard results in Trigger Strategies and Punishment and The Folk Theorem are proved. Debraj Ray’s LSE handout and Weibull’s notes both use it to verify grim trigger, tit-for-tat and always-defect in a couple of lines each (Ray, MA300.2 Lecture 2).

Failure Modes and Gotchas

Assuming every node starts a subgame. It does not — only nodes in singleton information sets whose descendant set cuts no information set. The moment a game has a simultaneous move or an unobserved action, most nodes stop starting subgames, and in the worst case none do. Symptom: your SPE checker reports that a profile is subgame perfect but the profile prescribes an obviously dominated action somewhere. Diagnosis: count the proper subgames; if the answer is zero, you have learned nothing that Nash did not already tell you. Fix: move up to sequential rationality with explicit beliefs.

Confusing “subgame perfect” with “sensible”. They are not the same, and the entry game with an information set above is the counterexample: (Stay out, Fight) is subgame perfect and yet Fight is optimal under no belief at all. Subgame perfection is a specific test with a specific blind spot, not a general-purpose plausibility filter.

Selecting equilibria arbitrarily inside a subgame. Bonanno’s algorithm says “select a Nash equilibrium of it” — singular article, but the subgame may have several. Different selections fold different payoff vectors upward and can produce genuinely different equilibria of the whole game. This is not a defect in the algorithm; it is the multiplicity of Nash equilibrium propagating. Symptom: two correct implementations disagree. Fix: enumerate the subgame’s equilibria and carry all branches, or state the selection rule explicitly.

Forgetting that a strategy specifies behaviour at unreachable nodes, including your own. In the centipede, player 1’s strategy assigns TAKE or PASS at both of her nodes even though taking at the first makes the second unreachable. If your representation omits those choices you will count strategies wrongly — my n = 16 enumeration has 2^16 = 65,536 profiles precisely because each player commits at all eight of her own nodes — and you will get the Nash-versus-SPE distinction backwards, since the whole distinction lives in the unreachable part.

Applying the one-shot deviation principle outside its hypotheses. It characterises subgame perfection, not Nash equilibrium, and for infinite-horizon games it needs continuity at infinity. Undiscounted infinite-horizon games with limit-of-means payoffs are the standard place it fails. Symptom: a profile passes the one-shot check but a patient multi-stage deviation is profitable. Fix: check that stage payoffs are bounded and discounted, or fall back on the definition.

Reading SPE as a behavioural prediction in long games. Everything in Backward Induction about the centipede applies here verbatim, because the unique SPE of the centipede is the backward-induction profile. In McKelvey and Palfrey’s six-move laboratory games the SPE prediction — take at node 1 — occurred in 0.7% of 281 plays. SPE is a good normative filter on plans and a poor descriptive model of people, and it degrades fastest exactly where its logic requires the most iterations.

Alternatives and When to Choose Them

Concept	When to reach for it	What it rules out that the previous one does not	Cost
Nash equilibrium	Simultaneous, one-shot games	—	Blind off the path; certifies incredible threats
Subgame perfect equilibrium	Sequential games with genuine proper subgames	Threats the threatener would not execute	Vacuous when there are no proper subgames
Backward Induction	Finite, perfect information	Nothing extra — it is SPE here, computed efficiently	Does not apply if any subgame has simultaneous moves
Sequential equilibrium (Kreps & Wilson 1982)	Any game with non-singleton information sets	Actions optimal under no belief at all	An equilibrium is now an assessment; consistency is fiddly to verify
Trembling-hand perfection (Selten 1975)	When weak dominance is the worry	Some weakly dominated strategies sequential equilibrium tolerates	Defined via a limit of perturbed games; harder to compute
Perfect Bayesian equilibrium	Applied work in signalling and industrial organisation	Broadly the same territory as sequential, with weaker consistency demands	Several inequivalent definitions in circulation
Correlated Equilibrium	Many players, computation matters	Nothing about credibility — a different axis entirely	Says nothing about sequential rationality

The selection rule in practice: count your proper subgames first. If every node is a singleton, use backward induction and stop — SPE is what you will get and the traversal is linear. If there are proper subgames but some contain simultaneous moves, use the SPE fold and be ready for mixed strategies inside a subgame. If there are no proper subgames worth the name, SPE is not a refinement of anything and you need beliefs; go to sequential equilibrium. And for verification of any of these on a game larger than a whiteboard, use the one-shot deviation principle rather than the definition — the 106× measured above understates it badly, since the definition simply cannot be run at all on a repeated game.

Production Notes

Subgame perfection is the working definition of “credible commitment” in applied economics. The Nobel committee’s assessment: “Selten’s subgame perfection has direct significance in discussions of credibility in economic policy, the analysis of oligopoly, the economics of information, etc. It is the most fundamental refinement of Nash equilibrium.” The provenance is worth recording precisely, because Selten’s original 1965 paper is in German and rarely read: subgame perfection was introduced in Spieltheoretische Behandlung eines Oligopolmodells mit Nachfrageträgheit, Zeitschrift für die gesamte Staatswissenschaft 121, 301–24 and 667–89, 1965; trembling-hand perfection followed in Reexamination of the Perfectness Concept for Equilibrium Points in Extensive Games, International Journal of Game Theory 4, 25–55, 1975. The 1994 prize was shared with Nash and Harsanyi “for their pioneering analysis of equilibria in the theory of non-cooperative games,” with the committee summarising the division of labour as “Nash provided the foundations for the analysis, while Selten developed it with respect to dynamics, and Harsanyi with respect to incomplete information.”

Stackelberg leadership is a subgame-perfection result, not a modelling assumption. Levin derives quantity leadership by solving firm 2’s best-response function first and folding it into firm 1’s problem — literally the SPE algorithm on a continuum of actions. The first-mover advantage that falls out is a consequence of requiring the follower’s response to be credible; if you solved the same model for Nash equilibrium you would find equilibria in which the follower “threatens” a punishing quantity and the leader is deterred. The same structure underlies Rubinstein’s unique-SPE bargaining result, which Levin describes as “a fairly reasonable dynamic specification of bargaining that yielded a unique subgame perfect equilibrium” against the Nash demand game’s multiplicity.

Where the refinement’s prediction has been tested against firms, it has failed in a specific and instructive direction. Selten’s chain-store paradox is the case: subgame perfection says never fight entry, and firms fight entry. The resolution that stuck was not to abandon subgame perfection but to change the information structure — Kreps and Wilson add “a ‘small’ amount of imperfect (or incomplete) information about players’ payoffs, and we find that this addition is sufficient to give rise to the ‘reputation effect’ that one intuitively expects.” If you are building a model whose subgame-perfect prediction is that reputation cannot exist, the model is almost certainly missing type uncertainty, not missing a solution concept.

Instrumentation advice for anyone implementing this. Report three numbers, not one: the count of proper subgames, the count of pure Nash equilibria, and the count of subgame-perfect ones. The first tells you whether the refinement can possibly bite; the ratio of the second to the third tells you how much it bit. In my entry game those numbers are 1, 2, 1; in the n = 16 centipede they are 16, 16384, 1; in the information-set entry game they are 0, 2, 2 — and that last row, where SPE equals Nash exactly because there are no proper subgames, is the diagnostic you want to see before you trust an SPE result.

Uncertain

Verify: Selten’s own 1975 statement of trembling-hand perfection and his own 1965 statement of subgame perfection. Reason: both primary sources were unobtainable here. link.springer.com/content/pdf/10.1007/BF01766400.pdf returns HTTP 200 with a 3,038-byte HTML shell rather than the PDF; the 1965 paper is in German in Zeitschrift für die gesamte Staatswissenschaft and was not found online in any form. Every claim attributed to Selten in this note is therefore sourced from (i) the Nobel committee’s 1994 press release, (ii) Kreps and Wilson’s direct discussion of Selten’s Figures 2 and 3, or (iii) the Stanford Encyclopedia — all read in full here — and not from Selten’s text. To resolve: obtain IJGT 4:25–55 or the reprint in Kuhn (ed.), Classics in Game Theory, Princeton University Press 1997, pp. 317–354.

Uncertain

Verify: the exact payoffs in Kreps and Wilson’s Figure 3 — RESOLVED 2026-08-29. The original flag was raised because dklevine.com/archive/refs4237.pdf has a text layer good enough for the prose while the figure’s payoff columns OCR as an ambiguous block, so this note built and verified its own two-player example with the same structure rather than reproduce unreadable numbers. That substitute example is still the one used above and is still correct.

The payoffs are now known. Sequential Equilibrium recovered them from Gambit’s own test corpus — catalog/journals/ijgt/selten1975/fig1.efg, the machine-readable encoding of Selten’s horse — and cross-checked them against four independent quantitative claims in the legible Kreps–Wilson running text. It went further and derived the quoted “player 3 chooses r with probability at least 3/4”, which Kreps and Wilson assert without explanation: scanning the belief × mixing space shows player 3’s belief on the d-node must be ≥ 2/3, and 3/4 is live only at exactly 2/3, where player 3 is indifferent.

The transferable lesson: when a figure will not OCR, look for the game in a solver’s test data. Gambit ships .efg encodings of the canonical examples from the literature, and a machine-readable file cannot OCR ambiguously.

See Also

• Backward Induction — the sibling note: the same fold restricted to perfect information, plus the epistemic critique (common knowledge of rationality at unreached nodes) and the centipede evidence that the prediction fails empirically
• Game Theory DP — the algorithmic treatment of the same traversal for zero-sum games: minimax recurrence, memoisation, complexity. Note that the one-shot deviation principle is unimprovability from dynamic programming under another name
• Nash Equilibrium — the concept this refines; the entry game above is the minimal example where Nash is not enough
• Extensive-Form Games — trees, information sets, and why a strategy is a complete contingent plan
• Imperfect Information and Information Sets — what happens when the subgame supply runs out, and the modelling device that makes poker different from chess
• Counterfactual Regret Minimization — the algorithm that works on information sets rather than subgames, which is why it handles the games SPE cannot
• Alpha-Beta Pruning — the efficiency story for the perfect-information special case
• Zermelo’s Theorem and Solved Games — existence of a pure-strategy SPE in finite perfect-information games
• Iterated Games and the Shadow of the Future — where the one-shot deviation principle does its real work
• The Folk Theorem — the set of payoffs supportable in subgame-perfect equilibrium of a repeated game
• Trigger Strategies and Punishment — credibility of punishment is exactly a subgame-perfection question
• Games and Strategic Systems in C MOC — parent map; this is a P3 rung and the bridge to P6