The Exact Computational Complexity of Evolutionarily Stable Strategies
成果类型：
Article
署名作者：
Conitzer, Vincent
署名单位：
Duke University
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.2018.0945
发表日期：
2019
页码：
783-792
关键词：
摘要：
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 Sigma(p)(2) complete.
来源URL：