Backward induction is a method for solving a finite sequential decision problem by working backward from its terminal states. At each stage, the optimal value or choice is determined using the later states that have already been solved, and the process is repeated until the initial state is reached. In dynamic programming, this gives a standard method for finite-horizon optimization theory problems.
In game theory, applying backward induction to a finite game of perfect information produces a subgame-perfect equilibrium. The centipede game is a standard example in which this prediction differs sharply from cooperative play.
