Abstract
We propose a novel graph-based reformulation for the concept of evolutionarily stable strategies. Evolutionarily stable strategy (ESS) analysis cannot always explain the long-term behavior of a natural selection-mutation process. Stochastic stability is a more general analysis tool as compared to ESS analysis because it can precisely characterize long-term stochastic behavior. However, one of the reasons why ESS analysis is still widely popular is its computational simplicity. Our objective is to provide a balance between the convenience of ESS analysis and the generality of stochastic stability. The fundamental object in our development is the transitive stability (TS) graph of an evolutionary process. From the TS-graph, we show that we can efficiently compute the smallest set of strategies that always contains the stochastically stable strategies (SSS) for a particular class of evolutionary processes. In particular, we prove that each terminal class of the TS-graph is potentially a stochastically stable group of strategies. In case there is a unique terminal class, then it corresponds exactly to the set of SSS. In case there are multiple terminal classes, then these contain the set of possible SSS, and we show that a unique determination is impossible without higher order analysis.