Backward Induction

Backward induction solves a finite game of perfect information by starting at the leaves and working toward the root: at every decision node whose successors already carry payoff vectors, the player who moves there picks the successor she most prefers, and that successor’s payoff vector is copied onto the node. Repeat until the root is marked, and you have both the game’s predicted outcome and a complete plan of play. The procedure is mechanically trivial — it is one post-order tree traversal — and philosophically the most contested idea in non-cooperative game theory, because making it valid requires assuming that every player is rational at every node, including nodes that can only be reached if somebody has already played irrationally. That assumption is close to self-contradicting, and the games that expose it — Rosenthal’s centipede, Selten’s chain store, the finitely repeated Prisoner’s Dilemma — are not curiosities. In laboratory play the first mover in a centipede game takes at the first node in 7% of four-move games and 1% of six-move games (McKelvey & Palfrey 1992, Table IIB), which is to say backward induction predicts the observed behaviour essentially never. This note is the game-theoretic treatment: what the procedure assumes, where the assumption fails, and why “people are just irrational” is not the resolution.

Relationship to Game Theory DP

The vault already carries Game Theory DP (4,839 words), which covers the same tree traversal under an algorithms-and-interviews framing: the minimax recurrence, memoisation over (i, j) subarray states, Sprague–Grundy theory for impartial games, alpha-beta, and the LeetCode problem families that reduce to it. That note owns the algorithmic and complexity treatment; read it for the recurrence, the state-space design, and the pruning. This note owns the solution concept: what the traversal is a model of, what it presupposes about the agents, which of those presuppositions are false, and what happens to the prediction when they are. The concrete difference is that Game Theory DP assumes two-player zero-sum payoffs and therefore alternates max and min on a single scalar; backward induction as a solution concept carries a payoff vector per node and every mover maximises her own component, which is why it applies to the centipede (where both players prefer passing to the backward-induction outcome) and minimax does not. Same traversal, different object, different failure modes. Cross-link, do not merge.

Mental Model

Think of a finite perfect-information game as a rooted tree in which each interior node is owned by the player whose turn it is, each edge is an action, and each leaf carries one number per player. Backward induction is a marking procedure. Initially only the leaves are marked. Then, repeatedly: find any unmarked node all of whose immediate successors are marked; let i be its owner; select the successor whose payoff vector gives i the highest number in i’s own coordinate; copy that entire vector onto the node and record the edge. Because the game is finite the procedure always terminates with the root marked (Bonanno, Game Theory, Definition 2.3).

Two details in that description do the real work and are the usual source of confusion.

First, the whole vector is copied, not just the mover’s own number. Node x is marked with what happens if play reaches x — a complete description of the outcome, for everybody. The mover selects on her own coordinate but the other coordinates ride along, because they are what the previous player will select on one level up. This is exactly the generalisation that makes backward induction more than minimax: in a zero-sum game the second coordinate is −1 times the first and can be dropped, and the alternating max/min of Game Theory DP falls out. In a general-sum game it cannot be dropped, and there is no min anywhere — every node is a max on a different coordinate.

Second, the selection is over immediate successors only. The mover does not search the whole subtree; she reads two or three already-computed vectors and compares one number in each. That is what makes the procedure linear in the size of the tree. The search is hidden in the fact that the successors were marked first.

flowchart TB
    subgraph pass3["Pass 3 - root marked"]
        R["node 1 owner P1<br/>marked (4,1) choose TAKE"]
    end
    subgraph pass2["Pass 2 - penultimate marked"]
        B["node 2 owner P2<br/>marked (2,8) choose TAKE"]
    end
    subgraph pass1["Pass 1 - leaves already marked"]
        L1["TAKE at 1<br/>(4,1)"]
        L2["TAKE at 2<br/>(2,8)"]
        L3["PASS at 2<br/>(16,4)"]
    end

    R -->|TAKE| L1
    R -->|PASS| B
    B -->|TAKE| L2
    B -->|PASS| L3

    style R fill:#ffd9d9
    style B fill:#d9e2ff

What this diagram shows. A two-node centipede in which the pot starts at (4, 1) and both piles double on every PASS. Leaves are marked first. Pass 2 marks P2’s node: P2 compares her own coordinate, 8 from TAKE against 4 from PASS, and chooses TAKE, so the node inherits the whole vector (2, 8). Pass 3 marks P1’s node: P1 compares 4 from TAKE against 2 from the marked successor, and chooses TAKE. The insight to take away: P1 does not compare 4 with 16 — the 16 she would get if both players passed is unreachable, because the marking has already established that P2 would not pass. Every objection to backward induction is an objection to that word “established”.

What Zermelo Actually Proved

Almost every textbook attributes backward induction to Ernst Zermelo’s 1913 paper on chess, Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. Schwalbe and Walker went back to the German original and found that most of the modern statements of “Zermelo’s theorem” are wrong, including the attribution of the method (Schwalbe & Walker, Zermelo and the Early History of Game Theory, verified readable on build). Their finding, stated flatly: “Note that in Zermelo’s paper, contrary to what is often claimed, no use is made of backward induction. The first time a proof by backward induction is used seems to be in von Neumann and Morgenstern (1953). The first mention of Zermelo in connection with induction was in Kuhn (1953).”

What Zermelo did do is worth knowing, because it clarifies what the theorem is actually about.

