Estrategias evolutivas sobre grafos -...

Estrategias evolutivas sobre grafos

Rafael Montoya Robledo

July 20, 2016

Rafael Montoya Robledo Estrategias evolutivas sobre grafos July 20, 2016 1 / 53

Overview

1 Introduccion

2 PreliminaresLa ecuacion reversa de KolmogorovSistemas con dinamicas lentas y rapidas

3 Estrategias evolutivas sobre grafosActualizacion DBActualizacion IMActualizacion BDLa ecuacion para un juego con tres estrategias


Nos basamos en el paper de Martin Nowak de la revista Nature.

Se juntan teorıa de juegos y sistemas dinamicos.

En un contexto muy biologico que es aplicable a comunidades engeneral e incluso a polıtica.

Cuentas algebraicamente molestas y aproximaciones un poco ligeras.


La ecuacion reversa de Kolmogorov

Dadas dos estrategias A1 y A2, la probabilidad de fijacion φ(p, x ; t) esla densidad de la que la frecuencia de jugadores con la estrategia A1

sea x en el tiempo t dado que empezo con frecuencia p.

La ecuacion de Kolmogorov hacia atras esta dada por

∂φ(p, x ; t)

∂t=

1

2Vδt

∂2

∂p2φ(p, x ; t) + Mδt

∂

∂pφ(p, x ; t) (1)

Donde M y V son respectivamente la media y la varianza del cambioen la frecuencia por unidad de tiempo.


Deduccion

g(p, ξ; δt) es la densidad de probabilidad de que la frecuencia de laestrategia A1 pase de x a x + ξ durante un intervalo de tiempo quemide δt.

Bajo esta notacion se tiene que

φ(p, x ; t + δt) =

∫g(p, ξ; δt)φ(p + ξ, x , ; t)dξ (2)

La siguiente figura ilustra lo que la integral hace:


Haciendo el desarrollo en expansion de Taylor de φ en la primeracomponente, reorganizando, ignorando los terminos de la expansionde orden superior a 3 y usando el hecho de que

∫g = 1 por ser

densidad se obtiene que:

φ(p, x ; t + δt)− φ(p, x ; t) =

∫gξ∂(φ)

∂p+ g

ξ2

2!

∂2(φ)

∂p2

donde g = g(p, ξ; δt) y φ = φ(p, x ; t).

Ahora se dividen ambos lados por δt y haciendo δt −→ 0 se obtieneque

∂φ(p, x ; t)

∂t=

V (p)

2

∂2φ(p, x ; t)

∂p2+ M(p)

∂φ(p, x ; t)

∂p

donde

M(p) = limδt→0

1

δt

∫ξg(p, ξ; δt)dξ

y

V (p) = limδt→0

1

δt

∫ξ2g(p, ξ; δt)dξ


Ahora, sustiuimos M(p) y V (p) por la media y la varianza del cambiopor unidad de tiempo respectivamente, y se obtiene la ecuacion deKolmogorov.

Nos interesa el problema de fijacion de una estrategia que ocurrecuando x = 1.

Definimos u(p, t) := φ(p, 1, t) que es la probabilidad de fijacin en eltiempo t. Note que u(0, t) = 0 y u(1, t) = 1. Ademas

∂u(p, t)

∂t=

Vδt

2

∂2u(p, t)

∂p2+ Mδt

∂u(p, t)

∂p.


Ahora definimos la probabilidad terminal de fijacion

u(p) = limt→∞

u(p, t).

Asumiendo que este limite converge y que la probabilidad terminal defijacion se estabiliza, obtenemos que

∂u

∂t= 0

La ecuacion

De lo anterior se deduce la siguiente ecuacuon que sera de vitalimportancia mas adelante

0 =Vδt

2

d2u(p)

dp2+ Mδt

du(p)

dp(3)

con condiciones de frontera u(0) = 0 y u(1) = 1.


Sistemas con dinamicas lentas y rapidas

Cuando un sistema dinamico se puede escribir como

x = f (x , y) (4)

y = εg(x , y) (5)

