Inapproximability results for constrained approximate Nash equilibria

DOI10.1016/J.IC.2018.06.001MaRDI QIDQ1784945zbMATH OpenOpenAlexWikidataFDO

Authors Argyrios Deligkas, John Fearnley, Rahul Savani

Publication date 27 September 2018

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2018.06.001

zbMATH Keywords

lower boundexponential time hypothesisapproximate Nash equilibriumconstrained equilibriumquasi-polynomial time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Noncooperative games (91A10)

Recommendations

• Inapproximability results for approximate Nash equilibria
• Approximating the best Nash equilibrium in \(n^{o(\log n)}\)-time breaks the exponential time hypothesis
• Inapproximability of Nash equilibrium
• Computing constrained approximate equilibria in polymatrix games
• Inapproximability of 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
• Can almost everybody be almost happy?
• 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
• Inapproximability results for approximate Nash equilibria
• 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
• On oblivious PTAS's for nash equilibrium
• On sparse approximations to randomized strategies and convex combinations
• The PCP theorem by gap amplification
• The complexity of computing a Nash equilibrium
• Two-query PCP with subconstant error
• Well supported approximate equilibria in bimatrix games
• \(\exists\mathbb{R}\)-complete decision problems about symmetric Nash equilibria in symmetric multi-player games

Cited in

(8)

• Inapproximability results for approximate Nash equilibria
• A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
• A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
• Approximating the best Nash equilibrium in \(n^{o(\log n)}\)-time breaks the exponential time hypothesis
• Inapproximability of NP-Complete Variants of Nash Equilibrium
• Approximating the existential theory of the reals
• Computational complexity of decision problems about Nash equilibria in win-lose multi-player games
• Approximating the existential theory of the reals

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

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