Inapproximability results for approximate Nash equilibria

DOI10.1007/978-3-662-54110-4_3MaRDI QIDQ2959816zbMATH OpenOpenAlexFDO

Authors Argyrios Deligkas, John Fearnley, Rahul Savani

Publication date 10 February 2017

Published in Web and Internet Economics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.03574

zbMATH Keywords

approximate Nash equilibriacompletenesshardnessrandomized exponential-time hypothesissocial welfare

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05) Welfare economics (91B15)

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 $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, if the exponential-time hypothesis (ETH) is true, then solving $left(frac18-mathrmO(delta)ight)$-NE $mathrmO(delta)$-SW for an $nimesn$ bimatrix game requires $n^{mathrmwidetildeOmega(logn)}$ time. Building on this result, we show similar conditional running time lower bounds on a number of decision problems for approximate Nash equilibria that do not involve social welfare, including maximizing or minimizing a certain player's payoff, or finding approximate equilibria contained in a given pair of supports. We show quasi-polynomial lower bounds for these problems assuming that ETH holds, where these lower bounds apply to $epsilon$-Nash equilibria for all $epsilon<frac18$. The hardness of these other decision problems has so far only been studied in the context of exact equilibria.

Recommendations

• Inapproximability results for constrained approximate Nash equilibria
• Approximating the best Nash equilibrium in \(n^{o(\log n)}\)-time breaks the exponential time hypothesis
• Inapproximability of Nash equilibrium
• Inapproximability of Nash equilibrium
• How Hard Is It to Approximate the Best Nash Equilibrium?

Cites work

• A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
• A note on approximate Nash equilibria
• An optimization approach for approximate Nash equilibria
• Approximating the best Nash equilibrium in \(n^{o(\log n)}\)-time breaks the exponential time hypothesis
• Distributed Methods for Computing Approximate Equilibria
• ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
• How Hard Is It to Approximate the Best Nash Equilibrium?
• Inapproximability of NP-complete variants of Nash equilibrium
• Nash and correlated equilibria: Some complexity considerations
• New algorithms for approximate Nash equilibria in bimatrix games
• New complexity results about Nash equilibria
• Non-cooperative games
• The complexity of computing a Nash equilibrium
• Well supported approximate equilibria in bimatrix games

Cited in

(8)

• Invariance and randomness in the Nash program for coalitional games
• Inapproximability results for constrained approximate Nash equilibria
• Inefficiency of the Nash equilibrium for selfish machine covering on two hierarchical uniform machines
• Inapproximability of NP-Complete Variants of Nash Equilibrium
• Detecting communities is hard (and counting them is even harder)
• Approximating the best Nash equilibrium in \(n^{o(\log n)}\)-time breaks the exponential time hypothesis
• Public Bayesian persuasion: being almost optimal and almost persuasive
• Approximations of Nash equilibria

This page was built for publication: Inapproximability results for approximate Nash equilibria

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2959816)