The Sequence Form

The sequence form is the strategic representation that makes extensive-form games computationally tractable. Its content is a single substitution: instead of a variable per pure strategy — a complete contingent plan, one move chosen at every information set, so the count is a product over information sets — put a variable per sequence, the list of a player’s own moves along one path from the root, so the count is a sum over information sets. ∏ becomes Σ, and an exponential object becomes a linear one. Bernhard von Stengel introduced it under that name, proving that a zero-sum extensive game becomes a linear program “whose size, in sparse representation, is linear in the size of the game tree” (von Stengel, Efficient Computation of Behavior Strategies, GEB 14:220–246, 1996); the companion paper by Daphne Koller, Nimrod Megiddo and von Stengel showed the general-sum case becomes a linear complementarity problem of the same linear size, solvable by Lemke’s algorithm (GEB 14:247–259, 1996). Both were preceded by their joint STOC 1994 paper (Koller, Megiddo & von Stengel, STOC ‘94, pp. 750–759, venue and pagination confirmed via dblp). This is why Kuhn poker — and games very much larger — can be solved at all.

Where this sits

This note is about the sequence form as a computational object: its constraint matrices, its sparse payoff matrices, the linear program and the linear complementarity problem they define. The modelling background — what an information set is, what a realization plan is, why Kuhn’s theorem lets you use behavioural strategies — belongs to Extensive-Form Games and is recapped here only enough to make the matrices readable. The game used as the worked example throughout is documented in Kuhn Poker; the algorithm this note is most usefully compared against is Counterfactual Regret Minimization. Stage P3/P6 of Games and Strategic Systems in C MOC.

---

Mental Model: ∏ Becomes Σ

Everything about the sequence form follows from one arithmetic observation, so it is worth stating before any definitions.

A pure strategy in an extensive game is an element of ∏_{h ∈ H_i} C_h — a choice at every information set the player owns, whether or not that set is reachable given the player’s own other choices. The count is a product. A sequence is the list of a player’s own moves along the path from the root to some node, so the set of sequences is S_i = {∅} ∪ { σ_h c | h ∈ H_i, c ∈ C_h } and the count is |S_i| = 1 + Σ_{h ∈ H_i} |C_h| — a sum. Since there are at most as many sequences as the tree has nodes, |S_i| is linear in the tree size (von Stengel 1996, §3; AGT ch. 3 §3.10).

The price is that you can no longer randomize by putting a probability distribution over your variables — a player cannot simply “pick a sequence,” because sequences at different parts of the tree are not alternatives to one another. As von Stengel puts it: “randomizing between such sequences can no longer be described by a single probability distribution, but requires a system of linear equations.” That system is the entire technical content of the representation, and it is what makes the whole thing an LP rather than a simplex optimization.

flowchart TB
    subgraph NF["NORMAL FORM — variable per PURE STRATEGY"]
        direction TB
        N1["A strategy = one move at EVERY information set"]
        N2["count = ∏ over information sets<br/>|H_i| sets, branching b  ⟹  ≈ b^|H_i|"]
        N3["Randomize: a probability distribution<br/>over strategies. Domain = a SIMPLEX."]
        N4["Payoff matrix: DENSE, exponentially large"]
        N1 --> N2 --> N3 --> N4
    end
    subgraph SF["SEQUENCE FORM — variable per SEQUENCE"]
        direction TB
        S1["A sequence = my own moves along ONE path"]
        S2["count = 1 + Σ over information sets<br/>|S_i| = 1 + Σ_h |C_h|  ⟹  linear in tree size"]
        S3["Randomize: a REALIZATION PLAN.<br/>Domain = a POLYTOPE Ex = e, x ≥ 0<br/>(the 'treeplex')"]
        S4["Payoff matrix: SPARSE — at most one<br/>nonzero per leaf of the tree"]
        S1 --> S2 --> S3 --> S4
    end
    NF -- "the substitution:<br/>plans → paths, ∏ → Σ" --> SF

What it shows: the two representations side by side, with the exponent-to-linear change traced to the single structural difference between a product and a sum. The insight: the sequence form does not approximate the game, discard strategies, or restrict the solution concept. It is an exact re-coordinatization. What it costs is the simplex — a set of probabilities summing to one — replaced by a polytope with one linear equation per information set. Every algorithmic consequence in this note is a consequence of that trade.

---

The Blow-up, Measured

The claim “the reduced normal form is exponential” is usually asserted. Here is the arithmetic, computed on generalized Kuhn poker with n cards (two players, one card each, ante 1, one optional bet of 1 — the classic game is n = 3).

The structure of the reduction is worth stating because it is not symmetric between the two players, and the asymmetry is the whole reason the reduced form still explodes:

• Player 1, holding a given card, has two information sets: act first and respond to a bet after I checked. The second is unreachable if the first move was bet, so ⟨bet, then-fold⟩ and ⟨bet, then-call⟩ are the same reduced strategy. Three distinguishable plans per card: bet, check-then-fold, check-then-call. Across n cards: 3^n.
• Player 2, holding a given card, also has two information sets: facing a check and facing a bet. But which one is reached depends on player 1’s move, not player 2’s. Nothing player 2 does makes either unreachable, so nothing can be identified. Four plans per card, across n cards: 4^n.

von Stengel names exactly this case and its consequence: “A player may have parallel information sets that are not distinguished by own earlier moves. These arise when a player receives information about an earlier move by another player. Combinations of moves at parallel information sets cannot be reduced, which causes a multiplicative growth of the number of reduced strategies. In general, the reduced strategic form can therefore still be exponential in the size of the game tree” (AGT ch. 3 §3.9).

Now the numbers. I built the tree explicitly and counted:

n	tree leaves	|S₁|	|S₂|	sequence-form matrix cells	reduced NF rows (3ⁿ)	reduced NF cols (4ⁿ)	reduced NF cells	nonzero cells in A
3	30	13	13	169	27	64	1,728	30
4	60	17	17	289	81	256	20,736	60
5	100	21	21	441	243	1,024	248,832	100
6	150	25	25	625	729	4,096	2,985,984	150
8	280	33	33	1,089	6,561	65,536	429,981,696	280
10	450	41	41	1,681	59,049	1,048,576	61,917,364,224	450
13	780	53	53	2,809	1,594,323	67,108,864	106,993,205,379,072	780
20	1,900	81	81	6,561	3,486,784,401	1,099,511,627,776	3.83 × 10²¹	1,900

