Backward Induction

Backward induction is an iterative process of reasoning backward from the end of a problem or situation to solve finite extensive-form and sequential games and infer a sequence of optimal actions. It is used in game theory. to determine the most optimal sequence of actions based on rational behavior.

Solving Sequential Games Using Backward Induction

Below is a simple sequential game between two players. The labels for Player 1 and Player 2 show the information sets for each. The numbers in the parentheses at the bottom of the tree are the payoffs at each respective point. The game is also sequential, so Player 1 makes the first decision (left or right) and Player 2 makes their decision after Player 1 (up or down).

Backward induction, like all game theory, uses the assumptions of rationality and maximization, meaning that Player 2 will maximize their payoff in any given situation. At either information set we have two choices, four in all. By eliminating the choices that Player 2 will not choose, we can narrow down our tree. In this way, we will mark the lines in blue that maximize the player's payoff at the given information set.

After this reduction, Player 1 can maximize their payoffs now that Player 2's choices are made known. The result is an equilibrium found by backward induction of Player 1 choosing "right" and Player 2 choosing "up." Below is the solution to the game with the equilibrium path bolded. 

Subgame perfect equilibrium

In game theory, a subgame perfect equilibrium (or subgame perfect Nash equilibrium) is a refinement of a Nash equilibrium used in dynamic games. A strategy profile is a subgame perfect equilibrium if it represents a Nash equilibrium of every subgame of the original game. Informally, this means that at any point in the game, the players' behavior from that point onward should represent a Nash equilibrium of the continuation game (i.e. of the subgame), no matter what happened before.