Inapproximability of NP-Complete Variants of Nash Equilibrium

DOI10.1007/978-3-642-22935-0_2MaRDI QIDQ3088077zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(12)

• Inapproximability of Nash equilibrium
• How Hard Is It to Approximate the Best Nash Equilibrium?
• Inapproximability of NP-Complete Variants of Nash Equilibrium
• scientific article; zbMATH DE number 5942357 (Why is no real title available?)
• Inapproximability of NP-complete variants of Nash equilibrium
• Small Clique Detection and Approximate Nash Equilibria
• \(\mathcal{NP}\)-hardness of pure Nash equilibrium in scheduling and network design games
• Inapproximability of Nash equilibrium
• How hard is it to approximate the best 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
• A polynomial-time algorithm for 1/3-approximate Nash equilibria in bimatrix games

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)