Journal
INTERNATIONAL JOURNAL OF GAME THEORY
Volume 37, Issue 1, Pages 93-113Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s00182-007-0095-0
Keywords
computational complexity; game theory; evolutionarily stable strategies; evolutionary biology; nash equilibria
Ask authors/readers for more resources
The concept of evolutionarily stable strategies ( ESS) has been central to applications of game theory in evolutionary biology, and it has also had an influence on the modern development of game theory. A regular ESS is an important refinement the ESS concept. Although there is a substantial literature on computing evolutionarily stable strategies, the precise computational complexity of determining the existence of an ESS in a symmetric two- player strategic form game has remained open, though it has been speculated that the problem is NP-hard. In this paper we show that determining the existence of an ESS is both NP-hard and coNP- hard, and that the problem is contained in Sigma(p)(2), the second level of the polynomial time hierarchy. We also show that determining the existence of a regular ESS is indeed NP-complete. Our upper bounds also yield algorithms for computing a ( regular) ESS, if one exists, with the same complexities.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available