Evolúciós potenciál játékok

Evolúciós potenciál játékok Szabó György MTA TTK MFA H-1525 Budapest, POB. 49, Hungary Magyar Fizikus Vándorgyűlés, ELFT, Debrecen, 2013. 08. 24.

Kivonat - Játékok és potenciál játékok definíciója - Általános tulajdonságok - Potenciál meghatározása néhány példában

- Potenciál játékok rácson -> Ising típusú modellek - Eltérések a potenciál játékoktól - Összegzés Együttműködők: Borsos István, Szolnoki Attila, Ben Allen, Martin Nowak, … Támogatás: OTKA 101490, Templeton Foundation, TAMOP-4.2.2.C-11 1

Játékok Játék = Leegyszerűsített élethelyzet Normál játék: N játékos (x=1, …, N) , véges számú stratégiával (sx=sx1, …, sxq), akik saját ux(s1, …, sN) nyereményüket kívánják maximálni. A játékosok intelligensek: ismerik a szabályokat, lehetőségeket, ill. nyereményeket és feltételezik, hogy társaik is intelligensek. A potencál játékoknál létezik egy V(s1, …, sN) potenciál, ami minden játékosra kielégíti a következő feltételt:

u x ( sx ; s x )  u x ( s x ; s x )  V ( sx ; s x )  V ( s x ; s x ) ,  s x , sx , s x ahol ux(sx;s-x) az sx stratégiát követő x játékos nyereménye, ha a többiek stratégiáját s-x jelöli. A potenciál a stratégiát változtató játékosok nyereményváltozásából épül fel, függetlenül attól, hogy a többiekkel mi történik.

A potenciál létezésének feltétele, hogy a stratégia térben minden zárt hurok mentén a potenciálváltozások összege zéró. 2

Általános tulajdonságok a kétszemélyes (x, y) (bi-mátrix) játékoknál Monderer & Shapley, GEB 14 (1996) 124

Nyereménymátrixok:

u x ( s x , s y )  s x  As y u y ( s y , s x )  s y  Bs x

1  0 0        0 1 0 ahol s x  s x1    , s x 2    ,  , s xn              0  0 1       és s y  

A játék és potenciál jelölése:  ( A11 , B11 )  ( A1n , B1n )   V11  V1n      G  ( A, B )        V       ( A , B )  ( A , B ) V  V  nn nn  nn   n1  n1 n1

1) Linearitás + tetszőleges konstans:

2) additivitás:

 V11  V1n  1  1     (A, B)  V               V  V  1  1 nn   n1  

(A, B)  V and (A, B)  V , then (A  A, B  B)  V  V

3) Szimmetrikus játéknál:

A  B and V  V 

3

Általános tulajdonságok (folytatás) 4) Ha a szimmetrikus játéknál (A=B) a nyereménymátrix is szimmetrikus (pl. testvéries játék) A=A+, akkor V=A. 5) A potenciál változatlan marad, azaz V=V’, ha a nyereményeket így változtatjuk:

 A11  1  A1n   n   B11   1  B1n   n      A       illetve B       A   A   B   B   nn n nn n  n1 1  n1 1 ez a tulajdonság bővíti a potenciál játékok halmazát. 6) N-szereplős játékot és potenciált párkölcsönhatásból is felépíthetünk: összegzés a kölcsönható párokra (x, y =1, …, N). U s   V (s , s )



x

y

és s=(s1,…,sN)

x, y

7) Ha a stratégiatér sztochasztikus evolúcióját a logit (log-linear) szabály vezérli,

exp(us (sx , s x ) / K ) wsx  sx     exp(us (sx, s x ) / K )

Blume, GEB 5 (1995) 387

sx {s x }

akkor a rendszer a Boltzmann eloszlásba fejlődik, azaz s valószínűsége:

ps  

1 exp( U (s) / K ) , ahol Z   exp( U (s) / K ) Z s

4

Minden szimmetrikus kétszemélyes kétstratégiás játék potenciál játék Gráf reprezentáció:

pontok = tiszta stratégia profilok (mikroállapotok) élek = lehetséges átmenetek, ha csak egy játékos vált stratégiát

S

S

Stratégia pár: (fehér és/vagy fekete) pont pár, nyeremény pár: (Aij, Bji) 1-T

