The complexity of pure Nash equilibria

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The complexity of pure Nash equilibria

Full text

Pdf (206 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing table of contents

Chicago, IL, USA

SESSION: Session 17B table of contents

Pages: 604 - 612

Year of Publication: 2004

ISBN:1-58113-852-0

Authors

Alex Fabrikant	UC Berkeley, CA
Christos Papadimitriou	UC Berkeley, CA
Kunal Talwar	UC Berkeley, CA

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 25, Downloads (12 Months): 192, Citation Count: 49

Additional Information:

abstract references cited by index terms review collaborative colleagues

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

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1007352.1007445 What is a DOI?

ABSTRACT

We investigate from the computational viewpoint multi-player games that are guaranteed to have pure Nash equilibria. We focus on congestion games, and show that a pure Nash equilibrium can be computed in polynomial time in the symmetric network case, while the problem is PLS-complete in general. We discuss implications to non-atomic congestion games, and we explore the scope of the potential function method for proving existence of pure Nash equilibria.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. Beckmann, C. McGuire, and C. Winsten. Studies in the Economics of Transportation. Yale University Press, 1956.
	2	V. Conitzer and T. Sandholm. Complexity results about nash equilibria. In Proc. of IJCAI, pages 765--771, 2003.
	3	S. C. Dafermos and F. T. Sparrow. The traffic assignment problem for a general network. Journal of Research of the National Bureau of Standards, 73(2):91--118, 1969.
	4	Alex Fabrikant , Ankur Luthra , Elitza Maneva , Christos H. Papadimitriou , Scott Shenker, On a network creation game, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.347-351, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872088]
	5	L. Fleischer, 2004. Personal Communication.
	6	Dimitris Fotakis , Spyros C. Kontogiannis , Elias Koutsoupias , Marios Mavronicolas , Paul G. Spirakis, The Structure and Complexity of Nash Equilibria for a Selfish Routing Game, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.123-134, July 08-13, 2002
	7	Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
	8	Andrew V. Goldberg , Robert E. Tarjan, Finding minimum-cost circulations by successive approximation, Mathematics of Operations Research, v.15 n.3, p.430-466, Aug. 1990 [doi>10.1287/moor.15.3.430]
	9	Michael D. Grigoriadis , Leonid G. Khachiyan, Coordination complexity of parallel price-directive decomposition, Mathematics of Operations Research, v.21 n.2, p.321-340, May 1996 [doi>10.1287/moor.21.2.321]
	10	David S. Johnson , Christos H. Papadimtriou , Mihalis Yannakakis, How easy is local search?, Journal of Computer and System Sciences, v.37 n.1, p.79-100, August 1988 [doi>10.1016/0022-0000(88)90046-3]
	11	Alexander V. Karzanov , S. Thomas McCormick, Polynomial Methods for Separable Convex Optimization in Unimodular Linear Spaces with Applications, SIAM Journal on Computing, v.26 n.4, p.1245-1275, Aug. 1997 [doi>10.1137/S0097539794263695]
	12	M. W. Krentel. Structure in locally optimal solutions. In Proc. of IEEE FOCS, pages 216--221, 1989.
	13	Richard J. Lipton , Evangelos Markakis , Aranyak Mehta, Playing large games using simple strategies, Proceedings of the 4th ACM conference on Electronic commerce, p.36-41, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779933]
	14	I. Milchtaich. Congestion games with player-specific payoff functions. Games and Economic Behavior, 13:111--124, 1996.
	15	D. Monderer and L. S. Shapley. Potential games. Games and Economic Behavior, 14:124--143, 1996.
	16	J. F. Nash. Equilibrium points in n-person games. In Proc. of National Academy of Sciences, volume 36, pages 48--49, 1950.
	17	James B. Orlin , Abraham P. Punnen , Andreas S. Schulz, Approximate local search in combinatorial optimization, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	18	Christos H. Papadimitriou, The complexity of the Lin-Kernighan heuristic for the traveling salesman problem, SIAM Journal on Computing, v.21 n.3, p.450-465, June 1992 [doi>10.1137/0221030]
	19	Christos H. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and System Sciences, v.48 n.3, p.498-532, June 1994 [doi>10.1016/S0022-0000(05)80063-7]
	20	R. W. Rosenthal. A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2:65--67, 1973.
	21	T. Roughgarden and E. Tardos. Bounding the inefficiency of equilibria in nonatomic congestion games. Games and Economic Behavior. To appear.
	22	Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
	23	R. Savani and B. von Stengel. Long lemke-howson paths. Technical Report LSE-CDAM-2003-14, LSE, 2003.
	24	Alejandro A. Schäffer , Mihalis Yannakakis, Simple local search problems that are hard to solve, SIAM Journal on Computing, v.20 n.1, p.56-87, Feb. 1991 [doi>10.1137/0220004]
	25	Adrian Vetta, Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.416, November 16-19, 2002
	26	B. von Stengel. Computing equilibria for two-person games. In R. J. Aumann and S. Hart, editors, Handbook of Game Theory, Vol. 3, chapter 45, pages 1723--1759. North-Holland, Amsterdam, 2002.
	27	M. Voorneveld, P. Borm, F. van Megen, S. Tijs, and G. Facchini. Congestion games and potentials reconsidered. International Game Theory Review, 1:283--299, 1999.

CITED BY 49

	Martin Gairing , Burkhard Monien , Karsten Tiemann, Selfish routing with incomplete information, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Magnús M. Halldórsson , Joseph Y. Halpern , Li (Erran) Li , Vahab S. Mirrokni, On spectrum sharing games, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Byung-Gon Chun , Kamalika Chaudhuri , Hoeteck Wee , Marco Barreno , Christos H. Papadimitriou , John Kubiatowicz, Selfish caching in distributed systems: a game-theoretic analysis, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Christos H. Papadimitriou , Tim Roughgarden, Computing equilibria in multi-player games, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Éva Tardos, Network games, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.341-342, June 13-16, 2004, Chicago, IL, USA
	George Christodoulou , Elias Koutsoupias, The price of anarchy of finite congestion games, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Baruch Awerbuch , Yossi Azar , Amir Epstein, Large the price of routing unsplittable flow, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Deeparnab Chakrabarty , Aranyak Mehta , Viswanath Nagarajan, Fairness and optimality in congestion games, Proceedings of the 6th ACM conference on Electronic commerce, p.52-57, June 05-08, 2005, Vancouver, BC, Canada
	Christos H. Papadimitriou, Computing correlated equilibria in multi-player games, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Dimitris Fotakis , Spyros Kontogiannis , Paul Spirakis, Selfish unsplittable flows, Theoretical Computer Science, v.348 n.2, p.226-239, 8 December 2005
	Constantinos Daskalakis , Paul W. Goldberg , Christos H. Papadimitriou, The complexity of computing a Nash equilibrium, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Richard Cole , Lisa Fleischer, Fast-converging tatonnement algorithms for one-time and ongoing market problems, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Vittorio Bilò , Michele Flammini , Giovanna Melideo , Luca Moscardelli, On Nash equilibria for multicast transmissions in ad-hoc wireless networks, Wireless Networks, v.14 n.2, p.147-157, March 2008
	Matt Lepinski , David Liben-Nowell , Seth Gilbert , April Rasala Lehman, Playing games in many possible worlds, Proceedings of the 7th ACM conference on Electronic commerce, p.150-159, June 11-15, 2006, Ann Arbor, Michigan, USA
	Rene Beier , Artur Czumaj , Piotr Krysta , Berthold Vöcking, Computing equilibria for a service provider game with (Im)perfect information, ACM Transactions on Algorithms (TALG), v.2 n.4, p.679-706, October 2006
	Chandra Chekuri , Julia Chuzhoy , Liane Lewin-Eytan , Joseph (Seffi) Naor , Ariel Orda, Non-cooperative multicast and facility location games, Proceedings of the 7th ACM conference on Electronic commerce, p.72-81, June 11-15, 2006, Ann Arbor, Michigan, USA
	Simon Fischer , Harald Räcke , Berthold Vöcking, Fast convergence to Wardrop equilibria by adaptive sampling methods, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Ara Hayrapetyan , Éva Tardos , Tom Wexler, The effect of collusion in congestion games, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Thomas Moscibroda , Stefan Schmid , Roger Wattenhofer, On the topologies formed by selfish peers, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Paul W. Goldberg , Christos H. Papadimitriou, Reducibility among equilibrium problems, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Panagiota N. Panagopoulou , Paul G. Spirakis, Algorithms for pure Nash equilibria in weighted congestion games, Journal of Experimental Algorithmics (JEA), 11, 2006
	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
	Alexander Skopalik , Berthold Vöcking, Inapproximability of pure nash equilibria, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	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
	Michal Penn , Maria Polukarov , Moshe Tennenholtz, Congestion games with load-dependent failures: identical resources, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA
	Angelo Fanelli , Michele Flammini , Luca Moscardelli, On the convergence of multicast games in directed networks, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	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
	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
	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
	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
	Vittorio Bilò , Angelo Fanelli , Michele Flammini , Luca Moscardelli, Graphical congestion games with linear latencies, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Dimitris Fotakis , Spyros Kontogiannis , Paul Spirakis, Atomic congestion games among coalitions, ACM Transactions on Algorithms (TALG), v.4 n.4, p.1-27, August 2008
	Michal Penn , Maria Polukarov , Moshe Tennenholtz, Asynchronous congestion games, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
	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
	Heiner Ackermann , Heiko Röglin , Berthold Vöcking, On the impact of combinatorial structure on congestion games, Journal of the ACM (JACM), v.55 n.6, p.1-22, December 2008
	Ioannis Caragiannis, Efficient coordination mechanisms for unrelated machine scheduling, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.815-824, January 04-06, 2009, New York, New York
	Zhenjie Zhang , Laks V. S. Lakshmanan , Anthony K. H. Tung, On domination game analysis for microeconomic data mining, ACM Transactions on Knowledge Discovery from Data (TKDD), v.2 n.4, p.1-27, January 2009
	Samuel Ieong , Robert McGrew , Eugene Nudelman , Yoav Shoham , Qixiang Sun, Fast and compact: a simple class of congestion games, Proceedings of the 20th national conference on Artificial intelligence, p.489-494, July 09-13, 2005, Pittsburgh, Pennsylvania
	Federico Mari , Igor Melatti , Ivano Salvo , Enrico Tronci , Lorenzo Alvisi , Allen Clement , Harry Li, Model checking nash equilibria in MAD distributed systems, Proceedings of the 2008 International Conference on Formal Methods in Computer-Aided Design, p.1-8, November 17-20, 2008, Portland, Oregon
	Heiner Ackermann , Heiko Röglin , Berthold Vöcking, Pure Nash equilibria in player-specific and weighted congestion games, Theoretical Computer Science, v.410 n.17, p.1552-1563, April, 2009
	Heiner Ackermann , Petra Berenbrink , Simon Fischer , Martin Hoefer, Concurrent imitation dynamics in congestion games, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	George Christodoulou , Elias Koutsoupias , Akash Nanavati, Coordination mechanisms, Theoretical Computer Science, v.410 n.36, p.3327-3336, August, 2009
	Tim Roughgarden, Intrinsic robustness of the price of anarchy, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	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
	Georg Gottlob , Gianluigi Greco , Francesco Scarcello, Pure Nash equilibria: hard and easy games, Journal of Artificial Intelligence Research, v.24 n.1, p.357-406, July 2005
	Dimitris Fotakis , Spyros Kontogiannis , Elias Koutsoupias , Marios Mavronicolas , Paul Spirakis, The structure and complexity of Nash equilibria for a selfish routing game, Theoretical Computer Science, v.410 n.36, p.3305-3326, August, 2009
	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

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.1 COMPUTATION BY ABSTRACT DEVICES
F.1.3 Complexity Measures and Classes
Subjects: Reducibility and completeness

Additional Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Theory

Keywords:
PLS, PLS-completeness, complexity, congestion games, games, local search, pure Nash equilibria

REVIEW

"William A Fahle : Reviewer"

A relatively new research area in theoretical computer science, at the intersection of game theory and computer science, is brought to light in this paper. The problem of computing pure Nash equilibria (PNE) is discussed, and specific cases of con more...

Collaborative Colleagues:

Alex Fabrikant: colleagues

Christos Papadimitriou: colleagues

Kunal Talwar: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player