Game Trees

Introduction: Why game trees matter 🎮

In many real-life situations, people do not choose all at once. They choose step by step, and each choice depends on what happened before. students, think of a chess match, a bargaining conversation, or a store deciding whether to lower prices after a competitor acts. These are sequential decisions, and game trees help us represent them clearly.

A game tree is a diagram that shows who moves, what choices they have, and what happens next. It lets us see the full path of a game from start to finish. In game theory, this is important because players often make decisions based on earlier actions, not just on a single simultaneous move. By the end of this lesson, you should be able to draw a basic game tree, identify nodes and branches, and read a sequential game from the diagram.

What a game tree shows 🌳

A game tree is a picture of a game played in steps. The tree starts with a single beginning point and grows outward as players make choices. Each point where a decision is made is called a node. Each possible choice from a node is shown by a branch, also called an edge.

The earliest point in the game is the root node. This is where the game begins. From there, branches lead to other nodes or to endings. If a branch leads to no more choices, the game has reached a terminal node. The terminal node represents a final outcome, such as a payoff, a win, a loss, or some other result.

A key idea is that the tree records the order of play. If Player 1 moves first, then Player 2 reacts, the tree shows Player 1’s choices first and Player 2’s possible responses after that. This is different from a table of strategies in simultaneous games because the timing is part of the structure.

Parts of a game tree 🧩

Let’s name the main parts clearly.

Root node: The starting point of the game.
Node: A point where a player must choose an action.
Branch: A line connecting one node to another, showing a possible action.
Terminal node: A final point where the game ends.
History: The sequence of actions that have happened so far.

A history is like a path through the tree. For example, if Player 1 chooses “Left” and then Player 2 chooses “Right,” that sequence is one history. Histories matter because later choices may depend on what came before.

In many trees, each path from the root node to a terminal node represents one possible outcome of the game. If there are several players and several stages, the tree helps us keep track of every possible sequence of actions 📌

How to draw a basic game tree ✏️

To draw a simple game tree, start with the first decision point. Suppose Player 1 moves first and can choose $A$ or $B$.

Draw a root node.
Draw two branches from it, one for $A$ and one for $B$.
If Player 2 moves after each of those choices, draw a new node at the end of each branch.
From each of Player 2’s nodes, draw branches for Player 2’s choices.
End each branch at a terminal node with the final outcome.

Here is a simple example in words:

Player 1 chooses $A$ or $B$.
If Player 1 chooses $A$, then Player 2 chooses $X$ or $Y$.
If Player 1 chooses $B$, then Player 2 chooses $X$ or $Y$.
Each pair of choices ends the game.

This tree has one root node, two decision nodes for Player 2, and four terminal outcomes. The full histories are $A \to X$, $A \to Y$, $B \to X$, and $B \to Y$.

Notice how the tree shows not just what players can do, but when they do it. That is the power of game trees: they reveal the structure of sequential choice.

Reading a sequential game from a tree diagram 👀

Reading a tree means following the branches from the start to the end. students, imagine a tree that says:

Player 1 chooses $L$ or $R$.
If Player 1 chooses $L$, then Player 2 chooses $U$ or $D$.
If Player 1 chooses $R$, then the game ends immediately.
Payoffs are attached at the terminal nodes.

To read this game, start at the root node. First ask: who moves? Player 1. What are the choices? $L$ and $R$. Then trace each branch.

If Player 1 chooses $L$, move to the next node and look at Player 2’s choices.
If Player 2 chooses $U$, go to that terminal node and read the outcome.
If Player 2 chooses $D$, go to the other terminal node and read that outcome.
If Player 1 chooses $R$, the game ends right away.

This method helps you understand the consequences of each action. A tree diagram turns a word problem into a visual map.

A useful habit is to read a tree from left to right or from top to bottom, depending on how it is drawn. The important thing is to follow the sequence correctly. The first move creates the next set of possibilities, and so on.

Example: a simple business decision 💼

Suppose a small business owner must decide whether to launch a product now or wait. If the owner launches now, a competitor may respond by lowering prices. If the owner waits, the competitor may stay calm.

We can represent this as a game tree:

Player 1: the business owner
Player 2: the competitor
Player 1 chooses $Launch$ or $Wait$
If Player 1 chooses $Launch$, Player 2 chooses $Cut$ or $Hold$
If Player 1 chooses $Wait$, the game ends with no further action

This tree shows a real pattern of decision-making. The business owner’s first move changes what the competitor gets to do next. That is the meaning of sequential interaction.

Game trees are useful because they make hidden timing visible. Without the tree, it may be hard to see which player has to respond after which action. With the tree, the order is obvious.

You can also attach outcomes to the ends. For example, the terminal nodes might say things like “higher profit,” “lower profit,” or “no change.” The exact numbers are not the main point here. What matters is that each final path leads to a distinct outcome.

Histories and decision paths 🛤️

A history is the record of actions taken so far. In a game tree, every node except the root has a history leading to it. This is why the same player may face different situations at different points in the game.

For example, if a player reaches one node after seeing $A$, and another node after seeing $B$, the player knows different information in each case. The history tells us how the game got there.

In basic extensive-form games, we often focus first on the structure of histories:

At the beginning, the history is empty.
After the first move, the history contains one action.
After the second move, the history contains two actions.
And so on until the game ends.

A path through the tree is simply one complete history from the root node to a terminal node. If a tree has several stages, the number of possible histories can grow quickly. This is one reason game trees are so helpful: they organize many possible sequences into a clear diagram.

Common mistakes to avoid ⚠️

When working with game trees, students sometimes mix up nodes and branches. Remember:

A node is a point.
A branch is the line connecting points.

Another common mistake is forgetting the order of moves. In a sequential game, the tree must show who acts first, second, and so on. If you reverse the order, the game changes.

It is also easy to forget terminal nodes. Every complete path should end somewhere. If a branch seems to keep going forever in a basic model, the tree may be incomplete.

Finally, do not confuse a history with a strategy. A history is what has happened so far. A strategy is a full plan that says what a player would do at every possible decision point. Strategies are important in later lessons, but here the focus is on reading the tree itself.

Conclusion

Game trees are a clear way to represent sequential games. They show the starting point, the choices at each step, the paths players can follow, and the final outcomes. students, when you can identify nodes, branches, terminal nodes, and histories, you can read many basic extensive-form games correctly.

This skill matters because many real decisions happen in sequence. A game tree helps us see how one choice creates the next one. That makes it a powerful tool for understanding dynamic choice in game theory.

Study Notes

A game tree is a diagram of a sequential game.
The root node is where the game starts.
A node is a point where a player makes a decision.
A branch shows a possible action or move.
A terminal node is an endpoint where the game finishes.
A history is the sequence of actions that has happened so far.
Each path from the root node to a terminal node is one possible outcome.
Game trees make the order of moves visible.
To read a tree, start at the root node and follow each branch in sequence.
Trees help us understand how earlier actions affect later choices.
In sequential games, the structure of the tree is just as important as the outcomes.