logo_ipparis.png     TelecomParis_endossem_IPP_RVB_100pix.png Telecom Paris
Dep. Informatique & Réseaux

Dessalles_2018.png J-L. DessallesHome page

November 2021
5

SECS.png Module Athens TP-09

    Social Emergence in Complex Systems
Lecturers:
    jean-louis Dessalles - Associate professor at Telecom-Paris
    Julien Lie-Panis - final year PhD student at Telecom-Paris and Institut Jean Nicod

                                other AI courses
5

Contents









Evolution of Altruism

BuntLine.jpg

This Lab work is based on the use of Evolife. If necessary, install it.

Please answer in English!

Nash equilibria & Evolutionarily Stable Strategies (ESS)

Social emergence
in complex systems

    

Nash equilibria
&
Evolutionarily Stable Strategies

    

    

teaching.dessalles.fr/SECS

Game theory

Game theory is a theoretical framework for describing social situations among competing players.

It applies to a variety of situations, in domains such as:
  • decision making
  • micro-economics
  • behavioral economics
  • psychologie
  • sociology
  • evolutionary biology
  • war
  • . . .

Game theory

Agents try to maximize their payoffs.

Game theory tries to find out optimal strategies, i.e. complete plans of actions a player will take in any circumstances that might arise.
8_5100898c6ff0e.jpg

Nash equilibrium

In a Nash equilibrium, no player has an incentive to deviate from their strategy. John Nash (1928-2015)

A symmetric Nash equilibrium is a strategy σ* such that for every i and any alternative strategy σ, player i’s utility verifies:

 σ:     ui(σ*σ*) > ui(σσ*)

Example

Prisoner’s dilemma

Cooperate

Defect

Cooperate

 -1-1 

-80

Defect

0-8

-5-5


Nash equilibrium:    Defect, Defect

Example

Coordination game

s1

s2

s1

 44 

00

s2

00

11


Nash equilibrium:    s1, s1
Nash equilibrium:    s2, s2
Nash equilibrium:    0.2 * s1 + 0.8 * s20.2 * s1 + 0.8 * s2

Example

Snowdrift game

Cooperate

Defect

Cooperate

 b/2 – c/2, b/2 – c/2 

 b/2 – c, b/2 

Defect

 b/2, b/2 – c 

00

Digging out the snowdrift gives each player a benefit of b/2. The cost c is born by the digger and is split when both dig.

(D,D) is the only symmetric Nash equilibrium.

Example

Rock, papers, scissors

R

P

S

R

 00 

-11

1-1

P

1-1

00

-11

S

-11

1-1

00


Nash equilibrium:    σ = (R/3, P/3, S/3)

Payoff matrix

A two-player game is represented by two matrices A and B.
(In preceding tables, A and B were juxtaposed with commas.)

C D
C  -1 -8
D   0 -5

Matrix A for Prisoner’s dilemma:    

In symmetric games, = A.

Strategies are represented by column vectors. $$\pmatrix{1\\0}$$ A pure strategy has one 1 and one 0. Mixed strategies indicate probabilities.

Payoff for strategy σ against strategy τ is given by: σ A τ.

Payoff matrix

A two-player game is represented by two matrices A and B.
Payoff for strategy σ against strategy τ is given by: σ A τ.

C D
C  -1 -8
D   0 -5

Matrix A for Prisoner’s dilemma:    


For instance, $$A D = \pmatrix{-1 & -8\\ 0 & -5} \pmatrix{0\\1} = \pmatrix{-8\\-5}$$

and:         \(C^{\top} A D = \pmatrix{1 & 0} \times \pmatrix{-8\\-5} = -8\)

Evolutionarily Stable Strategy (ESS)

Consider a symmetric two-player game with payoff matrices \(A, B\) (\(A = B^{\top}\)).
Will a (mixed) strategy \(\sigma\) resist invasion by any other strategy?
(\(\sigma\) may represent the proportion of pure strategies in a population.)

Suppose that \(\sigma\) faces the invasion by a small population of mutants that play strategy \(\tau\).

We want to compare payoff \(\sigma^{\top} A \tau\) with payoff \(\sigma^{\top} A \sigma\).

Evolutionarily Stable Strategy (ESS)

If \(\epsilon\) is the proportion of invaders, the payoff of a resident player is: $$\epsilon \sigma^{\top} A \tau + (1-\epsilon)\sigma^{\top} A \sigma = \sigma^{\top} A ((1-\epsilon)\sigma + \epsilon\tau)$$