(Original computation for this note; Python 3 standard library only, exact integers. Read the last column against the third-from-last: the number of nonzero entries in the sequence-form payoff matrix equals the number of leaves exactly, at every row — which is the theorem, not a coincidence, and is a useful check that the tree enumeration is right.)

Two readings. First, |S_i| = 4n + 1 — dead linear, 13 at n = 3 and 81 at n = 20. Second, the reduced normal form grows as 3^n · 4^n = 12^n; at a 20-card deck it is 3.8 × 10^21 cells, which is not a matrix anyone will build, while the sequence form is 81 × 81 with 1,900 nonzeros. At n = 13 — a real deck of one suit — the reduced normal form is already 10^14 cells and the sequence form is 2,809.

The sibling note measures the same blow-up from the other side

Extensive-Form Games measures the strategy count on tic-tac-toe: 10^25741 pure strategies for the first player against 291,682 sequences, a tree that a laptop builds in 27 ms. That note’s framing is worth repeating because it is the whole idea in one character: the strategy counter accumulates with *=, the sequence counter with +=.

---

Realization Plans, and the Constraint Matrix

A one-paragraph recap; the full development, including Kuhn’s theorem and why perfect recall is required, is in Extensive-Form Games.

Because the sequence variables are not alternatives, we cannot use a probability distribution over them. What we use instead is the realization plan: for a mixed strategy μ_i, define x(σ) = μ_i[σ] = Σ_{π_i} μ_i(π_i)·π_i[σ], where π_i[σ] is 1 if the pure strategy π_i prescribes every move in σ and 0 otherwise. In words, x(σ) is the probability that my own choices are consistent with travelling along σ — “the probability I do my part of this path.” Realization probabilities of a behaviour strategy β_i are just products along the path, β_i[σ] = ∏_{c in σ} β_i(c) (AGT eq. 3.21).

The characterization is what turns this into linear algebra:

Proposition 3.10 (von Stengel). A realization plan x of a mixed strategy of player 1 fulfils x(σ) ≥ 0 for all σ ∈ S₁ and

x(∅) = 1,        Σ_{c ∈ C_h} x(σ_h c) = x(σ_h)      for all h ∈ H₁.

Conversely, any x : S₁ → ℝ with these properties is the realization plan of a behaviour strategy of player 1, which is unique except at irrelevant information sets.

Read the second equation as flow conservation: probability arriving at information set h along its unique own-move prefix σ_h splits among the moves available at h, and nothing leaks. σ_h is well defined only under perfect recall — that is exactly the assumption that all nodes of h are reached by the same own-move sequence.

Writing these as E x = e, x ≥ 0 and F y = f, y ≥ 0, the matrix E has 1 + |H₁| rows and |S₁| columns: the first row is x(∅) = 1, and each subsequent row is −x(σ_h) + Σ_{c ∈ C_h} x(σ_h c) = 0. Every sequence appears exactly once with coefficient +1 in the column structure, which is why E is so sparse and so well conditioned.

Worked: the constraint matrices for Kuhn poker

Here they are, computed rather than typeset by hand. Player 1’s sequences are ∅, then for each card c the sequences c:p (check), c:b (bet), c:pf (check-then-fold) and c:pc (check-then-call). Player 2’s are ∅, then c|p:p / c|p:b (facing a check: check / bet) and c|b:f / c|b:c (facing a bet: fold / call).

Constraint matrix E  (7 x 13), right-hand side e:
                0   J:p   J:b   Q:p   Q:b   K:p   K:b  J:pf  J:pc  Q:pf  Q:pc  K:pf  K:pc
     x(0)=1     1     0     0     0     0     0     0     0     0     0     0     0     0  | 1
   IS J 1st    -1     1     1     0     0     0     0     0     0     0     0     0     0  | 0
   IS Q 1st    -1     0     0     1     1     0     0     0     0     0     0     0     0  | 0
   IS K 1st    -1     0     0     0     0     1     1     0     0     0     0     0     0  | 0
   IS J p.b     0    -1     0     0     0     0     0     1     1     0     0     0     0  | 0
   IS Q p.b     0     0     0    -1     0     0     0     0     0     1     1     0     0  | 0
   IS K p.b     0     0     0     0     0    -1     0     0     0     0     0     1     1  | 0

Constraint matrix F  (7 x 13), right-hand side f:
                  0   J|p:p   J|p:b   Q|p:p   Q|p:b   K|p:p   K|p:b   J|b:f   J|b:c   Q|b:f   Q|b:c   K|b:f   K|b:c
       y(0)=1       1       0       0       0       0       0       0       0       0       0       0       0       0  | 1
   IS J vs ck      -1       1       1       0       0       0       0       0       0       0       0       0       0  | 0
   IS Q vs ck      -1       0       0       1       1       0       0       0       0       0       0       0       0  | 0
   IS K vs ck      -1       0       0       0       0       1       1       0       0       0       0       0       0  | 0
  IS J vs bet      -1       0       0       0       0       0       0       1       1       0       0       0       0  | 0
  IS Q vs bet      -1       0       0       0       0       0       0       0       0       1       1       0       0  | 0
  IS K vs bet      -1       0       0       0       0       0       0       0       0       0       0       1       1  | 0

(Original computation for this note.) Three things are visible in these matrices that no prose statement conveys.

The −1 entries encode the tree. In E, the rows for player 1’s second decision (IS J p.b, etc.) carry their −1 in the J:p / Q:p / K:p column, not in the ∅ column — because the information set “I checked and now face a bet” is reached only after my own move check. In F, every −1 sits in the ∅ column, because player 2 makes no own move before any of his six information sets; which one he lands in is chosen by player 1. That structural difference is precisely the parallel-information-set phenomenon that costs player 2 all reduction in the normal form (4^n, not 3^n) — and in the sequence form it costs him exactly nothing: both players get a 7 × 13 constraint matrix.

