Hubbry Logo
Sequential gameSequential gameMain
Open search
Sequential game
Community hub
Sequential game
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Sequential game
Sequential game
from Wikipedia
Chess is an example of a sequential game.

In game theory, a sequential game is defined as a game where one player selects their action before others, and subsequent players are informed of that choice before making their own decisions.[1] This turn-based structure, governed by a time axis, distinguishes sequential games from simultaneous games, where players act without knowledge of others’ choices and outcomes are depicted in payoff matrices (e.g., rock-paper-scissors).

Sequential games are a type of dynamic game, a broader category where decisions occur over time (e.g., differential games), but they specifically emphasize a clear order of moves with known prior actions. Because later players know what earlier players did, the order of moves shapes strategy through information rather than timing alone. Sequential games are typically represented using decision trees, which map out all possible sequences of play, unlike the static matrices of simultaneous games. Examples include chess, infinite chess, backgammon, tic-tac-toe, and Go, with decision trees varying in complexity—from the compact tree of tic-tac-toe to the vast, unmappable tree of chess.[2]

Representation and analysis

[edit]

Decision trees, the extensive form of sequential games, provide a detailed framework for understanding how a game unfolds.[3] They outline the order of players’ actions, the frequency of decisions, and the information available at each decision point, with payoffs assigned to terminal nodes. This representation was introduced by John von Neumann and refined by Harold W. Kuhn between 1910 and 1930.[3]

Sequential games with perfect information—where all prior moves are known—can be analyzed using combinatorial game theory, a mathematical approach to strategic decision-making. In such games, a subgame perfect equilibrium can be determined through backward induction, a process of working from the end of the game back to the start to identify optimal strategies.[4]

Games can also be categorized by their outcomes: a game is strictly determined if rational players arrive at one clear payoff using fixed, non-random strategies (known as "pure strategies"), or simply determined if the single rational payoff requires players to mix their choices randomly (using "mixed strategies").[5]

Types and dynamics

[edit]

Sequential games encompass various forms, including repeated games, where players engage in a series of stage games, and each stage’s outcome shapes the next.[3] In repeated games, players have full knowledge of prior stages, and a discount rate (between 0 and 1) is often applied to assess long-term payoffs, reflecting the reduced value of future gains. This structure introduces psychological dimensions like trust and revenge, as players adjust their strategies based on past interactions. In contrast, simultaneous games lack this sequential progression, relying instead on concurrent moves and payoff matrices.

Many combinatorial games, such as chess or Go, align with the sequential model due to their turn-based nature. The complexity of these games varies widely: a simple game like tic-tac-toe has a manageable decision tree, while chess’s tree is so expansive that even modern computers cannot fully explore it.[6] These examples illustrate how sequential games blend strategic depth with temporal dynamics.

See also

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia
from Grokipedia
A sequential game is a fundamental concept in where players make strategic decisions in a predefined order, with at least some players able to observe the actions taken by predecessors before choosing their own moves. Unlike simultaneous games, where all participants act without knowledge of others' choices, sequential games emphasize the timing and of decisions, often modeled using an extensive-form representation such as a that depicts decision nodes, branches for possible actions, and terminal payoffs. This structure allows for the analysis of dynamic interactions, including cases of (where all prior moves are known) and imperfect information (where some moves are hidden). Sequential games are crucial for understanding real-world scenarios involving leadership and followership, such as the Stackelberg duopoly model, where a leader firm sets output first to maximize profits, anticipating the follower's optimal response. Key solution concepts include , a method that starts from the end of the game tree and works backward to determine optimal strategies at each decision point, assuming rational play. This process often leads to perfect equilibria, which refine Nash equilibria by ensuring strategies are optimal in every , preventing non-credible threats or promises. Common examples range from simple two-player turn-based games like to complex economic models, highlighting how the order of moves can alter outcomes and incentives. In broader applications, sequential games inform fields like , , and , particularly in algorithm design for under , such as strategies enhanced by alpha-beta to efficiently evaluate game trees. Their study reveals insights into commitment, reputation, and strategic foresight, underscoring the importance of and timing in competitive and settings.

Fundamentals

Definition

A sequential game is a type of non-cooperative game in in which players make decisions in a predefined order, with each player acting at their designated turn and subsequent players having the potential to observe prior actions. This structure contrasts with simultaneous-move games by emphasizing the timing and observability of choices, allowing for strategic interactions that unfold over multiple stages. Key characteristics of sequential games include the strict ordering of moves, which enables early actors to commit to strategies that constrain or influence the options available to later players, and their resolution through the extensive form, a representational framework that captures the sequence, information, and contingencies of play. These features highlight how sequential games model real-world scenarios involving timing, such as negotiations or resource allocation, where the first-mover advantage can shape outcomes. The foundational concept of sequential games traces its origins to the work of in the 1920s and 1940s, who introduced the extensive form in his 1928 paper on parlor games and expanded it in the 1944 book Theory of Games and Economic Behavior co-authored with , providing a mathematical basis for analyzing ordered . The term and modern formalization gained prominence in the 1960s through contributions by , who refined equilibrium analysis for such games, building directly on von Neumann's framework to address dynamic strategic behavior. In sequential games, players receive payoffs only upon reaching a terminal outcome, determined by the entire path of moves traversed in the game tree, ensuring that strategies account for the cumulative effects of all decisions.

Distinction from Simultaneous Games

In simultaneous games, players make their decisions concurrently, without knowledge of the actions chosen by others, which is typically represented in normal form using payoff matrices. A classic example is the , where both players select cooperate or defect at the same time, leading to a unique of mutual defection as each player's best response to the anticipated choice of the other. This structure emphasizes static best-response strategies and often results in multiple possible equilibria, some of which may rely on non-credible assumptions about off-path behavior. Sequential games, by contrast, involve players acting in a defined order, with later movers able to observe prior actions, which introduces dynamic strategic foresight and timing into the interaction. This observability enables credible threats or promises, as first movers can commit to actions that shape subsequent responses, potentially resolving ambiguities present in simultaneous settings and reducing the number of plausible equilibria. A prominent illustration of this contrast appears in oligopoly models, such as the , where the leader firm sets output first and the follower responds, unlike the simultaneous quantity choices in the Cournot model. In the Stackelberg setup, the leader produces more (e.g., 150 units versus the follower's 75 units in a duopoly with linear ), resulting in higher total output, lower , and greater leader profit compared to the symmetric Cournot equilibrium (100 units each). This first-mover commitment alters the outcome by making the leader's strategy observable and binding, demonstrating how sequential timing can create advantages absent in concurrent decision-making. The sequential structure facilitates more refined analysis through concepts like subgame perfection, which requires strategies to be optimal in every , thereby eliminating non-credible threats that may persist in Nash equilibria of simultaneous games. This refinement ensures sequential rationality throughout the game tree, providing a stricter criterion for equilibrium selection than the best-response focus of simultaneous models.

Representation

Extensive Form and Game Trees

