THE: Evoluˇcn´ı teorie her Evolutionary Game Theory Martin Hrub´y Brno University of Technology Brno Czech Republic
December 4, 2014
Martin Hrub´ y
Evoluˇ cn´ı teorie her
´ Uvod ˇ ano z: Cerp´ ◮
John Maynard Smith, George R. Price: The logic of animal conflict. Nature 246:15-18.
◮
Nisan et al.: Algorithmic Game Theory
◮
Dugatkin, L.A., Reeve, H.K. (editors): Game Theory and Animal Behavior, Oxford, 1998
◮
Vincent, T.L., Brown, J.S.: Evolutionary Game Theory, Natural Selection, and Darwinian Dynamics, Cambridge, 2005
◮
Magdal´ena Hykˇsov´ a: Pˇredn´ aˇsky z Teorie her, Fakulta ˇ dopravn´ı, CVUT
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Evoluˇcn´ı teorie her
Poˇc´atky: John Maynard Smith, George R. Price: The logic of animal conflict. Nature 246:15-18. ◮
Aplikace THE na strategick´e interakce ˇzivoˇciˇsn´ych druh˚ u.
◮
Zaveden´ı Evoluˇcnˇe stabiln´ı strategie (ESS)
◮
Uk´azalo se, ˇze principy chov´ an´ı rostlin a ˇzivoˇcich˚ u pˇri vz´ajemn´ych interakc´ıch lze zat´ım nejl´epe objasnit prostˇredky teorie her.
Dokonce se ukazuje (pr´y), ˇze nejvhodnˇejˇs´ı aplikace THE jsou pr´avˇe v biologii.
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Evoluce a Teorie her Velmi neform´alnˇe, bez n´ arok˚ u na odbornou vˇernost: ◮
Kdysi na poˇc´atku vznikl organismus schopn´y replikace (mnoˇzen´ı). Vznikla populace jedinc˚ u.
◮
V r´amci replikace m˚ uˇze doch´ azet k mutac´ım. Nevznikne klon jedince, ale modifikovan´ a verze – ta m´ a pˇr´ıleˇzitost uk´azat, zda-li je schopnˇejˇs´ı v pˇreˇzit´ı.
◮
Boj o zdroje, u ´zem´ı, ...
◮
Projevem evoluce tedy bylo vytvoˇrit n´ astroje na pˇreˇzit´ı.
◮
Budeme muset identifikovat hr´ aˇce, strategie a formu zisku.
Pˇres veˇsker´e filosofick´e u ´vahy o smyslu byt´ı, lze pˇredpokl´adat, ˇze nejv´ıc nejd˚ uleˇzitˇejˇs´ım c´ılem je pˇreˇz´ıt a rozmnoˇzit se. Evoluˇcn´ı THE aspoˇ n takto hodnot´ı kvalitu jedince.
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Co oˇcek´av´ame od spojen´ı evoluce a Teorie her? ◮
Co oˇcek´av´a biolog? Co oˇcek´ av´ a sociolog? A co matematik?
◮
Biolog si odpov´ı ot´ azky v´yvoje druh˚ u a pochop´ı proˇc evoluce dopadla jak dopadla (ona tedy st´ ale pokraˇcuje...).
◮
Sociolog/psycholog/ekonom/prognostik si na modelech uvˇedom´ı podobnosti s chov´ an´ım lid´ı.
◮
Zˇrejmˇe nikdo nechce predikovat chov´ an´ı ... v situaci ... ˇ Experimenty a korelace s realitou: C´ım je druh jednoduˇsˇs´ı, t´ım jeho chov´an´ı v´ıce odpov´ıd´ a matematick´emu modelu – a to vˇcetnˇe sm´ıˇsen´ych strategi´ı.
◮
◮
◮
Severoamerick´a kutilka (druh vosy) – klade vaj´ıˇcka do d´ıry v zemi spoleˇcnˇe s jejich budouc´ı potravou. Strategie: kopat vlastn´ı d´ıru, pouˇz´ıt jiˇz existuj´ıc´ı. Pozorov´an´ım bylo zjiˇstˇeno (na konkr´etn´ıch jedinc´ıch) sm´ıˇsen´e chov´an´ı, kter´e odpov´ıd´a racion´aln´ımu modelu. Obvyklejˇs´ı je gen. polymorfismus – urˇcit´a ˇc´ast populace prov´ad´ı jednu strategii, jin´a ˇc´ast populace jinou. Martin Hrub´ y
Evoluˇ cn´ı teorie her
Hr´aˇc, strategie a zisk P˚ ujdeme na samotnou podstatu vˇeci. ◮
◮
◮
◮
◮
Budeme ˇreˇsit element´ arn´ı interakce mezi jedinci. Neˇreˇs´ıme tud´ıˇz, proˇc si jedinec ”Franta” koup´ı Fiat m´ısto Renaulta. Vˇsechno jsou to projevy ”nˇekoho v pozad´ı”. Za vˇs´ım stoj´ı geny. Geny vol´ı strategii jedince ve hˇre o pˇreˇzit´ı a reprodukci. Strategie – behavior´ aln´ı fenotyp (fenotyp – soubor vˇsech pozorovateln´ych vlastnost´ı a znak˚ u organismu), tj. program ud´avaj´ıc´ı, jak bude jedinec konat v r˚ uzn´ych situac´ıch. Jedinec m´a jednu strategii nebo je schopen pro danou situaci strategii zvolit. V´yplatn´ı funkce – pˇredpoklady pro reprodukci.
Myˇslenka (R. Dawkins): Jedinci jsou geny. My jsme jejich n´ astroje (schr´anky) k pˇreˇzit´ı. Lety vz´ajemn´ych souboj˚ u gen˚ u se geny uˇcily a vyv´ıjely. Martin Hrub´ y
Evoluˇ cn´ı teorie her
Zbraˇnov´e vybaven´ı ˇzivoˇciˇsn´eho druhu
◮
Pˇreˇzij´ı ti nejvˇetˇs´ı?
◮
nebo ti s nejvˇetˇs´ımi zuby a dr´ apy?
◮
nebo ti nejagresivnˇejˇs´ı?
◮
nebo ti m´ırumilovn´ı?
Technick´a v´ybava jedince a fenotyp jeho chov´ an´ı? Hodn´y drak nepotˇrebuje zuby a agresivn´ı myˇs sotva nˇekoho poraz´ı. R. Dawkins: Pˇr´ıbˇeh pˇredka, Academia, 2008
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Evoluˇcnˇe stabiln´ı strategie (ESS)
J. M. Smith, G. R. Price (1973): ◮
ESS je strategie takov´ a, ˇze pokud je pˇrijata ˇcleny populace, pak je tato populace imunn´ı v˚ uˇci pˇr´ıpadn´emu mutantovi.
◮
Je to zpˇresnˇen´ı (refinement) Nashova ekvilibria, tzn. pokud je pˇrijato populac´ı, pak staˇc´ı jednoduch´ a logika pˇrirozen´eho v´ybˇeru na to, aby se populace zabezpeˇcila v˚ uˇci pˇr´ıpadn´emu mutantovi.
◮
ESS tedy tvoˇr´ı strategick´y profil s nˇejak´ymi vlastnostmi.
◮
M˚ uˇze existovat ryz´ı nebo sm´ıˇsen´ a podoba ESS.
◮
ESS tvoˇr´ı refinement NE, tzn. ne vˇsechna NE jsou ESS.
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Demo ESS Mˇejme nekoneˇcnˇe velkou (velikost je tedy dostateˇcn´a a nen´ı limituj´ıc´ı) populaci jedinc˚ u, kteˇr´ı se mnoˇz´ı asexu´ alnˇe. Jedinci se navz´ajem stˇret´avaj´ı po dvojic´ıch, tedy hraj´ı nekooperativn´ı hry dvou hr´aˇc˚ u s v´yplatn´ımi funkcemi u1 , u2 . Strategie I je evoluˇcnˇe stabiln´ı, pokud pro kaˇzdou strategii J 6= I plat´ı: u1 (I , I ) > u1 (J, I ) u1 (I , I ) = u1 (J, I ) ∧ u1 (I , J) > u1 (J, J) Je-li I ESS, pak (I , I ) je NE. Jak´y efekt m´a prohra?
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Evoluˇcnˇe stabiln´ı strategie
Definition ESS je strategie takov´ a, ˇze pokud ji pˇrijme vˇetˇsina populace, pak neexistuje mutantsk´a strategie, kter´ a by byla reprodukˇcnˇe u ´spˇeˇsnˇejˇs´ı. (Smith and Price, 1973) Pozn.: populace ji ”nepˇrijme”, ona ji reprezentuje. V´yvojov´y pohled: V´yvoj st´ ale prob´ıh´ a – ESS je zjednoduˇsuj´ıc´ı model a d´av´a smysl pˇri zn´ am´e mnoˇzinˇe strategi´ı. Neuvaˇzujeme pˇr´ıchod zcela nov´e strategie (v tomto smˇeru je pojem ”mutant” moˇzn´a nevhodn´y).
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Form´aln´ı definice ESS, THE-hledisko Mˇejme nekoneˇcnˇe velkou (velikost je tedy dostateˇcn´a a nen´ı limituj´ıc´ı) populaci jedinc˚ u, kteˇr´ı se mnoˇz´ı asexu´ alnˇe. Jedinci se navz´ajem stˇret´avaj´ı po dvojic´ıch, tedy hraj´ı nekooperativn´ı hry dvou hr´aˇc˚ u (tzv. vnitˇrn´ı hra). Pˇredpokl´adejme, ˇze vnitˇrn´ı hra Γ = ({A, B}; Ss ; U) je symetrick´a, U(s|t) ˇcteme uˇzitek hr´ aˇce hraj´ıc´ıho strategii s proti strategii t. Pojmem ∆(Ss ) budeme rozumˇet sm´ıˇsen´e rozˇs´ıˇren´ı Ss .
Definition Strategie I ∈ Ss je evoluˇcnˇe stabiln´ı, pokud pro kaˇzdou strategii J ∈ Ss , J 6= I plat´ı: U(I |I ) > U(J|I ) nebo U(I |I ) = U(J|I ) ∧ U(I |J) > U(J|J) Martin Hrub´ y
Evoluˇ cn´ı teorie her
Form´aln´ı definice ESS, THE-hledisko
Theorem Je-li I ESS, pak (I , I ) je NE. K n´aznaku d˚ ukazu se dostaneme d´ ale. Pozn´amka: ESS je refinement NE, tzn. nen´ı to ekvivalent NE, tzn. existuj´ı NE, kter´a nejsou sloˇzena z ESS.
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Form´aln´ı definice ESS, THE-hledisko
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Form´aln´ı definice ESS, THE-hledisko Jin´a definice (pˇredpokl´ ad´ a v´yskyt mutanta s ˇcetnost´ı ǫ):
Definition Strategie s je ESS pro dvouhr´ aˇcovou symetrickou hru Γ = (Q; Ss ; U), jestliˇze pro kaˇzdou t 6= s, existuje ǫt ∈ h0, 1i takov´e, ˇze pro kaˇzd´e ǫ, 0 < ǫ < ǫt , plat´ı (1 − ǫ)U(s|s) + ǫU(s|t) > (1 − ǫ)U(t|s) + ǫU(t|t)
Theorem Strategie s je ESS pro dvouhr´ aˇcovou symetrickou hru Γ = (Q; Ss ; U), jestliˇze (s, s) je NE v Γ a pro kaˇzdou best-response t na s, kde t 6= s, plat´ı U(s|t) > U(t|t).
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Tvoˇr´ı ESS Nashovo ekvilibrium? Situace (Skinner˚ uv chl´ıvek): m´ ame dvˇe prasata (dominantn´ı a submisivn´ı) zavˇren´a ve chl´ıvku vybavan´em p´ akou a korytem. Kdyˇz se stiskne p´aka, do koryta spadne ˇzr´ adlo s energetickou hodnotou 10 jednotek. Cesta k p´ ace a zp´ atky ke korytu spotˇrebuje 2 jednotky energie. Dominantn´ı prase v souboji o koryto vˇzdy v´ıtˇez´ı.
ˇ ESS je: jsi-li dominantn´ı prase, maˇckej p´ aku. Jsi-li submisivn´ı, sed u koryta. dominantn´ı/submisivn´ı stiskni p´ aku stiskni p´aku 8,-2 ˇ u koryta sed 10,-2 Martin Hrub´ y
Evoluˇ cn´ı teorie her
ˇ u koryta sed 5,3 0,0
Klasick´y demopˇr´ıklad: Jestˇr´abi a hrdliˇcky (Hawks and Doves) ◮
Jestˇr´abem a hrdliˇckou nemysl´ıme konkr´etn´ı ˇzivoˇciˇsn´e druhy !!!
◮
Je t´ım m´ınˇen charakter chov´ an´ı libovoln´eho jedince (genetick´y fenotyp).
◮
Jestˇr´ab vˇzdy u ´toˇc´ı a konˇc´ı aˇz pˇri v´ aˇzn´em zranˇen´ı.
◮
Hrdliˇcka hroz´ı pouze symbolicky, pˇri pˇr´ım´em u ´toku prch´ a (nezranˇena).
◮
Zisk z v´ıtˇezstv´ı – V , ztr´ ata ze zranˇen´ı – C .
Kter´a ze strategi´ı (H,D) m´ a vˇetˇs´ı ˇsanci na pˇreˇzit´ı? Hawk Hawk Dove
V −C V −C 2 , 2
0, V
Martin Hrub´ y
Dove V,0 V V 2, 2
Evoluˇ cn´ı teorie her
Hawks and Doves Hawk Hawk Dove
V −C V −C 2 , 2
0, V
Dove V,0 V V 2, 2
◮
Strategie Dove nen´ı ESS, protoˇze populaci hrdliˇcek m˚ uˇze napadnout jeden mutant (jestˇr´ ab), kter´y pak v n´ı bude velmi dobˇre prosperovat. Nav´ıc (D, D) nen´ı NE.
◮
Je-li V > C , pak je ESS b´yt jestˇr´ abem.
◮
Pˇr´ıklad: rypouˇs slon´ı (V >> C ), velmi ostr´e souboje.
◮
Je-li V < C , pak neexistuje ryz´ı NE, ale sm´ıˇsen´e, kde se hraje H s pravdˇepodobnost´ı V /C
H-D jako nekoneˇcnˇe-kr´at opakovan´ a hra. Lze uvaˇzovat kooperativn´ı chov´an´ı? Martin Hrub´ y
Evoluˇ cn´ı teorie her
Hawks and Doves
Uk´aˇzeme, ˇze H je ESS pro V > C : mˇejme sm´ıˇsenou strategii t = (p, 1 − p), kter´a s pravdˇepodobnost´ı p ∈ h0, 1) hraje H. V´ıme, ˇze U(H|H) =
V −C 2 .
Pak
V −C V −C + (1 − p)0 < 2 2 tedy U(H|H) > U(t|H); ∀t 6= H, tzn. ∀t 6= (1, 0). U(t|H) = p
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Demo: Vˇcely
Small Large
Small 5,5 8,1
Large 1,8 3,3
Kter´a strategie je ESS? 1) Pˇredpokl´adejme, ˇze je ESS b´yt mal´ a vˇcela (Small). Pak je oˇcek´avan´y uˇzitek mal´e vˇcely 5(1 − x) + 1 · x = 5 − 4x a velk´e vˇcely: 8(1 − x) + 3 · x = 8 − 5x Lze uk´azat, ˇze pro dostateˇcnˇe mal´e x je lepˇs´ı b´yt velk´a vˇcela neˇz mal´a, tzn. Small nen´ı ESS. Martin Hrub´ y
Evoluˇ cn´ı teorie her
Demo: Vˇcely
Small Large
Small 5,5 8,1
Large 1,8 3,3
Kter´a strategie je ESS? 2) Pˇredpokl´adejme, ˇze je ESS b´yt velk´ a vˇcela (Large). Pak je oˇcek´avan´y uˇzitek mal´e vˇcely (1 − x) + 5 · x = 1 + 4x a velk´e vˇcely: 3(1 − x) + 8 · x = 3 + 5x Lze uk´azat, ˇze pro dostateˇcnˇe mal´e x je lepˇs´ı b´yt velk´a vˇcela neˇz mal´a, tzn. Large je ESS. Martin Hrub´ y
Evoluˇ cn´ı teorie her
Smith, Price: The Logic of Animal Conflict, Nature, 1973 ◮
Konflikty mezi jedinci v r´ amci jednoho druhu mohou v´est ke zv´yhodnˇen´ı v´ıtˇeze (teritorium, soupeˇren´ı o samiˇcku, potrava).
◮
Mohlo by se zd´at, ˇze evoluce vyvine schopnosti (a pudy) jedinc˚ u k tot´aln´ımu zlikvidov´ an´ı protivn´ıka (”total war”).
◮
Paradoxnˇe evoluce vyvinula schopnosti slab´e, obvykle se konflikt odehraje na u ´rovni ritu´ al˚ u (”limited war”). Je obava z v´aˇzn´eho zranˇen´ı, kter´e jedinci v pˇr´ırodˇe znaˇcnˇe zkomplikuje ˇzivot.
◮
Pˇr´ıklad limited wars: hadi se jenom ”pˇretahuj´ı” bez pouˇzit´ı zub˚ u, rohy beran˚ u jsou zakroucen´e, ...
◮
Proˇc se tedy protivn´ıci nechtˇej´ı zlikvidovat? Proˇc jim to pˇr´ıroda komplikuje?
Ono by to totiˇz vedlo k z´ aniku takov´eho pˇr´ıliˇs bojovn´eho druhu. Martin Hrub´ y
Evoluˇ cn´ı teorie her
Smith, Price: case-study Pˇredpokl´adejme dvˇe z´ akladn´ı strategie hr´ aˇce (jedince): ◮
Conventional (C ) – nen´ı c´ılem v´ aˇznˇe zranit soupeˇre.
◮
Dangerous (D) – c´ılem je v´ aˇznˇe zranit soupeˇre. K tomu m˚ uˇze doj´ıt, pokud bude uplatˇ nov´ ana opakovanˇe.
◮
Pˇr´ıklad s hady: C je se pˇretahovat, D je kousnout.
U mnoha druh˚ u je strategi´ı C pouze pˇredv´ adˇet hrozbu. Pˇredpoklady: ◮
Hr´aˇci se v taz´ıch stˇr´ıdaj´ı (sekvenˇcn´ı situace, opakovanˇe). V kaˇzd´em tahu hr´aˇc m˚ uˇze zvolit C , D nebo R (ut´ect).
◮
Pokud zvol´ı D, je tu konstantn´ı pravdˇepodobnost, ˇze protivn´ıka v´aˇznˇe zran´ı (ten pak vˇzdy vol´ı R).
◮
Pokud hr´aˇc zvol´ı R, je konec boje a protihr´ aˇc se st´av´a v´ıtˇezem. Martin Hrub´ y
Evoluˇ cn´ı teorie her
Pˇr´ıklad souboje
kolo tah (I) reakce (II) ◮
1 C C
2 C C
3 C C
4 D D
5 C C
6 C C
7 C C
8 D R
Hr´aˇci se 3 kola oˇtuk´ avaj´ı
◮
pak ve 4. kole zahraje I strategii D a II odpov´ı D p´ar kol zase oˇtuk´av´ an´ı
◮
v osm´em kole I zahraje D a II uteˇce
◮
I je v´ıtˇez (a nikdo nen´ı zranˇen)
◮
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Pˇr´ıklad souboje: v´ysledky ◮
Zahr´at D nebo D v reakci na C se naz´yv´ a provokace (probe, provocation)
◮
Provokace v prvn´ım tahu se naz´yv´ a eskalace konfliktu (m´a konflikt pˇren´est z C do D)
◮
Hr´aˇc odpov´ıdaj´ıc´ı D na provokaci je odvetn´ık
◮
V naˇsem pˇr´ıkladˇe: v osm´em kole I zahraje D a II uteˇce. I je v´ıtˇez (a nikdo nen´ı zranˇen)
V´ysledkem souboje je nˇejak´y zisk, kter´y zohledˇ nuje tˇri faktory do pˇr´ınosu hr´aˇce v jeho reprodukˇcn´ım procesu: ◮
Pˇr´ınos z v´ysledku souboje, kter´y porovn´ av´ ame se ztr´atou v pˇr´ıpadˇe prohry.
◮
Ztr´ata z moˇzn´eho v´ aˇzn´eho zranˇen´ı.
◮
Ztr´ata z investovan´eho ˇcasu a energie v souboji. Martin Hrub´ y
Evoluˇ cn´ı teorie her
Pˇr´ıklad: strategie Za strategii budeme povaˇzovat koncept chov´ an´ı hr´aˇce v souboji (jakoby jeho ”mentalitu”). Podobnˇe jako u opakovan´ych her: ◮
◮
◮
◮
◮
Myˇs (mouse) – nikdy nehraje D, na tah D reaguje R (D ⇒ R). Jinak hraje C do konce. Jestˇr´ab (hawk) – vˇzdy hraje D. Pokraˇcuje v D, dokud nen´ı v´aˇznˇe zranˇen on nebo protivn´ık. N´asiln´ık (bully) – pokud zaˇc´ın´ a, pak zahraje D. Jinak vˇzdy C ⇒ D. Pokud protivn´ık podruh´e zahraje D, ut´ık´a (R). Odvetn´ık (retaliator) – zaˇc´ın´ a s C, pak vˇzdy C ⇒ C (pokud ovˇsem poˇcet kol pˇres´ ahne mez, hraje R). Pokud soupeˇr hraje D, pak s vysokou pravdˇepodobnost´ı D ⇒H D. Provokat´er-odvetn´ık (prober-retaliator) – pokud zaˇc´ın´a nebo v reakci na C hraje: C ⇒H C nebo C ⇒L D (ovˇsem R, pokud se pˇres´ahne mez poˇctu kol). Pokud zahraje D (provokace), pak v dalˇs´ım kole hraje C, pokud protivn´ık odpov´ı D. Jinak si troufne znova. Pokud protivn´ık zahraje D, pak D ⇒H D. Martin Hrub´ y
Evoluˇ cn´ı teorie her
Pˇr´ıklad: experiment ◮ ◮
Tˇechto 5 strategi´ı d´ av´ a 15 moˇzn´ych druh˚ u z´ apasu ( 52 + 5). Autoˇri provedli 2000 experiment˚ u pro kaˇzd´y druh z´apasu.
D´ale, nastaven´ı kl´ıˇcov´ych pravdˇepodobnost´ı jev˚ u: ◮ V´ aˇzn´e zranˇen´ı hr´aˇce, pokud protihr´ aˇc zahraje D: 0.10, ◮ Provokat´ er-odvetn´ık zahraje D v prvn´ım tahu nebo v reakci na C: 0.05. ◮ Provokat´ er nebo Provokat´er-odvetn´ık zahraje D (pokud nedoˇslo ke zranˇen´ı) v reakci na D: 1.00. Zisky: ◮ ◮ ◮
◮
V´ıtˇezstv´ı: 60 V´aˇzn´e zranˇen´ı: -100 Mal´e zranˇen´ı (po kaˇzd´em pˇrijat´em D, kter´e nezp˚ usobilo v´aˇzn´e zranˇen´ı – tzv. ˇskr´ abnut´ı): -2 ´ Uspora ˇcasu a energie pˇri vyhnut´ı se z´ apasu: od 0 do 20 podle okamˇziku R Martin Hrub´ y
Evoluˇ cn´ı teorie her
Pˇr´ıklad: v´ysledky (Smith and Price, 1973) Zisk je urˇcen pro ˇr´adkov´eho hr´ aˇce (situace oponenta m˚ uˇzeme vidˇet transponovanˇe): Myˇs Jestˇr´ ab N´ asiln´ık Odvetn´ık Provokat´er-o. Myˇs 29.0 19.5 19.5 29.0 17.2 80.0 -19.5 74.6 -18.1 -18.9 Jestˇr´ab N´asiln´ık 80.0 4.9 41.5 11.9 11.2 29.0 -22.3 57.1 29.0 23.1 Odvetn´ık Provokat´er-o. 56.7 -20.1 59.4 26.9 21.9 Zkoumejme ESS na sloupc´ıch tabulky: pro jestˇr´ ab´ı populaci (sloupec jestˇr´ab˚ u): je nejlepˇs´ı odpovˇed´ı b´yt jestˇr´ ab? Jestˇr´abi, chovaj´ıc´ı se jako myˇsi nebo n´ asiln´ıci, maj´ı v populaci jestˇr´ab˚ u lepˇs´ı vyhl´ıdky na pˇreˇzit´ı (b´yt jestˇr´ ab nen´ı ESS). Odvetn´ık je ESS (myˇs je ovˇsem stejnˇe dobr´ a). Martin Hrub´ y
Evoluˇ cn´ı teorie her
Pˇr´ıklad: z´avˇery
◮
Odvetn´ık je nejstabilnˇejˇs´ı strategie.
◮
Provokat´er-Odvetn´ık vyuˇz´ıv´ a schopnosti ”provokace” k pˇrevaze nad myˇs´ı.
◮
Lze uk´azat, ˇze pokud je v populaci alespoˇ n 7% myˇs´ı, pak pˇrevl´adne provok´at´er-odvetn´ık nad odvetn´ıkem.
◮
M˚ uˇzeme pˇredpokl´ adat urˇcitou ˇc´ ast populace s chov´an´ım myˇsi (nemocn´e, star´e, slab´e), kteˇr´ı se chovaj´ı jako myˇs z jin´ych d˚ uvod˚ u, neˇz genetick´ych.
◮
Studie ukazuje lepˇs´ı pˇredpoklady pro pˇreˇzit´ı u ”limited war” strategi´ı (narozd´ıl od ”total war” jestˇr´ aba). ´ ek nese uˇzitek z moˇzn´eho pˇreˇzit´ı. Utˇ
◮
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Pˇr´ıklad: z´avˇery
◮
V´ysledky jsou samozˇrejmˇe ovlivnˇeny nastaven´ymi pravdˇepodobnostmi, pokud bude pravdˇepodobnost v´aˇzn´eho zranˇen´ı 0.9 jako reakce na strategii D, pak pochopitelnˇe jestˇr´abi v´ıtˇez´ı (udeˇr´ı prvn´ı).
◮
Situace je nav´ıc jin´ a pˇri zmˇenˇe zisku u strategie R – pokud se bude zisk pˇri u ´tˇeku rovnat zisku pˇri zranˇen´ı (nˇekter´e druhy maj´ı pouze jednu pˇr´ıleˇzitost k reprodukci), pak opˇet v´ıtˇez´ı jestˇr´abi.
◮
Naopak, pokud zisk z v´yhry je kladn´y, zisk z u ´tˇeku nulov´y a zisk ze zranˇen´ı znaˇcnˇe z´ aporn´y, pak dostaneme populaci velmi m´ırumilovn´ych tvor˚ u.
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Re´aln´a zv´ıˇrata ◮
Zˇrejmˇe jsou re´aln´e situace koˇsatˇejˇs´ı neˇz tento model.
◮
Obecnˇe ovˇsem z´avˇery modelu funguj´ı: ˇc´ım v´ıc je druh bojovˇe vybavenˇejˇs´ı, t´ım m´enˇe se dopouˇst´ı D-strategi´ı v konfliktech se sv´ymi soukmenovci (nebo je tˇreba mnoho provokac´ı, aby se konflikt eskaloval).
◮
Jedinci mohou pouˇz´ıvat ”testy” (zkouˇsen´ı C a D) na zjiˇstˇen´ı, jak´eho typu je jejich protivn´ık (C nebo D).
◮
T´ım mohou jedinci dos´ ahnout informace o stavu protivn´ıka a l´epe se rozhodovat o akci R.
◮
Obvykl´e jsou pak strategie Provokat´er-odvetn´ık a myˇs.
Provokat´er-odvetn´ık a Myˇs jsou zˇrejmˇe z´ akladem stabiln´ı spoleˇcnosti (jestˇr´ab brzy naraz´ı, n´ asiln´ık je zbabˇelec a odvetn´ık je m´alo d˚ urazn´y). Martin Hrub´ y
Evoluˇ cn´ı teorie her
Re´aln´a zv´ıˇrata
◮
V situaci mnoha jestˇr´ ab˚ u (nebo naopak myˇs´ı) lze pˇredst´ırat jinou strategii neˇz je mi vlastn´ı.
◮
M´ame opˇet probl´em hrozby (threat), kter´ a mus´ı b´yt d˚ uvˇeryhodn´a. Pak protivn´ık ustoup´ı (Game of chicken) protivn´ıkovi odhodlan´emu k sebedestrukci. Pˇr´ıkladem jsou periody ”musth” u slon´ıch samc˚ u, kdy jsou tito extr´emnˇe agresivn´ı. Ostatn´ı jim radˇeji ustoup´ı a oni pak maj´ı ˇsanci oplodnit samici.
◮
Podobnou hrozbu najdeme napˇr. v seversk´e (vikingsk´e) literatuˇre o berserc´ıch – bojovn´ıc´ıch, kteˇr´ı se dost´avali v boji do extatick´eho stavu, kdy projevovali nadlidsk´e fyzick´e schopnosti a vˇsichni jim ustupovali
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Konflikty mezi jedinci, kteˇr´ı si nejsou schopni pˇrivodit v´aˇzn´e zranˇen´ı Pˇredpokl´ad´ame, ˇze bojovnˇe vybaven´ı jedinci se v r´amci sv´eho druhu zraˇ novat nebudou. ◮
Druhy, kter´e nejsou vybaveny ”zbranˇemi” tak´e vstupuj´ı do konfliktu. Obvykle pak v´ıtˇez´ı ten, kter´y v konfliktu d´ele vydrˇz´ı (neuteˇce).
◮
Pˇredpokl´ad´ame d´ ale, ˇze jedinci si uvˇedomuj´ı d´elku konfliktu. Rozhodnut´ı o d´elce jejich vytrv´ an´ı v konfliktu – mi je jejich strategi´ı.
◮
Pˇredpokl´adejme zisk pro v´ıtˇeze – v . Pˇredpokl´adejme dva jedince, ˇze m1 > m2 .
◮
Pak je u1 = v − m2 , u2 = −m2 .
◮
Je ˇsance odhadnout moje mi ? Existuje ESS? Martin Hrub´ y
Evoluˇ cn´ı teorie her
...Existuje zde ryz´ı ESS? Definujme U(I |J) jako oˇcek´ avan´y zisk pˇri hran´ı I proti J (protihr´aˇc hraje J). Z definice pak U(I |I ) > U(J|I ) U(I |I ) = U(J|I ) ∧ U(I |J) > U(J|J) jinak by v populaci s pˇrevl´ adaj´ıc´ı I pˇr´ıchoz´ı mutant (J) zp˚ usobil pˇrechod ke strategii J. ◮ ◮
◮
◮
Lze uk´azat, ˇze neexistuje ryz´ı ESS. Mutant s I + ǫ na tom bude vˇzdy l´epe. Dokonce, pokud m > v , pak mutant hraj´ıc´ı m2 = 0 bude taky l´epe prosperuj´ıc´ı. Mutant s I + ǫ zp˚ usob´ı pˇrerod spoleˇcnosti v I + ǫ. Tzn., d´elky souboj˚ u by ˇsly k nekoneˇcnu. Zkus´ıme naj´ıt sm´ıˇsenou ESS. Martin Hrub´ y
Evoluˇ cn´ı teorie her
...Sm´ıˇsen´a ESS
Strategie I jedince je d´ ana: ◮
Pˇredpokl´adejme, ˇze jedinec vyb´ır´ a svou m z intervalu hx, x + δi s pravdˇepodobnost´ı p(x)δ.
◮
I je ESS, pokud: p(x) =
−x 1 exp v v
Nem˚ uˇze existovat stabiln´ı populace s konstantn´ım chov´an´ım – mus´ı m´ıt prvky sm´ıˇsenosti.
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Dynamika v Evoluˇcn´ı teorii her Pˇredpokl´adejme populaci s dostateˇcnˇe mnoha jedinci (nen´ı podstatn´e), kde se odehr´ avaj´ı konflikty na u ´rovni dvouhr´aˇcov´ych nekooperativn´ıch her s nenulov´ym souˇctem. ◮
◮
◮
◮
◮
Nechˇt U(s|r ) je oˇcek´ avan´y zisk hr´ aˇce hraj´ıc´ıho s, kdy protihr´aˇc hraje r . Pˇredpokl´adejme k strategi´ı s1 , s2 , ..., sk , kter´e m˚ uˇzou ˇclenov´e populace hr´at. Nechˇt xi znaˇc´ı relativn´ı zastoupen´ı strategie si v populaci, x = (x1 , ..., xk ). Nechˇt wi (x) je fitness hr´ aˇce hraj´ıc´ıho si v populaci s rozloˇzen´ım strategi´ı x. D´ale, w (x) je stˇredn´ı hodnota pˇres celou populaci.
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Dynamika v Evoluˇcn´ı teorii her Stav x ′ odvozen´y z x je d´ an diferenˇcn´ı rovnic´ı naz´yvanou diskr´etn´ı replik´atorsk´a rovnice s frekvenˇcnˇe-z´ avislou fitness funkc´ı: x ′ = xi
wi (x) ; ∀i = 1, ..., k w (x)
Co je ta fitness? wi (x) = w0 +
k X
xj U(si |sj ); ∀i = 1, ..., k
j=1
kde w0 je z´akladn´ı oˇcek´ av´ an´ı populace, kdyby nemuseli hru hr´at (nedoch´azelo by k interakc´ım).
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Dynamika v Evoluˇcn´ı teorii her – pˇr´ıklady
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Dynamika v Evoluˇcn´ı teorii her – pˇr´ıklady
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Nashovo ekvilibrium Jak´y je vztah ESS a NE? Pokud m´a b´yt strategie s1 ESS, pak by v´yskyt mutanta s2 s frekvenc´ı ǫ mˇel d´at populaci st´ ale pozitivn´ı fitness w1 (x) − w2 (x). Pˇredpokl´adejme, ˇze x2 = ǫ je frekvence mutant´ı strategie s2 , strategie s1 m´a frekvenci x1 = 1 − ǫ. Pak obdrˇz´ıme: w1 (x) − w2 (x) = = (1 − ǫ)U(s1 |s1 ) + ǫU(s1 |s2 ) − (1 − ǫ)U(s2 |s1 ) − ǫU(s2 |s2 ) = = (1 − ǫ)[U(s1 |s1 ) − U(s2 |s1 )] + ǫ[U(s1 |s2 ) − U(s2 |s2 )]
Martin Hrub´ y
Evoluˇ cn´ı teorie her
Nashovo ekvilibrium
w1 (x)−w2 (x) = (1−ǫ)[U(s1 |s1 )−U(s2 |s1 )]+ǫ[U(s1 |s2 )−U(s2 |s2 )] Kdy je v´yraz kladn´y? Pro dostateˇcnˇe mal´e ǫ (v ESS oˇcek´av´ame mutantn´ı v´yskyt dostateˇcnˇe m´ alo frekventovan´y) je urˇcuj´ıc´ı prvn´ı ˇclen v´yrazu, a ten je kladn´y pro U(s1 |s1 ) > U(s2 |s1 ). Plyne z toho, ˇze s1 mus´ı b´yt best-response na s1 – a (s1 , s1 ) je tud´ıˇz NE. Pokud pˇresto pˇripouˇst´ıme, ˇze i s2 m˚ uˇze b´yt best-response na s1 , tedy, ˇze U(s1 |s1 ) = U(s2 |s1 ), pak je pro kladnost v´yrazu rozhoduj´ıc´ı druh´y ˇclen. Pokud tedy U(s1 |s1 ) = U(s2 |s1 ), pak mus´ı platit U(s1 |s2 ) > U(s2 |s2 ). Martin Hrub´ y
Evoluˇ cn´ı teorie her
Evoluˇcn´ı dynamika aplikovan´a na sobeck´e smˇerov´an´ı (Selfish Routing) ◮
M´ame s´ıˇt danou grafem G = (V , E ). Zkoum´ ame komunikaci mezi uzly s, t ∈ V vedenou po vˇsech moˇzn´ych cest´ach P.
◮
Jedinci populace jsou agenti smˇeruj´ıc´ı svou komunikaci s − t po r˚ uzn´ych cest´ach p ∈ P.
◮
Zkoum´ame komunikaˇcn´ı dobu na jednotliv´ych cest´ach (latence).
◮
Pˇredpokl´ad´ame, ˇze v kaˇzd´em kole se agenti potk´avaj´ı v n´ahodn´ych p´arech (a1 , a2 ) a sdˇeluj´ı si zkuˇsenosti s posledn´ım kolem. Pokud agent ai zjist´ı, ˇze agent aj komunikuje h˚ uˇr, z˚ ust´av´a u sv´e cesty, jinak se inspiruje aj .
◮
Lze uk´azat, ˇze syst´em evoluc´ı dojde do stavu rovnomˇern´eho zat´ıˇzen´ı s´ıtˇe pˇrenosem pˇres vˇsechny moˇzn´e cesty (Nash flow). Martin Hrub´ y
Evoluˇ cn´ı teorie her
Pˇr´ıˇstˇe
◮
Aplikace THE v modelov´ an´ı energetick´ych trh˚ u.
◮
Z´avˇereˇcn´e opakov´ an´ı – kter´e partie byly problematick´e?
◮
Steve Brams: Theory of Moves.
Martin Hrub´ y
Evoluˇ cn´ı teorie her
