The computational complexity of evolutionarily stable strategies |
| |
Authors: | K Etessami A Lochbihler |
| |
Institution: | 1.Laboratory for Foundations of Computer Science, School of Informatics,University of Edinburgh,Edinburgh,Scotland, UK;2.Fakult?t für Mathematik und Informatik,Universit?t Passau,Passau,Germany |
| |
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 -hard. In this paper we show that determining the existence of an ESS is both -hard and -hard, and that the problem is contained in , the second level of the polynomial time hierarchy. We also show that determining the existence of a regular ESS is indeed
-complete. Our upper bounds also yield algorithms for computing a (regular) ESS, if one exists, with the same complexities. |
| |
Keywords: | Computational complexity Game theory Evolutionarily stable strategies Evolutionary biology Nash equilibria |
本文献已被 SpringerLink 等数据库收录! |
|