The extensive form provides a complete and explicit representation of a sequential game, specifying the players involved, the order and sequences of their moves, the information available to each player at decision points, chance events if present, and the payoffs resulting from all possible outcomes. Formally, an extensive form game consists of a finite set of players N={1,2,,n}N = \{1, 2, \dots, n\}, a tree-structured set of nodes XX with a designated root and terminal nodes TXT \subseteq X, a player assignment function indicating who moves at each non-terminal node (or chance if applicable), action sets A(x)A(x) for each non-terminal node xXx \in X, probability distributions over actions at chance nodes, and payoff functions ui:TRu_i: T \to \mathbb{R} for each player iNi \in N at terminal nodes. This structure captures the temporal aspect of sequential decision-making, distinguishing it from normal form representations that abstract away the order of play. Game trees visualize the extensive form as a rooted at the initial decision point, typically the first player's move in a two-player game. Each non-terminal node represents a decision point—either controlled by a specific player or by chance—while branches emanating from a node correspond to the available actions in A(x)A(x), leading to successor nodes. Terminal nodes at the leaves of the are labeled with payoff vectors (u1,u2,,un)(u_1, u_2, \dots, u_n), reflecting the outcomes for all players. For instance, in a two-player sequential game, the root node is assigned to player 1, with branches for their actions branching to player 2's decision nodes or terminals, ensuring the exhaustively maps all possible move sequences. sets partition the non-terminal nodes to indicate which positions a player cannot distinguish, though their full in imperfect is detailed separately. Standard notation in game trees employs distinct symbols to clarify node types: player decision nodes are often marked with black dots or squares labeled by the acting player (e.g., "Player 1"), while chance nodes use open circles to denote probabilistic moves by . Branches are labeled with actions (e.g., "Up" or "Left"), and terminal payoffs are placed at leaves, sometimes with probabilities if chance events precede them. Strategies, which specify actions across relevant nodes, may be labeled on branches for clarity in pure strategy representations, though behavioral strategies are more common in mixed settings. To manage complexity in large extensive form games, normalization techniques prune irrelevant subtrees—such as those unreachable due to prior moves or dominated actions—reducing the tree without altering strategic content. Additionally, the reduced normal form converts the extensive form into an equivalent normal form game by focusing on behavioral strategies at information sets, eliminating redundant pure strategy profiles and pruning the action space for computational efficiency. These methods preserve the game's essential structure while facilitating analysis in practice.

Information Sets and Strategies

In sequential games with imperfect information, uncertainty is modeled using information sets, which are partitions of the nodes in the game tree where a player cannot distinguish between the nodes due to unobserved prior actions or chance moves. These sets group histories that appear identical to the player at the time of decision-making, such as when previous moves are hidden or simultaneous. A player's strategy in such games must account for this uncertainty by specifying actions contingent on the information set reached, rather than on specific nodes. A pure strategy is a complete, deterministic plan that assigns an action to every information set controlled by the player, effectively outlining behavior for all possible distinguishable situations. In contrast, a mixed strategy is a probability distribution over pure strategies, allowing randomization across these plans. For finite games with perfect recall—where players remember their past actions—behavioral strategies provide an equivalent representation, assigning probabilities directly to actions at each information set, which simplifies analysis without altering outcomes. This equivalence was established by Harold Kuhn, who showed that mixed and behavioral strategies yield the same expected payoffs under perfect recall. The strategy space in sequential games expands rapidly, as the number of pure strategies grows exponentially with the depth and of the game tree, particularly with increasing information sets. For instance, if a player has n information sets with k actions available at each, the total number of pure strategies is k^n; for binary choices (k=2), this is 2^n, which grows exponentially with the number of information sets, rendering full enumeration computationally infeasible for complex and motivating approximations in practice. A representative example occurs in poker-like games, where an information set encompasses all possible private card combinations consistent with the observed public actions and the player's hand, as the exact cards dealt to opponents remain hidden. In Texas Hold'em, for instance, a player's decision to bet or at a given betting round groups indistinguishable states based on incomplete knowledge of opponents' holdings, requiring strategies to specify actions across this set.

Solution Concepts

Backward Induction

Backward induction is a recursive procedure used to solve finite sequential games represented in extensive form with . It determines the optimal profile by starting at the end of the game tree and working backwards to the initial node, assuming rational play by all players at every decision point. This method, first systematically applied in the analysis of extensive-form games by von Neumann and Morgenstern, ensures that strategies are sequentially rational throughout the game. The algorithm of backward induction operates as follows:
  1. Begin at the terminal nodes of the game tree, where payoffs are fully specified for each player based on the path leading to that outcome.
  2. Move backward to the penultimate decision nodes: for each such node controlled by a player, select the action that maximizes that player's payoff, taking into account the payoffs at the terminal nodes reachable from those actions.
  3. Continue this process iteratively toward earlier decision nodes, at each step choosing the optimal action given the previously determined optimal continuations in subsequent subgames.
