Article

The complexity of computing a Nash equilibrium

Authors:

Constantinos Daskalakis,

Paul W. Goldberg,

Christos H. PapadimitriouAuthors Info & Claims

STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing

Pages 71 - 78

https://doi.org/10.1145/1132516.1132527

Published: 21 May 2006 Publication History

Abstract

We resolve the question of the complexity of Nash equilibrium by showing that the problem of computing a Nash equilibrium in a game with 4 or more players is complete for the complexity class PPAD. Our proof uses ideas from the recently-established equivalence between polynomial time solvability of normal form games and graphical games, establishing that these kinds of games can simulate a PPAD-complete class of Brouwer functions.

References

[1]

P. Beame, S. Cook, J. Edmonds, R. Impagliazzo, T. Pitassi. "The Relative Complexity of NP Search Problems," J. Comput. Syst. Sci. 57, 1, pp. 13--19, 1998.

Digital Library

[2]

X. Chen and X. Deng. "3-NASH is PPAD-Complete," Electronic Colloquium in Computational Complexity TR05-134, 2005.

[3]

X. Chen and X. Deng. "Settling the Complexity of 2-Player Nash-Equilibrium," Electronic Colloquium in Computational Complexity TR05-140, 2005.

[4]

X. Chen, X. Deng and S. Teng. "Computing Nash Equilibria: Approximation and Smoothed Complexity," arXiv report, 2006.

[5]

B. Codenotti, A. Saberi, K. Varadarajan and Y. Ye. "Leontief Economies Encode Nonzero Sum Two-Player Games," Proceedings of SODA, 2006.

Digital Library

[6]

V. Conitzer and T. Sandholm. "Complexity Results about Nash Equilibria," Proceedings of IJCAI, 2003.

Digital Library

[7]

C. Daskalakis, A. Fabrikant and C. H. Papadimitriou. "The Game World is Flat: The Complexity of Nash Equilibria in Succinct Games," To appear, 2006.

[8]

C. Daskalakis and C. H. Papadimitriou. "Three-Player Games Are Hard," Electronic Colloquium in Computational Complexity TR05-139, 2005.

[9]

A. Fabrikant, C.H. Papadimitriou and K. Talwar. "The Complexity of Pure Nash Equilibria," Proceedings of STOC, 2004.

Digital Library

[10]

J. Geanakoplos. "Nash and Walras Equilibrium via Brouwer," Economic Theory, 21, 2003.

[11]

I. Gilboa and E. Zemel. "Nash and correlated equilibria: Some complexity considerations," Games and Economic Behavior, 1989.

[12]

P. W. Goldberg and C. H. Papadimitriou. "Reducibility Among Equilibrium Problems," Proceedings of STOC, 2006.

Digital Library

[13]

M. Hirsch, C. H. Papadimitriou and S. Vavasis. "Exponential Lower Bounds for Finding Brouwer Fixpoints," J. Complexity 5, pp. 379--416, 1989.

Digital Library

[14]

D. S. Johnson, C. H. Papadimitriou and M. Yannakakis, "How Easy is Local Search?," J. Comput. Syst. Sci. 37, 1, pp. 79--100,1988.

Digital Library

[15]

M. Kearns, M. Littman and S. Singh. "Graphical Models for Game Theory," Proceedings of UAI, 2001.

Digital Library

[16]

C. E. Lemke and J. T. Howson, Jr. "Equilibrium points of bimatrix games", SIAM J. Appl. Math. 12, pp. 413--423, 1964.

[17]

R. Lipton and E. Markakis. "Nash Equilibria via Polynomial Equations," Proceedings of LATIN, 2004.

[18]

R. Lipton, E. Markakis and A. Mehta. "Playing large games using simple strategies," Proceedings of the ACM Conference on Electronic Commerce, 2003.

Digital Library

[19]

M. Littman, M. Kearns and S. Singh. "An Efficient Exact Algorithm for Single Connected Graphical Games," Proceedings of NIPS, 2002.

[20]

J. Nash. "Noncooperative Games," Annals of Mathematics, 54, 289--295, 1951.

[21]

J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior, Princeton University Press, 1944.

[22]

M.J. Osborne and A. Rubinstein. A Course in Game Theory, MIT Press (1994).

[23]

C. H. Papadimitriou. "On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence," J. Comput. Syst. Sci. 48, 3, pp. 498--532, 1994.

Digital Library

[24]

C. H. Papadimitriou and T. Roughgarden. "Computing equilibria in multi-player games," Proceedings of SODA, 2005.

Digital Library

[25]

C. H. Papadimitriou. "Computing Correlated Equilibria in Multiplayer Games," Proceedings of STOC, 2005.

Digital Library

[26]

R. Savani and B. von Stengel. "Exponentially many steps for finding a Nash equilibrium in a Bimatrix Game," Proceedings of FOCS, 2004.

