Inapproximability of NP-Complete Variants of Nash Equilibrium

DOI10.1007/978-3-642-22935-0_2zbMATH Open1343.68089arXiv1104.3760OpenAlexW1828524803MaRDI QIDQ3088077FDOQ3088077

Authors: Per Austrin, Mark Braverman, Eden Chlamtac 

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Abstract: In recent work of Hazan and Krauthgamer (SICOMP 2011), it was shown that finding an $eps$-approximate Nash equilibrium with near-optimal value in a two-player game is as hard as finding a hidden clique of size $O(logn)$ in the random graph $G(n,1/2)$. This raises the question of whether a similar intractability holds for approximate Nash equilibrium without such constraints. We give evidence that the constraint of near-optimal value makes the problem distinctly harder: a simple algorithm finds an optimal 1/2-approximate equilibrium, while finding strictly better than 1/2-approximate equilibria is as hard as the Hidden Clique problem. This is in contrast to the unconstrained problem where more sophisticated algorithms, achieving better approximations, are known. Unlike general Nash equilibrium, which is in PPAD, optimal (maximum value) Nash equilibrium is NP-hard. We proceed to show that optimal Nash equilibrium is just one of several known NP-hard problems related to Nash equilibrium, all of which have approximate variants which are as hard as finding a planted clique. In particular, we show this for approximate variants of the following problems: finding a Nash equilibrium with value greater than $eta$ (for any $eta>0$, even when the best Nash equilibrium has value $1-eta$), finding a second Nash equilibrium, and finding a Nash equilibrium with small support. Finally, we consider the complexity of approximate pure Bayes Nash equilibria in two-player games. Here we show that for general Bayesian games the problem is NP-hard. For the special case where the distribution over types is uniform, we give a quasi-polynomial time algorithm matched by a hardness result based on the Hidden Clique problem.

Full work available at URL: https://arxiv.org/abs/1104.3760

Recommendations

• Inapproximability of NP-complete variants of Nash equilibrium
• Inapproximability of Nash equilibrium
• Inapproximability of Nash equilibrium
• Inapproximability results for approximate Nash equilibria
• Inapproximability results for constrained approximate Nash equilibria
• On the complexity of approximating a Nash equilibrium
• scientific article; zbMATH DE number 6783488
• Complexity of pure-strategy Nash equilibria in non-cooperative games
• On the Complexity of Nash Equilibria and Other Fixed Points
• The Computational Complexity of Nash Equilibria in Concisely Represented Games

Mathematics Subject Classification ID

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

Cites Work

• An optimization approach for approximate Nash equilibria
• Title not available (Why is that?)
• Game theory
• New complexity results about Nash equilibria
• On the complexity of the parity argument and other inefficient proofs of existence
• A note on approximate Nash equilibria
• Settling the complexity of computing two-player Nash equilibria
• New algorithms for approximate Nash equilibria in bimatrix games
• How Hard Is It to Approximate the Best Nash Equilibrium?
• A new approach to the planted clique problem
• Random Tensors and Planted Cliques
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
• Inapproximability of NP-Complete Variants of Nash Equilibrium
• Nash and correlated equilibria: Some complexity considerations
• Small Clique Detection and Approximate Nash Equilibria

Cited In (11)

• \(\mathcal{NP}\)-hardness of pure Nash equilibrium in scheduling and network design games
• Title not available (Why is that?)
• How hard is it to approximate the best Nash equilibrium?
• Inapproximability of Nash equilibrium
• Inapproximability of NP-complete variants of Nash equilibrium
• Inapproximability of Nash equilibrium
• 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
• How Hard Is It to Approximate the Best Nash Equilibrium?
• Inapproximability of NP-Complete Variants of Nash Equilibrium
• Small Clique Detection and Approximate Nash Equilibria

This page was built for publication: Inapproximability of NP-Complete Variants of Nash Equilibrium

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