flowchart TB
    subgraph P1["Player 1's sequences for ONE card — the tree behind E's rows"]
        direction TB
        E1(("∅<br/>x(∅) = 1"))
        CK["c:p<br/>check"]
        BT["c:b<br/>bet"]
        FD["c:pf<br/>check, then fold"]
        CL["c:pc<br/>check, then call"]
        E1 -- "row 'IS c 1st':<br/>−x(∅) + x(c:p) + x(c:b) = 0" --> CK
        E1 --> BT
        CK -- "row 'IS c p.b':<br/>−x(c:p) + x(c:pf) + x(c:pc) = 0" --> FD
        CK --> CL
        BT -.->|"the 'respond to a bet' set is<br/>UNREACHABLE after my own bet —<br/>no equation, no variable"| X(("· nothing ·"))
    end
    subgraph P2["Player 2's sequences for ONE card — all rooted at ∅"]
        direction TB
        E2(("∅<br/>y(∅) = 1"))
        VC1["c|p:p"]; VC2["c|p:b"]
        VB1["c|b:f"]; VB2["c|b:c"]
        E2 -- "row 'IS c vs ck'" --> VC1
        E2 --> VC2
        E2 -- "row 'IS c vs bet'" --> VB1
        E2 --> VB2
    end

What it shows: the two players’ sequence trees for a single card, annotated with the E and F rows they generate. The insight: player 1’s second information set hangs below his own move check, so its equation subtracts x(c:p); player 2’s two information sets both hang directly off ∅, so both equations subtract y(∅). In the reduced normal form that difference is the gap between 3^n and 4^n. In the sequence form it is the difference between putting the −1 in column c:p and putting it in column ∅ — and both matrices come out 7 × 13.

Two 1s per row, one −1. Each row is −x(parent) + Σ_children x = 0: a flow-conservation equation on a tree. The matrix is an incidence-like structure with 3 nonzeros per row and one nonzero per column beyond the parents — 19 nonzeros out of 91 cells, about 21%.

The polytope dimension. |S_i| = 13 variables minus 1 + |H_i| = 7 linearly independent equations gives dimension 6 — which is Σ_h (|C_h| − 1) = 6 × (2 − 1) = 6, one free number per binary information set. That is exactly the number of parameters a behavioural strategy has. The sequence form is not adding degrees of freedom; it is embedding the same 6-dimensional object in a 13-dimensional space where the payoff is linear instead of multilinear.

That last sentence is the whole reason the representation exists, so it is worth being explicit about the alternative. If you parameterize directly by behaviour probabilities β_i(c), you also get a small number of variables — but the expected payoff Σ_leaves a(t)·β₀[σ₀(t)]·β₁[σ₁(t)]·β₂[σ₂(t)] is a sum of products of those variables, i.e. a polynomial, and optimizing it is not an LP. von Stengel states the trade in one sentence: behaviour probabilities “are also small in number, they can be characterized by linear equations (as any probabilities), but the expected payoff usually involves products of behaviour strategy probabilities. Using the resulting polynomials for computing equilibria is theoretically and practically much more difficult than the approach taken here” (von Stengel 1996, §1).

---

The Sparse Payoff Matrix

The second half of the representation is the payoff. For σ ∈ S₁ and τ ∈ S₂, define

        a_{στ}  =   Σ            a(t) · β₀[σ₀(t)]
                 leaves t with
                 σ₁(t)=σ, σ₂(t)=τ

(AGT eq. 3.26). Symbol by symbol: a(t) is player 1’s payoff at leaf t; β₀[σ₀(t)] is the product of the chance probabilities on the path to t, so the chance player is folded into the constant rather than carried as a variable; σ₁(t) and σ₂(t) are the two players’ own-move sequences on the path to t. The matrix B is the same with b(t). Expected payoffs are then xᵀAy and xᵀBy — bilinear, exactly as in a bimatrix game.

The critical structural property: A has at most one nonzero contribution per leaf. Every pair (σ, τ) that does not jointly lead to a leaf has an empty sum, hence a zero. So the number of nonzeros is bounded by the number of leaves, which is linear in the tree — while a normal-form payoff matrix is generally full.

Worked: Kuhn poker’s 13 × 13 payoff matrix

Sequence-form payoff matrix A: 13x13 = 169 entries, 30 nonzero (17.8% dense)
   A[  J:p][  Q|p:p] = -1/6      A[  K:p][  J|p:p] =  1/6      A[ Q:pf][  J|p:b] = -1/6
   A[  J:p][  K|p:p] = -1/6      A[  K:p][  Q|p:p] =  1/6      A[ Q:pf][  K|p:b] = -1/6
   A[  J:b][  Q|b:f] =  1/6      A[  K:b][  J|b:f] =  1/6      A[ Q:pc][  J|p:b] =  1/3
   A[  J:b][  Q|b:c] = -1/3      A[  K:b][  J|b:c] =  1/3      A[ Q:pc][  K|p:b] = -1/3
   A[  J:b][  K|b:f] =  1/6      A[  K:b][  Q|b:f] =  1/6      A[ K:pf][  J|p:b] = -1/6
   A[  J:b][  K|b:c] = -1/3      A[  K:b][  Q|b:c] =  1/3      A[ K:pf][  Q|p:b] = -1/6
   A[  Q:p][  J|p:p] =  1/6      A[ J:pf][  Q|p:b] = -1/6      A[ K:pc][  J|p:b] =  1/3
   A[  Q:p][  K|p:p] = -1/6      A[ J:pf][  K|p:b] = -1/6      A[ K:pc][  Q|p:b] =  1/3
   A[  Q:b][  J|b:f] =  1/6      A[ J:pc][  Q|p:b] = -1/3
   A[  Q:b][  J|b:c] =  1/3      A[ J:pc][  K|p:b] = -1/3
   A[  Q:b][  K|b:f] =  1/6      A[ K:pf][ ... ]
   A[  Q:b][  K|b:c] = -1/3

(Original computation for this note; entries are exact fractions.Fraction values.) Thirty nonzeros out of 169 cells — and thirty is exactly the leaf count of the Kuhn tree. Every entry is a 1/6, 1/3, −1/6 or −1/3: the 1/6 is the chance probability of one of the six deals, and the 1/3 entries are two chips rather than one (a called bet doubles the pot swing). Read A[K:b][Q|b:c] = 1/3: “I hold the king and bet, you hold the queen and call, the deal (K,Q) has probability 1/6, I win two chips” — (1/6)·2 = 1/3.

