Backward induction

Not to be confused with Backpropagation.

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]

  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.