| Abstract: |
We study two of the simple rules on finite graphs under the
death-birth updating and the imitation updating discovered by Ohtsuki,
Hauert, Lieberman, and Nowak [Nature, 441 (2006) 502-505]. Each
rule specifies a payoff-ratio cutoff point for the magnitude of fixation
probabilities of the underlying evolutionary game between cooperators and
defectors. We view the Markov chains associated with the two updating
mechanisms as voter model perturbations. Then we present a first-order
approximation for fixation probabilities of general voter model
perturbations on finite graphs subject to small perturbation in terms of
the voter model fixation probabilities. In the context of regular graphs,
we obtain algebraically explicit first-order approximations for the
fixation probabilities of cooperators distributed as certain uniform
distributions. These approximations lead to a rigorous proof that both of
the rules of Ohtsuki et al. are valid and are sharp. |