Backward induction solves a sequential game by starting with its final decisions and working towards the beginning, at each step choosing an action that is best for the player who moves there. For a quant modelling strategic execution or negotiation, it tests whether an anticipated response would still make sense when the counterparty actually gets to choose.
The elementary method applies to a finite game of perfect information: there are finitely many decision nodes, and each player observes the preceding actions when moving. Here we also assume the rules and payoffs are known to everyone. The game-theory question is whose objective determines each choice, rather than which outcome looks best to the modeller. Yildiz’s MIT notes, §1, set out the rollback procedure.
A threat that disappears after entry
Consider a fictional one-shot market-entry game. An entrant first chooses Stay out or Enter. After observing entry, the incumbent chooses Fight or Accommodate. Both maximise the dimensionless utility scores below. These are stipulated preferences, not estimated profits or a forecast of market behaviour.
Each pair is (entrant payoff, incumbent payoff):
| Outcome | Payoffs |
|---|---|
| Stay out; game ends | |
| Enter, then Fight | |
| Enter, then Accommodate |
The incumbent likes keeping the market to itself: its payoff of 2 exceeds the 1 from accommodation. But staying alone is no longer available after entry has happened. At that point, the incumbent compares its two remaining payoffs:
Carry the resulting payoff pair back to the entrant’s decision. Entering now gives the entrant 1, while staying out gives it 0:
The selected strategy profile is Enter; Accommodate if entry occurs, with realised payoffs .
Work backwards through incentives, then read the selected path forwards. At each decision, compare the acting player’s payoff, while carrying both players’ payoffs back through the tree.
Notice the two comparisons use different coordinates. At the incumbent’s node, maximise the second payoff; at the entrant’s node, maximise the first. Maximising their sum, or always maximising the entrant’s number, solves a different problem.
Why “Stay out; Fight if challenged” can still be Nash
A strategy in a sequential game is a complete contingent plan, including what to do at decision nodes that the plan never reaches. The incumbent’s strategy therefore specifies a response to entry even when the entrant stays out. Polak’s Yale lecture, chapters 5–6, explains this distinction and the entry-deterrence problem.
Suppose the specified profile is Stay out; Fight if entry occurs. It satisfies the Nash-equilibrium test of no profitable unilateral strategy change:
- Holding Fight fixed, the entrant gets 0 by staying out and −1 by entering, so it stays out.
- Holding Stay out fixed, the incumbent receives 2 whichever response it specifies. Changing its unused plan cannot raise that payoff.
But if entry actually occurs, fighting gives the incumbent −1 instead of the available 1. The threat is not credible: it is inconsistent with the incumbent’s incentives at the very decision where it would be carried out.
A subgame-perfect equilibrium requires a Nash equilibrium in every subgame, including those not reached along the selected path. In this perfect-information tree, the incumbent’s post-entry decision is itself a subgame. Fight fails there; Accommodate passes. Thus Enter; Accommodate if entry occurs is the unique subgame-perfect equilibrium of this example. Ozdaglar’s MIT lecture, slides 14–22, develops the refinement and its connection to backward induction.
What the rollback assumes
The algorithm chooses an optimal continuation at every decision node and retains these choices as strategies. It then propagates the associated payoff vectors backwards. On a finite perfect-information tree, this constructs a pure-strategy subgame-perfect equilibrium. Tied best actions can yield several pure-strategy solutions; preserve the alternatives rather than silently declaring uniqueness. Strict comparisons make this example unambiguous.
The reasoning is conditional on players anticipating rational continuation choices, including after unexpected moves. Hidden actions or private information prevent simply optimising independently at every drawn node: a player may not know which node has been reached. A Bayesian game introduces private types and beliefs; an infinite horizon removes the terminal decision from which this elementary procedure starts.
The rollback resembles dynamic programming, but different players can control different decisions and maximise different objectives. It also differs from rolling back an option-pricing tree: a European option’s continuation value uses discounted risk-neutral expectation, rather than a counterparty choosing its preferred branch.
A threat can become credible if an earlier action changes the later feasible choices or payoffs. That is the role of credible commitment. A verbal promise alone does not change this game’s payoff table. Repeated interaction, reputation and inventory constraints would need to be modelled explicitly before applying the conclusion to trading.
Test the continuation, even when it is unused
In a separate fictional game with the same timing, Stay out gives , Enter then Fight gives , and Enter then Accommodate gives . Payoffs again list entrant first and incumbent second. Find the backward-induction strategy profile and its realised payoffs. Is the incumbent’s off-path threat credible?
Answer. After entry, the incumbent prefers Fight because . Anticipating a payoff of −2 from entering, the entrant stays out because . The full profile is Stay out; Fight if entry occurs, with realised payoffs . Fighting is credible here despite never occurring: the changed payoffs make it optimal in the post-entry subgame. An unused action is not automatically an empty threat.
Sources
- Muhamet Yildiz, MIT 14.12, Lectures 7–9, §1 “Backwards induction” and §2 “Subgame perfection”.
- Ben Polak, Yale ECON 159, Lecture 15, chapter 5 “Games of Perfect Information: Definition” and chapter 6 “Games of Perfect Information: Economic Example”. The article uses independently specified payoffs.
- Asu Ozdaglar, MIT 6.254, Lecture 12: Extensive Form Games, slides 14–22 on noncredible threats, subgames, subgame perfection and backward induction.