Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 37 ยท Sequential Games

Extensive-Form Games and Game Trees

Model games where players move in turn with game trees: nodes, actions, payoffs, perfect and imperfect information, and how a tree converts to a payoff matrix.

So far, the games in this course were played simultaneously: everyone chooses without seeing what the others did. Many real situations are not like that. In chess you see the opponent's move first. A company decides whether to enter a market after seeing whether a rival is already there. When players move in turn, the order and the information they have become part of the game, and the matrix (normal form) is no longer the natural picture. The extensive form, a game tree, is.

In this lesson you will learn the vocabulary of game trees, build one in Python, and see how a tree can be flattened into a matrix, which shows why the tree carries more information.

The parts of a game tree

A game tree is a directed graph with no cycles. It has:

  • Nodes. The root is where the game starts. A decision node belongs to one player, who must choose there. A terminal node (a leaf) ends the game.
  • Edges (actions). Each edge leaving a decision node is an action the player at that node can take.
  • Payoffs. Each leaf carries one payoff for every player.
  • Information. What a player knows when moving. In a game of perfect information, every player sees all earlier moves. If a player cannot tell some nodes apart, those nodes sit in one information set, and the game has imperfect information. A simultaneous game is just a tree where the second mover cannot tell which action the first took.

Anatomy of a game tree

Root Where play starts
Decision nodes One player picks an action
Leaves The game ends here
Payoffs One number per player

Read the tree from the root down.

1 / 2

A small example: the entry game

An entrant (player E) decides whether to enter a market or stay out. If E stays out, E earns 0 and the incumbent (player I) earns 4. If E enters, I chooses to fight (a price war) or accommodate (share the market). Fighting gives both a payoff of -1. Accommodating gives E 2 and I 2.

flowchart TD
    E["E chooses"] -->|"Stay out"| L1["E 0, I 4"]
    E -->|"Enter"| I["I chooses"]
    I -->|"Fight"| L2["E -1, I -1"]
    I -->|"Accommodate"| L3["E 2, I 2"]

The entry game. Payoffs are written as (E, I).

Building a tree in Python

A simple representation: a leaf is a tuple of payoffs, and a decision node is a dictionary with the player's index and a mapping from action names to child nodes.

Python The entry game as data

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.

Strategies in a tree are complete plans

In the normal form, a strategy was one action. In a tree, a pure strategy is a complete plan of action: a choice at every decision node where that player could be asked to move, even nodes that the plan itself makes unreachable.

In the entry game, E has one decision node, so E has two strategies: Stay out and Enter. I also has one node, so I has two strategies: Fight and Accommodate. With more nodes, the count multiplies: a player with a node of 2 actions and another node of 3 actions has 2 x 3 = 6 strategies.

Why include choices at nodes that will not be reached? Because a strategy must say what you would do if play went there. Your opponent's decision to deviate depends on that belief, as the next lessons show.

Python Counting pure strategies

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.

From tree to matrix

Any extensive-form game has a normal form: list every pair of pure strategies, follow them down the tree, and record the leaf reached. For the entry game:

I: Fight I: Accommodate
E: Stay out 0, 4 0, 4
E: Enter -1, -1 2, 2

The matrix has two pure Nash equilibria: (Stay out, Fight) and (Enter, Accommodate). The first one is odd: I "threatens" to fight, E believes it and stays out. But if E did enter, would I really fight? Fighting gives I -1; accommodating gives 2. The threat is not credible. The matrix cannot show that, because it has erased the order of moves. The tree keeps it, and solving the tree from the end (the topic of the next lesson, backward induction) removes the bad equilibrium.

Python Flatten a tree into a matrix

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.

Imperfect information and information sets

Suppose I could not observe whether E entered before choosing. Then I's decision nodes would be joined in one information set, and I must pick the same action at all of them. A simultaneous game is therefore a special case of the extensive form, with the "second" mover ignorant of the first move. Information sets are drawn as a dashed line or a shaded oval around the nodes.

Another source of imperfect information is nature, a pseudo-player that moves randomly (a coin flip, a card deal, a random type). Nature's moves carry probabilities rather than payoffs, and expected payoffs are computed over them. Games where a player has private information, such as the hidden values in auctions, use this idea.

Common mistakes

  • Giving a strategy only for the reachable path. A strategy must cover every node you control.
  • Confusing an action (one choice at one node) with a strategy (the whole plan).
  • Treating a matrix and a tree as the same thing. Different trees can give the same matrix, and the matrix hides credibility.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In a game tree, what does a leaf (terminal node) contain?

    A leaf ends the game and lists one payoff per player.
  2. 2. A player controls two decision nodes, with 2 actions at one and 3 at the other. How many pure strategies does the player have?

    A pure strategy picks an action at every node, so the counts multiply: 2 x 3 = 6.
  3. 3. What is an information set?

    When a player cannot observe which of several nodes was reached, the nodes form one information set and the player must act the same way at all of them.
  4. 4. Why can the normal form hide something the game tree shows?

    The matrix lists strategy pairs and outcomes, but not whether a threatened action would be rational once reached.

Summary

  • An extensive-form game is a tree of decision nodes, actions and payoff leaves.
  • Perfect information means every move is observed. Information sets model hidden moves.
  • A pure strategy is a complete plan: one action at each of the player's decision nodes.
  • Every tree flattens to a matrix, but the matrix loses the move order and the credibility of threats.
  • Simultaneous games are trees with an information set joining the second mover's nodes.

Next: Backward Induction