Subgame

In game theory, a subgame is a subset of an extensive-form game that begins at a specific non-terminal node and includes all subsequent nodes, branches, information sets, and terminal payoffs, allowing it to be analyzed as a standalone game with the same rules and structure as the original.^[1]^[2] This structure ensures that the subgame has a unique starting point where the history up to that node is fully specified, and any information set containing a node in the subgame must be entirely included to preserve player beliefs and decision-making.^[1] Subgames are fundamental to refining solution concepts in dynamic games, particularly through the notion of subgame perfection, which requires strategies to form a Nash equilibrium not only in the full game but in every subgame as well.^[2] The concept of a subgame, introduced in the context of extensive-form games by Harold W. Kuhn in the 1950s, enables the elimination of non-credible threats or promises by applying backward induction starting from subgame endpoints.^[3] For instance, in sequential games like the centipede game, multiple subgames exist at each decision node, allowing analysis of player incentives at every stage.^[2] This refinement leads to subgame-perfect Nash equilibria (SPNE), which are more robust than standard Nash equilibria because they account for off-equilibrium behaviors in subgames.^[2] Subgames apply primarily to perfect-information games but extend to imperfect-information settings where information sets are respected, influencing applications in economics, political science, and computer science for modeling multi-stage interactions.^[1]

Basic Concepts

Extensive-Form Games

Extensive-form games provide a foundational representation in game theory for modeling sequential decision-making processes, where the order of moves and potential information asymmetries are explicitly captured. These games are depicted as tree diagrams, with non-terminal nodes representing decision points for players, branches illustrating possible actions available at each node, and terminal nodes specifying the payoffs received by each player upon reaching the end of a play path. This structure allows for the analysis of dynamic interactions, including games with perfect information, where players observe all prior actions, and imperfect information, where some history may be hidden. The key components of an extensive-form game include a set of players, sequences of actions leading to histories, and payoff assignments. In cases of imperfect information, information sets partition the decision nodes, grouping those indistinguishable to the acting player based on their available observations. A strategy in this framework is defined as a complete contingent plan for a player, specifying an action for every information set at which that player moves, ensuring the representation accounts for all possible decision contingencies. The extensive form was formalized by Harold W. Kuhn in his 1953 paper "Extensive Games and the Problem of Information," which introduced the tree-based approach to handle informational aspects in sequential games. Formally, such a game is denoted as \Gamma = (N, A, H, P, u), where N is the set of all nodes in the tree, A the set of feasible actions, H the set of histories (finite sequences of actions leading to nodes), P: H \setminus Z \to I the player function assigning a player i \in I to each non-terminal history (with Z denoting terminal histories), and u: Z \to \mathbb{R}^I the payoff function mapping terminal histories to payoff vectors for the players. Subgame perfect equilibrium serves as a primary solution concept for refining outcomes in these games by eliminating non-credible threats.

Definition of a Subgame

In extensive-form games, a subgame is a self-contained subset that begins at a non-terminal decision node and encompasses all subsequent nodes, actions, and outcomes, effectively forming an independent game embedded within the larger structure.^[2] This core definition ensures that the subgame inherits the original game's rules, payoffs, and player roles from that starting point onward, allowing it to be analyzed separately without altering the strategic incentives.^[4] Unlike mere histories or paths, which represent specific sequences of actions leading to particular outcomes, subgames must be "closed" under the game's structure, meaning they include every possible continuation from the initial node rather than selective trajectories, thereby preserving the full decision-making environment as a standalone extensive-form game.^[5] The formal criteria for identifying a subgame are threefold: first, it must contain a single initial non-terminal node; second, it includes all possible future actions, branches, and terminal payoffs reachable from that node; and third, in games with imperfect information, it respects the information partitions by ensuring that no information set is split—every information set containing a successor of the initial node must consist entirely of successors of that node.^[4] This last condition is crucial for maintaining the integrity of players' beliefs and strategies within the subgame, preventing scenarios where partial observability from the parent game disrupts the subgame's coherence.^[5] For illustration, in perfect-information extensive-form games represented as trees, every non-terminal node initiates a subgame because there are no overlapping information sets to complicate containment.^[2] In contrast, imperfect-information games restrict subgames to those nodes where all associated information sets are fully contained within the successors, excluding nodes that would fragment players' uncertainty across the boundary.^[4]

