Backward Induction¶

Method¶

Let $\Gamma$ be a finite extensive-form game of perfect information (every information set is a single node).

Take a decision node all of whose immediate successors are terminal nodes. At a player's node, choose an action that maximizes that player's payoff. At a Nature node, keep its fixed probabilities and compute each player's expected payoff across the successors.
Replace that node by a terminal node carrying the chosen action's payoffs, or the expected payoff vector at a Nature node.
Repeat steps 1–2 until the root has been processed.

The actions chosen at all player decision nodes, including nodes that are not reached, form a profile of strategies, the backward-induction solution. Without Nature, the path from the root through the chosen actions is the backward-induction outcome. With Nature, her fixed probabilities give a distribution over paths and terminal outcomes.

Interpretation¶

Each player is treated as a rational agent who, whenever she moves, best responds to what she correctly predicts later movers will do. The last mover's choice needs only her own rationality; the second-to-last mover's choice requires that she knows the last mover is rational, and so on. For long games the argument therefore relies on common knowledge of rationality, and in games such as the centipede game experimental behaviour departs from the prediction.

The method needs a last move. In infinite-horizon games, such as infinitely repeated games, there is no last node, and equilibria are checked instead with the one-stage deviation principle.

A common error is to report only the outcome. The solution is a full strategy profile: it states what each player would do at every node, including nodes that the solution itself avoids.

Key Results¶

In a finite game of perfect information, the backward-induction profile is a subgame-perfect Nash equilibrium, and every pure-strategy SPNE arises from backward induction with some tie-breaking (Zermelo, Kuhn).
Consequently every finite game of perfect information has a pure-strategy Nash equilibrium.
In a game without Nature, if no player has the same payoff at two different terminal nodes, there are no ties and the solution is unique. With Nature, distinct terminal payoffs need not prevent ties between expected continuation payoffs; uniqueness follows if every player node has a unique maximizing action during the backward calculation.
With ties, each choice among the maximizing actions gives a (possibly different) SPNE.
For games with imperfect information, generalized backward induction replaces each smallest subgame by the payoffs of one of its Nash equilibria and continues.

Examples¶

Entry game. Out gives $(0,2)$ to (entrant, incumbent); after In, Accommodate gives $(1,1)$ and Fight $(-1,-1)$ . At the incumbent's node, $1>-1$ $- 1$ , so she accommodates. Replacing the node by $(1,1)$ , the entrant compares $1$ (In) with $0$ (Out) and enters. Solution: (In, Accommodate).

Three-move centipede. Player 1 chooses Stop, giving $(1,0)$ , or Continue. Player 2 then chooses Stop, $(0,2)$ , or Continue. Player 1 finally chooses Stop, $(3,1)$ , or Continue, $(2,4)$ .

Node 3 (player 1): $3>2$ $2$ , Stop; replace by $(3,1)$ .
Node 2 (player 2): Stop gives $2$ , Continue gives $1$ ; Stop. Replace by $(0,2)$ .
Node 1 (player 1): Stop gives $1$ , Continue gives $0$ ; Stop.

Solution: player 1 plays (Stop, Stop), player 2 plays Stop, outcome $(1,0)$ . Both $(3,1)$ and $(2,4)$ give both players strictly more, so the outcome is not Pareto efficient.

Three-move centipede game drawn as a horizontal tree with Stop branches hanging down; every Stop branch is highlighted and each node carries its backward-induction value.

The figure solves the centipede from right to left. Step 1 compares $3$ with $2$ at player 1's last node and replaces it by $(3,1)$ ; step 2 lets player 2 compare $2$ with $1$ and replaces her node by $(0,2)$ ; step 3 lets player 1 compare $1$ with $0$ at the root. The highlighted Stop branches are the chosen actions at all three nodes, which together form the backward-induction solution, although only the first is reached.

Prerequisites¶

Sources¶

Game Theory · Week 3

Aliases: backwards induction, Zermelo's algorithm, rollback Keywords: solve from the end, perfect information, centipede game, Zermelo's theorem, Kuhn's theorem, tie-breaking, entry game Symbols: gamma

Last updated: 27 October 2026 11:52