Informatics Report Series



Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Title:The computational complexity of Evolutionarily Stable Strategies
Authors: Kousha Etessami ; Andreas Lochbihler
Date: 2004
Publication Title:Tech Report 055-04, Electronic Colloquium on Computational Complexity
Page Nos:055-04
Game theory has been used for a long time to study phenomena in evolutionary biology, beginning systematically with the seminal work of John Maynard Smith. A central concept in this connection has been the notion of an evolutionarily stable strategy (ESS) in a symmetric two-player strategic form game. A regular ESS is an important refinement of the ESS concept which has also been studied extensively and is further motivated by Harsanyi's result that "almost all" strategic form games contain only regular equilibria. There is a substantial literature on computing evolutionarily stable strategies, yet despite these efforts the precise computational complexity of determining the existence of an ESS in a game has remained elusive, although it has been speculated by some 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 it is contained in Sigma^P_2, the second level of the polynomial time hierarchy. On the other hand, we 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. Our upper bounds combine known criteria for the existence of an ESS based on quadratic forms, together with known results about the complexity of quadratic programming decision problems. Our lower bounds employ, among other things, a classic characterization of maximum clique size via quadratic programming.
Links To Paper
1st Link
2nd Link
Bibtex format
author = { Kousha Etessami and Andreas Lochbihler },
title = {The computational complexity of Evolutionarily Stable Strategies},
year = 2004,
pages = {055-04},
url = {},

Home : Publications : Report 

Please mail <> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh