Backward induction is a way of solving problems that unfold in steps. Instead of starting at the beginning and guessing what to do, you start at the very last decision, work out the best choice there, and then step back one decision at a time. Each earlier choice is made knowing how every later choice will be made. When you reach the first decision, you have a complete plan: the best action at every point along the way.
The idea is simple enough to explain to a child playing tic-tac-toe ("if I go here, they will go there, and then I lose, so I won't go here"), but it sits at the center of some of the most important tools in modern economics, computer science and game theory. It is the method behind dynamic programming, the reasoning behind the "subgame perfect equilibrium" in game theory, and the engine that generated the huge chess endgame databases that now tell computers the perfect move in any position with seven or fewer pieces.
It is also famous for its paradoxes. In several well-known games, backward induction gives an answer that is mathematically airtight and yet strikes almost everyone as wrong, and real people in laboratory experiments routinely ignore it. Understanding both the power of the method and the places where it breaks down is one of the best ways to understand how economists and game theorists think about rational decision-making.
This article explains how backward induction works, where it came from, how it is used, and why it remains debated.
The core idea in plain terms
Many decisions are sequential: what you do now changes the situation you will face later. A job seeker who turns down an offer today keeps searching tomorrow. A chess player's move determines the position the opponent will face. A company that enters a market changes the choice facing the firm already there.
Sequential problems can be hard to think about from the front, because the best move now depends on everything that might happen afterward. Backward induction removes that difficulty by reversing the direction of reasoning:
- Go to the final decision point. At that point, nothing comes afterward, so the best choice depends only on the immediate payoff. Work it out.
- Step back to the second-to-last decision. You now know exactly what will happen at the final step, so the second-to-last decision is also just a comparison of known outcomes.
- Keep stepping back, each time replacing the "future" with the answer you already computed.
- When you reach the first decision, you have the optimal plan for the whole problem.
The trick is that a large, tangled, multi-stage problem is converted into a chain of small, single-stage problems. Each small problem is easy because the future has already been "solved."
Two assumptions are hiding inside this procedure. First, the problem must have an end: a final decision point from which to start. Second, the decision maker (or each player, in a game) is assumed to act optimally at every later stage. Both assumptions turn out to matter a great deal, and most of the controversy around backward induction concerns the second one.
A short history
Cayley and the secretary problem (1875)
According to the Wikipedia article on backward induction, the first person known to use the method was the British mathematician Arthur Cayley, who applied it in 1875 while working on what is now called the secretary problem, a classic question about when to stop searching and accept an option.
Zermelo, chess, and a historical correction (1913–1928)
In 1913 the German mathematician Ernst Zermelo published a paper, "Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels" ("On an application of set theory to the theory of the game of chess"), which is often described as the first known paper in game theory. It concerned finite two-player games in which both players see everything (perfect information). Applied to chess, the result says that either White can force a win, or Black can force a win, or both sides can force at least a draw.
For a long time, textbooks said Zermelo proved this using backward induction, and the method for solving game trees is still often called "Zermelo's algorithm." However, Ulrich Schwalbe and Paul Walker, who translated Zermelo's paper into English in 1997, re-examined it in a 2001 article in Games and Economic Behavior. They found that Zermelo's paper contained the basic idea but no formal statement of backward induction; his argument relied on the fact that a winning player need not repeat positions. According to their account, the first explicit use of backward induction in this setting came from László Kalmár in 1928, building on the work of Zermelo and Kőnig.
Von Neumann and Morgenstern (1944)
John von Neumann and Oskar Morgenstern's Theory of Games and Economic Behavior, published in 1944, is the book usually credited with founding game theory as a field. Among other things, it proposed solving two-person zero-sum games by working backward through the game.
Bellman and dynamic programming (1950s)
In the 1950s the American mathematician Richard Bellman developed dynamic programming, a general method for breaking an optimization problem that unfolds over time into simpler subproblems. His paper "On the Theory of Dynamic Programming" appeared in 1952 and his book Dynamic Programming in 1957. The key equation of the method, now called the Bellman equation, relies on his "principle of optimality": an optimal policy has the property that, whatever the starting state and first decision, the remaining decisions must also be optimal for the situation that results. For problems with a finite number of periods, the Bellman equation is solved by backward induction: specify the best policy for the last period, then use it to find the best policy for the period before, and so on.
Bellman also connected the idea back to games. According to the Wikipedia article on endgame tablebases, in 1965 he proposed building databases to solve chess and checkers endgames by working backward from positions where one player had been checkmated or stalemated.
Selten and subgame perfection (1960s–1978)
The German economist Reinhard Selten developed the concept of subgame perfect equilibrium, which formalizes backward induction for games, and later the "trembling hand" refinement (1975). In 1978 he also published the chain-store paradox, one of the best-known challenges to backward induction, discussed below.
The 1980s onward: paradoxes and experiments
Robert Rosenthal introduced the centipede game in 1981. During the 1980s and 1990s philosophers and economists including Ken Binmore (1987), Philip Pettit and Robert Sugden (1989), Cristina Bicchieri (1993) and Robert Aumann (1995) argued over what backward induction actually assumes about rationality and knowledge. In parallel, experimental economists began testing whether real people reason backward, with results that are discussed later in this article.
Example 1: When to accept a job offer
The Wikipedia article on backward induction gives a clean decision example from search theory, the branch of microeconomics that studies how people decide when to stop looking for something.
Suppose a person is looking for work over ten periods, numbered t = 1 through t = 10. In each period they receive exactly one offer. With equal probability it is a good job paying $100 per period or a bad job paying $44 per period. Once they accept a job, they keep it for all remaining periods. If they reject an offer, they earn nothing that period and get a new offer in the next. To keep things simple, there is no interest rate and each dollar is worth the same to the person.
Should they ever accept a bad job? Starting from the beginning is confusing. Starting from the end is easy.
- Period 10 (last period). There is no future. A good job pays $100 and a bad job pays $44; rejecting pays $0. Accept anything.
- Period 9. Accepting a good job pays $100 for two periods, or $200. Accepting a bad job pays $88. If they reject, they move to period 10, where (as just shown) they accept whatever comes. That is worth $100 or $44 with equal chance, an expected $72. Since $88 is more than $72, they should accept even a bad offer in period 9.
- Period 8. Accepting a bad job pays 3 × $44 = $132. Rejecting leads to period 9, where they accept anything: a good job would then pay $200 and a bad one $88, for an expected $144. Since $144 is more than $132, they should reject a bad offer in period 8.
Continuing backward in the same way, the article concludes that a bad offer should be accepted only in periods 9 and 10. (One more step shows the pattern: in period 7 a bad job is worth 4 × $44 = $176, while waiting is worth half of $300 plus half of the $144 continuation value, or $222, so the person waits.)
The structure of the answer is intuitive once you see it: when time is plentiful, it pays to be picky; when time is running out, it pays to settle. Backward induction tells you exactly where that switch happens. Search models of this kind are used to study shopping, job hunting and even marriage.
Example 2: A sequential game and subgame perfect equilibrium
Game trees and subgames
In game theory, sequential games are drawn as game trees (the "extensive form"). Each node is a decision point for one player, each branch is a possible action, and each endpoint ("terminal node") lists the payoffs to every player. A subgame is any part of the tree that starts at a single decision node and includes everything that follows it.
A Nash equilibrium is a set of strategies in which no player can do better by changing their own strategy alone. The trouble is that in sequential games, Nash equilibrium can allow strategies that include "threats" a player would never actually carry out. A subgame perfect equilibrium fixes this by requiring that the strategies form a Nash equilibrium in every subgame, including ones that are never reached in actual play. In finite games of perfect information, backward induction is exactly how such an equilibrium is found: start with the smallest subgames at the end of the tree, solve them, replace each with its solution, and work back to the root.
The Stanford Encyclopedia of Philosophy entry on game theory notes that this procedure applies to finite sequential games of perfect information, and that the resulting outcome need not be socially efficient. That is one motivation for mechanism design, the study of how to change the rules of a game so that rational play produces better results.
The movie example
The Wikipedia article illustrates this with a two-stage game. Two friends want to see a movie together, but they disagree about which: Player 1 prefers The Terminator and Player 2 prefers Joker. Player 1 buys a ticket first and announces the choice; then Player 2 buys a ticket. In a second stage, each decides whether to actually go or to stay home.
The stage-one payoffs (Player 1's payoff listed first) are:
- Both choose Joker: 3, 5
- Player 1 Joker, Player 2 Terminator: 0, 0
- Player 1 Terminator, Player 2 Joker: 1, 1
- Both choose Terminator: 5, 3
The stage-two payoffs are:
- Both go: 6, 6
- Player 1 goes, Player 2 stays home: 4, −2
- Player 1 stays home, Player 2 goes: −2, 4
- Both stay home: −2, −2
Working backward, the analyst first solves the second stage, then Player 2's ticket choice given Player 1's announcement, and finally Player 1's opening choice, which anticipates everything that follows. The article's solution is that Player 1 buys a Terminator ticket, Player 2 follows with a Terminator ticket, and both go, for total payoffs of (11, 9). The key insight is that moving first is an advantage: by committing, Player 1 can pick the coordinated outcome that suits them, knowing Player 2 will rather follow than end up apart.
Example 3: The entry game and non-credible threats
Backward induction is especially important in industrial organization, the economics of how firms compete. The standard illustration is the entry game, described in the Wikipedia article.
An incumbent firm has a monopoly. A potential competitor decides whether to enter the market. If it stays out, the incumbent keeps its high monopoly profits and the entrant gets nothing. If it enters, the incumbent chooses either to fight (for example, a price war that hurts both firms) or to accommodate (keep prices high and share the market).
This game has two Nash equilibria:
- Enter and accommodate. The entrant enters and the incumbent shares the market.
- Stay out, because the incumbent threatens to fight. If the entrant believes the threat, staying out is its best response, and since nobody enters, the incumbent never has to carry the threat out.
Backward induction eliminates the second equilibrium. Look at the last decision: once the entrant is already in the market, fighting hurts the incumbent too, so its best move is to accommodate. The threat to fight is not credible. A rational entrant who reasons backward sees this and enters. The only subgame perfect equilibrium is "enter and accommodate."
This is the general lesson of subgame perfection: it rules out equilibria that depend on threats or promises a player would not actually want to carry out when the moment arrived.
Example 4: Chess and retrograde analysis
In chess, reasoning backward from the end has its own name: retrograde analysis. The term covers two related activities.
In chess problems, retrograde analysis means deducing which moves must have been played to reach a given position. A whole genre of puzzles ("retros") requires this, for example to establish whether castling or an en passant capture is still legal.
In computer chess, the same backward logic is used to build endgame tablebases: databases that store the perfect result and best move for every possible position with a small number of pieces. The program starts from positions that are already checkmate or stalemate, then finds every position one move earlier that leads to them, then every position one move before that, and so on, until every legal position with that set of pieces is classified. The timeline, according to the Wikipedia article on endgame tablebases, runs roughly as follows:
- 1965: Richard Bellman proposes the approach for chess and checkers endgames.
- 1970: Thomas Ströhlein's doctoral thesis analyzes several simple endgames, including king and queen against king.
- 1977: Ken Thompson's tablebase for king and queen against king and rook is used in a match against Grandmaster Walter Browne.
- 1991: Lewis Stiller's thesis covers some six-piece endgames.
- 2005: Tablebases for all positions with up to six pieces (including both kings) are completed; the widely used Nalimov format is named after Eugene Nalimov.
- 2012: The Lomonosov seven-piece tablebases are completed on a supercomputer, requiring about 140 terabytes.
- 2018: Ronald de Man and Bojun Guo release complete seven-piece Syzygy tablebases that take about 18.4 terabytes.
These databases revealed positions that no human would have guessed could be won, including a seven-piece position found in 2012 that requires 549 moves to force checkmate with perfect play. This is backward induction at a massive scale, and it shows the method's great strength: when a problem is finite and fully known, it gives exact, provably correct answers.
It also shows the method's main practical limit. The full game of chess is far too large to solve this way, because the number of positions explodes. Backward induction is perfectly correct in principle, but it requires visiting every relevant position, which is often impossible in practice.
The paradoxes of backward induction
The ultimatum game
In the ultimatum game, Player 1 proposes how to split a sum of money, say one dollar. Player 2 either accepts, in which case both receive the proposed amounts, or rejects, in which case both get nothing.
Backward induction says: at the last step, Player 2 compares a positive amount with zero and should accept any positive offer. Knowing this, Player 1 should offer the smallest possible amount. This is the unique subgame perfect equilibrium.
Real people do not behave this way. Proposers rarely offer the minimum, and responders often reject offers they consider unfair. The economist Colin Camerer, reviewing the evidence in the Journal of Economic Perspectives in 1997, observed that responders reject offers of less than 20 percent of the total about half the time, even though rejecting leaves them with nothing. Responders appear to care about fairness, or about the wider effects of accepting insulting offers, and not only about the money in front of them.
The centipede game
The centipede game, introduced by Robert Rosenthal in 1981, is the most famous illustration of how backward induction can produce a result that seems absurd. Two players take turns. At each turn, the player can either take a slightly larger share of a pot, ending the game, or pass, which makes the pot grow. Rosenthal's original version had 100 rounds, which gave the game its name.
Reason backward from the final round: the last mover should take, since passing gains nothing. So the player before should take one step earlier, before the other player can take. Repeating this argument all the way back, the first player should take at the very first opportunity. That is the unique subgame perfect equilibrium, even though both players would be far better off if they passed many times.
In experiments, people almost never take immediately. They typically pass for several rounds and then take, and few cooperate all the way to the end. Higher stakes move behavior somewhat closer to the prediction but do not reach it. Richard McKelvey and Thomas Palfrey's influential 1992 study found the data could be explained if a small share of players (around 5 percent in their model) were altruistic, which makes passing a sensible gamble for everyone else.
An interesting twist concerns chess players. In a 2009 study, Ignacio Palacios-Huerta and Oscar Volij reported that expert chess players stopped earlier than students, with the likelihood of continuing falling as chess rating rose, and that all the Grandmasters in their study stopped at the first opportunity. A 2010 study by Steven Levitt, John List and Sally Sadoff got strongly contradictory results: none of the sixteen Grandmasters they observed stopped at the first node. The question of how much expertise brings people closer to backward-induction play is still open.
Selten's chain-store paradox (1978)
Reinhard Selten's chain-store paradox extends the entry game over many towns. A chain store (the monopolist) operates in 20 towns. One at a time, a potential competitor in each town decides whether to enter. If a competitor stays out, it earns 1 and the chain earns 5. If it enters, the chain can cooperate (both earn 2) or be aggressive (both earn 0).
Backward induction says: in the 20th town there is no future to protect, so the chain cooperates if the competitor enters, and so the competitor enters. Since the last town's outcome is now fixed, the same reasoning applies in town 19, then 18, and so on back to the first. Every competitor enters, the chain always cooperates, and the chain earns 2 × 20 = 40.
Yet intuition says the chain should fight early to build a reputation for toughness and scare off later entrants. The Wikipedia article gives an example: if the chain is aggressive in the first 17 towns and cooperates in the last 3, and all 17 early competitors are deterred, the chain earns 91; even if 10 of them enter anyway, it earns 41, which still beats 40. This "deterrence" strategy is not a subgame perfect equilibrium, because it rests on a threat the chain would not want to carry out if put to the test. The paradox is that the "rational" answer seems to be the worse strategy.
One response is Selten's own distinction between levels of decision making (routine, imagination and reasoning), which suggests that deterrence can be a sensible way for people to decide even if it is not strictly rational in game-theoretic terms. Another response, as the article summarizes, is that if competitors assign even a small probability to the monopolist being the kind of player who fights out of spite, early aggression can become optimal, because it raises the chance that later competitors believe the monopolist is that type. This idea, that a little uncertainty about the other player's type can overturn the backward-induction result, became central to the economics of reputation.
The unexpected hanging
The unexpected hanging paradox is often mentioned alongside backward induction. A judge tells a prisoner he will be hanged on one weekday next week, and that the day will be a surprise. The prisoner reasons: it cannot be Friday, because if he were alive on Thursday evening he would know; with Friday ruled out, it cannot be Thursday either; and so on, until he concludes he cannot be hanged at all. Then he is hanged on Wednesday, completely surprised.
The Wikipedia article notes that the prisoner uses backward induction to reach a false conclusion, but argues that this does not undermine backward induction as used in game theory, because the paradox depends on the assumption that a person doing backward induction can be surprised, which backward induction theory itself does not assume.
What backward induction assumes about rationality
Common knowledge of rationality
For backward induction to give the right prediction in a game, it is not enough for each player to be rational. Each player must believe the others are rational, believe that the others believe they are rational, and so on without end. In the jargon, rationality must be common knowledge. Robert Aumann set out this connection formally in a 1995 paper in Games and Economic Behavior, "Backward induction and common knowledge of rationality."
The paradox of off-path reasoning
This requirement leads to a deep puzzle, discussed in the Stanford Encyclopedia of Philosophy entry on game theory. To justify the first player's choice to take immediately in the centipede game, we must say what the second player would do if the first player passed. But if the first player passed, the second player has just watched a supposedly rational opponent do something that backward induction says is irrational. Why should the second player still believe the opponent is rational and will take at the next opportunity? Cristina Bicchieri (1993), Ken Binmore (1987) and Philip Pettit and Robert Sugden (1989) all raised versions of this problem.
One standard way around it is Selten's 1975 "trembling hand" idea: players intend to play optimally but occasionally make small mistakes. An unexpected move can then be read as an accidental slip rather than proof of irrationality, and the rest of the backward-induction logic survives. Herbert Gintis has argued that the paradox depends on each player reasoning from the premise that the other is rational, and that dropping this premise removes the paradox. Other game theorists emphasize that players must learn to play equilibria through experience rather than deducing them in one step.
Ties and imperfect information
There are also technical limits. Backward induction works cleanly in finite games of perfect information when no player is ever indifferent between options. If there are ties, it can produce more than one solution. It can be applied to some games where players do not see every earlier move, but it is not a general method for such games, and it is hard to apply when players do not know other players' payoffs or past actions.
Limited backward induction: how real people reason
Because experimental subjects so often deviate from full backward induction, researchers have developed the idea of limited backward induction: people look ahead only a few steps rather than all the way to the end. According to the Wikipedia article, its effects are stronger in longer games and in later periods of a game.
Researchers have offered three broad explanations for deviations from backward-induction predictions: social preferences such as fairness, cognitive limits such as limited foresight, and cultural differences. Fairness is the most common explanation, but some models suggest that limited backward induction is the dominant factor in certain games. Several findings support the cognitive account:
- Public goods games with teams. In a 2018 study in the Journal of Public Economics, Caleb Cox and Brock Stoddard found that contributions were higher early in a repeated game and fell toward the end, with free-riding increasing as the end approached, consistent with players seeing only a limited way ahead.
- Race games. In games where players take turns choosing numbers to reach a target, researchers found that when a small intermediate prize was added, most players focused on reasoning toward that prize rather than the main goal, suggesting they had not fully reasoned backward from the end.
- Television game shows. A 2022 study by Bouke Klein Teeselink and coauthors titled "High-Stakes Failures of Backward Induction" examined the Showcase Showdown on the US game show The Price Is Right and found that contestants often deviated from optimal play, suggesting many looked only one stage ahead even with real money at stake.
The upshot is that backward induction is best understood as a benchmark: it describes what perfectly rational, perfectly informed players would do. Real behavior can be measured against it, and the gap tells researchers something about how people actually think.
Where backward induction is used
Despite its paradoxes as a description of human behavior, backward induction is an indispensable tool in many fields:
- Economics. Dynamic programming, solved by backward induction in finite-horizon problems, is a standard method in macroeconomics, finance and labor economics, where economists often call it a "recursive method." According to the Wikipedia article on the Bellman equation, the first known economic application was by Martin Beckmann and Richard Muth on inventory problems (1954); Robert Merton's 1973 intertemporal capital asset pricing model is a famous example; and the 1989 textbook by Nancy Stokey, Robert Lucas and Edward Prescott spread these methods throughout economic theory.
- Industrial organization. Entry deterrence, pricing and investment decisions are studied by asking which threats and commitments are credible, which is exactly what subgame perfection tests.
- Search and stopping problems. The job-offer example above generalizes to questions about when to sell an asset, when to stop searching for a house, or how long to keep looking for a partner.
- Computer science and artificial intelligence. Solving game trees in game-playing programs, constructing endgame databases, and planning in sequential decision problems all rely on working backward from final outcomes. In logic and automated reasoning, the related idea of backward chaining starts from a goal and works back to the facts that would establish it.
- Bargaining and politics. Models of negotiation in which offers alternate, or in which one side moves first, are commonly solved by backward induction to see who has the stronger position.
How to apply backward induction: a step-by-step method
For a finite problem in which you know the payoffs:
- Map the problem. List the decisions in order, who makes each one, what options exist, and what the final payoffs are. In a game, draw the tree.
- Find the last decisions. Identify every decision point whose options lead directly to final outcomes.
- Solve them. At each such point, choose the option with the highest payoff for whoever is deciding. If there is uncertainty, compare expected values, as in the job example.
- Replace and repeat. Replace each solved decision point with the payoff it produces, then treat the previous decisions as the new "last" decisions.
- Continue to the start. The choices you have recorded at each point form the complete optimal plan, or, in a game, the subgame perfect equilibrium.
- Check the assumptions. Ask whether the problem really has a fixed end, whether all players know the payoffs, whether there are ties, and whether it is realistic to assume every player will reason the same way. If not, treat the result as a benchmark, not a prediction.
Common mistakes include solving only the path you expect to be played (backward induction requires solving every branch, including those that will not be reached), forgetting that payoffs accumulate over time (as with the job that lasts several periods), and applying the method to problems with no defined end, where there is no last step to start from.
Frequently asked questions
Is backward induction the same as dynamic programming? Not exactly, but they are closely linked. Dynamic programming is a broad method for solving problems that unfold over time by breaking them into subproblems. For problems with a finite number of stages, the standard way to solve the dynamic programming equations is backward induction.
Who invented backward induction? No single person. Arthur Cayley used it in 1875 on the secretary problem. Zermelo's 1913 chess paper contained the basic idea, and László Kalmár gave the first explicit version in game theory in 1928. Von Neumann and Morgenstern (1944), Bellman (1950s) and Selten (1960s–1970s) turned it into the tools used today.
What is a subgame perfect equilibrium? It is a set of strategies that forms a Nash equilibrium in every part of a game, including parts that are never actually reached. In finite games of perfect information, backward induction finds it. Its main job is to rule out non-credible threats.
Why do people not follow backward induction in experiments? Researchers point to three kinds of explanation: people care about fairness and other people's payoffs, people have limited foresight and do not reason all the way to the end, and cultural norms shape expectations. Doubt about whether the other player will act "rationally" also makes cooperating early a reasonable gamble.
Does backward induction work in infinite games? Not directly, because there is no final step to start from. That is why, for example, an infinitely repeated game can sustain cooperation that backward induction rules out in the finite version.
Can backward induction solve chess? In principle, yes, because chess with standard drawing rules is a finite game of perfect information. In practice, the game is far too large. Backward induction has fully solved every position with seven or fewer pieces on the board, using enormous computer databases.
Sources and further reading
- Wikipedia, "Backward induction": https://en.wikipedia.org/wiki/Backward_induction
- Stanford Encyclopedia of Philosophy, "Game Theory": https://plato.stanford.edu/entries/game-theory/
- Wikipedia, "Centipede game": https://en.wikipedia.org/wiki/Centipede_game
- Wikipedia, "Chainstore paradox": https://en.wikipedia.org/wiki/Chainstore_paradox
- Wikipedia, "Zermelo's theorem (game theory)": https://en.wikipedia.org/wiki/Zermelo%27s_theorem_(game_theory)
- Wikipedia, "Retrograde analysis": https://en.wikipedia.org/wiki/Retrograde_analysis
- Wikipedia, "Bellman equation": https://en.wikipedia.org/wiki/Bellman_equation
- Wikipedia, "Endgame tablebase": https://en.wikipedia.org/wiki/Endgame_tablebase