Progress in approximate nash equilibria

Abstract

It is known [5] that an additively ε-approximate Nash equilibrium (with supports of size at most two) can be computed in polynomial time in any 2-player game with ε=.5. It is also known that no approximation better than .5 is possible unless equilibria with support larger than logn are considered, where n is the number of strategies per player. We give a polynomial algorithm for computing an ε-approximate Nash equilibrium in 2-player games with ε ≈ .38; our algorithm computes equilibria with arbitrarily large supports.

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 — 149 citations exist upstream.

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