Similarly, the payoff of an invader is: $$\epsilon \tau^{\top} A \tau + (1-\epsilon)\tau^{\top} A \sigma = \tau^{\top} A ((1-\epsilon)\sigma + \epsilon\tau)$$

If    \(\tau^{\top} A \sigma \lt \sigma^{\top} A \sigma\)    (i.e. \((\sigma,\sigma)\) is a Nash equilibrium), then for small enough \(\epsilon\), the resident’s payoff is larger than the mutant’s payoff ...
... but in case of equality, invasion is still impossible if:    \(\tau^{\top} A \tau \lt \sigma^{\top} A \tau\)
(meaning: if \(\tau\) is neutral against \(\sigma\), it does poorer against itself.)

If both conditions are met, then strategy \(\sigma\) is said to be
an evolutionarily stable strategy (ESS).

Evolutionarily Stable Strategy (ESS)


An evolutionarily stable strategy (ESS) cannot be invaded by a small number of players adopting a pure alternative strategy.

If all agents but one adopt the ESS, there is no incentive to adopt the new strategy.

In an evolving biological species, the a mutant behavior cannot invade the population.

Evolutionarily Stable Strategy (ESS)

Prisoner’s dilemma

Cooperate

Defect

Cooperate

 -1-1 

-80

Defect

0-8

-5-5


Defect is an ESS.

Evolutionarily Stable Strategy (ESS)

Coordination game

A

B

A

 44 

00

B

00

11


A is an ESS, B is an ESS,
0.2 * A + 0.8 * B, 0.2 * A + 0.8 * B is NOT an ESS
(A performs better against it).

Snowdrift game

Cooperate

Defect

Cooperate

 b/2 – c/2, b/2 – c/2 

 b/2 – c, b/2 

Defect

 b/2, b/2 – c 

00

Digging out the snowdrift gives each player a benefit of b/2. The cost c is born by the digger and is split when both dig.

When b/2 > c, the ESS is a mixture of C and D individuals.
When b/2 – c/2 > 0 > b/2 – c, (D, D) is the sole ESS
(although (C, C) would provide higher payoffs).

Rock, papers, scissors

R

P

S

R

 00 

-11

1-1

P

1-1

00

-11

S

-11

1-1

00


Nash equilibrium:    σ = (R/3, P/3, S/3)
No ESS.

Bibliography











The hawk-dove dilemma


HawkDove.png The existence of society supposes that violence remains contained. Can it be so in the absence of policing? Obviously, aggressive behaviour (intimidation) provides immediate payoff when performed against a non-aggressive victim. However, aggressors may loose a lot when confronting each other.
In Maynard Smith’s hawk-dove game, possible interactions are hawk-hawk, dove-dove and dove-hawk. The matrix below gives the payoffs for strategies indicated in the first column:

Hawk-dove game

hawk

dove

hawk

(V - C)/2

V

dove

0

V/2

Two players confront each other over a resource whose full value is V to either of them. Each player may play one of two strategies: H (Hawk) or D (Dove). Doves signal that they wish to share the resource equally. Hawks signal they are willing to fight to get the resource. When two Doves meet, each gives the characteristic sharing signal and the resource is divided equally, or, perhaps, a fair coin is tossed and the winner gets all. In any case, the expected return to each of the two Doves is V/2. When a Hawk meets a Dove, the Hawk (as it always does) signals fight, the Dove (as it always does) signals share, then the Dove retreats and the Hawk takes the entire resource. Finally, when two Hawks meet, each signal fight, neither retreats, both fight at a cost of C. In the end, the resource is shared equally, minus the cost, or, perhaps, half the time one Hawk gets the entire resource and half the time the other Hawk gets it. In any case, the expected return to each of the Hawks is (V - C)/2.
HawkDove DD
A Nash equilibrium characterizes a situation in which no player has any incentive to change strategy.
Is DD a Nash equilibrium? (DD means that both players play D).

Nash         Not Nash     Nash if V > C     Nash if V < C

    

HawkDove DH
Is DH a Nash equilibrium?

Nash         Not Nash     Nash if V > C     Nash if V < C

    

HawkDove HH
Is HH a Nash equilibrium?

Nash         Not Nash     Nash if V > C     Nash if V < C

    

The solution of the dilemma between two actual players would be to choose a probabilistic strategy. In a population of players, the proportion of hawks stabilizes to a definite value which defines an evolutionarily stable strategy.

