Article

Settling the Complexity of Two-Player Nash Equilibrium

Authors:

Xi Chen,

Xiaotie DengAuthors Info & Claims

FOCS '06: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science

Pages 261 - 272

https://doi.org/10.1109/FOCS.2006.69

Published: 21 October 2006 Publication History

Publisher Site

Abstract

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

Cited By

View all

Li HHuang WDuan ZMguni DShao KWang JDeng X(2024)A survey on algorithms for Nash equilibria in finite normal-form gamesComputer Science Review10.1016/j.cosrev.2023.10061351:COnline publication date: 25-Jun-2024
https://dl.acm.org/doi/10.1016/j.cosrev.2023.100613
Gao MJi ZLi TWang QOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Logarithmic-regret quantum learning algorithms for zero-sum gamesProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667481(31177-31203)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667481
Collina NArunachaleswaran EKearns MAgmon NAn BRicci AYeoh W(2023)Efficient Stackelberg Strategies for Finitely Repeated GamesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598695(643-651)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598695
Show More Cited By

Index Terms

Settling the Complexity of Two-Player Nash Equilibrium
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices
2. 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 ...
Settling the complexity of computing approximate two-player Nash equilibria

In our recent paper [Rubinstein 2016] we rule out a PTAS for the 2-Player Nash Equilibrium Problem. More precisely, we prove that there exists a constant ϵ > 0 such that, assuming the Exponential Time Hypothesis for PPAD, computing an ϵ-approximate Nash ...
Nash equilibrium based fairness
GameNets'09: Proceedings of the First ICST international conference on Game Theory for Networks

There are several approaches of sharing resources among users. There is a noncooperative approach wherein each user strives to maximize its own utility. The most common optimality notion is then the Nash equilibrium. Nash equilibria are generally Pareto ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

FOCS '06: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science

October 2006

748 pages

ISBN:0769527205

Publisher

IEEE Computer Society

United States

Publication History

Published: 21 October 2006

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

144
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Li HHuang WDuan ZMguni DShao KWang JDeng X(2024)A survey on algorithms for Nash equilibria in finite normal-form gamesComputer Science Review10.1016/j.cosrev.2023.10061351:COnline publication date: 25-Jun-2024
https://dl.acm.org/doi/10.1016/j.cosrev.2023.100613
Gao MJi ZLi TWang QOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Logarithmic-regret quantum learning algorithms for zero-sum gamesProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667481(31177-31203)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667481
Collina NArunachaleswaran EKearns MAgmon NAn BRicci AYeoh W(2023)Efficient Stackelberg Strategies for Finitely Repeated GamesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598695(643-651)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598695
Farina GCelli AMarchesi AGatti N(2022)Simple Uncoupled No-regret Learning Dynamics for Extensive-form Correlated EquilibriumJournal of the ACM10.1145/356377269:6(1-41)Online publication date: 18-Nov-2022
https://dl.acm.org/doi/10.1145/3563772
Eswaran SSachdeva MVimal VSeth DKalpam SAgarwal SMukherjee TDattagupta SGupta RLiu YShah MRajan STang JPrakash B(2020)Game Action Modeling for Fine Grained Analyses of Player Behavior in Multi-player Card Games (Rummy as Case Study)Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3394486.3403316(2657-2665)Online publication date: 23-Aug-2020
https://dl.acm.org/doi/10.1145/3394486.3403316
Wright JLeyton-Brown KBiró PHartline JOstrovsky MProcaccia A(2020)A Formal Separation Between Strategic and Nonstrategic BehaviorProceedings of the 21st ACM Conference on Economics and Computation10.1145/3391403.3399525(535-536)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.1145/3391403.3399525
Berthelsen MHansen K(2019)On the Computational Complexity of Decision Problems About Multi-player Nash EquilibriaAlgorithmic Game Theory10.1007/978-3-030-30473-7_11(153-167)Online publication date: 30-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-30473-7_11
Chan HJiang A(2018)An FPTAS for computing nash equilibrium in resource graph gamesProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304415.3304438(152-158)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304415.3304438
Gupta SMehta RAndre EKoenig SDastani MSukthankar G(2018)Nash Equilibrium Computation in Resource Allocation GamesProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3238035(1953-1955)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3238035
Panagopoulou PJohn KGrammati PStefanos GChristos D(2018)Simple algorithmic techniques to approximate nash equilibriaProceedings of the 22nd Pan-Hellenic Conference on Informatics10.1145/3291533.3291535(4-9)Online publication date: 29-Nov-2018
https://dl.acm.org/doi/10.1145/3291533.3291535
Show More Cited By

Abstract

Cited By

Index Terms

Recommendations

Settling the complexity of computing two-player Nash equilibria

Settling the complexity of computing approximate two-player Nash equilibria

Nash equilibrium based fairness

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations