Inapproximability Results for Approximate Nash Equilibria

DOI10.1007/978-3-662-54110-4_3zbMath1404.91004arXiv1608.03574OpenAlexW2509191640MaRDI QIDQ2959816

Rahul Savani, Argyrios Deligkas, John Fearnley

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

completenesshardnesssocial welfareapproximate Nash equilibriarandomized exponential-time hypothesis

Mathematics Subject Classification ID

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

Related Items (3)

Public Bayesian persuasion: being almost optimal and almost persuasive ⋮ Inapproximability results for constrained approximate Nash equilibria ⋮ Unnamed Item

Cites Work

• 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
• Non-cooperative games
• Distributed Methods for Computing Approximate 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
• A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
• The Complexity of Computing a Nash Equilibrium
• Approximating the best Nash Equilibrium in n^{o(log n)}-time breaks the Exponential Time Hypothesis
• Unnamed Item

This page was built for publication: Inapproximability Results for Approximate Nash Equilibria