Compare with the same game’s reduced normal form: 27 × 64 = 1,728 cells, all of them nonzero, each holding a payoff pair. The sequence form is 169 cells of which 30 matter, and it carries strictly the same information.

flowchart LR
    TREE["GAME TREE<br/>nodes, information sets,<br/>chance moves, leaf payoffs"]
    subgraph SFOBJ["THE SEQUENCE FORM = four sparse matrices"]
        direction TB
        EE["E : (1+|H₁|) × |S₁|<br/>flow conservation for player 1<br/>3 nonzeros per row"]
        FF["F : (1+|H₂|) × |S₂|<br/>flow conservation for player 2"]
        AA["A : |S₁| × |S₂|<br/>a_στ = Σ over leaves reached by (σ,τ)<br/>≤ one nonzero per LEAF"]
        BB["B : |S₁| × |S₂|<br/>same, player 2's payoffs<br/>(B = −A in the zero-sum case)"]
    end
    LP["ZERO-SUM: one linear program<br/>min eᵀu s.t. Fy=f, Eᵀu−Ay ≥ 0, y ≥ 0<br/>polynomial time"]
    LCP["GENERAL-SUM: a linear complementarity problem<br/>Lemke's algorithm<br/>exponential worst case"]
    TREE -- "one pass over the tree" --> SFOBJ
    SFOBJ -- "B = −A" --> LP
    SFOBJ -- "B ≠ −A" --> LCP

What it shows: the pipeline from tree to solver, and the single branch that decides which solver applies. The insight: the whole construction is one traversal of the game tree. There is no intermediate normal form to materialize and therefore no exponential step anywhere in the pipeline — the object you would have had to build is skipped, not compressed.

---

The Best-Response LP, and Its Dual

Everything algorithmic follows from one linear program: player 1’s best response to a fixed realization plan y of player 2.

   maximize   xᵀ(Ay)      subject to   Ex = e,   x ≥ 0                        (3.27)

Ay is a vector indexed by player 1’s sequences — the expected payoff contribution of each of his sequences against y. The feasible set is exactly the realization-plan polytope. Its dual introduces a vector u of unconstrained variables, one per row of E, i.e. one per information set of player 1 plus one for the root:

   minimize   eᵀu          subject to   Eᵀu ≥ Ay                              (3.28)

Both are feasible, so by strong LP duality they have the same optimal value (AGT ch. 3 §3.11).