He studied two-person games with no chance moves and strictly opposing interests, with finitely many positions but no stopping rule — so he explicitly allowed infinite plays. Modern statements assume a finite game; the restriction to finite games “dates back to von Neumann and Morgenstern (1953).”
His first question was whether “White is in a winning position” can be given an objective mathematical meaning. His answer is set-theoretic: the position is winning iff a certain set of move sequences (those by which White wins regardless of Black) is nonempty. If that set is empty but a second set — sequences by which White postpones loss indefinitely — is nonempty, the best White can force is a draw. If both are empty, Black can force a win.
He did not prove the popular trichotomy as his main result, and he certainly did not prove that the first mover has an advantage. Schwalbe and Walker single out Dimand & Dimand’s “first mover cannot lose” version as flatly contradicted: “The possibility of both sets being empty means that White can not guarantee that he will not lose.”
His actual focus was a quantitative question: given that White can force a win, how long does it take? He claimed the answer is bounded by the number of positions, and gave a proof by contradiction using non-repetition of positions.
That proof was wrong, or at least incomplete. Dénes König (1927) pointed out that Zermelo showed the shortening argument for a single line of play while implicitly assuming “that Black would never change his behaviour at any reoccurrence of a winning position,” and that what was needed was the claim for all of Black’s possible replies. König proved the boundedness result properly using what is now König’s lemma — the application to games was suggested to him by von Neumann. Zermelo then supplied a correct proof by a counting argument over the sets m_r of positions from which White forces a win in exactly r moves; it appears in the appendix to König’s paper and uses no non-repetition argument at all.

timeline
    title Provenance of the backward-induction folklore
    1913 : Zermelo - set-theoretic definition of a winning position; infinite plays allowed; no backward induction; boundedness proof incomplete
    1927 : Koenig - proves boundedness via Koenig's lemma at von Neumann's suggestion; Zermelo supplies a correct counting proof in the appendix
    1928 : Kalmar - generalises to infinitely many positions and infinite branching; recovers Zermelo's without-repetition claim
    1944 : von Neumann and Morgenstern - the first actual proof by backward induction
    1953 : Kuhn - first to associate Zermelo's name with induction; extensive form and information sets formalised
    1965 : Selten - subgame perfection, generalising backward induction beyond perfect information

What this diagram shows. The gap between what Zermelo proved and what “Zermelo’s theorem” now means, with the intermediate results that filled it. The insight to take away: the theorem you can safely cite as Zermelo’s is determinacy — a finite two-person game of perfect information with no chance moves has a value under optimal play — while the algorithm is von Neumann and Morgenstern’s, and the name is Kuhn’s mistake. If you need a citable modern statement, Levin’s is clean: “Any finite game of perfect information has a pure strategy subgame perfect equilibrium. For generic payoffs, there is a unique SPE” (Levin, Extensive Form Games, Proposition 7).

Resolved 2026-08-29 — the translation is available at that URL

An earlier revision of this note flagged the Zermelo attribution as uncertain on the grounds that the copy at people.math.harvard.edu/~elkies/FS23j.03/zermelo.pdf was “six pages and does not include the translation appendix”. Re-fetched 2026-08-29: that URL serves a 15-page PDF whose final four pages are Schwalbe and Walker’s complete English translation of Zermelo’s 1913 paper, headed “Ernst Zermelo: On an Application of Set Theory to the Theory of the Game of Chess” and footnoted “Translation by Ulrich Schwalbe and Paul Walker. In our translation we tried to stay as close as possible to the German original.” The translation was read in full and every Zermelo claim in this section now rests on it directly rather than on Schwalbe and Walker’s paraphrase: the set-theoretic definitions of U(q) and V(q), the explicit admission of infinite plays (“could also — at least theoretically — go on forever”), the non-repetition argument for the ≤ t bound, and Zermelo’s closing sentence “The question as to whether the starting position p₀ is already a ‘winning position’ for one of the parties is still open.”

Residual gap, much narrower than the original flag: the German original was still not located, so “the translation is faithful” remains Schwalbe and Walker’s word. To resolve fully: obtain Zermelo, Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels, Proc. Fifth Congress of Mathematicians (Cambridge 1912), CUP 1913, 501–504.

The Algorithm, Step by Step

Take the four-move centipede game exactly as run in the laboratory by McKelvey and Palfrey. Their design: “we start with a total pot of $.50 d i v i d e d in t o a l a r g e p i l eo f$ .40 and a small pile of $.10. E a c h t im e a pl a y er c h ooses t o p a ss, b o t h p i l es a r e m u l t i pl i e d b y tw o ." A pl a y er w h oc h ooses T A K E e n d s t h e g am e an d k ee p s t h e l a r g e p i l e; t h eo pp o n e n t g e t s t h es ma l l o n e . T h er e a r e f o u r d ec i s i o nn o d es, a l t er na t in g, R e d (pl a y er 1) f i r s t . I f a l l f o u r pl a y er s p a ss, t h e f ina l s pl i t i s ‘ ($ 6.40, $1.60)` in favour of Red.

Multiply everything by ten to work in integers. The tree is:

Node	Mover	TAKE gives (P1, P2)	PASS goes to
1	P1	(4, 1)	node 2
2	P2	(2, 8)	node 3
3	P1	(16, 4)	node 4
4	P2	(8, 32)	terminal (64, 16)

Now mark, right to left.

Node 4 (P2 moves). TAKE gives P2 32; PASS gives P2 16. P2 takes. Node 4 is marked (8, 32).
Node 3 (P1 moves). TAKE gives P1 16; PASS leads to node 4, marked (8, 32), so PASS gives P1 8. P1 takes. Node 3 is marked (16, 4).
Node 2 (P2 moves). TAKE gives P2 8; PASS leads to node 3, marked (16, 4), so PASS gives P2 4. P2 takes. Node 2 is marked (2, 8).
Node 1 (P1 moves). TAKE gives P1 4; PASS leads to node 2, marked (2, 8), so PASS gives P1 2. P1 takes. Root marked (4, 1).

The predicted outcome is that Red takes $0.40 imm e d ia t e l y an d B l u e g e t s$ 0.10, out of a pot that would have grown to $8.00 if everyone passed. And the reason is a single arithmetic fact that recurs at every node: passing once doubles your small pile, but taking now gets you the large pile, and the large pile is four times the small pile in this design. Passing is only worth it if the other player also passes, and the marking has already ruled that out one level down.

