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

Abstract

In this paper we present a generic reduction from the problem of finding an \epsilon-well-supported Nash equilibrium (WSNE) to that of finding an \Theta(\epsilon)-approximate Nash equilibrium (ANE), in large games with n players and a bounded number of strategies for each player.
Our reduction complements the existing literature on relations between WSNE and ANE, and can be applied to extend hardness results on WSNE to similar results on ANE.
This allows one to focus on WSNE first, which is in general easier to analyze and control in hardness constructions.

As an application we prove a 2^{\Omega(n/\log n)} lower bound on the randomized query complexity of finding an \epsilon-ANE in binary-action n-player games, for some constant \epsilon>0.
This answers an open problem posed by Hart and Nisan and Babichenko, and is very close to the trivial upper bound of 2^n.
Previously for WSNE, Babichenko showed a 2^{\Omega(n)} lower bound on the randomized query complexity of finding an \epsilon-WSNE for some constant epsilon>0.
Our result follows directly from combining Babichenko's result and our new reduction from WSNE to ANE.