Concepedia

Computational Complexity Of Equilibria

Computational Complexity of Equilibria is a theoretical framework in algorithmic game theory that characterizes the inherent difficulty of computing Nash equilibria in normal-form games, distinguishing it from related computational problems by focusing on the classification of equilibrium-finding tasks according to complexity classes such as PPAD or FNP.

247

Publications

14.4K

Citations

425

Authors

221

Institutions

Publications per year

2017–2026

47

Parents

Publications

247

The Complexity of Computing a Nash Equilibrium

Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou · SIAM Journal on Computing · 2009 · 951 citations

, , +11

Determining computational complexity from characteristic ‘phase transitions’

Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick et al. · Nature · 1999 · 803 citations

, , +14

The complexity of pure Nash equilibria

Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar · 2004 · 662 citations

, , +16

Settling the complexity of computing two-player Nash equilibria

Xi Chen, Xiaotie Deng, Shang‐Hua Teng · Journal of the ACM · 2009 · 579 citations

, , +17

Settling the Complexity of Two-Player Nash Equilibrium

Xi Chen, Xiaotie Deng · 2006 · 505 citations

, , +9

1–5 of 247

Authors

425

  1. CH
    Christos H. Papadimitriou

    University of California, Berkeley, United States

    12 publications · 2.9K citations

    11

    h-index

  2. PW
    Paul W. Goldberg

    University of Liverpool, United Kingdom

    10 publications · 2K citations

    10

    h-index

  3. CD
    Constantinos Daskalakis

    Massachusetts Institute of Technology, United States

    8 publications · 2K citations

    8

    h-index

  4. TS
    Tüomas Sandholm

    Carnegie Mellon University, United States

    7 publications · 542 citations

    7

    h-index

  5. HA
    Haris Aziz

    UNSW Sydney, Australia

    7 publications · 254 citations

    7

    h-index

1–5 of 425

Institutions

221

  1. Stanford University

    Stanford, United States

    14 h-index

    28 publications

    1.6K citations

  2. University of California, Berkeley

    Berkeley, United States

    13 h-index

    21 publications

    4.3K citations

  3. Carnegie Mellon University

    Pittsburgh, United States

    11 h-index

    21 publications

    1.1K citations

  4. University of Liverpool

    Liverpool, United Kingdom

    11 h-index

    24 publications

    1.3K citations

  5. Technische Universität Berlin

    Berlin, Germany

    9 h-index

    17 publications

    370 citations

  6. RWTH Aachen University

    Aachen, Germany

    9 h-index

    17 publications

    520 citations

  7. Hebrew University of Jerusalem

    Jerusalem, Israel

    8 h-index

    12 publications

    1.2K citations

  8. University of Oxford

    Oxford, United Kingdom

    8 h-index

    13 publications

    308 citations

1–8 of 221

Venues

  1. Proceedings of the AAAI Conference on Artificial Intelligence

    Conference · 12 publications · 265 citations

    12

    h-index

  2. arXiv (Cornell University)

    Repository · 11 publications · 207 citations

    10

    h-index

  3. Theoretical Computer Science

    10 publications · 315 citations

    10

    h-index

  4. ACM Transactions on Economics and Computation

    TEAC · 6 publications · 178 citations

    6

    h-index

  5. SIAM Journal on Computing

    5 publications · 1.4K citations

    5

    h-index

1–5