The Grammar of Games
Matrices, Trees, and Information

Notation Is a Tool for Thinking

Every scientific discipline needs a notation. Chemists have structural formulas. Musicians have staff notation. Mathematicians have equations. In each case, the notation is not merely a way to record what is already understood — it is a tool for thinking. A good notation makes certain relationships visible that would otherwise remain hidden. A poor one buries the essential structure under irrelevant detail.

Game theory is no different. Over the past century, game theorists have developed two primary representations for strategic situations, each with its own strengths and blind spots. The normal form, also called the strategic form, compresses a game into a payoff matrix — a compact grid that displays every player's available strategies and the outcomes they produce. The extensive form unfolds a game through time as a branching tree, revealing the sequential architecture of decisions and the information available at each moment of choice, as Osborne and Rubinstein described in 1994.

These are not interchangeable notations for the same thing, the way Celsius and Fahrenheit are interchangeable scales for temperature. Rather, they are genuinely different ways of seeing a strategic situation. A payoff matrix foregrounds the simultaneous, all-at-once nature of strategy choice: you pick a row, I pick a column, and the resulting cell gives us our payoffs. A game tree foregrounds sequence and information: who moves first, what they know when they move, and how each choice opens or forecloses future possibilities. As Myerson emphasised in 1991, these different representations naturally lead to different equilibrium analyses — different ways of asking "what should a rational player do?"

We will spend this chapter becoming fluent in both languages. By the end, you will be able to translate verbal descriptions into precise formal representations, convert between normal and extensive form for simple games, and — most importantly — understand why the choice of representation is not merely cosmetic. It is strategic in its own right.

The Normal Form · A Game as a Grid

The simplest and most widely recognised representation of a game is the payoff matrix. You likely encountered one in Chapter 1 when we introduced the Prisoner's Dilemma. Let's formalise what's happening in that clean grid of numbers.

A game in normal form consists of three elements, as Osborne and Rubinstein outlined in 1994. First, a set of players. We typically label them Player 1, Player 2, and so on, or give them descriptive names like Firm A, Firm B, or Alice and Bob. Second, a set of strategies for each player — the complete plans of action from which they must choose one. Third, a payoff function. For every combination of strategies, one chosen by each player, the payoff function assigns a numerical outcome to each player.

For a two-player game where Player 1 has m strategies and Player 2 has n strategies, we can arrange all of this into an m × n matrix. Player 1's strategies label the rows; Player 2's strategies label the columns. Each cell contains a pair of payoffs: Player 1's payoff, then Player 2's payoff. Consider a classic example — the Battle of the Sexes, sometimes updated as the Coordination Game. Two friends, Alex and Blake, want to spend the evening together but have different preferences. Alex prefers the opera; Blake prefers the football match. Going to the same event together is better for both than going to different events alone.

The beauty of this representation is its compression. In a single glance, you can see every possible outcome and every player's incentive structure. You can immediately start asking questions like: Is there a strategy that is best for Alex regardless of what Blake does? No — it depends on Blake's choice. Are there any outcomes where neither player would want to unilaterally deviate? Yes, but we'll formalise this as Nash Equilibrium in Chapter 3.

The Extensive Form · A Game as a Tree

Suppose we change the Battle of the Sexes so that Alex chooses first and Blake sees Alex's choice before deciding. The matrix can still represent this game — we'll see how shortly — but it does so awkwardly, obscuring the sequential structure that defines the strategic situation. To see that structure clearly, we need a different language entirely.

The extensive form represents a game as a tree — a branching diagram that unfolds from a single root through decision points to final outcomes. The concept was formalised by Harold Kuhn in his seminal 1953 paper, which gave us the mathematical framework still used today. A game tree consists of several elements.

First, nodes. These are the points in the tree. There are three types: a single root node where the game begins, decision nodes where a player must choose an action, and terminal nodes where the game ends and payoffs are assigned. Second, branches. Each branch emanating from a decision node represents one available action. Third, player assignments. Each decision node is assigned to the player who moves at that point. Fourth, payoff vectors. Each terminal node is labelled with a list of payoffs, one for each player. And fifth, information sets. We'll come to these shortly — they capture what a player knows at the moment of decision.

The sequential Battle of the Sexes

