Transcript Evolution of cooperation

Evolution: Games,
dynamics and algorithms
Karen Page
Bioinformatics Unit
Dept. of Computer
Science, UCL
Evolution
 Darwinian evolution is based on three fundamental
principles: reproduction, mutation and selection
 Concepts like fitness and natural selection are best
defined in terms of mathematical equations
 We show how many of the existing frameworks for the
mathematical description of evolution may be derived
from a single unifying framework
Summary of what will be
discussed
 Games, evolutionary game theory
 Key frameworks of evolutionary dynamics
 Deriving a unifying framework
 An application to Fisher’s Fundamental Theorem
 Relationship with Genetic Algorithms
What is game theory?
 Formal way to analyse interactions between agents who
behave strategically
 Mathematics of decision making in conflict situations
 Usual to assume players are “rational”
 Widely applied to the study of economics, warfare,
politics, animal behaviour, sociology, business, ecology
and evolutionary biology
Assumptions of game
theory
 The game consists of an interaction between two or
more players
 Each player can decide between two or more welldefined strategies
 For each set of specified choices, each player gets a
given score (payoff)
The Prisoners’ Dilemma
 Probably most studied of all games
 Not enough evidence to convict two suspects of armed robbery,
enough for theft of getaway car
 Both confess (4 years each), both stay quiet (2 years each), one
tells (0 years) the other doesn’t (5 years)
 Stay quiet= cooperate (C) ; confess = defect (D)
 Payoff to player 1:
player2


C D
C  R S 


player1
D  T P 
R is REWARD for mutual cooperation =3
S SUCKER’s payoff
=0
T TEMPTATION to defect
=5
P PUNISHMENT for mutual defection=1
with T>R>P>S
The problem of
cooperation
 What ever player 2 does, player 1
does better by defecting:
C
pl.1 
D
pl. 2

C
3

5
D
0

1
 Classical game theory
both players D
 Shame because they’d do better by both cooperating
 Cooperation is a very general problem in biology
 Everyone benefits from being in cooperative group, but
each can do better by exploiting cooperative efforts of
others
Trade wars and cartels
Import tariffs - Should countries remove them?
Price fixing- why not cheat?
Repeated games
In many situations, typically players interact
repeatedly- repeated Prisoners Dilemma
Strategies can involve memory, use reciprocity
Tit-for-tat
Pavlov
Game theory and a
computer tournament
Game theory says it is rational to defect in
single game or fixed number of rounds
Axelrod’s tournament- double victory for Titfor-Tat
Evolutionary Game Theory
So how can cooperation be
explained?
Evolutionary games
 John Maynard Smith- evolution of animal behaviour
 Behaviour shaped by trial and error- adaptation
through natural selection or individual learning
 Players no longer have to be ‘rational’: follow instincts,
procedures, habits rather than computing best strategy.
 Games played in a population. Scores are summed.
Strategies which do well against the population on
average propagate.
 Phenotypic approach to evolution
 Frequency-dependent selection
Simple evolutionary game
simulations
 Everyone starts with a random strategy
 Everyone population plays game against everyone else
 The payoffs are added up
 The total payoff determines the number of offspring
(Selection)
 Offspring inherit approximately the strategy of their
parents (Mutation)
 [Note similarity to genetic algorithms.]
 [Nash equilibrium in a population setting- no other
strategy can invade]
Evolution in the Prisoners’
Dilemma




Standard evolutionary game (random interactions)
 all Defect
Modifications- spatial games: Interactions no longer
random, but with spatial neighbours:
Sum scores. Player with highest score of 9 shaded
takes square (territory, food, mates) in next
generation
Some degree of cooperation evolves!
Simulations of the spatial
Prisoners Dilemma
75 generations
Winner-takes-all
selection
No mutation
Red=d(d last)
Blue=c(c last)
Yellow=d(c last)
Green=c(d last)
Conclusions on
Evolutionary Games
 Game theory can be applied to studying animal and
human behaviour (economics - evolutionary biology).
 Often traditional game theory’s assumption of
‘rationality’ fails to describe human/ animal behaviour
 Instead of working out the optimal strategy, assume
that strategies are shaped by trial and error by a
process of natural selection or learning. This can be
modelled by evolutionary game theory.
 Space can matter
