Grab the pennies on the very first move?

The centipede game

These rules and amounts come from a 1992 lab experiment. Moves 1, 3 and 5 belong to player A, moves 2, 4 and 6 to player B. Both want as much as possible for themselves, both see the whole game in advance and know the other one calculates too. How do you think A should play on the first move?

What real people do

The economist Robert Rosenthal invented the game in 1981, and in 1992 Richard McKelvey and Thomas Palfrey played it with students for real money. Logic promised that every game would end on the first move. About 5% did. Then researchers turned to chess players, who make a living by calculating ahead, and got two opposite results.

The most interesting part is in the last study. The same chess players also played a "race to 100": take turns adding numbers, and whoever says exactly 100 wins. There backward induction gives a simple winning strategy, and some players solved the game perfectly. Yet not one of these perfect logicians took the money on the first move of the centipede. They could reason from the end. They just didn't believe the opponent would reason the same way.

A game where logic never fails

Race to 21. The count starts at zero. You and a bot take turns adding 1, 2 or 3, and whoever says exactly 21 wins. There is no trust or pity here: one wins, the other loses. The bot reasons from the end. Do you think it matters who goes first?

What backward induction is

It is a way to solve a game from the end. First look at the last move: the choice there is obvious, because nothing comes after it. Knowing that, decide the move before it, then the one before that, and so on back to the first. The chain gives a single answer, and it is flawless if the game has an end, everyone sees everything, and everyone is sure the others will also reason all the way to the end.

That last condition is the weak link. The race to 21 doesn't need it: each position is a win or a loss whatever the opponent thinks. In the centipede everything depends on it: doubt the opponent's logic on any one of the six moves, and the chain falls apart.

A four-step recipe

1. Draw the game as a tree: each node is someone's move, each leaf is an outcome with every player's payoff.
2. Take the nodes followed only by leaves. The player who moves there will pick the leaf where he himself wins most.
3. Replace each such node with that leaf: the tree is now one move shorter.
4. Repeat until you reach the root. The choices made along the way are the solution of the game, in every situation, even those the game never reaches.

This finds what is now called a subgame perfect equilibrium. Reinhard Selten proposed the requirement in 1965: strategies must be best not only in the game that actually happens but in every part of it. That is why empty threats don't work: if carrying out a threat doesn't pay at the moment it is due, nobody will carry it out, and everyone knows it.

How much trust it takes for logic to lose

Imagine a crowd of B opponents. Most are flawless logicians: they take the money at the first chance, on move two. But a few are simply trusting and always pass. You are player A and don't know whom you've met. Compare two strategies: take the 40 cents at once, or pass all the way. How many trusting players must there be in the crowd for the second strategy to earn more?

The answer is tiny: it is enough for one opponent in 127 to be trusting. You risk pennies, 20 cents, and stand to win 25 dollars. Hence the power of doubt: to break the chain you don't have to think the opponent is a fool. It is enough not to be completely sure he is flawless.

Where it works and where it breaks

• Tic-tac-toeThere are only 5,478 different positions and 255,168 possible games. A computer goes through them from the end in an instant and sees: if neither side makes a mistake, it is a draw.
• Chess endgamesEndgame tablebases are built exactly this way: back from every checkmate position. In 2012 at Moscow State University the Lomonosov supercomputer covered every position with seven pieces and found a forced mate in 549 moves.
• Chess as a wholeIn 1913 Ernst Zermelo wrote one of the first papers on game theory, about chess. The theorem named after him is proved today by backward induction: in chess either White can force a win, or Black can, or each side can secure a draw. Which of the three, nobody knows yet: the tree is far too big.
• The ultimatum gameOne player proposes how to split a sum, the other accepts or refuses, and then neither gets anything. From the end: any non-zero share pays the responder, so the proposer should offer the minimum. In the first experiments by Güth, Schmittberger and Schwarze in 1982 and many since, people offer 40–50%, and offers of 20% or less are rejected about half the time.
• The chain-store paradoxReinhard Selten, 1978. A chain has stores in 20 towns, and a rival wants to enter each in turn. From the end: in the last town a price war no longer scares anyone, so the chain gives way there, and so in the one before… Selten himself wrote that in the chain's place he would ignore this conclusion and fight the rivals off.
• A prisoner's dilemma with a known endIf both know how many rounds there will be, cooperating in the last one makes no sense, so neither in the one before… Logic says defect from the very first round, though steady cooperation would give both more.

The key numbers of the race

Where 1 in 127 comes from

Aumann's theorem and its paradox

In 1995 Robert Aumann proved that if, in a game of perfect information, the players' rationality is common knowledge (everyone is rational, everyone knows that everyone is rational, everyone knows that everyone knows, and so on forever), the game ends exactly as backward induction says. So the logic of the centipede is flawless. The only question is whether such players exist.

And inside the reasoning itself sits a trap, taken apart in 1989 by the philosophers Philip Pettit and Robert Sugden. To decide whether to take on move one, A has to imagine what B will do on move two. But B only reaches move two if A passed, that is, did what a flawless logician never does. Why then should B believe that A will behave like a flawless logician from there on? Backward induction relies on belief in rationality exactly where that belief has already been refuted.