Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 6845))
Included in the following conference series:
1652Accesses
Abstract
In recent work of Hazan and Krauthgamer (SICOMP 2011), it was shown that finding anε-approximate Nash equilibrium with near-optimal value in a two-player game is as hard as finding a hidden clique of sizeO(logn) in the random graph\(G(n,\frac12)\). 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\(\frac{1}{2}\)-approximate equilibrium, while finding strictly better than\(\frac12\)-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η (for anyη > 0, even when the best Nash equilibrium has value 1 − η), 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 version available as arXiv:1104.3760. Research supported by NSERC. This work was done while the third author was at the University of Toronto.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Austrin, P., Braverman, M., Chlamtac, E.: Inapproximability of NP-Complete Variants of Nash Equilibrium. arXiv:1104.3760 (2011)
Alon, N., Krivelevich, M., Sudakov, B.: Finding a large hidden clique in a random graph. Rand. Struct. Algos. 13(3-4), 457–466 (1998)
Bosse, H., Byrka, J., Markakis, E.: New algorithms for approximate nash equilibria in bimatrix games. Theor. Comput. Sci. 411(1), 164–173 (2010)
Brubaker, S.C., Vempala, S.S.: Random tensors and planted cliques. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol. 5687, pp. 406–419. Springer, Heidelberg (2009)
Chen, X., Deng, X., Teng, S.-H.: Settling the complexity of computing two-player nash equilibria. J. ACM 56(3) (2009)
Conitzer, V., Sandholm, T.: New complexity results about Nash equilibria. Games and Economic Behavior 63(2), 621–641 (2008)
Daskalakis, C., Mehta, A., Papadimitriou, C.H.: Progress in approximate nash equilibria. In: ACM Conference on Electronic Commerce, pp. 355–358 (2007)
Daskalakis, C., Mehta, A., Papadimitriou, C.H.: A note on approximate Nash equilibria. Theor. Comput. Sci. 410(17), 1581–1588 (2009)
Feige, U., Krauthgamer, R.: The probable value of the lovász–schrijver relaxations for maximum independent set. SIAM J. Comput. 32(2), 345–370 (2003)
Frieze, A.M., Kannan, R.: A new approach to the planted clique problem. In: FSTTCS, pp. 187–198 (2008)
Feder, T., Nazerzadeh, H., Saberi, A.: Approximating Nash equilibria using small-support strategies. In: ACM Conference on Electronic Commerce, pp. 352–354 (2007)
Fudenberg, D., Tirole, J.: Game Theory. MIT Press, Cambridge (1991)
Gilboa, I., Zemel, E.: Nash and correlated equilibria: Some complexity considerations. Games and Econ. Behavior 1(1), 80–93 (1989)
Hazan, E., Krauthgamer, R.: How Hard Is It to Approximate the Best Nash Equilibrium?. SIAM J. Comput. 40(1), 79–91 (2011)
Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: ACM Conference on Electronic Commerce, pp. 36–41 (2003)
Minder, L., Vilenchik, D.: Small clique detection and approximate nash equilibria. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol. 5687, pp. 673–685. Springer, Heidelberg (2009)
Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comp. Sys. Sci. 48(3), 498–532 (1994)
Tsaknakis, H., Spirakis, P.G.: An optimization approach for approximate nash equilibria. Internet Mathematics 5(4), 365–382 (2008)
Author information
Authors and Affiliations
University of Toronto, Toronto, Canada
Per Austrin & Mark Braverman
Tel Aviv University, Tel Aviv, Israel
Eden Chlamtáč
- Per Austrin
You can also search for this author inPubMed Google Scholar
- Mark Braverman
You can also search for this author inPubMed Google Scholar
- Eden Chlamtáč
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
Department of Computer Science, University of Liverpool, Ashton Building, L69 3BX, Liverpool, UK
Leslie Ann Goldberg
Department of Computer Science, University of Kiel, Olshausenstr. 40, 24098, Kiel, Germany
Klaus Jansen
Tepper School of Business, Carnegie Mellon University, 5000 Forbes Avenue, 15213, Pittsburgh, PA, USA
R. Ravi
Centre Universitaire d’Informatique,, University of Geneva,, Battelle A 7 route de Drize, 1227, Carouge, Switzerland
José D. P. Rolim
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Austrin, P., Braverman, M., Chlamtáč, E. (2011). Inapproximability of NP-Complete Variants of Nash Equilibrium. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2011 2011. Lecture Notes in Computer Science, vol 6845. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22935-0_2
Download citation
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-642-22934-3
Online ISBN:978-3-642-22935-0
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative