The complexity of computing a Nash equilibrium.

Daskalakis, C., Goldberg, & Papadimitriou, C. H. (2009). The complexity of computing a Nash equilibrium. Communications of the ACM, 52(2), 89-97.

Type

Journal article

Intellectual base

Primary research

Year

2009

Link

https://doi.org/10.1145/1461928.1461951verified

Cited from

mathematics

Cited by

1 citation across 1 artifact.

Each citation links to the sentence it supports in the citing article.

Primes

• Game-Theoretic Strategy
  • Not always tractable. Computing a Nash equilibrium is PPAD-complete for general two-player games

    This source(The originating result establishing that computing a Nash equilibrium of a general `n`-player game in normal form is PPAD-complete — placing equilibrium computation in a complexity class that is widely believed not to admit polynomial-time algorithms. The Daskalakis-Goldberg-Papadimitriou result is the foundational theorem of algorithmic game theory and forces a methodological reckoning between the equilibrium concept and the computational capacities of any actual or modelled player.)

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:7ccbb39a306d · see in the full table