Stochastic dynamics in finite populations

In infinite, well-mixed population, the fraction of players can change continuously, as described by the replicator dynamics in well-mixed populations. But in finite populations of size Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} , the fraction must change at least by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/N} .

In this case microscopic probabilities have to defined that describe how a player switches strategy, as in spatial evolutionary games. There are many ways to define such microscopic evolutionary process. In each of them, strategies that lead to higher payoffs are more likely to spread in the population. For example, two players can be chosen at random to compare their payoffs. The probability that a player adopts the strategy of the other player can be a linear function of the payoff difference. If only better strategies are adopted, the direction of the dynamics becomes deterministic in 2×2 games. But if also worse strategies are sometimes adopted with a small probability, then even a dominant strategy will only take over the population with a certain probability. This approach provides a natural connection between evolutionary game theory and theoretical population genetics, where such probabilities are routinely studied.

Besides the game, two parameters describe the dynamics: The population size Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} and the intensity of selection Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w} , which measures how much the adoption of someone else’s strategy depends on the payoffs. If the product of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} is small, one speaks of weak selection and the dynamics is a small correction to random drift. If the product is large, then a deterministic replicator equation is recovered from finite population dynamics.

For weak selection, several new features appear in the system: In a bistable situation, one strategy can displace the other. Thus, a new concept of evolutionary stability is necessary. If we consider a single mutant in a population of size Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} , it will take over the population with probability Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/N} without selection, because each individual is equally likely to eventually become the ultimate ancestor. Adding a little amount of selection, a mutant is first disfavored in a bistable situation, but once it has reached a critical fraction, it is favored. The probability that a mutant will take over is a global measure for this process. Interestingly, this probability is larger than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/N} if the mutants become advantageous at a frequency larger than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/3} and smaller then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/N} otherwise, independent of the other details of the underlying game. This result holds for many evolutionary processes under weak selection. Using tools from population genetics, it can be proven that it holds for all processes within the domain of Kingman’s coalescence.

Rock-Paper-Scissors game

Blabla.

Payoff matrix: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{matrix}~&\begin{matrix}\ \ R\quad & S\quad & P\quad\end{matrix} \\ \begin{matrix}R\\S\\P\end{matrix}& \begin{pmatrix}0 & \frac{s}{2} & -1 \\ -1 & 0 & 2+s \\ \frac{1+s}{3} & -1 & 0\end{pmatrix}\end{matrix} }

Fixed point: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{\mathbf x} = \left(\frac12,\frac13,\frac16\right)}

Deterministic Dynamics

Replicator dynamics

Replicator-Mutator dynamics

Stochastic Dynamics

Stochastic differential equations

Stochastic differential equations, with mutations

Individual Based Simulations

Individual based simulations

Individual based simulations, with mutations

From finite to infinite populations

File:SDE vs IBS Performance

Performance comparison of individual based simulations (IBS) versus stochastic differential equations (SDE). a ratio of the CPU times Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle CPU_\text{SDE}/CPU_\text{IBS}} as a function of the population size, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} , and the number of strategic types, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} . The bold contour indicates equal performance. For small Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} and large Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} IBS are faster (red region), but for larger Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} and smaller Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} SDE are faster (blue region). Each contour indicates a performance difference of one order of magnitude. b computational time with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d=10} as a function of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} for IBD (red) and SDE (blue). As a reference for the scaling Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N^2} (red) and a constant (blue) are shown. c computational time with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N=5000} as a function of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} for IBD (red) and SDE (blue). As a reference for the scaling Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d^{1/2}} (red) and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d^3} (blue) are shown. For a proper scaling argument much larger Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} are required but already Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d=100} far exceeds typical evolutionary models and hence is only of limited relevance in the current context. All comparisons use a constant payoff matrix and the local update process (such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\mathcal A}_k(\mathbf x)=0} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma(\pi_j, \pi_k)=1/2} ), a mutation rate of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/N} and are based on at least Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1000} time steps as well as at least one minute running time. CPU time is measured in milliseconds required to calculate Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1000} time steps. The time increment for the SDE is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle dt=0.01} .

In unstructured, finite populations of constant size, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} , consisting of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} distinct strategic types and with a mutation rate, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu} , evolutionary changes can be described by the following class of birth-death processes: In each time step, one individual of type Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} produces a single offspring and displaces another randomly selected individual of type Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} . With probability Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1-\mu} , no mutation occurs and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} produces an offspring of the same type. But with probability Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu} , the offspring of an individual of type Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i\neq j} ) mutates into a type Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} individual. This results in two distinct ways to increase the number of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} types by one at the expense of decreasing the number of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} types by one, hence keeping the population size constant. Biologically, keeping $N$ constant implies that the population has reached a stable ecological equilibrium and assumes that this equilibrium remains unaffected by trait frequencies. The probability for the event of replacing a type $k$ individual with a type $j$ individual is denoted by $T_{kj}$ and is a function of the state of the population $\mathbf {X} =(X_{1},X_{2},\ldots X_{d})$, with $X_{n}$ indicating the number of individuals of type $n$ such that $\textstyle \sum _{n=1}^{d}X_{n}=N$.

