[etessami08ijgt] | Kousha Etessami, Andreas Lochbihler, The Computational Complexity of Evolutionarily Stable Strategies, International Journal of Game Theory, Vol. 31, (1), pp. 93--113, April 2008.
A preliminary version is available as ECCC tech report TR04-055,
2004. |
Zusammenfassung
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_2^p, 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.
Download
BibTeX
Institutsinterne Autoren