Loading article…
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.[1] 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.[2]
In dynamic programming, a method of mathematical optimization, backward induction is used for solving the Bellman equation.[3][4] 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.[5] 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.[6][7]
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 .
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.
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.[8]
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.[9]
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.
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.
For this example, payoffs are added across different stages. The game is a perfect information game. The normal-form matrices for these games are:
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:
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.[10]
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.[11]
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."[12]
While backward induction assuming formal rationality would predict that a responder would accept any offer greater than zero, responders in reality are not formally rational players and therefore often seem to care more about offer 'fairness' or perhaps other anticipations of indirect or external effects rather than immediate potential monetary gains.
A dynamic game in which the players are an incumbent firm in an industry and a potential entrant to that industry is to be considered. As it stands, the incumbent has a monopoly over the industry and does not want to lose some of its market share to the entrant. If the entrant chooses not to enter, the payoff to the incumbent is high (it maintains its monopoly) and the entrant neither loses nor gains (its payoff is zero). If the entrant enters, the incumbent can "fight" or "accommodate" the entrant. It will fight by lowering its price, running the entrant out of business (and incurring exit costs—a negative payoff) and damaging its own profits. If it accommodates the entrant it will lose some of its sales, but a high price will be maintained and it will receive greater profits than by lowering its price (but lower than monopoly profits).
既存企業が参入企業を前提として譲歩する場合、参入企業にとって最善の対応は参入すること（そして利益を得ること）である。したがって、参入企業が参入し、既存企業が参入時に譲歩するという戦略プロファイルは、後方帰納法と整合するナッシュ均衡である。しかし、既存企業が戦うつもりであれば、参入企業にとって最善の対応は参入しないことであり、参入企業が参入しない場合は、参入企業が参入するという仮説的なケースで既存企業がどのような選択をしても問題ない。したがって、既存企業が参入企業を前提として戦うが、参入企業が参入しない場合の戦略プロファイルもナッシュ均衡である。しかし、参入企業が方針を転換して参入した場合、既存企業にとって最善の対応は譲歩することである。戦うという脅威は信憑性がない。したがって、この2番目のナッシュ均衡は後方帰納法によって排除できる。
各意思決定プロセス（サブゲーム）においてナッシュ均衡を見つけることは、完全なサブゲーム均衡を構成する。したがって、完全なサブゲーム均衡を示すこれらの戦略プロファイルは、新規参入者を「脅す」ために用いられるような、信じがたい脅しなどの行動の可能性を排除する。既存企業が新規参入者との価格競争を始めると脅す場合、それは独占価格から新規参入者の価格よりわずかに低い価格まで自社の価格を引き下げると脅すことになるが、新規参入者が価格競争は両者にとって損失となるため実際には起こらないと知っていれば、これは非現実的で信じがたい脅しとなる。最適ではない均衡や実行不可能な均衡を含む可能性のある単一エージェント最適化とは異なり、完全なサブゲーム均衡は他のプレイヤーの行動を考慮し、どのプレイヤーも誤ってサブゲームに到達しないことを保証する。この場合、完全なサブゲーム均衡をもたらす後方帰納法は、新規参入者が戦略プロファイルにおける最良対応ではないと知って、既存企業の脅しに納得しないことを保証する。[ 13 ]
予期せぬ吊り下げのパラドックスは、後方帰納法に関連するパラドックスである。このパラドックスに登場する囚人は、後方帰納法を用いて誤った結論に達する。この問題の説明は、後方帰納法を行っている人物を驚かせることが可能であるという前提に基づいている。しかし、後方帰納法の数学理論はこの前提を置いていないため、このパラドックスは後方帰納法の理論結果を疑うものではない。
Backward induction works only if both players are rational, i.e., always select an action that maximizes their payoff. However, rationality is not enough: each player should also believe that all other players are rational. Even this is not enough: each player should believe that all other players know that all other players are rational, and so on, ad infinitum. In other words, rationality should be common knowledge.[14]
Limited backward induction is a deviation from fully rational backward induction. It involves enacting the regular process of backward induction without perfect foresight. Theoretically, this occurs when one or more players have limited foresight and cannot perform backward induction through all terminal nodes.[15] Limited backward induction plays a much larger role in longer games as the effects of limited backward induction are more potent in later periods of games.
Experiments have shown that in sequential bargaining games, such as the Centipede game, subjects deviate from theoretical predictions and instead engage in limited backward induction. This deviation occurs as a result of bounded rationality, where players can only perfectly see a few stages ahead.[16] This allows for unpredictability in decisions and inefficiency in finding and achieving subgame perfect Nash equilibria.
There are three broad hypotheses for this phenomenon:
Violations of backward induction is predominantly attributed to the presence of social factors. However, data-driven model predictions for sequential bargaining games (using the cognitive hierarchy model) have highlighted that in some games the presence of limited backward induction can play a dominant role.[17]
Within repeated public goods games, team behavior is impacted by limited backward induction; where it is evident that team members' initial contributions are higher than contributions towards the end. Limited backward induction also influences how regularly free-riding occurs within a team's public goods game. Early on, when the effects of limited backward induction are low, free riding is less frequent, whilst towards the end, when effects are high, free-riding becomes more frequent.[18]
Limited backward induction has also been tested for within a variant of the race game. In the game, players would sequentially choose integers inside a range and sum their choices until a target number is reached. Hitting the target earns that player a prize; the other loses. Partway through a series of games, a small prize was introduced. The majority of players then performed limited backward induction, as they solved for the small prize rather than for the original prize. Only a small fraction of players considered both prizes at the start.[19]
Most tests of backward induction are based on experiments, in which participants are only to a small extent incentivized to perform the task well, if at all. However, violations of backward induction also appear to be common in high-stakes environments. A large-scale analysis of the American television game show The Price Is Right, for example, provides evidence of limited foresight. In every episode, contestants play the Showcase Showdown, a sequential game of perfect information for which the optimal strategy can be found through backward induction. The frequent and systematic deviations from optimal behavior suggest that a sizable proportion of the contestants fail to properly backward induct and myopically consider the next stage of the game only.[20]