1-T

a változtató játékos nyereményének változása az élek mentén. összegük 0 a hurok mentén. T-S (kísértés-balek nyeremény) paramétertér

A potenciál létezik, ha

B21  B11  A22  A12  A21  A11  B22  B12 Ugyanez a társadalmi dilemmák szokásos jelölésében: Két stratégia: D: élősködő; C: együttműködő

S   (0,0) (T , S )  0   V    G ( sd )   ( S , T ) ( 1 , 1 ) S S  1  T     Folyamábra: A nyilak a magasabb potenciál felé mutatnak. Nincs irányított hurok. Tiszta Nash egyensúly = pont kimenő élek nélkül

5

Nemszimmetrikus 2x2-es potenciál játékok A társadalmi dilemmák jelölésében a nyeremény bimátrix: (T , S  a)  S a   (0,0) 0     G  V    (S , T  b) (1,1  c)   S S 1 T  a 

if a+b+c=0

Két hangolható paraméter (pl. a és b)

Ellenpélda (snóbli, vagy matching pennies):  (1,1) (1,1)   G (mp)   (  1 , 1 ) ( 1 ,  1 )  

folyamábra:

Ha (a+b+c) ≠ 0, akkor a játék

1 G  G ( pot )  G ( mp) ahol   (a  b  c) 8 A snóbli képviseli azt a 2x2-es kölcsönhatást, ami „kavar” az állapottérben.

6

Szimmetrikus 3x3-as potenciál játékok G  ( A, A) , A  A ( s )  A ( as ) A(s)  A(s)



and A ( as )

a  c  0     a 0 b   c b 0   

A potenciál származtatásánál csak az aszimmetrikus résszel kell foglalkozni. Kirchhoff törvények: 4(1) független hurok (piros körök) A potenciál létezik, ha a+b+c=0. Általánosan:

A12  A23  A31  A21  A32  A13  0 Egy G játék szétcsatolható, azaz

G  G ( pot )  G ( rsp ) ahol 1 és   ( A12  A23  A31  A21  A32  A13 ) 6

A (rsp )

 0 1  1     1 0 1   1 1 0   

A kő-papír-olló játék a játékok egy másik olyan osztályát képviseli, ami megakadályozza a potenciál létezését, illetve örvényeket kelt az állapottérben. Sejtés: kevert Nash egyensúlyok, ill. önszervező (térbeli spirál) mintázatok okozója.

7

Folyamábra a potenciál játékoknál A nyilak a jobb egyéni választás irányába mutatnak Nincs irányított hurok Példa: koordinációs játék négy személlyel, mindegyikük két lehetőség közül választ állapottér: 4-dimenziós „kocka” egyszerre csak egy játékos változtat Tiszta Nash egyensúly(ok) megtalálása: Véletlen kezdőállapotban a véletlenül választott játékosok új véletlen stratégiát választanak, ha az nekik megéri. Előbb-utóbb a rendszer elér egy olyan állapotba, ahonnan már senkinek sem éri meg eltérni, vagyis nincs kifelé mutató él.

Maximális potenciál = Nash egyensúly Több tiszta Nash egyensúly is létezhet. gráfelméleti tételek

8

Térbeli potenciál játékok N azonos játékost egy négyzetrács x pontjain helyezünk el. Periodikus határfeltétel biztosítja az eltolási szimmetriát. x játékos stratégiái: 1 0     s x     ,  ,    , és s  (s1 , s 2 ,, s N ) 0 1     A potenciál az első szomszédok közötti kétszemélyes potenciál játékból épül fel:

U (s) 

1 s x  Vs x     2 x , x ,

sx1

 s xn  V11  V1n  s x  ,1             V  V  s n 1 nn x   , n   

Ising modell: σx= -1, +1 (spin fel, spin le) állapotok Energia: J: csatolási állandó (J > 0: ferromágneses) 1 H   J  x x   h  x h: külső mágneses tér 2

 x,

 x

Rács gáz modell: nx=0, 1

1 H   J  n x n x     n x 2 x , x 9

