Introduction
In our previous lesson, we analyzed how to optimize an existing system using the forward-looking steps of the Theory of Constraints. We saw how identifying and exploiting a single policy constraint could dramatically improve a hospital's performance.
Now, we shift our perspective from optimizing the present to strategically planning the future. Today's lesson introduces backward induction, a cornerstone of game theory and the core mechanism for the "Strategic Back-Calculation" you aim to master. The learning outcome is to solve a sequential decision problem using backward induction on a decision tree.
This method involves starting at the final desired outcome and reasoning backward in time to determine the optimal sequence of actions to take in the present. It's a powerful tool for navigating any situation where your success depends on the choices of others, or on a series of your own future decisions.
The Logic of Backward Induction
In a sequential game, players make decisions one after another. Your first move should not be made in a vacuum; it must anticipate the rational responses of all other players (or your future self) to all possible subsequent moves. The most effective way to do this is to figure out the final move first and work your way back.
To see this logic in action, let's watch a video that introduces a simple sequential game and demonstrates why starting at the end is the only reliable way to find the optimal strategy.
Game Theory 101 (#17): Backward Induction
This video from the Game Theory 101 series by William Spaniel provides a clear rationale for backward induction and walks through a simple two-player game.
Please watch from the beginning until 04:01. Pay close attention to: Why simply looking forward from the start can be misleading. How determining the optimal move at the final decision point simplifies the choice at the preceding decision point.
As the video demonstrates, backward induction is a process of "pruning" the decision tree. At each final decision node, you identify the optimal action for the player whose turn it is. You can then discard all other branches originating from that node, as a rational player would never choose them. The payoff from that optimal action effectively becomes the value of reaching that node. This simplifies the game, allowing you to repeat the process at the next-to-last set of nodes, and so on, until you reach the beginning.
The Formal Algorithm
Given your background in applied mathematics, you'll appreciate the formal structure behind this process. A decision tree, or a game in its extensive form, consists of nodes (decision points), branches (actions), and leaves (final outcomes with payoffs).
Backward induction is an algorithm for finding a specific type of solution, the Subgame Perfect Equilibrium (SPE), in finite-horizon games. An SPE is a strategy profile where players' strategies constitute a Nash Equilibrium in every subgame of the original game. In simpler terms, it ensures that every player is acting optimally at every possible decision point, eliminating "non-credible threats"—actions a player might threaten but would not rationally execute if that point in the game were actually reached.
For a more rigorous definition, please review the first section of the following document from MIT OpenCourseWare.
This reading provides the formal definition of backward induction and lays out the mechanical algorithm.
Please read Section 9.1, 'Definition' (pages 131-133). Focus on understanding the assumption of 'sequential rationality' and the step-by-step procedure described, which culminates in the reduction of the game tree shown in the figures.
Worked Example: A Three-Player Game
The logic of backward induction extends to games with any number of players. The process remains the same: start at the final player's moves and work backward.
The following video demonstrates this with a more complex three-player scenario. Notice how the final player's (Harry's) predictable choices effectively remove several branches from the tree, which in turn determines the second player's (Voldemort's) optimal move, and finally, the first player's (Jenny's) best action.
This video by Ashley Hodgson provides an excellent step-by-step walkthrough of backward induction in a three-player game.
Watch from the beginning until 05:41. Your goal is to trace the logic from Harry's final decisions back to Jenny's initial choice. Observe how players' 'favorite' outcomes are often unattainable because of the rational choices of others later in the game.
The key insight here is that the actions of players further down the decision tree constrain the effective choices of players earlier in the tree. A choice that seems appealing on the surface might lead to a sequence of responses from others that results in a poor outcome for you. Backward induction makes this chain of consequences explicit.
Practice: The Subtraction Game
Now, let's apply this method yourself. Consider the classic "subtraction game."
Rules:
- There is a pile of 4 chips.
- Two players take turns. Player 1 goes first.
- On your turn, you can remove either 1 or 2 chips.
- The player who removes the last chip wins.
Your task is to determine Player 1's winning strategy. Use backward induction. Don't draw the full tree yet; just reason backward from the goal.
Think step-by-step:
- Endgame: To win, you must be the one to take the last chip(s). This means you want it to be your turn when there are 1 or 2 chips left.
- What state must you leave your opponent in for you to win? If you leave Player 2 with 3 chips, what can they do?
- If Player 2 takes 1 chip, 2 are left for you. You take both and win.
- If Player 2 takes 2 chips, 1 is left for you. You take it and win.
- Therefore, your goal is to force Player 2 into a situation where they are faced with a pile of 3 chips.
- Initial Move: You are Player 1, and you start with 4 chips. How can you leave Player 2 with 3 chips?
You must take 1 chip.
This is the solution derived from backward induction. By starting at the win condition and working backward, you identified the key intermediate state (leaving 3 chips for the opponent) and then determined the initial move required to get there.
Now, let's see this formalized. The following document explains this exact game with a game tree.
This handout from a Harvard Decision Theory course uses the subtraction game as its primary example for introducing games in extensive form and backward induction.
Please read the first page of the document. Compare the logic we just walked through with the 'leaves up' approach described in the text and illustrated in the game tree.
Conclusion
In this lesson, you have learned the fundamental technique of backward induction for solving sequential decision problems. This is the first step toward building your framework for strategic back-calculation.
Key Takeaways:
- Backward Reasoning: The optimal strategy in a sequential game is found by reasoning from the final move back to the first. This accounts for the rational responses of all players at all stages.
- Decision Trees: Sequential games are modeled using decision trees (extensive form), where nodes are decision points and leaves are outcomes.
- Pruning the Tree: Backward induction works by selecting the optimal move at each terminal decision node and replacing that subgame with the resulting payoff, effectively simplifying the game at each step.
- Subgame Perfect Equilibrium (SPE): The solution found through backward induction is an SPE, a robust equilibrium concept that eliminates non-credible threats and ensures rationality at every point in the game.
Preview of the Next Lesson:
We have now learned how to solve a given decision tree. But how do you create one for your own goals? In the next lesson, you will learn to construct a resource-dependency map by back-calculating from a defined goal to identify the 'Hook' (primary systemic constraint). We will bridge the gap between abstract game theory and your personal objective of mapping your path to maximum potential.