Evolutionary Games on Networks: from Brain Connectivity to Social Behavior

(1)

Evolutionary Games on Networks: from Brain Connectivity to Social Behavior

Chiara Mocenni

Dept. of Information Engineering and Mathematics, University ofi Siena (IT) (mocenni@dii.unisi.it)

In collaboration with D. Madeo, J. Moraes, J. P. Zubelli, E.

Santarnecchi, N. Bobko, A. Talarico, S. Mattera

IMPA, Rio de Janeiro (Brasil), February 25, 2016

(2)

Selection and Evolution in Homogeneous and Inhomogeneous Populations

Homogeneous case (J. Weibull, 1995)

Infinite population of phenotype-driven individuals Individuals transfer the phenotype to their offspring

Share of optimal payoff phenotype increases: natural selection

˙

x s = x s (p s − φ) Inhomogeneous case (D. Madeo and CM, 2015)

Finite population of individuals

Players aren’t phenotype-driven: mixed strategies are allowed The population structure is described by a graph

˙

x v ,s = x v ,s (p _{v ,s} ^G − φ ^G _v )

(3)

The two models: a comparison

Selection Mechanism Payoff Function

Initial Conditions Adjacency Matrix

Standard case

˙

x s = x s (p s − φ) x _s (0) = c _s p s (x ) = e ^T _s Bx φ(x ) = x ^T Bx

x = [x ₁ . . . x _M ] ^T ∈ ∆ _M

Networked case (EGN)

˙

x v ,s = x v ,s (p ^G _{v ,s} − φ ^G _v ) x _{v ,s} (0) = c _{v ,s}

p _{v ,s} ^G (X ) = e ^T _s B _v k _v (X ) φ ^G _v (X ) = x ^T _v B _v k _v (X ) k _v (X ) = P N

w =1 a vw x _w X = {x ₁ , . . . , x _N }

x _v = [x _{v ,1} . . . x _{v ,M} ] ^T ∈ ∆ _M

(4)

The average player k _v (X )

(5)

What kind of phenomena can be explained by the extended equation?

In the new framework selection depends not only on the payoff matrix, but also on social interactions

Initial Conditions set the system configuration at initial time, including extinction of strategies (x v ,s (0) = 0 for some v) Payoff Matrix describes the internal decision mechanism of individuals, e.g. propensity of individuals to cooperate or non cooperate with the opponent, presence of dominant strategies, indifference, etc.

Moreover, from the EGN structure follows that the preference

ordering in the payoff matrix may be changed by the entries of

adjacency matrix (no need for positive entries)

(6)

The (N, 2) equation

If only two strategies are considered, x _{v ,2} = 1 − x _{v ,1} , then we have x _v = [x v ,1 1 − x v ,1 ]. Then we can set y v = x v ,1 and y = [y 1 . . . y N ]:

˙

y v = y v (1 − y v )f v (y )

f v (y ) = σ v ,1 k v ,1 (y ) − σ v ,2 k v ,2 (y ) B _v =

b 11 b 12

b 21 b 22

, σ v ,1 = b 11 − b ₂₁ , σ v ,2 = b 22 − b ₁₂ k v ,1 (y ) = P N

w =1 a vw y w , k v ,2 (y ) = P N

w =1 a vw (1 − y w )

(7)

Three sets of steady states

Θ ^∗ = n

y ^∗ ∈ [0, 1] ^N : ∀v (y _v ^∗ = 0 ∨ y _v ^∗ = 1 ∨ f _v (y ^∗ ) = 0) o

1

Pure steady states: Θ ^p = {0, 1} ^N ⊆ Θ ^∗

2

Interior (mixed) steady states: Θ ^m = (0, 1) ^N ∩ Θ ^∗

3

Pure/mixed steady states: Θ ^pm = Θ ^∗ \ (Θ ^p ∪ Θ ^m )

(8)

Feasibility and stability of mixed steady states for generic adjacency matrices

Theorem

Suppose σ v ,1 = σ 1 and σ v ,2 = σ 2 ∀v and sign(σ ₁ ) = sign(σ 2 ) 6= 0.

Then there always exists a steady state y ^∗ ∈ Θ ^m such that ∀v y _v ^∗ = σ ₂

