Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games

Abstract

We study the randomized query complexity of approximate Nash equilibria (ANE) in large games. We prove that, for some constant $\hat{I}\mu >0$, any randomized oracle algorithm that computes an $\hat{I}\mu$-ANE in a binary-action, $n$-player game must make $2^{\hat{I}\text{c◯}(n/\log n)}$ payoff queries. For the stronger solution concept of well-supported Nash equilibria (WSNE), Babichenko previously gave an exponential $2^{\hat{I}\text{c◯}(n)}$ lower bound for the randomized query complexity of $\hat{I}\mu$-WSNE, for some constant $\hat{I}\mu >0$; the same lower bound was shown to hold for $\hat{I}\mu$-ANE, but only when $\hat{I}\mu =O(1/n)$. Our result answers an open problem posed by Hart and Nisan and Babichenko and is very close to the trivial upper bound of $2^n$. Our proof relies on a generic reduction from the problem of finding an $\hat{I}\mu$-WSNE to the problem of finding an $\hat{I}\mu /(4\hat{I}\pm )$-ANE, in large games with $\hat{I}\pm$ actions, which might be of independent interest.

10 pages