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. ISSN 0890-5401, 1090-2651

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:	01 Mar 2026 03:27
DOI:	10.1016/j.ic.2018.06.001
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3021907
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.