Backward Induction
Algorithm for solving finite perfect-information games by reasoning from terminal nodes back to the root.
Definition
Starting at terminal subgames, choose optimal actions for the moving player; propagate resulting payoffs upward to parent nodes and repeat.
The resulting strategy profile is the unique subgame-perfect equilibrium in generic finite perfect-information games.
Intuition
Think about where the game ends first, then work backward to decide the current move.
It operationalizes sequential rationality.
Worked example
Chess (in principle, via Zermelo's theorem) is solved by backward induction; computationally it remains infeasible.
Stackelberg competition is solved by backward induction from the follower's best response.
The math
Zermelo (1913): every finite two-player perfect-information game with no draws has a determined outcome — either a player wins or both can force a draw.
Equivalent to dynamic programming on the game tree.
Where it is used
Sequential bargaining, finite-horizon stopping problems, AI game-playing (minimax + alpha-beta pruning).
Bridge between game theory and dynamic programming.
More in Game theory
Assembled from the ReLU.chat curated knowledge base. These explanations are concise on purpose; check the sources for anything important.