The exact computational complexity of evolutionarily stable strategies

Published

Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Conitzer, V

Published Date

  • December 1, 2013

Published In

Volume / Issue

  • 8289 LNCS /

Start / End Page

  • 96 - 108

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

Digital Object Identifier (DOI)

  • 10.1007/978-3-642-45046-4_9

Citation Source

  • Scopus