Journal articles or Book chapters PUBLISHED

1. Conitzer, V, The exact computational complexity of evolutionarily stable strategies, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8289 LNCS (December, 2013), pp. 96-108, Springer Berlin Heidelberg [doi].
   (last updated on 2024/04/18)

   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 -complete. © 2013 Springer-Verlag.