Alex chooses first between Opera and Football. Blake observes Alex's choice, then chooses between Opera and Football. The game tree has a root node where Alex decides, two decision nodes for Blake — one reached after Alex chooses Opera and the other after Alex chooses Football — and four terminal nodes with the same payoffs as in our matrix.

Notice what the tree makes visible that the matrix obscured: Blake gets to see what Alex did before choosing. This is an enormous strategic advantage. Blake can simply follow Alex to whichever event Alex chose, guaranteeing coordination. And Alex, knowing this, should choose Opera — Alex's preferred event — expecting Blake to follow. The sequential structure completely resolves the coordination problem that made the simultaneous version so tricky. This insight is essentially invisible in the payoff matrix but jumps off the page in the game tree, as Levin noted in 2002.

Strategy ≠ Action

Here is where many students — and even some textbooks — get tripped up. In everyday language, "strategy" and "action" are nearly synonymous. In game theory, they are profoundly different concepts, and confusing them leads to serious errors in analysis.

An action, sometimes called a move, is a single choice made by a player at a particular decision node. In the sequential Battle of the Sexes, "Blake chooses Opera" is an action — a choice made at one specific moment in the game.

A strategy, by contrast, is a complete contingent plan — a specification of what action a player would take at every decision node where that player might be called upon to act, as Osborne and Rubinstein explained in 1994. This includes decision nodes that the player's own earlier choices may have made unreachable.

This last point is crucial and counterintuitive, so let's dwell on it. In the sequential Battle of the Sexes, Blake has two decision nodes: one reached if Alex chose Opera, another reached if Alex chose Football. A strategy for Blake must specify an action at both nodes. So Blake's strategies are not simply "Opera" or "Football" but rather complete plans.

Blake could plan "Opera if Alex chose Opera, Opera if Alex chose Football" — always go to the Opera regardless. Or "Opera if Alex chose Opera, Football if Alex chose Football" — match Alex's choice, the follow strategy. Or "Football if Alex chose Opera, Opera if Alex chose Football" — do the opposite of Alex, the contrary strategy. Or finally, "Football if Alex chose Opera, Football if Alex chose Football" — always go to Football regardless.

Blake has four strategies, not two — even though Blake only has two actions at any given node. This is because a strategy is a function that maps every information set to an action, as Fudenberg and Tirole described in 1991. The number of strategies grows multiplicatively: if a player has k decision nodes, each with 2 possible actions, that player has 2^k strategies.

A strategy is a complete contingent plan of action for a player: it specifies a feasible action for the player at every node at which it would be that player's turn to move, even at nodes that will not be reached given the other actions specified by the strategy.

MIT OpenCourseWare, 2012

Why insist on specifying actions at unreachable nodes? Because the threat of what you would do at an unreachable node can influence other players' behaviour, making it reachable — or keeping it unreachable precisely because the threat is credible. We'll explore this idea in depth when we study subgame perfect equilibrium in Chapter 5. For now, the essential point is this: a strategy is a complete algorithm for playing the game, telling you what to do in every conceivable situation, including situations you plan to avoid, as Wikipedia contributors noted in 2025.

Perfect and Imperfect Information

So far, our game trees have assumed that every player can observe everything that happened before their turn. Blake saw Alex's choice; Café B observed Café A's location. Games where every player can see all previous moves are called games of perfect information — chess, tic-tac-toe, and the sequential games we've examined so far are all examples, as Aumann and Hart discussed in 2002.

But most real-world strategic situations involve imperfect information: a player must make a choice without knowing exactly what has happened before. Poker is the paradigmatic example — you cannot see your opponent's hole cards, so when you decide to bet or fold, you don't know which node of the game tree you're actually at. In a simultaneous-move game like the original Battle of the Sexes, Blake chooses without knowing Alex's choice, even though we might draw the tree with Alex's node "first" for visual convenience.

The information set

The formal device for capturing imperfect information is the information set, introduced by Kuhn in 1953. An information set groups together decision nodes that a player cannot distinguish between at the moment of choice. When two or more nodes belong to the same information set, the player at those nodes must be the same person, the available actions must be the same, and — crucially — the player cannot tell which node they're at.

