Query Complexity of Approximate Nash Equilibria

Abstract

We study the query complexity of approximate notions of Nash equilibrium in games with a large number of players n . Our main result states that for n -player binary-action games and for constant ε, the query complexity of an ε-well-supported Nash equilibrium is exponential in n . As a consequence of this result, we get an exponential lower bound on the rate of convergence of adaptive dynamics to approximate Nash equilibria.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 46 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.