σ 1 + σ 2

Moreover,

λ(J(y ^∗ )) = σ ₁ σ ₂ σ 1 + σ 2

λ(A)

The steady state depends on the payoff matrix, while its

stability depends mainly on the graph

(9)

From connected to reduced connectivity adjacency matrices

In the previous results we assumed some conditions on the payoff matrices (all nodes share the same σs, with same sign) and did not make any assumption on the adjacency matrix Is the feasibility of internal steady states depending on the graph’s structure? How can we weaken a central node?

We take a fully connected graph, choose one specific node

and start deleting iteratively all links from this node

What is the effect in the mixed steady state of such

procedure? (D. Madeo, CM, J. C. Moraes, J.P. Zubelli,

submitted 2015)

(10)

Mixed steady states with reduced connectivity

For each node and for each link removal, we find lower and upper bounds of the ratio d v = _σ ^σ

^{v ,2}

v ,1

+σ

v ,2

in order the mixed steady state to be feasible

These bounds depend on the average of the d _v s of connected nodes

For large networks (N → ∞) the only possibility for the steady state to be interior is that all nodes share the same d v

Moreover, the average of the steady state component for each

node corresponds to the average of the d _v s

(11)

Asymptotic behavior of a network with 50 nodes

Asymptotic behavior of the solution for nodes 1, 20, 30 and 40.

Homogeneous initial conditions 0.6 are set for all nodes, except for

node 1, where y 1 (0) ∈ [0, 1].

(12)

Modeling brain connectivity by EGN equation

Brain connectivity refers to patterns of connectivity between distinct units within a nervous system

The units correspond to individual neurons, neuronal populations, or anatomically segregated brain regions

The connectivity can by:

Anatomical (anatomical links) Functional (statistical

dependencies)

Effective (causal interactions)

(13)

fMRI data for brain connectivity

The network of connections can be reconstructed by means of functional magnetic resonance imaging (fMRI)

fMRI data consist with spatio-temporal measures of the

oxygen consumption in unitary volumes (voxels) of brain

(14)

Network reconstruction

Nodes of the network are anatomical regions of the brain

Edges are obtained by calculating correlation coefficients

(functional connectivity) or Granger causality (effective

connectivity) between the time course recorded by the fMRI in

two nodes (usually 7-10 minutes experiments)

(15)

Why evolutionary games?

Brain behavior is regulated by activation or inhibition With payoff matrix B v node v is always activated by node w : strategy 1 is optimal response to strategy 1 (b ₁₁ > b ₂₁ ) and strategy 2 is optimal response to strategy 2 (b ₂₂ > b ₁₂ ) However, negative edge weights can reverse the response

Negative a _vw may produce oscillating behavior in the model!

(16)

Some examples of oscillations: comparison with real data

No optimization or inverse problems solved!

(17)

A real example

The network considers 11 anatomic regions (nodes) In each node, a time series z _t of 7 minutes, with sampling time of 2.3 sec., is recorded

Two strategies available: activation and inhibition Payoff matrix B =

0.5 −0.5

−0.5 0.5

, ∀v (σ ₁ = 1, σ ₂ = 1) EGN equation ˙ x v = x v (1 − x v )f v (x ) =

x v (1 − x v )

"

(σ 1 + σ 2 )

N

X

w =1

a v ,w x w − σ ₂

N

X

w =1

a v ,w

#

(18)

How to reconstruct the elements of A from the data points

The linear dependence of the system on parameters a v ,w

suggests that we can estimate θ = {a v ,w } using a least square optimization on the basis of some observations of x _v

Measurements of the variables x _v are available at equispaced time instants: z _{v ,k} = x v (t _k ), with t _k = kτ c for all

k = 0, . . . , T − 1, τ _c > 0.

Considering the Euler discretization of EGN:

x _{v ,k+1} = x _{v ,k} + τ _c m _v (x _k ) ^> θ,

where x _{v ,k} = x _v (t _k ), x _k = [x _1,k , . . . , x _N,k ] ^> , and m _v (x ) ∈ R ^N

²