This step-by-step elimination of suboptimal actions yields a unique path of play (under generic payoff assumptions) that constitutes the predicted outcome of the game. Backward induction relies on several key assumptions: the game must have a finite horizon with a finite number of stages and actions; all information is perfect, meaning each decision node is reachable via a unique history known to the decision maker; and players are fully rational, with common knowledge of rationality among all participants. These conditions ensure that players can anticipate future optimal responses without uncertainty about past moves or the structure of the game. Violations of finiteness or perfect information prevent the method from converging to a well-defined solution. The outcome of is a perfect , where the strategy profile induces play not only in the entire game but in every starting from any decision node. By construction, this eliminates non-credible threats or promises, as only strategies that are optimal in off-path subgames survive the backward reasoning process. This refinement strengthens the standard by focusing on sequential rationality. Despite its foundational role, has notable limitations. It cannot be applied to infinite-horizon games, where the lack of terminal nodes precludes starting the recursive process from a defined endpoint. The method also breaks down in imperfect information settings, as information sets may link non-sequential nodes, complicating the identification of unique optimal actions. Additionally, the backward induction solution can be sensitive to slight perturbations, such as minor changes in payoffs or small probabilities of implementation errors (trembles), potentially leading to different outcomes unless refined further, as in trembling-hand perfect equilibrium.

Subgame Perfect Equilibrium

In sequential games represented in extensive form, a (SPE) is a profile that forms a not only for the entire but also for every , defined as a portion of the game tree starting from any non-terminal node and encompassing all subsequent branches and payoffs. This refinement, introduced by , eliminates supported by non-credible off-path , ensuring that players' actions remain optimal even in hypothetical deviations that alter the course from any point. In finite-horizon games of , where players move alternately with full knowledge of prior actions, the set of perfect equilibria precisely matches the strategy profiles derived via , which systematically solves the game by determining optimal actions starting from terminal nodes and working backward. This equivalence highlights SPE as a theoretical justification for the backward induction procedure, guaranteeing robustness across all possible subgames without relying on unsupported threats. For sequential games with imperfect information, where players cannot distinguish between certain nodes, subgame perfection alone is insufficient due to the need for consistent beliefs at information sets; it requires sequential rationality, meaning players best respond to their beliefs about histories reaching each decision point. Kreps and Wilson extended this framework in their sequential equilibrium concept, which combines subgame perfection with limits of Bayes-rational beliefs as perturbations approach zero, providing a stable solution for such games. A key insight from SPE arises in finitely repeated games, where it resolves paradoxes involving empty threats, as illustrated by Selten's chain-store paradox: an incumbent firm faces sequential market entries by potential competitors, but reveals that the firm's aggressive retaliation threats in later periods lack credibility, prompting all entrants to enter and undermining any deterrence strategy. This outcome underscores how SPE enforces sequential rationality, preventing equilibria based on implausible commitments that unravel under scrutiny of later subgames.

Classifications

Perfect Information Games

In sequential games with , every player observes all prior actions before making their move, resulting in a single information set associated with each in the game . This full observability eliminates hidden actions or chance elements at , leading to deterministic paths from the initial node to terminal outcomes, where payoffs are assigned based on the final . Such games are typically represented as finite trees with alternating moves, no simultaneous decisions, and complete knowledge of the structure, including all possible future branches. A key feature of these games is their solution determinacy, particularly in finite two-player zero-sum settings. Zermelo's theorem (1913) establishes that always identifies a unique , where one player has a winning strategy, the opponent has a strategy to force a draw, or both can force a draw, depending on the payoffs. This result extends more broadly: every finite with admits a pure-strategy Nash equilibrium, computable via by evaluating subgames from the leaves upward. serves as the primary solver, ensuring rational play at every decision node. Strategically, amplifies the role of move order in shaping outcomes. The first mover often enjoys an advantage by committing to an action that constrains mover's responses, as seen in leader-follower models where the leader's choice influences subsequent optimal replies; however, this can reverse into a disadvantage if payoffs favor later commitment. This commitment power underscores how enables credible threats or promises along the equilibrium path, altering incentives compared to simultaneous-move settings. From a computational perspective, games are solvable in polynomial time relative to the size of the game tree using , making them tractable for small or moderately sized trees like . In contrast, for non-zero-sum multi-player variants or when games are succinctly represented (e.g., via rules generating large trees), problems such as determining equilibrium payoffs or outcomes become NP-hard or even , as the effective search space explodes exponentially.

