The Exact Computational Complexity of Evolutionarily Stable Strategies

2018/05/06 by Conitzer, Vincent · 1 citation
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1805.02226

Abstract

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 Σ₂^P-complete.

Cited by

• Computing Evolutionarily Stable Strategies in Multiplayer Games

Related

• Existence of Evolutionarily Stable Strategies Remains Hard to Decide for\n a Wide Range of Payoff Values
• Computational Complexity of Multi-Player Evolutionarily Stable Strategies
• Computing Evolutionarily Stable Strategies in Imperfect-Information Games
• Time Complexity Analysis of an Evolutionary Algorithm for approximating\n Nash Equilibriums
• The Complexity of Computing a Nash Equilibrium