Backward Induction and Subgame Perfect Nash Equilibrium

1. The Theoretical Foundation: Zermelo's Theorem

Before we dive into the algorithm, let's appreciate its theoretical underpinnings. In 1913, Ernst Zermelo proved a theorem stating that any finite, two-player game of perfect information where the outcomes are win, lose, or draw (like chess or tic-tac-toe) has a determined outcome. This means either Player 1 can force a win, Player 1 can force a draw, or Player 2 can force a win.

The genius of Zermelo's theorem is not just its conclusion, but its proof. The proof itself is an argument by induction, which is the very logic that powers the backward induction algorithm. Given your interest in mathematical rigor, seeing this connection between a foundational theorem and a practical algorithm is insightful.

2. The Algorithm of Backward Induction

The inductive proof you just watched provides the blueprint for a practical algorithm. We can solve any finite game of perfect information by working backward from the end.

The procedure is as follows:

1. Identify the final subgames: Start at the decision nodes just before the terminal nodes (the final outcomes).
2. Determine the optimal final moves: For each of these final decision nodes, find the optimal action for the player whose turn it is by comparing their payoffs. A rational player will choose the action that leads to their highest payoff.
3. Prune the tree: "Prune" or eliminate the branches corresponding to the non-optimal actions. You can now treat the decision node as if it leads directly to the outcome of the optimal choice. Replace that node with the payoff vector associated with that optimal action.
4. Iterate backwards: Move to the now-penultimate (second-to-last) decision nodes and repeat the process, taking the determined outcomes from the next stage as given.
5. Continue to the beginning: Repeat this process until you have worked all the way back to the initial node of the game. The sequence of optimal actions you have identified forms the SPNE path.

Let's see this in action.

Let's apply the algorithm to the game in the image:

• Final Nodes (Celine's moves):
  • At node c, Celine chooses between "Sports" (payoff 2) and "Comedy" (payoff 4). She will choose Comedy. We prune the "Sports" branch. The outcome at node 'c' is effectively (4, 4).
  • At node d, Celine chooses between "Sports" (payoff 3) and "Comedy" (payoff 1). She will choose Sports. We prune the "Comedy" branch. The outcome at node 'd' is effectively (3, 3).
• Previous Node (Bob's move):
  • At node b, Bob anticipates Celine's choices. If he chooses "Sports", he knows the game proceeds to node 'c' where Celine will choose "Comedy", giving him a payoff of 4. If he chooses "Comedy", the game goes to node 'd' where Celine will choose "Sports", giving him a payoff of 3. He prefers 4, so he will choose Sports. We prune the "Comedy" branch from node 'b'.
• Initial Node (Bob's move):
  • At node a, Bob chooses between "Sports", giving him a payoff of 2, or "Comedy", which leads to node 'b'. He knows that if the game reaches node 'b', he will choose "Sports" and get a payoff of 4. He prefers 4 over 2, so he will choose Comedy. We prune the "Sports" branch from node 'a'.

The path we have traced is the Backward Induction Outcome: Bob chooses Comedy, then Bob chooses Sports, then Celine chooses Comedy. The final payoff is (4, 4).

3. Finding and Stating the SPNE

The backward induction outcome is the path that will actually be played. The Subgame Perfect Nash Equilibrium (SPNE) is the full strategy profile that supports this outcome. Remember, a strategy is a complete plan of action for every decision node a player might face.

To state the SPNE, we list the optimal action we found for every single decision node, even those on paths that were pruned.

For the game above, the SPNE is:

• Bob's Strategy: {Choose Comedy at node a, Choose Sports at node b}
• Celine's Strategy: {Choose Comedy at node c, Choose Sports at node d}

The actions for the pruned nodes (like Bob choosing 'Sports' at node 'a') are the credible threats (or promises) that make the equilibrium path hold.

4. Practice Problem

Now it's your turn. Use the backward induction algorithm to find the SPNE of the game shown in the tree below.

Take a moment to work through it on your own before revealing the solution.

Conclusion

You have now mastered backward induction, the fundamental algorithm for analyzing finite sequential games of perfect information. This method operationalizes the concept of SPNE, allowing you to systematically discard non-credible threats and find the unique, rational outcome.

Key Takeaways:

• Backward induction is a recursive algorithm that solves a game by starting at the terminal nodes and working backward.
• At each decision node, you determine the optimal action by assuming all future actions will also be optimal.
• The algorithm identifies a unique path, the backward induction outcome, and a complete Subgame Perfect Nash Equilibrium (SPNE) strategy profile.
• The SPNE must specify an action for every decision node, including those off the equilibrium path, as these actions are what make the path credible.

In the next lesson, we will apply this tool to analyze a classic economic scenario: an incumbent firm deciding whether to fight or accommodate a new entrant. This will allow you to use subgame perfection to formally distinguish between credible and non-credible threats in a strategic business context.