Fetching the paper…
Reading the bibliography…
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.
Equilibrium points in n-person games
John Nash · 1950
Earlier work this paper cites.
Equilibrium points of bimatrix games
Carlton Lemke and Joseph Howson · 1964
Earlier work this paper cites.
The logic of animal conflict
George Price and John Maynard Smith · 1973
Earlier work this paper cites.
Nash and correlated equilibria: Some complexity considerations
Itzhak Gilboa and Eitan Zemel · 1989
Earlier work this paper cites.
On the complexity of the parity argument and other inefficient proofs of existence
Christos H. Papadimitriou · 1994
Earlier work this paper cites.
On the complexity of min-max optimization problems and their approximation
Ker-I Ko and Chih-Long Lin · 1995
Earlier work this paper cites.
Algorithms, games and the Internet
Christos H. Papadimitriou · 2001
Cited alongside, same era.
The computational complexity of evolutionarily stable strategies
Kousha Etessami and Andreas Lochbihler · 2004
Cited alongside, same era.
A note on the computational hardness of evolutionary stable strategies
Noam Nisan · 2006
Cited alongside, same era.
Hard-to-solve bimatrix games
Rahul Savani and Bernhard von Stengel · 2006
Cited alongside, same era.
Computational evolutionary game theory
Siddharth Suri · 2007
Cited alongside, same era.
New complexity results about Nash equilibria
Vincent Conitzer and Tuomas Sandholm · 2008
Later among the works it cites.
Completeness in the polynomial-time hierarchy: A compendium, 2008
Marcus Schaefer and Christopher Umans · 2008
Later among the works it cites.
Settling the complexity of computing two-player Nash equilibria
Xi Chen, Xiaotie Deng, and Shang-Hua Teng · 2009
Later among the works it cites.
The complexity of computing a Nash equilibrium
Constantinos Daskalakis, Paul Goldberg, and Christos H. Papadimitriou · 2009
Later among the works it cites.
On the complexity of Nash equilibria and other fixed points
Kousha Etessami and Mihalis Yannakakis · 2010
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…