con x ∈ Rn y y ∈ Rm, y ε es pequeno se dice que x = (x1, ..., xn) sonvariables de dinamica rapida, mientras que y = (y1, ..., ym) se llamanvariables de dinamica lenta.

Es importante notar que como ε es pequeno entonces

|y | << |x |.

Esto hace que la convergencia de y sea mucho mas lenta, permitiendoasumir que f (x , y) = 0. Esto puede permitir escribir todo el sistemasolo en terminos de y .


Es importante ver que si tomamos τ = εt, el sistema (??) se puedeescribir como

εdx

dτ= f (x , y) (6)

dy

dτ= g(x , y). (7)


Contexto del juego

Consideremos un juego entre estrategias A y B, con matriz de pagos

A BA a bB c d

Supongamos que la poblacion de jugadores es de tamano N y sedistribuye sobre los vertices de un grafo de orden k .

Con unidades de tiempo y reglas de actualizacion el grafo va a irevolucionando en torno a las distintas estrategias que van a irocupando los distintos nodos.


Sean pA y pB las frecuencias de A y B respectivamente.

Sean pAA, pBB , pAB , y pBA las frecuencias de las parejas AA, BB,AB y BA respectivamente. Estas probabilidades estan dadas sobre lasarıstas del grafo. Es decir, pXY representa la frecuencia de aristas queune nodos tipo−X a nodos tipo−Y .

Sea qX |Y la probabilidad condicional de que haya un tipo−X en unnodo dado que ese nodo tiene un vecino tipo−Y . donde X y Yrepresentan estrategias A o B.

Se tienen las siguientes identidades:

pA + pB = 1 (8)

qA|X + qB|X = 1 (9)

pXY = qX |Y pY (10)

pAB = pBA (11)

Lo anterior implica que todo el sistema se puede escribir en terminosde pA y qA|A.


Actualizacion DB


Bajo esta regla de actualizacion, en cada unidad de tiempo, unindividuo es eliminado al azar y luego, los vecinos de este individuocompiten por imponerle su estrategia al nodo. Esta competencia sehace porporcional al fitness.

Suponga que, al azar, un tipo−B. Esto sucede con probabilidad pB .Ahora, sus k vecinos compiten por el nodo.

Escribamos k = kA + kB donde kA y kB son la cantidad de vecinos Ay B respectivamente. La frecuencia de esta configuracion (que unnodo tipo−B tenga kA vecinos tipo−A y kB vecinos tipo−B ) estadada por: (

k!

kA!kB !

)qkA

A|BqkB

B|B .


Por otro lado, el fitness de un jugador en este caso esta dado por

fA = (1− w) + w[(k − 1)qA|Aa + ((k − 1)qB|A + 1)b

](12)

= 1 + w[(k − 1)qA|Aa + ((k − 1)qB|A + 1)b − 1

]︸︷︷︸:=FA

(13)

fB = (1− w) + w[(k − 1)qA|Bc + ((k − 1)qB|B + 1)d

](14)

= 1 + w[(k − 1)qA|Bc + ((k − 1)qB|B + 1)d − 1

]︸︷︷︸:=FB

(15)

Aquı el parametro w ∈ [0, 1] representa la intensidad de la seleccion.


La probabilidad de que uno de los vecinos tipo−A tome la vacanteesta dada por

kAfAkAfA + kB fB

.

que es proporcional al fitness.

Sea ∆pA la v.a. que describe el cambio en la frecuencia en unaunidad de tiempo. Entonces:

P(∆pA =1

N) = pB

∑kA+kB=k

(k!

kA!kB !

)qkA

A|BqkB

B|BkAfA

kAfA + kB fB.


En este caso el numero de pares AA aumenta kA y por lo tanto pAA

aumenta2kA

kN=

kA

(kN

2)︸︷︷︸

cantidad de aristas

con probabilidad:

P(∆pAA =2kA

kN) = pB

(k!

kA!kB !

)qkA

A|BqkB

B|BkAfA

kAfA + kB fB. (16)


Sı en vez de eliminar a un tipo−B se elimina a un tipo−A, se tieneque el fitness esta dado por

gA = (1− w) + w[((k − 1)qA|A + 1)a + ((k − 1)qB|A)b

](17)

gB = (1− w) + w[((k − 1)qA|B + 1)c + ((k − 1)qB|B)d

](18)

Se tiene tambien que la probabilidad de que un tipo−B tome lavacante es

kBgB

kAgA + kBgB.

En este caso se obtiene que

P(∆pA = − 1

N) = pA

∑kA+kB=k

(k!

kA!kB !

)qkA

A|AqkB

B|AkBgB

kAgA + kBgB.

(19)


Similarmente se obtiene que

P(∆pAA = −2kA

kN) = pA

(k!

kA!kB !

)qkA

A|AqkB

B|AkBgB

kAgA + kBgB. (20)


pA =1

NP(∆pA =

1

N)− 1

NP(∆pA = − 1

N) (21)

= wk − 1

NpAB(Iaa + Ibb − Icc − Idd) + O(w2). (22)

Donde

Ia =k − 1

kqA|A(qA|A + qB|B) +

1

kqA|A) (23)

Ib =k − 1

kqB|A(qA|A + qB|B) +

1

kqB|B) (24)

Ic =k − 1

kqA|B(qA|A + qB|B) +

1

kqA|A) (25)

Id =k − 1

kqB|B(qA|A + qB|B) +

1

kqB|B). (26)


Como el sistema se puede describir en terminos de pA y qA|A, losanteriores resultados se pueden escribir como

pA = wF1(pA, qA|A) + O(w2) (30)

˙qA|A = F2(pA, qA|A) + O(w). (31)

Para w muy pequeno estamos en un problema de dinamica lenta yrapida. Luego podemos suponer que la relacion F2(pA, qA|A) = 0.

Esto nos situa en la variedad donde se cumple la identidad

qA|A = pA +1

k − 1(1− pA).

Con esta identidad, todo el sistema se puede describir en terminos deuna sola variable (pA).


Ahora se puede calcular y aproximar la media y la varianza del cambiopor unidad de tiempo e introducirlos a la ecuacion reversa deKolmogorov.

E(∆pA) ≈ wk − 2

k(k − 1)NpA(1− pA)(αpA + β)∆t := m(pA)∆t

Var(∆pA) ≈ 2(k − 2)

N2(k − 1)pA(1− pA)∆t := v(pA)∆t

Dondeα = (k + 1)(k − 2)(a− b − c + d)

yβ = (k + 1)a + (k2 − k − 1)b − c − (k2 − 1)d .


La probabilidad de fijacion φA(y) de que un tipo−A con frecuenciainicial pA(t = 0) = y satisface la ecuacion reversa de Kolmogorov :

0 = E(y)d

dyφA(y) +

Var(y)

2

d2

dy2φA(y) (32)

Con

E(y) = wk − 2

k(k − 1)Ny(1− y)(αy + β) + O(w2)

Var(y) =2(k − 2)

N2(k − 1)y(1− y) + O(w).


Una solucion aproximada para φA(y) es dada por

φA(y) ≈ y + wN

6ky(1− y)((α + 3β) + αy). (33)

Se quiere buscar condiciones sobre a, b, c y d para queρA := φA( 1

N ) > 1N .

Para N grande, ρA >1N ⇐⇒ α + 3β > 0 que es equivalente a

(k2 + 2k + 1)a + (2k2 − 2k − 1)b > (k2 − k + 1)c + (2k2 + k − 1)d .


Ahora si consideramos el juego de cooperadores y defractores con lasiguiente matriz de pagos

A BA b − c −cB b 0

Se obtiene que ρA >1N ⇐⇒

bc > k


Actualizacion IM

Bajo esta regla de actualizacion, en cada unidad de tiempo, unindividuo es escogido al azar y luego, este se compara con sus vecinosy decide o no cambiar su estrategia proporcional al pago.

La diferencia fundamental con DB es que en este caso el pago querecibe el individuo al actualizar su estrategia tambien importa.

El fitness de un jugator tipo B con kA vecinos tipo A y kB vecinostipo B esta dado por

f0 = 1− w + w(kAc + kBd).

La probabilidad de que este jugador tipo B adopte la estrategia Aesta dado por

kAfAkAfA + kB fB + f0

