The computational complexity of evolutionarily stable strategies

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.