Abstract
The concept of an evolutionarily stable strategy (ESS), introduced by Smith and Price [4], is a refinement of Nash equilibrium in 2-player symmetric games in order to explain counter-intuitive natural phenomena, whose existence is not guaranteed in every game. The problem of deciding whether a game possesses an ESS has been shown to be \(\varSigma _{2}^{P}\)-complete by Conitzer [1] using the preceding important work by Etessami and Lochbihler [2]. The latter, among other results, proved that deciding the existence of ESS is both NP-hard and coNP-hard. In this paper we introduce a reduction robustness notion and we show that deciding the existence of an ESS remains coNP-hard for a wide range of games even if we arbitrarily perturb within some intervals the payoff values of the game under consideration. In contrast, ESS exist almost surely for large games with random and independent payoffs chosen from the same distribution [11].
The work of the second author was partially supported by the ERC Project ALGAME.
For a full version with detailed examples and proofs see https://arxiv.org/abs/1701.08108 [5].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Conitzer, V.: The exact computational complexity of evolutionarily stable strategies. In: Chen, Y., Immorlica, N. (eds.) WINE 2013. LNCS, vol. 8289, pp. 96–108. Springer, Heidelberg (2013). doi:10.1007/978-3-642-45046-4_9
Etessami, K., Lochbihler, A.: The computational complexity of evolutionarily stable strategies. Int. J. Game Theory 37(1), 93–113 (2008). doi:10.1007/s00182-007-0095-0
Lewontin, R.: Evolution and the theory of games. J. Theor. Biol. 1(3), 382–403 (1961)
Smith, J.M., Price, G.R.: The logic of animal conflict. Nature 246(5427), 15–18 (1973)
Melissourgos, T., Spirakis, P.: Existence of evolutionarily stable strategies remains hard to decide for a wide range of payoff values. ArXiv e-prints, January 2017
Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Turán. Can. J. Math. 17, 533–540 (1965)
Nash, J.: Non-cooperative games. Ann. Math. 54(2), 286–295 (1951)
Nisan, N.: A note on the computational hardness of evolutionary stable strategies. Electron. Colloq. Comput. Complex. (ECCC) 13(076) (2006)
Papadimitriou, C., Yannakakis, M.: The complexity of facets (and some facets of complexity). J. Comput. Syst. Sci. 28(2), 244–259 (1984)
Schaffer, M.E.: Evolutionarily stable strategies for a finite population and a variable contest size. J. Theor. Biol. 132(4), 469–478 (1988)
Sergiu Hart, B.W., Rinott, Y.: Evolutionarily stable strategies of random games, and the vertices of random polygons. Ann. Appl. Probab. 18(1), 259–287 (2008)
Smith, J.M.: The theory of games and the evolution of animal conflicts. J. Theor. Biol. 47(1), 209–221 (1974)
Spielman, D.A., Teng, S.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM 52(10), 76–84 (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Melissourgos, T., Spirakis, P. (2017). Existence of Evolutionarily Stable Strategies Remains Hard to Decide for a Wide Range of Payoff Values. In: Fotakis, D., Pagourtzis, A., Paschos, V. (eds) Algorithms and Complexity. CIAC 2017. Lecture Notes in Computer Science(), vol 10236. Springer, Cham. https://doi.org/10.1007/978-3-319-57586-5_35
Download citation
DOI: https://doi.org/10.1007/978-3-319-57586-5_35
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-57585-8
Online ISBN: 978-3-319-57586-5
eBook Packages: Computer ScienceComputer Science (R0)