.


El fitness de un jugador tipo A esta dado por

g0 = 1− w + w(kAa + kBb).

Similarmente la probabilidad de que un jugador tipo A adopte laestrategia B es:

kBgB

kAgA + kBgB + g0.


Ahora se puede calcular y aproximar la media y la varianza del cambiopor unidad de tiempo e introducirlos a la ecuacion reversa deKolmogorov.

E(∆pA) ≈ wk − 2

k(k − 1)NpA(1− pA)(αpA + β)∆t := m(pA)∆t

Var(∆pA) ≈ 2(k − 2)

N2(k − 1)pA(1− pA)∆t := v(pA)∆t

Dondeα = (k + 3)(k − 2)(a− b − c + d)

β = (k + 3)a + (k2 + k − 4)b − 2c − (k2 + 2k − 3)d .


La probabilidad de fijacion φA(y) de que un tipo−A con frecuenciainicial pA(t = 0) = y satisface la ecuacion reversa de Kolmogorov :

0 = E(y)d

dyφA(y) +

Var(y)

2

d2

dy2φA(y) (36)

Con

E(y) = wk − 2

k(k − 1)Ny(1− y)(αy + β) + O(w2)

Var(y) =2(k − 2)

N2(k − 1)y(1− y) + O(w).



φA(y) ≈ y + wN

6ky(1− y)((α + 3β) + αy). (37)

Se quieren buscar condiciones sobre a, b, c y d para queρA := φA( 1

N ) > 1N .


(k2 + 4k + 3)a + (2k2 + 2k − 3)b > (k2 + k + 3)c + (2k2 + 5k − 3)d .




Se obtiene que ρA >1N ⇐⇒

bc > k + 2


Actualizacion BD

Bajo esta regla de actualizacion, en cada unidad de tiempo, unindividuo es escogido para reproducirse proporcional al fitness. Luego,uno de sus vecinos es escogido al azar para ser remplazado por elrecien nacido.

La probabilidad de que un jugador tipo A con kA vecinos tipo A y kB

vecinos tipo B sea seleccionado para reproducirse esta dada por[pA

k!

kA!kB !qkA

A|AqkB

B|A

]︸︷︷︸

frecuencia de la configuracion

[1− w + w(kAa + kBb).]︸︷︷︸fitness del jugador tipo A

Si uno de los vecinos tipo B se escoge para ser elimindado (lo cualocurre con probabilidad kB

k ) entonces pA aumenta en 1 (o sea, ∆pA

aumenta por 1N ) y ∆pAA aumenta por

2(1+(k−1)qA|B)

kN ).


As mismo, la probabilidad de que un jugador tipo B se escoja parareproduccion esta dada por[

pBk!

kA!kB !qkA

A|BqkB

B|B

][1− w + w(kAc + kBd)] .

Si un vecino tipo A es remplazado (pasa con probabilidad kAk )

entonces pA disminuye por 1 y pAA disminuye por (k − 1)qA|A.


P(∆pA =1

N) =

∑kA+kB=k

pAk!

kA!kB !qkA

A|AqkB

B|AkB

k[1 + w(kAa + kBb − 1)]

P(∆pA = − 1

N) =

∑kA+kB=k

pBk!

kA!kB !qkA

A|BqkB

B|BkA

k[1 + w(kAc + kBd − 1)]


Ahora obtenemos aproximaciones para la media y la varianza

E(∆pA) =w

N

k − 2

k − 1pA(1− pA)(αpA + β)︸︷︷︸

:=m(pA)

dondeα = (k − 2)(a− b − c + d)

yβ = a + (k − 1)b − c − (k − 1)d .

Var(∆pA) =2

N2

k − 2

k − 1pA(1− pA)︸︷︷︸

:=v(pA)


φA(y) = y + wN

6y(1− y)((α + 3β) + αy).



φA(y) ≈ y + wN

6ky(1− y)((α + 3β) + αy). (38)

Se quieren buscar condiciones sobre a, b, c y d para queρA := φA( 1

N ) > 1N .


(k + 1)a + (2k − 1)b > (k + 1)c + (2k − 1)d .




