an objective or potential function and
thus does not prove that computing an
MNE of a bimatrix game is in PLS. In
conjunction with our earlier reasoning, however, the Lemke-Howson algorithm shows that the problem is not
NP-hard unless NP = coNP. 25
A complexity class that is related to
but apparently different from PLS is
PPAD, which stands for “polynomial
parity argument, directed version”.
This class was defined in Papadimi-trou32 to capture the complexity of
computing MNE and related problems, such as computing approximate Brouwer fixed points. Its formal
definition parallels that of PLS, with a
PPAD problem consisting of the minimal ingredients necessary to execute
a Lemke-Howson-like path-following
procedure (again easily phrased as
three polynomial-time algorithms). A
problem in PPAD is PPAD-complete if
every problem in PPAD reduces to it in
polynomial time; the complete problem is then polynomial-time solvable
only if all problems in PPAD are. Since
PPAD contains several well-studied
problems that are not known to be
solvable via a polynomial-time algorithm, a proof of PPAD-completeness
can be interpreted as a significant intractability result.
A few years ago, the problem of
computing an MNE of a bimatrix game
was shown to be PPAD-complete. 8, 12
Thus, if P ≠ PPAD, there is no general-purpose and computationally efficient
algorithm for this problem, and in particular there is no general and tractable
way for players to reach a Nash equilibrium in a reasonable amount of time.
This hardness result casts doubt on the
predictive power of the Nash equilibrium concept in arbitrary games. See
Chen8 and Daskalakis et al. 12 for the
details of this tour de force result and
Daskalakis et al. 13 for a high-level survey of the proof.
The rapid rate of progress in algorith-
mic game theory has been nourished
by deep connections with other areas
of theoretical computer science and
a consistent infusion of new moti-
vating applications. There remains
a surfeit of important open research
directions across all three of the AGT
areas surveyed here, such as develop-
ing theory for the design and analysis
of mechanisms for multi-parameter
problems, for minimizing the ineffi-
ciency of equilibria (for example, via
a mediating network protocol), and
for the computation of approximate
equilibria. See Roughgarden35 and the
concluding sections of many chapters
in Nisan30 for more details and many
concrete open problems.
This work is supported in part by nsF CAReeR Award CCF-
0448664, an onR young Investigator Award, an AFosR
MuRI grant, and an Alfred P. sloan Fellowship.
1. Archer, A. and Tardos, É. Truthful mechanisms for one-parameter agents. FOCS ’01, 482–491.
2. Awerbuch, b., Azar, y., epstein, A., Mirrokni, V.s., and
skopalik, A. Fast convergence to nearly optimal
solutions in potential games. EC ’08, 264–273.
3. babaioff, M., lavi, R., and Pavlov, e. single-value
combinatorial auctions and algorithmic implementation
in undominated strategies. JACM 56, 1 (2009).
4. beckmann, M.j., McGuire, C.b., and Winsten, C.b.
Studies in the Economics of Transportation. yale
university Press, 1956.
5. bertsekas, D.P. and Tsitsiklis, j.n. Parallel and
Distributed Computation: Numerical Methods.
6. blum, A., hajiaghayi, M., ligett, K., and Roth, A. Regret
minimization and the price of total anarchy. STOC ’08,
7. braess, D. Über ein Paradoxon aus der
Verkehrsplanung. Unternehmensforschung, 12 (1968),
8. Chen, X., Deng, X., and Teng, s.-h. settling the
complexity of computing two-player nash equilibria.
JACM 56, 3 (2009).
9. Chien, s. and sinclair, s. Convergence to approximate
nash equilibria in congestion games. SODA ’07,
10. Cohen, j.e. and horowitz, P. Paradoxical behavior of
mechanical and electrical networks. Nature 352, 8
11. Cramton, P., shoham, y., and steinberg, R., eds.
Combinatorial Auctions. MI T Press, 2006.
12. Daskalakis, C., Goldberg, P. W., and Papadimitriou, C.h.
The complexity of computing a nash equilibria. SIAM
Journal on Computing 39, 1 (2009), 195–259.
13. Daskalakis, C., Goldberg, P. W., and Papadimitriou, C.h.
The complexity of computing a nash equilibrium.
Commun. ACM 52, 2 (Feb. 2009) 89–97.
14. Dhangwatnotai, P., Dobzinski, s., Dughmi, s., and
Roughgarden, T. Truthful approximation schemes for
single-parameter agents. FOCS ’08, 15–24.
15. etessami, K. and yannakakis, M. on the complexity of
nash equilibria and other fixed points. SIAM Journal
on Computing 39, 6 (2010) 2531–2597.
16. Fabrikant, A. and Papadimitriou, C.h. The complexity
of game dynamics: bGP oscillations, sink equlibria, and
beyond. SODA ’08, 844–853.
17. Fabrikant, A., Papadimitriou, C.h., and Talwar, K. The
complexity of pure nash equilibria. S TOC ’04, 604–612.
18. Feigenbaum, j., Parkes, D. C., and Pennock, D. M.
Computational challenges in e-commerce. Commun.
ACM 52, 1 (jan. 2009), 70–74.
19. Goemans, M. X., Mirrokni, V.s., and Vetta, A. sink
equilibria and convergence. FOCS ’05, 142–151.
20. jackson, M.o. A crash course in implementation theory.
Social Choice and Welfare 18, 4 (2001), 655–708.
21. johnson, D.s., Papadimitriou, C.h., and yannakakis, M.
how easy is local search? J. Computer and System
Sciences 37, 1 (1988), 79–100.
22. Koutsoupias, e. and Papadimitriou, C.h. Worst-case
equilibria. STACS ’ 99, 404–413.
23. lavi, R., Mu’alem, A., and nisan, n. Towards a
characterization of truthful combinatorial auctions.
FOCS ’03, 574–583.
24. lemke, C.e. and howson, j. T., jr. equilibrium points of
bimatrix games. SIAM J. 12, 2 (1964), 413–423.
25. Megiddo, n. and Papadimitriou, C.h. on total functions,
existence theorems and computational complexity.
Theoretical Computer Science 81, 2 (1991), 317–324.
26. Monderer, D. and shapley, l.s. Potential games. Games
and Economic Behavior 14, 1 (1996), 124–143.
27. Myerson, R. optimal auction design. Mathematics of
Operations Research 6, 1 (1981), 58–73.
28. nash, j. F., jr. equilibrium points in n-person games. In
Proceedings of the National Academy of Science 36, 1
29. nisan, n. and Ronen, A. Algorithmic mechanism design.
Games and Economic Behavior 35, 1–2 (2001), 166–196.
30. nisan, n., Roughgarden, T., Tardos, É., and Vazirani, V. V.,
eds. Algorithmic Game Theory. Cambridge university
31. nisan, n., schapira, M., Valiant, G., and Zohar, A. best-reply mechanisms. Working paper, 2009.
32. Papadimitriou, C.h. on the complexity of the parity
argument and other inefficient proofs of existence. J.
Computer and System Sciences 48 3 (1994), 498–532.
33. Papadimitriou, C.h., schapira, M., and singer, y. on the
hardness of being truthful. FOCS ’08, 250–259.
34. Rosenthal, R. W. A class of games possessing pure-strategy nash equilibria. International J. Game Theory
2, 1 (1973), 65–67.
35. Roughgarden, T. Algorithmic game theory: some
greatest hits and future directions. TCS ’08, 21–42.
36. Roughgarden, T. Intrinsic robustness of the price of
anarchy. S TOC ’09, 513–522.
37. Roughgarden, T. The price of anarchy is independent
of the network topology. J. Computer and System
Sciences 67, 2 (2003), 341–364.
38. Roughgarden, T. Computing equilibria: A computational
complexity perspective. Economic Theory 42, 1 (jan.
39. Roughgarden, T. and Tardos, É. how bad is selfish
routing? JACM 49, 2 (2002), 236–259.
40. shoham, y. Computer science and game theory.
Commun. ACM 51, 8 (Aug. 2008), 75–79.
41. shoham, y. and leyton-brown, K. Multiagent Systems:
Algorithmic, Game Theoretic and Logical Foundations.
Cambridge university Press, 2008.
42. steiglitz, K. Snipers, Shills, and Sharks: eBay and
Human Behavior. Princeton university Press, 2007.
43. Vickrey, W. Counterspeculation, auctions, and
competitive sealed tenders. J. Finance 16, 1 (1961),
Tim Roughgarden ( firstname.lastname@example.org) is an assistant
professor in the computer science and management
science and engineering departments at stanford
university, stanford, CA. he is the recipient of ACM’s 2009
Grace Murray hopper Award.