Epsilon-stability and the speed of learning in network games

This paper introduces epsilon-stability as a generalization of the concept of stochastic stability in learning and evolutionary game dynamics. An outcome of a model of stochastic evolutionary dynamics is said to be epsilon-stable in the long-run if for a given model of mistakes it maximizes its invariant distribution. We construct an efficient algorithm for computing epsilon-stable outcomes and provide conditions under which epsilon-stability can be approximated by stochastic stability. We also define and provide tighter bounds for contagion rate and metastability as measures for characterizing the short-run and medium-run behaviour of a typical stochastic evolutionary model. Keywords Stochastic evolution, network games, epsilon-stable sets, expected waiting time, metastability, contagion rate.