Con estos valores se obtiene que ρC > 1N > ρD solo para valores

negativos de b o c , luego, ρD > 1N > ρC para todo b > c > 0.

La cooperacion no es favorecida bajo la regla de actualizacion BD.


Resumen

Actualizacion DB

La cooperacion es favorecida cuando bc > k.

Actualizacion IM

La cooperacion es favorecida cuando bc > k + 2.

Actualizacion BD

La cooperacion no es favorecida.


Notacion

Sean A1,A2 y A3 alelos/estrategias. Sea φ(p1, p2, x1, x2, t + δt) ladensidad de probabilidad de que la frecuencia A1 se halle entre x1 andx1 + dx1 y que la frecuencia de A2 se halle entre x2 y x2 + dx2 en eltiempo t; dado que la frecuencia inicial ( en t = 0) de A1 y A2 sea p1y p2 respectivamente.

Sea g(x1, x2, ξ1, ξ2, t, δt) la densidad de probabilidad de que lasfrecuencias cambien de x1 y x2 a x1 + ξ1 y x2 + ξ2 respectivamente,en el intervalo de tiempo (t, t + δt).

Consideremos el caso cuando x1 y x2 son fijas y p1 y p2 son variablesaleatorias.


Deduccion

Primero tenemos que:

φ(p1, p2, x1, x2, t+δt) =

∫ ∫g(p1, p2, ξ1, ξ2, δt)φ(p1+ξ1, p2+ξ2, x1, x2, t)dξ1dξ2.

Por Teorema de taylor tenemos que

φ(p1, p2, x1, x2, t + δt)

=

∫ ∫g(p1, p2, ξ1, ξ2, δt)φ(p1 + ξ1, p2 + ξ2, x1, x2, t)dξ1dξ2

=

∫ ∫{(gφ) + gξ1

∂

∂ξ2φ+ gξ2

∂

∂ξ2φ

+ gξ212

∂2

∂ξ21(φ) + gξ1ξ2

∂2

∂ξ1∂ξ2(φ) + g

ξ222

∂2

∂ξ22(φ) + O(ξ3)}dξ1dξ2


Como g es una densidad (∫ ∫

g = 1) y suponiendo que la suma, ladiferenciacion y las integrales se pueden intercambiar libremente,obtenemos que:

φ(p1, p2, x1, x2, t + δt) ≈ φ(p1 + ξ1, p2 + ξ2, x1, x2, t)+

∂

∂ξ1(φ)

∫ ∫ξ1gdξ1dξ2 +

∂

∂ξ2(φ)

∫ ∫ξ2gdξ1dξ2

+1

2{ ∂

2

∂ξ21(φ)


∂2

∂ξ22(φ)

∫ ∫ξ22gdξ1dξ2}+

∂2

∂ξ1∂ξ2(φ)

∫ ∫ξ1ξ2gdξ1dξ2.


Luego, si restamos el primer termino de la deracha y dividimos por δtse obtiene que:

φ(p1, p2, x1, x2, t + δt)− φ(p1, p2, x1, x2, t)

δt

approx∂

∂ξ1(φ

δt)


∂

∂ξ2(φ

δt)

∫ ∫ξ2gdξ1dξ2

+1

2{ ∂

2

∂ξ21(φ

δt)

∫ ∫ξ21gdξ1dξ2+

∂2

∂ξ22(φ

δt)

∫ ∫ξ22gdξ1dξ2}+

∂2

∂ξ1∂ξ2(φ

δt)

∫ ∫ξ1ξ2gdξ1dξ2


Ahora, dejando δt −→ 0 se obtiene que:

∂

∂tφ(p1 + ξ1, p2 + ξ2, x1, x2, t) ≈ ∂

∂ξ1(φ)M1 +

∂

∂ξ2(φ)M2

+1

2{ ∂

2

∂ξ21(φ)V11 +

∂2

∂ξ22(φ)V22}+

∂2

∂ξ1∂ξ2(φ)V12

con

M1(p1, p2, x1, x2) = limδt−→0

1

δt

∫ ∫ξ1gdξ1dξ2

M2(p1, p2, x1, x2) = limδt−→0

1

δt

