On the Complexity of Nash Equilibria in Anonymous Games

被引：18
|
作者：
Chen, Xi [1 ]
Durfee, David [2 ]
Orfanou, Anthi [1 ]
机构：
[1] Columbia Univ, 1214 Amsterdam Ave, New York, NY 10027 USA
[2] Georgia Inst Technol, Atlanta, GA 30332 USA
来源：
STOC'15: PROCEEDINGS OF THE 2015 ACM SYMPOSIUM ON THEORY OF COMPUTING | 2015年
关键词：
D O I：
10.1145/2746539.2746571
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We show that the problem of finding an epsilon-approximate Nash equilibrium in an anonymous game with seven pure strategies is complete in PPAD, when the approximation parameter epsilon is exponentially small in the number of players.
引用
收藏
页码：381 / 390
页数：10
相关论文
共 50 条
  • [1] Approximate Nash equilibria in anonymous games
    Daskalakis, Constantinos
    Papadimitriou, Christos H.
    JOURNAL OF ECONOMIC THEORY, 2015, 156 : 207 - 245
  • [2] Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games
    Daskalakis, Constantinos
    Papadimitriou, Christos H.
    PROCEEDINGS OF THE 49TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2008, : 25 - 34
  • [3] Query complexity of approximate equilibria in anonymous games
    Goldberg, Paul W.
    Turchetta, Stefano
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2017, 90 : 80 - 98
  • [4] THE COMPLEXITY OF NASH EQUILIBRIA IN STOCHASTIC MULTIPLAYER GAMES
    Ummels, Michael
    Wojtczak, Dominik
    LOGICAL METHODS IN COMPUTER SCIENCE, 2011, 7 (03)
  • [5] On the complexity of constrained Nash equilibria in graphical games
    Greco, Gianluigi
    Scarcello, Francesco
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (38-40) : 3901 - 3924
  • [6] The complexity of Nash equilibria in infinite multiplayer games
    Ummels, Michael
    FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATIONAL STRUCTURES, PROCEEDINGS, 2008, 4962 : 20 - 34
  • [7] On the Complexity of Nash Equilibria of Action-Graph Games
    Daskalakis, Constantinos
    Schoenebeck, Grant
    Valiant, Gregory
    Valiant, Paul
    PROCEEDINGS OF THE TWENTIETH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2009, : 710 - +
  • [8] The Complexity of Nash Equilibria in Limit-Average Games
    Ummels, Michael
    Wojtczak, Dominik
    CONCUR 2011: CONCURRENCY THEORY, 2011, 6901 : 482 - +
  • [9] The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games
    Ummels, Michael
    Wojtczak, Dominik
    AUTOMATA, LANGUAGES AND PROGRAMMING, PT II, PROCEEDINGS, 2009, 5556 : 297 - +
  • [10] The Computational Complexity of Nash Equilibria in Concisely Represented Games
    Schoenebeck, Grant R.
    Vadhan, Salil
    ACM TRANSACTIONS ON COMPUTATION THEORY, 2012, 4 (02)
12345