Inapproximability results for constrained approximate Nash equilibria

DOI10.1016/j.ic.2018.06.001zbMath1400.68086OpenAlexW2806555090WikidataQ129723213 ScholiaQ129723213MaRDI QIDQ1784945

Rahul Savani, John Fearnley, Argyrios Deligkas

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) Noncooperative games (91A10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

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 existential theory of the reals ⋮ Approximating the existential theory of the reals

Cites Work

• Unnamed Item
• Approximate well-supported Nash equilibria below two-thirds
• New complexity results about Nash equilibria
• Well supported approximate equilibria in bimatrix games
• A note on approximate Nash equilibria
• New algorithms for approximate Nash equilibria in bimatrix games
• Nash and correlated equilibria: Some complexity considerations
• On sparse approximations to randomized strategies and convex combinations
• Non-cooperative games
• Can Almost Everybody be Almost Happy?
• Distributed Methods for Computing Approximate Equilibria
• Inapproximability Results for Approximate Nash Equilibria
• How Hard Is It to Approximate the Best Nash Equilibrium?
• ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria
• An Optimization Approach for Approximate Nash Equilibria
• Two-query PCP with subconstant error
• A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
• Existential-R-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games
• On oblivious PTAS's for nash equilibrium
• The Complexity of Computing a Nash Equilibrium
• Approximating the best Nash Equilibrium in n^{o(log n)}-time breaks the Exponential Time Hypothesis
• The PCP theorem by gap amplification

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