Inapproximability results for constrained approximate Nash equilibria

Deligkas, Argyrios, Fearnley, JS and Savani, Rahul ORCID: 0000-0003-1262-7831
(2018) Inapproximability results for constrained approximate Nash equilibria. Information and Computation, 262 (1). 40 - 56.

[img] Text
note.pdf - Accepted Version

Download (470kB)


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 -NE -SW for an bimatrix game requires 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 . The hardness of these other decision problems has so far only been studied in the context of exact equilibria.

Item Type: Article
Uncontrolled Keywords: Approximate Nash equilibrium, Constrained equilibrium, Quasi-polynomial time, Lower bound, Exponential time hypothesis
Depositing User: Symplectic Admin
Date Deposited: 30 May 2018 08:53
Last Modified: 16 Aug 2022 12:11
DOI: 10.1016/j.ic.2018.06.001
Related URLs: