Person:

Fudenberg, Drew

This note characterizes the impact of adding rare stochastic mutations to an “imitation dynamic,” meaning a process with the properties that absent strategies remain absent, and non-homogeneous states are transient. The resulting system will spend almost all of its time at the absorbing states of the no-mutation process. The work of Freidlin and Wentzell [Random Perturbations of Dynamical Systems, Springer, New York, 1984] and its extensions provide a general algorithm for calculating the limit distribution, but this algorithm can be complicated to apply. This note provides a simpler and more intuitive algorithm. Loosely speaking, in a process with K strategies, it is sufficient to find the invariant distribution of a K×K Markov matrix on the K homogeneous states, where the probability of a transit from “all play i” to “all play j” is the probability of a transition from the state “all agents but 1 play i, 1 plays j” to the state “all play j”.

This paper studies the effect of randomness in per-period matching on the long-run outcome of non-equilibrium adaptive processes. If there are many matchings between each strategy revision, the randomness due to matching will be small; our question is when a very small noise due to matching has a negligible effect. We study two different senses of this idea, and provide sufficient conditions for each. The less demanding sense corresponds to sending the matching noise to zero while holding fixed all other aspects of the adaptive process. The second sense in which matching noise can be negligible is that it does not alter the limit distribution obtained as the limit of the invariant distributions as an exogenous “mutation rate” goes to zero.

We analyze a class of imitation dynamics with mutations for games with any finite number of actions, and give conditions for the selection of a unique equilibrium as the mutation rate becomes small and the population becomes large. Our results cover the multiple-action extensions of the aspiration-and-imitation process of Binmore and Samuelson [Muddling through: noisy equilibrium selection, J. Econ. Theory 74 (1997) 235–265] and the related processes proposed by Benaı¨m and Weibull [Deterministic approximation of stochastic evolution in games, Econometrica 71 (2003) 873–903] and Traulsen et al. [Coevolutionary dynamics: from finite to infinite populations, Phys. Rev. Lett. 95 (2005) 238701], as well as the frequency-dependent Moran process studied by Fudenberg et al. [Evolutionary game dynamics in finite populations with strong selection and weak mutation, Theoretical Population Biol. 70 (2006) 352–363]. We illustrate our results by considering the effect of the number of periods of repetition on the selected equilibrium in repeated play of the prisoner's dilemma when players are restricted to a small set of simple strategies.

The repeated Prisoner's Dilemma is usually known as a story of tit-for-tat (TFT). This remarkable strategy has won both of Robert Axelrod's tournaments. TFT does whatever the opponent has done in the previous round. It will cooperate if the opponent has cooperated, and it will defect if the opponent has defected. But TFT has two weaknesses: (i) it cannot correct mistakes (erroneous moves) and (ii) a population of TFT players is undermined by random drift when mutant strategies appear which play always-cooperate (ALLC). Another equally simple strategy called ‘win-stay, lose-shift’ (WSLS) has neither of these two disadvantages. WSLS repeats the previous move if the resulting payoff has met its aspiration level and changes otherwise. Here, we use a novel approach of stochastic evolutionary game dynamics in finite populations to study mutation–selection dynamics in the presence of erroneous moves. We compare four strategies: always-defect (ALLD), ALLC, TFT and WSLS. There are two possible outcomes: if the benefit of cooperation is below a critical value then ALLD is selected; if the benefit of cooperation is above this critical value then WSLS is selected. TFT is never selected in this evolutionary process, but lowers the selection threshold for WSLS.