Extensive-Form Games & Backward Induction
Game trees, solved by rolling back optimal moves from the leaves.
The idea
An extensive-form game represents play that unfolds in turns, each player seeing all earlier moves. Draw the game as a tree: each non-leaf node belongs to the player who moves there, the branches leaving it are that player's options, and each leaf carries a payoff for every player.
Algorithm.
Algorithm: Backward Induction Input: a finite game tree Output: a branch fixed at every node, and the payoffs of the play those choices produce 1. pick a node whose branches all lead to leaves 2. the player moving there chooses the branch whose leaf pays them the most in their own coordinate; record that choice // no further uncertainty at such a node 3. replace the node by the chosen leaf's payoffs // the node becomes a leaf; each recorded choice stays optimal given the choices below it 4. if the root is now a leaf, return the recorded choices and the root's payoffs; otherwise go to step 1
The result is a subgame-perfect equilibrium: a branch fixed at every node, such that at no node — including nodes the play never reaches — can the player moving there raise their own payoff by choosing a different branch, given the choices fixed everywhere else. The requirement at unreached nodes is what gives the concept its force: a threat that would not be optimal to carry out is not credible, and subgame perfection excludes it.
The figure shows one rollback step on a schematic tree: the root's other branch ends at the payoff pair $(a_{1}, a_{2})$, and player $2