The complexity of computing a Nash equilibrium

By Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou. 2006

1,530 citations recorded by the source corpus.

Subfields: Economics and Econometrics, Management Science and Operations Research, Game & Decision Theory

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

In Game & Decision Theory

Citations in the corpus

OpenSpiel: A Framework for Reinforcement Learning in Games (2019, background): “, the agents Rock, Paper, and Scissors in the eponymous game), unlike the Elo rating system [4]; an additional practical benefit is that it is also tractable to compute in general games, unlike ranking systems relying on Nash equilibria [19].”
The Mechanics of n-Player Differentiable Games (2018, background): “Finding equilibria can be reformulated as a nonlinear complementarity problem, but these are ‘hopelessly impractical to solve’ in general (Shoham & Leyton-Brown, 2008) because the problem is PPAD hard (Daskalakis et al., 2009).”
From Duels to Battlefields: Computing Equilibria of Blotto and Other Games (2016, background): “Indeed, the conclusions to date have been largely negative: computing a Nash equilibrium of a normal-form game is known to be PPAD-complete [15, 21], even for two-player games [11].”
Stable Opponent Shaping in Differentiable Games (2018, background): “Convergence has been studied in a number of restricted game classes, with various algorithms improving on simultaneous gradient descent: policy prediction in two-player two-action bimatrix games (Zhang & Lesser, 2010); WoLF in two-player two-action games (Bowling & Veloso, 2001); AWESOME in repeated”
Actor-Critic Policy Optimization in Partially Observable Multiagent Environments (2018, background): “The guarantees that Nash equilibrium provides are less clear for the (n > 2)-player case, and finding one is hard [20].”
Differentiable Game Mechanics (2019, background): “Finding Nash equilibria can be reformulated as a nonlinear complementarity problem, but these are ‘hopelessly impractical to solve’ in general (Shoham and Leyton-Brown, 2008) because the problem is PPAD hard (Daskalakis et al., 2009).”
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium (2020, background): “The recent work in Jia et al. (2019) studies turn-based zero-sum Markov games, where the transition model is assumed to be embedded in some d-dimensional feature space, extending the MDP model proposed by Yang and Wang (2019b).”
On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract) (2010, methodology): “The Nash problem has been investigated intensely recently in the TCS community, and last year in a breakthrough set of papers [10, 7, 8] it was shown that computing an (exact) Nash equilibrium for 2 players is PPAD-complete, and so is the problem of computing a (cid:2) -Nash Equilibrium ( (cid:2) -N”
α-Rank: Multi-Agent Evaluation by Evolution (2019, methodology): “This yields a major computational advantage, in stark contrast to conducting rankings by solving for Nash (which is PPAD-complete for general-sum games [22], which our meta-games may be).”
Decentralized charging control for large populations of plug-in electric vehicles (2010, background): “Such problems are, however, generally computationally intractable for large population size N , see [11] and the references therein.”
Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability (2021, background): “Since the matrix U t is not zero-sum, a Nash equilibrium may not be efﬁciently computable [Dey, 2019; Daskalakis et al., 2009]; however, a CCE is guaranteed to exist and is easily computed by solving the above linear feasiblity problem.”
Core Challenges of Social Robot Navigation: A Survey (2021, background): “…(in the best case, social navigation is related to n-body classical physical simulation, which requires supercomputers [183]), game-theoretic approaches [44, 67], braid theoretic [150], or joint probabilistic inference [227]—is inherently non-convex (whether some objective function might reduce…”
Settling the Complexity of Two-Player Nash Equilibrium (2006, methodology): “Since xC [v] = x[v] < x[v1]+x[v2], we have x[v] = xC [v] > xC [v]− = min(x[v1]+x[v2],xC [v])− and the proposition is proven.”
The State of Solving Large Incomplete-Information Games, and Application to Poker (2010, background): “The problem of finding a Nash equilibrium in two-player general-sum games is PPAD-complete even in normal form games with complete information (Daskalakis, Goldberg, and Papadimitriou 2008; Chen and Deng 2006), suggesting that there likely is no polynomial-time algorithm for all instances.”
On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games (2019, neutral): “The classical problem of ﬁnding Nash equilibria in multi-player games has been a focus of intense research in computer science, control theory, economics and mathematics (Basar and Olsder, 1998; Nisan et al., 2007; C. Daskalakis, 2009).”