Evolutionary dynamics
General framework
Quasispecies
equation
Replicator-mutator
equation
Lotka-Volterra
equation
replicator-mutator
Price equation
Game dynamical
equation
Price
equation
replicator
Price equation
Adaptive dynamics
The replicator equation
 Replicator equation describes evolution of frequencies of
phenotypes within a population with fitnessproportionate selection
 Eg. game theory, replicators like “Game of Life”
 Frequency of type i is y and fitness of type i is f i then
i

y i  y i ( f i ( y )  f ( y )),
where f ( y )  i yi f i ( y )
The equivalence with
Lotka Volterra equations
 Lotka Volterra systems of ecology describe the numbers
of animals (eg. fish) of different species and are of the
form:

xi  xi f i ( x )
where xi is the abundance of species i, fi its fitness and
there are n species in total.
 Often these interacting species oscillate in abundance.
 There is a precise equivalence with the replicator system
for (n+1) types given by the substitution
yi  xi ( X  1) i  1,, n yn 1  1 ( X  1) .
Replicator equation with
mutation and quasispecies
 Suppose there are errors in replicating. The probability
of type j mutating to type i is q ji .
 We obtain a replicator equation with mutation:

yi   j y j f j ( y )q ji  f ( y ) yi
 The equivalent with numbers rather than frequencies of
types is

xi   j x j f j q ji
 When the fitnesses do not depend on frequencies, this is
the quasispecies eqn. (Probably the case in most GAs?)
Quasispecies equation
Describes molecular evolution (Eigen)

yi   j y j f j q ji  f yi
N biochemical sequences
Biochemical species i has frequency yi
Replication at rate fi is error-prone - mutation to
type j at rate qij
Adaptive dynamics
framework
 Game consists of a continuous space of strategies (eg.)
 Population is assumed to be homogeneous- all players
adopt same strategy
 Mutation generates variant strategies very close to the
resident strategy
 If a mutant beats the resident players it takes over
otherwise it is rejected
 Adaptive dynamics illustrates the nature of evolutionary
stable strategies
Adaptive dynamics
equations
 Strategies are described by continuous parameters :
S ( p1 , p2 ,...., pn )
'
'
'
'
S
(
p
,
p
,....,
p
 Expected score of mutant
1
2
n ) against S is
given by E(S’,S)
 The adaptive dynamics flow in the direction which
maximises the score:
E S ' , S 
p i 
, i  1,, n
'
pi
S ' S
We can derive Price’s equation
from replicator-mutator equation
 Price’s equation from population genetics describes any
type of selection.
 Suppose an individual of type i, frequency yi , has some
trait p of value ip

p  i yi pi , so using the replicator equation with
mutation we obtain

p  Cov( f , p )  E ( fp )
 This applies when the values of pi are const.
 [p is the expected mutational change in p.]
Price’s equation

p  Cov( f , p )  E ( fp )
selection
mutation
Price’s equation gives rise
to adaptive dynamics
 If we assume that the mutation is localised and
symmetrical then we can neglect the second term in
Price’s eqn.
 Assume population is almost homogeneous and fitness
is differentiable then we can Taylor expand the fitness,
obtaining
f
p  ( p )Var( p )
p

 cf. adaptive dynamics:
E S ' , S 
p i 
'
pi
S ' S
General framework
Quasispecies
equation
Replicator-mutator
equation
Lotka-Volterra
equation
replicator-mutator
Price equation
Game dynamical
equation
Price
equation
replicator
Price equation
Adaptive dynamics
Fisher’s fundamental
theorem
 Suppose fitnesses of genotypes constant. Can consider f
as the trait p and obtain (for symmetric mutation):

f  Cov( f , f )  Var( f )
 Fisher’s fundamental theorem of NS
 In general, fitnesses of genotypes depend on
environment. In game theory context, depend on the
frequencies of other genotypes. Fisher’s theorem doesn’t
apply- eg. PD
Generalized version
 We can use Price’s equation to obtain a generalized
version of Fisher’s fundamental theorem:

f  Var ( f )  Cov( f , g ) where g i  
j
f j
xi
xj
 This applies when the f i s depend linearly on the
frequencies of genotypes- normally the case in
evolutionary game theory.
Fisher’s theorem and GAs
 In most GAs, fitnesses of particular solutions
