Why does a threat that would hurt the threatener fail?
Topics 11 to 15 asked who gains when several players choose. These nine go further: what changes when the moves come in turns (25), when players hold secrets (26), when they meet again (27), when they learn as they go (28), when a shared signal is allowed (29), when each chooses a route (30), when the question is how hard an equilibrium is to find (31), the one place where quantum physics changes a game's value (32), and then a market you design and attack yourself (33).
In topic 11 everyone chose at once. Most real decisions come in turns, and turns change what a plan has to be: it must be sensible at every point you might reach, not only the one you expect to.
A new firm is deciding whether to enter a market that one incumbent has to itself. The incumbent warns: if you come in, I will fight you. Fighting would hurt the incumbent too. It earns 0 if it fights and 2 if it simply shares the market, against 4 for keeping the market to itself. So ask what the incumbent would actually do once the entrant is in: it would share, because 2 is more than 0. A threat the threatener would not carry out is an empty threat, and an entrant who sees through it walks in.
The method is backward induction: go to the last decision in the game, work out what the player there would do, replace that decision by its outcome, and step back one move. It is how a chess player reasons about the final moves first, and it is the reason the order of moves matters so much: the same payoffs, with the moves made at once, give a different game.
The odd thing is that the entry game has 2 Nash equilibria, not one. One of them, "stay out, because the incumbent would fight", survives only because nobody ever gets to test the threat. Reinhard Selten's refinement, subgame perfection (1975), throws it out: an equilibrium must also be an equilibrium of every smaller game that starts partway through.
Write the game in normal form: the entrant picks a row, and the incumbent picks a plan for the node it only reaches after entry (one column per plan). Payoffs are (entrant, incumbent):
| Plan: accommodate | Plan: fight | |
|---|---|---|
| In | 2, 2 | -1, 0 |
| Out | 0, 4 | 0, 4 |
Checking each cell for a profitable deviation by either player leaves exactly 2 Nash equilibria: (In, accommodate) and (Out, fight). Rolling the tree back leaves 1: (In, accommodate).
Theorem (Kuhn, 1953). Every finite game of perfect information has a subgame-perfect equilibrium in pure strategies, and backward induction finds it. In the zero-sum case this is a result Zermelo stated for chess in 1913: from the first move, either one side can force a win or both can force at least a draw.
The saving is in the counting. A player with m decision nodes and two moves at each has 2m plans, so the normal form has that many rows. With m = 20 that is 1,048,576 plans. Folding the tree compares the two moves at each node once: 20 comparisons. The normal form is the honest definition; the tree is the way to compute.
Change any payoff, then fold the tree one step at a time. The page lists every Nash equilibrium of the one-shot form and which of them survive the rollback. Try making fighting worth more than sharing: the threat becomes credible and the second equilibrium becomes subgame-perfect too.
Solving a game by search Checkers has about 5 × 1020 positions. Schaeffer and colleagues showed in 2007 that with perfect play by both sides the game is a draw (Science 317, 1518 (2007)). They did it by searching forward from the opening and backward from a database of solved endings, which is backward induction pushed as far as a computer could push it. It is a weak solution: it gives a strategy that never loses, not a verdict on every position.
When the tree is too big to fold Go has far too many positions to fold. AlphaGo (Silver et al., Nature 529, 484 (2016)) searches a small part of the tree and replaces the unreachable leaves by a learned guess of who is winning. The principle is the one on this page, rollback from the leaves, with an estimate standing in for the leaves it cannot see.
This topic has no quantum link, and none is claimed. The first game on this site where quantum physics changes the answer is topic 32.
Check yourself
An incumbent firm threatens to fight any new entrant, but fighting would leave it worse off than sharing the market. What does backward induction conclude?
Backward induction starts at the last decision. The incumbent compares fighting with sharing and shares. The entrant, knowing that, enters. The threat is an empty one, which is why subgame perfection rules out the equilibrium that depends on it.