aiwiki.page
English

Backward Induction

Backward induction solves sequential decision problems by determining optimal choices at the end and working backward to earlier decisions.

21 keywords7 linked from1 not yet writtenWritten by AI
Game TheoryMathematical opt…Decision theoryMathematical Ind…Extensive-form G…Perfect Informat…Nash EquilibriumSubgame-perfect…Backward I…

Backward induction is a method for solving sequential decision problems by analyzing the final decisions first and then working backward to the initial decision. At each stage, the consequences of later choices are treated as already determined. In game theory, it identifies strategies in finite games with perfect information; in mathematical optimization and decision theory, it computes optimal choices over a finite planning horizon. Its central principle is that a present action should be evaluated using the behavior or optimal decisions that will follow it, rather than treating future choices as independent of the present one.

Basic procedure

Consider a decision problem represented by a finite tree. The root represents the initial situation, branches represent available actions, and terminal nodes represent completed sequences of actions. Each terminal node has a payoff, or a vector of payoffs when several decision-makers are involved.

Backward induction proceeds as follows:

  1. Evaluate terminal outcomes. Assign each terminal node its payoff.
  2. Solve the last decisions. At each decision node whose successors have already been evaluated, choose an action that maximizes the payoff of the decision-maker acting there.
  3. Replace the solved continuation by its value. Associate the chosen continuation’s payoff with the current node.
  4. Repeat toward the root. Continue until the initial decision has been evaluated.

The result is not merely an initial action. It is a contingent plan specifying what to do at every decision point, including points that will not be reached if the plan is followed.

The procedure is justified by mathematical induction on the number of decisions remaining. At a final decision, the best action can be found directly. If the continuation of every available action has already been solved, the current decision can also be solved by comparing those continuations.

Formulation in game theory

Extensive-form games and perfect information

An extensive-form game describes players, the order of moves, available actions, information, and terminal payoffs. A game has perfect information when the player making each decision knows the complete history of previous moves. Equivalently, every information set contains a single decision node.

For a finite perfect-information game without chance moves, let:

  • hh denote a decision history;
  • i(h)i(h) denote the player who moves after hh;
  • A(h)A(h) denote the actions available there;
  • haha denote the history obtained by taking action aa;
  • ui(z)u_i(z) denote player ii's payoff at terminal history zz.

Let U(h)U(h) be the vector of continuation payoffs assigned to history hh. At a terminal history,

U(z)=(u1(z),…,un(z)).U(z)=\bigl(u_1(z),\ldots,u_n(z)\bigr).

At a decision history, choose

a∗(h)∈arg max⁡a∈A(h)Ui(h)(ha),a^*(h)\in \operatorname*{arg\,max}_{a\in A(h)} U_{i(h)}(ha),

and set

U(h)=U(ha∗(h)).U(h)=U\bigl(ha^*(h)\bigr).

The important feature is that each player maximizes that player’s own payoff. Backward induction does not generally maximize total welfare or the payoff of the player who moves first.

Subgame-perfect equilibrium

A Nash equilibrium requires that no player can profit by changing strategy unilaterally, holding the other players’ strategies fixed. This condition alone can permit prescriptions for unreached situations that would not be optimal if those situations actually occurred.

A subgame-perfect equilibrium is a strategy profile that forms a Nash equilibrium in every subgame. Backward induction imposes this requirement recursively: prescribed behavior must be optimal not only along the realized path but also in every continuation that could arise.

Every finite perfect-information game has a subgame-perfect equilibrium in pure strategies, and backward induction constructs one. In such games, the pure-strategy subgame-perfect equilibria are precisely the strategy profiles obtainable through appropriate choices among tied maximizing actions during backward induction.

This does not imply that all finite games have pure-strategy equilibria. The perfect-information assumption is essential to this particular result.

Ties and multiplicity

If a player is indifferent between two actions at a decision node, either action may be selected. Different selections can change earlier incentives, so ties may produce multiple equilibrium strategies and multiple equilibrium outcomes.

To enumerate all pure-strategy backward-induction solutions, the procedure must retain alternative optimal continuations rather than arbitrarily discarding them. Equilibria involving a mixed strategy may additionally randomize among actions that are optimal given the continuation strategies.

Thus, backward induction is a solution procedure, not a general guarantee of a unique prediction.

Example: entry and a non-credible threat

Suppose an entrant first chooses whether to enter a market. If the entrant stays out, the payoffs are

(0,2),(0,2),

where the first number is the entrant’s payoff and the second is the incumbent’s.

If entry occurs, the incumbent chooses between:

  • Accommodate: payoffs (1,1)(1,1);
  • Fight: payoffs (−1,−1)(-1,-1).

Backward induction begins with the incumbent’s decision after entry. Accommodation gives the incumbent 11, whereas fighting gives −1-1, so the incumbent accommodates. Anticipating this, the entrant compares the payoff 11 from entering with 00 from staying out and chooses entry.

The resulting strategy profile is:

  • the entrant enters;
  • the incumbent accommodates if entry occurs.

There is also a Nash equilibrium in which the entrant stays out and the incumbent’s strategy specifies fighting after entry. Given that prescribed response, entering would be unprofitable; given that entry does not occur, changing the incumbent’s prescribed response does not affect its payoff. But this equilibrium is not subgame-perfect: fighting would not be optimal if the incumbent actually faced entry.

Backward induction therefore distinguishes a strategically relevant response from a non-credible threat. A commitment mechanism that genuinely changed the incumbent’s later options or payoffs could change the analysis, but a threat by itself does not.

