The exact computational complexity of evolutionarily stable strategies
Publication
, Journal Article
Conitzer, V
Published in: Mathematics of Operations Research
January 1, 2019
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 ΣP2 complete.
Duke Scholars
Published In
Mathematics of Operations Research
DOI
EISSN
1526-5471
ISSN
0364-765X
Publication Date
January 1, 2019
Volume
44
Issue
3
Start / End Page
783 / 792
Related Subject Headings
- Operations Research
- 4901 Applied mathematics
- 0802 Computation Theory and Mathematics
- 0103 Numerical and Computational Mathematics
- 0102 Applied Mathematics
Citation
APA
Chicago
ICMJE
MLA
NLM
Conitzer, V. (2019). The exact computational complexity of evolutionarily stable strategies. Mathematics of Operations Research, 44(3), 783–792. https://doi.org/10.1287/moor.2018.0945
Conitzer, V. “The exact computational complexity of evolutionarily stable strategies.” Mathematics of Operations Research 44, no. 3 (January 1, 2019): 783–92. https://doi.org/10.1287/moor.2018.0945.
Conitzer V. The exact computational complexity of evolutionarily stable strategies. Mathematics of Operations Research. 2019 Jan 1;44(3):783–92.
Conitzer, V. “The exact computational complexity of evolutionarily stable strategies.” Mathematics of Operations Research, vol. 44, no. 3, Jan. 2019, pp. 783–92. Scopus, doi:10.1287/moor.2018.0945.
Conitzer V. The exact computational complexity of evolutionarily stable strategies. Mathematics of Operations Research. 2019 Jan 1;44(3):783–792.
Published In
Mathematics of Operations Research
DOI
EISSN
1526-5471
ISSN
0364-765X
Publication Date
January 1, 2019
Volume
44
Issue
3
Start / End Page
783 / 792
Related Subject Headings
- Operations Research
- 4901 Applied mathematics
- 0802 Computation Theory and Mathematics
- 0103 Numerical and Computational Mathematics
- 0102 Applied Mathematics