An extensive-form game is a representation in game theory that specifies who can act, which actions are available, what each player knows when acting, and how outcomes determine payoffs. It usually takes the form of a game tree: branches represent actions, decision nodes represent opportunities to act, and terminal nodes represent completed plays. Unlike a payoff table alone, the extensive form explicitly describes the timing and informational structure of strategic interaction, making it particularly useful for analyzing sequential decisions, threats, commitments, and learning.
Structure and formal definition
A game tree is a rooted tree, a special kind of directed graph, in which each node has a unique path from the root. The root represents the beginning of play. At a nonterminal node, either a player chooses an action or a chance event occurs. Following the corresponding branch leads to another node. A terminal node ends the play and specifies each player’s payoff.
A standard finite extensive-form game can be described using:
- A finite set of players .
- A finite set of histories , including the empty history , and containing every prefix of each history it contains.
- A set of terminal histories.
- A player function assigning each nonterminal history to a player or to chance.
- A set of available actions at each nonterminal history .
- For each player, a partition of that player’s decision histories into information sets.
- A probability distribution over available actions at each chance history.
- A payoff function for every player .
A history is a sequence of actions already taken. If , the history obtained by appending action is denoted .
Payoffs are commonly interpreted as utilities. When outcomes are random, the usual model evaluates them through expected utility. This interpretation requires more than an ordinal ranking of terminal outcomes: numerical payoff differences matter for choices among lotteries.
The tree describes the rules and possible developments of the game, not just what happens under a particular prediction. Branches that equilibrium play never reaches remain part of the game.
Information sets
An information set collects decision nodes that a player cannot distinguish when choosing an action. All nodes in one information set belong to the same player and must offer the same available actions. A player therefore cannot condition a choice on which node within that information set has actually been reached.
In diagrams, nodes in the same information set are often joined by a dashed line or enclosed within a common boundary.
For example, suppose player 1 chooses left or right, after which player 2 chooses up or down without observing player 1’s choice. Player 2’s two possible decision nodes belong to one information set. Although the drawing places player 2’s decision after player 1’s, player 2 cannot react to the earlier choice. In this way, an extensive form can represent strategically simultaneous decisions.
Perfect and imperfect information
A game has perfect information if every information set contains exactly one node. Whenever a player acts, that player knows the entire history of play. Chess, when modeled with its ordinary publicly observed moves, is an example.
A game has imperfect information if some information set contains multiple nodes. Hidden cards, unobserved actions, and simultaneous choices are common sources.
Perfect information is different from complete information. Complete information concerns knowledge of the game’s underlying characteristics, especially players’ payoff functions and types. Perfect information concerns observation of what has happened during play. A game can have known payoff functions while still containing hidden actions.
Perfect recall
A player has perfect recall if the player does not forget information previously available or actions previously taken. More precisely, histories within one of that player’s information sets must imply the same sequence of earlier information sets and own actions.
Perfect recall does not mean knowing everything that has occurred. A poker player can remember every observation and personal action while remaining ignorant of opponents’ cards.
Imperfect-recall models allow forgetting. Their strategic properties differ from those of perfect-recall games, particularly in how randomization can be represented.
Strategies and induced outcomes
An action is a choice at one decision point. A strategy is a complete contingent plan.
A pure strategy for player specifies one available action at every information set belonging to that player, including information sets that would not be reached if the strategy were followed. If player has information sets , the pure-strategy set is
Consequently, a small tree can generate many pure strategies. With information sets and two actions at each, a player has pure strategies.
There are two principal ways to introduce randomization:
- A mixed strategy is a probability distribution over complete pure strategies.
- A behavioral strategy assigns a probability distribution over actions separately at each information set.
These are not identical descriptions. A mixed strategy randomizes over complete plans, whereas a behavioral strategy specifies local randomization at decision points.
Kuhn’s theorem establishes their realization equivalence in finite games with perfect recall: for either kind of strategy, there is a strategy of the other kind that induces the same distribution over terminal histories against every fixed profile of opponents’ strategies. This equivalence can fail without perfect recall.
For a behavioral-strategy profile , the probability of a terminal history is the product of the relevant action probabilities along its path, including chance probabilities. Player ’s expected payoff is
Here, each player’s action probability depends on the information set reached, not on an unobserved node within it.
Relationship to strategic form
Every finite extensive-form game induces a normal-form game, also called a strategic-form game. Each player’s pure strategies are the complete contingent plans described above, and the payoff assigned to a strategy profile is the expected payoff generated by those plans and any chance moves.
This conversion permits the use of standard equilibrium analysis, but it can obscure the game’s sequential structure. Different extensive forms can induce the same strategic-form payoff structure while differing in which actions are observed and which continuation games can be identified.
The extensive form is therefore not merely an elaborate payoff table. Its explicit timing and information structure supports equilibrium refinements that evaluate behavior after histories that may never occur in equilibrium.
Equilibrium and sequential rationality
Nash equilibrium
A Nash equilibrium is a strategy profile in which no player can improve their expected payoff by changing their own strategy while the others’ strategies remain fixed.
Applied to an extensive-form game, this condition compares complete contingent plans. By itself, it may not impose sensible behavior at decision points that equilibrium play never reaches. In particular, an equilibrium can rely on a threat that would not be optimal to carry out.
Subgame-perfect equilibrium
A subgame begins at a decision node that is a singleton information set, includes all its successors, and does not cut across any information set. The entire game is itself a subgame.
A subgame-perfect equilibrium is a strategy profile that induces a Nash equilibrium in every subgame. This strengthens Nash equilibrium by requiring optimal strategic behavior in every properly defined continuation game, including those off the equilibrium path.
In finite games of perfect information, subgame-perfect equilibria can be found by backward induction. Starting at the final decision nodes, the analyst identifies optimal actions and then works toward the root, replacing solved continuations with their resulting payoffs. Ties can produce multiple solutions. With imperfect information, the absence of proper subgames can make subgame perfection much less restrictive.
Sequential equilibrium and beliefs
In imperfect-information games, optimal continuation choices can depend on beliefs about which node in an information set has been reached.
A sequential equilibrium specifies both behavioral strategies and beliefs at information sets. It requires:
- Sequential rationality: each player’s continuation strategy is optimal at every information set, given beliefs and the other players’ strategies.
- Consistency: strategies and beliefs arise as limits of completely mixed behavioral-strategy profiles, with beliefs calculated using Bayes’ theorem.
The limiting requirement disciplines beliefs even at information sets assigned zero probability by equilibrium play. Sequential equilibrium implies subgame perfection in finite games with perfect recall.
Example: entry and a noncredible threat
Consider a market-entry game with an entrant and an incumbent:
- The entrant chooses Stay out or Enter.
- If entry occurs, the incumbent observes it and chooses Accommodate or Fight.
- Payoffs, listed as entrant then incumbent, are:
| Outcome | Entrant | Incumbent |
|---|---|---|
| Stay out | 0 | 2 |
| Enter, Accommodate | 1 | 1 |
| Enter, Fight | −1 | −1 |
The strategy profile Stay out, Fight is a Nash equilibrium. Given the incumbent’s planned response, the entrant prefers staying out. Given that the entrant stays out, the incumbent’s planned response does not affect the realized payoff.
However, this equilibrium is not subgame perfect. If entry actually occurs, the incumbent prefers accommodating, which yields , to fighting, which yields . The threat to fight is therefore not credible under sequential optimization.
Backward induction selects Accommodate after entry, and then Enter at the initial node. This example illustrates why specifying off-path actions is necessary and why Nash equilibrium alone need not eliminate noncredible threats.
Chance and incomplete information
Chance nodes represent events not chosen strategically by a player, such as a card deal or an externally determined state. Their probabilities are part of the model; chance is not treated as a player optimizing a payoff.
Incomplete information is often represented through the Harsanyi transformation. An initial chance move selects players’ types, which may encode private information about preferences, costs, or signals. Each player observes the information specified by the model, often including their own type but not others’ types.
This converts uncertainty about underlying characteristics into imperfect information within an expanded game tree. The standard construction uses a commonly known prior distribution over types. A type need not be a psychological personality: it is a formal variable describing strategically relevant private information.
Computation and applications
Extensive-form models are used in bargaining, auctions, market entry, contracting, political competition, security interactions, and games such as poker. They are especially useful when the order of decisions, opportunities for commitment, and disclosure of information affect incentives.
Direct conversion to strategic form can be computationally expensive because the number of complete plans grows rapidly. For finite games with perfect recall, the sequence form uses realization weights for sequences of a player’s actions, subject to linear constraints. Its representation size is linear in the explicit game-tree size, avoiding the potentially exponential enumeration of pure strategies.
In two-player zero-sum games with perfect recall, this structure permits equilibrium computation through linear programming. It does not remove the difficulty of an enormous underlying tree, nor does it give the same computational guarantees for general-sum games.
Historical development and limitations
John von Neumann and Oskar Morgenstern’s Theory of Games and Economic Behavior (1944) helped establish the systematic study of strategic interaction. Harold Kuhn’s work in 1953 developed a standard framework for extensive games and established the central equivalence result for mixed and behavioral strategies under perfect recall. Later work on subgame perfection and sequential equilibrium sharpened the analysis of credible continuation behavior.
An extensive-form model requires explicit assumptions about available actions, observation, memory, chance probabilities, and payoffs. Changing an information set can change the strategic problem even when the displayed terminal payoffs remain unchanged.
Large trees are difficult to construct and solve, and equilibrium may be nonunique. Standard equilibrium analysis also assumes strategically consistent optimization; bounded reasoning, mistakes, and learning require additional modeling choices. Games with infinite horizons or continuous action spaces need further mathematical assumptions, so results for finite trees do not automatically extend to them.