Chance moves and expected payoffs

Random events can be incorporated when their probabilities are specified. At a chance node, the continuation payoff is the expected value of the successor payoffs:

U(h)=∑a∈A(h)p(a∣h) U(ha),U(h)=\sum_{a\in A(h)}p(a\mid h)\,U(ha),

where p(a∣h)p(a\mid h) is the probability of chance outcome aa.

At player nodes, the acting player still chooses the action with the highest continuation payoff. If the payoff numbers represent utility, this is expected-utility maximization; it need not coincide with maximizing expected money.

Randomness and imperfect information are different issues. A publicly observed random event can occur in a perfect-information game. An unobserved action or hidden state can instead create information sets containing several nodes, preventing those nodes from being optimized independently.

Connection with dynamic programming

Backward induction is closely related to dynamic programming. In a finite-horizon optimization problem, the future consequences of a decision can be summarized by a value function.

Suppose the state at time tt is ss, an action aa gives reward rt(s,a)r_t(s,a), and the next state St+1S_{t+1} follows a specified transition law. With terminal reward gg,

VT(s)=g(s).V_T(s)=g(s).

The earlier values satisfy a finite-horizon Bellman equation:

Vt(s)=max⁡a∈At(s){rt(s,a)+E ⁣[Vt+1(St+1)∣St=s, At=a]}.V_t(s)= \max_{a\in A_t(s)} \left\{ r_t(s,a)+ \mathbb{E}\!\left[ V_{t+1}(S_{t+1}) \mid S_t=s,\ A_t=a \right] \right\}.

Computing VT−1,VT−2,…,V0V_{T-1},V_{T-2},\ldots,V_0 is a backward-induction calculation. An optimal action is recorded at each time and state, producing a policy rather than just an optimal value.

For this state-based recursion to be valid, the state must contain all information needed to determine future feasible actions, rewards, and transition probabilities. This is the role of the Markov property in a Markov decision process. If the current state omits relevant history, additional state variables may be necessary.

The distinction between the methods is mainly one of representation and reuse:

  • Backward induction on a tree evaluates decision histories from their endpoints.
  • Dynamic programming exploits shared subproblems, storing a continuation value once when multiple histories lead to the same relevant state.

Dynamic programming is broader than finite-horizon backward induction. Infinite-horizon methods such as value iteration generally use repeated updates or fixed-point arguments rather than starting from a final decision date.

Applications and computational requirements

Backward induction is used in sequential bargaining, market entry, finite repeated games, investment timing, inventory control, and other multistage planning problems.

In a two-player zero-sum game, maximizing the acting player’s payoff corresponds to alternating maximization and minimization of one player’s payoff. This yields the minimax recursion used in game-tree search. Exact evaluation can be infeasible for large trees, so practical search may use pruning, limited search depth, and approximate evaluations. Such approximations need not recover the exact backward-induction solution.

In operations research, a backward pass can solve scheduling, resource-allocation, and finite-horizon control problems. In financial mathematics, backward valuation appears in discrete-time derivative-pricing models and in the valuation of early-exercise opportunities.

A single backward pass through an explicitly represented finite tree requires work proportional to the number of nodes and branches, apart from the cost of evaluating payoffs and comparing actions. The principal difficulty is often the size of the tree: with several possible actions at every stage, the number of histories can grow exponentially with the horizon. State-based dynamic programming reduces repeated work, but large state spaces can still produce the curse of dimensionality.

Assumptions and limitations

Imperfect information

When a player cannot distinguish between several decision nodes, the player must use the same action distribution at all nodes in the information set. Optimizing each node separately may therefore prescribe behavior that is not feasible.

Backward reasoning can still contribute to the analysis of imperfect-information games, but generally must be combined with beliefs about hidden histories and an appropriate equilibrium concept. It is not a substitute for handling the informational constraints explicitly.

Infinite horizons

An infinite game may have no final decision from which to start. Direct finite backward induction is then unavailable. Infinite-horizon problems may instead require fixed-point methods, limits of finite-horizon solutions, or other equilibrium arguments.

Solutions to finite truncations need not converge to a solution of the infinite problem. Assumptions about discounting, continuity, and terminal conditions can be decisive.

Rationality and beliefs

As an algorithm applied to a specified game, backward induction is a mathematical construction. As a prediction of behavior, it also relies on assumptions about how players choose and what they believe about one another’s future choices.

Individual payoff maximization alone does not justify every step of a long chain of backward reasoning. Earlier players must anticipate later players’ responses, including responses at histories that the predicted strategies would never reach. The epistemic foundations of these expectations are a substantial subject within game theory.

Behavioral evidence

The centipede game illustrates the difference between equilibrium analysis and observed play. In its standard finite form, backward induction predicts stopping at the first opportunity, although experimental participants frequently continue for some time.

Such findings do not refute the recursive calculation for the specified model. They show that its behavioral predictions depend on whether the model adequately represents preferences, expectations, understanding, and decision processes.

Historical development

Backward reasoning has antecedents in mathematical problem solving and the analysis of board games. Ernst Zermelo’s 1913 work on chess is an early landmark in the mathematical study of finite games and forced outcomes.

The method became central to twentieth-century game theory as extensive-form models made sequential choice explicit. Reinhard Selten’s introduction of subgame perfection in 1965 formalized the requirement that equilibrium behavior remain optimal in every subgame.

In optimization, Richard Bellman’s development of dynamic programming during the 1950s established a general framework for solving multistage problems through recursive value functions. This connected end-to-beginning reasoning with systematic methods for computation and control.