Backward induction is the process of determining a sequence of optimal choices by reasoning from the endpoint of a problem or situation back to its beginning using individual events or actions. Backward induction involves examining the final point in a series of decisions and identifying the optimal process or action required to arrive at that point. This process continues backward until the best action for every possible point along the sequence is determined. Backward induction was first utilized in 1875 by Arthur Cayley, who discovered the method while attempting to solve the secretary problem.
In dynamic programming, a method of mathematical optimization, backward induction is used for solving the Bellman equation.Mario Miranda and Paul Fackler, "Applied Computational Economics and Finance", Section 7.3.1, page 164. MIT Press, 2002. In the related fields of automated planning and scheduling and automated theorem proving, the method is called backward search or backward chaining. In chess, it is called retrograde analysis.
In game theory, a variant of backward induction is used to compute subgame perfect equilibria in sequential games.Drew Fudenberg and Jean Tirole, "Game Theory", Section 3.5, page 92. MIT Press, 1991. The difference is that optimization problems involve one decision maker who chooses what to do at each point of time. In contrast, game theory problems involve the interacting decision of several players. In this situation, it may still be possible to apply a generalization of backward induction, since it may be possible to determine what the second-to-last player will do by predicting what the last player will do in each situation, and so on. This variant of backward induction has been used to solve formal games from the beginning of game theory. John von Neumann and Oskar Morgenstern suggested solving zero-sum, two-person formal games through this method in their Theory of Games and Economic Behaviour (1944), the book which established game theory as a field of study.
Decision-making example Optimal-stopping problem Consider a person evaluating potential employment opportunities for the next ten years, denoted as times . At each , they may encounter a choice between two job options: a 'good' job offering a salary of or a 'bad' job offering a salary of . Each job type has an equal probability of being offered. Upon accepting a job, the individual will maintain that particular job for the entire remainder of the ten-year duration.
This scenario is simplified by assuming that the individual's entire concern is their total expected monetary earnings, without any variable preferences for earnings across different periods. In economic terms, this is a scenario with an implicit interest rate of zero and a constant marginal utility of money.
Whether the person in question should accept a 'bad' job can be decided by reasoning backwards from time . At , the total earnings from accepting a 'good' job is ; the value of accepting a 'bad' job is ; the total earnings from rejecting the available job is . Therefore, if they are still unemployed in the last period, they should accept whatever job they are offered at that time for greater income. At , the total earnings from accepting a 'good' job is because that job will last for two years. The total earnings from accepting a 'bad' job is . The total expected earnings from rejecting a job offer are now plus the value of the next job offer, which will either be with 1/2 probability or with 1/2 probability, for an average ('expected') value of . Therefore, the job available at should be accepted. At , the total earnings from accepting a 'good' job is ; the total earnings from accepting a 'bad' job is . The total expected earnings from rejecting a job offer is now plus the total expected earnings from waiting for a job offer at . As previously concluded, any offer at should be accepted and the expected value of doing so is . Therefore, at , total expected earnings are higher if the person waits for the next offer rather than accepting a 'bad' job.
By continuing to work backwards, it can be verified that a 'bad' offer should only be accepted if the person is still unemployed at or ; a bad offer should be rejected at any time up to and including . Generalizing this example intuitively, it corresponds to the principle that if one expects to work in a job for a long time, it is worth picking carefully.
A dynamic optimization problem of this kind is called an optimal stopping problem because the issue at hand is when to stop waiting for a better offer. Search theory is a field of microeconomics that applies models of this type to matters such as shopping, job searches, and marriage.
Game theory In game theory, backward induction is a solution methodology that follows from applying sequential rationality to identify an optimal action for each information set in a given game tree. It develops the implications of rationality via individual information sets in the extensive-form representation of a game.
In order to solve for a subgame perfect equilibrium with backwards induction, the game should be written out in extensive form and then divided into subgames. Starting with the subgame furthest from the initial node, or starting point, the expected payoffs listed for this subgame are weighed, and a rational player will select the option with the higher payoff for themselves. The highest payoff vector is selected and marked. To solve for the subgame perfect equilibrium, one should continually work backwards from subgame to subgame until the starting point is reached. As this process progresses, the initial extensive form game will become shorter and shorter. The marked path of vectors is the subgame perfect equilibrium.
Multi-stage game The application of backward induction in game theory can be demonstrated with a simple example. Consider a multi-stage game involving two players planning to go to a movie.
Player 1 wants to watch The Terminator, and Player 2 wants to watch Joker. Player 1 will buy a ticket first and tell Player 2 about her choice. Next, Player 2 will buy his ticket.
Once they both observe the choices, the second stage begins. In the second stage, players choose whether to go to the movie or stay home.
As in the first stage, Player 1 chooses whether to go to the movie first. After observing Player 1's choice, Player 2 makes his choice.
For this example, payoffs are added across different stages. The game is a perfect information game. The normal-form matrices for these games are:
Stage 1 Joker Terminator Joker 3, 5 0, 0 Terminator 1, 1 5, 3
Stage 2 Go to Movie Stay Home Go to Movie 6, 6 4, -2 Stay Home -2, 4 -2, -2
The extensive form of this multi-stage game can be seen to the right. The steps for solving this game with backward induction are as follows: Analysis starts from the final nodes. Player 2 will observe 8 subgames from the final nodes to choose "go to movie" or "stay home". Player 2 would make 8 possible comparisons in total, choosing the option with the highest payoff in each. For example, considering the first subgame, Player 2's payoff of 11 for "go to movie" is higher than his payoff of 7 for "stay at home." Player 2 would therefore choose "go to movie." The method continues for every subgame. Once Player 2's optimal decisions have been determined (bolded green lines in the extensive form diagram), analysis starts for Player 1's decisions in her 4 subgames. The process is similar to step 2, comparing Player 1's payoffs in order to anticipate her choices. Subgames that would not be chosen by Player 2 in the previous step are no longer considered because they are ruled out by the assumption of rational play. For example, in the first subgame, the choice "go to movie" offers a payoff of 9 since the decision tree terminates at the reward (9, 11), considering Player 2's previously established choice. Meanwhile, "stay home" offers a payoff of 1 since it ends at (1, 9), so Player 1 would choose "go to movie." The process repeats for each player until the initial node is reached. For example, Player 2 would choose "Joker" for the first subgame in the next iteration because a payoff of 11 ending in (9, 11) is greater than "Terminator" with a payoff of 6 at (6, 6). Player 1, at the initial node, would select "Terminator" because it offers a higher payoff of 11 at (11, 9) than Joker, which has a reward of 9 at (9, 11). To identify a subgame perfect equilibrium, one needs to identify a route that selects an optimal subgame at each information set. In this example, Player 1 chooses "Terminator" and Player 2 also chooses "Terminator." Then they both choose "go to movie." The subgame perfect equilibrium leads to a payoff of (11,9).
Limitations Backward induction can be applied to only limited classes of games. The procedure is well-defined for any game of perfect information with no ties of utility. It is also well-defined and meaningful for games of perfect information with ties. However, in such cases it leads to more than one perfect strategy. The procedure can be applied to some games with nontrivial information sets, but it is not applicable in general. It is best suited to solve games with perfect information. If all players are not aware of the other players' actions and payoffs at each decision node, then backward induction is not so easily applied.
Ultimatum game A second example demonstrates that even in games that formally allow for backward induction in theory, it may not accurately predict empirical game play in practice. This example of an asymmetric game consists of two players: Player 1 proposes to split a dollar with Player 2, which Player 2 then accepts or rejects. This is called the ultimatum game. Player 1 acts first by splitting the dollar however they see fit. Next, Player 2 either accepts the portion they have been offered by Player 1 or rejects the split. If Player 2 accepts the split, then both Player 1 and Player 2 get the payoffs matching that split. If Player 2 decides to reject Player 1's offer, then both players get nothing. In other words, Player 2 has veto power over Player 1's proposed allocation, but applying the veto eliminates any reward for both players.
Considering the choice and response of Player 2 given any arbitrary proposal by Player 1, formal rationality prescribes that Player 2 would accept any payoff that is greater than or equal to $0. Accordingly, by backward induction Player 1 ought to propose giving Player 2 as little as possible in order to gain the largest portion of the split. Player 1 giving Player 2 the smallest unit of money and keeping the rest for themselves is the unique subgame-perfect equilibrium. The ultimatum game does have several other Nash Equilibria which are not subgame perfect and therefore do not arise via backward induction.
The ultimatum game is a theoretical illustration of the usefulness of backward induction when considering infinite games, but the ultimatum games theoretically predicted results do not match empirical observation. Experimental evidence has shown that a proposer, Player 1, very rarely offers $0 and the responder, Player 2, sometimes rejects offers greater than $0. What is deemed acceptable by Player 2 varies with context. The pressure or presence of other players and external implications can mean that the game's formal model cannot necessarily predict what a real person will choose. According to Colin Camerer, an American behavioral economist, Player 2 "rejects offers of less than 20 percent of X about half the time, even though they end up with nothing."