∫ ∫ξ2gdξ1dξ2

V11(p1, p2, x1, x2) = limδt−→0

1

δt

∫ ∫ξ21gdξ1dξ2

V22(p1, p2, x1, x2) = limδt−→0

1

δt

∫ ∫ξ22gdξ1dξ2

V12(p1, p2, x1, x2) = limδt−→0

1

δt

∫ ∫ξ1ξ2gdξ1dξ2


Ahora, remplazamos M1,M2,V11,V22 y V12 porE(X ),E(Y ),Var(X ),Var(Y ) y E(XY ) respectivamente, donde X yY son los cambios en las frecuencias por unidad de tiempo.

Se obtiene entonces la siguiente EPD:

∂

∂tφ(p1 + ξ1, p2 + ξ2, x1, x2, t) = E(X )

∂

∂ξ1(φ) + E(Y )

∂

∂ξ2(φ)

+1

2OtCov(X ,Y )Oφ

donde O = ( ∂∂x ,

∂∂y )t y Cov(X ,Y ) es la matriz de covarianza del

vector aleatorio (X ,Y ).


u(p1, p2, t) := φ(p1, p2, 1, 0, t) se puede interpretar como laprobabilidad de fijacion en el timepo t cuando la frecuencia inicial es(p1, p2). Entonces u(p1, p2, t) satisface:

∂u(p1, p2, t)

∂t= E(X )

∂

∂ξ1(u(p1, p2, t)) + E(Y )

∂

∂ξ2(u(p1, p2, t))

+1

2OtCov(X ,Y )Ou(p1, p2, t)

Imponemos las condiciones de frontera u(1, 0, t) = 1, u(0, p2, t) = 0que son propias del problema de fijacionAhora la probabilidad de fijacion es dada poru(p1, p2) = limt−→∞ u(p1, p2, t).Como en el caso de dos estrategias, ∂u

∂t = 0. Esto nos arroja lasiguiente EDP:

0 = E(X )∂

∂ξ1(u(p1, p2)) + E(Y )

∂

∂ξ2(u(p1, p2))

+1

2OtCov(X ,Y )Ou(p1, p2)Rafael Montoya Robledo Estrategias evolutivas sobre grafos July 20, 2016 51 / 53

Que viene despues...

Ahora , si consideramos un juego sobre un Grafo de tamano N ygrado k con tres estrategias (A, B y C ) y usando la misma notacionque en el juego de dos estrategias obtenemos el sistema

pA + pB + pC = 1

qA|X + qB|X + qC |X = 1

pXY = qX |Y pY

pXY = pYX

En este caso la matriz de pagos es:

A B CA a b cB d e fC g h i

.


En este caso pC = 1− pA − pB . La idea aca es expresar todo elsistema en terminos de pA, pB y de los qX |Y .

Utilizando las mismas ideas de dinamica rapida y lenta se va a buscarponer todo el sistema en terminos de pA y pB . para buscar los valoresesperados y la matriz de covarianza de los cambios de frecuencia porunidad de tiempo (E(∆pA),E(∆pB),Var(∆pA),Var(∆pB) yE(∆pA∆pB) para remplazarlos en la EDP y poder estimar laprobabilidad de fijacion.


Bibliografıa

Hopfbauer, J., and Sigmund,K.

Evolutionary Games and Population Dynamics

Cambridge University Press pp. 1-140. June 13, 1998.

Crow, J.F., Kimura, M.

An Introduction to Population Genetics Theory

Burgess Publishing Company pp 371-382, 1970.

Ohtsuki,H., Hauert,C., Lieberman, E. and Nowak,M.A.

A Simple Rule for the Evolution of Cooperation on graphs and Social Networks

nature Magazine Vol 441—25, pp 502-505, May 2006.

Perko, L.

Differential Equations and Dynamical Systems

Texts in Applied Mathematics 7, Third Edition, Springer pp 1-192, 1991.

Roubicek, T.,

Nonlinear Partial Differential Equations with Applications

Birkhauser Second Edition, 2005.


Estrategias evolutivas sobre grafos -...

Documents

Transcript of Estrategias evolutivas sobre grafos -...