flowchart LR
    N1["node 1<br/>P1<br/>mark (4,1)"]
    N2["node 2<br/>P2<br/>mark (2,8)"]
    N3["node 3<br/>P1<br/>mark (16,4)"]
    N4["node 4<br/>P2<br/>mark (8,32)"]
    T1["(4,1)"]
    T2["(2,8)"]
    T3["(16,4)"]
    T4["(8,32)"]
    T5["(64,16)"]

    N1 -->|TAKE chosen| T1
    N1 -.->|PASS| N2
    N2 -->|TAKE chosen| T2
    N2 -.->|PASS| N3
    N3 -->|TAKE chosen| T3
    N3 -.->|PASS| N4
    N4 -->|TAKE chosen| T4
    N4 -.->|PASS| T5

    style N1 fill:#ffd9d9
    style N3 fill:#ffd9d9
    style N2 fill:#d9e2ff
    style N4 fill:#d9e2ff

What this diagram shows. McKelvey and Palfrey’s four-move centipede with the backward-induction marks written on each node. Pink nodes belong to player 1, blue to player 2; solid arrows are chosen actions, dashed arrows are rejected ones. The insight to take away: every single node is marked TAKE, and the marks were computed right-to-left, so the leftmost decision — the only one that is ever actually made — is justified by a chain of three counterfactual claims about nodes that the prediction says will never be visited. That is the whole controversy in one picture.

What Backward Induction Assumes

The traversal is a fact about the tree. Interpreting the traversal as a prediction about players requires an epistemic premise, and the premise is much stronger than “the players are rational.”

The Stanford Encyclopedia states the requirement plainly for the standard three-node example: “Player I plays L at node 8 because she knows that Player II is economically rational, and so would, at node 9, play L because Player II knows that Player I is economically rational and so would, at node 10, play L” (SEP, Game Theory, §2.8). Each level of the backward pass consumes one more level of “I know that you know that I know…”. A game with k decision nodes needs roughly k levels of iterated knowledge of rationality. That alone would be a bounded-rationality complaint, not a paradox.

The paradox is sharper. Aumann’s terminology is the cleanest available. He distinguishes (Aumann 1998, On the Centipede Game, §1):

Substantive rationality — “it is assumed common knowledge that each player i would act rationally at each of his vertices v, even when i knows that v will not be reached.” This is a claim about counterfactual behaviour.
Material rationality — “that i act rationally at those of his vertices that are actually reached.” Much weaker; “the counterfactual component of this condition is much smaller.”

Aumann’s 1995 result is that in perfect-information games, common knowledge of substantive rationality implies the backward-induction outcome. But he immediately concedes the cost: “common knowledge of material rationality does not in general lead to the backward induction outcome.” The strong premise is exactly the one that does the work, and the strong premise is the counterfactual one.

Why is that a problem rather than merely an assumption? Because the counterfactual it asks you to entertain is inconsistent with its own antecedent. Bicchieri’s formulation, as reported by the SEP:

Player I must suppose that Player II, at node 9, would predict Player I’s economically rational play at node 10 despite having arrived at a node (9) that could only be reached if Player I is not economically rational! … Player II can solve the game only by using a backward induction argument that takes as a premise the failure of Player I to behave in accordance with economic rationality. This is the paradox of backward induction.

The epistemic-game-theory literature has sharpened this into an impossibility result. Adding just one more level of knowledge breaks the argument: if player b knows what a knows, then b knows that a’s only rational choice at the first node is to stop, so b knows his own node will not be reached; contrapositively, if b observes that his node has been reached, he must conclude that common knowledge of rationality does not hold (SEP, Epistemic Foundations of Game Theory, §3.2.3). And the general statement: “Reny (1992) strengthened this observation by arguing that common knowledge of rationality is consistent only in trivial games where every node is reached by the subgame perfect equilibrium.”

That is a remarkable thing for a solution concept to be. The premise that justifies the calculation is self-undermining precisely on the set of nodes the calculation reasons about.

flowchart TD
    CKR["Common knowledge of<br/>substantive rationality"]
    BI["Backward induction<br/>outcome predicted"]
    OFF["Play is observed<br/>off the predicted path"]
    CONTRA["The observer must infer<br/>that CKR is false"]
    NOJUST["The backward-induction<br/>reasoning at this node<br/>is no longer justified"]
    REVISE["What should the observer<br/>believe instead?"]

    CKR --> BI
    BI --> OFF
    OFF --> CONTRA
    CONTRA --> NOJUST
    NOJUST --> REVISE
    REVISE -->|"trembling hand:<br/>execution error, beliefs unchanged"| CKR
    REVISE -->|"incomplete information:<br/>opponent may be a different type"| ALT["Reputation equilibria<br/>cooperation off the BI path"]
    REVISE -->|"belief revision:<br/>opponent is not maximising"| ALT

    style CONTRA fill:#ffe0cc
    style ALT fill:#d9f2d9

What this diagram shows. The self-undermining loop at the heart of the backward-induction paradox, and the three standard escape routes. The insight to take away: the escapes are not refinements of the argument, they are replacements of the premise. Selten’s trembling hand keeps common knowledge of rationality and blames the hand (“a decision and its consequent act may ‘come apart’ with some nonzero probability”, per SEP §2.8). Kreps–Milgrom–Roberts–Wilson keep rationality and drop complete information about payoffs. Belief-revision accounts keep the observation and drop common knowledge. All three predict different behaviour off the path, and off the path is where the prediction lives.

The Centipede Game, Worked in Full

