A Note on Varying Mutation Rates in 2 × 2 Coordination Games^{∗}

Alexander F. Tieman^{†}and Harold Houba^{‡}

June 9, 1998

Abstract

The model of 2 × 2 coordination games in Kandori, Mailath, and Rob (1993) is extended to allow for a mutation rate that is stochastic over time. The expected time the system spends in the risk dominated equilibrium is systematically underestimated by the standard model in Kandori, Mailath, and Rob (1993) when the latter model’s (fixed) mutation rate is equal to the expected mutation rate. A small population result corrects a minor omission in Kandori, Mailath, and Rob (1993).

∗This paper has benefitted significantly from comments by and discussions with Gerard van der Laan, Nam-Kyoo Boots, Oddvar Kaarboe and various participants at the 1998 Stony Brook Summer Festival on Game Theory. The authors would like to thank Larry Samuelson for encouraging this research project and participants at the 1997 Summer school in Oberwesel, Germany, for comments.

†Tinbergen Institute and Free University, Department of Econometrics, De Boelelaan 1105, 1081HV Amsterdam, The Netherlands. E-mail: xtieman@econ.vu.nl, Phone: +31-20-4446022, Fax: +31-20-4446020, URL: http://www.econ.vu.nl/~xtieman/ .

‡Free University.

1. Introduction.

The central message in both Kandori, Mailath, and Rob (1993) (henceforth KMR) and Young (1993) (and in related model like Ellison (1993), Bergin and Lipman (1996) or Rhode and Stegeman (1996)) is that noise in the form of mutations matters for the selection of one Nash equilibrium among strict Nash equilibria. In this note the evolutionary process for 2 × 2 coordination games in KMR^{1} is extended to replace the constant mutation rate by a per-period mutation rate that is small but stochastic over time. To be precise, in each time period the mutation rate is a draw from a non-degenerate i.i.d. random variable with support on a subset of a small bounded interval of non-negative numbers. A non-constant mutation rate is closer to (economic) reality than a fixed mutation rate, since in the three interpretations of mutations most frequently mentioned in the literature, namely experimentation, (computational) errors in the implementation of an action and genetic mutation, are all three difficult to reconcile with the assumption that the mutation rate is constant, as already noted by Bergin and Lipman (1996). Events outside of the model will cause economic subjects to experiment more, make more mistakes or experience a higher rate of genetic mutation at certain times than at others. We model such outside influence indirectly through the stochastic mutation rate.

Our main result states that in 2 × 2 coordination games the expected time the system spends in the risk dominated equilibrium (the equilibrium with the smaller basin of attraction) is systematically underestimated by the results of KMR when the constant mutation rate in the latter model is set equal to the expected per-period mutation rate in our extended model. A numerical example shows that the magnitude of the underestimation can be quite large. These results are of importance for (economic) phenomena that can be modelled as coordination games, e.g. for the macroeconomic literature on coordination failure (see e.g. Cooper and John (1988)).

Our main result is derived for a sufficiently large population. However, we also investigate small populations and find different results. As a topic of related interest our analysis reveals a minor mistake in the results reported in KMR and we provide the correct specification.

In most of the literature, the mutation rate is taken to zero in the limit in order to state a clear result on the invariant distribution on the state space. Performing a similar exercise in our extended model by letting the support of the stochastic mutation rate pile up at 0 in the limit would yield the same invariant distribution as found in KMR. For that reason we omit this routine exercise. Furthermore, in all of the proofs attention is restricted to the case in which the Darwinian dynamics are the best reply dynamics. Subsequently, we argue that the results holds for all Darwinian dynamics.

1It is not hard to make the same extension in the closely related model of Young (1993).

2. The Model.

In this note we use the framework of KMR, section 7. Specifically, we focus on the (fixed) coordination game

\begin{matrix}1\2 & s_{1} & s_{2} \\ s_{1} & a, a & 0, 0 \\ s_{2} & 0, 0 & 1, 1 \end{matrix}

with a > 1, played repeatedly in a population consisting of N players. By z_{t} ∈ Z, Z = {0, 1, …, N}, we denote the number of players adopting action s_{1} at time t. Thus z_{t} = N, denoted by E_{1} = (s_{1}, s_{1}) , yields the risk dominant equilibrium at any play of the stage game between two players from the population, while z_{t} = 0, denoted by E_{2} = (s_{2}, s_{2}), yields the risk dominated equilibrium. The population state z^{∗} = \frac{N+a−1}{a+1} reflects the (unstable) mixed equilibrium. By the entier function [z^{∗}] , we denote the largest integer smaller or equal to z^{∗}. We focus on best reply deterministic dynamics given by