(chromosomes) probably fixed and so (except for the
complication of recombination) Fisher’s theorem should
hold:
f  Var ( f )
 So for a GA with fitness-proportionate selection, no
recombination and fixed fitness for a given solution,
the average fitness of the population of solutions
increases until there is no diversity left in the fitnesses.
Conclusions on unifying
evolutionary dynamics
 Unifying framework
 Different frameworks for different problems.
 We derive from Price’s equation a generalized version of
Fisher’s Fundamental Theorem of Natural Selection.
 The Price – replicator framework can also be applied to
discrete time formulations and to formulations with
sexual reproduction.
Relationship to GAs
Evolutionary games and
genetic algorithms
 Two-way interaction:
1) So far discussed computer simulations of
evolutionary processes, eg. evolution of animal
behaviour
2) Evolutionary computation, eg. genetic algorithms =
computer science based on theory of biological evolution
 Evolutionary games very like genetic algorithms- but
1) Population size is usually quite large and may be few
phenotypes: space well searched but not v. efficient.
2) Usually no recombination
3) Fitnesses depend on interactions
Genetic Algorithms
 Evolutionary models are computer algorithms which use
evolutionary methods of optimisation to solve practical problems
(cf. finding stable strategies in games rather than working out
‘rational’ solution)- eg. Evolutionary programming, genetic
algorithms
 Evolutionary operations involved in genetic algorithms: selection,
mutation, recombination:
How evolutionary
dynamics relates to GAs
 GAs evolve by selection and mutation  their dynamics
can be (to some extent) described by the replicator
equation with mutation (cf. unifying framework).
 The replicator equation describes fitness-proportionate
selection.
 Ficici, Melnik and Pollack (2000) - effects of different
types of selection (eg. truncation) on the dynamics of
the Hawk-Dove game + relevance for evolutionary
algorithms. Can lead to different dynamics.
 Must also consider the effects of recombination.
Incorporating recombination
into the replicator framework
 Do this by assuming that rjk;i = probability that when
parent chromosome of type j combines with parent
chromosome of type k, an offspring of type i is formed.
 No mutation, recombination after replication:
yi '   j ,k r jk ;i
 [NB discrete-time version]
f j fk
y j yk
f f
Adding in mutation
 Add in mutation. Assume, as before, q ij is probability
type i mutates to form type j ( qiilarge). Assume this
happens after recombination.
 What we had before was
f j fk
yi '   j ,k r jk ;i
y j yk
 What we have now is
yi ' '  l qli yl '   j ,k ,l qli r jk ;l
f f
f j fk
y j yk
f f
The diversity of the population
and adaptive dynamics
 From Fisher’s theorem, see that no diversity of fitness in
population  no further increase in average fitness.
 However, because the variation in the parameters of the
your system has become very small (population
convergence), does not mean no further evolution.
 In the case of small variation, we can apply the adaptive
dynamics framework which shows how the average
values of traits (parameters) will change in time
f
p
( p)Var ( p)
p

Relationship: evolutionary games
& GAs - Conclusions
 Often evolution leads in the long run to ‘optimal’
solutions, like Nash equilibria.
 Ability of evolutionary processes to seek out optimal
strategies has been exploited in computer science by the
development of genetic algorithms and
evolutionary computation for problem solving.
 Comparing with the use of computer simulations to
study biological evolution, we see that there is a twoway interaction between biological evolutionary
theory and computer science.
Relationship to GAsConclusions
 Frameworks of evolutionary dynamics can be applied to
GAs by modifying them to include recombination.
 Which framework is most informative depends on the
individual problem, but we have shown they are
equivalent.
 Eg. can look at detailed dynamics using the replicatormutator framework
 Or we can look at a “converged” population using
the adaptive dynamics framework.
 Looking further at the relationship between GAs and
evolutionary dynamics could yield new solutions/
techniques for both.
Acknowledgements
Martin Nowak (IAS, Princeton)
Terry Leaves (BNP Paribas, London)
Karl Sigmund (Univ. Vienna)
Steven Frank (Univ. California, Irvine)
Peter Bentley (UCL)
Christoph Hauert (Univ. British Columbia)
http://www.univie.ac.at/virtuallabs/Spatial2x2Ga
mes/
Anargyros Sarafopoulos (Univ. Bournemouth)
Bernard Buxton (UCL)