Launch Evolife from the Evolife directory with starter. Load the HawkDove.evo configuration. Choose appropriate values for the two parameters V and C (see in the Scenarios/DyadicGames/HawkDove section). Let the program run (button [Run]). Observe the proportion of hawks in the population and the number of peaceful (DD) encounters for various values of the two parameters. The meaning of curves is written in the Legend window.

For what follows, set parameters C and V such that C be significantly larger than V (e.g. 60 and 10).
HawkDove Noise
Open the S_HawkDove.py file (in the directory Scenarii) and locate the hawk() function. As you can see, the effect of noise is to blur the distinction between the two strategies. Set the noise level (in the Configuration Editor, Ecology section) to a significant value (e.g. 30). Observe and explain the effect of noise.

    

HawkDove Gradual (1)
The Hawk gene is currently coded using 1 bit in genemap. Make it gradual by using more bits (e.g. 10). Now, the gene indicates the probability of being hawk.
Change the hawk function accordingly and copy the modified line in the box below.

    

HawkDove Gradual (2)
Restore values to default (e.g. relaod HawkDove.evo).
Compare the evolution of Hawk/Dove genes with what we have with single bit genes (you may display the genome window). How did it change? Why?

    

Suggestions for further work









Individual fitness


Fitness.png Load the configuration Favourable.evo in the Configuration Editor (Starter). In this application, implemented in Scenarii/S_Favourable.py, individuals are rewarded depending on the value of the gene named favourable. The other gene, named neutral, has no effect. Choose a positive value for parameter IndividualBenefit (in the section Scenarios/BehaviouralEcology/Favourable in the Configuration Editor). Run Evolife (button [Run]). As predicted by basic Darwinian principles, the average value of the first gene should rise to maximum, whereas the neutral gene average value oscillates around 50 (the amplitude of the deviation depends on the size of the population).
Fitness (1)
Change the interpretation of DNA from ‘Weighted’ to ‘Unweighted’ in the ‘genetic’ section of Starter. Does this have any effect on the evolution of the gene? (pay attention to the ‘Genome’ window)

Evolution is now slower, as all bits have to evolve independently
Evolution is now faster, as all bits have to evolve independently

    

Fitness (2)
Try a negative value for IndividualBenefit. You may have to change DNAFill (which defines how DNA is initialized) to -1 (random DNA) or to 1 (whole DNA filled with 1s). What do you observe?

    

Accumulation
Change the value of Cumulative to 1, to indicate that scores are not reset each year and are instead accumulated throughout the individual’s life. You may open the Field window (shortcut 'f') to display individuals according to their score (vertical axis). Compare the cumulative and non-cumulative cases. How does accumulation change the evolution of the Favourable gene? Why?

    









Ecological vs. Reproductive selection


Darwinian selection may act in several ways. Two of them are implemented in Evolife.
SelectionPressure
Keep the value of Cumulative set to 1. Change selection from the ecological mode to the reproductive mode, by setting parameter SelectionPressure to zero and Selectivity to a reasonable value such a 10. Does it change anything in the last experiment?

    









Public goods


(if you made many changes, you may reload Favourable.evo from the Configuration Editor).

Landscape.png Individuals may contribute to public welfare. This is controlled by parameter CollectiveBenefit (in the section Scenarios/BehaviouralEcology/Favourable in the Configuration Editor). The value of the gene favourable, cumulated over all individuals in the group, provides a public good that will be redistributed to all members in the group (see S_Favourable.py). Intuitively, we would expect the gene to remain stable at high values, as the whole group benefits from the contribution of all its members.

Set CollectiveBenefit to a high value such as 100, and IndividualBenefit to a smaller negative value, such as -10. The net profit for each member of the group may be significant, with a maximum of 90 if everyone contributes 100% to the public good. We may thus intuitively expect the value of the gene to rise.
Public Goods
Run the program (button [Run]) and see what happens. Do you understand why? (you may have a look at this). Try to set IndividualBenefit to -1. Does it change the result? Try to switch Cumulative between 0 and 1.

    

To understand the limits of the so-called "group-selection", you may read Group Competition, by Samuel Bowles.

Let’s suppose that all individuals have the same gene value m, except for a proportion p of them (mutants) whose gene value is M. Let’s call: C’s benefit is: CB * (N*m/N) + IB * m = (CB+IB)*m
PublicGoodsEquation
Give a formal expression of A’s and B’s benefit. Calculate the differences A–B and A–C.


    


PublicGoodsGroups
These expressions suggest ways to have collective benefit prevail over individual loss.
Suggestion: you may change (NumberOfGroups) to 10 to get smaller groups. Does it help?

    

Forum: Public goods
This effect, known as The tragedy of the commons (Hardin, 1968) is quite counterintuitive at first sight. Share any thought, comment or interrogation you might have about it.

    Hardin, G. (1968). The tragedy of the commons. Science, 162 (3859), 1243-1248.

    Hardin, G. (1968). The tragedy of the commons. Science, 162 (3859), 1243-1248.">         









Sex ratio


MaleFemelleSymbol.jpg SexRatio.gif Sex ratio is one the most famous problems in evolutionary theory. It is also one of the most impressive achievements of the game theoretic approach to evolution.
In our species, the sex ratio is roughly 1:1 (it is actually 1.05:1 in favour of boys; note that the ratio is currently 1:1.2 in some developing countries (see diagram) for non-biological reasons that you can figure out!!). From a "Public Goods" perspective, a 1:1 ratio is absurd. Only females contribute energetically to the reproduction of the population; tolerating 50% of males seems underproductive, since 1% would suffice for siring all the children.

What’s wrong in this reasoning?

As it turns out, the welfare of the population is not what is maximized through the mechanics of natural selection. If one adopts the perspective of gene (or schema) replication, then the game theoretic optimum is predicted to be reached, in most species, for a 1:1 ratio between sexes.

Run Evolife with the SexRatio configuration (button [Run]). Observe that both the average value of the gene and the sex ratio itself remain stable around 50% .

Open the S_SexRatio.py file. In this scenario, individuals can be male or female (interestingly, we chose to implement the distinction as a phenotypic character, as it is not inherited). Individuals have a gene, called sexControl. When expressed in females, this gene is supposed to control the sex ratio of children. This is performed in the new_agent function.
Have a look at the implementation in S_SexRatio.py. Locate the lines in the new_agent function where the child’s sex is determined. Replace the line:


if random.randint(0,100) >= mother.gene_relative_value('sexControl'):

by either of the following lines:


if random.randint( 0, 60) >= mother.gene_relative_value('sexControl'):
if random.randint( 0, 60) <= mother.gene_relative_value('sexControl'):
if random.randint(40,100) >= mother.gene_relative_value('sexControl'):
if random.randint(40,100) <= mother.gene_relative_value('sexControl'):

These lines introduce a sex bias in favour of one of the two sexes.

Sex bias at birth
What do we observe at the population level?

Sex ratio gets biased as expected
Sex ratio remains unbiased
Sex ratio gets slightly biased     

    

To explain what we see, let’s consider three alleles of 'sexControl': Let’s suppose that we are in a situation in which the actual sex ratio in the population is 1:9 (there are nine times more females).
Sex ratio
    Which allele will be the most successful?

SC1     SC5     SC9

    


Selective death

    Restore the code line as it was.
Selective death
Run the simulation (button [Run]) with a non-zero value of the parameter SelectiveDeath, such as 75%. Males are "killed" at birth up to that proportion (new_agent is called from Group.py in the Ecology directory). We expect this selective infanticide to change the sex ratio. What do you observe?

the sex ratio remains close to 50%     the sex ratio climbs up to 75%
the sex control gene remains close to 50%     the sex control gene climbs up to 75%

    

Selective death (2)
Do you understand why?

    

Wasp.gif Bee.gif Ant.gif Hymenoptera (which include ants, wasps, bees) are known to have sometimes a sex ratio close to 3:1 in favour of females. This is explained by the imbalance of relatedness: In these species, female workers are related 0.75 to their sisters (one inherited mutation has 75% chance to be present in a sister), whereas they are related 0.25 with their brothers. The female workers are observed to bring the sex ratio from 1:1 among eggs to 3:1 (3 females for 1 male) by killing a certain amount of male larvae. This phenomenon provides one of the most striking evidence that evolution is governed by strict (and computable) laws.

Let’s compute the probability of transmission of a mutation from worker to niece or nephew. Let p be the proportion of females in the population, and b the worker’s bias in favour of sisters. The transmission w --> f --> f involves bias b times prob. 0.75 that the mutation be present in the sister, times prob. 1/(Np) that the sister be selected for reproduction (N = size of the local population), times prob. 0.5 that the child born is female, times prob. 0.5 that the mutation is passed on to the niece.

