Global Information Lookup Global Information

Backward induction information


Backward induction is the process of determining a sequence of optimal choices by reasoning from the end point of a problem or situation back to its beginning via individual events or actions (point by point).[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 Behavior (1944), the book which established game theory as a field of study.[6][7]

  1. ^ "Non-credible threats, subgame perfect equilibrium and backward induction", Game Theory, Cambridge University Press, pp. 317–332, 2012-05-31, retrieved 2024-04-04
  2. ^ Rust, John (9 September 2016). Dynamic Programming. The New Palgrave Dictionary of Economics: Palgrave Macmillan. ISBN 978-1-349-95121-5.
  3. ^ Adda, Jerome; Cooper, Russell W. (2003-08-29). Dynamic Economics: Quantitative Methods and Applications. MIT Press. ISBN 978-0-262-01201-0.
  4. ^ Mario Miranda and Paul Fackler, "Applied Computational Economics and Finance", Section 7.3.1, page 164. MIT Press, 2002.
  5. ^ Drew Fudenberg and Jean Tirole, "Game Theory", Section 3.5, page 92. MIT Press, 1991.
  6. ^ MacQuarrie, John. "4, Fundamentals". Mathematics and Chess. University of St Andrews. Retrieved 2023-11-25.
  7. ^ 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

Request time (Page generated in 0.9193 seconds.)

Backward induction

Last Update:

Backward induction is the process of determining a sequence of optimal choices by reasoning from the end point of a problem or situation back to its beginning...

Word Count : 3488

Solution concept

Last Update:

realistic. In dynamic games, backward induction can be used to eliminate unrealistic Nash equilibria. Backward induction assumes that players are rational...

Word Count : 1626

Induction

Last Update:

Word-sense induction Backward induction in game theory and economics Induced representation, in representation theory Mathematical induction, a method...

Word Count : 205

Mathematical induction

Last Update:

Well-Ordering" (PDF). York University. Retrieved 28 May 2023. "Forward-Backward Induction | Brilliant Math & Science Wiki". brilliant.org. Retrieved 23 October...

Word Count : 6860

Subgame perfect equilibrium

Last Update:

determining subgame perfect equilibria in the case of a finite game is backward induction. Here one first considers the last actions of the game and determines...

Word Count : 1544

Backward chaining

Last Update:

(simpler) subgames to find a solution to the game, in a process called backward induction. In chess, it is called retrograde analysis, and it is used to generate...

Word Count : 806

Centipede game

Last Update:

introductory game theory courses and texts to highlight the concept of backward induction and the iterated elimination of dominated strategies, which show a...

Word Count : 2899

Induction puzzles

Last Update:

{\displaystyle X} . Muddy children puzzle can also be solved using backward induction from game theory. Muddy children puzzle can be represented as an extensive...

Word Count : 6926

Game tree

Last Update:

complete game tree can be generated, a deterministic algorithm, such as backward induction or retrograde analysis can be used. Randomized algorithms and minmax...

Word Count : 1357

Chainstore paradox

Last Update:

make, where a "deterrence strategy" appears optimal instead of the backward induction strategy of standard game theory reasoning. The paradox was first...

Word Count : 1188

Sequential game

Last Update:

perfect information, a subgame perfect equilibrium can be found by backward induction. Simultaneous game Subgame perfection Sequential auction Brocas; Carrillo;...

Word Count : 598

The Price Is Right

Last Update:

perfect information for which the equilibrium can be found through backward induction. Several papers have solved the optimal strategy for particular spin...

Word Count : 17240

Solving chess

Last Update:

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...

Word Count : 1574

Stackelberg competition

Last Update:

C i ( q i ) {\displaystyle C_{i}(q_{i})} . The model is solved by backward induction. The leader considers what the best response of the follower is, i...

Word Count : 4267

Glossary of economics

Last Update:

imitate the system, because the reform will offend vested interests. backward induction The process of reasoning backwards in time, from the end of a problem...

Word Count : 25060

Markov decision process

Last Update:

solution. In value iteration (Bellman 1957), which is also called backward induction, the π {\displaystyle \pi } function is not used; instead, the value...

Word Count : 4869

Dynamic programming

Last Update:

any quantity of capital at any previous time can be calculated by backward induction using the Bellman equation. In this problem, for each t = 0 , 1 ,...

Word Count : 9215

Heuristic

Last Update:

of equationsPages displaying wikidata descriptions as a fallback Backward induction – Process of reasoning backwards in sequence Metaheuristic – Optimization...

Word Count : 8771

Search algorithm

Last Update:

the hypothetical physical versions of quantum computing systems. Backward induction – Process of reasoning backwards in sequence Content-addressable memory –...

Word Count : 1574

Complete information

Last Update:

find viable strategies. In dynamic games with complete information, backward induction is the solution concept, which eliminates non-credible threats as...

Word Count : 940

Monty Hall problem

Last Update:

hand Strategies Appeasement Backward induction Bid shading Collusion De-escalation Deterrence Escalation Forward induction Grim trigger Markov strategy...

Word Count : 9895

Game theory

Last Update:

decision tree. To solve any extensive form game, backward induction must be used. It involves working backward up the game tree to determine what a rational...

Word Count : 15903

Curse of dimensionality

Last Update:

explained below. When solving dynamic optimization problems by numerical backward induction, the objective function must be computed for each combination of values...

Word Count : 4129

PDF Search Engine © AllGlobal.net