Nash proved every game has an equilibrium. That is an existence theorem, not a recipe. For large games, actually computing an equilibrium can be as hard as searching a maze that you know has an exit but cannot shortcut to.
The complexity of equilibria
Existence and computability are different questions. A Nash equilibrium is guaranteed, yet finding one is PPAD-complete, believed to require exponential effort in the worst case. The gap traces back to a combinatorial fact, Sperner’s lemma, where a solution provably exists but locating it can mean a long walk.
Nash's theorem guarantees a mixed equilibrium exists in every...
A problem being hard to solve is different from its solution...
Predict, then play
Sperner’s lemma: color a triangle’s corners 1, 2, 3, and color each edge midpoint with one of its two corner colors. However you do it, at least one small triangle uses all three colors.
Why did that happen?
Take a guess, then reveal the reason
The boundary coloring forces a kind of parity: as you trace the edges, the colors must switch in a way that leaves an odd number of complete triangles inside, so at least one must exist. That is a pure existence guarantee, with no shortcut to say where. The same structure underlies Nash: a fixed-point argument (Brouwer via Sperner) proves an equilibrium is there, but the proof gives no efficient way to find it. Existence and tractability are separate.
The math
PPAD is a complexity class for problems whose solutions are guaranteed to exist by a parity argument (an “end of a directed line”), like Sperner’s lemma and Brouwer fixed points. Computing a Nash equilibrium of a general game is PPAD-complete: as hard as any problem in the class. This is strong evidence that no efficient (polynomial-time) algorithm exists, even though a solution is guaranteed. The special case of two-player zero-sum games is easy, solvable as a linear program.
The Lemke-Howson algorithm finds a two-player Nash equilibrium by pivoting along a path of almost-equilibria, exactly the “follow the directed line to its end” structure of PPAD. Savani and von Stengel (2006) constructed games forcing this path to be exponentially long. So the guarantee that the path ends (a solution exists) does not bound how far you must walk.
The contrast with zero-sum games is sharp: there, the minimax value is a linear program, computable quickly. Difficulty appears only in general (non-zero-sum) games.
Work it out
Existence without a shortcut
Try to two-color your way out of a panchromatic triangle in the interactive: fix the corners at 1, 2, 3 and set each midpoint to one of its allowed colors. Enumerate the four small triangles. No matter the choice, an odd number of them (so at least one) carry all three colors. You cannot avoid it, and there is no rule that names the winner without checking.
Now scale up. In a finely subdivided triangle with millions of cells, the panchromatic triangle still exists, but finding it may require following a corridor of cells step by step, a walk that can be exponentially long. That is the essence of PPAD: the exit is guaranteed, the search is not cheap. Computing a Nash equilibrium inherits exactly this hardness.
Key idea
A Nash equilibrium always exists, but computing one is PPAD-complete, as hard as finding the guaranteed-but-hidden panchromatic triangle in Sperner’s lemma. Zero-sum games are the easy exception, solvable as a linear program.
Check yourself
Sources
- Daskalakis, C., Goldberg, P. W., and Papadimitriou, C. H. (2009). The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1), 195-259.
- Savani, R., and von Stengel, B. (2006). Hard-to-solve bimatrix games. Econometrica, 74(2), 397-429.