We study the deterministic and randomized query complexity of finding approximate equilibria in bimatrix games. We show that the deterministic query complexity of finding an $\epsilon$-Nash equilibrium when $\epsilon < \frac{ 1}{ 2}$ is $\Omega(k^2)$, even in zero-one constant-sum games. In combination with previous results \cite{ FGGS13}, this provides a complete characterization of the deterministic query complexity of approximate Nash equilibria. We also study randomized querying algorithms. We give a randomized algorithm for finding a $(\frac{ 3 - \sqrt{ 5}}{ 2} + \epsilon)$-Nash equilibrium using $O(\frac{ k \cdot \log k}{ \epsilon^2})$ payoff queries, which shows that the $\frac{ 1}{ 2}$ barrier for deterministic algorithms can be broken by randomization. For well-supported Nash equilibria (WSNE), we first give a randomized algorithm for finding an $\epsilon$-WSNE of a zero-sum bimatrix game using $O(\frac{ k \cdot \log k}{ \epsilon^4})$ payoff queries, and we then use this to obtain a randomized algorithm for finding a $(\frac{ 2}{ 3} + \epsilon)$-WSNE in a general bimatrix game using $O(\frac{ k \cdot \log k}{ \epsilon^4})$ payoff queries. Finally, we initiate the study of lower bounds against randomized algorithms in the context of bimatrix games, by showing that randomized algorithms require $\Omega(k^2)$ payoff queries in order to find a $\frac{ 1}{ 6k}$-Nash equilibrium, even in zero-one constant-sum games. In particular, this rules out query-efficient randomized algorithms for finding exact Nash equilibria.
Categories: cs.GT