Here's one of the most elegant insights in game theory: a simultaneous game can be represented in extensive form by treating it as a sequential game with imperfect information, as Levin explained in 2002. Return to the original simultaneous Battle of the Sexes. We can draw the tree with Alex moving "first" and Blake moving "second" — but we indicate that Blake's two decision nodes form a single information set, meaning Blake cannot observe Alex's choice. From Blake's perspective, the situation looks identical whether Alex chose Opera or Football.

This is why every normal-form game can be represented in extensive form, and vice versa. The two representations are translatable, though the translation can be revealing. When we convert a simultaneous game to extensive form, we must add information sets to capture the simultaneity. When we convert a sequential game to normal form, we must enumerate all complete contingent plans as strategies — which is why the normal-form version of even a simple sequential game can have a surprisingly large strategy set.

The distinction is clean: a game has perfect information if every information set contains exactly one node — at every decision point, the player knows precisely where they are in the tree. A game has imperfect information if at least one information set contains multiple nodes — somewhere in the game, some player must choose without knowing what happened earlier, as Fudenberg and Tirole noted in 1991. This distinction has profound consequences for analysis. Games of perfect information can be solved by backward induction — reasoning backward from the end of the tree — and are guaranteed to have equilibria in pure strategies, according to Aumann and Hart in 2002. Games of imperfect information are generally harder: they may require mixed strategies, or randomisation, and the appropriate solution concept may be more demanding than simple Nash equilibrium.

Matching Pennies · A Game With No Pure Equilibrium

One canonical example of imperfect information is matching pennies: two players simultaneously reveal a penny, each showing Heads or Tails. If the pennies match, Player 1 wins; if they mismatch, Player 2 wins. There is no pair of pure strategies that constitutes an equilibrium — whatever Player 1 picks, Player 2 wants to mismatch; whatever Player 2 picks, Player 1 wants to match. The arrows chase each other around the matrix without ever settling.

Drawn in extensive form, matching pennies is a tree with one player at the root and the other player's two decision nodes joined in a single information set — because the second mover cannot see the first mover's coin. This is the same imperfect-information construction that we just used to render the simultaneous Battle of the Sexes, applied to a zero-sum game. The lesson generalises: any genuinely simultaneous game can be drawn as a tree with imperfect information, and the position of the information set is what does all the strategic work.

Translation · Tree to Matrix, Matrix to Tree

Now that we have both languages in hand, let's practise translation. The ability to move fluidly between normal form and extensive form is one of the most valuable technical skills in applied game theory, as Myerson argued in 1991.

The conversion from a game tree to a payoff matrix is always possible. The procedure is straightforward. First, enumerate every strategy for each player — remember, a strategy is a complete contingent plan specifying an action at every information set. Second, for each combination of strategies, trace through the tree to determine the terminal node reached and the corresponding payoffs, as Levin described in 2002.

For the sequential Battle of the Sexes, Alex has 2 strategies — Opera or Football — and Blake has 4 strategies, the four contingent plans listed earlier. The resulting normal-form matrix is therefore 2 by 4. If Alex chooses Opera and Blake's strategy is the follow plan ("Opera if Alex chose Opera, Football if Alex chose Football"), then the game reaches the Opera–Opera terminal node with payoffs (3, 2). If Alex chooses Football and Blake's strategy is the same follow plan, the game reaches Football–Football with payoffs (2, 3). You fill in every cell this way. Notice that the 2 × 4 matrix is larger than the original 2 × 2 simultaneous version. The additional columns represent the additional strategic richness that sequential play creates — Blake's ability to condition on Alex's observed move.

Going the other direction — from matrix to tree — requires a key choice: who moves first? For a simultaneous game, there is no "first mover" — but in the extensive form, we must draw someone's node at the top. The trick is that we use information sets to erase the artificial sequencing we've imposed. Either player can be drawn first, as long as the second player's nodes are connected in a single information set, indicating they can't observe the first player's move. This produces two different-looking trees that are strategically identical — both equivalent to the original simultaneous game, as Levin explained in 2002.

This is a profound observation: multiple different extensive forms can correspond to the same normal form. The normal form is "coarser" — it throws away information about timing and observability that the extensive form preserves. Two games with very different sequential structures — one where Player 1 moves first but unobserved, another where Player 2 moves first but unobserved — can yield identical payoff matrices.

Both Views, Side by Side