Formal Properties

Conditions for Subgame Identification

To identify a subgame within an extensive-form game, a candidate portion must satisfy several necessary conditions rooted in the game's tree structure. First, it requires a unique starting node, from which the subgame consists of the entire subtree including all descendant nodes and the associated actions, ensuring no truncation of paths.^[6] Second, the subgame must preserve the original payoff structure, meaning terminal nodes within it yield the same payoffs as in the full game, without alteration or external dependencies.^[6] These conditions ensure the subgame is a self-contained strategic environment that mirrors the broader game's mechanics at its conclusion. In games with imperfect information, an additional rule applies to maintain informational consistency: no information set intersecting the subgame can contain nodes both inside and outside it. Formally, for every information set I in the game, if I intersects the subtree rooted at the starting node x, then I must be entirely contained within that subtree. This requirement, often referred to as Kuhn's condition for subgame initiation, prevents the subgame from inheriting unresolved uncertainty from the parent game, as players must be able to distinguish the subgame's context without links to external histories. Violation of this rule disqualifies a candidate, as it would imply players in the subgame face information sets that are incomplete or contaminated by prior branches. Common pitfalls in subgame identification arise particularly in imperfect-information settings, where information sets span multiple branches. For instance, if a proposed subgame rooted at node x includes only part of an information set—such as one node from a set linking to both included and excluded paths—the structure fails, as the set cannot be split without distorting player knowledge.^[7] Another frequent error occurs when overlooking non-terminal nodes whose successors straddle information sets; even if the node appears isolated, any intersecting set not fully included invalidates the subgame, leading to analyses that overlook strategic spillovers.^[7] An algorithmic check provides a systematic way to verify subgame status in a game tree:

Select a candidate starting node x (non-terminal).
Construct the subtree T_x as all nodes reachable from x, including actions and terminal payoffs.
For each information set I in the full game, test intersection: if any node in I belongs to T_x, confirm all nodes in I are also in T_x.
If the test passes for all relevant I, and payoffs are unchanged, T_x qualifies as a subgame; otherwise, reject.^[8] This process, applicable to both perfect and imperfect information, highlights why many imperfect-information games lack proper subgames beyond the whole tree.^[8]

Proper and Induced Subgames

A proper subgame in an extensive-form game is any subgame that excludes the root node of the original game tree, thereby commencing from a subsequent decision node and encompassing all its descendants. This distinction ensures that proper subgames capture continuations of play after initial actions, excluding the full game structure itself. The original game always qualifies as a subgame, but proper subgames are strictly subsets, facilitating focused analysis of later stages without revisiting the outset.^[9] An induced subgame refers to a proper subgame that arises with positive probability following a specific strategy profile, meaning it lies on a path consistent with the players' planned actions. Such subgames are structurally identical to standard proper subgames but are delimited by the probabilities implied by the strategies, emphasizing reachable continuations rather than all possible branches. This notion underscores variations in subgame structure tied to strategic choices, though it remains rooted in the game's tree without altering the underlying rules.^[10] Every extensive-form game possesses itself as a subgame, with proper subgames forming the collection of all valid continuations from non-root nodes. In finite extensive-form games, the number of proper subgames is finite. In perfect-information games, where all information sets are singletons, this number directly corresponds to the finite count of non-terminal histories in the game tree. In imperfect-information games, the number is smaller, corresponding only to those non-terminal histories that satisfy the subgame identification conditions. These finiteness properties hold regardless of information structure, ensuring a countable set of analyzable segments.^[9] The identification of proper and induced subgames relates closely to the game's tree architecture. In perfect-information games, where all information sets are singletons, every non-terminal node initiates a proper subgame, yielding a subgame at each decision point. Conversely, in imperfect-information games, proper subgames are fewer, as they require the initiating node to belong to a singleton information set that satisfies the subgame condition—preserving all subsequent information sets intact—thus restricting subgames to points of full observability. Induced subgames inherit these constraints but are further filtered by strategy-induced reachability. These classifications presuppose the conditions for subgame identification, such as non-interruption of information sets.^[10]

Equilibrium Analysis

Subgame Perfect Equilibrium

