backward induction: one construct, many systems

In the theory of extensive-form games, backward induction solves a game of perfect information by starting at the terminal decisions, fixing each player's optimal choice there, and folding those choices back toward the first move so that every decision is a best response to rational continuation. Kuhn's 1953 Extensive games and the problem of information set out the extensive form and the reasoning that yields this kind of solution, which later underpins subgame-perfect equilibrium. The referent is a procedure for sequential strategic choice; it is the same stepping-back-from-the-end logic that operations research developed as dynamic programming.[1]

Unit

The optimal action chosen at each decision node, resolved from the terminal nodes back

Recovery means

Not applicable

Measured by

Applied by solving terminal subgames first and propagating optimal choices back to the root of the game tree

Bellman's 1957 Dynamic programming states the principle of optimality: an optimal policy has the property that, whatever the initial decision, the remaining decisions must be optimal for the state that results; so a multistage optimization is solved by working backward from the last stage, computing the best continuation value at each state. This backward recursion over stages is the identical construct as game-theoretic backward induction, with decision nodes replaced by states and payoffs by value functions. It is the engine behind optimal control, shortest-path algorithms, and sequential decision problems throughout operations research.[2]

Unit

The optimal value and decision at each state, computed from the final stage backward

Recovery means

Not applicable

Measured by

Implemented as a backward recursion solving the Bellman equation stage by stage