Lecture 18: Imperfect Information, Information Sets and Subgame Perfection

What this lecture covers

This lecture bridges the two halves of the course: simultaneous-move games (analyzed with Nash equilibrium, before the midterm) and sequential-move games under perfect information (analyzed with backward induction, after the midterm). It introduces the information set, a formal tool for representing what a player does or does not know at a given point in a game tree, and uses it to show that any simultaneous-move game can be redrawn as a tree, and vice versa. The lesson is that what matters for a game's structure is information, not the order in which moves happen.

The second half of the lecture shows why plain Nash equilibrium is not good enough once games mix sequential and simultaneous elements: some Nash equilibria rely on players making empty threats they would never actually carry out. To fix this, the lecture defines a subgame formally and introduces subgame perfect equilibrium, a refinement that requires equilibrium play in every subgame, not just the game as a whole. This sets up the tool used for the rest of the course, including bargaining and repeated games.

Key ideas

• Information set: a collection of a player's decision nodes that the player cannot tell apart, drawn as a dotted line connecting the nodes in a game tree.
• Perfect vs. imperfect information: perfect information means every information set contains exactly one node; imperfect information is everything else.
• Valid information sets: nodes in the same information set must offer the same number of choices, and a player cannot forget their own earlier move (the "perfect recall" assumption).
• Strategy under imperfect information: a strategy specifies an action at each information set, not at each individual node, since a player cannot condition on information they do not have.
• Trees and matrices are interchangeable: any simultaneous-move game (like Prisoners' Dilemma) can be drawn as a tree with an information set, and any tree can be converted into a normal-form payoff matrix.
• Time versus information: what determines whether a game behaves as "simultaneous" is whether players know each other's moves before deciding, not the literal timing of those moves.
• Nash equilibrium can be implausible in dynamic games: some Nash equilibria of the induced matrix rely on off-path behavior that contradicts backward induction, i.e., an empty threat.
• Subgame: a piece of the tree that starts at a single node, includes all of that node's successors, and does not split any information set.
• Subgame perfect equilibrium (SPE): a Nash equilibrium of the whole game that also induces a Nash equilibrium in every one of its subgames, ruling out equilibria built on non-credible threats.

Walkthrough

From perfect to imperfect information: a first example (0:01)

The lecture starts with a familiar perfect-information tree solved by backward induction, then modifies it so Player 2 cannot distinguish between two of Player 1's opening moves. Connecting those two nodes with a dotted line introduces the information set. The example shows that once Player 2 cannot tell which node she is at, Player 1's incentives change completely, since Player 1 can no longer be "crushed" by an opponent who observed the exact move.

Formal definitions: information sets, rules, and perfect/imperfect information (around 9:30)

The lecture defines an information set formally and states two rules that a valid information set must satisfy: nodes within it must offer the same number of available choices, and information sets cannot violate perfect recall (a player must remember their own past moves). It also gives the formal definitions of perfect information (every information set is a single node) and imperfect information (the rest), then adapts the definition of a strategy to specify play at each information set rather than each node.

Rebuilding familiar games as trees (around 18:46)

Using a two-player example with an information set, the lecture shows the resulting game reduces to the classic Prisoners' Dilemma matrix, demonstrating that simultaneous-move games are really just trees where neither player observes the other's move before choosing. It then works through converting a more general tree into a matrix and back again, showing that two trees that look temporally different (Player 1 moves first vs. Player 2 moves first) can represent the exact same game once you account for who knows what and when.

A tree with a repeated decision, and the failure of plain Nash equilibrium (around 35:10)

A richer three-move tree is converted into a matrix with four strategies for Player 1 (since a strategy must specify choices at every information set, even ones that will never be reached). Solving for Nash equilibria yields three candidates, but working through the tree with backward-induction reasoning shows two of them rely on Player 1 threatening to choose an option she would never actually pick if that part of the tree were reached, exposing them as implausible.

Subgames and the case for a stronger solution concept (around 49:59)

A second, three-player example reinforces the point: a matrix-derived Nash equilibrium turns out to prescribe non-equilibrium play in a smaller "game within the game" that starts once Player 1 makes a particular choice. The lecture formalizes this game-within-a-game as a subgame, defined by three requirements: it starts at a single node, includes all of that node's successors, and never splits an information set.

Subgame perfect equilibrium and worked examples (around 1:10:37)

The lecture defines subgame perfect equilibrium: a Nash equilibrium that also induces a Nash equilibrium in every subgame of the game. Applying this to both earlier examples eliminates the implausible equilibria and leaves the intuitively correct outcomes, matching what backward-induction reasoning would predict. This closes the lecture's transition from Nash equilibrium and backward induction toward a single unified solution concept for games with both sequential and simultaneous elements.

Before you watch

• Be solid on Nash equilibrium and payoff matrices from the first half of the course.
• Be comfortable with backward induction and game trees from the sequential-move lectures, including the entry game example referenced here.
• Reviewing how strategies were defined for perfect-information games will make the updated definition easier to follow.

Check your understanding

1. What makes a collection of nodes a valid information set, and what two conditions would make an information set drawing invalid?
2. Why does a strategy need to specify an action at every information set, even ones that will not be reached under that same strategy?
3. Explain, using the lecture's example, how the same game can be represented with Player 1 moving first or Player 2 moving first without changing the outcome.
4. Why can a Nash equilibrium of the normal-form matrix correspond to an "empty threat" when the game is actually played as a tree?
5. What three conditions must a piece of a game tree satisfy to count as a subgame, and how does subgame perfect equilibrium use that definition to rule out implausible Nash equilibria?