Backward Induction: Solving Games by Working Backwards

You’re playing chess. How do you decide your next move? Master players don’t just think one move ahead — they think many moves ahead, anticipating their opponent’s responses, then their own responses to those responses, and so on.

This is backward induction — one of game theory’s most powerful techniques. Instead of reasoning forward from the start, you reason backward from the end.

And it reveals some surprising truths about strategy.

The Core Idea

Backward induction is a method for solving sequential games (games where players move in turns) by:

1. Starting at the final decision point
2. Determining the optimal choice at that point
3. Moving backward to the previous decision point
4. Repeating until you reach the beginning

The result: a complete strategy for every player that specifies optimal play at every possible point in the game.

A Simple Example: The Take-Away Game

Two players alternate taking 1, 2, or 3 coins from a pile of 10 coins. The player who takes the last coin wins.

Who wins with optimal play, and what’s the strategy?

Let’s use backward induction.

Step 1: Analyze the End

If 1-3 coins remain, the current player takes them all and wins.

If 4 coins remain, the current player loses:

• Take 1 → 3 remain → opponent wins
• Take 2 → 2 remain → opponent wins
• Take 3 → 1 remains → opponent wins

So 4 coins = losing position.

Step 2: Work Backwards

If 5-7 coins remain, the current player can force the opponent into the 4-coin losing position:

• From 5: take 1 → leave 4 → opponent loses
• From 6: take 2 → leave 4 → opponent loses
• From 7: take 3 → leave 4 → opponent loses

So 5, 6, or 7 coins = winning positions.

If 8 coins remain, the current player loses (opponent gets to 5-7 and wins).

Step 3: Pattern Emerges

Positions: W = Win, L = Lose

Pattern: Positions that are multiples of 4 are losing positions!

Optimal strategy from 10 coins: Player 1 takes 2, leaving 8 (a losing position for Player 2). Player 1 wins with optimal play.

Formal Game Trees

Sequential games are represented as game trees (also called extensive form).

Each node represents a decision point. Each edge represents an action. Terminal nodes show final payoffs.

Example: The Ultimatum Game (Simplified)

Player 1 proposes how to split $10. Player 2 accepts or rejects. If rejected, both get $0.

Let’s say Player 1 can only propose (5,5) or (8,2).

Backward induction:

1. At each of Player 2’s decision nodes, compare payoffs:

   • After (5,5) offer: Accept gives 5, Reject gives 0 → Accept
   • After (8,2) offer: Accept gives 2, Reject gives 0 → Accept

2. At Player 1’s decision node, knowing Player 2 accepts both:

   • Offer (5,5) → get 5
   • Offer (8,2) → get 8
   • Choose (8,2)

Backward induction prediction: Player 1 offers (8,2), Player 2 accepts.

(But as we’ll see in the next post, humans often reject unfair offers — a challenge to rational choice theory!)

Subgame Perfect Equilibrium

Backward induction finds the subgame perfect Nash equilibrium (SPNE).

Nash Equilibrium: Strategies are best responses to each other.

Subgame Perfect: Strategies are optimal at every possible point in the game, even off the equilibrium path.

Why It Matters: Eliminating Non-Credible Threats

Consider this game:

1. Player 1 chooses: Share ($5 each) or Grab ($8 for P1, then P2 decides)
2. If P1 grabs, P2 chooses: Accept ($8, $2) or Burn (both get $0)

Is “I’ll burn it if you grab” a credible threat?

Backward induction:

At P2’s decision: Accept gives 2, Burn gives 0 → Accept

At P1’s decision: Share gives 5, Grab gives 8 → Grab

SPNE: (Grab, Accept)

The threat to burn is not credible because when the moment comes, P2 prefers to accept. Player 1 should ignore the threat.

Lesson: Only credible threats affect optimal play. Backward induction reveals which threats are credible.

Classic Application: Stackelberg Competition

Two firms choose production quantities. Firm 1 moves first, Firm 2 observes and responds.

Market price: P = 100 - Q (where Q = q₁ + q₂)

Costs: Zero (for simplicity)

Firm profits:

• Firm 1: π₁ = q₁(100 - q₁ - q₂)
• Firm 2: π₂ = q₂(100 - q₁ - q₂)

Backward Induction Solution:

Step 1: Firm 2’s optimal response to q₁

Maximize π₂ = q₂(100 - q₁ - q₂)

Take derivative: 100 - q₁ - 2q₂ = 0

Firm 2’s best response: q₂ = (100 - q₁)/2

Step 2: Firm 1’s optimal choice, anticipating Firm 2’s response

Substitute into π₁: π₁ = q₁(100 - q₁ - (100 - q₁)/2) = q₁(50 - q₁/2)

Maximize: 50 - q₁ = 0

Firm 1’s optimal quantity: q₁ = 50

Step 3: Firm 2’s response

q₂ = (100 - 50)/2 = 25

Outcome:

• Firm 1 produces 50, earns 50 × 50 = $2500
• Firm 2 produces 25, earns 25 × 25 = $625
• First-mover advantage!

The Centipede Game: A Paradox

Two players alternate choosing to Continue or Stop. The pot grows each round, but stopping gives you a slightly larger share.

Payoffs increase as the game continues, but the player who stops gets slightly more than if the other player stops next.

Backward induction prediction:

• At the last decision (P1 at round 5): Stop and get 5 vs Continue and get 6. But wait — by stopping, P1 gets 5, P2 gets 3. By continuing, both get 6. If P1 is selfish about getting more than P2, they stop.

Let me reconsider the payoffs more carefully. In the centipede game, the typical structure is:

• Stopping gives you more NOW than continuing and letting the opponent stop next
• But continuing and having the opponent also continue gives both more

Simplified version:

Round 1: P1 can stop (1, 0) or continue Round 2: P2 can stop (0, 3) or continue Round 3: P1 can stop (4, 1) or continue Round 4: Both get (2, 5) if reached

Backward induction:

At round 3: P1 stops (gets 4 instead of 2) → (4, 1)

At round 2: P2 stops (gets 3 instead of 1) → (0, 3)

At round 1: P1 stops (gets 1 instead of 0) → (1, 0)

Backward induction predicts: P1 stops immediately at round 1!

In experiments: People usually continue several rounds. Why?

• Trust that opponent will reciprocate
• Social preferences (fairness, cooperation)
• Bounded rationality
• Reputation concerns

This is a paradox of backward induction: the logic is ironclad, but it predicts behavior that seems absurd and empirically doesn’t happen.

Limitations of Backward Induction

1. Perfect Rationality Assumption

Backward induction assumes all players are perfectly rational and know all others are perfectly rational, ad infinitum. But humans aren’t perfect reasoners.

2. Complete Information Assumption

You need to know the entire game tree and all payoffs. In reality, there’s often uncertainty.

3. Commitment Problems

Sometimes you want to credibly commit to an irrational action. (More on this in game theory applications to negotiation.)

4. Trembling Hand

What if players sometimes make mistakes? This can break backward induction logic (see the centipede game).

When Backward Induction Works Best

Backward induction is most reliable when:

1. The game tree is small and tractable
2. Payoffs are well-defined and known
3. Rationality is reasonable: contexts like chess, business strategy, optimal stopping problems
4. Stakes are high enough that players think carefully
5. Players have experience with the game structure

Real-World Applications

1. Chess and Go

Computer chess engines use backward induction (via algorithms like minimax) to search game trees and find optimal moves.

2. Business Strategy

• Should you enter a market, anticipating incumbent response?
• Use backward induction to predict whether they’ll fight or accommodate

3. Negotiations

• Work backward from the final offer to determine opening positions
• Anticipate counteroffers and concessions

4. Political Strategy

• Legislative voting: predict how amendments will affect final votes
• Campaign strategy: anticipate opponent responses to your moves

5. Legal Proceedings

• Litigation vs settlement decisions
• Anticipate jury verdicts and appellate outcomes

Practice Problem: The Pirate Game

Five pirates must divide 100 gold coins. They vote on proposals in order (Pirate 1, then 2, etc.). If a proposal gets a majority (including the proposer), it passes. Otherwise, the proposer is thrown overboard, and the next pirate proposes.

Pirates are:

1. Rational and greedy (want maximum coins)
2. Bloodthirsty (prefer throwing pirates overboard if indifferent)
3. Self-preserving (prefer survival above all)

Question: What should Pirate 1 propose?

Key Takeaways

1. Backward induction solves sequential games by reasoning from the end to the beginning
2. Start at final decision nodes and work backward to determine optimal strategies
3. Finds subgame perfect equilibrium — strategies that are optimal at every point
4. Eliminates non-credible threats — only credible commitments matter
5. First-mover advantage often exists (Stackelberg competition)
6. Paradoxes arise when perfect rationality is assumed (centipede game)
7. Most powerful for: chess, business strategy, negotiations, sequential decision-making

What’s Next?

Backward induction assumes players are perfectly rational. But what if they’re not? What if emotions, fairness, and social preferences matter?

Next, we’ll explore The Ultimatum Game — a simple game that reveals the limits of rational choice theory and shows that humans aren’t always the selfish calculators economists assume.

This post is part of the Game Theory Series, where we explore the mathematics of strategic decision-making.