vault

PPAD-Completeness

45 min read

PPAD-Completeness

PPAD — “polynomial parity argument, directed version” — is the complexity class that exists because Nash’s theorem is true. That sounds like a joke and is not. A problem whose answer is guaranteed to exist for every input cannot be NP-complete unless NP = coNP (Megiddo & Papadimitriou 1991, Theorem 2.1), so the entire machinery of NP-hardness — the standard vocabulary for saying “this is intractable” — is unavailable for computing a Nash equilibrium. Christos Papadimitriou’s response was to build a new vocabulary: classify total search problems by which non-constructive lemma their existence proof leans on, and take completeness in that class as the evidence of hardness (Papadimitriou 1994, JCSS 48(3):498–532; venue and pagination confirmed against dblp). PPAD is the class whose lemma is “a directed graph with an unbalanced node has a second unbalanced node.” Twelve years later, computing a mixed Nash equilibrium was proved complete for it — first for three or more players (Daskalakis, Goldberg & Papadimitriou), then, surprisingly, for two (Chen & Deng 2005/2006). This note is the complexity-theoretic backing for the claim that runs through Games and Strategic Systems in C MOC: existence is not construction.

Where this sits

This is the theory note behind stage P2 of Games and Strategic Systems in C MOC. It assumes you know what a mixed strategy is (Mixed Strategies) and what an equilibrium is (Nash Equilibrium); it explains why the two algorithms in that stage — Support Enumeration and The Lemke-Howson Algorithm — are both exponential in the worst case and why nobody has done better. The contrast that makes it practically useful is at the end: Zero-Sum Games and the Minimax Theorem and Correlated Equilibrium are both polynomial-time solvable by linear programming, so the hardness is specific to general-sum Nash and not to “games” as such.

Mental Model: A Proof You Can Follow but Never Finish

Start with the definitional layer, because almost every confusion about PPAD is a confusion about what kind of object is being classified.

NP is a class of decision problems: given an input, answer yes or no. Equilibrium computation is not a decision problem — the output is a strategy profile, not a bit. The corresponding class of search problems is FNP (“functional NP”): given an instance, produce a witness, or output the string "no" if none exists (Roughgarden, CS364A Lecture 20 §2). FP is the subclass solvable in polynomial time. Formally, FNP is parameterized by a polynomially balanced, polynomial-time recognizable relation R ⊆ Σ* × Σ*: on input x, return some y with (x,y) ∈ R (Papadimitriou 1994 §2).

TFNP — “total functions in NP” — is the subclass of FNP where a witness always exists: for every x there is some y with (x,y) ∈ R, so the "no" branch is dead code. Megiddo and Papadimitriou introduced it in 1991 and immediately noted the identity that makes it strange: TFNP coincides with F(NP ∩ coNP). Their listed members were factoring, local optimization (PLS), Brouwer fixed points, a computational Sperner’s lemma, bimatrix equilibria, and the linear complementarity problem for P-matrices (Megiddo & Papadimitriou 1991).

Here is the key intuition, stated crisply by Goldberg and Papadimitriou two and a half decades later: to place a problem in TFNP you must prove a theorem of the form ∀x ∃y Φ(x,y). If that proof is constructive in a computationally meaningful sense, the problem is in FP and there is nothing to discuss. So every intractable TFNP problem must harbour an exponentially non-constructive step — usually a combinatorial lemma asserting that some element exists in an exponentially large structure (Goldberg & Papadimitriou, TFNP: An Update, CIAC 2017). Classify the problems by which lemma, and you get subclasses with complete problems.

flowchart TB
    subgraph FNP["FNP — search problems, witness may or may not exist"]
        direction TB
        FSAT["FSAT<br/>(FNP-complete)<br/>a formula may be unsatisfiable"]
        subgraph TFNP["TFNP — a witness ALWAYS exists (= F(NP ∩ coNP))"]
            direction TB
            FACT["Factoring<br/>lemma: fundamental theorem of arithmetic"]
            subgraph PPA["PPA — 'a graph with an odd-degree node has another'"]
                direction TB
                SMITH["SMITH: second Hamilton cycle<br/>in an odd-degree graph"]
                subgraph PPAD["PPAD — 'a directed graph with an unbalanced<br/>node has another'"]
                    EOL["END OF THE LINE<br/>(the canonical complete problem)"]
                    NASHP["NASH · BROUWER · SPERNER<br/>KAKUTANI · P-LCP · ARROW-DEBREU"]
                end
            end
            subgraph PLS["PLS — 'every DAG has a sink'"]
                LOCALCUT["Local max-cut,<br/>pure equilibria of congestion games"]
            end
            PPP["PPP — pigeonhole principle<br/>PIGEONHOLE CIRCUIT"]
        end
    end
    FP["FP — solvable in polynomial time<br/>zero-sum Nash, correlated equilibrium"] --> PPAD
    FP --> PLS
    PPAD -.->|"⊆"| PPP

What it shows: the containment lattice of total search classes and where the game-theoretic problems land. The insight: PPAD is not “a bit harder than P” — it is a sibling of PLS, not a subset of it, sitting inside TFNP, which itself sits inside FNP but cannot contain an FNP-complete problem without collapsing NP and coNP. Everything below is a consequence of that one structural fact. Papadimitriou proved FP ⊆ PPAD ⊆ PPA ⊆ FNP (Proposition 1) and, with Vavasis and Yannakakis, PPAD ⊆ PPP (Proposition 4); whether PPA = PPAD was open in 1994 and, as of this writing, remains so.

Why Totality Kills NP-Completeness — The Argument Everyone Skips

This is the subtle point that motivates PPAD’s existence, and it is usually compressed into a parenthesis. It deserves the space.

Theorem (Megiddo & Papadimitriou 1991, Thm 2.1). There is an FNP-complete problem in TFNP if and only if NP = coNP.

The “if” direction is immediate: TFNP = F(NP ∩ coNP), so if NP = coNP then NP ∩ coNP = NP and any FNP-complete problem already lives there. The “only if” direction is the interesting one, and it is short enough to walk through symbol by symbol.

Suppose some total problem Π is FNP-complete. Then functional SAT reduces to it: there exist polynomial-time functions

  • f mapping a Boolean formula φ to an instance f(φ) of Π, and
  • g mapping any solution y of f(φ) back to either a satisfying assignment of φ or the literal string "no".

Now take an unsatisfiable φ. Because Π is total, f(φ) still has a solution y — this is the whole trick. That y is short (polynomially bounded) and it is efficiently checkable: run f on φ to reconstruct the instance, verify (f(φ), y) ∈ R, then run g and confirm it returns "no". If both checks pass, φ is genuinely unsatisfiable. So y is a short, polynomial-time-verifiable certificate of unsatisfiability — which is exactly a nondeterministic algorithm for UNSAT, i.e. coNP ⊆ NP, hence NP = coNP.