For such processes we can easily derive a Master equation:

$P^{\tau +1}({\mathbf {X} })=P^{\tau }({\mathbf {X} })+\!\sum _{j,k=1}^{d}\!P^{\tau }({\mathbf {X} }_{j}^{k})T_{kj}({\mathbf {X} }_{j}^{k})-P^{\tau }({\mathbf {X} })\ T_{jk}({\mathbf {X} }))$

where $P^{\tau }({\mathbf {X} })$ denotes the probability of being in state $\mathbf {X}$ at time $\tau$ and ${\mathbf {X} }_{j}^{k}=(X_{1},\ldots X_{j}-1,\ldots X_{k}+1,\ldots X_{d})$ represents a state adjacent to $\mathbf {X}$. For large but finite $N$ the Kramers-Moyal expansion yields a convenient approximation in the form of a Fokker-Planck equation:

${\dot {\rho }}({\mathbf {x} })=-\sum _{k=1}^{d-1}{\frac {\partial }{\partial x_{k}}}\rho ({\mathbf {x} }){\mathcal {A}}_{k}({\mathbf {x} })+{\frac {1}{2}}\sum _{j,k=1}^{d-1}{\frac {\partial ^{2}}{\partial x_{k}\partial x_{j}}}\rho ({\mathbf {x} }){\mathcal {B}}_{jk}({\mathbf {x} })$

where ${\mathbf {x} }={\mathbf {X} }/N$ represents the state of the population in terms of frequencies of the different strategic types and $\rho ({\mathbf {x} })$ is the probability density in state $\mathbf {x}$. The drift vector ${\mathcal {A}}_{k}({\mathbf {x} })$ is given by

${\mathcal {A}}_{k}({\mathbf {x} })=\sum _{j=1}^{d}{\Big (}T_{jk}({\mathbf {x} })-T_{kj}({\mathbf {x} }){\Big )}=-1+\sum _{j=1}^{d}T_{jk}({\mathbf {x} })$

For the second equality we have used $\textstyle \sum _{j=1}^{d}T_{kj}({\boldsymbol {x}})=1$, which simply states that a $k$-type individual transitions to some other type (including staying type $k$) with probability one. ${\mathcal {A}}_{k}({\mathbf {x} })$ is bounded in $[-1,d-1]$ because the $T_{jk}$ are probabilities.

The diffusion matrix ${\mathcal {B}}_{jk}({\mathbf {x} })$ is defined as

${\begin{aligned}{\mathcal {B}}_{jk}({\mathbf {x} })&=-{\frac {1}{N}}\left[T_{jk}({\mathbf {x} })+T_{kj}({\mathbf {x} })\right]\quad {\rm {for}}\quad j\neq k\\{\mathcal {B}}_{jj}({\mathbf {x} })&={\frac {1}{N}}\sum _{l=1,l\neq j}^{d}{\Big (}T_{jl}({\mathbf {x} })+T_{lj}({\mathbf {x} }){\Big )}\end{aligned}}$

Note that the diffusion matrix is symmetric, ${\mathcal {B}}_{jk}({\mathbf {x} })={\mathcal {B}}_{kj}({\mathbf {x} })$ and vanishes as $\sim 1/N$ in the limit $N\to \infty$.

The noise arising through demographic changes and mutations is uncorrelated in time and hence the Itô calculus can be applied to derive a Langevin equation

${\dot {x}}_{k}={\mathcal {A}}_{k}({\mathbf {x} })+\sum _{j=1}^{d-1}{{\mathcal {C}}_{kj}({\mathbf {x} })}\xi _{j}(t)$

where the $\xi _{j}(t)$ represent uncorrelated Gaussian white noise with unit variance, $\langle \xi _{k}(t)\xi _{j}(t^{\prime })\rangle =\delta _{kj}\delta (t-t^{\prime })$. The matrix ${{\mathcal {C}}({\mathbf {x} })}$ is defined by ${\mathcal {C}}^{T}({\mathbf {x} }){\mathcal {C}}({\mathbf {x} })={\mathcal {B}}({\mathbf {x} })$ and its off-diagonal elements are responsible for correlations in the noise of different strategic types. In the limit $N\to \infty$ the matrix ${\mathcal {C}}({\mathbf {x} })$ vanishes with $\sim 1/{\sqrt {N}}$ and we recover a deterministic replicator mutator equation.

References

• Traulsen, A., Claussen, J. C. & Hauert, C. (2012) Stochastic differential equations for evolutionary dynamics with demographic noise and mutations. Phys. Rev. E in print.
• Traulsen, A., Claussen, J. C. & Hauert, C. (2006) Coevolutionary dynamics in large, but finite populations. Phys. Rev. E 74 011901.
• Traulsen, A., Claussen, J. C. & Hauert, C. (2005) Coevolutionary Dynamics: From Finite to Infinite Populations. Phys. Rev. Lett. 95 238701.