Extensive Form Representation of Sequential Games

1. From Matrices to Trees

In a simultaneous game, the payoff matrix captures everything we need: players, strategies, and payoffs. But it inherently hides the temporal structure of the game. If Player 1 moves first and Player 2 observes that move before making their own, a matrix isn't the most intuitive way to show this.

The extensive form, or game tree, is a more powerful representation for these dynamic situations. It visually maps out every possible sequence of moves in the game.

As the video explains, a game tree consists of:

• Nodes: Points in the game where a decision is made or the game ends.
• Branches: The actions available to a player at a decision node.
• Payoffs: The outcomes for each player at the end of the game.

2. The Anatomy of a Game Tree

Let's formalize the components of a game tree. Understanding this vocabulary is crucial for both drawing and interpreting them.

Here are the key elements defined:

1. Initial Node (or Root): The single starting point of the game.
2. Decision Nodes: Points where a player must choose an action. Each decision node is assigned to a specific player.
3. Terminal Nodes (or Leaves): The endpoints of the game. No more actions can be taken. Each terminal node has a corresponding set of payoffs for all players.
4. Branches: These connect the nodes and represent the actions a player can take.
5. Path: A sequence of nodes and branches from the initial node to a terminal node, representing one possible playthrough of the game.

3. A Classic Example: The Entry Game

Let's apply these concepts to a classic scenario. Imagine a new startup (the Entrant) considering entering a market dominated by an established firm (the Incumbent).

• Player 1 (Entrant): Moves first. Can choose to Enter the market or stay Out.
• If the Entrant stays Out, the game ends. The Entrant gets a payoff of 0, and the Incumbent keeps its monopoly profit of 2.
• If the Entrant Enters, the game continues.
• Player 2 (Incumbent): Observes the entry. Can choose to Fight the new competitor (e.g., by starting a price war) or Accommodate them.
• If the Incumbent Fights, both firms suffer. The Entrant gets -1, and the Incumbent gets -1.
• If the Incumbent Accommodates, they share the market. The Entrant gets 1, and the Incumbent gets 1.

How would you draw this as a game tree? Take a moment to sketch it out using the components we've defined.

Click here to see the game tree for the Entry Game.

Here is the extensive form representation of the Entry Game. Compare it to your sketch.

4. The Formal Rules of a Game Tree

Not every tree-like diagram is a valid game tree. For our analysis to be sound, a game tree must adhere to a strict set of rules. Your interest in mathematical rigor will be well-served by understanding these formal properties.

To summarize the essential rules from the video:

1. Single Initial Node: Every game tree has exactly one starting point (initial node), which has no predecessors.
2. Unique Path to the Top: Every node other than the initial one has exactly one immediate predecessor. This ensures there are no "loops" and that the history leading to any point in the game is unique.
3. Distinct Action Labels: All branches extending from the same decision node must have different action labels. A player cannot have two identical choices at the same point in time.
4. Player Ownership of Information Sets: We'll define information sets shortly, but the rule states that all decision nodes within a single information set must belong to the same player.
5. Consistency within Information Sets: All nodes within the same information set must have the same number of outgoing branches, with the exact same set of action labels. This ensures that a player who is uncertain about their exact position still knows what their available actions are.

5. Perfect vs. Imperfect Information

So far, in our Entry Game example, the Incumbent knew that the Entrant had chosen to Enter. The Incumbent was at a specific, known decision node. This is called a game of perfect information.

A game has perfect information if, at every move, the player whose turn it is knows the full history of the game up to that point. In a game tree, this means every decision node is in its own information set.

What if a player doesn't know the previous move? This is a game of imperfect information. We represent this by grouping decision nodes into an information set, often drawn with a dashed line or a circle connecting them. A player knows which information set they are in, but not which specific node within that set.

This game tree represents a simultaneous game. Player 2's two decision nodes are connected by a dashed line, forming a single information set. This signifies that Player 2 does not know whether Player 1 chose 'Boxing' or 'Opera' when making their own decision.

This diagram shows that Player 2 must make a choice without knowing Player 1's action. Because Player 2 doesn't know whether they are at the left node or the right node, their choice must be consistent across both (as required by Rule 5). This is how we use a game tree to represent a simultaneous game, like the ones we studied before.

6. A Crucial Distinction: Actions vs. Strategies

In simultaneous games, the terms "action" and "strategy" were interchangeable. In sequential games, they mean very different things. This is one of the most important conceptual shifts in this module.

• An action is a single choice made at a single decision node (e.g., the Incumbent choosing 'Fight').
• A strategy is a complete, contingent plan of action. It specifies what action a player will take at every single one of their decision nodes, regardless of whether that node is actually reached during play.

Let's revisit the Entry Game.

• The Entrant has only one decision node and two actions: {Enter, Out}. So, the Entrant's strategies are simply: 1. Enter, 2. Out.
• The Incumbent also has only one decision node (after the Entrant plays Enter) with two actions: {Fight, Accommodate}. So, the Incumbent's strategies are: 1. Fight, 2. Accommodate.

Now consider a slightly more complex game:

A game tree where Player 1 chooses A or B. If A, Player 2 chooses C or D. If B, Player 2 chooses E or F.

What are Player 2's strategies? Player 2 has two decision nodes. A strategy must specify a plan for both.

• Action at the top node (if P1 plays A): {C, D}
• Action at the bottom node (if P1 plays B): {E, F}

A strategy for Player 2 is a pair of actions, one for each contingency. The set of pure strategies for Player 2 is:

1. (C, E) - "I will play C if P1 plays A, and E if P1 plays B."
2. (C, F) - "I will play C if P1 plays A, and F if P1 plays B."
3. (D, E) - "I will play D if P1 plays A, and E if P1 plays B."
4. (D, F) - "I will play D if P1 plays A, and F if P1 plays B."

Player 2 has four pure strategies, even though they will only ever take one action in any single playthrough. This concept of a complete plan is fundamental to solving sequential games.

Conclusion

In this lesson, you have learned the graphical language of sequential games. We have moved from the static world of matrices to the dynamic world of trees, which explicitly captures the sequence and information available to players at each step.

Key Takeaways:

• Sequential games are represented in extensive form using game trees.
• A game tree is built from nodes (initial, decision, terminal) and branches (actions).
• A valid game tree must follow specific formal rules that ensure its logical consistency.
• Perfect information means players know the full history of play (all information sets are singletons). Imperfect information involves uncertainty, represented by information sets containing multiple nodes.
• In sequential games, a strategy is a complete, contingent plan of action that specifies a choice for every possible decision node a player might face.

You are now equipped to represent complex, dynamic strategic interactions. In our next lesson, we will build directly on this foundation. We will define the concepts of subgames and Subgame Perfect Nash Equilibrium (SPNE), and learn the powerful algorithm of backward induction to solve these games and find the most credible strategic outcomes.