If every game has an equilibrium, why is finding one hard?
Topics 11 to 15 asked who gains when several players choose. These nine go further: what changes when the moves come in turns (25), when players hold secrets (26), when they meet again (27), when they learn as they go (28), when a shared signal is allowed (29), when each chooses a route (30), when the question is how hard an equilibrium is to find (31), the one place where quantum physics changes a game's value (32), and then a market you design and attack yourself (33).
John Nash proved in 1950 that every finite game has an equilibrium (possibly in mixed strategies). The proof does not say how to find it. For two players there is a procedure that always works (Lemke and Howson, 1964), and for decades it was open whether a fast one exists.
The slow procedure is support enumeration. In an equilibrium each player mixes over some set of moves, their support. Guess the two supports, and finding the mixed strategies is a system of linear equations: make each player indifferent between the moves in their support. Check that the answers are probabilities and that no move outside the support does better. If it fails, guess again. For a game with n moves per player there are about 4n guesses.
The answer, worked out between 2006 and 2009 by Daskalakis, Goldberg and Papadimitriou and by Chen, Deng and Teng, is probably not. Finding a Nash equilibrium of a two-player game is as hard as a class of problems called PPAD, the problems where a solution is guaranteed to exist by a parity argument but can be hard to locate. Zero-sum games are the exception: topic 12's linear program solves those quickly.
Two cautions. The result is about the worst case: the random games on this page are solved in a blink. And PPAD is not the class NP: it is a statement about problems whose answer always exists, which is why it is a different kind of hardness.
Support enumeration. For payoff matrices A (row) and B (column), try a row support I and column support J of the same size k. Find a column mix y on J and a number v with AI,J y = v for every row in I and Σy = 1. Find a row mix x on I and a number w with x BI,J = w for every column in J and Σx = 1. The pair is a Nash equilibrium if x, y ≥ 0 and no row outside I earns more than v against y and no column outside J earns more than w against x.
Counting the guesses. There are C(n, k) supports of each size k, so C(n, k)2 pairs, and Σk=1..n C(n, k)2 = C(2n, n) − 1 in all (by Vandermonde's identity). That is about 4n/√(πn).
Always an odd number. For almost every game, with no accidental ties, the number of Nash equilibria is odd (Wilson, 1971). For two players the Lemke–Howson path-following argument shows why: it starts from an artificial equilibrium, each path ends at a genuine one, and the paths pair the equilibria up except for one. A second method, run on the same random games as the page's toy, reached these (it follows one path per starting label, so it need not reach every equilibrium that exhaustive enumeration finds):
| Actions per player | Pairs of supports tried | Distinct equilibria reached by Lemke–Howson from its 2n starting labels |
|---|---|---|
| 2 | 5 | 2 |
| 3 | 19 | 1 |
| 4 | 69 | 2 |
| 5 | 251 | 1 |
| 6 | 923 | 2 |
The hardness result. Daskalakis, Goldberg and Papadimitriou (2009) showed that finding a Nash equilibrium of a game with four or more players is PPAD-complete; Chen, Deng and Teng (2009) extended it to two players, which is the case with the guaranteed odd count and the Lemke–Howson path. If a fast algorithm existed for two players, it would solve every problem in PPAD fast.
Why zero-sum is easy. In a zero-sum game the equilibria are the solutions of a linear program (topic 12), which has fast algorithms. Dropping “one player's gain is the other's loss” takes the problem from one with a fast algorithm to one that is PPAD-complete.
Draw a random game with two to eight actions per player. The page tries every pair of equal-sized supports, lists the equilibria it finds and counts the attempts. Draw several games: the count of equilibria is almost always odd.
Why it matters beyond games Equilibria are how economists predict what markets and mechanisms do. If finding one is intractable, a prediction that rests on players computing it is shaky. Much of algorithmic game theory since 2006 asks which games are easy (zero-sum games, and games in which one player has only two moves), and which weaker notions can be computed fast (correlated equilibrium, topic 29).
The sources Nash, PNAS 36, 48 (1950), doi:10.1073/pnas.36.1.48 and Annals of Mathematics 54, 286 (1951), doi:10.2307/1969529. Lemke and Howson, SIAM Journal 12, 413 (1964), doi:10.1137/0112033. Wilson, SIAM Journal on Applied Mathematics 21, 80 (1971), doi:10.1137/0121011. Daskalakis, Goldberg and Papadimitriou, SIAM Journal on Computing 39, 195 (2009), doi:10.1137/070699652. Chen, Deng and Teng, Journal of the ACM 56, article 14 (2009), doi:10.1145/1516512.1516516.
No quantum link is claimed. Whether quantum computers could find equilibria faster is an open question and nothing in this topic claims a quantum speed-up.
Check yourself
What does the PPAD-completeness of two-player Nash equilibrium say?
Nash's theorem guarantees an equilibrium for every finite game. The hardness result says that a fast general algorithm would solve every problem in PPAD fast, which is not expected. Zero-sum games remain easy (linear programming), and nothing here claims a quantum speed-up.