prediction. In view of these concerns, the main question
that emerges is whether there exists a polynomial-time
approximation scheme (PTAS) for computing approximate
Nash equilibria. That is, is there an algorithm for e-Nash
equilibria which runs in time polynomial in the game size,
if we allow arbitrary dependence of its running time on 1/e?
Such an algorithm would go a long way towards alleviating
the negative implications of our complexity result. While
this question remains open, one may find hope (at least for
games with a few players) in the existence of a subexponen-tial algorithm18 running in time O(nlogn/e ), where n is the size
2
of the game.
How about classes of concisely represented games with
many players? For a class of “tree-like” graphical games,
a PTAS has been given in Daskalakis and Papadimitriou, 6
but the complexity of the problem is unknown for more
general low-degree graphs. Finally, another positive recent
development7 has been a PTAS for a broad and important
class of games, called anonymous. These are games in
which the players are oblivious to each other’s identities;
that is, each player is affected not by who plays each strategy, but by how many play each strategy. Anonymous games
arise in many settings, including network congestion, markets, and social interactions, and so it is reassuring that
in these games approximate Nash equilibria can be computed efficiently.
An alternative form of computational hardness, exemplified in Hart and Mansour,
14 arises where instead of identifying problems that are resistant to any efficient algorithm,
one identifies problems that are resistant to specific “
natural” algorithms. In Hart,
14 lower bounds are shown for
“decoupled” dynamics, a model of strategic interaction in
which there is no central controller to find an equilibrium.
Instead, the players need to obtain one in a decentralized
manner. The study and comparison of these models will
continue to be an interesting research theme.
Finally, an overarching research question for the
Computer Science research community investigating game-theoretic issues, already raised in Friedman and Shenker10
but made a little more urgent by the present work, is to
identify novel concepts of rationality and equilibrium, especially applicable in the context of the Internet and its computational platforms.
References
1. bubelis, v. on equilibria in finite
games. Int. J. Game Theory 8, 2
(1979), 65–79.
2. chen, X., deng, X. settling the
complexity of 2-player nash-equilibrium.
Proceedings of FOCS (2006).
3. chen, X., deng, X., teng, s. computing
nash equilibria: approximation and
smoothed complexity. Proceedings of
FOCS (2006).
4. conitzer, v., sandholm, t. complexity
results about nash equilibria.
Proceedings of IJCAI (2003).
5. daskalakis, c., Papadimitriou, c.h.
three-player games are hard.
Electronic Colloquium in Computational
Complexity, tr05-139, 2005.
66. daskalakis, c., Papadimitriou, c. h.
discretized multinomial distributions
and nash equilibria in anonymous
games. Proceedings of FOCS (2008).
77. daskalakis, c., goldberg, P. W.,
Papadimitriou, c.h. the complexity
of computing a nash equilibrium.
Proceedings of STOC (2006).
8. daskalakis, c., goldberg, P. W.,
Papadimitriou, c.h. the complexity
of computing a nash equilibrium.
SICOMP. to appear.
9. etessami, k., yannakakis, M. on
the complexity of nash equilibria
and other fixed points (extended
abstract). Proceedings of FOCS
(2007), 113–123.
10. friedman, e., shenker, s. Learning
and implementation on the Internet.
department of economics, rutgers
University, 1997.
11. garey, M.r., Johnson, d.s. Computers
and Intractability: A Guide to
the Theory of NP-Completeness.
freeman, 1979.
12. gilboa, i., zemel, e. nash and
correlated equilibria: some
complexity considerations. Games
Econ. Behav. (1989).
13. goldberg, P. W., Papadimitriou, c.h.
reducibility among equilibrium
problems. Proceedings of STOC (2006).
14. hart, s. Mansour, y. how long to
equilibrium? the communication
complexity of uncoupled equilibrium
procedures. Proceedings of STOC (2007).
15. kearns, M., littman, M., singh, s.
graphical models for game theory.
Proceedings of UAI (2001).
16. knaster, b., kuratowski, c.,
mazurkiewicz, s. ein beweis des
fixpunktsatzes für n-dimensionale
simplexe. Fundamenta Mathematicae
14, (1929), 132–137.
17. lemke, c.e., howson, Jr.J.t.
equilibrium points of bimatrix games.
SIAM J. Appl. Math. 12, (1964),
413–423.
188. lipton, r., Markakis, e., Mehta, a.
Playing large games using simple
strategies. Proceedings of the ACM
Conference on Electronic Commerce
(2003).
19. nash, J. noncooperative games. Ann.
Math. 54, (1951), 289–295.
20. Papadimitriou, c.h. on the complexity
of the parity argument and other
inefficient proofs of existence.
J. Comput. Syst. Sci. 48, 3 (1994),
498–532.
21. scarf, h.e. the approximation of
fixed points of a continuous mapping.
SIAM J. Appl. Math. 15, (1967),
1328–1343.
22. shoham, y. computer science and game
theory. Commun. ACM 51, 8, 75–79.
Constantinos Daskalakis
( costis@cs.berkeley.edu), computer
science division, Uc berkeley.
Paul W. Goldberg
( P.W.goldberg@liverpool.ac.uk),
department of computer science,
University of liverpool.
© 2009 acM 0001-0782/09/0200 $5.00
Christos H. Papadimitriou
( christos@cs.berkeley.edu), computer
science division, Uc berkeley.
the research reported here by daskalakis
and Papadimitriou was supported by nsf
grant ccf0635319.
febrUary 2009 | vol. 52 | no. 2 | CommunICatIons of the aCm
97
