Settling the Complexity of Two-Player Nash Equilibrium

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Settling the Complexity of Two-Player Nash Equilibrium

Full text

Publisher Site

Source

FOCS archive
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science table of contents

Pages: 261 - 272

Year of Publication: 2006

ISBN ~ ISSN:0272-5428 , 0-7695-2720-5

Authors

Xi Chen	Tsinghua University, China
Xiaotie Deng	City University of Hong Kong, Hong Kong, China

Publisher

IEEE Computer Society Washington, DC, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 36

Additional Information:

abstract cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	10.1109/FOCS.2006.69

ABSTRACT

We prove that the problem of finding a Nash equilibrium in a two-player game is PPAD-complete.

CITED BY 36

	Andrew Gilpin , Tuomas Sandholm, Lossless abstraction of imperfect information games, Journal of the ACM (JACM), v.54 n.5, p.25-es, October 2007
	David S. Johnson, The NP-completeness column: Finding needles in haystacks, ACM Transactions on Algorithms (TALG), v.3 n.2, p.24-es, May 2007
	Edith Elkind , Leslie Ann Golberg , Paul W. Goldberg, Computing good nash equilibria in graphical games, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA
	Vincenzo Bonifaci , Ugo Di Iorio , Luigi Laura, The complexity of uniform Nash equilibria and related regular subgraph problems, Theoretical Computer Science, v.401 n.1-3, p.144-152, July, 2008
	Tomas Feder , Hamid Nazerzadeh , Amin Saberi, Approximating nash equilibria using small-support strategies, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA
	Constantinos Daskalakis , Aranyak Mehta , Christos Papadimitriou, Progress in approximate nash equilibria, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA
	Peter Bro Miltersen , Troels Bjerre Sørensen, Fast algorithms for finding proper strategies in game trees, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.874-883, January 20-22, 2008, San Francisco, California
	Christos H. Papadimitriou , Tim Roughgarden, Computing correlated equilibria in multi-player games, Journal of the ACM (JACM), v.55 n.3, p.1-29, July 2008
	Po-An Chen , David Kempe, Altruism, selfishness, and spite in traffic routing, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA
	Constantinos Daskalakis , Grant Schoenebeck , Gregory Valiant , Paul Valiant, On the complexity of Nash equilibria of action-graph games, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.710-719, January 04-06, 2009, New York, New York
	Yoav Shoham, Computer science and game theory, Communications of the ACM, v.51 n.8, August 2008
	Avrim Blum , MohammadTaghi Hajiaghayi , Katrina Ligett , Aaron Roth, Regret minimization and the price of total anarchy, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Christian Borgs , Jennifer Chayes , Nicole Immorlica , Adam Tauman Kalai , Vahab Mirrokni , Christos Papadimitriou, The myth of the folk theorem, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Ashish Goel , Hamid Nazerzadeh, Price based protocols for fair resource allocation: convergence time analysis and extension to Leontief utilities, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1145-1153, January 20-22, 2008, San Francisco, California
	Jun Xiao , Naixue Xiong , Laurence T. Yang , Y. He, A joint selfish routing and channel assignment game in wireless mesh networks, Computer Communications, v.31 n.7, p.1447-1459, May, 2008
	Alex Fabrikant , Christos H. Papadimitriou, The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.844-853, January 20-22, 2008, San Francisco, California
	Steve Chien , Alistair Sinclair, Convergence to approximate Nash equilibria in congestion games, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.169-178, January 07-09, 2007, New Orleans, Louisiana
	Tomas Klos , Gerrit Jan van Ahee, Evolutionary dynamics for designing multi-period auctions, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
	Baruch Awerbuch , Yossi Azar , Amir Epstein , Vahab Seyed Mirrokni , Alexander Skopalik, Fast convergence to nearly optimal solutions in potential games, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA
	Ye Du, Note: On the complexity of deciding bimatrix games similarity, Theoretical Computer Science, v.407 n.1-3, p.583-586, November, 2008
	Bruno Codenotti , Amin Saberi , Kasturi Varadarajan , Yinyu Ye, The complexity of equilibria: Hardness results for economies via a correspondence with games, Theoretical Computer Science, v.408 n.2-3, p.188-198, November, 2008
	Sam Ganzfried , Tuomas Sandholm, Computing an approximate jam/fold equilibrium for 3-player no-limit Texas Hold'em tournaments, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
	Xiaotie Deng , Ye Du, The computation of approximate competitive equilibrium is PPAD-hard, Information Processing Letters, v.108 n.6, p.369-373, November, 2008
	Felix Brandt , Felix Fischer , Markus Holzer, Symmetries and the complexity of pure Nash equilibrium, Journal of Computer and System Sciences, v.75 n.3, p.163-177, May, 2009
	Felix Brandt , Felix Fischer , Paul Harrenstein , Yoav Shoham, Ranking games, Artificial Intelligence, v.173 n.2, p.221-239, February, 2009
	Spyros C. Kontogiannis , Panagiota N. Panagopoulou , Paul G. Spirakis, Polynomial algorithms for approximating Nash equilibria of bimatrix games, Theoretical Computer Science, v.410 n.17, p.1599-1606, April, 2009
	Constantinos Daskalakis , Paul W. Goldberg , Christos H. Papadimitriou, The complexity of computing a Nash equilibrium, Communications of the ACM, v.52 n.2, February 2009
	Albert Xin Jiang , Kevin Leyton-Brown, Computing pure Nash equilibria in symmetric action graph games, Proceedings of the 22nd national conference on Artificial intelligence, p.79-85, July 22-26, 2007, Vancouver, British Columbia, Canada
	Constantinos Daskalakis , Aranyak Mehta , Christos Papadimitriou, A note on approximate Nash equilibria, Theoretical Computer Science, v.410 n.17, p.1581-1588, April, 2009
	George Christodoulou , Elias Koutsoupias , Akash Nanavati, Coordination mechanisms, Theoretical Computer Science, v.410 n.36, p.3327-3336, August, 2009
	Felix Brandt , Felix Fischer , Paul Harrenstein , Yoav Shoham, A game-theoretic analysis of strictly competitive multiagent scenarios, Proceedings of the 20th international joint conference on Artifical intelligence, p.1199-1206, January 06-12, 2007, Hyderabad, India
	Georg Gottlob , Gianluigi Greco , Toni Mancini, Complexity of pure equilibria in Bayesian games, Proceedings of the 20th international joint conference on Artifical intelligence, p.1294-1299, January 06-12, 2007, Hyderabad, India
	Gianluigi Greco , Francesco Scarcello, On the complexity of constrained Nash equilibria in graphical games, Theoretical Computer Science, v.410 n.38-40, p.3901-3924, September, 2009
	Robert Kleinberg , Georgios Piliouras , Éva Tardos, Load balancing without regret in the bulletin board model, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Felix Brandt , Markus Brill , Felix Fischer , Paul Harrenstein, Computational aspects of Shapley's saddles, Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems, May 10-15, 2009, Budapest, Hungary
	Vahab S. Mirrokni , Alexander Skopalik, On the complexity of nash dynamics and sink equilibria, Proceedings of the tenth ACM conference on Electronic commerce, July 06-10, 2009, Stanford, California, USA