Imperfect Information Games

In sequential games with imperfect information, players face partial observability, where they cannot distinguish between certain decision points, modeled through information sets that encompass multiple nodes in the game tree. This structure necessitates that players maintain beliefs about the possible underlying histories or states of nature at each information set, which are typically updated via when new actions or signals are observed along the equilibrium path. Such beliefs enable rational under , as players condition their strategies on these probabilistic assessments rather than full knowledge of prior moves. Solving for equilibria in these games presents significant challenges due to the need to specify beliefs not only on the equilibrium path but also off it, where Bayes' rule may not apply directly owing to zero-probability events. The (PBE) addresses this by requiring that strategies and beliefs form a at every information set, with beliefs updated consistently using Bayes' rule wherever possible and sequentially rational thereafter. Introduced formally by Fudenberg and Tirole, PBE ensures that players' actions remain optimal given their updated beliefs, even in response to deviations, thereby refining coarser solution concepts like Bayesian Nash equilibrium for dynamic settings. A key application arises in signaling games, where private information about player types influences sequential interactions. In Spence's seminal 1973 model of the job market, workers possess unobserved levels (high or low), and they choose levels to signal their type to employers, who update beliefs about productivity based on observed signals and offer wages accordingly. Separating equilibria emerge when high-productivity workers find it optimal to signal costly education, while low types do not, leading to efficient information transmission under asymmetric information. The analytical and of imperfect information games stems from the in strategy spaces as the number of information sets increases, since pure strategies must specify actions for every possible belief-contingent . This expansion often renders exact solutions infeasible for large games, prompting the use of approximations, techniques, or software tools like , which computes equilibria in extensive-form representations through methods such as sequence-form .

Examples

Zermelo's Chess Analysis

