Sequence Form Representations for Sequential Games

51 concepts38 papers1 proposal

When modeling strategic interactions over time—such as poker, auctions, or multi-stage negotiations—game theorists use extensive-form games (EFGs). Visually, these are game trees where players take turns making moves under conditions of imperfect information.

Historically, solving these games required converting them into a simplified "normal-form" matrix. However, this conversion triggers an exponential explosion in the size of the strategy space. To solve large-scale sequential games, researchers had to find a way to represent strategies without mapping out every hypothetical universe. The solution is the sequence-form representation.

The Curse of Contingency Plans

To understand why the sequence form is so powerful, we must first look at why the traditional normal-form representation fails.

In a normal-form representation, a player's strategy is a complete contingency plan. It is an exhaustive manual of instructions that specifies a deterministic action for every single decision point (information set) the player owns. Crucially, this manual must dictate what to do even at decision points that are completely unreachable due to the player's own prior choices.

Imagine a game tree with a depth of ten layers where a player makes a binary choice at each step. The number of possible information sets grows exponentially, and consequently, the number of deterministic contingency plans explodes. Representing this as a matrix yields a space too massive for any computer to store or optimize over.

The Core Insight: Realization Sequences

The breakthrough came when researchers realized they did not need to track global combinations of conditional plans. Instead, they could track the sequences of actions a player actually takes.

In their foundational paper, Generating and Solving Imperfect Information Games, Daphne Koller et al. introduced the sequence-form representation. This framework shifts the focus from global strategies to realization weights (or realization probabilities) of sequences of moves. A sequence is simply a history of actions taken exclusively by one specific player up to a given point in the game tree.

Why does this work? The magic relies on the assumption of perfect recall—the idea that players remember their own past choices. Under perfect recall, each information set for a player is uniquely defined by the sequence of that player's own past actions leading up to it.

Instead of specifying what to do at every dead end, the sequence form only tracks the probability that a player intends to execute a specific sequence of their own actions. Because the number of distinct sequences is exactly equal to the number of information sets plus one (for the empty sequence), the size of the strategy space drops from exponential to strictly linear relative to the size of the game tree.

The Geometry of the Treeplex

By representing strategies as sequences, the constraints ensuring that these probabilities are valid form a highly structured geometric object.

For a sequence-form strategy to be valid, the realization probability of a parent sequence must equal the sum of the realization probabilities of its immediate child sequences (a property known as conservation of probability flow). Because these constraints are entirely linear, the space of all valid sequence-form strategies forms a convex polytope called a treeplex.

As Christian Kroer et al. demonstrated in Solving Large Sequential Games with the Excessive Gap Technique, we can define proximal operators and dilated distance-generating functions directly over these treeplexes. This geometric formulation allows first-order optimization methods to navigate the strategy space efficiently, bypassing the complex hierarchical dependencies inherent in sequential decision-making.

Because the strategic space is enclosed within a polynomial number of linear constraints, finding a Nash equilibrium in a two-player zero-sum game can be formulated as a standard linear programming problem. This insight allowed early computational game theory solvers, such as the one detailed in Optimal Rhode Island Hold'em Poker by Andrew Gilpin et al., to compute exact, unexploitable minimax strategies for games with billions of nodes.

Scaling to Complex Equilibria and Team Coordination

The linear scaling of the sequence form does more than just accelerate zero-sum Nash equilibrium computations; it makes entirely new solution concepts computationally tractable.

Stackelberg Equilibria

In security scenarios where a leader must commit to a strategy before a follower responds, computing a Strong Stackelberg Equilibrium is notoriously difficult. In Sequence-Form Algorithm for Computing Stackelberg Equilibria in Extensive-Form Games, Branislav Bošanský et al. showed that by representing the leader's choices in sequence form, the optimization problem scales linearly with the game tree. This mathematical framework has since been extended to model subrational opponents who make localized mistakes, as explored in Computing Quantal Stackelberg Equilibrium in Extensive-Form Games.

Correlated and Team Strategies

When multiple players coordinate or receive private signals from a mediator, the joint strategy space typically suffers another exponential explosion. To combat this, the authors of Ex ante coordination and collusion in zero-sum multi-player extensive-form games introduced a "realization form" that tracks the probabilities of reaching terminal nodes rather than enumerating full joint plans.

By mapping joint team strategies to distributions over sequence pairs—often called correlation plans—researchers can optimize coordinated behavior without exhaustive enumeration, a technique advanced by Andrea Celli et al. in Connecting Optimal Ex-Ante Collusion in Teams to Extensive-Form Correlation: Faster Algorithms and Positive Complexity Results.

Accelerating Learning and Evolutionary Dynamics

Beyond static optimization, the sequence form fundamentally alters how reinforcement learning and evolutionary algorithms operate in sequential environments.

In evolutionary game theory, algorithms like replicator dynamics simulate how populations of strategies adapt over time. Running these dynamics over a normal-form matrix requires exponential time and memory. However, in Efficient Evolutionary Dynamics with Extensive-Form Games, Nicola Gatti et al. proved that replicator dynamics can be executed directly on the sequence form. This approach guarantees exact mathematical equivalence to traditional normal-form updates while achieving an exponential reduction in computational complexity.

The authors expanded this principle in Sequence-Form and Evolutionary Dynamics: Realization Equivalence to Agent Form and Logit Dynamics, proving that logit dynamics can similarly be mapped to sequence structures. This insight was also leveraged by Fabio Panozzo et al. in Evolutionary Dynamics of Q-Learning over the Sequence Form, where adapting Q-learning to sequence-form representations yielded speedups exceeding 1000x compared to matrix-based reinforcement learning.

Normal-Form Strategy:
[Info Set 1: Action A] AND [Info Set 2: Action B] AND [Info Set 3: Action C] ... (Exponential Combinations)

Sequence-Form Strategy:
[Empty] -> [Action A] -> [Action A, Action B] -> [Action A, Action B, Action C] (Linear Paths)

Bridging the Gap to Modern Online Optimization

Recently, the sequence form has served as a bridge allowing advanced online learning algorithms designed for simple matrix games to run directly on complex sequential trees.

For example, Chung-Wei Lee et al. introduced Kernelized Multiplicative Weights in Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games. By exploiting the combinatorial structure of the sequence-form polytope, their algorithm simulates normal-form learning updates in linear time, directly transferring strong regret bounds to sequential settings.

Finally, this geometric tractability unlocks solutions to long-standing open problems in regret minimization. In Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Games, Gabriele Farina et al. proved that the entire set of linear transformations for sequence-form strategies can be represented as a convex polytope defined by a polynomial number of linear constraints. This allows agents to efficiently compute complex strategy deviations, enabling AI systems to minimize swap regret and converge to sophisticated equilibrium classes in polynomial time.

Key Foundational Work

Generating and Solving Imperfect Information Games (1995) — contributed 2 concept elements to this direction.
On the NP-completeness of Finding an Optimal Strategy in Games with Common Payoffs (2001) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 38 papers
  2. Version 1 · 2026-10-04 · 60 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_sequence_form_representation_99f495d7,
  title = {sequence form representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequence-form-representation/rdr_99f495d7436544fcb566201f2f48be33},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_sequence_form_representation_99f495d7_v2,
  title = {sequence form representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequence-form-representation/rdr_99f495d7436544fcb566201f2f48be33/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake