Abstract
While the computational complexity of many game-theoretic solution concepts, notably Nash equilibrium, has now been settled, the question of determining the exact complexity of computing an evolutionarily stable strategy has resisted solution since attention was drawn to it in 2004. In this paper, I settle this question by proving that deciding the existence of an evolutionarily stable strategy is \(\Sigma_2^P\)-complete.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Andersen, G., Conitzer, V.: Fast equilibrium computation for infinitely repeated games. In: Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, Bellevue, WA, USA, pp. 53–59 (2013)
Borgs, C., Chayes, J., Immorlica, N., Kalai, A.T., Mirrokni, V., Papadimitriou, C.: The myth of the Folk Theorem. Games and Economic Behavior 70(1), 34–43 (2010)
Chen, X., Deng, X., Teng, S.-H.: Settling the complexity of computing two-player Nash equilibria. Journal of the ACM 56(3) (2009)
Conitzer, V., Korzhyk, D.: Commitment to correlated strategies. In: Proceedings of the National Conference on Artificial Intelligence (AAAI), San Francisco, CA, USA, pp. 632–637 (2011)
Conitzer, V., Sandholm, T.: Computing the optimal strategy to commit to. In: Proceedings of the ACM Conference on Electronic Commerce (EC), Ann Arbor, MI, USA, pp. 82–90 (2006)
Conitzer, V., Sandholm, T.: New complexity results about Nash equilibria. Games and Economic Behavior 63(2), 621–641 (2008)
Daskalakis, C., Goldberg, P., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM Journal on Computing 39(1), 195–259 (2009)
Etessami, K., Lochbihler, A.: The computational complexity of evolutionarily stable strategies. International Journal of Game Theory 37(1), 93–113 (2004); an earlier version was made available as ECCC tech report TR04-055 (2004)
Etessami, K., Yannakakis, M.: On the complexity of Nash equilibria and other fixed points. SIAM Journal on Computing 39(6), 2531–2597 (2010)
Gilboa, I., Zemel, E.: Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior 1, 80–93 (1989)
Hansen, K.A., Miltersen, P.B., Sørensen, T.B.: The computational complexity of trembling hand perfection and other equilibrium refinements. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds.) SAGT 2010. LNCS, vol. 6386, pp. 198–209. Springer, Heidelberg (2010)
Jiang, A.X., Leyton-Brown, K.: Polynomial-time computation of exact correlated equilibrium in compact games. Games and Economic Behavior (2013)
Ko, K.-I., Lin, C.-L.: On the complexity of min-max optimization problems and their approximation. In: Du, D.-Z., Pardalos, P.M. (eds.) Minimax and Applications, pp. 219–239. Kluwer Academic Publishers, Boston (1995)
Kontogiannis, S.C., Spirakis, P.G.: Equilibrium points in fear of correlated threats. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol. 5385, pp. 210–221. Springer, Heidelberg (2008)
Lemke, C., Howson, J.: Equilibrium points of bimatrix games. Journal of the Society of Industrial and Applied Mathematics 12, 413–423 (1964)
Littman, M.L., Stone, P.: A polynomial-time Nash equilibrium algorithm for repeated games. Decision Support Systems 39, 55–66 (2005)
Nash, J.: Equilibrium points in n-person games. Proceedings of the National Academy of Sciences 36, 48–49 (1950)
Nisan, N.: A note on the computational hardness of evolutionary stable strategies. Electronic Colloquium on Computational Complexity (ECCC) 13(076) (2006)
Papadimitriou, C.H., Roughgarden, T.: Computing correlated equilibria in multi-player games. Journal of the ACM 55(3) (2008)
Papadimitriou, C.H.: Algorithms, games and the Internet. In: Proceedings of the Annual Symposium on Theory of Computing (STOC), pp. 749–753 (2001)
Price, G., Smith, J.M.: The logic of animal conflict. Nature 246, 15–18 (1973)
Savani, R., von Stengel, B.: Hard-to-solve bimatrix games. Econometrica 74, 397–429 (2006)
Schaefer, M., Umans, C.: Completeness in the polynomial-time hierarchy: A compendium (2008)
Sørensen, T.B.: Computing a proper equilibrium of a bimatrix game. In: Proceedings of the ACM Conference on Electronic Commerce (EC), Valencia, Spain, pp. 916–928 (2012)
Suri, S.: Computational evolutionary game theory. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.) Algorithmic Game Theory, vol. 29. Cambridge University Press (2007)
von Stengel, B., Zamir, S.: Leadership games with convex strategy sets. Games and Economic Behavior 69, 446–457 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Conitzer, V. (2013). The Exact Computational Complexity of Evolutionarily Stable Strategies. In: Chen, Y., Immorlica, N. (eds) Web and Internet Economics. WINE 2013. Lecture Notes in Computer Science, vol 8289. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45046-4_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-45046-4_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45045-7
Online ISBN: 978-3-642-45046-4
eBook Packages: Computer ScienceComputer Science (R0)