m _{v ,w} = x _v (t _k )(1 − x _v (t _k ))((σ ₁ + σ ₂ )x _w (t _k ) − σ ₂ ), t _k = kτ c and τ c > 0 for all k = 0, . . . , T − 1. Then, we can write the discretized EGN in matricial form:

Y (x ) = U(x )θ, (1)

(19)

The linear formulation of the problem

Y (x ) =







x _1,1 − x _1,0 x _2,1 − x _2,0

.. . x _N,1 − x _N,0

x _1,2 − x _1,1 x 2,2 − x _2,1

.. . x _N,2 − x _N,1

.. . x _1,T − x _{1,T −1} x _2,T − x _{2,T −1}

.. . x _N,T − x _{N,T −1}







and U(x ) = τ _c







m ₁ (x ₀ ) ^>

m ₂ (x ₀ ) ^>

.. . m _N (x ₀ ) ^>

m ₁ (x ₁ ) ^>

m 2 (x 1 ) ^>

.. . m _N (x ₁ ) ^>

.. . m ₁ (x _{T −1} ) ^>

m 2 (x T −1 ) ^>

.. . m _N (x _{T −1} ) ^>







,

(20)

Parameter estimation

We want to find the parameters θ which minimize the distance between the observations and the model We can minimize the objective function:

1 NT kY (z) − U(z)θk

²

= 1 NT

N

X

v =1 T −1

X

k=0

z

v ,k+1

− z

v ,k

− τ

c

m

v

(z

k

)

^>

θ

²

This function is convex and, under certain hypotheses, it has only one solution:

θ = (U(z) ˆ ^> U(z)) ⁻¹ U(z) ^> Y (z),

θ are the estimated parameters based on the observation z ˆ

(21)

Estimated parameters and LS errors: moving windows

Each window consists of 18 data points shifted by 5 points

(22)

Parameter estimation and fitting: 18 data points/node

(23)

Parameter estimation and fitting: 175 data points/node

(24)

Parameter estimation and fitting: long term simulation

Long term simulation: parameters estimated over 18 data points

Long term simulation: parameters estimated over 175 data points

(25)

Correlation matrices of real data and simulations

ρ _X,Y = cov (X, Y)

σ _X σ _Y

(26)

LS error Vs Correlation error

LS error: _NT ¹ kY (z) − U(z)θk ²

Correlation error: _N ¹

2

kC (z) − C (z _k )k ²

(27)

Application to Crime Dynamics: residential burglaries in

Cascavel, Brasil (2010-2012)

(28)

Application to Crime Dynamics: time series of all burglaries (2010-2012)

The possibility of modeling crime dynamics by means of

mathematical models has recently attracted a lot of researchers

(M. D’Orsogna and M. Perc, 2015)

(29)

Building the network: spatial aggregation

More sophisticated aggregation method, such as spatial

segregation, are under investigation

(30)

Two Networks

Road Network Criminals Network

The road network is geographic

The second can be calculated in two ways:

By the linear correlation between the time series of the burglaries measured in any couple of regions

By estimating the entries of the adjacency matrix from data

(31)

Modeling by EGN

We consider the evolutionary game equation on networks, where The state variable x v represents the probability that a burglary happens in region v

The payoff matrix B v embeds the preference ordering of criminals allowing them to make or not a burglary in region v Matrix B v can vary according to the characteristics of region (node) v

The selection mechanism optimizes the decision making of robbers (from their point of view!)

In order to account for the two networks (two adjacency

matrices) we can consider the weighted sum of the two (recall

linear relationship of the equations on the entries of the

adjacency).

(32)

Some preliminary results

Fitting between model simulation and real data in a network with 9 nodes

Estimated Adjacency

Matrix

(33)

Conclusions and Future Developments

The extended version of the evolutionary game equation (EGN) accounting for a graph of connections among players has been introduced

The model allows to describe the system dynamics at a small scale, where inhomogeneities are also present

We showed that EGN can been used to model complex phenomena, such as brain connectivity and crime dynamics Future developments will concern the study of the stability of internal steady states in networks with n strategies

A better understanding of the role of graph topology in the system’s dynamics and stability is under investigation (G.

Iacobelli, D. Madeo, CM, submitted 2015)

Evolutionary Games on Networks: from Brain Connectivity to Social Behavior

Evolutionary Games on Networks: from Brain Connectivity to Social Behavior

Chiara Mocenni

Dept. of Information Engineering and Mathematics, University ofi Siena (IT) (mocenni@dii.unisi.it)

In collaboration with D. Madeo, J. Moraes, J. P. Zubelli, E.

Santarnecchi, N. Bobko, A. Talarico, S. Mattera

IMPA, Rio de Janeiro (Brasil), February 25, 2016

Selection and Evolution in Homogeneous and Inhomogeneous Populations

Homogeneous case (J. Weibull, 1995)

Infinite population of phenotype-driven individuals Individuals transfer the phenotype to their offspring

Share of optimal payoff phenotype increases: natural selection

˙

x s = x s (p s − φ) Inhomogeneous case (D. Madeo and CM, 2015)

Finite population of individuals

Players aren’t phenotype-driven: mixed strategies are allowed The population structure is described by a graph

˙

x v ,s = x v ,s (p v ,s G − φ G v )

The two models: a comparison

Selection Mechanism Payoff Function

Initial Conditions Adjacency Matrix

Standard case

˙

x s = x s (p s − φ) x s (0) = c s p s (x ) = e T s Bx φ(x ) = x T Bx

x = [x 1 . . . x M ] T ∈ ∆ M

Networked case (EGN)

˙

x v ,s = x v ,s (p G v ,s − φ G v ) x v ,s (0) = c v ,s

p v ,s G (X ) = e T s B v k v (X ) φ G v (X ) = x T v B v k v (X ) k v (X ) = P N

w =1 a vw x w X = {x 1 , . . . , x N }

x v = [x v ,1 . . . x v ,M ] T ∈ ∆ M

The average player k v (X )

What kind of phenomena can be explained by the extended equation?

In the new framework selection depends not only on the payoff matrix, but also on social interactions

Moreover, from the EGN structure follows that the preference

ordering in the payoff matrix may be changed by the entries of

adjacency matrix (no need for positive entries)

The (N, 2) equation

If only two strategies are considered, x v ,2 = 1 − x v ,1 , then we have x v = [x v ,1 1 − x v ,1 ]. Then we can set y v = x v ,1 and y = [y 1 . . . y N ]:

˙

y v = y v (1 − y v )f v (y )

f v (y ) = σ v ,1 k v ,1 (y ) − σ v ,2 k v ,2 (y ) B v =

 b 11 b 12

b 21 b 22



, σ v ,1 = b 11 − b 21 , σ v ,2 = b 22 − b 12 k v ,1 (y ) = P N

w =1 a vw y w , k v ,2 (y ) = P N

w =1 a vw (1 − y w )

Three sets of steady states

Θ ∗ = n

y ∗ ∈ [0, 1] N : ∀v (y v ∗ = 0 ∨ y v ∗ = 1 ∨ f v (y ∗ ) = 0) o

Pure steady states: Θ p = {0, 1} N ⊆ Θ ∗

Interior (mixed) steady states: Θ m = (0, 1) N ∩ Θ ∗

Pure/mixed steady states: Θ pm = Θ ∗ \ (Θ p ∪ Θ m )

Feasibility and stability of mixed steady states for generic adjacency matrices

Theorem

Suppose σ v ,1 = σ 1 and σ v ,2 = σ 2 ∀v and sign(σ 1 ) = sign(σ 2 ) 6= 0.

Then there always exists a steady state y ∗ ∈ Θ m such that ∀v y v ∗ = σ 2

σ 1 + σ 2

Moreover,

λ(J(y ∗ )) = σ 1 σ 2 σ 1 + σ 2

λ(A)

The steady state depends on the payoff matrix, while its

stability depends mainly on the graph

From connected to reduced connectivity adjacency matrices

In the previous results we assumed some conditions on the payoff matrices (all nodes share the same σs, with same sign) and did not make any assumption on the adjacency matrix Is the feasibility of internal steady states depending on the graph’s structure? How can we weaken a central node?

We take a fully connected graph, choose one specific node

and start deleting iteratively all links from this node

What is the effect in the mixed steady state of such

procedure? (D. Madeo, CM, J. C. Moraes, J.P. Zubelli,

submitted 2015)

