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). pp. 40-56.

Text note.pdf - Author Accepted Manuscript Download (470kB)

Abstract

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:	19 Jan 2023 01:33
DOI:	10.1016/j.ic.2018.06.001
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3021907