Inapproximability of NP-Complete Variants of Nash Equilibrium
From MaRDI portal
Publication:3088077
DOI10.1007/978-3-642-22935-0_2zbMath1343.68089arXiv1104.3760OpenAlexW1828524803MaRDI QIDQ3088077
Per Austrin, Eden Chlamtáč, Mark Braverman
Publication date: 17 August 2011
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1104.3760
Noncooperative games (91A10) 2-person games (91A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (3)
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 ⋮ Inapproximability of NP-Complete Variants of Nash Equilibrium
Cites Work
- New complexity results about Nash equilibria
- A note on approximate Nash equilibria
- New algorithms for approximate Nash equilibria in bimatrix games
- Nash and correlated equilibria: Some complexity considerations
- On the complexity of the parity argument and other inefficient proofs of existence
- How Hard Is It to Approximate the Best Nash Equilibrium?
- Inapproximability of NP-Complete Variants of Nash Equilibrium
- Settling the complexity of computing two-player Nash equilibria
- An Optimization Approach for Approximate Nash Equilibria
- Random Tensors and Planted Cliques
- Small Clique Detection and Approximate Nash Equilibria
- The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Inapproximability of NP-Complete Variants of Nash Equilibrium