A subgame perfect equilibrium (SPE) is a refinement of the Nash equilibrium concept specifically designed for extensive-form games, ensuring that the strategies prescribed remain optimal even in every possible subgame of the original game. Introduced by Reinhard Selten in 1965, an SPE requires that a strategy profile induces a Nash equilibrium in every subgame, thereby eliminating equilibria that rely on non-credible off-equilibrium-path behaviors.^[11]^[12] This concept addresses limitations in standard Nash equilibria, which may sustain outcomes through implausible threats or promises that players would not rationally follow if the game reached certain points. Formally, consider an extensive-form game represented as a game tree, where a subgame is a portion of the tree starting from a non-terminal node such that every information set that intersects the subgame is entirely contained within it. A strategy profile \sigma = (\sigma_1, \dots, \sigma_n) for players $1 to n constitutes an SPE if, for every subgame beginning at a node x, the restricted strategies \sigma_x (the continuation strategies from x) form a Nash equilibrium with respect to the payoffs induced solely by actions within that subgame. That is, no player can unilaterally deviate from \sigma_x to improve their payoff in the subgame, given the strategies of others. This restriction ensures sequential rationality throughout the game tree, applying both on and off the equilibrium path.^[2] The refinement property of SPE over Nash equilibrium arises because it enforces credibility by requiring optimality in all subgames, thus discarding equilibria supported by empty threats—such as a commitment to an irrational action if a deviation occurs—since those would not constitute Nash equilibria in the relevant subgames. For instance, in games where Nash equilibria might involve pre-commitment to suboptimal actions to deter opponents, SPE rules them out unless they remain rational conditionally. This makes SPE particularly suitable for analyzing dynamic games with sequential moves.^[12] In finite extensive-form games with perfect recall, the existence of at least one SPE is guaranteed. Perfect recall ensures that players remember all their past actions and information, allowing the use of behavioral strategies equivalent to mixed strategies. Kuhn's theorem establishes this equivalence, enabling the application of inductive methods to confirm that SPEs exist by constructing equilibria subgame by subgame from terminal nodes upward.^[2]

Backward Induction Method

The backward induction method serves as the standard algorithm for computing subgame perfect equilibria in finite extensive-form games with perfect information. It proceeds by starting at the terminal nodes of the game tree, where payoffs are known, and iteratively moving backward toward the root node. At each decision node, the player selects the action that maximizes their expected payoff, given the optimal actions already determined for all subsequent nodes. This backward propagation updates the value of each node to reflect the expected payoff from the optimal continuation strategy.^[2] In perfect information games, where each decision node is reachable by at most one history and information sets are singletons, the method directly identifies pure strategy subgame perfect equilibria by eliminating non-credible actions through this recursive optimization. The process ensures sequential rationality, as strategies prescribed at every subgame are optimal given the strategies in all subsequent subgames. (Note: Zermelo's 1913 theorem on chess applies the principle, but for general games, see Kuhn 1953.) For games with imperfect information, backward induction extends to behavioral strategies, which assign probabilities to actions at each information set rather than contingent plans over histories. This requires perfect recall—where players remember all their past actions—and consistency such that the strategy induces the same probabilities across indistinguishable histories within an information set. Kuhn's equivalence theorem guarantees that, under perfect recall, behavioral strategies are as expressive as mixed strategies for equilibrium analysis in such games. The method assumes finite length and a finite number of actions at each node; in infinite-horizon games, such as those with discounting in repeated interactions, pure strategy subgame perfect equilibria may fail to exist, necessitating mixed or trembling-hand refinements. In finite games of perfect information, backward induction always yields at least one subgame perfect equilibrium, though multiple equilibria can arise if payoff ties occur at some nodes, allowing for indifferent optimal actions. This outcome aligns with the subgame perfect equilibrium concept by ensuring credibility throughout the game tree.^[2]

Examples and Applications

Perfect Information Examples

In perfect information games, subgames correspond to every decision node in the extensive-form representation, allowing straightforward identification and analysis via backward induction to compute subgame perfect equilibria (SPE). A classic illustration is the two-stage ultimatum game, where two players divide a pie of size c > 0. Player 1 (the proposer) first chooses an offer x to Player 2 (the responder), with $0 \leq x \leq c. Player 2 then decides to accept (receiving x, while Player 1 gets c - x) or reject (both receive 0).^[13] The extensive form is a binary tree: the root node is Player 1's choice of x, branching to Player 2's accept/reject node for each x. Every node after Player 1's move constitutes a subgame, as Player 2's decision is independent of prior history. Backward induction begins at Player 2's subgames: for any x > 0, acceptance yields higher payoff than rejection (0), so Player 2 accepts all positive offers; for x = 0, Player 2 is indifferent but accepts in equilibrium. Anticipating this, Player 1 offers x = 0 to maximize their payoff c. The unique SPE is thus Player 1 offers 0 and Player 2 accepts any offer, yielding payoffs (c, 0).^[13] Another example is the simple entry deterrence game underlying Selten's chain-store paradox, a two-stage perfect information game between an incumbent firm (Player I) and a potential entrant (Player E). Player E first chooses to stay out (securing a safe payoff of 1) or enter the market. If out, Player I earns monopoly profit of 5. If enter, Player I chooses to accommodate (both earn 2 from shared duopoly) or fight (both earn 0 from price war).^[14] The extensive form tree starts at Player E's root node (enter/out), with the out branch terminating at payoffs (1 for E, 5 for I). The enter branch leads to Player I's subgame node (fight/accommodate), terminating at (0, 0) or (2, 2), respectively. The sole proper subgame is after entry, where Player I's choice is isolated. Backward induction solves this subgame first: Player I accommodates (2 > 0). Foreseeing accommodation, Player E enters (2 > 1). The unique SPE is entry followed by accommodation, with payoffs (2, 2).^[14] This SPE eliminates non-credible threats, such as Player I's empty promise to fight, which would deter entry in a Nash equilibrium but fails subgame perfection since Player I rationally accommodates once entry occurs. In the full chain-store paradox with multiple potential entrants in finite periods, iterative backward induction similarly yields accommodation in every subgame after entry, undermining deterrence despite the incumbent's incentive to build a reputation for aggression.

Imperfect Information Applications

In games with imperfect information, the identification of subgames is constrained by information sets, which must be entirely contained within or excluded from any subgame, often resulting in fewer proper subgames than in perfect information settings. This restriction influences the analysis of subgame perfect equilibrium (SPE), as strategies must be Nash equilibria in these limited subgames while respecting players' beliefs about unobserved actions.^[7] A seminal example is the Beer-Quiche signaling game, where a sender of unknown type (tough or weak, with prior probabilities 1/10 and 9/10, respectively) chooses to drink beer or eat quiche, observed by a receiver who then decides to duel or accommodate. The tough type values dueling highly if drinking beer but not quiche, while the weak type prefers accommodation regardless of choice, creating incentives for signaling. Subgames here include the full game and the two post-signal subtrees (after beer or quiche), as the receiver's singleton information sets following each observed signal allow these proper subtrees.^[15]^[7] SPE in the Beer-Quiche game yields both separating and pooling (babbling) equilibria under perfect Bayesian rationality. In the separating equilibrium, the tough sender drinks beer, the weak eats quiche, and the receiver accommodates beer drinkers (inferring toughness) while dueling quiche eaters (inferring weakness), with off-path beliefs deterring deviations. A babbling pooling equilibrium has both types drinking beer, the receiver dueling with probability 1/2 to keep the weak type indifferent, and dueling quiche eaters with beliefs of weakness. These equilibria highlight how signals can convey or obscure private information, depending on parameter values like the tough type's prior.^[15] In economic applications like entry games with asymmetric information, imperfect knowledge of the incumbent's costs (private to the incumbent) limits subgames to the full game and post-entry nodes, as the entrant's information sets may link multiple incumbent cost realizations. This reduction enables multiple SPE, such as reputation-building paths where a "normal" incumbent fights entrants early to signal toughness, deterring future entry over multiple periods despite the risk of losses.^[16] The key insight from such imperfect information settings is that fewer subgames weaken SPE's refinement over Nash equilibrium, often preventing unique predictions via backward induction and requiring supplementary belief-based refinements like perfect Bayesian equilibrium to resolve multiplicity.^[16]^[7] These concepts underpin 1980s advancements in auction theory and bargaining with private information, extending Selten's 1965 SPE framework to analyze signaling in common-value auctions (where bids reveal private signals) and bilateral bargaining (where offers convey type), influencing outcomes like the winner's curse mitigation and efficient trade probabilities.^[12]^[17]