Rosenthal introduced the game in 1981; Aumann calls it “a touchstone of the theory of PI games. Almost every paper on the subject mentions it, and in many it is the chief object of analysis.” What makes it a touchstone rather than a curiosity is the magnitude of the disagreement between theory and observation. In a Prisoner’s Dilemma the theory predicts an outcome that is merely Pareto-dominated. In the centipede the theory predicts that the players will leave 94% of the money on the table, and then they do not.

The theoretical prediction

McKelvey and Palfrey state it exactly: “All standard game theoretic solutions (Nash equilibrium, iterated elimination of dominated strategies, maximin, rationalizability, etc.) would predict f_1 = 1 if i = 1, f_i = 0 otherwise. The requirement of rationality that subjects not adopt dominated strategies would predict that f_{n+1} = 0 and p_n = 1.” In words: every standard concept says the game ends at the first node, and even the weakest of them — do not play a strictly dominated strategy — says that the player with the last move must take.

The data

Their experiment ran seven sessions with 20 subjects each at Caltech and Pasadena Community College, with a rotating matching scheme designed so “that no player i ever plays against a player who has previously played someone who has played someone that i has already played” — and, they note, the same holds for any number of iterations of that phrase. That construction is doing serious work: it removes every supergame channel that could rationalise cooperation, so what is left is the one-shot prediction against one-shot play.

Proportion of games ending at each terminal node (Table IIA), pooled:

Version	n	f₁	f₂	f₃	f₄	f₅	f₆	f₇
Four move	281	.071	.356	.370	.153	.049	—	—
High payoff (4× stakes)	100	.150	.370	.320	.110	.050	—	—
Six move	281	.007	.064	.199	.384	.253	.078	.014

Implied probability of taking conditional on reaching each node (Table IIB), pooled:

Version	p₁	p₂	p₃	p₄	p₅	p₆
Four move	.07	.38	.65	.75	—	—
High payoff	.15	.44	.67	.69	—	—
Six move	.01	.06	.21	.53	.73	.85

Read the first column. In the six-move game the first mover took immediately once in every 143 plays. The authors’ own summary is blunt: “we can reject out of hand either of these hypotheses of rationality. … So the subjects clearly do not iteratively eliminate dominated strategies.”

Two further facts from the same table deserve emphasis because they are usually dropped from the retelling.

Even the last-move dominance test fails. “When a game reaches the last move, Table IIB shows that the player with the last move adopts the dominated strategy of choosing PASS roughly 25% of the time in the four move games, 15% in the six move games, and 31% in the high payoff games.” Passing at the last node is a pure gift with no strategic upside whatsoever — the game ends immediately after. A quarter of subjects gave the money away.
The theory is directionally right about the shape. “The most obvious and consistent pattern in the data is that in all of the sessions, the probability of TAKE increases as we get closer to the last move.” Backward induction gets the gradient right and the level catastrophically wrong. That is a strong hint that something like backward induction is operating in players’ heads, just truncated.

The stakes were not trivial: “Students earned from a low of $7.00 t o ahi g h o f$ 75.00, in sessions that averaged less than 1 hour — average earnings were $20.50.” Raising them fourfold moved p₁ from .07 to .15, which is in the predicted direction and nowhere near 1.00.

xychart-beta
    title "Six-move centipede: measured P(TAKE) by node vs the prediction"
    x-axis "decision node" [1, 2, 3, 4, 5, 6]
    y-axis "probability of taking, given the node is reached" 0 --> 1
    bar [0.01, 0.06, 0.21, 0.53, 0.73, 0.85]
    line [1, 1, 1, 1, 1, 1]

What this diagram shows. Bars are the measured probability of taking at each node conditional on the node being reached, pooled over 281 plays of the six-move game (McKelvey & Palfrey Table IIB). The flat line at 1.0 is what backward induction predicts at every node. The insight to take away: the observed curve is monotone increasing and approaches — but never reaches — the prediction near the end. Subjects behave as though they are doing backward induction over a short horizon anchored at the end of the game, not over the whole game. The four-move numbers in the table above have the same shape at a higher level (.07, .38, .65, .75), which is what you would expect if the anchored window is roughly constant in length regardless of how long the game is.

The paradox is not resolved by calling people irrational

Three lines of evidence make “subjects are irrational” untenable as an explanation.

First, passing is the profit-maximising choice given the observed distribution of opponents. Levitt, List and Sadoff computed this on their own data: “Given the high pass rates observed in the data, passing maximizes expected returns at every node except the last one (where passing guarantees a loss). For instance, in our data the average final payoff to player 1 when he elected to pass at the first node was $44.85, co m p a r e d t o a g u a r an t ee d$ 4 from stopping at the first node” (Levitt, List & Sadoff 2011). A subject who passes is not failing at optimisation; she is optimising against the empirical opponent instead of against the theoretical one. What fails is not the players’ rationality but the common knowledge premise that lets each player treat the theoretical opponent as the real one.

Second, subjects who demonstrably can backward-induct still pass. The same paper ran a “race to 100” game — alternately add a number from 1 to 9 (or 1 to 10) to a running total, first to reach exactly 100 wins, winner-take-all. This is constant-sum and winner-take-all, so “behavior in these games does not depend on social preferences or beliefs about the rationality of one’s opponent,” and it “requires the player to reason backward ten moves.” Result: “in the version of race to 100 in which players choose numbers between 1 and 9, nearly 60 percent of the chess players achieve the Nash solution. Yet, among those subjects who perfectly backward induct in race to 100, not a single one stopped at the first node in centipede. Indeed, the ‘best inductors’ in the race to 100 game had low stoppage rates in centipede at any node, passing nearly 84 percent of the time.” The capability is present and unused, which means the missing ingredient is a belief about the opponent, not a cognitive limitation.

