Subgame perfect equilibrium
In game theory, a subgame perfect equilibrium (SPE), also known as subgame perfect Nash equilibrium (SPNE), is a refinement of the Nash equilibrium concept applied to extensive-form games, requiring that players' strategies constitute a Nash equilibrium not only in the overall game but in every subgame arising from any decision node.[1] This ensures sequential rationality, eliminating strategies supported by non-credible threats or promises that would not be optimal if the game reached those points.[2] Introduced by economist Reinhard Selten in 1965 as part of his analysis of dynamic oligopoly models, the concept was formally defined and expanded in his 1975 work on perfectness in extensive games.[1][2] Selten's innovation addressed limitations in Nash equilibria for sequential games, where players might anticipate future moves but could sustain implausible off-equilibrium behavior; SPE resolves this by applying backward induction, starting from terminal nodes and working reversely to derive optimal strategies at each information set.[1] In finite extensive games with perfect recall, at least one SPE always exists, and it can be computed by iteratively solving subgames.[2] The significance of SPE lies in its foundational role in non-cooperative game theory, earning Selten a share of the 1994 Nobel Prize in Economic Sciences alongside John Harsanyi and John Nash for advancing equilibrium analysis.[1] It has profound applications in economics, including credibility in monetary policy—where central banks' threats of high interest rates must be believable—and oligopoly dynamics, where firms' entry deterrence strategies are scrutinized for subgame consistency.[1] Beyond economics, SPE informs bargaining models like the ultimatum game, industrial organization, and even political science analyses of sequential decision-making under uncertainty.[1]Fundamentals
Definition
In game theory, a subgame perfect equilibrium (SPE) is a refinement of the Nash equilibrium tailored to extensive-form games, ensuring that players' strategies remain optimal not only in the overall game but also in every possible subgame that may arise during play.[3] The concept was first introduced by Reinhard Selten in 1965 in the context of dynamic oligopoly models with perfect information, and formally developed for general finite extensive-form games in 1975 to eliminate such non-credible strategies.[4][5] This concept addresses limitations in Nash equilibria, where off-equilibrium-path behaviors might involve non-credible threats or promises, by imposing sequential rationality throughout the game tree. Formally, consider an extensive-form game represented by a game tree \Gamma with players I, strategy sets S_i for each player i \in I (encompassing both pure strategies, which specify actions at each decision node, and mixed strategies, which assign probabilities to actions), payoff functions u_i: S \to \mathbb{R} for each i, and information sets that group nodes indistinguishable to players in cases of imperfect information. A strategy profile \sigma^* = (\sigma_i^*, \sigma_{-i}^*) is a subgame perfect equilibrium of \Gamma if, for every subgame \Gamma' of \Gamma starting at some history or node h, the restriction \sigma^*|_{\Gamma'} constitutes a Nash equilibrium of the subgame \Gamma'. That is, \forall i \in I, \ \forall \sigma_i \in S_i(\Gamma'), \quad u_i(\sigma^*|_{\Gamma'}) \geq u_i(\sigma_i, \sigma_{-i}^*|_{\Gamma'}) where S_i(\Gamma') denotes player i's feasible strategies in \Gamma', and payoffs are evaluated within that subgame.[3] The core requirement of SPE is sequential rationality, meaning that at every decision node (or information set) in any subgame, each player's strategy maximizes their expected payoff given the strategies of others, conditional on reaching that point.[6] This ensures that strategies prescribe credible actions everywhere in the game tree, preventing equilibria supported solely by empty threats, and applies to both perfect and imperfect information settings as long as subgames are well-defined.[5]Subgames and Extensive Form Games
Extensive form games provide a detailed representation of sequential strategic interactions, capturing the order of moves and information available to players. Introduced by von Neumann and Morgenstern, these games are modeled using a game tree, where nodes represent decision points or terminal outcomes, and branches denote possible actions taken by players or chance events. Each nonterminal node is assigned to a specific player who chooses among the available actions leading to child nodes, while terminal nodes specify payoff vectors for all players based on the path taken to reach them. To handle imperfect information, information sets group nodes where a player cannot distinguish between them, ensuring that strategies are consistent across indistinguishable situations.[7] A key structural element in extensive form games is the subgame, which allows for the decomposition of the overall game into smaller, self-contained components for analysis. Formally, a subgame is defined as follows: consider a nonterminal history h in the game such that the information set containing the node corresponding to h is a singleton \{h\}; the subgame rooted at this node consists of all successor nodes of h, along with the associated actions, information sets, and payoffs, provided that every information set intersecting this subtree is either entirely contained within it or entirely outside.[7] This ensures that the subgame replicates the original game's structure from that point onward, independent of prior history. Subgames rooted at the initial node of the full game are trivial in the sense that they encompass the entire game; proper subgames, by contrast, begin at some intermediate singleton information set and exclude the preceding history, enabling recursive nested analysis of strategic incentives. Trivial subgames, often consisting of single terminal nodes, offer no further decisions and thus trivial payoffs.[7] Games of perfect information form a special class of extensive form games where every information set is a singleton, meaning that at each decision node, the player knows exactly the full history of all previous actions.[7] This structure eliminates uncertainty about prior moves and facilitates straightforward sequential reasoning, as formalized by Kuhn in his analysis of such games. Subgame perfect equilibrium refines the standard Nash equilibrium by imposing consistency requirements specifically within these subgame structures.[7]Solution Concepts
Backward Induction
Backward induction is the foundational technique for computing subgame perfect equilibria (SPE) in finite extensive-form games with perfect information, where players move sequentially and observe all prior actions.[4] Introduced as part of the SPE concept, it systematically eliminates non-credible strategies by reasoning from the game's end toward the beginning, ensuring that strategies are optimal in every subgame. The process begins at the terminal nodes of the game tree, where payoffs are fixed and known. At each such node, the payoffs determine the outcomes. Moving backward, for every decision node reachable after the terminal payoffs are assigned, the player to move selects the action that maximizes their payoff, given the already determined optimal continuations from subsequent nodes. Suboptimal actions—those yielding lower payoffs—are pruned from consideration, effectively simplifying the tree by removing dominated branches. This iterative pruning continues up the tree until the initial node, yielding a strategy profile where no player has an incentive to deviate at any point. Formally, at any non-terminal history h where player i moves, the optimal action a^* is chosen as a^* = \arg\max_a u_i(\sigma_{-i} \mid h, a), where u_i is player i's payoff function and \sigma_{-i} \mid h denotes the continuation strategies of the other players following history h and action a. This choice incorporates the backward-inducted optima from all downstream subgames. This method applies specifically to finite-horizon games with perfect information, where the game tree is acyclic and has a finite depth, allowing complete traversal from the end. It does not extend directly to infinite-horizon games, as there are no terminal nodes to initiate the induction, nor to games with imperfect information without modifications, such as incorporating beliefs over hidden actions.[4] The outcome of backward induction in these games is a pure-strategy SPE, as each decision node prescribes a unique best response under the assumption of strict preferences over payoffs. However, if ties exist at any node—where multiple actions yield the same maximum payoff—multiple pure-strategy SPE may arise, corresponding to different resolutions of the indifference.Computing Subgame Perfect Equilibria
The computation of subgame perfect equilibria (SPE) in extensive-form games relies on verifying sequential rationality—ensuring that no player has a profitable deviation in any subgame—across the game's structure. A general approach uses dynamic programming to recursively evaluate subgames, starting from terminal nodes and propagating optimal strategies backward through the game tree, which enforces the Nash equilibrium condition in each subgame. For specific classes of games, such as two-player constant-sum extensive-form games, linear programming formulations in the sequence form allow efficient solving of SPE by optimizing realization probabilities subject to best-response constraints in subgames.[8] In extensive-form games with imperfect information, where players cannot distinguish certain histories, computing SPE necessitates incorporating consistent beliefs over information sets to maintain sequential rationality. This often involves refinements like sequential equilibrium, which pairs behavioral strategies with belief systems that are derived via Bayes' rule where possible and ensure no player regrets past actions given updated beliefs.[9] Software tools such as Gambit can model imperfect-information games and compute Nash equilibria using sequence-form methods (for two-player constant-sum cases), which coincide with SPE in perfect-information settings. For imperfect information, refinements like sequential equilibrium are used to ensure subgame perfection. Graphical tools like the Game Theory Explorer (GTE) aid in visualizing and solving game trees for Nash equilibria.[10][11] The computational complexity of finding SPE is PPAD-complete for approximating equilibria in general n-player extensive-form games of perfect recall, reflecting the challenge of locating fixed points in strategy spaces with subgame constraints.[12] However, for games with perfect information, SPE can be computed in polynomial time using backward induction as a special case.[12] One approach is to find a strategy profile \sigma that is sequentially rational in every subgame, meaning that for every player j and subgame, \sigma_j is a best response to \sigma_{-j} in that subgame; this is often operationalized through best-response dynamics, iteratively updating strategies until convergence in subgames.[13]Examples
Simple Ultimatum Game
The ultimatum game is a two-player, sequential bargaining game in which one player, the proposer, offers to split a fixed amount of money—typically $1—with the other player, the responder, who can either accept the offer or reject it.[14] If the responder accepts, the division occurs as proposed, with the proposer receiving the remainder; if rejected, both players receive nothing.[15] This setup highlights strategic decision-making under perfect information, where the responder moves last after observing the offer.[16] In standard Nash equilibrium analysis without subgame perfection, multiple outcomes qualify as equilibria: the proposer can offer any share x where $0 < x \leq 1, and the responder accepts any positive offer while being indifferent to zero, as long as the strategy profile is mutually best responding overall.[15] These equilibria include "fair" splits like 50-50, since a responder who rejects low offers could deter them, but such rejections are not sequentially rational in every subgame.[17] However, Nash equilibria fail to eliminate non-credible threats by the responder to reject small offers, potentially sustaining higher shares for the responder.[15] Subgame perfect equilibrium refines this by applying backward induction, starting from the responder's subgames. In each subgame following an offer x > 0, the responder rationally accepts, as x > 0 strictly dominates rejection (yielding 0).[15] For x = 0, the responder is indifferent and can accept or reject in equilibrium.[17] Anticipating acceptance of any positive offer, the proposer optimally offers the smallest feasible positive amount, \epsilon (approaching zero, such as one cent in discrete versions), maximizing their payoff at nearly $1 while giving the responder nearly nothing.[15] The unique subgame perfect equilibrium thus consists of the proposer offering \epsilon and the responder accepting all offers x \geq 0.[17] This equilibrium reveals the responder's rational indifference to minimal offers, eliminating fairness-based rejections as non-credible strategies that unravel under backward induction.[15] By requiring optimality in every subgame, subgame perfect equilibrium underscores how sequential rationality prevents empty threats, leading to a lopsided outcome that contrasts with experimental behavior where responders often reject low offers.[14]Entry Deterrence Game
The entry deterrence game, commonly referred to as the chain-store paradox, serves as a canonical example of how subgame perfect equilibrium addresses credibility problems in sequential strategic interactions. Developed by Reinhard Selten in 1978, the game models an incumbent monopolist (the chain store) confronting a sequence of potential entrants across a finite number of independent markets, typically denoted as k markets. Each entrant decides whether to stay out or enter their respective market, with subsequent entrants observing all prior outcomes. If an entrant stays out, the incumbent secures a monopoly profit. Upon entry, the incumbent chooses between accommodating the entrant (sharing the market) or fighting (engaging in a costly price war). The structure captures the tension between short-term gains and long-term deterrence strategies.[18] The payoffs in the stage game are designed to reflect realistic economic incentives, where the incumbent strictly prefers no entry to accommodation, and accommodation to fighting. A standard representation, consistent with Selten's formulation, is as follows:| Outcome | Entrant Payoff | Incumbent Payoff |
|---|---|---|
| Stay out | 0 | 9 |
| Enter and accommodate | 5 | 2 |
| Enter and fight | -2 | 0 |