Game complexity
2019-06-07 — 2026-04-29
Wherein the Nash Equilibrium, Whose Existence Is Guaranteed by Fixed-Point Arguments, Is Established as PPAD-complete, While Correlated Equilibrium Is Seen to Admit a Linear-Programming Solution.
The complexity of finding game theory solutions, as seen in cooperation, mechanism design, adversarial training, and so on.
A question from classical game theory: are the equilibria the classical theory promises us actually computable?
Finding a Nash equilibrium of a general two-player game is impractically computationally expensive, in a sense that I make precise in a moment. We might care about this because even though such equilibria might exist, bounded agents might have difficulties finding them, even in moderately size games, even though Nash’s theorem guarantees such equilibria exist. This is the stylised fact behind a lot of bounded-rationality and learning-based approaches to playing games and game-theory adjacent fields.
The computational complexity of markets is also punishing for related reasons.
Anyway, let us take a brief tour of the kind of hardness we see.
1 Nash equilibrium
The basic problem: given payoff matrices \(A, B\) for a two-player game, find mixed strategies \(\sigma, \tau\) such that neither player can profitably deviate. Nash 1950 says they exist; the computational problem is to find them.
Tractable special cases:
- Zero-sum games (\(B = -A\)): Can be solved by linear programming by von Neumann’s minimax theorem. Consequently this is the case where most early algorithmic work happened.
- Known support: if the support of the equilibrium is given, the rest reduces to linear programming.
- Various structured cases — graphical games with bounded treewidth, certain symmetric games — admit polynomial algorithms.
But the general case is PPAD-complete (Daskalakis, Goldberg, and Papadimitriou 2009; Chen and Deng 2006). PPAD — Polynomial Parity Argument on Directed graphs — is a complexity class of search problems guaranteed to have a solution by parity or fixed-point arguments. A classic is the example of Brouwer’s fixed-point theorem: any continuous map from a compact convex set to itself has a fixed point, but finding one is in PPAD.
PPAD is a subset of TFNP, the class of search problems whose solutions are “total”, i.e. they always exist, given the inputs. This is distinct from SAT’s (NP-complete) hardness; there the question is whether any solution exists at all. In particular, we know that no PPAD-complete problem can be NP-hard unless NP = coNP.
2 Concisely represented games
The PPAD-completeness result above is stated for games given by their explicit payoff matrices, which is exponentially large in the number of players. Many practical games are concisely represented — graphical games, action-graph games, congestion games — where the description size is polynomial in the number of agents. The complexity story can change for such games, but not necessarily for the better (Schoenebeck and Vadhan 2009); insofar as a concise encoding shrinks the input but does not necessarily give us any extra exploitable structure, so “polynomial in the inputs” can be much more demanding than it appears.
3 Approximate Nash
As always with brutal computational complexity results it is worth checking if settling for approximate solutions helps us. If we settle for an \(\epsilon\)-equilibrium — no player gains more than \(\epsilon\) by deviating, instead of literally zero gain — this does help. Lipton, Markakis, and Mehta (2003) devised an \(n^{O(\log n / \epsilon^2)}\) time algorithm for fixed \(\epsilon\). That running time is quasi-polynomial: slower than any polynomial \(n^c\), but far faster than the exponential \(2^n\) blow-up. The form misleads, because base and exponent both grow; for fixed \(\epsilon\) it rewrites as \(2^{O(\log^2 n)}\), and the comparison is then between \(\log^2 n\) and \(n\) up in the exponent, which is no contest. Taking the exponent as a bare \(\log_2 n\) to see the shape, at \(n=1000\) that is around \(10^{30}\) operations against \(10^{301}\) for \(2^n\). The trick was to search only over small supports — small subsets of pure strategies that might appear in the equilibrium — and check each candidate via linear programming.
Fixed \(\epsilon\) is load-bearing there. The exponent carries \(1/\epsilon^2\), so letting the accuracy sharpen with the game — \(\epsilon = 1/n\), say — sends the running time to \(n^{O(n^2\log n)}\), which is far past \(2^n\) rather than short of it. The algorithm dies at the point where we start asking it for accuracy that scales.
Two standard bars measure how well approximation buys us out of a hardness result. A PTAS, a polynomial-time approximation scheme, hits any accuracy \(\epsilon\) we fix in advance in time polynomial in \(n\), with the dependence on \(\epsilon\) allowed to be as ugly as it likes — \(n^{1/\epsilon}\) qualifies, and at \(\epsilon=0.01\) that is \(n^{100}\). An FPTAS, the fully polynomial version, is the stronger bar: polynomial in \(n\) and \(1/\epsilon\) together, so that buying accuracy costs only polynomially more. Lipton et al. clear neither, since quasi-polynomial is easier than exact and still not polynomial.
Neither bar is reachable. The FPTAS goes because \(\epsilon\)-Nash is already PPAD-hard at inverse-polynomial \(\epsilon\) — the same regime where the exponent above explodes — so having one would collapse PPAD into P, which nobody expects. The PTAS goes to Rubinstein (2016): under the exponential-time hypothesis for PPAD there is a constant \(\epsilon\) that no polynomial-time algorithm gets below, and the quasi-polynomial lower bound he proves essentially meets the Lipton et al. upper bound above. Algorithm and hardness result are the same fact approached from either end.
Continuous local search (CLS) (Daskalakis and Papadimitriou 2011) is a related complexity class for problems where iterative local improvement of a continuous candidate converges to a local optimum — gradient descent is the prototype. Some natural game-theoretic problems probably have this flavour.
5 Algorithmic mechanism design
Designing the rules of the game — auctions, pricing, voting mechanisms — has its own complexity story. Some problems are NP-hard; some reduce to standard optimisation. The general programme treats mechanism design as algorithm design with an extra incentive-compatibility constraint.
6 Foundations under computability
When agents are themselves computational and reason about each other, classical game theory’s assumptions start to wobble. Two threads worth knowing about:
Fallenstein, Taylor, and Christiano (2015) develops reflective oracles — a formalism in which agents can in some sense reason about each other’s reasoning, addressing the diagonal/self-reference issues inherent in agents simulating each other. Useful when we want classical-style equilibrium theory to apply to AI agents reasoning about other AI agents.
Wyeth et al. (2025) extends this into limit-computable equilibria for extensive-form games, connecting to the Bayesian “grain of truth” tradition of learning in unknown games under computational constraints.
7 So do we even get to Nash equilibrium anyway?
If equilibria are intractable to compute, real agents probably do not reach them. Observed strategic play is mostly off-equilibrium, approximate, or learned through interaction — not the closed-form predictions of classical theory. This is the load-bearing observation behind behavioural game theory and learning-based approaches like multi-agent RL.
Computational complexity matters even outside computer science — see Aaronson (2011) for the careful version of this argument.
Kaznatcheev (2020) makes a related observation from biology: frequency-dependent selection in evolutionary dynamics is exponentially more powerful than frequency-independent selection, so the computational reach of evolution itself is shaped by game-theoretic structure.
8 Incoming
- How long until we approach Nash equilibrium (also covers Aumann’s correlated equilibrium).
- Fortnow and Gasarch, The complexity of Nash equilibrium
- What is PPAD