Let's bring all these ideas together by examining how the simultaneous and sequential versions of the Battle of the Sexes look in both representations. In the simultaneous Battle of the Sexes, the normal form is a 2 × 2 matrix with strategies Opera and Football for each player. Two Nash equilibria exist: Opera–Opera and Football–Football — but the game itself gives no mechanism for coordinating on one. In extensive form, it's a tree with either player drawn at the root. Crucially, the second player's two decision nodes are in a single information set because the second player cannot observe the first player's choice. This information set is what makes the game genuinely simultaneous despite being drawn sequentially.

In the sequential Battle of the Sexes, the extensive form is a tree with Alex at the root and Blake's two decision nodes in separate information sets, each containing one node, because Blake observes Alex's choice. The backward induction solution is clear: Alex chooses Opera, Blake follows. The normal form is a 2 × 4 matrix — Alex has 2 strategies; Blake has 4. The additional strategies for Blake reflect the richer strategic possibilities that observation creates. This matrix has multiple Nash equilibria, some of which involve Blake making "incredible threats" — plans that Blake would not actually follow through on if the relevant node were reached. Identifying and eliminating such threats requires the concept of subgame perfect equilibrium, which we'll develop in Chapter 5.

The key lesson: the same underlying strategic interaction looks fundamentally different depending on the representation and the information structure. Changing whether a move is observed can transform the entire strategic logic of a game.

Common knowledge, revisited

In Chapter 1 we introduced common knowledge — the infinite regress of mutual knowledge that lets the Prisoner's Dilemma logic go through. Information sets are how that idea enters the formal grammar of games. In game theory, we typically assume the structure of the game itself — who the players are, what strategies are available, what the payoffs are, and which nodes share an information set — is common knowledge. When we then add an information set joining two nodes, we are saying not just "Blake can't observe Alex's move," but "Alex knows Blake can't observe, Blake knows that Alex knows, Alex knows that Blake knows that Alex knows…" all the way down. The information set is common knowledge of imperfect information.

The Budget Game · One Example, Both Forms

Let's close with an example that exercises all the concepts from this chapter. Consider a simplified model of a legislative process. A committee chair, Player 1, proposes either a High budget or a Low budget. A ranking member, Player 2, then decides to Accept or Amend the proposal — and Player 2 can observe the proposal, so this is a game of perfect information.

In extensive form, this game has a rich tree structure: Player 1's node at the root, Player 2's nodes in separate information sets since Player 2 observes the proposal. To convert to normal form, we must enumerate Player 2's strategies — complete contingent plans specifying an action at every information set. Player 2 has two information sets, one after High and one after Low, each with two actions — Accept or Amend — giving 2 × 2 = 4 strategies. Player 1 has 2 strategies. The normal form is a 2 × 4 matrix.

Now suppose we change the game so that Player 2 could not observe whether the proposal was High or Low — perhaps the vote is on a motion whose content hasn't been fully disclosed. Player 2's two decision nodes would collapse into a single information set. Player 2 would now have only 2 strategies — Accept or Amend, applied blindly — and the normal form would shrink to a 2 × 2 matrix. The information structure, represented by information sets in the extensive form, directly determines the strategy sets and the dimensions of the normal form.

This is the fundamental insight of this chapter: representation is not just bookkeeping. The way you model information — who knows what when — is itself a strategic choice that shapes the entire analysis. In Kuhn's words from 1953, the extensive form with information sets provides the "complete description" of a game. Everything else — normal form, solution concepts, equilibrium predictions — is derived from it.

Four Pitfalls Students Walk Into

1 · Confusing strategies with actions

An action is a single move at a single node. A strategy is a complete plan for every node where you might act. If you find yourself saying "Player 2's strategy is to choose Left," ask: at which information set? What does Player 2 do at every other information set? A strategy must answer all these questions.

2 · Forgetting to specify actions at unreachable nodes

A strategy must cover nodes that your own earlier choices have made unreachable. This feels wasteful, but it's essential — other players' behaviour may depend on what they believe you would do at those nodes.

3 · Drawing a sequential tree for a simultaneous game without information sets

If you represent a simultaneous game in extensive form, you must indicate that the second mover's decision nodes form an information set. Without this, you've drawn a sequential game — a fundamentally different strategic situation.

4 · Assuming the normal form preserves all information

Converting from extensive form to normal form is always possible, but information may be lost. Two different game trees with different information structures can yield identical payoff matrices. The matrix is a projection, not a complete picture.