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 $\epsilon$, the query complexity of an $\epsilon$-well-supported Nash equilibrium is exponential in $n$. One of the consequences of this result is an exponential lower bound on the rate of convergence of adaptive dynamics to approxiamte Nash equilibrium.

References in corpus (4)

• The Query Complexity of Correlated Equilibria
• Query Complexity of Correlated Equilibrium
• Computational Complexity of Approximate Nash Equilibrium in Large Games
• Learning Equilibria of Games via Payoff Queries

Cited by in corpus (3)

• Computational Complexity of Approximate Nash Equilibrium in Large Games
• Learning Equilibria of Games via Payoff Queries
• Approximate Nash Equilibria via Sampling