Inapproximability results for constrained approximate Nash equilibria

We study the problem of finding approximate Nash equilibria that satisfy certain conditions, such as providing good social welfare. In particular, we study the problem ϵ-NE δ-SW: find an ϵ-approximate Nash equilibrium (ϵ-NE) that is within δ of the best social welfare achievable by an ϵ-NE. Our main result is that, if the exponential-time hypothesis (ETH) is true, then solving (18−O(δ))-NE O(δ)-SW for an n×n bimatrix game requires nΩ˜(log⁡n) time. Building on this result, we show similar conditional running time lower bounds for a number of other decision problems for ϵ-NE, where, for example, the payoffs or supports of players are constrained. We show quasi-polynomial lower bounds for these problems assuming ETH, where these lower bounds apply to ϵ-Nash equilibria for all ϵ<18. The hardness of these other decision problems has so far only been studied in the context of exact equilibria.