Solving Game Theory Problems with Backward Induction

Backward induction is a powerful mathematical method used in game theory to solve sequential games by working backward from the end of a decision tree to the beginning. This article explains the core concept of backward induction, outlines a step-by-step guide to applying it, illustrates the process with a practical two-player game, and addresses its limitations in real-world scenarios.

What is Backward Induction?

In game theory, games are generally classified as either simultaneous (where players act at the same time) or sequential (where players take turns). Backward induction is specifically designed for sequential games of perfect information, meaning games where players know all previous moves before making their own.

The process involves analyzing the game starting from the very last decision point (the terminal nodes) and determining what the final player would do to maximize their utility. Once that final decision is established, the analyst steps one turn backward to determine what the second-to-last player would do, assuming the last player will act rationally. This process repeats until the first move of the game is determined.

By using this method, players can identify the “Subgame Perfect Equilibrium,” which represents the optimal sequence of decisions where no player has an incentive to deviate from their strategy.

Step-by-Step Guide to Solving a Game

To solve a sequential game using backward induction, follow these steps:

  1. Draw the Game Tree (Extensive Form): Represent the game visually. Nodes represent decision points for specific players, branches represent available choices, and the final leaves (terminal nodes) display the payoffs for all players involved.
  2. Locate the Final Decision Nodes: Find the decision points that immediately precede the end of the game. Identify which player makes the decision at these nodes.
  3. Determine the Optimal Final Moves: For each final decision node, determine which option yields the highest payoff for the active player.
  4. Prune the Tree: Assume the player will choose that optimal path. Erase the suboptimal branches and move the chosen payoffs back to the parent decision node.
  5. Move Backward: Step back to the preceding set of decision nodes. Analyze the choices of the player active at this stage, knowing how the subsequent player will react based on step 3.
  6. Repeat Until the Start: Continue this backward progression until you reach the very first decision node of the game. The remaining path from the start to the end represents the equilibrium of the game.

A Practical Example

Consider a simple two-player, sequential game between Player 1 and Player 2.

To solve this using backward induction, we start at Stage 2 with Player 2’s choices: * If Player 1 chose Left: Player 2 compares their own payoffs for Up (4) versus Down (2). Since 4 is greater than 2, Player 2 will choose Up. The payoff for this path is (2, 4). * If Player 1 chose Right: Player 2 compares their own payoffs for Up (1) versus Down (3). Since 3 is greater than 1, Player 2 will choose Down. The payoff for this path is (3, 3).

Now, we move backward to Stage 1, where Player 1 makes the initial choice. Player 1 is highly rational and anticipates Player 2’s optimal responses: * If Player 1 chooses Left, they know Player 2 will choose Up, resulting in a payoff of 2 for Player 1. * If Player 1 chooses Right, they know Player 2 will choose Down, resulting in a payoff of 3 for Player 1.

Player 1 compares their final payoffs: choosing Left yields 2, while choosing Right yields 3. Since 3 is greater than 2, Player 1 chooses Right.

The backward induction solution (Subgame Perfect Equilibrium) is: Player 1 plays Right, and Player 2 plays Down if Player 1 plays Right (and Up if Player 1 plays Left).

Limitations of Backward Induction

While mathematically sound, backward induction relies on two strict assumptions: perfect rationality and common knowledge of rationality. It assumes all players will always make the utility-maximizing choice and that every player knows everyone else will do the same.

In real life, human psychology, emotions, and cognitive limitations often lead to deviations. In famous experiments like the “Centipede Game,” human players frequently cooperate longer than backward induction predicts, because they trust each other to not take the immediate greedy choice, resulting in higher mutual payoffs than the strict mathematical equilibrium.