w --> f --> f:    b * 0.75 * 1/(Np) * 0.50 * 0.50

Similarly:

w --> f --> m:    b * 0.75 * 1/(Np) * 0.50 * 0.50
w --> m --> f:    (1-b) * 0.25 * 1/(N(1-p)) * 0.50 * 1
w --> m --> m:    (1-b) * 0.25 * 1/(N(1-p)) * 0.50 * 0

If we sum the four probabilities, take the first derivative in b and make it zero, then make p=b (equilibrium), we get b = p = 3/4, which means a 3:1 ratio in favour of females.

To represent the phenomenon (in a somewhat crude way) in our scenario, we suppose that the mother (not the worker) still controls the sex ratio, but that the daughter’s DNA is re-crossed with the mother’s genome a second time (see S_SexRatio.py). As a consequence, the mother-daughter relatedness is 0.75 (Note that this situation resembles the hymenoptera case, but only vaguely).

Run the simulation (button [Run]) after having set parameter Hymenoptera to 1. Observe the resulting sex ratio.

To explain it, we will compute the probability that a given mutation expressed in the female propagates to her grandchildren (distinguishing the four possibilities).
Let p be the proportion of females in the population, and b the mother’s bias in favour of daughters.
The transmission f --> f --> f involves:

f --> f --> f:    b * 0.75 * 1/(Np) * b * 0.75

Mother Daughter Relatedness
Write the four probabilities from female to grandchild in the box below.

If you feel in good form, you may sum up the four probabilities, take the first derivative in b to find the optimum, make b = p because the optimum must be an equilibrium. This will give you p ≈ 0.78. This is the value you should have observed (a gray code may avoid problems with anisotropy of mutations).


    


Mother Son Relatedness
Modify S_SexRatio.py so that sons, and not daughters, get more genes from the mother. What do you read from the simulation? Do you see why the result is different?

    

Suggestions for further work

    









Runaway selection


le_paon_fait_la_roue_-_jardins_de_bagatelle.jpg Runaway selection has been imagined by Ron Fischer to explain extravagant features in animals (such as the peacock tail) as resulting from sexual selection. The scenario presented here is somewhat simpler than Fischer’s. However, it presupposes a direct advantage for females making the right choice.

We suppose that it is crucial for females to mate with males that are in good health. The reason for this might be to avoid being infected by a contagious male during contact (see: Hamilton, W. D. & Zuk, M. (1982). Heritable true fitness and bright birds: a role for parasites? Science, 218 (4570), 384-387). If the risk for females is significant, we observe that Open the file S_Runaway.py (in the Scenarii directory). Locate the start_game function. Observe that both sexes pay a cost.
Open Starter    from the Evolife directory and load the Runaway scenario. Run it and observe that males evolve to invest massively in costly signals. The phenomenon is slightly richer than that. The two genes 'FemaleDemand' and 'MaleInvestment' co-evolve: females compare more males and males compete to please them. The crucial point here is that females have no absolute reference. They just compare males with one another.

Runaway Low Quality Cost
Go to the Scenarios/BehaviouralEcology/Runaway section in Starter. Change the price for choosing an unhealthy male (parameter LowQualityCost). Which is the mimimum value for which runaway selection seems to be stable?

    150 120
    100 80
    70    

    


In the current implementation, females get a proportional penalty for mating with an unhealthy male. To get closer to the infection metaphor, we want to make penalty binary (the male is infected or he is not).

Runaway binary code
Go back to S_Runaway.py and introduce a new phene 'Parasite' in 'phenemap'. Phenes are randomly drawn between 0 and 100 at birth. This new phene is used to make individuals sick.

Go to the new_agent function. It is called just after a new individual has been born. Compare the newborn’s phene 'Parasite' to the value of the parameter ParasiteProbability (that you can set using Starter). When it is smaller (which means that the individual is sick), divide the newborn’s quality by 2 (put the new value as second argument in Phene_value).

Now go a few lines up, at the end of the parents function. Make the penalty binary instead of proportional by comparing again the father’s 'Parasite' phene to ParasiteProbability. If he is infected, the mother should lose 'LowQualityCost' score points.

    [Copy your last modification below]

    

You should observe that the runaway mechanism still works, though for different values of LowQualityCost.
Runaway binary cost
For which minimal value of LowQualityCost do you observe runaway selection?

    300 250
    200 150
    100    

    

Suggestions for further work

    

            
BuntLine.jpg

Back to the main page