In 1913, published the paper "Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels," providing the first formal mathematical analysis of chess as a finite, two-person, of . He proved that such games are determinate, meaning that from the initial position, either White has a winning strategy (forcing a win regardless of Black's play), Black has a winning strategy, or both players can force a draw. Zermelo represented chess using a structure, where each node corresponds to a board position, branches denote legal moves alternating between players, and terminal nodes at the leaves represent endgames resolved as wins, losses, or draws with payoffs of +1, -1, or 0 for . The tree is finite due to the limited number of distinct positions (assuming no repetitions beyond a fixed length), allowing an inductive classification: starting from terminals, positions are labeled as winning if a move leads to an opponent's losing position, drawing if all moves lead to drawing or winning positions for the opponent, and so on backward through the tree. This inductive method, while not explicitly termed in Zermelo's work, establishes the core principle by constructing sets of winning sequences Ur(q)U_r(q) and drawing sequences Vs(q)V_s(q) from any position qq, ensuring a win or draw in at most rr or ss moves against optimal opposition. The proof demonstrates theoretical solvability but underscores practical limitations, as the chess tree's scale—estimated at approximately 104310^{43} reachable positions—renders exhaustive computation infeasible without modern approximations. Zermelo's analysis forms the foundational theorem for extensive-form representations in games, influencing later developments in and AI techniques for solving board games, such as AlphaZero's use of search trees informed by similar principles.

Entry Deterrence Models

Entry deterrence models illustrate how sequential games capture strategic interactions between an incumbent firm and a potential entrant in economic markets. In the basic setup, the incumbent moves first by making an observable , such as expanding production capacity, which commits it to a certain level of output in the subsequent competitive stage. The entrant then observes this action and decides whether to enter the market, incurring a fixed entry ; if entry occurs, the firms compete, often modeled as a Cournot duopoly where payoffs depend on their output choices. This structure highlights the incumbent's ability to influence the entrant's decision through credible preemptive actions. Equilibrium analysis typically employs to resolve the game, ensuring strategies are optimal at every decision node. If entry would be efficient—yielding positive profits for the entrant net of costs—the subgame perfect outcome often involves accommodation, where the accepts rather than engaging in unprofitable fights post-entry. However, the can deter entry by overinvesting in capacity to make post-entry payoffs negative for the entrant, as the sunk credibly signals aggressive ; this works when the incumbent's allows it to commit to a scale that shifts the post-entry equilibrium in its favor. threats, where the promises low prices after entry, may also deter if they are credible, though in single-period games, such threats are often empty without commitment devices. Preemptive mergers exemplify first-mover advantages in these models, where an incumbent firm initiates a horizontal merger with a potential rival to deter subsequent entries by altering market structure and raising barriers for others. However, such strategies carry risks of exposure, as the merger decision may signal intentions to competitors, potentially triggering counter-mergers or regulatory scrutiny that undermines the deterrence. Extensions to repeated settings reveal the chain-store paradox, where an incumbent chain facing sequential entry in multiple markets fights aggressively in early ones to build a for toughness, deterring later entrants despite predicting accommodation in finite games. In Selten's 1978 model, the unique involves the incumbent always accommodating after the first entry, leading to a counterintuitive unraveling where no deterrence occurs, even if fighting would be profitable initially. This paradox is resolved in infinite-horizon or incomplete-information frameworks, where reputation effects allow predation to sustain deterrence; for instance, if entrants believe with small probability that the incumbent is irrationally aggressive, the incumbent may rationally fight early to preserve this belief and avoid entry across markets. These models tie into real-world antitrust scrutiny, particularly in industries like airlines where incumbents use hub strategies and capacity expansions to deter low-cost entrants. For example, in the 2000 Spirit Airlines v. Northwest Airlines case, Spirit alleged predatory pricing on routes to its Detroit hub, claiming Northwest priced below variable costs to eliminate competition; the district court granted summary judgment to Northwest in 2001, but the Sixth Circuit reversed in 2005, remanding the case for trial. Following Northwest's bankruptcy filing in 2005 and the Supreme Court's denial of certiorari in 2006, the matter did not proceed to trial. Similar allegations arose in the U.S. Department of Justice's 1999 suit against American Airlines, where rapid capacity increases were challenged as predatory responses to entrants like Vanguard Airlines, though the case was ultimately dismissed for failing to prove below-cost pricing with monopoly recoupment intent.

Salary Negotiations

Salary negotiations serve as a classic example of sequential bargaining games in imperfect information settings, where an employee and employer alternate offers and counteroffers, with each party observing prior proposals before responding. The process begins with one party, often the employee, making an initial salary demand, followed by the employer's counteroffer, and potentially further rounds until agreement or breakdown. This sequential structure allows later movers to condition their strategies on observed actions, potentially conferring a second-mover advantage through informed responses, though the first mover can leverage anchoring effects to shape expectations. Game-theoretic analysis, such as Rubinstein's alternating-offer model, predicts immediate agreement under complete information, with the surplus divided based on relative patience (discount factors); however, incomplete information about reservation wages often leads to delays, gradual concessions, and risks of impasse if offers reveal irreconcilable valuations. Empirical studies of bargaining patterns, including salary contexts, show frequent use of split-the-difference offers and reciprocal concessions, deviating from pure strategic predictions and highlighting behavioral influences. While first-mover advantages exist via initial anchoring, exposure of one's reservation value in early offers can disadvantage the proposer if the counterpart exploits the information asymmetry.

References

Add your contribution
Related Hubs
User Avatar
No comments yet.