The dual variables have a reading that ties this back to the algorithm every reader already knows. e = (1, 0, 0, …, 0)ᵀ, so eᵀu = u_∅ — the objective is the single dual variable attached to the root. And the constraint Eᵀu ≥ Ay, written out for the column of a sequence σ_h c, says u_h ≥ (Ay)_{σ_h c} + Σ_{h' : σ_{h'} = σ_h c} u_{h'}: the value at information set h is at least the immediate payoff of move c plus the values of the information sets that move leads to. At optimum this holds with equality for the best move. That is backward induction, written as an LP. von Stengel remarks on the connection at the end of the 1996 paper: “The constraints in the sequence form are closely related to backward induction.” See Backward Induction for the perfect-information version of the same recursion.

Zero-sum: one linear program

Now let player 2 choose y. If the game is zero-sum (B = −A), player 2 must assume player 1 maximizes xᵀAy, whose value is the optimum of (3.27), which equals the dual optimum eᵀu. So player 2 minimizes eᵀu over both u and y at once — legal, because the dual constraints Eᵀu ≥ Ay are linear in y as well:

   minimize   eᵀu     subject to   Fy = f,   Eᵀu − Ay ≥ 0,   y ≥ 0           (3.29)
      u, y

and its dual, which is player 1’s max-min problem:

   maximize   fᵀv     subject to   Ex = e,   Fᵀv − Aᵀx ≤ 0,   x ≥ 0          (3.30)
      v, x

Theorem 3.13 (von Stengel). The equilibria of a two-person zero-sum game in extensive form with perfect recall are the solutions to the LP (3.29) with sparse payoff matrix A and constraint matrices E and F. The size of this LP is linear in the size of the game tree.

The 1996 statement is the same result with the emphasis on primal/dual pairing: “The equilibria of a zero-sum game in extensive form with perfect recall are the optimal primal and dual solutions of a linear program whose size, in sparse representation, is linear in the size of the game tree” (Theorem 5.1). Note the corollary von Stengel draws immediately: this proves existence of an equilibrium in the zero-sum case, by LP duality, without any fixed-point theorem — the same relationship that Zero-Sum Games and the Minimax Theorem documents for normal-form games, lifted to trees.

A practical detail from the paper that survives into every implementation: LP (3.29) has |S₁| + 1 + |H₂| constraints and (3.30) has |S₂| + 1 + |H₁|, and “the running time of the simplex algorithm … is mostly determined by the number of constraints and very little by the number of variables. Therefore, it may be advantageous in certain cases to run the simplex algorithm on the dual LP instead.” A second reduction, also from §5: sequences that lead to no leaf (like the empty sequence for a player who always moves first) contribute only zero columns to A and B, and their variables can be eliminated from the constraints outright.

sequenceDiagram
    autonumber
    participant T as Game tree
    participant B as Builder (one traversal)
    participant P as Primal LP (3.29): min eᵀu over (u, y)
    participant D as Dual LP (3.30): max fᵀv over (v, x)
    participant R as Realization plans (x*, y*)

    T->>B: nodes, information sets, chance probs, leaf payoffs
    B->>B: S₁, S₂ (one sequence per own-move path)
    B->>B: E, F  (one row per information set + normalisation)
    B->>B: A     (one nonzero per leaf, chance folded in)
    B->>P: sparse E, F, A
    P->>D: strong duality — same optimal value = game value
    P-->>R: y* (player 2's min-max realization plan)
    D-->>R: x* (player 1's max-min realization plan)
    R->>R: β(c) = x(σ_h c) / x(σ_h)  — divide child by parent
    Note over R: behaviour strategy recovered directly;<br/>NO normal form was ever built

What it shows: the end-to-end zero-sum pipeline, with the duality step that produces both players’ strategies from one solve. The insight: the last step is a division, not a search. Because x* is a realization plan, the behavioural strategy is read off by dividing each sequence’s probability by its parent’s — the inverse of the multiplication that defined β_i[σ]. Where the parent is zero the information set is irrelevant and the behaviour there is arbitrary, which is Proposition 3.10’s “unique except at irrelevant information sets.”

General-sum: a linear complementarity problem

If B ≠ −A, the two best-response LPs cannot be fused into one objective. What survives is complementary slackness. A feasible x is optimal for (3.27) exactly when there is a dual u with Eᵀu ≥ Ay and xᵀ(Eᵀu − Ay) = 0; symmetrically for player 2 with yᵀ(Fᵀv − Bᵀx) = 0. Both vectors in each product are nonnegative, so the condition says they cannot both be positive in the same coordinate.

Theorem 3.14 (von Stengel). (x, y) is an equilibrium iff there are vectors u, v with

Ex = e,  x ≥ 0        Fy = f,  y ≥ 0
Eᵀu − Ay ≥ 0          Fᵀv − Bᵀx ≥ 0
xᵀ(Eᵀu − Ay) = 0      yᵀ(Fᵀv − Bᵀx) = 0

The size of E, F, A, B is linear in the size of the game tree.

The 1996 companion paper states it as Theorem 1.2 of the STOC version: “The Nash equilibria of a general two-player perfect-recall game in extensive form are the solutions of a linear complementarity problem whose size, in sparse representation, is linear in the size of the game tree. The problem of finding an equilibrium can be solved by Lemke’s algorithm” (Koller, Megiddo & von Stengel, STOC 1994).

flowchart TB
    subgraph CS["Complementary slackness, per sequence σ of player 1"]
        direction TB
        Q{"Is x_σ strictly positive?<br/>(do I ever play this sequence?)"}
        Y1["YES ⟹ the slack must vanish:<br/>(Eᵀu − Ay)_σ = 0<br/>σ is an OPTIMAL continuation —<br/>its value equals the information set's value"]
        N1["NO (x_σ = 0) ⟹ the slack may be positive:<br/>(Eᵀu − Ay)_σ ≥ 0 with slack allowed<br/>σ is a strictly WORSE continuation,<br/>so it is never played"]
        Q -- "played" --> Y1
        Q -- "not played" --> N1
    end
    BOTH["Impose the same condition for player 2 with<br/>yᵀ(Fᵀv − Bᵀx) = 0, plus feasibility Ex=e, Fy=f, x,y ≥ 0"]
    LCPB["A LINEAR COMPLEMENTARITY PROBLEM<br/>Theorem 3.14 — size linear in the game tree"]
    LEM["Solved by LEMKE's algorithm:<br/>add an auxiliary column and scalar z₀,<br/>start at x = 0, y = 0,<br/>pivot keeping complementarity,<br/>stop when z₀ leaves the basis"]
    CS --> BOTH --> LCPB --> LEM

What it shows: what the two orthogonality conditions actually assert, resolved to the level of a single sequence. The insight: complementarity is the sequence-form restatement of the indifference principle — every sequence played with positive probability must be exactly optimal, and every strictly suboptimal sequence must carry probability zero. It is the same condition that governs Mixed Strategies in a normal-form game, transplanted from strategies to paths.

Why Lemke and not Lemke–Howson. This is the single most-missed point in the area. The Lemke-Howson Algorithm solves the LCP arising from a bimatrix game, where the strategy constraints are single normalization rows (1ᵀx = 1) and the dual variables are scalars that can be eliminated by scaling. In the sequence form the constraints are a whole matrix E and the duals u, v are vectors of unconstrained variables — as von Stengel puts it, “u and v are not scalar dual variables that are easily eliminated from the system.” Koller, Megiddo and von Stengel’s contribution in the second GEB paper is exactly this repair: use Lemke’s (1965) more general complementary pivoting algorithm, which introduces an auxiliary column and a scalar z₀ giving an initial feasible basis at x = 0, y = 0, then pivots — r_σ leaves the basis as x_σ enters, maintaining complementarity — until z₀ leaves the basis, at which point the solution is an equilibrium. They prove termination for this particular LCP; it is not automatic, since Lemke’s algorithm can in general ray-terminate without a solution.

The complexity context is the one PPAD-Completeness supplies: an LCP formulation does not make the general-sum problem polynomial. Lemke’s algorithm, like Lemke–Howson, is a path-following method whose path can be exponentially long, and the underlying two-player Nash problem is PPAD-complete. What the sequence form buys is that the LCP is linear in the tree rather than exponential — you have removed the representational blow-up, not the intrinsic hardness.

---

Verified: Kuhn Poker, Exactly

A representation is only trustworthy if it reproduces a known answer. Kuhn poker’s value to player 1 is −1/18, and its equilibria form a one-parameter family indexed by α ∈ [0, 1/3], the probability with which player 1 bluffs the jack (Kuhn Poker). I built the E, F, A above from the tree, constructed the realization plans of that family from the known behaviour strategies, and evaluated xᵀAy in exact rational arithmetic.

=== Equilibrium check: value of the game for the one-parameter family ===
  alpha =    0:  Ex=e? True   Fy=f? True   value x^T A y = -1/18   (= -1/18? True)
  alpha = 1/12:  Ex=e? True   Fy=f? True   value x^T A y = -1/18   (= -1/18? True)
  alpha =  1/9:  Ex=e? True   Fy=f? True   value x^T A y = -1/18   (= -1/18? True)
  alpha =  1/6:  Ex=e? True   Fy=f? True   value x^T A y = -1/18   (= -1/18? True)
  alpha =  1/4:  Ex=e? True   Fy=f? True   value x^T A y = -1/18   (= -1/18? True)
  alpha =  1/3:  Ex=e? True   Fy=f? True   value x^T A y = -1/18   (= -1/18? True)

Two checks in one line each. Ex = e and Fy = f confirm the plans are genuinely feasible points of the two polytopes — that the behaviour-to-realization conversion respected flow conservation at all six information sets. And the value is −1/18 exactly, for every member of the family, which is the defining property of an equilibrium family in a zero-sum game.

Feasibility and the right value do not by themselves prove equilibrium. So, separately, an exhaustive best-response check. Because a best response can always be taken pure, it suffices to enumerate all reduced pure strategies — 3³ = 27 for player 1 and 4³ = 64 for player 2 — convert each to its realization plan, and evaluate:

=== Exact best-response verification (alpha = 1/9) ===
  P1 reduced pure strategies enumerated: 27   best payoff vs y* = -1/18  (strategy ('pf','pf','pc'))
  P2 reduced pure strategies enumerated: 64   best (lowest) payoff vs x* = -1/18  (strategy ('bp','pb','bb'))
  Both equal -1/18 = -1/18 ?  True

(Original computation for this note, fractions.Fraction throughout — no floating point anywhere, so −1/18 is an exact identity and not a rounding coincidence.) Player 1 cannot beat −1/18 against y* and player 2 cannot hold him below −1/18 against x*: the pair is an equilibrium, verified rather than asserted, and it was verified through the sequence-form matrices, which therefore encode the game correctly.

The best-responding pure strategies are themselves informative. Player 1’s is ('pf','pf','pc') — check-fold with the jack, check-fold with the queen, check-call with the king. Against this particular y* the queen never wants to call. Player 2’s is ('bp','pb','bb'): with the jack, bet if checked to and fold to a bet (a pure bluff); with the queen, check if checked to and call a bet; with the king, bet and call. These are pure best responses to a mixed equilibrium strategy, which is what the indifference condition predicts — see Mixed Strategies.

---

Where the Sequence Form Came From

The idea was found more than once, which is itself a comment on how natural it is once you look at the tree instead of the strategy list.

timeline
    title Independent discoveries and the consolidation
    1953 : Kuhn — information sets, perfect recall, and Kuhn's theorem (behaviour ≡ mixed under perfect recall)
    1962 : Romanovskii — a Russian-language construction containing the main ideas, unknown in the West for decades
    1964-1965 : Lemke & Howson — complementary pivoting for bimatrix games; Lemke's more general algorithm
    1972 : Wilson — best responses generated directly from the game tree as Lemke-Howson pivoting columns
    1992 : Koller & Megiddo (GEB) — first polynomial-time algorithm for zero-sum extensive games; realization weights for ONE player, ellipsoid method with a backward-induction separation oracle
    1993-1994 : von Stengel's technical report, then Koller, Megiddo & von Stengel at STOC '94 — sequences used SYMMETRICALLY for both players; LP and LCP both linear in the tree
    1996 : Two companion GEB papers — von Stengel (zero-sum, the name "sequence form"); Koller, Megiddo & von Stengel (general-sum, Lemke's algorithm)
    2002 : von Stengel's Handbook of Game Theory chapter 45 — the scholarly consolidation
    2007 : Zinkevich et al. — CFR; iterative regret minimisation displaces LP at poker scale
    2010-2024 : First-order methods and Blackwell approachability on the same polytope, now called the "treeplex"

What it shows: three independent arrivals at the same construction, and the two-step consolidation into the modern form. The insight: Koller & Megiddo’s 1992 algorithm was already polynomial, but by a very different route — it kept an LP with exponentially many inequalities and made it tractable by solving the separation problem with backward induction, feeding the ellipsoid method. von Stengel’s improvement was to treat both players symmetrically, which makes the whole system small rather than making a large system separable. The 2024 literature calls the resulting polytope a treeplex and writes the equilibrium problem as min_{x ∈ X} max_{y ∈ Y} ⟨x, My⟩ where X and Y are sequence-form polytopes, noting that this “can be formulated as a linear program [von Stengel, 1996]” but that first-order methods are preferred at scale (Chakrabarti, Grand-Clément et al., arXiv:2403.04680 §2).

von Stengel’s own attribution is precise and worth repeating verbatim, because secondary sources routinely credit only one of the three: “Main ideas of the sequence form have been discovered independently by (Koller and Megiddo, 1992; Romanovskii, 1962; von Stengel, 1996)” (AGT ch. 3 §3.12).

Uncertain

Verify: the content of I. V. Romanovskii’s 1962 paper (Reduction of a game with complete memory to a matrix game, Soviet Mathematics 3:678–681) and precisely which of the sequence-form ideas it contains. Reason: cited only through von Stengel’s attribution line; the original is in Russian, was not retrieved during this task, and no English translation was located. To resolve: locate the Soviet Mathematics — Doklady translation and compare its construction with Proposition 3.10.

---

Failure Modes and Gotchas

Perfect recall is not a technicality — without it the problem is NP-hard. The characterization of realization plans by linear constraints depends entirely on σ_h being well defined, i.e. on all nodes of an information set being reached by the same own-move sequence. Koller, Megiddo and von Stengel state the general situation bluntly: “The major problem in this context is in deciding whether a particular vector x = (x_σ) represents some mixed strategy μ₁. In general, this problem is NP-hard. However, if the players have perfect recall, we can characterize realization weights by a small set of linear constraints” (STOC 1994 §4). It gets worse: for a zero-sum game, Koller & Megiddo (1992, p. 534) showed it is NP-hard to find an optimal mixed strategy for a player without perfect recall, and a max-min behaviour strategy may involve irrational numbers even for a player with the weaker “perfect memory” property (p. 537) — so it cannot be the solution of any LP with rational data. If your model has absent-minded or abstracted-away memory, the sequence form does not merely lose efficiency; it stops applying.

There is one salvage, and it is narrow. For a player with perfect memory (may forget earlier moves, but not earlier knowledge), von Stengel shows Theorems 5.1 and 5.2 still hold “provided a player without perfect recall may use mixed strategies,” via the complete inflation of the game — but the resulting equilibrium strategies “may no longer be behaviour strategies for a player without perfect recall, since the probability for a move at an information set that is partitioned in the complete inflation may depend on an earlier move.”

The equilibrium you get is not subgame perfect. von Stengel is explicit: “the equilibria that can be computed with the sequence form are arbitrary and need not induce an equilibrium in every subgame, in which case they are not subgame perfect.” The LP/LCP knows about reachable payoffs; behaviour at information sets with realization probability zero is entirely unconstrained. If you need Subgame Perfect Equilibrium or Sequential Equilibrium, you must either decompose by subgames first (von Stengel’s Algorithm 3.9 — find an equilibrium of each subgame in increasing order of inclusion and replace it by its payoff pair) or use a perturbed formulation. OpenSpiel implements the latter, following Miltersen & Sørensen’s perturbed LPs for sequential equilibria — the module’s own docstring names both constructions and the equations it builds (sequence_form_lp.py).

Irrelevant information sets make the behaviour strategy non-unique, and code must handle the division by zero. Recovering β(c) = x(σ_h c) / x(σ_h) is undefined when x(σ_h) = 0. Proposition 3.10 says the behaviour there is arbitrary; implementations must pick something. OpenSpiel picks the uniform distribution, guarded by an explicit epsilon:

        unif_pr = 1.0 / num_actions
        ...
        pr_action = (rel_weight / total_weight if total_weight > 1e-20 else unif_pr)

That 1e-20 is a real engineering decision hiding behind a theorem: “unique except at irrelevant information sets” becomes, in floating point, “unique except where the denominator underflows,” and the two are not the same set.

Sequence-form matrices must be stored sparsely or the whole point is lost. Every size theorem in this note is stated “in sparse representation.” A is |S₁| × |S₂| cells with only O(leaves) nonzeros; materializing it densely reintroduces a quadratic blow-up in the tree size — not exponential, but enough to matter. Kuhn poker at n = 20 cards is 6,561 cells with 1,900 nonzeros; a game with 10^6 sequences per player is 10^12 dense cells and perhaps 10^7 nonzeros.

Do not confuse the sequence form with an abstraction. Abstraction (bucketing hands, merging betting sequences) is a lossy reduction that changes the game; the sequence form is lossless and changes only the coordinates. Poker solvers use both, and conflating them leads to the wrong conclusion about where the approximation error comes from. In the CFR paper’s own framing, the LP-with-realization-plans representation “is linear in the number of game states, rather than exponential, but considerable additional technology is still needed to handle games the size of poker. Abstraction, both hand-chosen and automated, is commonly employed” (Zinkevich et al. 2007 §1).

Chance probabilities live in the payoff matrix, not in the constraints. a_{στ} already multiplies by β₀[σ₀(t)]. A common bug is to also weight the realization plan by chance, double-counting the deal. The Kuhn matrix above is the diagnostic: every entry should be a chance probability times a chip count, and if the 1/6s appear anywhere in E or F, something is wrong. Relatedly, von Stengel assumes all chance probabilities are positive, “by pruning any tree branches that are unreached by chance” — a zero-probability branch breaks the “only if” direction of realization equivalence.

Degeneracy. The LCP for a general-sum sequence form inherits every degeneracy pathology of complementary pivoting. Gambit’s implementation routes both the normal-form and extensive-form LCP through the same tableau machinery (src/solvers/lcp/efglcp.cc alongside nfglcp.cc, sharing src/solvers/linalg/lemketab.{h,cc} — repository tree, fetched 2026-08-29), and the lexicographic-perturbation discipline discussed in The Lemke-Howson Algorithm applies unchanged.

---

Alternatives and When to Choose Them

This is the section that matters in practice, and the honest comparison is with Counterfactual Regret Minimization — which is not an alternative representation, a point that is widely misunderstood.

The 2024 treeplex literature says it plainly: CFR “is a regret minimizer for the treeplex” (arXiv:2403.04680 §1). The treeplex is the sequence-form polytope. So CFR and sequence-form LP operate on the same feasible set and solve the same saddle-point problem min_{x∈X} max_{y∈Y} ⟨x, My⟩. They differ in the algorithm applied to it, and that difference is entirely about scale and about what you want out of the answer.

	Sequence-form LP / LCP	Counterfactual Regret Minimization
What it solves	the exact LP (zero-sum) or LCP (general-sum)	the same saddle point, iteratively
Answer quality	exact rational equilibrium (with exact arithmetic)	ε-equilibrium; ε → 0 as O(1/√T)
Memory	the four sparse matrices + the simplex/LCP tableau; basis fill-in is the binding constraint	O(1) numbers per information-set action pair — regret sum and strategy sum
Per-step cost	a pivot on the tableau	one tree traversal (vanilla) or one sampled trajectory
Guarantee	zero-sum: polynomial. General-sum: exponential worst case (Lemke); underlying problem is PPAD-complete	zero-sum two-player: average strategy converges to Nash. General-sum: no such guarantee
Practical ceiling (2007 data)	abstractions of ~10^7 game states	10^12 game states (CFR10, 2,000 M iterations, 326 h on 4 CPUs)
Anytime?	no — a partial simplex run is not a strategy	yes — stop whenever, the average strategy is your answer
Best for	small and medium trees where you want the exact answer, all equilibria, or a certified value	large trees, poker-scale, where an approximate answer that improves monotonically is what you need

The scale numbers deserve their own line because they are the reason the field moved. The CFR paper’s own framing of the state of the art it displaced: “State of the art in solving extensive games has traditionally made use of linear programming using a realization plan representation” — citing Koller & Megiddo — with abstraction reducing two-player limit Texas hold’em “from 10^18 to a tractable number of game states (e.g., 10^7)”; iterative first-order methods had reached 10^10; and CFR’s reported results reach 10^12:

Abs   Size (×10⁹)  Iterations (×10⁶)  Time (h)  Exploitability (mb/h)
 5          6.45               100        33            3.4
 6         27.7                200        75            3.1
 8        276                  750       261            2.7
10       1646                 2000       326†           2.2
                                    †: parallel implementation with 4 CPUs

(Zinkevich et al. 2007, Figure 1a.) The measured convergence behaviour is what makes it work: “the number of iterations needed is growing linearly with the number of information sets” while “the time per iteration is nearly independent of the size of the abstraction,” so “the overall computational complexity is only linear in the size of the chosen card abstraction.”

When each is right, stated plainly.

• Use the sequence-form LP when the tree is small enough to build (up to roughly 10^5–10^7 sequences depending on your solver and memory), when you need an exact rational answer, when you need the value certified rather than estimated, or when you need to enumerate or characterize the equilibrium set rather than find one point in it. Kuhn poker, Leduc hold’em, inspection games, small negotiation and signalling models: this is the right tool, and it is the one that gives you a number you can put in a proof.
• Use CFR when the tree is too large for a tableau, when an anytime approximate answer is acceptable, when you want to exploit sampling (external/outcome sampling, CFR+) to make per-iteration cost independent of tree size, or when you intend to abstract anyway — in which case the abstraction error dominates the solver error and exactness is a false economy.
• Use neither when the game has perfect information, where Backward Induction is linear-time and gives a pure subgame-perfect equilibrium directly.
• Use the reduced normal form plus The Lemke-Howson Algorithm only when the tree is tiny and you specifically want the bimatrix machinery — for instance to enumerate all equilibria via Support Enumeration, which has no clean sequence-form analogue. The STOC 1994 paper does offer a sequence-form improvement here (Theorem 4.2: all Nash equilibria can be found in time exponential in the tree size rather than doubly exponential, by enumerating only small supports, justified by Theorem 4.1 — every strategy has an equivalent one whose support is at most the number of leaves) but it remains exponential.
• Use first-order methods on the treeplex — Excessive Gap Technique, Mirror Prox, predictive online mirror descent, Blackwell approachability — when you want CFR’s memory profile with a better rate. These reach O(1/T) versus CFR’s O(1/√T) and operate on the identical polytope (arXiv:2403.04680 §1).

The framing to carry away: the sequence form is the representation; LP, LCP, CFR and first-order methods are four algorithms over it. Choosing CFR is not choosing against the sequence form — it is choosing an iterative method over an exact one on the same polytope.

---

Production Notes

OpenSpiel ships a sequence-form LP and names its sources. open_spiel/python/algorithms/sequence_form_lp.py (550 lines, fetched 2026-08-29) states in its module docstring: “In this implementation, we follow closely the construction in Koller, Megiddo, and von Stengel, Fast Algorithms for Finding Randomized Strategies in Game Trees… Specifically, we construct and solve equations (8) and (9) from this paper.” Equations (8) and (9) are exactly the primal/dual pair reproduced above as (3.29)/(3.30) — player 2’s min-max LP and its dual. The same module implements the sequential-equilibrium refinement via Miltersen & Sørensen’s perturbed LPs. The build is a single recursive traversal accumulating chance_reach and threading parent_is_keys — i.e. the σ_h bookkeeping made concrete.

Gambit implements the extensive-form LCP as a first-class solver. src/solvers/lcp/efglcp.cc sits beside nfglcp.cc and both use src/solvers/linalg/lemketab.{h,cc} — Lemke’s tableau, distinct from lhtab.{h,cc}, the Lemke–Howson tableau used only for bimatrix games. That file split is Theorem 3.14’s warning (“the LH algorithm cannot be applied … u and v are not scalar dual variables”) expressed as source layout. Gambit also carries src/games/behavspt.h and the behaviour-strategy machinery in src/games/gametree.h — the extensive-form side is not a thin wrapper over the normal form.

Neither is installed on this machine. Verified during the MOC build (2026-08-28): no pip, no numpy, no gambit CLI. Every matrix and every number in this note came from Python’s standard library with fractions.Fraction. That is a constraint worth embracing rather than working around: on a game the size of Kuhn poker, exact rational arithmetic makes the −1/18 an identity you can assert, and floating point makes it a number you have to squint at. For the C implementation the MOC calls for, the same logic points to integer pivoting — the technique documented in The Lemke-Howson Algorithm — over floating-point simplex.

What actually limits the LP in practice is fill-in, not the matrix. The four matrices are sparse by construction; the simplex basis factorization is not. This is the standard reason large sequence-form LPs die on memory rather than time, and it is why Gilpin, Hoda, Peña and Sandholm’s first-order methods (2010, Mathematics of Operations Research 35(2):494–512) and the whole subsequent treeplex literature exist — they need only matrix-vector products with A, never a factorization.

Uncertain

Verify: the bibliographic details and headline results of Hoda, Gilpin, Peña & Sandholm, Smoothing Techniques for Computing Nash Equilibria of Sequential Games. Reason: the CMU-hosted PDF returned HTTP 404 during this task, and the citation here comes from a web-search summary plus the citation list in arXiv:2403.04680, which was fetched. To resolve: retrieve the Mathematics of Operations Research paper or its CMU technical-report version and check the volume/pages and the exact convergence rate claimed.

The historical arc is the useful production lesson. The sequence form did not make poker solvable on its own; it made poker formulable, and then abstraction plus iterative methods made it solvable. The 1996 papers turned an exponential representation into a linear one; the 2007 CFR paper turned a linear-but-still-enormous LP into a memory-light iteration; the 2015+ work (CFR+, first-order methods, and the superhuman systems built on them) refined the iteration. Every one of those steps operates on the polytope von Stengel wrote down. If you are building a solver for a tree-structured imperfect-information game today, the sequence form is not one of your options — it is the coordinate system, and your choice is which algorithm to run in it.

---

See Also

• Extensive-Form Games — the modelling background: information sets, perfect recall, realization plans, Kuhn’s theorem, and the strategy-count blow-up measured on three real games
• Kuhn Poker — the worked game used throughout, its twelve information sets, and the derivation of the −1/18 value verified here
• Counterfactual Regret Minimization — the iterative alternative on the same polytope; the honest comparison is in Alternatives above
• The Lemke-Howson Algorithm — the bimatrix complementary-pivoting method, and why it does not apply to the sequence-form LCP
• Backward Induction — what the dual constraints Eᵀu ≥ Ay are, written as a recursion; linear-time for perfect information
• Subgame Perfect Equilibrium — the refinement the sequence form does not deliver by itself; use von Stengel’s Algorithm 3.9 instead
• Sequential Equilibrium — the stronger refinement, reachable from the sequence form via perturbed LPs
• Zero-Sum Games and the Minimax Theorem — the normal-form ancestor of the LP in this note; LP duality is the minimax theorem
• PPAD-Completeness — why the general-sum LCP is exponential no matter how small you make the matrices
• Support Enumeration — the enumeration approach that has no clean sequence-form analogue, and the STOC ‘94 small-support theorem that partly rescues it
• Mixed Strategies — the indifference condition that explains why pure best responses to a mixed equilibrium are what the verification above found
• Imperfect Information and Information Sets — the modelling device that makes all of this necessary
• Games and Strategic Systems in C MOC — the parent map; stages P3 (game trees) and P6 (learning in games)