The complexity of computing a Nash equilibrium

By Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou. CACM, 2009

450 citations recorded by the source corpus.

Subfields: Economics and Econometrics, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/469133e860a5c46d524e83a1418420d138f97aea

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Economics and Econometrics

In Management Science and Operations Research

Citations in the corpus

Superhuman AI for multiplayer poker (2019, background): “No polynomial-time algorithm is known for finding a Nash equilibrium in two-player non-zero-sum games, and the existence of one would have sweeping surprising implications in computational complexity theory ( 13 , 14 ).”
Time and Space: Why Imperfect Information Games are Hard (2018, background): “A Nash equilibrium is also hard to compute (or even approximately compute) if the game has more than two players [21], is not constant-sum [19], or is not perfect recall [50].”
Settling the complexity of computing two-player Nash equilibria (2007, methodology): “Technically, we use the proof framework developed by Daskalakis, Goldberg, and Papadimitriou [Goldberg and Papadimitriou 2006; Daskalakis et al. 2006a] in their work for characterizing the complexity of four-player Nash equilibria.”
Learning in Multi-agent Systems with Sparse Interactions by Knowledge Transfer and Game Abstraction (2015, unknown): “, computing a Nash equilibrium is a PPAD-hard problem [3]).”
Prosocial learning agents solve generalized Stag Hunts better than selfish ones (2017, background): “me theoretic issues we discuss in this paper. 2Note that computing a Nash equilibrium is in general computationally difﬁcult and so we cannot guarantee convergence for all games in a reasonable time (Daskalakis et al., 2009). 2 strategy 2 player games as long as any 2 2 sub-game is a Stag Hunt. This”
Computer-Aided Verification for Mechanism Design (2015, methodology): “Finally, as an intermediate step in our formalization, we provide the first formal verification of incentive compatibility for the celebrated Vickrey-Clarke-Groves mechanism.”
The computational complexity of linear optics (2010, background): “ there is always at least one valid solution, and the problem is to ﬁnd a solution: a famous example is ﬁnding a Nash equilibrium of a game, the problem shown to be PPAD-complete by Daskalakis et al. [17]. More formally, a search problem Ris a collection of nonempty sets (Bx)x∈{0,1}∗, one for each i”
The complexity of constrained min-max optimization (2020, background): “The complexity class PPAD is of particular importance, since it contains lots of fundamental problems in Game Theory, Economics, Topology and several other fields [11, 12].”