How to Solve Sequential Games Using Backward Induction

Sequential Games and Backward Induction

Game Trees and the Logic of Sequence

When players move in sequence, you need a different tool than a matrix — you need a tree. A game tree (or extensive form game) maps out every possible sequence of decisions and where they lead. Chess has a game tree so vast it makes your head spin — more possible positions than atoms in the observable universe — but the principle stays the same: at each decision point (a node), a player picks a branch, which leads to the next node, which opens up more choices, until you hit a terminal node where payoffs get assigned.

What makes game trees so useful is they expose the logic of decision-making over time. Unlike simultaneous-move games (like the Prisoner's Dilemma, where both players choose blind), sequential games have something crucial: information unfolds as you go. When you move second, you can see (at least some of) what the first player did. That changes everything strategically — and it's what makes backward induction so elegant.

The key insight is backward induction: you start at the end of the tree and work your way back, figuring out at each node what a rational player would actually choose, given what comes next, until you've traced out the whole path. It's like reading a story backwards — you know the ending and you work out how each earlier decision made it happen.

A Concrete Example: Entry Deterrence

Let's use something real: how do companies already in a market stop new competitors from coming in?

Picture this: an incumbent firm (I) owns a market. A potential entrant (E) faces a choice: enter or stay out. If E enters, then I decides whether to fight (start a price war) or accommodate (share the market).

Here's what the payoffs look like:

• E stays out: I gets 5, E gets 0
• E enters, I accommodates: I gets 3, E gets 3
• E enters, I fights: I gets 1, E gets -1

Now work backward:

1. Last node (E has already entered): I chooses between accommodating (payoff 3) and fighting (payoff 1). A rational I accommodates.

2. First node (E's decision): E knows that if it enters, I will accommodate and E gets 3. E chooses between staying out (0) and entering (3). A rational E enters.

3. The solution: Enter, then accommodate. Both get 3.

Here's the thing that's fascinating: the incumbent might threaten to fight before E even moves. It'll announce: "Enter my market and I'll crush you with a price war." But that threat is bluffing. Backward induction shows that if E actually entered, fighting would hurt I's own payoff. Smart entrants see through it.

This reveals something essential: threats only work if they're credible. A credible threat is one you'd actually want to follow through on if the moment came. A non-credible threat — one you'd have no reason to execute — doesn't scare rational players, because they can work out what you'll really do using backward induction.

In practice, incumbents try to make threats stick by using commitment devices — they lock themselves into positions that make the threat painful enough to follow through on. Build massive excess capacity before an entrant arrives, and if they enter, you can flood the market with cheap product without losing much. Suddenly the threat to fight gets credible. (We'll dive deeper into commitment devices in the next section.)

Why Information Matters

Game trees also show exactly what each player knows when they move. Can you see every choice the previous player made? Or are you moving blind? Some games have perfect information — you see the complete history. Chess works this way. Other games have imperfect information — you can't see everything that happened, or you can't see it all. Poker's the classic: you don't know your opponent's cards.

Backward induction usually assumes perfect information. With imperfect information, things get messier — you can't just work backward through the tree because you're uncertain about where you actually are in it.

The Centipede Game: Where Backward Induction Breaks Down

Here's one of game theory's most disturbing puzzles. Two players face a pile of money starting at $2. You take turns. On your turn, you either:

• Stop: End the game. You each take $1.
• Pass: The pile grows to $4, then $8, scaling up to $1024 eventually. The other player moves.

If you keep passing all the way, you each walk away with $512. Sounds great, right? But here's where it falls apart: on the very last turn, whoever moves should stop and pocket the bigger share ($513 vs $511). Knowing that will happen, the second-to-last player should stop before reaching it. And knowing that, the third-to-last player should stop earlier. Backward induction unravels the whole tree. The logic keeps eating itself. The conclusion? Rational players should stop at move one and take $1 each — even though they could've both gotten $512 by working together.

Welcome to the Centipede Game, named for the many "legs" (turns) on the game tree. It's one of game theory's sharpest clashes with real human behavior.

What Actually Happens

When researchers run this experimentally, something weird occurs: subjects almost never stop at the first move. Players pass constantly. Often they get really far down the tree — to points where each could leave with hundreds of dollars. Most real people somehow recognize the mutual gain and manage to cooperate in ways the theory says shouldn't happen.

Why the Gap?

Is this irrational? Or does it hint that the model is missing something?

• Bounded rationality and limited lookahead. Most humans don't think 20 moves ahead. They use shortcuts: "If we both keep passing, we both win. Let's do that." That's not irrational — it's rational when you account for the cognitive effort of deep backward induction.

• Fairness and caring about others' payoffs. Some players genuinely care about equal splits or the other person's welfare, not just their own number. Taking $1 while the other player could get $512 feels wrong. This is the same fairness instinct we'll see wreck other games later.

• Reputation and signaling. Stop at move one and you signal: "I'm a selfish rational automaton." Pass for a while and you signal: "I'm cooperative, trustworthy, reliable." In a one-shot game, this shouldn't matter — yet people play like it does.

• Implicit cooperation gets missed by the model. In real life, there's often an unspoken agreement: "Let's both keep passing." That agreement holds because both players have skin in the game, or because social pressure backs it up. Standard game theory doesn't model these external enforcement mechanisms.

The centipede game exposes a real limit: backward induction nails the Nash equilibrium in sequential games, but often predicts behavior humans find repulsive. That's not a bug, though — it's forcing us to reconsider whether our definition of rationality captures what humans actually value.

graph TD
    A["Start: $2 in pile<br/>(E's turn)"]
    A -->|"Stop"| B["Each gets $1"]
    A -->|"Pass"| C["$4 in pile<br/>(I's turn)"]
    C -->|"Stop"| D["I gets $2, E gets $2"]
    C -->|"Pass"| E["$8 in pile<br/>(E's turn)"]
    E -->|"Pass"| F["...continues..."]
    F -->|"Eventually pass"| G["$1024 in pile<br/>(I's final move)"]
    G -->|"Stop"| H["I gets $513, E gets $511"]
    
    style B fill:#ffcccc
    style D fill:#ffe6cc
    style H fill:#ccffcc
    style G fill:#fff9e6
    
    classDef backward fill:#e6f3ff,stroke:#0066cc,stroke-width:2px
    class A,C,E,G backward

Subgame Perfect Equilibrium: Refining Backward Induction

Backward induction doesn't just find any Nash equilibrium — it finds a particularly strong one: a subgame perfect equilibrium (SPE). A subgame is any chunk of the game tree starting at some node and including all decisions and outcomes downstream. An SPE is a strategy profile that stays a Nash equilibrium not just overall, but in every subgame you could look at.

Why care? In the entry game, we figured out that I accommodates if E enters. That's a Nash equilibrium within the subgame "after entry." The full strategy — "E enters, I accommodates" — is subgame perfect because it's a best response at every decision point, not just along the path you expect to follow.

This solves a problem that backward induction alone avoids: non-credible threats. In a matrix game, you can write a strategy like "Fight if entry occurs, even if I'd rather accommodate." But under subgame perfection, this isn't an equilibrium because it fails the rationality test in the subgame where it would be tested. The threat gets cut down.

Subgame perfection is a refinement — it narrows down which equilibria count by eliminating ones that lean on incredible commitments. It matters especially in sequential games and bargaining, where the order of play hands some players natural leverage.

Practical Implications: When Do People Actually Use Backward Induction?

Game trees and backward induction shine in settings where:

• Everyone understands the game structure clearly.
• The time horizon is short enough to think through (nobody plans 50 moves ahead).
• The stakes justify the mental work.
• There's a definite endpoint.

In chess, experts do something like backward induction — they look several moves ahead and assess positions based on what comes next. In business deals, sharp negotiators think sequentially: "If I ask for X, they counter with Y, I hit back with Z, and we land here." But in unfamiliar games or complicated ones, people grab heuristics and often miss the backward induction story entirely.

The centipede game teaches us that human behavior often diverges from the prediction — not because people are irrational, but because the model leaves out what actually matters to humans: fairness, reputation, the limits of human cognition, and the possibility that cooperation can be real, not just a game theory artifact.