Third — and this is the honest negative — the literature does not agree on the facts. Palacios-Huerta and Volij ran centipede games at international chess tournaments and reported the opposite: “69 percent of chess players stopped immediately, and when restricted to Grandmasters, this percentage escalated to 100 percent” (Palacios-Huerta & Volij 2009). Levitt, List and Sadoff replicated the design at two international open tournaments with 206 chess players (103 pairs: 26 Grandmasters, 20 International Masters, 61 Masters) and found the reverse: “in our sample, chess players end the game at the first node in only 3.9 percent of the games, compared to 69 percent for Palacios-Huerta and Volij (2009) in their artefactual field experiment. And, importantly, not a single one of the 16 Grandmasters in our experiment stop at the first node, whereas all 26 of the Grandmasters in Palacios-Huerta and Volij (2009) stopped at the first node.”

Uncertain

Verify: what actually distinguishes the two chess-player centipede experiments. Reason: two American Economic Review papers, using the same subject population type and nominally the same game, report 0% versus 100% first-node stopping among Grandmasters — the largest possible disagreement. Both PDFs were fetched and read directly here; neither is misquoted. Candidate explanations include differences in recruitment, in whether opponents’ chess status was disclosed, in stake size, and in whether the centipede was played before or after other games (Levitt et al. report a footnote effect: among pairs who played centipede before the race-to-100 games, 1.9% stopped at the first node). To resolve: read the published comment/reply exchange, if any, and compare instructions verbatim. Until then, do not cite either result as “the” finding about experts and backward induction.

The safe conclusion is narrower and still damning for the concept as a positive prediction: in every published centipede experiment, immediate stopping is a minority outcome, usually a small one, and the deviation persists under high stakes, under expert subjects, and under matching schemes engineered to eliminate repeated-game incentives.

The Paradox of Backward Induction

It is worth separating the several distinct objections that get bundled under this heading, because they have different remedies.

1. The counterfactual objection (Bicchieri, Binmore, Pettit & Sugden, Reny). Discussed above: the argument requires reasoning about a node whose being reached refutes the argument’s premise. Reny’s sharpening — that common knowledge of rationality is consistent only in games where the subgame-perfect path reaches every node — makes this an impossibility rather than a discomfort.

2. The depth-of-knowledge objection. Even granting coherence, the argument consumes one level of iterated knowledge per node. For a six-move centipede that is six levels; for the finitely repeated Prisoner’s Dilemma with 200 rounds it is 200. There is no empirical evidence that humans maintain iterated knowledge to any such depth, and the McKelvey–Palfrey gradient is exactly what you would expect from agents doing two or three levels anchored at the end.

3. The indifference objection. The marking procedure requires the mover to pick the best successor. When two successors tie, the procedure says “select one,” and the choice is arbitrary — but it is not innocuous, because the other players’ payoffs at the two tied successors may differ wildly and will propagate up the tree. Megiddo puts it precisely: “Indifference of a player with respect to two distinct outcomes of a game cannot be handled by small perturbations, because the actual choice may have significant impact on other players, and cause them to act in a way that has significant impact of the indifferent player” (Megiddo, arXiv:2307.04029). This is why the uniqueness half of the modern Zermelo statement is always hedged with “for generic payoffs” — Bonanno’s worked example has three backward-induction solutions purely from one tie.

4. The off-path-beliefs objection. Backward induction assigns a definite continuation to every node but says nothing about what a player should believe on reaching an off-path node. In perfect-information games you can get away with this because every node is a singleton and the continuation is determined by the marks. In games with information sets you cannot, and this is precisely the gap that Subgame Perfect Equilibrium narrows and sequential equilibrium closes.

The standard textbook remedy for (1) is Selten’s trembling hand: “if there is even a remote possibility that a player may make a mistake — that her ‘hand may tremble’ — then no contradiction is introduced by a player’s using a backward induction argument that requires the hypothetical assumption that another player has taken a path that an economically rational player could not choose.” Note what this buys and what it costs. It buys logical consistency: player II at node 9 can believe player I is rational and that node 9 was reached, because the reaching was a slip. It costs the interpretation: the model now says that off-path play conveys no information at all about the opponent, which is exactly the assumption the reputation literature shows to be wrong.

The Finitely Repeated Prisoner’s Dilemma Unravels the Same Way

The centipede is not a special construction. The SEP entry on the Prisoner’s Dilemma derives it as a limiting case: “Consider a PD in which the punishment payoff is zero. Now iterate the asynchronous version of this game a fixed number times. Imagine that both players are restricted to highly ‘punitive’ strategies according to which, they must always defect against a player who has ever defected. … The result is a centipede game” (SEP, Prisoner’s Dilemma, §12). The centipede is the finitely repeated Prisoner’s Dilemma with grim-trigger strategies, drawn as a tree.

The unravelling argument is the backward pass, one round at a time:

Suppose the players know the game will last exactly n rounds. Then, no matter what node have been reached, at round n−1 the players face an ordinary (“one-shot”) PD, and they will defect. At round n−2 the players know that, whatever they do now, they will both defect at the next round. Thus it is rational for them to defect now as well. By repeating this argument sufficiently many times, the rational players deduce that they should defect at every node on the tree. Indeed, since at every node defection is a best response to any move, there can be no other subgame-perfect equilibria.

Selten’s chain-store paradox is the same argument in an industrial-organisation costume, and Kreps and Wilson’s summary of it is the crispest statement of the unravelling I have found: “In the last stage the monopolist will not fight because there are no later entrants to demonstrate for. So in the last stage, entry will surely occur. But then in the penultimate stage, the monopolist again has no reason to fight — it is costly in the short run and has no effect on the last stage. The next-to-last entrant, realizing this, will surely enter. This logic can be repeated, unraveling from the back: In each stage entry and acquiescence will occur” (Kreps & Wilson, Reputation and Imperfect Information, JET 27 (1982) §2).