Roughgarden’s rendering makes the same point about bimatrix games specifically and adds the crucial supporting fact: Nash equilibria have descriptions of polynomial length, because once you fix the supports the mixing probabilities are recovered by solving a linear system (Lecture 20, Theorem 3.1 and footnote 2). Without that, the certificate would not be short and the argument would not run.

sequenceDiagram
    autonumber
    participant U as Unsatisfiable formula φ
    participant f as Reduction f (poly-time)
    participant Pi as Total problem Π
    participant g as Back-map g (poly-time)
    participant V as Verifier

    U->>f: φ
    f->>Pi: instance f(φ)
    Note over Pi: Π is TOTAL — a solution y exists<br/>even though φ has no satisfying assignment
    Pi-->>g: solution y (polynomially short)
    g-->>V: g(y) = "no"
    V->>V: recompute f(φ); check (f(φ), y) ∈ R; check g(y) = "no"
    V-->>U: certified UNSATISFIABLE in poly time
    Note over V,U: y is a short proof of unsatisfiability<br/>⟹ coNP ⊆ NP ⟹ NP = coNP

What it shows: the chain of implications turning an FNP-completeness reduction into a coNP certificate. The insight: totality is not a convenience, it is the load-bearing hypothesis. The reduction is forced to hand you a witness for a “no” instance, and that witness becomes the unsatisfiability proof that complexity theorists do not believe exists. This is why “prove NASH is NP-complete” was never a viable research programme, and why the field had to invent a new class instead of reusing the old one.

A tempting counter-move is: fine, ask for a Nash equilibrium with a property. That does become NP-complete — deciding whether a game has an equilibrium maximizing the sum of payoffs, or one placing positive probability on a given strategy, is NP-hard (Gilboa & Zemel 1989; Conitzer & Sandholm 2003, both cited in DGP §1). But that problem is no longer total: an equilibrium with the requested property need not exist, and the "no" branch comes back to life. The instant you restore the possibility of “no solution,” NP-completeness becomes available again — which is the cleanest possible confirmation that totality was the obstruction.

Megiddo and Papadimitriou made the same point with a beautiful concrete example: SECOND TRICHROMATIC TRIANGLE — given a Sperner labelling and one trichromatic triangle, decide whether another exists — is NP-complete (their Theorem 2.2). Finding a Sperner triangle is total and lands in PPAD; deciding whether a second one exists is not total and lands in NP-complete. Same combinatorial object, one word of difference, entirely different complexity.

Uncertain

Verify: the exact statements of Gilboa & Zemel (1989) and Conitzer & Sandholm (2003) on which equilibrium-with-property questions are NP-complete. Reason: both are cited second-hand from the DGP survey, which was fetched; neither original was retrieved during this task. To resolve: fetch Games and Economic Behavior 1(1):80–93 and the IJCAI 2003 proceedings and check which properties (max welfare, given support, uniqueness, count > 1) are individually proved hard.

END OF THE LINE: The Canonical Complete Problem

Papadimitriou’s 1994 definition of PPAD is machine-based rather than problem-based. A problem in PPA is given by a polynomial-time machine M and a polynomial p; the configuration space on input x is C(x) = Σ^{p(|x|)}, all strings of that length; and M(x,c) outputs a set of at most two configurations. Neighbourhood is defined symmetrically by fiat — [c,c'] ∈ G(x) iff c ∈ M(x,c') and c' ∈ M(x,c) — which syntactically guarantees G(x) is an undirected graph of degree ≤ 2 without requiring M to be consistent. M is standardized so that 0…0 is always a leaf. The problem: find a leaf other than 0…0.

To get PPAD, “modify the definition of PPA so that M(x,c) is an ordered pair of configurations. The graph G(x) is now directed: (c,c') ∈ G(x) iff c' is the second component of M(x,c), and c is the first component of M(x,c'). We are asking for any node (other than 0…0) with indegree + outdegree = 1” (Papadimitriou 1994 §2). Both classes are then closed under reductions by definition.

The modern presentation replaces the machine with two Boolean circuits and gives the problem a name. The name has drifted — Rubinstein notes that “in the literature the problem has been called EndOfTheLine; we believe that the name EndOfALine is a more accurate description” (Rubinstein 2016, footnote 1) — but the definition is stable:

END OF A LINE (Rubinstein Def. 1.1, attributed to Daskalakis–Goldberg–Papadimitriou). Given two circuits S and P, each with m input bits and m output bits, such that P(0^m) = 0^m ≠ S(0^m), find an input x ∈ {0,1}^m such that P(S(x)) ≠ x or S(P(x)) ≠ x ≠ 0^m.

Walk that symbol by symbol. S is the successor circuit, P the predecessor circuit. A directed edge v → v' is deemed to exist only when both circuits agree: S(v) = v' and P(v') = v. This mutual-consistency convention is what forces in-degree and out-degree to be at most 1 without trusting the circuits — a lying circuit simply produces extra solutions, never an unsolvable instance. The precondition P(0^m) = 0^m ≠ S(0^m) says the all-zeros string has no predecessor and does have a successor: it is the standard source. The graph is therefore a disjoint union of simple paths and simple cycles over 2^m nodes. The parity argument then says: the path leaving 0^m must stop somewhere, and where it stops is a solution. P(S(x)) ≠ x catches a sink; S(P(x)) ≠ x ≠ 0^m catches a non-standard source.

flowchart LR
    subgraph implicit["The implicitly defined graph on 2^m nodes"]
        direction LR
        Z(("0…0<br/>standard<br/>source")) --> A1((·)) --> A2((·)) --> A3((·)) --> SINK(("sink<br/>SOLUTION"))
        B0(("non-standard<br/>source<br/>SOLUTION")) --> B1((·)) --> B2(("sink<br/>SOLUTION"))
        C1((·)) --> C2((·)) --> C3((·)) --> C1
        ISO(("isolated<br/>node"))
    end
    CIRC["Circuits S and P<br/>size poly(m)<br/>the ENTIRE input"] -.->|"defines"| implicit

What it shows: the shape of every PPAD instance — paths, cycles, and isolated nodes — with the three kinds of legal answer marked. The insight: the input is the pair of circuits, not the graph. The graph has 2^m nodes and is never materialized. Naive path-following from the standard source is guaranteed correct and can take 2^m − 1 steps; the entire question of PPAD = FP is whether you can telescope that path without walking it. Note also the free gift the definition hands you: cycles and isolated nodes are ignorable, and a second source is just as good an answer as a sink.

Papadimitriou’s own intuition pump for why this is hard is worth quoting, because it is a better explanation than most formal treatments:

“Everybody remembers all games of chess they have played in their life. You have played an odd number of games, and you must find a fellow odd player (known to exist by the parity argument). Depth-first search can solve this problem, but it is too memory-consuming. […] Alas, this algorithm may take time proportional to the number of all games of chess ever played!” — Papadimitriou 1994 §1

The “chessplayer algorithm” is not a throwaway; formalizing it proves Theorem 1 of the paper, that PPA' = PPA — allowing polynomially large degree and asking for any odd-degree node gives no extra power, because you can split each degree-k node into ⌈k/2⌉ degree-≤2 nodes using a pairing of its incident edges. This robustness under redefinition is what makes PPA and PPAD feel like natural classes rather than artifacts.

One redefinition is not harmless, and it is the sharpest illustration of why “find the other end of this path” is a different problem from “find an end”:

Theorem 2 (Papadimitriou 1994). If we demand the particular leaf at the other end of the standard path, the resulting classes PPA" and PPAD" equal FPSPACE.

The proof uses Bennett’s result that every polynomial-space computation can be made reversible, so each configuration has at most one predecessor and one successor; the configuration graph of a reversible PSPACE machine is then exactly a PPAD-style line, and its far end is the halting configuration containing the answer. Asking for any end is PPAD; asking for the end is all of PSPACE. The gap between those two questions is the entire subject.

Worked Computation: A Polynomial Circuit With an Exponential Path

The phrase “exponentially long path in a polynomial-size implicit graph” is easy to nod along to and hard to feel. So here is a concrete END OF A LINE instance you can run, built with nothing but int arithmetic.

Take M = 2^m and the affine map S(v) = (5v + 1) mod 2^m. By the Hull–Dobell criterion a linear congruential map v ↦ av + c (mod 2^m) has full period 2^m when c is odd and a − 1 is divisible by 4; with a = 5, c = 1 both hold, so the map is a single 2^m-cycle. Break the cycle by making the unique predecessor of 0 into a sink and 0 into a source, exactly matching the END OF A LINE precondition. Both S and P are a multiply-and-add on m bits — a circuit of size O(m²) at worst, O(m) with a carry-save adder — while the path they define has 2^m − 1 edges.

=== END OF THE LINE: a poly-size circuit with an exponentially long path ===
 m   naive path-following steps   sink found   closed-form sink   agree?
  4                          15            3                  3   True
  8                         255           51                 51   True
 12                       4,095          819                819   True
 16                      65,535       13,107             13,107   True
 20                   1,048,575      209,715            209,715   True
 22                   4,194,303    3,355,443          3,355,443   True
 24                  16,777,215    3,355,443          3,355,443   True

(Original computation for this note; Python 3 standard library only, no external solver. Step counts match 2^m − 1 exactly at every m, confirming the full-period claim rather than assuming it. The apparent coincidence at m = 22 and m = 24 is real and checkable by hand: 5 × 3{,}355{,}443 = 16{,}777{,}215 = 2^24 − 1 ≡ −1 modulo both 2^22 and 2^24, so −5^{-1} has the same residue in both rings.)

The last two columns are the point. The closed-form sink is (−5^{-1}) mod 2^m, computed in O(m) bit operations by the extended Euclidean algorithm. For this instance, the exponentially long path can be telescoped instantly — because the successor circuit has algebraic structure that a solver can exploit. That is precisely what a polynomial-time PPAD algorithm would have to do for every instance, including instances where S is an arbitrary Boolean circuit with no structure whatsoever to exploit. Papadimitriou’s chessplayer, in other words, has a shortcut only if he can invert the entire history of chess.

This also explains why the black-box lower bounds are not the end of the story. Hirsch, Papadimitriou and Vavasis proved that any algorithm treating the Brouwer function as an oracle needs Ω((1/ε)^{d})-type time; but a PPAD algorithm is handed the circuit, not an oracle, so it may “delve into the detailed properties of the function” (AGT book, ch. 2 §2.4.1). The oracle bound rules out the naive approach; PPAD-completeness is the evidence that the non-naive approach does not exist either.

Sperner’s Lemma and Brouwer: The Geometric Root

PPAD’s game-theoretic content comes entirely from a chain of reductions that bottoms out in a colouring lemma about triangles.

Sperner’s lemma (2-D). Triangulate a triangle whose corners are labelled 0, 1, 2. Colour every vertex of the triangulation with a colour in {0,1,2}, subject to one rule: a vertex lying on the face opposite corner t may not receive colour t (corners get their own colour; boundary vertices get one of the two colours of their edge’s endpoints; interior vertices are free). Such a colouring is admissible. Then there is an odd number — hence at least one — of trichromatic small triangles, whose three corners carry all three colours.

Papadimitriou’s proof of membership (his Theorem 3, k-D SPERNER ∈ PPAD for all k ≥ 2) is the reason the lemma sits in this class at all, and it is a direct construction of the END-OF-THE-LINE graph:

“In the two-dimensional case the nodes are the triangles […] and there is an arc from one triangle to the other if they have colors 0 and 1, and they share a 0-1 edge. The arc is directed away from the simplex in which the colors on the common arc in the clockwise direction are 0-1. The standard leaf corresponds to the outermost 0-1 triangle. All other leaves are adjacent to trichromatic triangles.”

flowchart TB
    subgraph proof["Sperner's proof IS a path-following algorithm"]
        direction TB
        START["Outermost 0–1 edge on the boundary<br/>(made unique by an added external edge)<br/>= STANDARD SOURCE"]
        MID["Enter a triangle through a 0–1 edge.<br/>It has colours 0 and 1, so it has a<br/>SECOND 0–1 edge — unless it is trichromatic"]
        RULE["Orientation rule: traverse the 0–1 edge<br/>leaving colour 0 on the right.<br/>This makes in-degree = out-degree = 1"]
        END["Cannot exit the boundary (only one external 0–1 edge)<br/>Cannot revisit (a triangle has at most two 0–1 edges)<br/>⟹ path must stop at a TRICHROMATIC triangle"]
        START --> MID --> RULE --> END
    end
    END -.->|"the stopping point is<br/>the PPAD witness"| WIT["Panchromatic simplex<br/>≈ approximate Brouwer fixed point<br/>≈ approximate Nash equilibrium"]

What it shows: why Sperner’s lemma is not merely true but directed, and how its constructive proof is literally a walk along an END-OF-THE-LINE path. The insight: Papadimitriou singles out this orientability as “a subtle difference from the application of the pure even-leaf argument”: in Smith’s theorem (second Hamilton cycle in an odd-degree graph, the flagship PPA problem) you can stand in the middle of a path and have no clue which of the two directions is right; in Sperner you always do. That is the whole difference between PPA and PPAD, and it is why “problems in PPA that have a topological-geometric flavor seem to crowd into PPAD, whereas those of a more generic combinatorial or algebraic nature do not.”

Verifying the parity claim computationally

Sperner’s lemma is usually quoted as “at least one.” The stronger odd form is what makes the parity argument work, so it is worth checking rather than trusting. Using the standard triangulation of the unit triangle at lattice points (i,j,k) with i+j+k = n — which has (n+1)(n+2)/2 vertices and exactly n² small triangles (n(n+1)/2 upward plus n(n−1)/2 downward) — I generated admissible colourings and counted panchromatic triangles.

nverticessmall trianglestrialspanchromatic count (min…max)every count odd?
2643001…1yes
31093001…5yes
415163001…7yes
628363001…19yes
845643003…25yes
129114430017…49yes
2023140030061…111yes
408611600300303…407yes

And exhaustively, over every admissible colouring for small n:

nverticestrianglesadmissible colouringswith an odd panchromatic count
13111 (all)
26488 (all)
3109192192 (all)

(Original computation for this note. The triangle count matching n² exactly at every row is an independent check that the triangulation was enumerated correctly — a wrong upward/downward split would have shown up immediately as a mismatch.)

Note what the min column does as n grows: at n = 40 a random admissible colouring contains hundreds of trichromatic triangles. Solutions are not rare — they are everywhere. Hardness in PPAD has nothing to do with witnesses being scarce; it is about not knowing where they are without walking.

Brouwer. From Sperner to Brouwer is a limiting argument. Colour each vertex x of a fine triangulation by the direction of the displacement f(x) − x — in two dimensions, by which of three 120°-ish angular sectors it falls into (DGP §3.1, Figure 6). The boundary conditions make the colouring admissible. Sperner then yields a trichromatic triangle: three nearby points being pushed in three mutually conflicting directions. Under a Lipschitz condition d(F(x₁), F(x₂)) ≤ K·d(x₁,x₂), a function cannot fluctuate fast enough for that to happen except near an approximate fixed point. Take finer and finer subdivisions, use compactness to extract a convergent subsequence, use continuity in the limit: f(x*) = x*.

The Lipschitz constant is not decoration. DGP are explicit: it “ensures that approximate fixed points can be localized by examining the value F(x) when x ranges over a discretized grid,” and “in the absence of a Lipschitz constant K, there would be no such guarantee and the problem of computing fixed points would become intractable.” A BROUWER instance is therefore the triple (circuit Π_F, Lipschitz constant K, accuracy ε), and the output is any x with d(F(x), x) ≤ ε.

Nash. Nash’s own 1950 proof already reduces NASH to BROUWER: build a continuous “regularized best response” map on the product of the players’ simplices whose fixed points are exactly the equilibria. Roughgarden gives the clean version — fᵢ(x) = argmax_{xᵢ'} [ E_{s∼(xᵢ', x₋ᵢ)}[πᵢ(s)] − ‖xᵢ' − xᵢ‖₂² ], where the first term rewards best-responding (linear in xᵢ') and the second penalizes moving far (strictly convex), so the argmax is unique and f is well defined and continuous (Lecture 20 §7). Every equilibrium is a fixed point; conversely, if x is not an equilibrium then some player can gain by shifting ε of probability mass, so x is not fixed.

There is a second, independent route into PPAD for two-player games, and the two are incomparable. The Lemke-Howson Algorithm follows a path of vertices on a pair of polytopes; its convergence proof is a parity argument, not an objective-function argument. The AGT chapter spells out the correspondence node by node: the vertices of the implicit graph are the vertices of the polytope “where all strategies, with the possible exception of strategy n, are represented”; each has in-degree and out-degree at most one; the all-zero vertex is the standard source; and the adjacent vertices are found by a simplex pivot (AGT ch. 2 §2.4). The two routes differ in what they buy you:

Route into PPADNumber of playersExact or approximateSource
Sperner → Brouwer → Nash’s fixed-point mapany finite kapproximate equilibrium onlyNash 1950 / DGP
Lemke–Howson pivoting on the best-response polytopes2 onlyexact equilibriumLemke & Howson 1964

With three or more players an exact equilibrium can be irrational (Nash’s own observation), so “compute the exact equilibrium” is not even an FNP problem in the usual encoding; Etessami and Yannakakis built the class FIXP to handle that regime, and computing exact k-player equilibria for k ≥ 3 “appears to be strictly harder than PPAD problems” (Roughgarden L20, citing Etessami & Yannakakis, SICOMP 39(6):2531–2597). For two players the equilibrium is always rational with polynomially bounded numerators and denominators, which is exactly why the two-player case is the clean computational question.

Uncertain

Verify: the precise definition of FIXP and the claim that exact 3-player NASH is FIXP-complete. Reason: Etessami & Yannakakis (SICOMP 2010) was not retrieved — homepages.inf.ed.ac.uk/kousha/j43.pdf returned HTTP 404 during this task, and the claim here rests on Roughgarden’s one-line citation plus the DGP survey’s mention. To resolve: locate the SICOMP paper or the FOCS 2007 extended abstract on an author mirror and check whether the completeness is for exact NASH with k ≥ 3 specifically, and what the FIXP reductions are (they are not the usual polynomial-time many-one reductions).

From END OF THE LINE to Two-Player Nash

The headline result took two papers and about nine months.

timeline
    title Nash equilibrium becomes PPAD-complete
    1928-1950 : von Neumann minimax (zero-sum, LP-solvable)
              : Nash 1950 — every finite game has a mixed equilibrium
    1964-1965 : Lemke-Howson pivoting algorithm — exponential worst case
    1991 : Megiddo & Papadimitriou — TFNP; no total problem is FNP-complete unless NP = coNP
    1994 : Papadimitriou, JCSS 48(3), pp. 498-532 — PPA, PPAD, PPP defined; 3D SPERNER, BROUWER, KAKUTANI, BORSUK-ULAM proved PPAD-complete; NASH and P-LCP placed in PPAD
    2005 : Daskalakis, Goldberg & Papadimitriou — 4-player NASH is PPAD-complete (ECCC / STOC 2006)
    2005 : Chen & Deng (TR05-134) and Daskalakis & Papadimitriou (TR05-139), independently — 3-player NASH
    2005-2006 : Chen & Deng (ECCC TR05-140, FOCS 2006) — 2-player NASH is PPAD-complete
    2006 : Chen, Deng & Teng (FOCS) — no FPTAS unless PPAD ⊆ P; smoothed complexity of Lemke-Howson not polynomial unless PPAD ⊆ RP
    2016 : Rubinstein — constant-ε two-player Nash needs n^(log^(1-o(1)) n) time under ETH for PPAD
    2021-2023 : Fearnley, Goldberg, Hollender & Savani — CLS = PPAD ∩ PLS; gradient descent to a KKT point is complete for it

What it shows: the sixty-year gap between “an equilibrium exists” and “finding one is complete for a class built for the purpose,” and how fast the last mile went once the class was right. The insight: the 1991 and 1994 papers are the enabling work — the 2006 results are reductions into a target that had to be invented first. Note also that the 1994 paper already contained the answer for SPERNER and BROUWER; only NASH was left, and it was left for twelve years.

The reduction, in outline

DGP’s construction goes END OF THE LINE → BROUWER → graphical game → 3-player game, and every step has a distinct trick.

Embedding a path in a cube. The 2^n nodes of the END-OF-THE-LINE graph get two “special sites” each in the unit 3-cube, at locations computable from the node’s name. Grid points get one of four colours {0,1,2,3} representing four displacement vectors chosen to point away from one another, so that F(x) − x ≈ 0 is only possible where all four colours meet. An edge u → v of the graph is drawn as a tube of coloured grid points joining u’s site to v’s. All four colours become adjacent only at the ends of tubes — i.e. exactly at the unbalanced nodes. Three dimensions rather than two is not aesthetic: it is what lets tubes cross without touching, which is the technical obstruction Papadimitriou flagged as open problem (3) in 1994 (“Is 2D-SPERNER PPAD-complete? At present we see no way of defeating the problem created by crossings of the tubes”). This yields BROUWER is PPAD-complete.

Games that do arithmetic. The second half turns a circuit into a game. Give each player two actions, stop and go; identify the player with the probability X ∈ [0,1] they assign to go. A multiplication gadget on players x, y, z plus a mediator w: pay w the amount X·Y for playing stop and Z for playing go, and pay z to play the opposite of w. In any Nash equilibrium Z = X·Y. The argument is a two-line case analysis, reproduced verbatim from DGP §4.2: “if Z > X·Y, then w would prefer strategy go, and therefore z would prefer stop, which would make Z = 0, and would violate the assumption Z > X·Y.” Analogous gadgets give Z = X + Y and Z = ½X.

The brittle comparator. Comparison is where it gets interesting, and the obstruction is not an engineering failure but a theorem. A comparator gadget that outputs a clean binary signal on equal inputs cannot exist — “if a non-brittle comparator gadget existed, then we could construct a game that has no Nash equilibria, contradicting Nash’s theorem.” So the gadget outputs anything when its inputs are equal, and the construction repairs this by evaluating the Brouwer function at a grid of nearby points and averaging, which makes the computation robust at the cost of a small error. This is the deep reason the hardness is stated for ε-approximate equilibria: brittleness is forced by Nash’s theorem itself.

Many players down to three. The resulting object is a graphical game (Kearns–Littman–Singh): players sit on a graph and each player’s utility depends only on neighbours, so the game has a description polynomial in the number of players rather than n·s^n. Three-colour the graph so no two players who interact — or who both interact with a third — share a colour, then hire three “lawyers,” one per colour, each representing all players of that colour. A lawyer representing m clients has 2^m actions and encodes their joint stop/go profile. To stop a lawyer from over-allocating probability to lucrative clients, the three lawyers additionally play a high-stakes generalized rock–paper–scissors on the side, which forces balanced allocation. That gives three players.

And then two. Chen and Deng’s contribution was to notice something DGP had not: “the graphical games resulting from our construction are not using the multiplication operation (except for multiplication by a constant), and therefore can even be simulated by a two-player game” (DGP §5). Their own paper puts it as getting “rid of the graphical game model” entirely and giving “a direct reduction from 3-Dimensional Brouwer to 2-Nash” with new arithmetic and logic gadgets (Chen & Deng, ECCC TR05-140 §1). DGP call the result “unexpected, one reason being that the probabilities that arise in a 2-player Nash equilibrium are always rational numbers, which is not the case for games with three or more players” — the two-player case looked structurally easier, and that intuition was wrong. The journal version is Chen, Deng & Teng, JACM 56(3), 2009, whose abstract states plainly: “We settle a long-standing open question in algorithmic game theory. We prove that Bimatrix […] is complete for the complexity class PPAD” (arXiv:0704.1678).

The Approximation Picture

If exact equilibria are hard, the natural retreat is approximation. An ε-approximate Nash equilibrium is a profile where no player can gain more than ε by deviating (payoffs normalized to [0,1]); the stronger well-supported variant, which is what the hardness results actually use, demands that no strategy played with positive probability is more than ε worse than a best response (DGP Figure 4, eq. (3)). The regimes separate sharply by how ε scales with the game size n.

Regime for εStatusSource
ε exponentially small in nPPAD-completeDGP (STOC 2006 / SICOMP 39(1):195–259, 2009)
ε = 1/n^Θ(1) (inverse polynomial)PPAD-complete ⟹ no FPTAS unless PPAD ⊆ PChen, Deng & Teng, arXiv:cs/0602043
ε an arbitrary constantsolvable in n^{O((log n)/ε²)} (QPTAS)Lipton, Markakis & Mehta 2003, via Barbados Thm 1.15 / Cor 1.17
ε ≈ 1/3polynomial-timeTsaknakis & Spirakis 2008
ε a sufficiently small constantno n^{log^{1−δ} n} algorithm under ETH for PPAD — the QPTAS is essentially optimalRubinstein 2016, Thm 1.2

The Lipton–Markakis–Mehta result is the one worth understanding, because it explains why constant-ε hardness had to be quasi-polynomial rather than exponential. Theorem (LMM). For every ε > 0 and every n × n bimatrix game there exists an ε-approximate equilibrium in which each player randomizes uniformly over a multi-set of O((log n)/ε²) pure strategies. The proof is a sampling argument: take an exact equilibrium (x*, y*), draw Θ((log n)/ε²) pure strategies i.i.d. from each, and let (x̂, ŷ) be the empirical distributions. Chernoff bounds say every row’s expected payoff against ŷ is within ε/2 of its payoff against y*, so every strategy in x̂’s support is within ε of a best response (Barbados §1.4.1).

Two consequences follow immediately. First, brute-force enumeration over all such sparse multi-sets gives the n^{O((log n)/ε²)} algorithm. Second — and this is the constraint that shaped a decade of research — the search space is only quasi-polynomially large, so quasi-polynomial hardness is the strongest result anyone could hope to prove. Roughgarden’s framing: “the algorithm reveals no structure of the problem other than the fact that the natural search space for it has quasi-polynomial size. It is easy to imagine that there are no ‘shortcuts’ to searching this space.”

Rubinstein’s 2016 breakthrough supplied the matching lower bound, and the assumption it needs is worth naming precisely. ETH for PPAD: solving EndOfALine requires time 2^{Ω̃(n)}, where n is the size of the circuits. Under it, ε-approximate two-player Nash for sufficiently small constant ε needs n^{log^{1−o(1)} n} time. The reduction has to blow an n-bit EndOfALine instance up into a 2^{√n} × 2^{√n} game — the √n coming from a birthday-paradox argument, and the exponentiation from PCP machinery plus “Althöfer games” that force players to randomize near-uniformly over √n-sized subsets. Rubinstein notes this is “the first time that such ideas are used for a reduction between problems inside PPAD,” which is the methodological news: probabilistically checkable proofs, invented for NP, made to work inside a total class.

How much should one believe ETH for PPAD? Roughgarden is careful, and so should the reader be: “The answer is far from clear, although there are exponential query lower bounds for PPAD problems and no known techniques that show promise for a subexponential-time algorithm for the succinct EoL problem” (Barbados, footnote 2 to Thm 5.1). It is a strictly stronger assumption than PPAD ⊄ P, which is itself strictly stronger than P ≠ NP in the sense that P = NP would collapse PPAD too.

What Is Not Hard — And This Is the Practical Payoff

Everything above concerns general-sum Nash equilibria in normal-form games. Shift any one of those three qualifiers and the picture can flip completely. This is the section to remember when someone tells you “game theory is intractable.”

flowchart LR
    subgraph POLY["Polynomial time — linear programming"]
        ZS["Zero-sum 2-player<br/>MINIMAX<br/>von Neumann → LP duality"]
        CE["CORRELATED EQUILIBRIUM<br/>a linear system in the joint distribution"]
        CCE["COARSE CORRELATED EQ.<br/>weaker constraints, also an LP<br/>reached by no-regret dynamics"]
    end
    subgraph HARD["PPAD-complete"]
        GS["General-sum 2-player NASH<br/>Chen &amp; Deng 2006"]
        KP["k-player ε-NASH<br/>DGP 2006"]
    end
    subgraph OTHER["Other classes"]
        PLSX["Pure equilibria of congestion games<br/>PLS-complete"]
        FIXPX["EXACT k-player NASH, k ≥ 3<br/>irrational solutions — FIXP"]
    end
    ZS -->|"drop 'zero-sum'"| GS
    CE -->|"insist on independent randomization"| GS
    GS -->|"insist on pure strategies<br/>+ congestion structure"| PLSX
    GS -->|"insist on exactness with k ≥ 3"| FIXPX

What it shows: the tractability frontier, with the exact modelling decision that crosses it labelled on each arrow. The insight: the hardness is not in “equilibrium,” it is in the conjunction of general-sum payoffs and independent randomization. Relax either and you are back in linear programming.

Zero-sum is polynomial. The minimax theorem is equivalent to strong LP duality; the two players’ problems are literally dual linear programs, and their common optimal value is the game value (Barbados §1, Theorem 1.1 and the surrounding discussion). Chen and Deng put it first in their list of reasons two-player Nash looked tractable: “the zero-sum version can be solved in polynomial time by linear programming” via Khachiyan’s ellipsoid algorithm. Roughgarden adds a further structural gift: in a zero-sum game the min-max pairs are the optimal solutions of those two LPs, so the set of equilibria is convex — you can interchange equilibria between players freely, and there is a well-defined value. Neither property survives in general-sum games, and their loss is arguably the real source of the difficulty. See Zero-Sum Games and the Minimax Theorem.

Correlated equilibrium is polynomial. A correlated equilibrium is a joint distribution ρ over strategy profiles such that a player told to play j by the mediator has no incentive to deviate, conditional on that recommendation. Write one variable x_s per outcome s; the conditions are then a linear system:

Σ_{s : sᵢ = j} uᵢ(s)·x_s  ≥  Σ_{s : sᵢ = j} uᵢ(sᵢ', s₋ᵢ)·x_s     for every player i and every j, sᵢ' ∈ Sᵢ
Σ_s x_s = 1,      x_s ≥ 0

(Barbados §5.4.1, eq. (5.6)). The coarse variant drops the conditioning and is an even smaller system, eq. (5.3). Both are solvable by LP in time polynomial in the normal form size. The contrast with Nash could not be sharper, and the reason is structural rather than accidental: correlated equilibria form a convex polytope (indeed one containing every Nash equilibrium as a vertex-adjacent point of the product-distribution slice), while Nash equilibria are the fixed points of a nonlinear map and form a non-convex set. Convexity is what LP eats. See Correlated Equilibrium.

There is a second, more remarkable route to correlated equilibria that has nothing to do with LP: no-regret dynamics. If every player runs an external-regret-minimizing algorithm, the time-averaged play converges to the set of coarse correlated equilibria; with swap regret, to correlated equilibria (Roughgarden Lectures 17 and 18). That gives a decentralized, plausible-as-behaviour path to equilibrium — the exact thing PPAD-hardness rules out for Nash. Roughgarden’s critique of the LP route makes the point: “Algorithms for linear programming do not resemble how players typically make decisions.” No-regret dynamics do. See Regret and No-Regret Learning and Multiplicative Weights Update.

Worked computation: the size of what you are searching

The gap between the LP route and the enumeration route is not asymptotic hand-waving; it is arithmetic. Support Enumeration must, in the worst case, consider every pair of non-empty supports. For an n × n bimatrix game that is (2^n − 1)² pairs, against a zero-sum LP with n + 1 variables and n + 1 constraints:

nnon-empty supports per playersupport pairs to examinezero-sum LP size
5319616 vars, 6 constraints
101,0231,046,52911 vars, 11 constraints
1532,7671,073,676,28916 vars, 16 constraints
201,048,5751,099,509,530,62521 vars, 21 constraints
2533,554,4311,125,899,839,733,76126 vars, 26 constraints
301,073,741,8231,152,921,502,459,363,32931 vars, 31 constraints

(Original computation for this note.) At n = 30 — a game you could print on one page — support enumeration faces roughly 1.15 × 10^18 support pairs, while the zero-sum LP has thirty-one variables. That factor is the practical meaning of “the hardness is specific to general-sum Nash.”

To be scrupulous: support enumeration’s cost is a property of that algorithm, not a lower bound on the problem. But Lemke–Howson, the algorithm that avoids enumeration by pivoting, is also exponential in the worst case — Savani and von Stengel (2004) constructed bimatrix games whose Lemke–Howson paths are exponentially long, cited in AGT ch. 2 §2.4 — and Chen, Deng and Teng closed the escape hatch of “well, hard instances are rare”: the smoothed complexity of Lemke–Howson, or of any algorithm for bimatrix Nash, is not polynomial in n and 1/σ under perturbations of magnitude σ, unless PPAD ⊆ RP (arXiv:cs/0602043).

The Neighbourhood: PPA, PPP, PLS, PPADS, CLS

PPAD has siblings, and knowing them prevents the most common misattribution (“this problem is PPAD-hard” when it is actually PLS-hard). Each class is named by its lemma (Goldberg & Papadimitriou 2017 §1):

ClassThe lemma it encodesCanonical complete problemGame-theoretic inhabitant
PLS“every DAG has a sink”local max-cut, FLIPpure equilibria of congestion games (Roughgarden L19)
PPA“a finite graph with an odd-degree node has another”LEAFSMITH (second Hamilton cycle); necklace splitting; Borsuk–Ulam in PPAD
PPAD“a directed graph with an unbalanced node has another”END OF THE LINENASH, BROUWER, SPERNER, KAKUTANI, ARROW-DEBREU market equilibrium, P-LCP
PPADS“a second oppositely unbalanced node must exist”—contains PPAD
PPP“f : {0,1}^n → {0,1}^n has a preimage of 0^n or a collision”PIGEONHOLE CIRCUITEQUAL SUMS; collision-resistant hashing
CLScontinuous local search; = PPAD ∩ PLSKKT point of a C¹ function on [0,1]²contraction fixed points, simple stochastic games, network coordination games

Three facts from this table earn their place.

PPAD ⊆ PPP (Papadimitriou 1994, Proposition 4, credited to Vavasis and Yannakakis): define π_G(x) to be x itself if x is a sink, G²(x) if x is a non-standard source, and G(x) otherwise; any collision of π reveals a non-standard source or a sink. Combined with PPAD ⊆ PPA, this places PPAD at the bottom of the visible part of the lattice.

PPP = FP would destroy one-way permutations (Papadimitriou 1994, Proposition 3). Given an alleged one-way permutation π, build the circuit C(y) = π(y) ⊕ x; since π is a permutation, C has no collisions, so a PIGEONHOLE CIRCUIT solver must return a y with C(y) = 0^n, i.e. π(y) = x. This is the earliest link between TFNP and cryptography, and the modern versions run the other way: under indistinguishability obfuscation, PPAD (and hence NASH) is intractable (Goldberg & Papadimitriou §2).

CLS = PPAD ∩ PLS. Daskalakis and Papadimitriou defined CLS in 2011 as a “natural” counterpart to the intersection, and the 2017 survey reported it as “lying within (and probably well within)” PPAD ∩ PLS with no non-generic complete problems known. That expectation was wrong: Fearnley, Goldberg, Hollender and Savani proved CLS = PPAD ∩ PLS exactly, by showing that computing a Karush–Kuhn–Tucker (KKT) point of a continuously differentiable function over [0,1]² is PPAD ∩ PLS-complete — “the first non-artificial problem to be shown complete for this class” (arXiv:2011.01929, abstract). Their framing is the one worth carrying away: the complexity of gradient descent on a bounded convex polytopal domain is exactly PPAD ∩ PLS. A note on equilibrium computation and a note on optimization turn out to be about the same object.

Failure Modes and Gotchas

“PPAD-complete means it’s as hard as NP-complete.” No. PPAD-completeness is strictly weaker evidence. P = NP would immediately give PPAD = P (PPAD is essentially a subset of NP, since a witness is efficiently checkable), so PPAD-hardness cannot be stronger than NP-hardness. The AGT chapter is blunt: “it could very well be that PPAD = P = NP.” The argument for taking it seriously is empirical and structural, not deductive — decades of failure on BROUWER, relativized worlds where PPAD ≠ P (Beame et al. 1998), and the observation that a PPAD algorithm would have to defeat both the oracle separations and the Hirsch–Papadimitriou–Vavasis black-box lower bound.

Confusing PPAD with PLS. They are incomparable siblings, not nested. If your problem’s existence proof is “keep improving an objective until you can’t” — local search, potential functions, better-response dynamics in congestion games — it is a PLS problem and PPAD-hardness is the wrong hammer. Roughgarden’s pictures are diagnostic: a PLS instance is a DAG with an objective function on the nodes; a PPAD instance is a graph of in- and out-degree ≤ 1 with no objective function and possibly with cycles (Lecture 20, Figures 2 and 3). The absence of an objective function in PPAD is the substantive difference: it is what makes the second algorithm in the definition (the predecessor circuit) necessary at all, since without it there is nothing to “keep the third algorithm honest.”

Assuming exact and approximate hardness are the same statement. They are not, and the ε regime matters enormously (see the table above). Sloppy citation of “computing a Nash equilibrium is PPAD-complete” hides which of five different theorems is meant. When it matters — and for anything approximation-related it always matters — state the ε regime.

Assuming exact equilibria are always well defined. For two players they are rational and polynomially representable. For three or more players, Nash’s own 1950 paper already noted that all equilibria may be irrational, so “output the exact equilibrium” is not a well-posed FNP problem in binary encoding. This is why the DGP results are stated for ε-approximate equilibria and why FIXP exists.

Mistaking abundance for tractability. The Sperner computation above found hundreds of trichromatic triangles in a random colouring at n = 40. Solutions to PPAD problems are typically plentiful. The difficulty is navigational, not statistical. Corollaries: random sampling is not a strategy, and “I found a solution quickly on my instances” says nothing about worst case.

Reading SECOND TRICHROMATIC TRIANGLE’s NP-completeness as contradicting Sperner’s PPAD membership. They are different problems: one is total (find a trichromatic triangle), one is not (decide whether a second exists given one). Megiddo and Papadimitriou proved the latter NP-complete precisely to illustrate the boundary.

Treating the Lipschitz constant as boilerplate. Drop K from a BROUWER instance and approximate fixed points stop being localizable on a grid; the problem leaves the regime the class was built for. Similarly, SPERNER and BROUWER instances are specified with syntactic proofs that the input satisfies its restrictions — Papadimitriou is explicit that this is to avoid smuggling in promise problems, since “TFNP trivially contains a host of uninteresting promise problems.” A hardness result about a promise problem is a weaker statement than it looks.

Alternatives and When to Choose Them

If you actually need to compute something about a game and Nash is out of reach, these are the moves, in rough order of how much they cost you in modelling fidelity.

If you can…UseComplexityTrade-off
Make the game zero-sum (or it already is)LP / minimax; Zero-Sum Games and the Minimax TheorempolynomialRequires strictly opposed interests. Buys convexity, a unique value, and interchangeable equilibria.
Accept a mediator / shared signalCorrelated equilibrium LP; Correlated Equilibriumpolynomial in normal-form sizeRequires a correlating device; the solution concept is weaker (larger set), which is often an advantage — it can beat every Nash equilibrium in welfare.
Accept decentralized learning rather than a solved pointNo-regret dynamics; Regret and No-Regret Learning, Multiplicative Weights Updateconverges to (coarse) correlated equilibrium in polynomially many roundsYou get time-averaged, approximate, correlated behaviour — not a Nash equilibrium, and not the current strategy.
Accept a constant approximationLMM sparse-support enumerationn^{O((log n)/ε²)}Quasi-polynomial and, by Rubinstein, essentially optimal under ETH for PPAD. Tsaknakis–Spirakis gets ε ≈ 1/3 in polynomial time, which is a very weak guarantee.
Restrict to small gamesSupport Enumeration with exact rational arithmetic(2^m − 1)(2^n − 1) support pairsExact and trivially correct; dies past n ≈ 12–15 per the table above. Use fractions.Fraction, not floats: on a small game you cannot otherwise distinguish a bug from rounding.
Restrict to two players and want an exact answerThe Lemke-Howson Algorithmexponential worst case (Savani & von Stengel 2004); not smoothed-polynomial (CDT 2006)Fast in practice on most instances, produces exact rational equilibria, and its parity-argument convergence proof is what puts 2-player NASH in PPAD in the first place.
Restrict to extensive-form two-player zero-sum gamesThe Sequence FormLP linear in the size of the game treeSidesteps the exponential reduced normal form entirely; the reason Kuhn poker and larger games are solvable at all.
Restrict to a structured classcongestion / potential games (The Price of Anarchy), anonymous games, tree-like graphical gamesPLS-complete for pure equilibria; PTAS for anonymous gamesStructure is the only reliable route to tractability; the price is that your model must genuinely have it.
Accept a different questionPrice of anarchy / stability boundsoften provable without computing any equilibriumYou get a bound on how bad equilibrium can be rather than the equilibrium. Frequently this is what you actually wanted.

The meta-point, which Games and Strategic Systems in C MOC states as its central theme: Gale–Shapley proved stable matchings exist by exhibiting an O(n²) algorithm, and matching deployed — see The Gale-Shapley Algorithm and Hospital-Residents and the NRMP. Nash proved equilibria exist by a fixed-point theorem, and general-sum equilibrium computation did not deploy. The difference is not the quality of the mathematics; it is whether the existence proof was constructive in a computationally meaningful sense. PPAD is the formal name for the gap between the two kinds of proof.

Production Notes

Nobody ships a general-sum Nash solver at scale, and this is why. The practical systems in this area all take one of the escape routes above. Superhuman poker (Libratus, DeepStack, Pluribus) works because heads-up poker is two-player zero-sum, where Counterfactual Regret Minimization converges to equilibrium with no PPAD obstruction; Pluribus’s six-player results come with explicitly weaker theoretical guarantees for exactly this reason. Ad auctions (Ad Auctions and GSP) avoid equilibrium computation altogether by designing a mechanism and letting bidders find their own way. Market-equilibrium computation in production settings uses convex-program formulations (Eisenberg–Gale and relatives) that are polynomial for restricted utility classes — while the general Arrow–Debreu problem is exactly one of the PPAD-complete problems in Papadimitriou’s original list.

Reference solvers exist and are worth reading, not reimplementing blindly. Gambit implements support enumeration, Lemke–Howson, and simplicial-subdivision fixed-point methods; nashpy is a smaller Python library covering the first two. Neither is installed on this machine (verified during the MOC build, 2026-08-28: no pip, no numpy, no gambit CLI), which is why every number in this note came from stdlib Python with exact integer arithmetic. That constraint turns out to be pedagogically useful: fractions.Fraction gives exact answers on small games, and the counting arguments above need nothing more than int.

The intellectual consequence is the one the authors themselves emphasize. DGP’s conclusion: the result “raises concerns about the credibility of the mixed Nash equilibrium as a general-purpose framework for behavior prediction.” Roughgarden’s version: “If no polynomial-time algorithm can compute a MNE of a game, then we don’t expect a bunch of strategic players to find one quickly, either. More generally, in classes of games of interest, polynomial-time tractability of computing an equilibrium can be used as a necessary condition for its predictive plausibility.” That last sentence is the practical takeaway for anyone modelling a system: computational tractability of your solution concept is not a nice-to-have; it is a sanity check on whether the concept predicts anything at all. He also adds the honest caveat — intractability “is not necessarily first on the list of the Nash equilibrium’s drawbacks. For example, its non-uniqueness already limits its predictive power in many settings.”

What is still open, as of this writing (2026-08). Whether PPA = PPAD; whether PPAD = FP; whether 2D-SPERNER is PPAD-complete (Papadimitriou’s 1994 open problem (3) — resolved affirmatively by Chen & Deng for the 2-D discrete fixed-point problem, but the reader should verify the exact form of that resolution before relying on it); whether an average-case hardness result holds for PPAD (Roughgarden’s open problem after Theorem 4.5); and the plausibility of ETH for PPAD itself.

Uncertain

Verify: that Chen & Deng resolved Papadimitriou’s open problem (3) by proving the 2-D discrete fixed-point problem PPAD-complete, and whether that is the same statement as “2D-SPERNER is PPAD-complete.” Reason: this claim is from background knowledge and was not confirmed against a fetched primary source during this task — the FOCS 2006 paper “On the complexity of 2D discrete fixed point problem” was not retrieved. To resolve: fetch that paper (or its ECCC/arXiv version) and check whether the completeness is for the Sperner formulation, the discrete Brouwer formulation, or both.

Uncertain

Verify: the Savani & von Stengel (2004) construction of bimatrix games with exponentially long Lemke–Howson paths, including whether the bound is 2^{Ω(n)} and for which game family (their construction uses cyclic polytopes). Reason: cited second-hand from the AGT book chapter, which was fetched; the original FOCS 2004 / Econometrica 2006 paper was not retrieved during this task. To resolve: fetch von Stengel’s LSE page, which hosts his papers.

See Also

Graph View

Backlinks