Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 37 ยท Sequential Games

Backward Induction

Solve sequential games from the leaves up. Write a backward induction solver in Python, apply it to the entry game, the centipede game and a take-away game.

In a sequential game, the player who moves last has an easy job: look at the options, pick the best payoff. The player before that knows what the last mover will do, so that choice is also easy. Repeat all the way to the root. This reasoning, backward induction, is the standard way to solve finite games of perfect information.

You will write a solver once and reuse it on three games. Along the way you will meet a famous puzzle, the centipede game, where the logic is flawless and the result still surprises people.

The algorithm

For a tree with perfect information:

  1. Start at the decision nodes whose children are all leaves.
  2. At each such node, the player moving picks the action with the highest payoff for themselves. Record the choice, and replace the node by the payoffs that choice leads to.
  3. Move one level up and repeat, treating the replaced nodes as leaves.
  4. When you reach the root, you have a payoff vector for the whole game and a choice at every node.

Backward induction

Start at the leaves Find the last decisions
Pick the best action Best for the mover
Collapse the node Replace it by that payoff
Reach the root A full plan appears

Each player assumes later movers act rationally.

1 / 2

A recursive solver

The function returns the payoff vector reached from a node together with the choices made below it. Ties are resolved by taking the first best action, so you should check manually whether ties exist (they can produce several solutions).

Python A backward induction solver

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Result: E enters and I accommodates, giving (2, 2). The "Stay out" equilibrium of the matrix is rejected: I's threat to fight is not what I would choose once E has entered. A threat is credible only if carrying it out is optimal at that moment.

The centipede game

Two players alternate. A pot starts small. At each turn the mover either takes (ends the game, receiving the larger share) or passes (the pot grows). Here is a version with four turns:

flowchart LR
    A["P1: take 2,0 or pass"] --> B["P2: take 1,3 or pass"]
    B --> C["P1: take 4,2 or pass"]
    C --> D["P2: take 3,5 or pass"]
    D --> E["Both pass: 6,4"]

Payoffs for taking are written (P1, P2). If both always pass, the final payoffs are (6, 4).

Backward induction says: at the last turn, P2 compares taking (5) with passing (4), so P2 takes. Knowing this, P1 at turn three compares taking (4) with passing, which leads to (3, 5) and gives P1 only 3, so P1 takes. Then P2 at turn two compares taking (3) with passing, which leads to (4, 2) and gives P2 only 2, so P2 takes. Finally P1 at turn one compares taking (2) with passing, which leads to (1, 3) and gives P1 only 1, so P1 takes at once.

Python Solving the centipede game

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The prediction, "take immediately", gives (2, 0), much worse for both than passing to the end. In lab experiments, people usually pass for several rounds. Explanations include doubt about the other player's rationality, fairness, and the fact that the argument rests on common knowledge of rationality at every step: I know you are rational, and you know I know it, and so on. If a player deviates, the reasoning has no answer for what to believe next.

A take-away game

Backward induction also solves combinatorial games. In a take-away game, there is a pile of stones; players alternately remove 1, 2 or 3 stones; whoever takes the last stone wins. A position is winning for the mover if some move leads to a losing position for the opponent.

Python Winning and losing positions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The losing positions are exactly the multiples of 4: from 4, any move leaves 1 to 3 stones, and the opponent finishes. The pattern is typical: backward induction turns a game with many lines of play into a table filled from the end.

Why it works, and where it breaks

Backward induction needs:

  • A finite tree (or at least a known end).
  • Perfect information: you can see which node you are at.
  • Rationality that is common knowledge.

With imperfect information you cannot collapse a node, because the player does not know where they are. The tool that extends the idea is subgame perfection, in the next lesson. Also, if there are payoff ties at a node, there may be several backward induction solutions; you must follow every tied branch to list them all.

Common mistakes

  • Choosing the action that is best for the observer instead of the mover at that node.
  • Skipping nodes that are "off the path". The plan must cover them, because they determine what is credible.
  • Forgetting that in a game with ties the solution is not unique.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Where does backward induction start?

    The last decisions are easiest to solve, and earlier decisions are then solved using those results.
  2. 2. In the entry game, why does the incumbent's threat to fight fail?

    A threat is credible only if carrying it out is optimal when the moment arrives; here 2 beats -1.
  3. 3. In the take-away game with moves of 1 to 3 stones, which pile sizes are losing for the player to move?

    From a multiple of 4, any move leaves 1 to 3 stones above a multiple of 4, and the opponent restores a multiple of 4.
  4. 4. What does backward induction predict in the centipede game?

    At every turn taking beats passing once later movers are assumed to take, so the unraveling reaches the very first move.

Summary

  • Backward induction solves finite perfect-information games from the leaves to the root.
  • It yields a complete plan, including actions at nodes that are never reached.
  • It removes non-credible threats such as the incumbent's fight in the entry game.
  • It assumes common knowledge of rationality, which explains why people deviate in the centipede game.
  • Win/lose tables for combinatorial games are backward induction in disguise.

Next: Subgame-Perfect Equilibrium