z_{t+1} = B (z) = \{ \begin{matrix}0, & if z_{t} < z^{∗}, \\ z^{∗}, & if z_{t} = z^{∗}, \\ N, & if z_{t} > z^{∗}. \end{matrix}

As in KMR we add a stochastic component representing random mutation. The best reply dynamics with random mutation enable us to model the process of switching between states E_{1} and E_{2} as a two state Markov chain. We define P (ε) to be the transition matrix of this Markov chain, where ε > 0 is the constant mutation rate. Now, the expected time spent in the equilibrium E_{1} respectively E_{2} is given by \frac{1}{p(ε)} and \frac{1}{p′(ε)}, where

p (ε) = ∑_{j=N−[z^{∗}]}^{N} \binom{N}{j}ε^{j} (1 − ε)^{N−j} and p′ (ε) = ∑_{j=[z^{∗}]+1}^{N} \binom{N}{j}ε^{j} (1 − ε)^{N−j} .

The transition matrix P (ε) of this Markov chain is given by

P (ε) = ( \begin{matrix}1 − p (ε) & p (ε) \\ p′ (ε) & 1 − p′ (ε) \end{matrix} )

and the stationary distribution, denoted by μ (P (ε)) = (μ_{1} (P (ε)) , μ_{2} (P (ε))) , only puts weight on the two states E_{1} and E_{2}. The weight on E_{1} respectively E_{2} is given by

μ_{1} (P (ε)) = \frac{p′ (ε)}{p (ε) + p′ (ε)} and μ_{2} (P (ε)) = 1 − μ_{1} (P (ε)) = \frac{p (ε)}{p (ε) + p′ (ε)}.

The innovative feature of our model lies in the assumption that the mutation rate ε_{t} at time t is stochastic. At every time t, the mutation rate ε_{t} is a realization of a random variable θ with an arbitrary non-degenerate, discrete probability distribution Θ, which has its support on a subset of [0, \overline{ε}], for some \overline{ε} > 0. Since every continuous probability distribution can be approximated arbitrarily close by a discrete probability distribution there is no loss in generality in using a discrete Θ.

The case of a stochastic mutation rate yields an inhomogeneous Markov chain, which can be handled as follows. In every period, the dynamics consist of a compounded lottery. At each time t, first a draw ε_{t} from θ ∼ Θ determines the mutation rate for period t, and next, the mutation rate ε_{t} determines the transition probabilities p (ε_{t}) and p′ (ε_{t}) in the transition matrix of the Markov chain. These two stochastic events can be compounded into a single transition matrix IEP (θ) , θ ∼ Θ, where

IEP (θ) = ( \begin{matrix}1 − IEp (θ) & IEp (θ) \\ IEp′ (θ) & 1 − IEp′ (θ) \end{matrix} ) ,

and IE (.) is the expectation operator. Therefore, the invariant distribution of our extended model is the invariant probability distribution of the transition matrix IEP (θ).

3. Results.

Our main result states an order on the following three numbers, namely μ_{2}(P (IEθ)) is the smallest number, μ_{2}(IEP (θ)) is the largest number and IEμ_{2}(P (θ)) lies in between these two numbers. Since μ_{2}(IEP (θ)) corresponds to the true invariant distribution the other two can be regarded as (inexact) approximations of μ_{2}(IEP (θ)). The number μ_{2}(P (IEθ)) corresponds to the standard model in KMR, where the constant mutation rate is taken equal to the per-period expected mutation rate IEθ of the stochastic variable θ ∼ Θ. The main result shows that the latter interpretation systematically underestimates the expected time the system spends in the dominated equilibrium E_{2}. The number IEμ_{2}(P (θ)) refers to the standard KMR model with the constant mutation rate ε_{0} drawn randomly at time t = 0 and, once drawn, remaining fixed at ε_{0} over time. Then IEμ_{2}(P (θ)) is the ex-ante (before drawing ε_{0}) expected probability of being in E_{2} at an arbitrary time t far enough away from t = 0. This number is a better approximation for μ_{2}(IEP (θ)) than μ_{2}(P (IEθ)). The order of these three numbers is the result stated in the following theorem, which applies to relatively large populations.

Theorem 3.1. Let a > 1 + \frac{2}{N−3} for N odd and a > 1 + \frac{4}{N−4} for N even. Then there exists an \overline{ε} > 0 such that μ_{2}(P (IEθ)) < IEμ_{2}(P (θ)) < μ_{2}(IEP (θ)), where θ is a random variable with distribution Θ, with Θ an arbitrary non-degenerate discrete probability distribution with support on a subset of [0, \overline{ε}].

Proof of the first inequality in Theorem 3.1. In order to proof the first inequality, it suffices to show that μ_{2} (P (ε)) is convex in ε and to apply Jensen’s inequality. Substituting p (ε) and p′ (ε) in μ_{2} (P (ε)) yields

μ_{2} (P (ε)) = \frac{∑_{j=N−[z^{∗}]}^{N} \binom{N}{j}ε^{j} (1 − ε)^{N−j}}{∑_{j=N−[z^{∗}]}^{N} \binom{N}{j}ε^{j} (1 − ε)^{N−j} + ∑_{j=[z^{∗}]+1}^{N} \binom{N}{j}ε^{j} (1 − ε)^{N−j}} .

By dividing both the numerator and the denominator by ε^{[z^{∗}]+1} (1 − ε)^{N−[z^{∗}]−1} we get

μ_{2} (P (ε)) = \frac{∑{N−[z^{∗}]−1 \atop j=N−2[z^{∗}]−1} \binom{N}{j+[z^{∗}]+1} (\frac{ε}{(1−ε)})j}{∑_{j=N−2[z^{∗}]−1}^{N−[z^{∗}]−1} \binom{N}{j+[z^{∗}]+1} (\frac{ε}{(1−ε)})^{j} + ∑_{j=0}^{N−[z^{∗}]−1} \binom{N}{j+[z^{∗}]+1} (\frac{ε}{(1−ε)})^{j}} ,

which is equivalent to

μ_{2} (P (ε)) = \frac{∑{N−[z^{∗}]−1 \atop j=N−2[z^{∗}]−1} \binom{N}{j+[z^{∗}]+1} (\frac{ε}{(1−ε)})j}{2 · ∑_{j=N−2[z^{∗}]−1}^{N−[z^{∗}]−1} \binom{N}{j+[z^{∗}]+1} (\frac{ε}{(1−ε)})^{j} + ∑_{j=0}^{N−2[z^{∗}]−2} \binom{N}{j+[z^{∗}]+1} (\frac{ε}{(1−ε)})^{j}} .

We define the terms C (ε) and D (ε) as

C (ε) = ∑_{j=0}^{N−2[z^{∗}]−2} \binom{N}{j + [z^{∗}] + 1} (\frac{ε}{(1 − ε)})^{j} (3.1)

and

D (ε) = ∑_{j=N−2[z^{∗}]−1}^{N−[z^{∗}]−1} \binom{N}{j + [z^{∗}] + 1} (\frac{ε}{(1 − ε)})^{j}  (3.2)

leading to μ_{2} (P (ε)) = \frac{D(ε)}{C(ε)+2D(ε)}.

The second derivative of μ_{2} (P (ε)) with respect to ε, μ2^{′′} (P (ε)) , is given by

\begin{matrix}\{C (ε) D′′ (ε) − C′′ (ε) D (ε)\} & \{C (ε) + 2D (ε)\} \\ \{C (ε) + 2D (ε)\} & 3 \end{matrix} + \frac{2 \{C′ (ε) D (ε) − C (ε) D′ (ε)\} \{C′ (ε) + 2D′ (ε)\}}{\{C (ε) + 2D (ε)\}^{3}}.

Explicit expressions for the derivatives C′ (ε) , C′′ (ε) , D′ (ε) and D′′ (ε) can be found in the appendix. From these expressions we see that the denominator of μ2^{′′} (P (ε)) is strictly positive for all ε ∈ (0, 1) and that the numerator of μ2^{′′} (P (ε)) is a higher order polynomial function of ε. Label the smallest positive root of the numerator of μ2^{′′} (P (ε)) as \overline{ε}_{1}. If the polynomial has no root larger than 0, we set \overline{ε}_{1} to 1. The function μ2^{′′} (P (ε)) is either positive or negative on the whole interval (0, \overline{ε}_{1}). To determine the sign of μ2^{′′} (P (ε)) on (0, \overline{ε}_{1}) , we distinguish the case N even and the case N odd.

For N even, note that since [z^{∗}] < \frac{1}{2}N is always integer, N − 2 [z^{∗}] − 1 can only take the values 1, 3, 5, …. The condition a > 1 + \frac{4}{N−4} guarantees that N − 2 [z^{∗}] − 1 > 1, and thus that N − 2 [z^{∗}] − 1 ≥ 3, ensuring that D (0) = D′ (0) = D′′ (0) = 0, since the lowest power of ε in these polynomials is at least 1. Thus μ2^{′} (P (ε)) and μ2^{′′} (P (ε)) are both 0 in ε = 0. Furthermore, we see that μ_{2} (P (0)) = 0 and μ_{2} (P (ε)) > 0 for ε > 0, leading to the conclusion μ2^{′} (P (ε)) > 0 for small ε > 0. Repeating this line of reasoning we conclude from μ2^{′} (P (0)) = 0 and μ2^{′} (P (ε)) > 0, for small ε > 0, that μ2^{′′} (P (ε)) > 0 for small ε > 0. Thus μ2^{′′} (P (ε)) is positive on (0, \overline{ε}_{1}) .

Now consider the case N odd. Note that since [z^{∗}] < \frac{1}{2}N is always integer, N − 2 [z^{∗}] − 1 can only take the values 0, 2, 4, …. Furthermore, the condition a > 1 + \frac{2}{N−3} guarantees that N − 2 [z^{∗}] − 1 > 0, and thus that N − 2 [z^{∗}] − 1 ≥ 2, ensuring that D (0) = D′ (0) = 0. We now consider two cases, D′′ (0) = 0, when N − 2 [z^{∗}] − 1 > 2 and D′′ (0) > 0, when N − 2 [z^{∗}] − 1 = 2. In the former case (D′′ (0) = 0), the same argument used above for N even ensures that μ2^{′′} (P (ε)) > 0 on (0, \overline{ε}_{2}) , for some \overline{ε}_{2} > 0.^{2} In the latter case (D′′ (0) > 0), the numerator of μ2^{′′} (P (ε)) is equal to C^{2} (ε) D′′ (ε) > 0 in ε = 0. By a continuity argument this proves that μ2^{′′} (P (ε)) > 0 for all ε ∈ (0, \overline{ε}_{3}) , for some \overline{ε}_{3} > 0.

Thus μ_{2} (P (ε)) is a convex function on (0, \overline{ε}) , with \overline{ε} = min \{\overline{ε}_{1}, \overline{ε}_{2}, \overline{ε}_{3}\} > 0. Applying Jensen’s inequality results in μ_{2}(P (IEθ)) < IEμ_{2}(P (θ)). □

2The maximal \overline{ε}_{2} is the smallest positive root of μ2^{′′} (P (ε)) , which will generically be different from \overline{ε}_{1}.

Proof of the second inequality in Theorem 3.1. In this proof we will first focus attention on a Bernoulli distribution Θ, i.e. Pr (ε_{t} = ε_{high}) = λ, Pr (ε_{t} = ε_{low}) = 1 − λ, ε_{high}, ε_{low} > 0. Subsequently we will argue that the obtained results hold for all non-degenerate discrete probability distributions Θ.

We assume w.l.o.g. that ε_{low} = ε > 0 and ε_{high} = (1 + α) ε, α > 0. In table 3.1, we have calculated IEμ_{i} (P (θ)) = λμ_{i} (P ({1 + α} ε)) + (1 − λ) μ_{i} (P (ε)) , i = 1, 2, and μ_{i} (IEP (θ)) = μ_{i} (λP ({1 + α} ε) + (1 − λ) P (ε)) , i = 1, 2.

\begin{matrix}i & IEμ_{i}(P (θ)) & μ_{i}(IEP (θ)) \\ 1 & λ\frac{p′((1+α)ε)}{p((1+α)ε)+p′((1+α)ε)} + (1 − λ) \frac{p′(ε)}{p(ε)+p′(ε)} & \frac{λp′(ε)−λp′((1+α)ε)−p′(ε)}{λp(ε)−λp((1+α)ε)−p(ε)+λp′(ε)−λp′((1+α)ε)−p′(ε)} \\ 2 & λ\frac{p((1+α)ε)}{p((1+α)ε)+p′((1+α)ε)} + (1 − λ) \frac{p(ε)}{p(ε)+p′(ε)} & \frac{λp(ε)−λp((1+α)ε)−p(ε)}{λp(ε)−λp((1+α)ε)−p(ε)+λp′(ε)−λp′((1+α)ε)−p′(ε)} \end{matrix}

Table 3.1: The expressions IEμ_{i} (P (θ)) and μ_{i} (IEP (θ)) for i = 1, 2.

To show that

λ\frac{p ((1 + α) ε)}{p ((1 + α) ε) + p′ ((1 + α) ε)} + (1 − λ) \frac{p (ε)}{p (ε) + p′ (ε)}

< \frac{p (ε) − λp (ε) + λp ((1 + α) ε)}{p (ε) − λp (ε) + λp ((1 + α) ε) + p′ (ε) − λp′ (ε) + λp′ ((1 + α) ε)}

we rewrite the LHS, resulting in

\frac{p (ε) p ((1 + α) ε) + p (ε) p′ ((1 + α) ε)}{\{p ((1 + α) ε) + p′ ((1 + α) ε)\} \{p (ε) + p′ (ε)\}}

< \frac{p (ε) − λp (ε) + λp ((1 + α) ε)}{p (ε) − λp (ε) + λp ((1 + α) ε) + p′ (ε) − λp′ (ε) + λp′ ((1 + α) ε)}.

Since both numerators and denominators are positive, cross multiplication results in {p (ε) p ((1 + α) ε) + p (ε) p′ ((1 + α) ε)} ·

{p (ε) − λp (ε) + λp ((1 + α) ε) + p′ (ε) − λp′ (ε) + λp′ ((1 + α) ε)}
< {p ((1 + α) ε) + p′ ((1 + α) ε)} {p (ε) + p′ (ε)} {p (ε) − λp (ε) + λp ((1 + α) ε)} .

We substract the common term p^{2} (ε) p ((1 + α) ε) − λp (ε)^{2} p ((1 + α) ε) + λp (ε) p^{2} ((1 + α) ε) + p (ε) p ((1 + α) ε) p′ (ε)

−λp (ε) p ((1 + α) ε) p′ (ε) + λp (ε) p ((1 + α) ε) p′ ((1 + α) ε) + p^{2} (ε) p′ ((1 + α) ε)
−λp^{2} (ε) p′ ((1 + α) ε) + p (ε) p′ ((1 + α) ε) p′ (ε) − λp (ε) p′ ((1 + α) ε) p′ (ε)

from both sides and get

{p ((1 + α) ε) + p′ ((1 + α) ε)} {λp (ε) p′ ((1 + α) ε)}
< {p ((1 + α) ε) + p′ ((1 + α) ε)} {λp ((1 + α) ε) p′ (ε)} .

Thus, it remains to be shown that

λp (ε) p′ ((1 + α) ε) < λp ((1 + α) ε) p′ (ε) . (3.3)

We divide by λ > 0 and write down the Taylor expansion for small α around p′ (ε) and p (ε)

p (ε) \{p′ (ε) + α\frac{d}{dε}p′ (ε) + O (α^{2})\} < p′ (ε) \{p (ε) + α\frac{d}{dε}p (ε) + O (α^{2})\} .

Then we rewrite the expression disregarding the higher order term, deduct the common term p (ε) p′ (ε) and divide by α, resulting in p (ε) \frac{d}{dε}p′ (ε) < p′ (ε) \frac{d}{dε}p (ε) . We now write down these terms explicitly and isolate the lowest orders of ε on both sides. Furthermore we divide by the common term and neglect all powers of 1 − ε ≈ 1. This results in

([z^{∗}] + 1) ε^{N} − (N − [z^{∗}] − 1) ε^{N+1} < (N − [z^{∗}]) ε^{N} − [z^{∗}] ε^{N+1},

an inequality that is true for [z^{∗}] < \frac{N}{2} − \frac{1}{2} (i.e. a > \frac{N−1}{N−3}), since then N − [z^{∗}] > [z^{∗}] + 1 and [z^{∗}] < N − [z^{∗}] − 1. Note that we do not need the restriction a > \frac{N}{N−4} for N even in this proof. Furthermore, note that we made use of the fact that ε > 0 is small, resulting in an upperbound \overline{ε}_{4} > 0 for the value of ε for which this proof hold.

A simple induction argument now shows that the inequality holds for all non-degenerate discrete probability distributions Θ with support on a subset of the interval [0, \overline{ε}_{5}] , where \overline{ε}_{5} > 0 is an upperbound that can be from an expression similar to (3.3) for any specific distribution. We conclude the proof with the remark that the \overline{ε} in the Theorem is the minimum of the upperbounds mentioned in the proof, thus \overline{ε} = min_{i} \overline{ε}_{i}. □

Corollary 3.2. Let a > 1 + \frac{2}{N−3} for N odd and a > 1 + \frac{4}{N−4} for N even. Then there exists an \overline{ε} > 0 such that μ_{1}(P (IEθ)) > IEμ_{1}(P (θ)) > μ_{1}(IEP (θ)), where θ is a random variable with distribution Θ, with Θ an arbitrary non-degenerate discrete probability distribution with support on a subset of [0, \overline{ε}].

Driving the proof is the result that the probability of switches between the two equilibria is higher than in the fixed mutation rate model, i.e. IEp(θ) > p(IEθ) and IEp′(θ) > p′(IEθ), and that the probability of a switch from E_{1} to E_{2} increases faster than the probability of a switch from E_{2} to E_{1}. Furthermore, it is clear from the proof that the expected time spent in the risk dominated equilibrium grows more than linear in the probability mass that is put on high mutation rate. Note however, that μ_{2} (ε) ≤ \frac{1}{2} for all ε ∈ [0, 1] .

In order to obtain some insight in the magnitude of the underestimation, we consider the example a = 2, N = 10 and Pr(ε_{t} = \frac{1}{50}) = Pr(ε_{t} = \frac{1}{200}) = \frac{1}{2}. Then IEθ = \frac{1}{80} and

μ_{2}(P (IEθ)) = 1. 15 × 10^{−6} and μ_{2}(IEP (θ)) = 4. 76 × 10^{−6}.

Thus, μ_{2}(IEP (θ)) is roughly 315% larger than μ_{2}(P (IEθ)), showing a rather severe underestimation of the time spent in E_{2} when IEθ is taken as the mutation rate in the standard KMR framework.

The above results only holds for sufficiently large populations. At this point we take a further look at 1 < a ≤ 1 + \frac{4}{N−4}, i.e. N − 2 [z^{∗}] − 1 = 1, for N even and at 1 < a ≤ 1 + \frac{2}{N−3}, i.e. N − 2 [z^{∗}] − 1 = 0, for N odd. From the restriction on a and lim_{N→∞} 1 + \frac{4}{N−4} = lim_{N→∞} 1 + \frac{2}{N−3} = 1 it is clear that for a fixed a, the following results only hold for small N and thus that they are only useful in relatively small populations. The following proposition states that for small populations, μ_{2}(P (IEθ)) is a better (but still inaccurate) approximation of μ_{2}(IEP (θ)) than IEμ_{2}(P (θ)) is.

Proposition 3.3. For N even, let a ∈ (1, 1 + \frac{4}{N−4}], i.e. N − 2 [z^{∗}] − 1 = 1. Then there exists an \overline{ε} > 0 such that IEμ_{2}(P (θ)) < μ_{2}(P (IEθ)) < μ_{2}(IEP (θ)), where θ is a random variable with distribution Θ, with Θ an arbitrary non-degenerate discrete probability distribution with support on a subset of [0, \overline{ε}].

Proof of the first inequality of Proposition 3.3. Restricting a ∈ (1, 1 + \frac{4}{N−4}] is equivalent to requiring that z^{∗} ∈ [\frac{1}{2}N − 1, \frac{1}{2}N) . Since \frac{1}{2}N −1 is an integer for N even, this means that [z^{∗}] = \frac{1}{2}N −1 and thus that N −2 [z^{∗}]−1 = 1. This leads to C (ε) = \binom{N}{[z^{∗}]+1} = \binom{N}{\frac{1}{2} N}, being a constant for all ε ∈ [0, 1] . Thus μ_{2} (P (ε)) = _{\frac{D(ε)}{\binom{N}{\frac{1}{2} N}+2D(ε)}} and

lim_{ε↓0} μ2^{′′} (P (ε)) = \frac{\binom{N}{\frac{1}{2} N}D′′ (0) − 4 [D′ (0)]^{2}}{\binom{N}{\frac{1}{2} N}2} = \frac{\binom{N}{\frac{1}{2} N} · 2 [\binom{N}{\frac{1}{2} N+1} + \binom{N}{\frac{1}{2} N+2}] − 4\binom{N}{\frac{1}{2} N+1}^{2}}{\binom{N}{\frac{1}{2} N}2} .

We focus on the numerator \binom{N}{\frac{1}{2} N} · 2 \{\binom{N}{\frac{1}{2} N+1} + \binom{N}{\frac{1}{2} N+2}\} − 4\binom{N}{\frac{1}{2} N+1}^{2} which is equal to

\frac{(N!)^{2}}{(\frac{1}{2}N + 1)! (\frac{1}{2}N)! (\frac{1}{2}N − 1)! (\frac{1}{2}N − 2)!} ·

\{ \frac{2}{\frac{1}{2}N (\frac{1}{2}N − 1)} + \frac{2}{(\frac{1}{2}N + 2) · \frac{1}{2}N} − \frac{4}{(\frac{1}{2}N + 1) (\frac{1}{2}N − 1)}\} .

To determine the sign of this expression we look at the part in brackets

\frac{2}{\frac{1}{2}N (\frac{1}{2}N − 1)} + \frac{2}{(\frac{1}{2}N + 2) · \frac{1}{2}N} − \frac{4}{(\frac{1}{2}N + 1) (\frac{1}{2}N − 1)} = \frac{−16}{(N + 2) (N + 4) N} < 0, ∀N ∈ IN.

Thus we have that μ2^{′′} (P (0)) < 0 and by a continuity argument thus μ2^{′′} (P (ε)) < 0, ε ∈ (0, \overline{ε}_{1}) , for some \overline{ε}_{1} > 0.^{3} Applying Jensen’s inequality to the concave function μ_{2} (P (ε)) results in the first part of the proposition. □ Proof of the second inequality of Proposition 3.3. Restricting a ∈ (1, 1 + \frac{4}{N−4}] is equivalent to requiring that [z^{∗}] = \frac{1}{2}N − 1. Under this condition we first prove that μ_{2}(P (IEθ)) < μ_{2}(IEP (θ)) for θ a random variable with a Bernoulli distribution Θ, i.e. Pr (ε_{t} = (1 + α) ε) = λ, Pr (ε_{t} = ε) = 1 − λ, α > 0. For such θ, μ_{2}(P (IEθ)) < μ_{2}(IEP (θ)) yields

\frac{p (λαε + ε)}{p (λαε + ε) + p′ (λαε + ε)} < \frac{p (ε) − λp (ε) + λp ((1 + α) ε)}{p (ε) − λp (ε) + λp ((1 + α) ε) + p′ (ε) − λp′ (ε) + λp′ ((1 + α) ε)}.

Since both the numerators and denominators are strictly positive, cross multiplying does not alter the sign and we obtain

p (λαε + ε) {p (ε) − λp (ε) + λp ((1 + α) ε) + p′ (ε) − λp′ (ε) + λp′ ((1 + α) ε)}

< {p (λαε + ε) + p′ (λαε + ε)} {p (ε) − λp (ε) + λp ((1 + α) ε)} .

When we expand this expression and deduct the common (positive) term p (ε) p (λαε + ε) − λp (ε) p (λαε + ε) + λp ((1 + α) ε) p (λαε + ε) from both sides of the inequality and then rearrange the terms, we get p (λαε + ε) {p′ (ε) − λp′ (ε) + λp′ ((1 + α) ε)} < p′ (λαε + ε) {p (ε) − λp (ε) + λp ((1 + α) ε)} .

3The maximal value for \overline{ε}_{1} is the smallest positive root of the numerator of μ2^{′′} (P (ε)) or 1 in case μ2^{′′} (P (ε))

has no root larger than 0.

Now, we use the explicit expressions for p (ε) and p′ (ε) and, since ε is small, we focus on the lowest power of ε on both sides of the inequality sign. We replace all terms 1 − ε ≈ 1 by 1 and divide by \binom{N}{[z^{∗}]+1}\binom{N}{N−[z^{∗}]} and get

ε^{[z^{∗}]+1} (λαε + ε)^{N−[z^{∗}]} − λε^{[z^{∗}]+1} (λαε + ε)^{N−[z^{∗}]} + λ (1 + α)^{[z^{∗}]+1} ε^{[z^{∗}]+1} (λαε + ε)^{N−[z^{∗}]}

< ε^{N−[z^{∗}]} (λαε + ε)^{[z^{∗}]+1} − λε^{N−[z^{∗}]} (λαε + ε)^{[z^{∗}]+1} + λ (1 + α)^{N−[z^{∗}]} ε^{N−[z^{∗}]} (λαε + ε)^{[z^{∗}]+1} .

We now divide both sides by the common term^{4} (λα + 1)^{[z^{∗}]+1} ε^{N−1}, resulting in (λα + 1)^{N−2[z^{∗}]−1} − λ (λα + 1)^{N−2[z^{∗}]−1} + λ (1 + α)^{[z^{∗}]+1} (λα + 1)^{N−2[z^{∗}]−1} < 1 − λ + λ (1 + α)^{N−[z^{∗}]} . since [z^{∗}] = \frac{1}{2}N − 1, this expression reduces to

(λα + 1) \{1 − λ + λ (1 + α)^{\frac{N}{2}} \} < 1 − λ + λ (1 + α)^{\frac{N}{2} +1} . Although (λα + 1) (1 − λ) > 1 − λ, the second terms on both sides compensate this, as follows

(λα + 1) (1 − λ) − (1 − λ) < λ (1 + α)^{\frac{N}{2} +1} − λ (1 + α)^{\frac{N}{2}} (λα + 1) which, after some rewriting, gives

λα (1 − λ) < (1 + α)^{\frac{N}{2}} λα (1 − λ) ⇔ 1 < (1 + α)^{\frac{N}{2}} , a true statement for any α > 0 and N ∈ IN^{+}. Thus, we have proven the result for ε ∈ (0, \overline{ε}_{2}) , for some small \overline{ε}_{2} > 0, and a Bernoulli distribution Θ. An induction argument suffices to show that it holds for any random variable θ with a non-degenerate discrete probability distribution Θ with support on a subset of [0, \overline{ε}_{3}] for some small \overline{ε}_{3} > 0. Finally, in Proposition 3.3, \overline{ε} = min \{\overline{ε}_{1}, \overline{ε}_{2}, \overline{ε}_{3}\} . □

The following proposition states the result for small populations with an odd number of agents. Then all three numbers coincide and are equal to a half.

Proposition 3.4. For N odd, let a ∈ (1, 1 + \frac{2}{N−3}], i.e. N − 2 [z^{∗}] − 1 = 0. Then it holds that μ_{2}(P (IEθ)) = IEμ_{2}(P (θ)) = μ_{2}(IEP (θ)) = \frac{1}{2}, where θ is a random variable with distribution Θ, with Θ an arbitrary non-degenerate discrete probability distribution with support on a subset of [0, 1].

4(λα + 1)^{[z^{∗}]+1} is the lowest power of (λα + 1) , since [z^{∗}] + 1 = \frac{1}{2} N and N − [z^{∗}] = \frac{1}{2} N + 1

Proof. Restricting a ∈ (1, 1 + \frac{2}{N−3}] is equivalent to requiring that z^{∗} ∈ [\frac{1}{2}N − \frac{1}{2}, \frac{1}{2}N) . Since \frac{1}{2}N − \frac{1}{2} is an integer for N odd, this means that [z^{∗}] = \frac{1}{2}N − \frac{1}{2} and thus that N − 2 [z^{∗}] − 1 = 0. This results in C (ε) = 0 for all ε ∈ [0, 1] , what comes down to lim_{ε↓0} μ_{2} (P (ε)) = lim_{ε↑1} μ_{2} (P (ε)) = μ_{2} (P (ε)) = \frac{D(ε)}{C(ε)+2D(ε)} = \frac{1}{2} ∀ε ∈ (0, 1) . □

Since the result of Proposition 3.4 also applies to fixed mutation rate ε = IEθ, our result is different from KMR’s Theorem 3. The explanation is that [z^{∗}] = \frac{1}{2}N − \frac{1}{2} implies that the assertion in KMR’s proof of their Theorem 3, that there will always exist an integer α, z^{∗} < α ≤ \frac{1}{2}N is incorrect. For [z^{∗}] = \frac{1}{2}N−\frac{1}{2}, it takes the same number of mutations to upset the efficient equilibrium E_{1}, as it takes to upset E_{2}. A symmetry argument leads to the conclusion that, for [z^{∗}] = \frac{1}{2}N − \frac{1}{2}, the invariant distribution in KMR should be μ = (μ_{1}, μ_{2}) = (\frac{1}{2}, \frac{1}{2}). Thus, the above result shows that the restriction to even N in KMR does have an impact, thereby contradicting the assertion in Rhode and Stegeman (1996) that it does not.

In order to show the different regions in the (a, N) plane, we present figure 3.1 for N even. For N odd, the figure looks very similar to this figure. From the figure we see that for either N large or a large, we are in the region where Theorem 3.1 applies. Only for small N and a not too large, we are in the region where Propositions 3.3 and 3.4 are applicable.

Figure 3.1: The different regions in the (a, N) plane for N even.

To obtain some insight in the magnitude of the maximum value of the upperbound \overline{ε} in Theorem 3.1, we present the value for ε_{1} in the proof of the Theorem in table 3.2 (to be precise, Proposition 3.3 applies to the case N = 10 and a = 1.5). For different combinations (a, N), it presents [z^{∗}] and ε_{1}. From this table we see that ε_{1} is far away from 0, indicating that the

\begin{matrix}N\a & 1.5 & 2 & 5 \\ 10 & 4; 1. 31 & 3; 0. 58 & 2; 0. 69 \\ 20 & 8; 0. 51 & 7; 0. 57 & 4; 0. 73 \\ 100 & 40; 0.57 & 33; 0.64 & 17; 0.81 \end{matrix}

Table 3.2: The values for [z^{∗}] (1^{st} entry) and the values for ε_{1} (2^{nd} entry) as a function of N and a.

interval [0, ε_{1}] is large. Furthermore we note that, for the cases where Theorem 3.1 applies, the value of ε_{1} is increasing in a.

An upperbound for the second inequality in Theorem 3.1 (ε_{4} resp. ε_{5}) can be derived from solving equation (3.3) if Θ is a Bernoulli distribution and from solving an expression similar to (3.3) for a general non-degenerate discrete probability distribution Θ.

4. Concluding Remarks.

Thus far we have shown that, given that the payoff from the risk dominant equilibrium is sufficiently high, or, equivalently, when the population N is sufficiently large, the expected time the evolutionary system with best reply dynamics and a stochastic mutation rate spends in the risk dominated equilibrium is systematically underestimated when one calculates this time in the conventional way by assuming a fixed mutation rate that is equal to the expected mutation rate. The crucial feature in reaching this conclusion is the minimum number of mutations needed in order to escape the basin of attraction of an equilibrium (the cost minimizing itrees, i = 0, N), as is the case in KMR and Young (1993). Since this minimum number of mutations does not change if we assume Darwinian dynamics instead of best reply dynamics as the deterministic component of the dynamics, our results go through for general deterministic Darwinian dynamics.

References

Bergin, J. and B.L. Lipman (1996). Evolution with state-dependent mutations. Econometrica

64, 943–956. Cooper, R.W. and A. John (1988). Coordinating coordination failures in keynesian models.

Quarterly Journal of Economics 103, 441–463.

Ellison, G. (1993). Learning, local interaction, and coordination. Econometrica 61, 1047–

1071. Kandori, M., G.J. Mailath, and R. Rob (1993). Learning, mutation and long run equilibria

in games. Econometrica 61, 29–56. Rhode, P. and M. Stegeman (1996). A comment on "learning, mutation, and long-run equi-

libria in games". Econometrica 64, 443–449. Young, H.P. (1993). The evolution of conventions. Econometrica 61, 57–84.

A. Explicit Expressions for the Derivatives of C (ε) and D (ε) .

Differentiating (3.1) with respect to ε, using \frac{d}{dε} (\frac{j+1}{(1−ε)^{2}} (\frac{ε}{(1−ε)})^{j}) = \frac{2(j+1)}{(1−ε)^{3}} (\frac{ε}{(1−ε)})^{j}+\frac{j(j+1)}{(1−ε)^{4}} (\frac{ε}{(1−ε)})^{j−1} ,

j ≥ 1, yields C′ (ε) = ∑_{j=1}^{N−2[z^{∗}]−2} \binom{N}{j+[z^{∗}]+1} \frac{j}{(1−ε)^{2}} (\frac{ε}{(1−ε)})^{j−1} = ∑_{j=0}^{N−2[z^{∗}]−3} \binom{N}{j+[z^{∗}]+2} \frac{j+1}{(1−ε)^{2}} (\frac{ε}{(1−ε)})^{j}and

C′′ (ε) = \binom{N}{[z^{∗}]+2} \frac{2}{(1−ε)^{3}} +∑_{j=1}^{N−2[z^{∗}]−3} \binom{N}{j+[z^{∗}]+2} \{\frac{2(j+1)}{(1−ε)^{3}} (\frac{ε}{(1−ε)})^{j} + \frac{j(j+1)}{(1−ε)^{4}} (\frac{ε}{(1−ε)})^{j−1}\} = \binom{N}{[z^{∗}]+2} \frac{2}{(1−ε)^{3}} +

∑_{j=0}^{N−2[z^{∗}]−4} \binom{N}{j+[z^{∗}]+3} \{\frac{2(j+2)}{(1−ε)^{3}} (\frac{ε}{(1−ε)})^{j+1} + \begin{matrix}(j+1) & (j+2) \\ (1−ε) & ^{4} \end{matrix} (\frac{ε}{(1−ε)})^{j}\} .

Similarly, differentiating (3.2) with respect to ε yields D′ (ε) = ∑_{j=N−2[z^{∗}]−2}^{N−[z^{∗}]−2} \binom{N}{j+[z^{∗}]+2} \frac{j+1}{(1−ε)^{2}} (\frac{ε}{(1−ε)})^{j}

and D′′ (ε) = ∑_{j=N−2[z^{∗}]−3}^{N−[z^{∗}]−3} \binom{N}{j+[z^{∗}]+3} \{\frac{2(j+2)}{(1−ε)^{3}} (\frac{ε}{(1−ε)})^{j+1} + \begin{matrix}(j+1) & (j+2) \\ (1−ε) & ^{4} \end{matrix} (\frac{ε}{(1−ε)})^{j}\}.

From these expressions and lim_{j→0} lim_{ε→0} (\frac{ε}{(1−ε)})^{j} = lim_{ε→0} lim_{j→0} (\frac{ε}{(1−ε)})^{j} = 1, we see that

C (0) = \binom{N}{[z^{∗}]+1}, when N − 2 [z^{∗}] − 2 ≥ 0, i.e. when N − 2 [z^{∗}] − 1 ≥ 1, and C (ε) = 0 for all ε ∈ [0, 1] , when N − 2 [z^{∗}] − 1 < 1,

C′ (0) = \binom{N}{[z^{∗}]+2}, when N − 2 [z^{∗}] − 3 ≥ 0, i.e. when N − 2 [z^{∗}] − 2 ≥ 1, and C′ (0) = 0, when N − 2 [z^{∗}] − 3 < 0,

C′′ (0) = 2\binom{N}{[z^{∗}]+2} + 2\binom{N}{[z^{∗}]+3} when N − 2 [z^{∗}] − 4 ≥ 0, i.e. when N − 2 [z^{∗}] − 3 ≥ 1, and C′′ (0) = 2\binom{N}{[z^{∗}]+2}, when C′ (0) > 0, i.e. when N − 2 [z^{∗}] − 2 ≥ 1, and C′′ (0) = 0, when N − 2 [z^{∗}] − 2 < 1.

Similarly, we see that D (0) = 0, when N −2 [z^{∗}]−1 ≥ 1, D′ (0) = 0, when N −2 [z^{∗}]−2 ≥ 1, and D′′ (0) = 0, when N − 2 [z^{∗}] − 3 ≥ 1.Therefore, μ′_{2} (0) = \frac{C(0)D′(0)−D(0)C′(0)}{[C(0)+2D(0)]^{2}} is equal to 0 whenever N − 2 [z^{∗}] − 2 ≥ 1.

When N − 2 [z^{∗}] − 1 = 1, the derivative D′ (ε) sums from j = 0 and consequently D′′ (ε) becomes \binom{N}{[z^{∗}]+2} \frac{2}{(1−ε)^{3}} +∑_{j=1}^{N−[z^{∗}]−2} \binom{N}{j+[z^{∗}]+2} \{\frac{2(j+1)}{(1−ε)^{3}} (\frac{ε}{(1−ε)})^{j} + \frac{j(j+1)}{(1−ε)^{4}} (\frac{ε}{(1−ε)})^{j−1}\} = \binom{N}{[z^{∗}]+2} \frac{2}{(1−ε)^{3}} +

∑_{j=0}^{N−[z^{∗}]−3} \binom{N}{j+[z^{∗}]+3} \{\frac{2(j+2)}{(1−ε)^{3}} (\frac{ε}{(1−ε)})^{j+1} + \begin{matrix}(j+1) & (j+2) \\ (1−ε) & ^{4} \end{matrix} (\frac{ε}{(1−ε)})^{j}\} . Thus, when N −2 [z^{∗}]−1 = 1, it

follows that D′ (0) = \binom{N}{[z^{∗}]+2} = \binom{N}{\frac{1}{2} N+1} and D′′ (0) = 2\binom{N}{[z^{∗}]+2} + 2\binom{N}{[z^{∗}]+3} = 2\binom{N}{\frac{1}{2} N+1} + 2\binom{N}{\frac{1}{2} N+2}.