Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat
Cited by 249

The DOI matches its Crossref record.

On the Complexity of Nash Equilibria and Other Fixed Points

Open access
Etessami, Kousha, Yannakakis, Mihalis · 2010 · SIAM Journal on Computing

Abstract

We reexamine what it means to compute Nash equilibria and, more generally, what it means to compute a fixed point of a given Brouwer function, and we investigate the complexity of the associated problems. Specifically, we study the complexity of the following problem: given a finite game, $\Gamma$, with 3 or more players, and given $\epsilon>0$, compute an approximation within $\epsilon$ of some (actual) Nash equilibrium. We show that approximation of an actual Nash equilibrium, even to within any nontrivial constant additive factor $\epsilon<1/2$ in just one desired coordinate, is at least as hard as the long-standing square-root sum problem, as well as a more general arithmetic circuit decision problem that characterizes P-time in a unit-cost model of computation with arbitrary precision rational arithmetic; thus, placing the approximation problem in P, or even NP, would resolve major open problems in the complexity of numerical computation. We show similar results for market equilibria: it is hard to estimate with any nontrivial accuracy the equilibrium prices in an exchange economy with a unique equilibrium, where the economy is given by explicit algebraic formulas for the excess demand functions. We define a class, FIXP, which captures search problems that can be cast as fixed point computation problems for functions represented by algebraic circuits (straight line programs) over basis $\{+,*,-,/,\max,\min\}$ with rational constants. We show that the (exact or approximate) computation of Nash equilibria for 3 or more players is complete for FIXP. The price equilibrium problem for exchange economies with algebraic demand functions is another FIXP-complete problem. We show that the piecewise linear fragment of FIXP equals PPAD. Many other problems in game theory, economics, and probability theory can be cast as fixed point problems for such algebraic functions. We discuss several important such problems: computing the value of Shapley's stochastic games and the simpler games of Condon, extinction probabilities of branching processes, probabilities of stochastic context-free grammars, and termination probabilities of recursive Markov chains. We show that for some of them, the approximation, or even exact computation, problem can be placed in PPAD, while for others, they are at least as hard as the square-root sum and arithmetic circuit decision problems.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1137/080720826

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cited by

See all 249

Metadata

Authors
Etessami, K., & Yannakakis, M.
Venue
SIAM Journal on Computing
Published
2010-01
Volume
39
Issue
6
Pages
2531-2597
ISSN
  • 0097-5397 (ISSN-L)
  • 1095-7111
OpenAlex
W1991624978
Cited by
249
References
0
FWCI
13.92
Type
journal article
Language
en
Open access
green

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: On the Complexity of Nash Equilibria and Other Fixed Points. https://app.cochat.ai/papers/10.1137/080720826
The paper
Etessami, K., & Yannakakis, M. (2010). On the Complexity of Nash Equilibria and Other Fixed Points. SIAM Journal on Computing. https://doi.org/10.1137/080720826

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.