Inapproximability results for constrained approximate Nash equilibria
DOI10.1016/J.IC.2018.06.001zbMATH Open1400.68086OpenAlexW2806555090WikidataQ129723213 ScholiaQ129723213MaRDI QIDQ1784945FDOQ1784945
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
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
lower boundexponential time hypothesisapproximate Nash equilibriumconstrained equilibriumquasi-polynomial time
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Noncooperative games (91A10)
Cites Work
- Non-cooperative games
- An optimization approach for approximate Nash equilibria
- The complexity of computing a Nash equilibrium
- New complexity results about Nash equilibria
- A note on approximate Nash equilibria
- New algorithms for approximate Nash equilibria in bimatrix games
- Well supported approximate equilibria in bimatrix games
- How Hard Is It to Approximate the Best Nash Equilibrium?
- On sparse approximations to randomized strategies and convex combinations
- Inapproximability of NP-complete variants of Nash equilibrium
- Nash and correlated equilibria: Some complexity considerations
- On oblivious PTAS's for nash equilibrium
- The PCP theorem by gap amplification
- Two-query PCP with subconstant error
- Inapproximability results for approximate Nash equilibria
- Distributed Methods for Computing Approximate Equilibria
- A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
- Can almost everybody be almost happy?
- ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
- \(\exists\mathbb{R}\)-complete decision problems about symmetric Nash equilibria in symmetric multi-player games
- Approximating the best Nash equilibrium in \(n^{o(\log n)}\)-time breaks the exponential time hypothesis
Cited In (9)
- 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
- On tightness of the Tsaknakis-Spirakis algorithm for approximate Nash equilibrium
- 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)
