Backward Induction

Backward induction solves sequential (extensive-form) games by starting at the terminal nodes and working backward to the root. At each decision node, the player chooses the action that maximizes their payoff given what will happen downstream. Concrete example — The Centipede Game: Two players alternate. At each turn, a player can "take" (ending the game) or "pass." The pot grows at each stage: stage 1 payoffs are (1,0), stage 2 payoffs are (0,2), stage 3 are (3,1), stage 4 are (2,4). At the last node, Player 2 prefers to take (4 > 1). Knowing this, at the second-to-last node, Player 1 prefers to take (3 > 2). Continuing backward, the subgame-perfect equilibrium has Player 1 taking immediately — even though mutual cooperation would yield higher payoffs. The algorithm: 1. Identify all terminal nodes and their payoffs 2. At each decision node with only terminal successors, the player picks the action giving the best payoff 3. Replace that node with its resulting payoff 4. Repeat until you reach the root Subgame-perfect equilibrium: Backward induction produces a strategy profile that is a Nash equilibrium in every subgame — not just the overall game. This eliminates "incredible threats" that ordinary Nash equilibrium allows. When to use: Any finite sequential game with perfect information — bargaining games (Rubinstein model), pirate puzzles, Stackelberg competition, centipede games, and option exercise timing. The technique also applies to dynamic programming and optimal stopping problems. Limitation: Requires the game to be finite. In infinite-horizon games, you need other methods (folk theorems, value functions).