The computational complexity of evolutionarily stable strategies

K. Etessami, A. Lochbihler

Research output: Contribution to journalArticlepeer-review

Abstract

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 Σ2p, 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.

Original languageEnglish
Pages (from-to)93-113
Number of pages21
JournalInternational Journal of Game Theory
Volume37
Issue number1
DOIs
Publication statusPublished - 2008

Keywords

  • Computational complexity
  • Evolutionarily stable strategies
  • Game theory
  • Evolutionary biology
  • Nash equilibria

Fingerprint

Dive into the research topics of 'The computational complexity of evolutionarily stable strategies'. Together they form a unique fingerprint.

Cite this