Mixed steady states with reduced connectivity

For each node and for each link removal, we find lower and upper bounds of the ratio d v = σ σ

+σ

in order the mixed steady state to be feasible

These bounds depend on the average of the d v s of connected nodes

For large networks (N → ∞) the only possibility for the steady state to be interior is that all nodes share the same d v

Moreover, the average of the steady state component for each

node corresponds to the average of the d v s

Asymptotic behavior of a network with 50 nodes

Asymptotic behavior of the solution for nodes 1, 20, 30 and 40.

x v ,s = x v ,s (p _{v ,s} ^G − φ ^G _v )

x s = x s (p s − φ) x _s (0) = c _s p s (x ) = e ^T _s Bx φ(x ) = x ^T Bx

x = [x ₁ . . . x _M ] ^T ∈ ∆ _M

x v ,s = x v ,s (p ^G _{v ,s} − φ ^G _v ) x _{v ,s} (0) = c _{v ,s}

p _{v ,s} ^G (X ) = e ^T _s B _v k _v (X ) φ ^G _v (X ) = x ^T _v B _v k _v (X ) k _v (X ) = P N

w =1 a vw x _w X = {x ₁ , . . . , x _N }

x _v = [x _{v ,1} . . . x _{v ,M} ] ^T ∈ ∆ _M

The average player k _v (X )

If only two strategies are considered, x _{v ,2} = 1 − x _{v ,1} , then we have x _v = [x v ,1 1 − x v ,1 ]. Then we can set y v = x v ,1 and y = [y 1 . . . y N ]:

f v (y ) = σ v ,1 k v ,1 (y ) − σ v ,2 k v ,2 (y ) B _v =

b 11 b 12

, σ v ,1 = b 11 − b ₂₁ , σ v ,2 = b 22 − b ₁₂ k v ,1 (y ) = P N

Θ ^∗ = n

y ^∗ ∈ [0, 1] ^N : ∀v (y _v ^∗ = 0 ∨ y _v ^∗ = 1 ∨ f _v (y ^∗ ) = 0) o

Pure steady states: Θ ^p = {0, 1} ^N ⊆ Θ ^∗

Interior (mixed) steady states: Θ ^m = (0, 1) ^N ∩ Θ ^∗

Pure/mixed steady states: Θ ^pm = Θ ^∗ \ (Θ ^p ∪ Θ ^m )

Suppose σ v ,1 = σ 1 and σ v ,2 = σ 2 ∀v and sign(σ ₁ ) = sign(σ 2 ) 6= 0.

Then there always exists a steady state y ^∗ ∈ Θ ^m such that ∀v y _v ^∗ = σ ₂

λ(J(y ^∗ )) = σ ₁ σ ₂ σ 1 + σ 2

For each node and for each link removal, we find lower and upper bounds of the ratio d v = _σ ^σ

These bounds depend on the average of the d _v s of connected nodes

node corresponds to the average of the d _v s

Negative a _vw may produce oscillating behavior in the model!

The network considers 11 anatomic regions (nodes) In each node, a time series z _t of 7 minutes, with sampling time of 2.3 sec., is recorded

0.5 −0.5

, ∀v (σ ₁ = 1, σ ₂ = 1) EGN equation ˙ x v = x v (1 − x v )f v (x ) =

a v ,w x w − σ ₂

suggests that we can estimate θ = {a v ,w } using a least square optimization on the basis of some observations of x _v

Measurements of the variables x _v are available at equispaced time instants: z _{v ,k} = x v (t _k ), with t _k = kτ c for all

k = 0, . . . , T − 1, τ _c > 0.

x _{v ,k+1} = x _{v ,k} + τ _c m _v (x _k ) ^> θ,

where x _{v ,k} = x _v (t _k ), x _k = [x _1,k , . . . , x _N,k ] ^> , and m _v (x ) ∈ R ^N

m _{v ,w} = x _v (t _k )(1 − x _v (t _k ))((σ ₁ + σ ₂ )x _w (t _k ) − σ ₂ ), t _k = kτ c and τ c > 0 for all k = 0, . . . , T − 1. Then, we can write the discretized EGN in matricial form: