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): 18, Downloads (12 Months): 134, Citation Count: 26

Additional Information:

abstract references cited by index terms review collaborative colleagues peer to peer

Tools and Actions:	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
	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
	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 26

	Panagiota N. Panagopoulou , Paul G. Spirakis, Algorithms for pure Nash equilibria in weighted congestion games, Journal of Experimental Algorithmics (JEA), 11, 2006
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	É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
	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
	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
	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
	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
	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
	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
	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

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

Peer to Peer - Readers of this Article have also read:

Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein
Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM 34, 12
Ellen Francik , Susan Ehrlich Rudman , Donna Cooper , Stephen Levine
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE conference on Design automation
Gwo-Dong Chen , Daniel D. Gajski

Adobe Acrobat

QuickTime

Windows Media Player

Real Player