Algorithm for Evolutionarily Stable Strategies against Pure Mutations

Evolutionarily stable strategy (ESS) is an important solution concept in game theory which has been applied frequently to biology and even cancer. Finding such a strategy has been shown to be difficult from a theoretical complexity perspective. Informally an ESS is a strategy that if followed by the population cannot be taken over by a mutation strategy. We present an algorithm for the case where mutations are restricted to pure strategies. This is the first positive result for computation of ESS, as all prior results are computational hardness and no prior algorithms have been presented.