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 epsilon-NE delta-SW: find an epsilon-approximate Nash equilibrium (epsilon-NE) that is within delta of the best social welfare achievable by an epsilon-NE. Our main result is that, delta the exponential-time hypothesis (ETH) is true, then solving (1/8-O(delta))-NE O(delta)-SW for an n x n bimatrix game requires n((Omega) over tilde 'log) (n') time. Building on this result, we show similar conditional running time lower bounds for a number of other decision problems for epsilon-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 epsilon-Nash equilibria for all epsilon<1/8. The hardness of these other decision problems has so far only been studied in the context of exact equilibria. (C) 2018 Elsevier Inc. All rights reserved.