Digital Library

[27]

G. Schoenebeck and S. Vadhan. "The Computational Complexity of Nash Equilibria in Concisely Represented Games," To appear in ACM EC, 2006.

Digital Library

Cited By

Wu ZMu YYang XChen G(2024)Nash Equilibrium Solving for General Non-Zero-Sum Games from Non-Convergent Dynamics of Fictitious Play2024 43rd Chinese Control Conference (CCC)10.23919/CCC63176.2024.10662312(8180-8187)Online publication date: 28-Jul-2024
https://doi.org/10.23919/CCC63176.2024.10662312
Gharibian S(2024)Guest Column: The 7 faces of quantum NPACM SIGACT News10.1145/3639528.363953554:4(54-91)Online publication date: 3-Jan-2024
https://dl.acm.org/doi/10.1145/3639528.3639535
Qin RYu Y(2024)Learning in games: a systematic reviewScience China Information Sciences10.1007/s11432-023-3955-x67:7Online publication date: 28-Jun-2024
https://doi.org/10.1007/s11432-023-3955-x
Show More Cited By

Index Terms

The complexity of computing a Nash equilibrium
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Settling the complexity of computing two-player Nash equilibria

We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class PPAD (Polynomial Parity Argument, Directed version) introduced by Papadimitriou in 1991.

Our result, building upon the work of ...
The Complexity of Computing a Nash Equilibrium

In 1951, John F. Nash proved that every game has a Nash equilibrium [Ann. of Math. (2), 54 (1951), pp. 286-295]. His proof is nonconstructive, relying on Brouwer's fixed point theorem, thus leaving open the questions, Is there a polynomial-time ...
On the Complexity of Approximating a Nash Equilibrium
Special Issue on SODA'11

We show that computing a relatively (i.e., multiplicatively as opposed to additively) approximate Nash equilibrium in two-player games is PPAD-complete, even for constant values of the approximation. Our result is the first constant inapproximability ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing

May 2006

786 pages

ISBN:1595931341

DOI:10.1145/1132516

Program Chair:
Jon Kleinberg
Cornell University, Ithaca, NY

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 May 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC06

Sponsor:

STOC06: Symposium on Theory of Computing

May 21 - 23, 2006

WA, Seattle, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

320
Total Citations
View Citations
1,942
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wu ZMu YYang XChen G(2024)Nash Equilibrium Solving for General Non-Zero-Sum Games from Non-Convergent Dynamics of Fictitious Play2024 43rd Chinese Control Conference (CCC)10.23919/CCC63176.2024.10662312(8180-8187)Online publication date: 28-Jul-2024
https://doi.org/10.23919/CCC63176.2024.10662312
Gharibian S(2024)Guest Column: The 7 faces of quantum NPACM SIGACT News10.1145/3639528.363953554:4(54-91)Online publication date: 3-Jan-2024
https://dl.acm.org/doi/10.1145/3639528.3639535
Qin RYu Y(2024)Learning in games: a systematic reviewScience China Information Sciences10.1007/s11432-023-3955-x67:7Online publication date: 28-Jun-2024
https://doi.org/10.1007/s11432-023-3955-x
Liu L(2024)Approximate Nash Equilibrium Learning for n-Player Markov Games in Dynamic PricingProgress in Artificial Intelligence10.1007/978-3-031-73497-7_29(360-371)Online publication date: 3-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-73497-7_29
Hakim RMilionis JPapadimitriou CPiliouras G(2024)Swim till You Sink: Computing the Limit of a GameAlgorithmic Game Theory10.1007/978-3-031-71033-9_12(205-222)Online publication date: 31-Aug-2024
https://doi.org/10.1007/978-3-031-71033-9_12
Anagnostides ISandholm TOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)On the interplay between social welfare and tractability of equilibriaProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668295(49927-49959)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668295
Fox JMacDermott MHammond LHarrenstein PAbate AWooldridge M(2023)On Imperfect Recall in Multi-Agent Influence DiagramsElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.379.17379(201-220)Online publication date: 11-Jul-2023
https://doi.org/10.4204/EPTCS.379.17
Rajasekaran SBansal SVardi MElkind E(2023)Multi-agent systems with quantitative satisficing goalsProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/32(280-288)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/32
Deligkas AFasoulakis MMarkakis E(2023)A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix GamesACM Transactions on Algorithms10.1145/360669719:4(1-17)Online publication date: 8-Aug-2023
https://dl.acm.org/doi/10.1145/3606697
Lotidis KMertikopoulos PBambos N(2023)The Stability of Matrix Multiplicative Weights Dynamics in Quantum Games2023 62nd IEEE Conference on Decision and Control (CDC)10.1109/CDC49753.2023.10384169(1225-1232)Online publication date: 13-Dec-2023
https://doi.org/10.1109/CDC49753.2023.10384169
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten