# The Exact Computational Complexity of Evolutionarily Stable Strategies

arXiv: https://arxiv.org/abs/1805.02226 · HTML: https://mlsanity.com/paper/1805.02226/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 May 2018.

## Built on by (most cited first, 3 of 3)

- [Computing Evolutionarily Stable Strategies in Multiplayer Games](https://mlsanity.com/paper/2511.20859/) (2025)
- [Computing Evolutionarily Stable Strategies in Imperfect-Information Games](https://mlsanity.com/paper/2512.10279/) (2025)
- [Evolutionarily Stable Stackelberg Equilibrium](https://mlsanity.com/paper/2603.18385/) (2026)

## Abstract (arXiv)

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 Sigma2P-complete.