This article's tone or style may not reflect the encyclopedic tone used on Wikipedia. See Wikipedia's guide to writing better articles for suggestions.(September 2023) (Learn how and when to remove this message)
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 most 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 (i.e. for every possible information set) 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 a method 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 a method 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, whereas game theory problems involve the decisions of several players interacting. In this situation it may still be possible to apply a generalization of backward induction, since by anticipating what the last player will do in each situation, it may be possible to determine what the second-to-last player will do, and so on. This variant of backward induction has been used to solve formal games from the very beginning of game theory. John von Neumann and Oskar Morgenstern suggested solving zero-sum, two-person formal games by this method in their Theory of Games and Economic Behaviour (1944), the book which established game theory as a field of study.[6][7]
^"Non-credible threats, subgame perfect equilibrium and backward induction", Game Theory, Cambridge University Press, pp. 317–332, 2012-05-31, retrieved 2024-04-04
^Rust, John (9 September 2016). Dynamic Programming. The New Palgrave Dictionary of Economics: Palgrave Macmillan. ISBN 978-1-349-95121-5.
^Adda, Jerome; Cooper, Russell W. (2003-08-29). Dynamic Economics: Quantitative Methods and Applications. MIT Press. ISBN 978-0-262-01201-0.
^Mario Miranda and Paul Fackler, "Applied Computational Economics and Finance", Section 7.3.1, page 164. MIT Press, 2002.
^Drew Fudenberg and Jean Tirole, "Game Theory", Section 3.5, page 92. MIT Press, 1991.
^MacQuarrie, John. "4, Fundamentals". Mathematics and Chess. University of St Andrews. Retrieved 2023-11-25.
^von Neumann, John; Morgenstern, Oskar (1953). "Section 15.3.1.". Theory of Games and Economic Behavior (Third ed.). Princeton University Press.
and 23 Related for: Backward induction information
Backwardinduction is the process of determining a sequence of optimal choices by reasoning from the endpoint of a problem or situation back to its beginning...
realistic. In dynamic games, backwardinduction can be used to eliminate unrealistic Nash equilibria. Backwardinduction assumes that players are rational...
Word-sense inductionBackwardinduction in game theory and economics Induced representation, in representation theory Mathematical induction, a method...
determining subgame perfect equilibria in the case of a finite game is backwardinduction. Here one first considers the last actions of the game and determines...
(simpler) subgames to find a solution to the game, in a process called backwardinduction. In chess, it is called retrograde analysis, and it is used to generate...
introductory game theory courses and texts to highlight the concept of backwardinduction and the iterated elimination of dominated strategies, which show a...
{\displaystyle X} . Muddy children puzzle can also be solved using backwardinduction from game theory. Muddy children puzzle can be represented as an extensive...
make, where a "deterrence strategy" appears optimal instead of the backwardinduction strategy of standard game theory reasoning. The paradox was first...
complete game tree can be generated, a deterministic algorithm, such as backwardinduction or retrograde analysis can be used. Randomized algorithms and minmax...
perfect information, a subgame perfect equilibrium can be found by backwardinduction. Simultaneous game Subgame perfection Sequential auction Brocas; Carrillo;...
perfect information for which the equilibrium can be found through backwardinduction. Several papers have solved the optimal strategy for particular spin...
rule). Each of these variations ends in win, loss or draw. By working backward from the end one can determine whether there is a forced win, the position...
C i ( q i ) {\displaystyle C_{i}(q_{i})} . The model is solved by backwardinduction. The leader considers what the best response of the follower is, i...
any quantity of capital at any previous time can be calculated by backwardinduction using the Bellman equation. In this problem, for each t = 0 , 1 ,...
decision tree. To solve any extensive form game, backwardinduction must be used. It involves working backward up the game tree to determine what a rational...
stage game equilibrium in each round. This can be deduced through backwardinduction. The unique stage game Nash equilibrium must be played in the last...
physics – Idea of connecting all of physics into one set of equations Backwardinduction – Process of reasoning backwards in sequence Metaheuristic – Optimization...
explained below. When solving dynamic optimization problems by numerical backwardinduction, the objective function must be computed for each combination of values...
the hypothetical physical versions of quantum computing systems. Backwardinduction – Process of reasoning backwards in sequence Content-addressable memory –...
solution. In value iteration (Bellman 1957), which is also called backwardinduction, the π {\displaystyle \pi } function is not used; instead, the value...
find viable strategies. In dynamic games with complete information, backwardinduction is the solution concept, which eliminates non-credible threats as...
Global Information