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.
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.)
- Not always tractable. Computing a Nash equilibrium is PPAD-complete for general two-player games
Verification¶
Does it exist? Not checked yet. This entry carries no identifier to resolve. It was extracted from the citation as written in the article, normalized, and deduplicated against the rest of the registry.
Does it back the claim? Not recorded. The single citation of this work carries no recorded support check.
Was it audited? Yes. A second, independent pass read the citation against the article text and recorded a verdict.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:7ccbb39a306d · see in the full table