9 Evolutionary Games in Finite PopulationS Flashcards
Chapter 9: populations are finite and change by random birth/death events
stochastic modelling
(no longer deterministic, we dont consider an infinite pop but model this stochastically)
(in ch6 we expect as infinite pop of replicator equations etc, showing fractions change according to replicator eqs)
formulation of evolutionary games in populations of finite size N (constant)
modelled in terms of Markov processes; focus on symmetric games with 2 pure strategies
evolutionary symmetric games in finite and well-mixed populations of size N =>
modelled as birth-death processes
EGT: dynamic theory of dynamic, no rationality but fitness (expected payoff), replicator dynamics
we will consider finite populations here,
can be large but finite
Population games
x(t) = (x(t), 1-x(t))^T
at each time t, the state of the population of size N is described by “stategy profile”
x(t) = (x(t), 1-x(t))^T
= x(t)e𝒸+ (1-x(t))e𝒹
with 0 ≤ x(t) ≤ 1
x(t) fraction of C in pop at time t
1-x(t) fraction of D in pop at time t
e.g
N= 10 of which 4 individuals of species C (cooperators) and
6 of species D (defectors
strategy profile
x(t) = (x(t), 1-x(t))^T
x(t) = (x(t), 1-x(t))^T
= 0.4e𝒸+ 0.6e𝒹
=(0.4,0.6)^T
How does change in time? Prob. that x=1 in the long run?
N → ∞?
Now N is finite and composition changes by random
birth/death events => x(t) fluctuates=> stochastic modelling
However, when N → ∞, we recover replicator dynamics, and
as in Chapter 6
x˙ = x(1 − x)[x(a − c) + (1 − x)(b − d)]
Population games: how we relate to evolutionary game theory
- strategies/frequencies as species fractions
- fitness here proportional to expected payoff (up to a constant)
- successful species spread
- outcomes: absorbing equilibria are x=0 (all-D) and x=1 (all-C); in an infinitely large population (when N < ∞)
( N → ∞) there is a coexistence equilibrium
payoff
A
C D
C a b
D c d
coexistence equilibrium
x˙ = x(1 − x)[x(a − c) + (1 − x)(b − d)]
when N < ∞
x∗ ≡ x∗e𝒸+ (1 − x∗)e𝒹
with
x∗ = [d-b]/[a-c+d-b]
b (with 0 < x∗ < 1),
when b>d and c> a (asymptotically stable)
d b<d and c<a (unstable).
In a finite population is metastable when b>d, c>a:
after a long-time coexistence, either C or D goes extinct
APPLIES WHEN N < ∞ finite pops
Idea of the stochastic modelling (Markov chain): assumptions
assume an “urn model” containing a constant number
of balls, say N finite (constant population size), i “balls” are of type C (red) and N-i are of type D (blue)
at each time step:draw a pair
if different colour:
one is chosen to reproduce BIRTH EVENT and offspring replaces instantaneously any other ball DEATH with some probability
otherwise: nothing happens
balls reurned to urn, always N balls
Birth and death rates are functions of the fitness of C and D
URN MODEL
assume an “urn model” containing a constant number
of balls, say N finite (constant population size), i “balls” are of type C (red) and N-i are of type D (blue)
at each time step:draw a pair
if different colour:
one is chosen to reproduce BIRTH EVENT and offspring replaces instantaneously any other ball DEATH with some probability
otherwise: nothing happens
balls reurned to urn, always N balls
Birth and death rates are functions of the fitness of C and D
MC?
=> Markov chain with absorbing boundaries at i=0 and i=N
(all balls the same colour: all blue i=0 all red i=N)
=> Since N is constant and i can change by +1 or -1, this can be viewed as a birth-death process
(relative to a reference species, say C).
=> Final state: all-C with i=N or all-D with i=0.
guaranteed to end up in one of the absorbig states
URN MODEL giving Markov chain
For a given initial condition, what is the probability to end in state all-C, with all cooperators (i=N)?
Interpretation of this Markov chain: frequency-dependent (or fitness-dependent) birth-and-death process
for a reference species (say C) in which each birth/death of C is accompanied by death/birth of D
9.2 Birth-and-death processes and evolutionary games
diagram
Dynamics by copying
and replacement
Population of finite and constant
size N, consisting of C and D individuals
diagrams showing
[N=10, i=6 if choosing 2 with different colour, transition to i+1 or i-1 with respective rates with simultaneous birth/death giving a replacement
]
[also if 2 of the same colour are chosen no transition]
λᵢ: birth rate of C in state (i, N − i)
µᵢ : death rate of C in state (i, N − i)
i= #C’s
N-I=# D’s
9.2 Birth-and-death processes and evolutionary games
explaining transitions using the urn model
λᵢ: birth rate of C in state (i, N − i)
µᵢ : death rate of C in state (i, N − i)
i= #C’s
N-I=# D’s
- Randomly pick 2 individuals in state (i, N-i)
- Nothing happens unless a CD pair is picked
- Transition i -λᵢ→ i + 1corresponds to CD - λᵢ →CC
i.e. birth of C (simultaneous death of D); t → t + dt - Transition i-µᵢ→i-1 corresponds to CD-µᵢ→DD,
i.e. death of C (simultaneous birth of D);t → t + dt - Dynamics ceases when i=N (all-C) or i=0 (allD)
=> Population is in an absorbing state and there is FIXATION of the corresponding species C or D
λᵢ: birth rate of C in state (i, N − i)
µᵢ : death rate of C in state (i, N − i)
depend on
depend on the fitness
f𝒸(i) of c
f𝒹(i) of d
so the Number of C’s at time t is X(t)
Markov chain can be seen as a fitness-dependent birth-death process on finite state space {0,1,2,..,n}
with absorbing boundaries at 0 and N
9.2 Birth-and-death processes and evolutionary games
TRANSITION MATRIX
pᵢ₊ₖ,ᵢ(∆t) =
pᵢ₊ₖ,ᵢ(∆t) =
Prob{**X(t + ∆t) − X(t} **= k|X(t) = i
= Prob{ ∆X(t)= k|X(t) = i} dep on change in # in time increment
=
{λᵢ∆t + o(∆t) if k = 1
{µᵢ∆t + o(∆t) if k = −1
{1 − (λᵢ + µᵢ)∆t + o(∆t) if k = 0
{o(∆t) otherwise
since i=0,n ABSORBING
with λ₀= λₙ = µ₀ = µₙ = 0
9.2 Birth-and-death processes and evolutionary games
CHOOSING
λᵢ
µᵢ
λᵢ= [prob. draw CD pair] ×increasing function of f𝒸(i)
= [(i/N)[(N-i)/N ] ×increasing function of f𝒸(i)
[fraction of C x fraction of D]
µᵢ = [prob. draw CD pair] ×increasing function of f𝒹(i)
= (i/N)(N-i)/N ×increasing function of f𝒹(i)
9.2 Birth-and-death processes and evolutionary games
fitnesses and expected payoff
Fitnesses
f𝒸(i) and
f𝒹(i)
in state (i,N-i)
expected payoff
Π𝒸(i)
Π𝒹(i)
f𝒸/𝒹(i)= 1-s + sΠ𝒸/𝒹(i)
(1-s + s *expected payoff)
s encoding selection strength/intensity
where expected payoff in state (i.N-i) in the absence of self interactions are:
Π𝒸(i) = a ([i-1]/[N-1]) + b ([N-i]/[N-1])
Π𝒹(i) = c([i]/[N-1]) + d([N-i-1]/[N-1])
here N-1 denominators come from no self interactions
f𝒸/𝒹(i)= 1-s + sΠ𝒸/𝒹(i)
s encoding selection strength/intensity
where expected payoff in state (i.N-i) in the absence of self interactions are:
Π𝒸(i) = a ([i-1]/[N-1]) + b ([N-i]/[N-1])
Π𝒹(i) = c([i]/[N-1]) + d([N-i-1]/[N-1])
here N-1 denominators come from no self interactions
WHAT HAPPENS AS S VARIES?
Parameter s is between 0 and 1 measures the selection “strength” or “intensity”
When s → 0 , the selection is vanishingly small: C and D have almost same fitness and the game
does not matter: λᵢ & µᵢ and don’t depend on Π𝒸/𝒹
=> when s → 0, evolution is entirely random
When s → 1, the selection is strong: fitness of C and D coincide with Π𝒸(i) and Π𝒹(i)
=> evolution dominated by outcome of stage games
1-s is a constant baseline fitness contribution added to the frequency-dependent contribution
from the stage game that is sΠ𝒸/𝒹
In practice, the parameter s is often small but non-zero. i.e. : selection is “weak
Two common choices for functions of f𝒸/𝒹
MORAN PROCESS
λᵢ=(i/N) ((N-i)/N) [f𝒸(i)/f_overline(i)]
µᵢ=(i/N) ((N-i)/N) [f𝒹(i)/f_overline(i)]
giving
µᵢ/λᵢ
=f𝒹(i) /f𝒸(i)
where the average fitness is
f_overline(i) = (1/N)f𝒸(i) + [1-(i/N)] f𝒹(i)
The dynamics with both processes is the same in the weak selection limit, i.e. when s«1
RELATES TO AVERAGE FITNESS
Two common choices for functions of f𝒸/𝒹
FERMI PROCESS
λᵢ=(i/N) ((N-i)/N) [2]/[1+ exp(f𝒹(i)-f𝒸(i))]
µᵢ=(i/N) ((N-i)/N) [2]/[1+ exp(-(f𝒹(i)-f𝒸(i))]
The dynamics with both processes is the same in the weak selection limit, i.e. when s«1
SUMMARY
here λᵢ µᵢ depend on..
these rates will depends on states and numbers of individuals of each type
λᵢ= [prob. draw CD pair] ×increasing function of f𝒸(i)
= [(i/N)[(N-i)/N ] ×increasing function of f𝒸(i)
[fraction of C x fraction of D]
µᵢ = [prob. draw DC pair] ×increasing function of f𝒹(i)
= (i/N)(N-i)/N ×increasing function of f𝒹(i)
the functions will depends on the expected payoffs ie the fitnesses of the process
we also introduced selection strength
when s is 0: fitness is the e same for both species
when s=1 baseline fitness vanishes: strong selection, dep completely on fitnesses of species
summary model
Evolution in finite population of constant size N: 2-player games with 2 pure strategies,
C and D, and of payoff matrix
A=
[a b]
[c d]
=> birth-death process for reference species (say C) with absorbing boundaries
=> outcome of games with 2 pure strategies (C and D): all-C or all-D, i.e. fixation of C or D.
Dynamics: birth and death rates according to fitness-dependent Moran/Fermi process
Selection intensity: , weak selection when 0<s«1 (biologically relevant)
Evolution & fixation probabilities in 2-player games with 2 pure strategies
Markov chains with absorbing boundaries give outcomes that are:
2 possible outcomes: fixation of either C or D
all pop C
or
all pop D
fixation probabilities
ϕᵢᶜ
ϕᵢᴰ
ϕᵢᶜ
C fixation probability starting from state (i, N-i), i.e. probability to end up in state all-C where C has
taken over (no D left), when i ̸= 0, N
(is the probability to end up in all-C when t → ∞)
probability of ending in this absorbing state
ϕᵢᴰ
D fixation probability starting from state (i, N-i), i.e. probability to end up in state all-D where D has
taken over (no C left), when i ̸= 0, N
probability of ending in the other absorbing state
clearly
ϕᵢᶜ+ϕᵢᴰ=1
meaning
ϕᵢᴰ= 1-ϕᵢᶜ
if we find c we find d
using first step analysis
ϕᵢᶜ =
fixation probability
probability that cooperation wins
end up in all C state
ϕᵢᶜ
=
([λᵢ]/[µᵢ+λᵢ]) ϕᵢ₊₁ᶜ + ([µᵢ]/[µᵢ+λᵢ]) ϕᵢ₋₁ᶜ
with boundary conditions
ϕ₀ᶜ =0 ϕₙᶜ =1
Fixation of C is certain
if initially initially i=N
(already in all-C)
SIMILAR TO RANDOM WALK
moves to left and right depend on rates, fractions relate to probabilities of births and deaths
ABSORBING BOUNDARIES
so if you start at 0 probability of 0 as absorbed here
if already start at N probability 1 guaranteed
LOOKING AT:
ϕᵢᶜ
=
([λᵢ]/[µᵢ+λᵢ]) ϕᵢ₊₁ᶜ + ([µᵢ]/[µᵢ+λᵢ]) ϕᵢ₋₁ᶜ
with boundary conditions
ϕ₀ᶜ =0 ϕₙᶜ =1
gives a 2nd-order linear map
µᵢ ϕᵢ₋₁ᶜ + λᵢ ϕᵢ₊₁ᶜ -[µᵢ+λᵢ])ϕᵢᶜ=0
solved by iteration (see notes):
ϕᵢᶜ =
[1 + Σₖ₌₁ᶦ⁻¹ ∏ⱼ₌₁ᵏ(µⱼ/λⱼ)]/
[1 + Σₖ₌₁ᴺ⁻¹ ∏ⱼ₌₁ᵏ (µⱼ/λⱼ)]
or i = 1, . . . , N and
ϕ₀ᶜ = 0
dependent on ration of death/birth rates
denominator: normalisation
i encourage you to show this yourselves (doesnt show)
considering case:
fixation of a single C “intruder/mutant
What is the proabbility that the single intruder prevails?
ϕ₁ᶜ when i=1
denoted by ϕᶜ
diagram N=10 C=1 D=9
population of D
with a single C
we say ϕ₁ᶜ≡ϕᶜ by defn here
transition to N=10 C=10 D=0
ONE SINGLE C
GIVES FIXATION
OF ALL C
what is this probability?
considering case:
fixation of a single C “intruder/mutant
we say ϕ₁ᶜ≡ϕᶜ by defn here
transition to N=10 C=10 D=0
ϕ₁ᶜ≡ϕᶜ
(called this)
= [1]/
[1+ Σₖ₌₁ᴺ⁻¹ ∏ⱼ₌₁ᵏ (µⱼ/λⱼ)]
(obtained by setting i=1 in original)
fixation probability of a single D
ϕₙ₋₁ᴰ
ϕᴰ≡ϕₙ₋₁ᴰ
= 1 - ϕₙ₋₁ᶜ
=ϕᶜ ∏ₖ₌₁ᴺ⁻¹ (µₖ/λₖ)
example: 1
neutral dynamics when C and D have same fitness
neutral dynamics when C and D have same fitness
=> no selection intensity, s=0 and
f𝒸 (i)= f𝒹(i) =1
meaning
λᵢ = µᵢ = [i(N-i)]/[N^2]
and
ϕᵢᶜ = [1+i-1]/[1+N-1] = i/N (same as initial fraction of i in population)
and
ϕᶜ = 1/N = ϕᴰ
(ϕᵢᶜ from λᵢ/µᵢ=1)
so if no selection is 0, proability that a single C out of 10 individuals fixates the population is 1/10 if N=10
Example 2: when C and D have constant fitness,
used in
MORAN PROCESS
λᵢ=(i/N) ((N-i)/N) [f𝒸(i)/f_overline(i)]
µᵢ=(i/N) ((N-i)/N) [f𝒹(i)/f_overline(i)]
giving
µᵢ/λᵢ
=f𝒹(i) /f𝒸(i)
where the average fitness is
f_overline(i) = (1/N)f𝒸(i) + [1-(i/N)] f𝒹(i)
f𝒸 (i) = r = constant and f𝒹(i) = 1 ,
(species have constant finesses but fitnesses differ )
if r>1 C is fitter than D
if r<1 D is fitter than C
with the fitness dependent moran process we have: (replacing fitnesses with r and 1)
λᵢ=(i/N) ((N-i)/N) [r/[(1/N)r + [1-(i/N)]] = r[i(N-i)]/[N^2]
µᵢ=(i/N) ((N-i)/N) [1/(1/N)r + [1-(i/N)]] = [i(N-i)]/[N^2]
giving
µᵢ/λᵢ
=1 /r
where the average fitness is
f_overline(i) = (1/N)r + [1-(i/N)]
ϕᵢᶜ= [1 + Σₖ₌₁ᶦ⁻¹ ∏ⱼ₌₁ᵏ(µⱼ/λⱼ)]/
[1 + Σₖ₌₁ᴺ⁻¹ ∏ⱼ₌₁ᵏ (µⱼ/λⱼ)]
= [1 + Σₖ₌₁ᶦ⁻¹ r⁻ᵏ]/
[1 + Σₖ₌₁ᴺ⁻¹ r⁻ᵏ]
=[rᴺ⁻ᶦ(rᶦ-1)]/[rᴺ-1]
ϕᶜ =[rᴺ⁻¹(r-1)]/[rᴺ-1]
= [1-r⁻¹]/[1-r⁻ᴺ]
for N»1
ϕᶜ→
{1-r⁻¹ if r>1
{rᴺ⁻¹(1-r) if r<1
using the geometric progression
(makes sense as r<1 corresponds to fitness of C less than D etc)
Comparison with neutral case:
We say that selection
favours the fixation of C if ϕᶜ > 1/N
and
opposes it if ϕᶜ < 1/N
Similarly, selection
favours the fixation of D if ϕᴰ>1/N
and
opposes it if ϕᴰ < 1/N
q3 ps5
here ϕᴰ = ϕᶜ ∏ₖ₌₁ᴺ⁻¹ (1/r) = [r-1]/[r^N -1]
=> When r>1 and N»1, fixation of C is favoured by selection
=> When r<1 and N»1, fixation of C is opposed by selection
for large N
N»1
=> When r>1 and N»1, fixation of C is favoured by selection
ϕᶜ→ 1 − 1/r > 1/N
=> When r<1 and N»1, fixation of C is opposed by selection
ϕᶜ→ rN ≈ 0 and <1/N
9.4 Fixation in sym. 2-player games with 2 pure strategies & freq.-dependent finesses
In evolutionary game theory, fitness is generally frequency dependent with explicit functions
We know consider no longer constant finesses but those which are functions
f_{c/D}(i) explicit functions
MORAN PROCESS
f𝒸/𝒹(i)= 1-s + sΠ𝒸/𝒹(i)
µᵢ/λᵢ =f𝒹(i)/f𝒸(i)
ratio in this case
FERMI PROCESS
f𝒸/𝒹(i)= 1-s + sΠ𝒸/𝒹(i)
µᵢ/λᵢ =exp(f𝒹(i) - f𝒸(i))
For the fitness-dep. Moran process:
ϕᵢᶜ
using
ϕᵢᶜ= [1 + Σₖ₌₁ᶦ⁻¹ ∏ⱼ₌₁ᵏ(µⱼ/λⱼ)]/
[1 + Σₖ₌₁ᴺ⁻¹ ∏ⱼ₌₁ᵏ (µⱼ/λⱼ)]
ϕᵢᶜ= [1 + Σₖ₌₁ᶦ⁻¹ ∏ⱼ₌₁ᵏf𝒹(i)/f𝒸(i)]/
[1 + Σₖ₌₁ᴺ⁻¹ ∏ⱼ₌₁ᵏ f𝒹(i)/f𝒸(i)]
generally complicated nonlinear
functions of j
For the Fermi process
ϕᵢᶜ
using
ϕᵢᶜ= [1 + Σₖ₌₁ᶦ⁻¹ ∏ⱼ₌₁ᵏ(µⱼ/λⱼ)]/
[1 + Σₖ₌₁ᴺ⁻¹ ∏ⱼ₌₁ᵏ (µⱼ/λⱼ)]
ϕᵢᶜ= [1 + Σₖ₌₁ᶦ⁻¹ ∏ⱼ₌₁ᵏexp(f𝒹(j) - f𝒸(j))]/
[1 + Σₖ₌₁ᴺ⁻¹ ∏ⱼ₌₁ᵏ exp(f𝒹(j) - f𝒸(j))]
here we could re-write using exponential property of sum in products
generally complicated nonlinear
functions of j
The case i=1 (fixation of a single cooperator) under weak selection, 0<s«1, is of particular interest.
Weak selection, allows to simplify the analysis because if s is small, we have
f𝒹(i)/f𝒸(i)
f𝒹(i)/f𝒸(i)
≈ 1 + s(Π𝒹(i) − Π𝒸 (i))
and
exp(f𝒹(i)−f𝒸(i)) ≈ 1 + s(Π𝒹(i) − Π𝒸(i))
expanding to first order in s for small s
gives same result as the two processes
Σⱼ₌₁ᵏ[f_D(j) − f_C (j)]
Σⱼ₌₁ᵏ[f_D(j) − f_C (j)]
= s Σⱼ₌₁ᵏ[Π𝒹(j) − Π𝒸(j))]
by defn
= [sk]/[2(N-1)][(b + c − a − d)(k + 1) + 2(d − b)N − 2(a − d)]
Upon neglecting terms of order , under weak selection, with 0<s«1 and Ns«1,
ϕC ≈
ϕᶜ
≈[1/N][1 − (s/6) ({a + 2b − c − 2d} N − {2a + b + c − 4d})]⁻¹
to first order in Ns«1
The idea of the derivation of this result is outlined in the lecture notes, and the complete derivation
is covered in a question Q1 of Example Sheet 5.
This result is valid under weak selection for the dynamics with both Moran and Fermi processes
Hence using a Taylor expansion in s, we have found
Similarly, when 0<Ns«1,
ϕᶜ
≈
Under weak selection, when Ns«1, the fixation probability of a single C for the fitness-dependent
Moran and Fermi processes is
ϕᶜ
≈[1/N][1 − (s/6)((αN + β)]⁻¹
where ,
α ≡ a + 2b − c − 2d
β ≡ 4d − (2a + b + c)
and terms of order Ns^2 and higher have been neglected
SO USING
Under weak selection, when Ns«1, the fixation probability of a single C for the fitness-dependent
Moran and Fermi processes is
ϕᶜ
≈[1/N][1 − (s/6)((αN + β)]⁻¹
where ,
α ≡ a + 2b − c − 2d
β ≡ 4d − (2a + b + c)
and terms of order Ns^2 and higher have been neglected
if i gave you payoff matrix a,b,c,d
you can work out alpha and beta
then for small s with constant finite pop size N
and thus work out
ϕᶜ
ϕᴰ
Hence using a Taylor expansion in s, we have found
Similarly, when 0<Ns«1,
ϕᴰ
≈
ϕᴰ
≈
[1/N] [a+(s/6)(α_overlineN + β_overline]
where
α_overline ≡ 2(c − a) + d − b,
β_overline ≡ 4a − (2d + b + c)
,
Influence of selection on evolution:
When does selection favour or oppose fixation of C?
Comparison with fixation in the absence of selection,
when ϕᶜ = 1/N (s=0)
⇒
ϕᶜ >1/N
C has higher fixation probability under selection pressure than without
=> selection favours fixation of C
ϕᶜ <1/N
If C has lower fixation probability under selection pressure than without
=> selection opposes fixation of C
SUMMARY
Under weak selection (0<Ns«1):
Condition favouring fixation of C is
Nϕᶜ > 1 ⇒ 1 +(s/6)
(αN + β) > 1
⇒
αN + β > 0
SUMMARY
Under weak selection (0<Ns«1):
Condition opposing fixation of C is
Nϕᶜ < 1
⇒
1 +(s/6)(αN + β) < 1 ⇒ αN + β < 0
summary fixation
we look at the probabilities of everyone ending up being all C or all D
e.g if only one defector in a sea of cooperators
what is the probability that a single defector takes over. We looked at examples of these
we looked at the case where both have same fitness and we saw the prob of a single intruder taking over being 1/N (absence of selection)
we saw case of different but constant fitness
and we saw the case for fitness of both types dependent on population composition, in which case analysis is found by evaluating the formulae
(1 +sum)/(1+sum)
which boils down to a fomula 1/N[1+(s/6)(alpha N+beta] when Ns is small ie weak selection
allows us to compare selection
and what happens in absence of selection s=0
in example sheet 5 we see more
Evolutionary games in finite population are modelled as birth-death processes with
absorbing boundaries. 2-player games with 2 pure strategies (C and D) in population of constant size N leads to fixation of C or D => discussion of fixation probability, especially in the weak selection limit
individuals type C asi
# D as N-i
which changes according to birth and death process
with 2 absorbing boundaries at i=N and i=0
we look at prob we end up in one of the absorbing states
important case arises when i=1
For 2-player games with 2 pure strategies, C and D, with payoff matrix ,
in a population of constant size N, under weak selection s (0<Ns«1)
C D
C a b
D c d
small s
what does small s mean?
when s is small then: we have contribution of baseline (1-s) and contribution from expected payoff
when s is close to 1: fitness of each type correspond to expected payoff of each game
what is the fixation of a single C
For 2-player games with 2 pure strategies, C and D, with payoff matrix ,
in a population of constant size N, under weak selection s (0<Ns«1)
C D
C a b
D c d
small s
ϕC ≈
1/N [1 + (s/6)*(αN + β)]
where
with
α = a − c + 2(b − d),
β = 4d − (2a + b + c)
SO IF I GIVE YOU PAYOFF AND ASK THIS YOU SUBSTITUTE TO FIND if selection weak
what is the fixation of a single C
For 2-player games with 2 pure strategies, C and D, with payoff matrix ,
in a population of constant size N, under weak selection s (0<Ns«1)
C D
C a b
D c d
s=0
no selection means
ϕC =1/N
both types same fitness, evolution only by pure chance
0<Ns<1
Condition opposing fixation of C is
Nϕᶜ < 1
[1 + (s/6)*(αN + β)]
< 1 ⇒
αN + β < 0
selection will oppose c fixation
Condition favouring fixation of C is
Nϕᶜ > 1
[1 + (s/6)*(αN + β)]
αN + β > 0
selection will oppose C fixation
e.g this one satisfied if both alpha and beta are positive
Nϕᶜ > 1
implies
condition favouring fixation of C and also implies
{any N > 0 if α, β > 0
{never if α, β < 0
{N > −β/α if α > 0, β < 0
{0 < N < −β/α if α < 0, β > 0
last 2 only matter if N not too large
we can use this if selection weak, Ns small
When the selection favours the fixation of C
depends on N (weak selection)
When N is large and selection is weak, with N»1 and Ns«1,
Nϕᶜ >1
if
Nϕᶜ <1
if
(ie neclecting terms that dont depend on N in a(N-2) +b(2N-1) >c(N+1)+2d(N-2)
Nϕᶜ > 1
if
α > 0 ⇐⇒ a + 2b > c + 2d
Nϕᶜ <1
if
α < 0 ⇐⇒ a + 2b < c + 2d
An interesting situation arises for coordination games, for which a > c and d > b
We remember that when the dynamics is given by the replicator equations (REs) and they
say that the absorbing states all-C and all-D correspond to evolutionary stable states (ESSes),
x=1 and x=0
and there is an unstable coexistence equilibrium at a frequency
x*= (d-b)/(a-c+d-b)
of C
since
Nϕᶜ > 1
when
a + 2b > c + 2d ⇒ a − c > 2(d − b)
if N»1 and 0<Ns«1
under this condition we have
x* = [d-b]/[a-c+d-b]
< [d-b]/[2(d-b) +(d-b)
=1/3
if N»1 and 0<Ns«1
Hence, under weak selection and in a large (but finite) population, N»1 and 0<Ns«1, selection favours in coordination games if , i.e. if the basin of attraction of x* is greater than 2/3
one third law
Hence, under weak selection and in a large (but finite) population, N»1 and 0<Ns«1, selection favours in coordination games if , i.e. if the basin of attraction of x* is greater than 2/3
diagram
ϕᶜ >1/N | ϕᶜ<1/N
|————-|——————-|
all D all C
x=0 1/3 x=1
SO UNDER THESE CONDITIONS the LOCATION of x* will tell us if fixation FAVOURS/OPPOSES
if we find x* <1/3 we have selection favours fixation of C
if >1/3 selection opposes the fixation of C
one third law notions
Hence, under weak selection and in a large (but finite) population (
𝑁≫1 and
0<Ns≪1), selection favors the mixed strategy 𝑥∗ in coordination games if the basin of attraction of 𝑥∗ is greater than
2/3 . This means that more than
2/3 of the population should be inclined to adopt
𝑥∗, ensuring that the mixed strategy is stable and favored by selection.
summary recap so far
We have seen that in a finite population :
- Outcome is fixation of either C or D => final state is either all-C or all-D (there is no coexistence)
- A single C intruder has a chance to fixate which has a simple expression under weak selection
- Selection can either favour or oppose the fixation of either species, under conditions that depend on N
ie we eventually end up in an absorbing state
> Notion of evolutionary stability has to be modified: ESS instead ESSₙ
Evolutionary stability in finite populations
ESS_N
conditions for an ESS_N
in prev chapters for N large payoff matrix ESS if d>b d payoff for ESS
In a finite population of constant size N, there are two conditions to be satisfied simultaneously for D to be “evolutionary stable in a finite population”
ESS_N CONDITIONS
(i) “Selection opposes C invading D” (invasion condition) => fitness of D has to be greater than fitness of C “invading single mutant” C:
f𝒹(1) > f𝒸 (1) ⇐⇒ Π𝒹(1) > Π𝒸(1)
As seen in Chapter 5, this means that D are fitter than C
(ii) “Selection opposes C replacing D” (replacement condition) =>
ϕᶜ < 1/N
(⇒ Nϕᶜ < 1)
This means that a single C mutant is less likely to fixate than by pure chance (when s=0).
In a finite population of constant size N, there are two conditions to be satisfied simultaneously for D to be “evolutionary stable in a finite population”
ESS_N CONDITIONS
derived further
Using the expressions of Π𝒸𝒹
condition (i): N(d − b) > 2d − (b + c)
Under weak selection, 0<Ns«1,
condition (ii) yields:
c(N + 1) + 2d(N − 2) > a(N − 2) + b(2N − 1)
when N»1 large but finite and 0<NS«1
ii becomes
c+2d>a+2b
equivalent to
x∗ = [d − b]/[a − c + d − b] > 1/3
Conditions (i) and (ii) for evolutionary stability in a finite population depend on the population
size N. For the case of D being :
summary
- If N is small: the condition d>b is neither sufficient nor necessary for D to be ESS_N
(d>b is necessary and sufficient for D to be ESS when , N=infinity) see Chapters 5 & 6 - If N is large but finite, the condition d>b is necessary but not sufficient for D to be
: in addition, it is necessary that
ϕᶜ<1/N
worked examples in full lecture notes …..
and sheet 5
LEVEL 5
Gillespie algorithm
The Gillespie algorithm is a simulation method that allows us to simulate exactly the dynamics
prescribed by the master equation (ME) associated with a continuous-time Markov chain
birth and death Markov processes
usually master eq difficult to solve
Level 5
consider the case of two-player symmetric games with 2 pure strategies, C and D, and payoff matrix
C D
C a b
D c d
Number of C individuals at time t is X(t) t in i ∈ {0, 1, . . . , N}
TRANISITION MATRIX ELEMENTS
probability in time step that
given X(t) we have difference
pᵢ₊ₖ,ᵢ(∆t) = Prob{X(t + ∆t) − X(t) = k|X(t) = i} =
=
{λᵢ∆t + o(∆t) if k = 1
{µᵢ∆t + o(∆t) if k = −1
{1 − (λᵢ + µᵢ)∆t + o(∆t) if k = 0
{o(∆t) otherwise
where
λᵢ: birth rate of C in state (i, N − i)
µᵢ : death rate of C in state (i, N − i)
BIRTH AND DEATH PROCESS
BIRTH AND DEATH PROCESS
MASTER EQUATION
BALANCE EQUATION
(d/dt)pᵢ(t) = λᵢ₋₁pᵢ₋₁(t) + µᵢ₊₁pᵢ₊₁(t) − (λᵢ + µᵢ) pᵢ(t),
for i = 1, 2, . . . , N − 1
gain terms and loss terms!!!
(d/dt)p(t) = µ₁p₁(t),
and
(d/dt)pₙ(t) = λₙ₋₁pₙ₋₁(t)
Absorbing states at i=0 and i=N =>
λ_0 = µ_0 = λ_N = µ_N = 0
initially what do we have…
Initially 0<k<N individuals of type C
=> final state is all-C with probability ϕₖᶜ
or all D with prob 1 − ϕₖᶜ
Simulation with the Gillespie algorithm in 4 steps:
1) Generate 2 random numbers .r_1 and r_2 uniformly distributed in [0,1] At time X(t)=i
2) Get the so-called “propensity function” λ_i + µ_i of the currents state (i,N-i)
3) The waiting time τ to the next transition (i,N-i) - C birth or death ->(i ± 1, N ∓ 1 − i)
is exp(-(λ_i + µ_i)τ( => transition occurs at time t +τ with τ= - ln(r_i)/(λ_i + µ_i))
4) Update the state at time :t +τ
if 0 ≤ r2 ≤ λ_i/(λ_i + µ_i)
birth of C and death of D => new state is (i+1, N - 1 - i)
if r_2 > λ_i/(λ_i + µ_i) death of C and birth of D => new state is (i-1, N + 1 - i)
Repeat steps 1-4 until an absorbing state, either all-C (i=N) or all-D (i=0) is reached.
ALLOWS TO SIMULATE PROCESS DESCRIBED BY ME
in practice, the fixation probability ϕₖᶜ is computed by generating a large number M of long sample paths
with the above algorithm for long enough for fixation to occur: Mc will end up in all-C and M-Mc in all-D
Fixation probability ϕₖᶜ is thus ϕₖᶜ=M_C/M
proportion of times you end up in the absorbing state C
why τ= - ln(r_i)/(λ_i + µ_i))
In Chapter 8, we have seen that the cumulative distribution of waiting time Ti is
F_i(t)
=Prob(Ti ≤ t) = 1 − e−(λi+µi)t
According to Theorem 9.1:
T_i= F_i ^-1(1-r~) = F_i^-1 =- ln(r_i)/(λ_i + µ_i))
, where r and r~ are random number
uniformly distributed between [0,1].
here Tau =T_i
The Gillespie algorithm is reliable and efficient because
because the time increment is drawn from the exact waiting time (exponential) distribution. It can be generalized to multivariate processes (> 2 species
The Gillespie algorithm replicates the ME and reproduces the absorption/fixation properties of the Markov chain
metastability
When , the replicator equation (deterministic ODE) can predict the stable coexistence and that the absorbing states are unstable. That’s the case in anti-coordination games, like the hawk-dove game. In this case, when , fluctuations still cause fixation in either all-C or all-D, but this occurs after a time that grows exponentially with t. This is an example where the coexistence in a finite population
is not stable but metastable.
The phenomenon of metastability stems from stochastic effects arising from fluctuations due to random birth and death events occurring in a finite population is; it is well captured by Gillespie simulations.
not technically stable as after a very very very very long time will leave
note in e.g
The mean-field approximation consists of neglecting all fluctuations,
and treat the finite population as if it was infinitely large =>
The mean-field approximation cannot properly capture phenomena that are driven by fluctuations (e.g. fixation, metastability)
Simulations with the Gillespie algorithm for a population of finite size N show that after
spending a time that grows dramatically with N around x=1/2 (metastable coexistence state),
there is absorption into the state x=0 or x=1, with probability that can be determined
from the sample paths, as above.
This stochastic phenomenon cannot be captured by the (deterministic) mean-field
approximation. However, it can be described accurately by Gillespie simulations
EXAMPLE
consider the system with birth and death rates
λⱼ = (j/2N)(1 − j/N)
and
µⱼ = (j^2/N^2)(1 − (j/N))
> birth-death process with absorbing states
j=0 and j=N
ME gives
x_1 = E((X(t)/N)), x2 = E((X(t)/N)^2), x_3 = E((X(t)/N)^3)
From the ME, we obtain the equation for
N (dx_1/dt) = SUM_j=0 to N (λ_j − µ_j )p_j (t) = · · · = (x_1 − x_2)/2 − (x_2 − x_3)
infinite set of coupled ODES? what do we do?
Resort to mean-field approximation (uncontrolled) =>
we assume
x≡ x_1,
x_2 ≈ x^2,
x_3 ≈ x^3
and get the ODE:
N(dx/dt)= (x/2)(1-x) - x^2(1-x)
=x(1-x)[0.5-x]
giving
x=1/2 is stable (if we neglect all fluctuations)
x=0, 1 are unstable absorbing states
