Backward induction is the process of reasoning backward in time, from the end of a problem or situation, to determine a sequence of optimal actions. It is an algorithm for computing equilibria of games with sequential structure, known as early as Zermelo. It proceeds by first considering the last time a decision might be made and choosing what to do in any situation at that time. Using this information, one can then determine what to do at the second-to-last time of decision. This process continues backward until one has determined the best action for every possible situation (i.e. for every possible information set) at every point in time. It was first used by Zermelo in 1913, to prove that chess has pure optimal strategies. It is a staple of game-theoretic applications and a standard criterion which solution concepts are expected to satisfy.
In the mathematical optimization method of dynamic programming, backward induction is one of the main methods for solving the Bellman equation. In-game theory, backward induction is a method used to compute subgame perfect equilibria in sequential games. In-game theory, it is an iterative process of reasoning backward in time, from the end of a problem or situation, to solve finite extensive form and sequential games, and infer a sequence of optimal actions. The only difference is that optimization involves just one decision-maker, who chooses what to do at each point of time, whereas game theory analyzes how the decisions of several players interact. That is, by anticipating what the last player will do in each situation, it is possible to determine what the second-to-last player will do, and so on. The natural way to solve the problem above is to require that a player’s strategy specify optimal actions at every node of the game tree. 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.
Definition: A player’s strategy exhibits sequential rationality if it maximizes his or her expected payoff, conditional on every information set at which he or she has the move. That is, player ‘i’s strategy should specify an optimal action at each of player ‘i’s information sets, even those that player ‘i’ does not believe will be reached in the game.
Backward induction has been used to solve games as long as the field of game theory has existed. It is the process of reasoning backward in time, from the end of a problem or situation, to determine a sequence of optimal actions. John von Neumann and Oskar Morgenstern suggested solving zero-sum, two-person games by backward induction in their Theory of Games and Economic Behavior (1944), the book which established game theory as a field of study.
