A Nash Equilibrium Always Exists, but Computing One Is PPAD-Complete — Epoche C1
In a one-page note of 1950, expanded into a full paper in 1951, John Nash proved that every finite game — finitely many players, each choosing among finitely many actions — has at least one equilibrium, provided players are allowed to randomise. A comfortable belief grew from this theorem: since an equilibrium always exists, analysing a game means computing it and announcing the result as what rational players will do. The step from "it exists" to "we can find it" went largely unexamined. This essay examines that step, and the answer, assembled between 1991 and 2009, is negative in a precise sense. Computing a Nash equilibrium is complete for a complexity class called PPAD, whose problems are widely believed to admit no polynomial-time algorithm. Getting to that statement requires first seeing exactly what Nash's proof does and does not deliver. Existence by fixed point A mixed strategy is a probability distribution over a player's actions: to play one is to let a random device pick the action with the stated probabilities. Write $\sigma_i$ for a mixed strategy of player $i$, $\sigma_{-i}$ for the strategies of everyone else, and $u_i$ for player $i$'s expected payoff. A profile $(\sigma_1^*,\ldots,\sigma_n^*)$, one strategy per player, is a Nash equilibrium when nobody gains by deviating alone: $$u_i(\sigma_i^*, \sigma_{-i}^*) \;\ge\; u_i(\sigma_i, \sigma_{-i}^*) \quad\text{for every player } i \text{ and every alternative } \sigma_i .$$ Nash's 1951 argument constructs an explicit continuous map on the space of profiles that pushes probability towards actions currently paying above average. For each player $i$ and each pure action $a$, define the gain $$\varphi_i(a;\sigma) \;=\; \max\bigl(0,\; u_i(a,\sigma_{-i}) - u_i(\sigma)\bigr),$$ the amount by which playing $a$ outright would beat what $i$ is currently getting, or zero if it would not. The map sends $\sigma_i(a)$ to $\bigl(\sigma_i(a) + \varphi_i(a;\sigma)\bigr)\big/\bigl(1 + \sum_b \varphi_i(b;\sigma)\bigr)$, the denominator restoring the probabilities to sum to one. Why its fixed points are exactly the equilibria takes three lines. At a fixed point, clearing the denominator gives $\sigma_i(a)\sum_b\varphi_i(b) = \varphi_i(a)$ for every $a$. Suppose some player's gains were not all zero, so $\sum_b \varphi_i(b) \gt 0$. Since $u_i(\sigma)$ is the average of $u_i(a,\sigma_{-i})$ weighted by $\sigma_i$, at least one action $a$ actually played must pay at or below that average, and for it $\varphi_i(a) = 0$; but then $\sigma_i(a)\sum_b\varphi_i(b) = 0$ with $\sigma_i(a) \gt 0$ forces the sum to vanish, a contradiction. So every gain is zero, meaning no pure action beats the current payoff — and since any mixed deviation is an average of pure ones, that is the Nash condition. The existence of a fixed point then comes from Brouwer's theorem: every continuous map from a compact convex set into itself leaves at least one point unmoved. The space of profiles is a product of probability simplices, which is closed, bounded and convex, and the map above is manifestly continuous, so the hypotheses hold. What matters for this essay is what the theorem withholds. It certifies that a fixed point exists; it names no procedure for locating one. Nash's proof inherits that silence exactly. The cost of the search The silence would be harmless if the obvious methods worked, so consider them. Take two players with $m$ actions each. The natural approach guesses the supports — the sets of actions each player uses with positive probability. A correct guess makes the rest easy, because of an indifference condition that follows directly from the definition: every action inside a player's support must earn exactly the same expected payoff, since if one earned less the player would shift probability away from it, contradicting equilibrium. Fixing the supports therefore turns the problem into a system of linear equations in the probabilities, together with the inequalities saying that actions outside the support do no better. Linear systems are cheap. The guessing is not. Each player has $2^m - 1$ non-empty candidate supports, so there are $(2^m-1)^2$ pairs to test; at $m = 50$ that is about $2^{100} \approx 1.3\times10^{30}$. The Lemke–Howson algorithm of 1964 avoids blind enumeration, and its structure matters later, so it is worth describing. Label each pure action of each player, and call a candidate profile completely labelled when, for every action, either that action is unplayed or it is a best response — which is precisely the equilibrium condition restated. Lemke and Howson start from an artificial completely labelled point at which both players play nothing, drop one label, and follow the resulting path of almost-completely-labelled points, pivoting from vertex to vertex much as the simplex method does in linear programming. The path is unique and cannot revisit a point, so it must terminate, and it can only terminate at another completely labelled point: an equilibrium. As a by-product the pairing of path endpoints shows that a generic two-player game has an odd number of equilibria. That is an elegant algorithm, and it is not fast. Savani and von Stengel constructed in 2006 a family of square two-player games on which the Lemke–Howson path has exponential length no matter which label is dropped to start it. Meanwhile one special case shows what tractability looks like: two-player zero-sum games, where one player's gain is the other's loss, reduce by von Neumann's minimax theorem to a pair of dual linear programs, and linear programming has been known since Khachiyan's work in 1979 to be solvable in polynomial time. So the question is sharp. Is the general case intrinsically hard, or was the right idea still missing? Why NP-completeness is the wrong yardstick The standard way to argue that a problem is intrinsically hard is to prove it NP-complete, and the first thing to establish is that this route is closed — otherwise the eventual answer looks lik