Sztochasztikus dinamika A „logit” szabály a nagyobb egyéni nyeremény illetve a magasabb U(s) potenciál irányába tereli a rendszert hasonlóan a Glauber, 1 w(s  s)  1  exp[( U (s)  U (s)) / K ] vagy Metropolis dinamikákhoz, amelyek az alacsonyabb H energiájú állapot valószínűségét növelik. Mindegyik rendszer a Boltzmann eloszlásba fejlődik [H = - U(s)], azaz s valószínűsége:

ps  

1 exp( U (s) / K ) , ahol Z   exp( U (s) / K ) Z s

ami kielégíti a részletes egyensúly feltételét minden lehetséges oda-vissza átmenet esetében

p(s)w(s  s)  p(s)w(s  s) A részletes egyensúly és a Boltzmann eloszlás változatlanul megmarad, ha az odavissza átmenetek w(s→s’ ) és w(s’→s) valószínűségét ugyanazzal a szorzófaktorral megváltoztatjuk. Analógia a közlekedő edényekkel, ha N kicsi. Ergodikus jelenségek, ha N tart a végtelenhez.

10

Ising modellel azonos térbeli 2x2-es evolúciós játékok Társadalmi dilemma jelölésben (D és C stratégiák) a potenciál: G

( sd )

S   (0,0) (T , S )  0       V   (S , T ) (1,1)   S S 1 T 

Mágneses Ising modell:  H  1 J  sx sx  h sx  1 VIsing 2 x, 2 x, x z szomszéd 2h    VIsing

J  h z  Js1s2  ( s1  s2 )   z   J 

J   2h  J  z 

A paraméterek összehasonlításából:  4 J  T  1  S , and  4h / z  (S  1  T )

J>0 : ferromágneses rend J<0 : anti-ferromágneses (sakktábla) rend h>0 : homogén spin fel állapot

h<0 : homogén spin le állapot A J=0 eset „áljátéknak” felel meg (pl. adományozó vagy közlegelő játékok)

11

Snóbli sakktáblán A játékosok négyzetrácson (sakktáblán) helyezkednek el Az evolúciót Glauber dinamika vezérli G=G (mp) játék az első-szomszédok között Az MC szimuláció véletlen eloszlást mutat:

Low noise

High noise

Korrelációs függvény K függvényében: cij ( x)  ni ( y  x)n j ( y)  ni ( y  x) y

y

n j ( y)

y

MC szimuláció, ha i=j=1 kör:

x=(0,1) or (1,0)

négyzet:

x=(1,1)

gyémánt: x=(2,0) Fekete szimbólumok: csak pozitív változás lehet (K=0) 12

Héja-galamb játék snóblival fűszerezve G=G (sd) +εG (mp)

Mov.1: T=1.4; S=0.3; ε=0.0; K=0.2 Mov.2: T=1.4; S=0.3; ε=0.1; K=0.2

Mov.3: T=1.3; S=0.4; ε=0.1; K=0.2 MC szimuláció sakktáblán K=0.2; ε = 0.1

Mov.4: T=1.41; S=0.4; ε=0.1; K=0.2 Mov.5: T=1.4; S=0.3; ε=0.2; K=0.2

C stratégia gyakorisága az alrácsokon

A görbék színváltozása állapotváltozást jelöl. Kis ε-nál az egyik alrács-rendezett szerkezet stabil. Nagy ε rombolja a rendeződést.

13

Héja-galamb játék snóblival fűszerezve (folytatás) Snóblizás segítheti az együttműködés fenntartását

MC szimuláció, ha T=1.9 és S=0.4 Átlagos nyeremény K-függése

„Red Queen” effektus Lewis Carroll: Alice Tükörországban Az evolúciónál fontos az állandósult változás

O (frat): a játékosok testvéries osztozkodást feltételezve választanak új stratégiát 14

Összegzés 1) A potenciál játék fogalma segíti - a jelenségek értelmezését - a tiszta Nash egyensúlyok megtalálását

2) Az evolúciós potenciál játékok - segítik a „jobb” Nash egyensúlyok megtalálását - kiterjesztik és definiálják a termodinamika érvényességét a társadalmi jelenségekre

3) A potenciál játék nem különleges ritkaság

4) A potenciál játéktól való eltérés a dinamikai folyamatok hátterében megbúvó kölcsönhatásként értelmezhető

Köszönöm a figyelmet

15