flowchart RL
    R5["round n<br/>known last<br/>DEFECT"]
    R4["round n-1<br/>next round already<br/>settled as D,D<br/>DEFECT"]
    R3["round n-2<br/>DEFECT"]
    R2["..."]
    R1["round 1<br/>DEFECT"]

    R5 --> R4 --> R3 --> R2 --> R1

    NOTE["The induction needs only one thing:<br/>a commonly known last round"]
    NOTE -.-> R5

    style R5 fill:#ffd9d9
    style R1 fill:#ffd9d9

What this diagram shows. The unravelling of cooperation in a finitely repeated Prisoner’s Dilemma, running right to left from the known final round. The insight to take away: the only structural input is the existence of a commonly known upper bound on the horizon. Nothing about the payoffs matters beyond the stage game having a strictly dominant defection.

That last point is the connection to Iterated Games and the Shadow of the Future, and it is sharper than “repeat the game and cooperation appears.” The SEP records an observation “apparently originating in Kavka 1983, and given more mathematical form in Carroll, that the backward induction argument applies as long as an upper bound to the length of the game is common knowledge.” The worked example: “since shopkeeper Jones cannot make more than one sale a second and since he will live less than a thousand years, he and customer Smith can calculate (conservatively) that they cannot possibly conduct more than 10¹² transactions.” The unravelling therefore threatens every real repeated interaction, because every real repeated interaction has a computable upper bound. What rescues cooperation in the indefinite-horizon model is not the absence of a last round but the absence of a commonly known one: “in an indefinite IPD as described above, there can be no upper bound on the length of the game. There is, instead, some fixed probability p that, at any time in which the game is still being played, it will continue to be played with probability p.” Discounting and continuation probability are mathematically interchangeable here, and either one is what Trigger Strategies and Punishment and The Folk Theorem rest on.

The escape route that survives contact with data is Kreps, Milgrom, Roberts and Wilson’s: keep the finite horizon, keep rationality, and add a small amount of incomplete information about payoffs. As the SEP summarises it, “a finitely repeated PD where one or both rational players believes (falsely) that there is some probability that the other has adopted Tit For Tat, will admit equilibria in which both players defect only at rounds close to the final.” Kreps and Wilson’s own abstract for the parallel chain-store result: “we reexamine Selten’s model, adding to it 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.”

The prediction that comes out — cooperate until near the end, then defect — matches the experimental record, and it was already visible in the older data McKelvey and Palfrey cite: “Selten and Stoecker (1986) … finds that experienced subjects exhibit a pattern of ‘tacit cooperation’ until shortly before the end of the game, when they start to adopt noncooperative behavior.”

Uncertain

Verify: the exact bound Kreps, Milgrom, Roberts & Wilson prove on the number of end-game rounds in which defection occurs. Reason: the 1982 Journal of Economic Theory paper is a paywalled or image-only source here. web.stanford.edu/~milgrom/publishedarticles/RationalCooperation.pdf returned HTTP 200 but pdftotext extracts five bytes — it is a pure image scan with no text layer; the DTIC mirror apps.dtic.mil/sti/tr/pdf/ADA121729.pdf returned HTTP 403. Everything stated above about the KMRW result is taken from the SEP summary and from Kreps & Wilson’s companion JET paper, both read directly. To resolve: obtain a text-bearing copy of JET 27(2) 245–252 and read the bound.

A Backward-Induction Solver in C

The claims above are checkable, so I checked them. The solver is a generic finite perfect-information game tree with per-node payoff vectors and a single post-order pass. It is deliberately not minimax: there is no min in it and no zero-sum assumption. Each mover maximises her own coordinate.

typedef struct {
    int   player;              /* -1 for a terminal node, else 0 or 1        */
    int   nchild;
    int   child[MAXCHILD];     /* indices into the arena                     */
    int   payoff[NPLAYERS];    /* meaningful only at terminal nodes          */
    int   dindex;              /* decision-node index for its owner, else -1 */
} Node;
 
static void bi(const Game *g, int x, int *best, int out[NPLAYERS]) {
    visited++;
    const Node *nd = &g->n[x];
    if (nd->player < 0) {                  /* leaf: already marked          */
        leaves_seen++;
        out[0] = nd->payoff[0];
        out[1] = nd->payoff[1];
        return;
    }
    int bestc = -1, bestval = 0, cur[NPLAYERS], keep[NPLAYERS] = {0, 0};
    for (int c = 0; c < nd->nchild; c++) {
        bi(g, nd->child[c], best, cur);    /* mark the successor first      */
        if (bestc < 0 || cur[nd->player] > bestval) {
            bestc  = c;
            bestval = cur[nd->player];     /* compare ONLY the mover's own  */
            keep[0] = cur[0];              /* but carry the WHOLE vector up */
            keep[1] = cur[1];
        }
    }
    best[x] = bestc;
    out[0] = keep[0];
    out[1] = keep[1];
}

Line by line, the two lines that matter are bestval = cur[nd->player] — the comparison is on the mover’s own coordinate, which is why this is not minimax — and keep[0] = cur[0]; keep[1] = cur[1] — the entire vector propagates, which is why the other player’s payoff at the chosen successor is available to the previous mover. Strip the second coordinate and negate on alternate plies and you have exactly the recurrence in Game Theory DP.

The centipede builder reproduces McKelvey and Palfrey’s laboratory trees exactly, at ten times the stakes so the arithmetic stays in integers:

static int build_centipede(Game *g, int n) {
    int scale[64], small[64];
    scale[0] = 4; small[0] = 1;            /* $0.40 large pile, $0.10 small */
    for (int i = 1; i <= n; i++) {
        scale[i] = scale[i-1] * 2;         /* "both piles are multiplied    */
        small[i] = small[i-1] * 2;         /*  by two" on every PASS        */
    }
    /* ... build back to front, TAKE gives the mover scale[i] ... */
}

For n = 4 this generates the tree in McKelvey and Palfrey’s Figure 1 scaled by ten; for n = 6, their Figure 2. Their six-move terminal node is ($25.60, $6.40); the builder produces (256, 64). That agreement is the check that the game being solved is the game that was actually run.

Measured results

Built with gcc -O2 -Wall -Wextra -std=c11 (gcc 16.1.1, Fedora, Linux 7.1.8, 32 logical cores). All numbers below were produced on 2026-08-28 with /proc/loadavg reading 2.49 2.13 1.89 at the start of the run — the machine was moderately loaded, so treat the wall times as upper bounds.

Centipede, backward induction:

n	nodes	leaves	nodes visited	BI value (P1, P2)	action at root
2	5	3	5	(4, 1)	TAKE
4	9	5	9	(4, 1)	TAKE
6	13	7	13	(4, 1)	TAKE
8	17	9	17	(4, 1)	TAKE
10	21	11	21	(4, 1)	TAKE
12	25	13	25	(4, 1)	TAKE

The node count is 2n + 1 and visited equals allocated: the traversal touches every node exactly once, which is the whole point — backward induction is O(|tree|), not O(b^d). The value is (4, 1) for every n, which is the formal statement of “the pot can grow to any size and the first mover still takes $0.40.”

Nash equilibria versus subgame-perfect equilibria. The solver also enumerates every pure strategy profile — a strategy being a choice at every node the player owns, including unreachable ones — and classifies each as Nash and/or subgame perfect:

n	profiles	pure Nash equilibria	subgame perfect	share of NE with the BI outcome
2	4	1	1	1/1
4	16	4	1	4/4
6	64	16	1	16/16
8	256	64	1	64/64
10	1,024	256	1	256/256
12	4,096	1,024	1	1,024/1,024
14	16,384	4,096	1	4,096/4,096
16	65,536	16,384	1	16,384/16,384

Three things fall out. The pure Nash count is exactly 2^(n−2), growing exponentially, while there is always exactly one subgame-perfect equilibrium — a measured demonstration that subgame perfection is a strict refinement. And every Nash equilibrium yields the backward-induction outcome (4, 1), which confirms the textbook claim from the SEP that “the only Nash equilibria of the game are those where the first player takes two dollars on the first move and the only subgame perfect equilibrium is the one in which both players take two dollars on any turn they should get.” The extra Nash equilibria differ only in what players plan to do at nodes that are never reached. That is why the centipede is such a clean test case: the refinement changes the strategy prediction without changing the outcome prediction at all, so any experimental deviation is a deviation from all of them at once.

An independent Python re-implementation using exact integer arithmetic reproduces the same counts (1, 4, 16, 64, 256, 1024 for n = 2 … 12) and confirms ne == 2^(n−2) and that all Nash outcomes equal the backward-induction value.

Tic-tac-toe, as the checkable zero-sum case. Full backward induction from the empty board with no memoisation and no pruning:

value from the empty board (X to move): 0   (0 = draw)
nodes visited : 549946
terminal nodes: 255168
   X wins     : 131184
   O wins     :  77904
   draws      :  46080
wall time     : 0.0064 s        loadavg 2.49 2.13 1.89

255,168 is the standard published count of distinct tic-tac-toe games, and the win/loss/draw split 131,184 / 77,904 / 46,080 matches it; two independently written implementations (C and Python) produced identical figures here. The value 0 is the known result that tic-tac-toe is a draw under optimal play. This is the sanity check the Games and Strategic Systems in C MOC asks for — solve a game whose answer you already know before trusting the solver on one you do not. It is also the case where backward induction and minimax genuinely coincide: the game is strictly competitive, so a single scalar suffices and the max/min alternation of Game Theory DP is exactly this code with the vector collapsed. See Alpha-Beta Pruning for what these node counts become when you stop expanding provably irrelevant subtrees.

Failure Modes and Gotchas

Assuming the game is zero-sum when it is not. This is the single most common error when carrying minimax intuitions into game theory, and the centipede is the counterexample: both players strictly prefer passing to the backward-induction outcome, so there is no scalar to alternate max and min on. If you write return -bi(child) you have silently assumed strict competition. Symptom: the solver reports plausible values on chess-like games and nonsense on anything with common interest. Diagnosis: check whether payoff[0] + payoff[1] is constant across all leaves; if not, you need vectors.

Ties propagate arbitrary choices upward. When a mover is indifferent, the procedure picks one successor and the other player’s payoff from that successor propagates. Two runs of the same solver with different child ordering can therefore produce different predicted outcomes. This is not a bug in the code; it is the reason every careful statement of the uniqueness result says “for generic payoffs.” Bonanno’s Definition 2.3 is explicit: “in general, at a decision node there may be several choices that maximize the payoff of the player who moves at that node. If that is the case then the procedure requires that one such choice be selected. This arbitrary choice may lead to the existence of several backward-induction solutions.” Symptom: your solver disagrees with a textbook on a game with repeated payoff values. Fix: detect ties explicitly and either enumerate all solutions or refuse to report a unique one.

Confusing the backward-induction outcome with the backward-induction profile. The outcome is the terminal node reached; the profile is the complete plan, including moves at unreached nodes. My measurements above make the gap concrete: at n = 16 there are 16,384 pure Nash equilibria, all with the same outcome, and only one is the backward-induction profile. Papers that say “the centipede has a unique equilibrium” almost always mean the unique subgame-perfect profile, and papers that say “all equilibria predict immediate stopping” mean the unique outcome. Both are true and they are different statements.

Reading off-path marks as predictions. A node marked (16, 4) is not a prediction that anyone will ever get 16. It is a conditional: if this node were reached, this is what would follow. Since backward induction typically predicts that the node is never reached, the mark is a counterfactual, and — per the paradox above — a counterfactual whose antecedent contradicts the premises used to compute it.

Recursion depth and repeated positions. The generic solver above recurses to the depth of the tree. For a game like tic-tac-toe that is nine plies and harmless; for anything deeper, and especially for any game where the same position is reachable by multiple move orders, the unmemoised traversal is exponential where a memoised one is polynomial. That is precisely the territory Game Theory DP covers, and the fix — a transposition table keyed on the position rather than the path — is the same one. Note that memoisation is only sound if the payoff depends on the position and not on the path taken to reach it.

Treating experimental refutation as a coding error. If your solver says “take at node 1” and your subjects pass, the solver is right and the model is wrong. The failure is in the mapping from the situation to the tree — usually in the payoffs (subjects may value the opponent’s money), in the information (subjects may not believe the opponent is a maximiser), or in the horizon (subjects may not treat the announced last round as final).

Alternatives and When to Choose Them

Concept	Applies to	What it adds	What it costs
Backward induction	Finite, perfect information	A complete plan and a unique outcome for generic payoffs; `O(tree)`	Requires common knowledge of substantive rationality; incoherent off-path
Subgame Perfect Equilibrium (Selten 1965)	Any extensive-form game with proper subgames	Generalises the idea to games with simultaneous moves inside subgames	Silent when there are no proper subgames
Trembling-hand perfection (Selten 1975)	Extensive and normal form	Makes off-path reasoning coherent by positing execution errors	Off-path play conveys no information about the opponent
Sequential equilibrium (Kreps & Wilson 1982)	Games with information sets	Explicit beliefs at every information set, consistent with Bayes where it applies	An equilibrium is now an assessment, not a strategy profile
Quantal response equilibrium	Anything with noisy agents	Fits the observed monotone take-probability gradient rather than predicting a step function	Estimated, not derived; a free parameter per specification
Reputation / incomplete information (KMRW 1982)	Finitely repeated games	Recovers cooperation-until-the-end from a small prior on opponent type	Requires positing types; multiple equilibria return
Alpha-Beta Pruning	Zero-sum, perfect information	Same answer, far fewer nodes	No help in general-sum games — you cannot prune on a vector
Counterfactual Regret Minimization	Large imperfect-information games	Converges without enumerating the tree	Approximate; two-player zero-sum guarantees only

The practical selection rule: if the game is finite and perfect-information and you want the answer, use backward induction; if you want to predict behaviour, do not. For prediction, the question to ask first is whether the horizon is commonly known, because if it is not, the entire induction fails to start and you should be reading Iterated Games and the Shadow of the Future and The Folk Theorem instead.

Production Notes

Where the algorithm is deployed and works. Backward induction is the computational core of every solved game — see Zermelo’s Theorem and Solved Games — and of retrograde analysis in endgame tablebases, where the marking procedure runs over positions rather than a tree because positions repeat. It is also what a Stackelberg model is: Levin solves quantity leadership by “work[ing] backward” from firm 2’s best-response function, and the resulting first-mover advantage is a backward-induction artefact, not a modelling assumption.

Where it is deployed and its predictions fail predictably. Selten’s chain-store paradox was posed as a live problem in industrial organisation because the theory’s prediction — never fight entry — contradicted what firms were observed to do. The resolution that stuck (Kreps & Wilson, Milgrom & Roberts, 1982) was to keep backward induction and change the information structure, and this remains the standard move: when a finite-horizon model predicts unravelling and the field does not unravel, add incomplete information about types rather than abandoning the induction.

Anchoring at the end is a real phenomenon, and it is measurable. McKelvey and Palfrey’s Table IIB shows take probabilities rising from .01 to .85 across six nodes. Nagel and Tang ran the centipede in reduced normal form — both players choose their stopping node simultaneously, 100 repetitions against randomly chosen opponents — precisely to separate learning from the tree structure (Nagel & Tang 1998, Journal of Mathematical Psychology 42:356–384). If you are modelling human agents in a finite-horizon interaction, the useful default is not “they will backward-induct” and not “they will ignore the endgame,” but “they will backward-induct over a short window anchored at the end.”

A practical instrumentation habit. Report node counts, not just values. The tic-tac-toe figures above (549,946 nodes, 255,168 leaves) are checkable against published counts and instantly reveal an off-by-one in terminal detection or a missing win-check. Any game-tree code that does not count nodes cannot be verified against anything.

Uncertain

Verify: Selten’s 1975 formulation of trembling-hand perfection, in his own words. Reason: link.springer.com/content/pdf/10.1007/BF01766400.pdf returns HTTP 200 with an HTML shell rather than the PDF (3,038 bytes, file reports “HTML document”). Selten’s 1965 subgame-perfection paper is in German in Zeitschrift für die gesamte Staatswissenschaft 121, 301–24 and 667–89 and was not located online at all. Everything attributed to Selten here is therefore cited bibliographically and via secondary quotation — the Nobel committee’s 1994 press release, the Stanford Encyclopedia, and Kreps & Wilson’s direct discussion of Selten’s Figure 3 — not from the primary text. To resolve: obtain International Journal of Game Theory 4:25–55 or the reprint in Kuhn (ed.), Classics in Game Theory, Princeton 1997, pp. 317–354.

vault

Explorer

Backward Induction

Backward Induction

Mental Model

What Zermelo Actually Proved

The Algorithm, Step by Step

What Backward Induction Assumes

The Centipede Game, Worked in Full

The theoretical prediction

The data

The paradox is not resolved by calling people irrational

The Paradox of Backward Induction

The Finitely Repeated Prisoner’s Dilemma Unravels the Same Way

A Backward-Induction Solver in C

Measured results

Failure Modes and Gotchas

Alternatives and When to Choose Them

Production Notes

See Also

Graph View

Table of Contents

Backlinks