ˇ Z ÁPADO CESKÁ U NIVERZITA V P LZNI ˇ FAKULTA A PLIKOVANÝCH V ED K ATEDRA M ATEMATIKY
ˇ BAKALÁ RSKÁ PRÁCE ˇ E VOLU CNÍ DYNAMIKA MALÝCH POPULACÍ
P LZE Nˇ , 2015
D ANIEL Š PALE
Prohlášení Pˇredkládám tímto k posouzení a obhajobˇe bakaláˇrskou práci zpracovanou na závˇer studia na Fakultˇe aplikovaných vˇed Západoˇceské univerzity v Plzni. Prohlašuji, že jsem bakaláˇrskou práci vypracoval samostatnˇe a výhradnˇe s použitím odborné literatury a pramenu, ˚ jejichž úplný seznam je její souˇcástí.
V Plzni, dne 27. kvˇetna 2015 ......................................... vlastnoruˇcní podpis
Podˇekování Tímto bych chtˇel podˇekovat doc. RNDr. Petru Stehlíkovi, Ph.D. za vstˇrícnost, trpˇelivost a odborné rady pˇri konzultacích a psaní této práce. Dˇekuji i své rodinˇe a pˇrátelum ˚ za podporu.
Abstrakt Cílem této práce je cˇ tenáˇre seznámit se základními principy teorie evoluˇcní dynamiky a evoluˇcních her na grafech obzvlášt’ ve vztahu k vývoji spolupráce. Hlavní pozornost bude následnˇe upˇrena na nový model podle vzoru replikátorové dynamiky pro vývoj spolupráce populací, které jsou spojeny v jednom grafu. Dále je provedena analýza modelu jako takového stejnˇe jako analýza jeho dynamických vlastností. Nakonec je model vyzkoušen na malém grafu, jehož základní vlastnosti jsou prozkoumány. Klíˇcová slova: teorie her, evoluˇcní dynamika, evoluˇcní hry na grafech, replikátorová dynamika, matematická analýza, diferenciální rovnice
Abstract The aim of this thesis is to give an introduction to the basic principles of evolutionary dynamics and evolutionary games on graphs especially in connection with evolution of cooperation. The main focus will be then directed to a new model generalizing the replicator dynamics. It describes evolution of cooperation for populations connected in one graph. Furthermore, both the model itself and its dynamical characteristics are analysed. Finally, the new model is tested on a small graph whose basic characteristics are investigated. Keywords: game theory, evolutionary dynamics, evolutionary games on graphs, replicator dynamics, mathematical analysis, differential equations
Obsah 1
Úvod
2
2
Základy z teorie her 2.1 Úvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 3 3
3
Evoluˇcní dynamika - vývoj spolupráce 3.1 Úvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Evoluˇcní hry - základní vlastnosti . . . . . . . . . . . . . . . . . . . . . . . 3.3 Koncepty a modely pro zahrnutí vlivu cˇ asu . . . . . . . . . . . . . . . . .
8 8 8 11
4
Evoluˇcní hry na grafech 4.1 Úvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Základní princip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Užitky a zvolení nových strategií . . . . . . . . . . . . . . . . . . . . . . .
13 13 13 14
5
Nový model dynamiky spolupráce v grafech 5.1 Úvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Úplné "nekoneˇcnˇe velké" grafy a aproximace replikátorovými rovnicemi 5.2.1 Populace spojené v grafu - potˇreba nového modelu . . . . . . . . 5.3 Populace spojené v grafu - nový model spolupráce . . . . . . . . . . . . . 5.3.1 Užitek jedné populace . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.2 Prumˇ ˚ erný užitek v okolí populace . . . . . . . . . . . . . . . . . . 5.3.3 Zbývající cˇ leny v modelu . . . . . . . . . . . . . . . . . . . . . . . 5.4 Analytické urˇcení stabilního rˇ ešení . . . . . . . . . . . . . . . . . . . . . . 5.4.1 Úprava funkcí pro dané stacionární rˇ ešení . . . . . . . . . . . . . 5.4.2 Urˇcení Jacobiho matice pro dané stacionární rˇ ešení . . . . . . . . 5.5 Hledání stabilních rˇ ešení pro jednoduchý graf . . . . . . . . . . . . . . .
17 17 17 19 20 21 23 24 25 26 27 28
Závˇer
32
6
Kapitola 1
Úvod Pojem "hra" je ve svˇetˇe široce známý od nejmladších, až po nejstarší obyvatele této planety. Hrát si muže ˚ úplnˇe každý a s každým, avšak pˇredmˇety her mohou být zcela odlišné - muže ˚ jít o spoleˇcenskou hru mezi dvˇema dˇetmi stejnˇe, jako o lva, který nahání svou koˇrist. Na (témˇerˇ ) všechny takové situace dokáže oblast teorie her nabídnout model, ze kterého se dá odvodit nˇejaký budoucí vývoj, a to ne jen pro dvˇe malé dˇeti, ale tˇreba i pro celé populace. V rámci této práce právˇe do této oblasti nahlédneme. Nejdˇrív si pˇredstavíme nˇekolik základních pojmu˚ z teorie her vˇcetnˇe jednoho ze základních konceptu˚ této matematické disciplíny - Nashovy rovnováhy. Jako souˇcást druhé kapitoly budou nastínˇeny cˇ tyˇri klasické kooperaˇcní hry, které ještˇe využijeme pozdˇeji v této práci. Poté totiž nahlédneme do problematiky evoluˇcních dynamik. Teorie her dokáže, jak již bylo naznaˇceno, modelovat vývoj v cˇ ase pro nejruznˇ ˚ ejší situace, což je jedním z duvod ˚ u, ˚ proˇc nachází široké využití v biologii nebo tˇreba ekonomii. My se pak budeme zvlášt’ soustˇredit na vývoj spolupráce a pˇredstavíme si nˇekteré koncepty, jak spolupráci "v budoucnu" sledovat. Následuje pˇresun k pomˇernˇe nové tematice z této oblasti - evoluˇcní hry na grafech. Ukážeme si nˇekteré zvláštnosti a základní principy, jak se evoluce na grafech sleduje. Pˇredposlední a zárovenˇ nejduležitˇ ˚ ejší kapitola je vˇenovaná novému modelu spolupráce v grafech. Pokusíme se popsat chování populací, které jsou spojené v grafu, popíšeme si základní vlastnosti modelu a budeme hledat takové podmínky, aby všechny populace spolupracovaly nebo naopak. Na závˇer model "vyzkoušíme" na jednoduchém grafu.
Veškeré výpoˇcty cˇ i simulace, které se objeví v této práci, byly naprogramovány v softwaru MATLAB. Jejich zdrojové kódy se nachází na pˇriloženém CD.
2
Kapitola 2
Základy z teorie her 2.1
Úvod
Obecnˇe známé jsou hry jako "Vˇeznovo ˇ dilema", cˇ i koordinaˇcní hry jako "Válka pohlaví". V rámci této práce se i krátce podíváme na to, jak tyto takzvané statické hry vyˇrešit, ale teorie her sahá svým polem pusobnosti ˚ mnohem dál. Pozdˇeji uvidíme, že za urˇcitých podmínek (napˇríklad pˇri konstelaci užitku, ˚ jakou mužeme ˚ najít u zmínˇených her), existují nástroje, jak popsat vývoj celých populací z hlediska evoluce - tato problematika sahá do takzvané evoluˇcní dynamiky, o kterou se zajímají ve velkém také biologové, jako se píše napˇríklad v této literatuˇre [1]. Nicménˇe v této kapitole si uvedeme nˇekolik základních pojmu, ˚ které budeme potˇrebovat a používat v dalších kapitolách.
2.2
Základní pojmy
Definujme si nejprve pojem, který dává celé této disciplínˇe matematiky své jméno - hra. Definice 2.2.1 (hra). Model stˇretnutí nˇekolika stran, které na sebe navzájem svými rozhodnutími pusobí, ˚ se nazývá hra (viz [1]). Poznámka 2.2.1. Ve hˇre úˇcastnˇené strany se nazývají hráˇci. Obecnˇe platí, že poˇcet hráˇcu˚ není omezen, ba naopak. Pozdˇeji uvidíme, že budeme uvažovat i "nekoneˇcnˇe velké" populace. Definice 2.2.2 (strategie, cˇ istá strategie). Rozhodnutí, která mohou hráˇci uˇcinit, se jmenují strategie. Pokud volba není urˇcena pravdˇepodobností, tak mluvíme o cˇ isté strategii (viz [8]) Poznámka 2.2.2. Mimo cˇ isté existují i takzvané smíšené strategie, které udávají, s jakou pravdˇepodobností si hráˇc urˇcitou cˇ istou strategii zvolí (viz [1], [8]). Pokud nebude stanoveno jinak, tak budeme uvažovat pouze cˇ isté strategie. 3
Pˇríklad 2.2.1. Ve hˇre "Vˇeznovo ˇ dilema" si mohou hráˇci (vˇezni) vybírat ze dvou cˇ istých strategií: "Pˇriznat se"a "Zapírat". Hra "Kámen, nužky, ˚ papír" má právˇe 3 strategie. Poznámka 2.2.3. Stejnˇe jako poˇcet hráˇcu˚ nemá omezení, tak totéž platí pro poˇcet strategií. U velkého poˇctu (ˇcistých) strategií v literatuˇre objevíme i princip aproximace spojitou množinou strategií (viz [8]). Pˇreformulujeme-li znˇení Definice 2.2.1, tak se hráˇci navzájem ovlivnují ˇ volbou jejich strategie. Z našeho pohledu je zde duležité ˚ nˇejakým zpusobem ˚ cˇ íselnˇe vyjádˇrit, jestli je pro hráˇce volba urˇcité strategie výhodná cˇ i nikoli, a právˇe za tímto úˇcelem se v teorii her zavádí pojem užitek. Definici pojmu užitek, která stojí v souvislosti s pojmem optimalizace, mužeme ˚ nalézt napˇríklad ve zdroji [8]. Pro naše úˇcely nahradíme v definici autora množinu akcí množinou strategií. Definice 2.2.3 (užitek). Užitek je funkcí u : S −→ RN , kde S je množinou všech strategií a RN budou užitky všech hráˇcu. ˚ Neznamená to nic jiného, než že pro každou volbu strategie dostaneme cˇ íselné vyjádˇrení výše užitku, a to nejen pro jednoho, ale rovnou pro všechny hráˇce. Zohlednujeme ˇ tím to, co nám rˇ íká Definice 2.2.1, tedy že volba strategie jednoho hráˇce má vliv na ostatní. Tudíž i pro nˇe dostaneme pˇri zohlednˇení jejich volby strategie odpovídající užitek. Jak ale takové stˇretnutí hráˇcu˚ modelovat, cˇ i znázornit? I zde existuje více možností, které i závisí na konkrétních podmínkách daného stˇretu. Definice 2.2.4 (statická hra). Hra, ve které každý hráˇc udˇelá jedno rozhodnutí, které navíc udˇelá bez vˇedomosti o tom, jak si zvolili ostatní hráˇci, nazveme statickou hrou (viz [8]). Poznámka 2.2.4. Ve statických hrách udˇelají hráˇci rozhodnutí "najednou", to znamená hra nezávisí na cˇ ase. Opakem statické hry, je hra dynamická, kde hráˇci rozhodují po sobˇe a tedy ví, jakou strategii zvolili ostatní hráˇci (viz [8]). Abychom mˇeli jasnˇe urˇcenou statickou hru, musíme znát tˇri aspektech: (i) pˇresný poˇcet hráˇcu˚ i, (ii) pevnˇe danou množinu strategií S (viz 2.2.2), (iii) užitkovou funkci u (viz 2.2.3). Uvedeme si nˇekolik pˇríkladu˚ statických her, které se v této práci ještˇe nˇekolikrát objeví. Pˇríklad 2.2.2. Zavedeme si další hru: "Lov jelena". V této hˇre dochází ke "stˇretu" dvou myslivcu, ˚ kteˇrí vyrazili na lov. Každý z nich má dvˇe volby: bud’ lovit jelena nebo se spokojit s menší koˇristí - se zajícem. Jelena jsou schopni ulovit jen v pˇrípadˇe, kde ho loví oba najednou, zatímco zajíce dokáže ulovit každý myslivec sám. Myslivci o sobˇe ví, ale netuší, pro kterou koˇrist se rozhodne ten druhý. Máme tedy pˇrípad klasické statické hry o dvou hráˇcích a dvou strategiích. Ponˇevadž strategie jsou stejné, muže ˚ z hlediska jejich kombinace dojít ke 3 situacím: 4
• oba se rozhodnou pro jelena - v takovém pˇrípadˇe jsou schopni ho ulovit a získají oba maximální užitek (10) • jeden z nich se rozhodne pro jelena a druhý pro zajíce - myslivec lovící jelena vyjde "naprázdno" (0), druhý je odmˇenˇen za zajíce jen nepatrnˇe vˇetším užitkem (1) • oba se rozhodnou pro zajíce - oba jsou schopni zajíce ulovit a mají stejný a stejnˇe malý užitek (1) Všechny tyto podmínky lze zapsat maticovˇe:
jelen zajíc
jelen 10;10 1;0
zajíc 0;1 1;1
Maticovému zápisu je tˇreba rozumˇet takto: v prvním sloupci zleva stojí strategie prvního, takzvaného rˇádkového, hráˇce - v prvním rˇ ádku shora strategie druhého, takzvaného sloupcového, hráˇce. Zbylá cˇ ást matice nám pak ukazuje pro danou kombinaci strategií užitky obou hráˇcu˚ - nejprve užitek rˇ ádkového, pak užitek sloupcového hráˇce. Pˇríklad 2.2.3. Podobnˇe, jako pro hru "Lov jelena", si zavedeme matice užitku˚ pro již zmínˇené "Vˇeznovo ˇ dilema": pˇriznat se zapírat
pˇriznat se -10;-10 -20;0
zapírat 0;-20 -1;-1
Záporné užitky si zde mužeme ˚ pˇredstavit jako poˇcet let, které si daný hráˇc (podezˇrelý) odsedí ve vˇezení. Zdánlivé jasnˇe z hlediska podezˇrelých "vítˇezí" kombinace (zapírat, zapírat), ale pomoci metod rˇ ešení, které si krátce uvedeme pozdˇeji, ukážeme, že pokud by hráˇci volili racionálnˇe, tak "správné rˇ ešení" dopadne pˇresnˇe opaˇcnˇe, než bychom asi oˇcekávali. Jedná se o jeden z nejznámˇejších pˇríkladu˚ z oblasti teorie her. Pˇríklad 2.2.4. "Jestˇrábi a holubice":
jestˇráb holubice
jestˇráb -5;-5 0;10
holubice 10;0 5;5
I tato hra je známým pˇríkladem a zajímají se o ni pˇredevším biologové. Zkoumá se totiž chování agresivních (jestˇrábi) a pasivních (holubice) jedincu˚ v jedné populaci s tím, jestli muže ˚ dojít k jejich soužití, cˇ i nikoli. Skuteˇcnˇe struktura užitku˚ této hry ukazuje, že jedinci budou mít "optimální" užitek, když jen cˇ ást populace bude agresivní a druhá cˇ ást pasivní (viz [1]). 5
Pˇríklad 2.2.5. "Plná spolupráce"- tato hra se nejˇcastˇeji objevuje v souvislosti s nejvyšším stupnˇem spolupráce (k tomu více pozdˇeji). Pˇri jakékoli poˇcáteˇcní volbˇe strategií vede struktura užitku˚ (opˇet pˇri racionálním chování hráˇcu) ˚ k tomu, že oba budou chtít spolupracovat.
spolupracovat nespolupracovat
spolupracovat 10;10 -5;5
nespolupracovat 5;-5 -10;-10
Definice 2.2.5 (Symetrické hry). Pokud mají oba hráˇci stejné strategie a pro kombinace tˇechto strategií stejné užitky, tak mužeme ˚ matici užitku˚ zjednodušit. Matice ve své puvodní ˚ podobˇe bude vypadat takto:
A B
A a; a c; b
B b; c d; d
kde S = {A,B} a a, b, c, d jsou jednotlivé užitky. V zjednodušeném tvaru pak vypadá takto:
A B
A a c
B b d
Hry, které mají dané vlastnosti, budeme nazývat symetrické (viz [1]). Nás samozˇrejmˇe bude zajímat, jak tyto hry rˇ ešit, to znamená jaká je z matematického pohledu optimální volba jednotlivých hráˇcu. ˚ Existují v tomto smˇeru ruzné ˚ koncepty, které se liší pˇredevším odlišným významem pojmu "optimální". My se podíváme na ten asi nejznámˇejší z nich. Definice 2.2.6 (Nashova rovnováha). Kombinaci strategií budeme považovat za Nashovu rovnováhu, pokud hráˇci zmˇenou vlastní strategie nemužou ˚ zvýšit vlastní užitek (viz [6]). Poznámka 2.2.5. V pˇrípadˇe, že Nashovu rovnováhu budou tvoˇrit pouze cˇ isté strategie, tak hovoˇríme o cˇ isté Nashovˇe rovnováze.
6
Poznámka 2.2.6. Pro pˇrípad dvou hráˇcu˚ s množinami strategií S1 a S2 , znamená tato definice, že pokud platí následující: u(s1∗ , s2∗ ) ≥ u(s1 , s2∗ ), ∀s1 ∈ S1 a zárovenˇ u(s1∗ , s2∗ ) ≥ u(s1∗ , s2 ), ∀s2 ∈ S2 tak kombinace strategií (s1∗ , s2∗ ) je cˇ istou Nashovou rovnováhou. Vycházíme zde z podobného vyjádˇrení pro smíšené strategie (viz [8]). Podmínky uvedené v pˇredchozí poznámce nám rovnou dávají pˇredpis pro zpusob ˚ rˇ ešení tˇechto her - optimální kombinace strategií hráˇcu˚ budeme hledat pomocí takzvané podtrhávací metody. Její princip si osvˇetlíme na následujícím pˇríkladu. Pˇríklad 2.2.6. Uvažujme znovu situaci z Pˇríkladu 2.2.3. Které strategie budou volit racionálnˇe se rozhodující hráˇci? Definice 2.2.6 a speciálnˇe pro tento pˇrípad pak Poznámka 2.2.6 nám dávají jasný návod. Znamená to, že pro pevnˇe zvolenou strategii druhého hráˇce budeme pro prvního hráˇce z jeho strategií hledat nejvyšší užitek, který podtrhneme (proto se tato metoda nazývá podtrhávací). To samé provedeme pro ostatní strategie druhého hráˇce, cˇ ímž získáme optimální "reakce" prvního na jakoukoli strategii druhého hráˇce. Celý tento postup opakujeme i pro druhého hráˇce. V našem pˇríkladu podtrhneme následovnˇe: pˇriznat se zapírat
pˇriznat se -10;-10 -20;0
zapírat 0;-20 -1;-1
Z hlediska obecného blaha se zdá být nejlepší kombinace (zapírat, zapírat). Oba ale mají možnost si zmˇenou strategie pˇrilepšit a proto se radˇeji pˇriznají, což vede ke kombinaci (pˇriznat se, pˇriznat se). V této konstelaci si však už nikdo vlastním rozhodnutím pˇrilepšit nemuže ˚ a jedná se tedy o cˇ istou Nashovu rovnováhu. Poznámka 2.2.7. Samozˇrejmˇe existují hry, které mají vˇetší poˇcet cˇ istých rovnovah (napˇríklad pokud bychom Pˇríklady 2.2.4 a 2.2.2 vyˇrešili podtrhávací metodou) stejnˇe, jako existují hry, kde nenajdeme ani jednu cˇ istou Nashovu rovnováhu. Tušíme, že když neexistuje cˇ istá rovnováha, tak ta naše "optimální reakce" bude ležet nˇekde "mezi" cˇ istými strategiemi - dostáváme se opˇet ke smíšeným rovnováhám a tím i k jedné z centrálních vˇet teorie her. Vˇeta 2.2.1 (Existence Nashovy rovnováhy). Každá (statická) hra s koneˇcným poˇctem hráˇcu˚ disponujícím koneˇcným poˇctem strategií má minimálnˇe jednu Nashovu rovnováhu. Ta muže ˚ být cˇ istá, ale i smíšená (viz [8]). Poznámka 2.2.8. Stejnˇe jako pro hledání cˇ istých rovnovah existuje i pro hledání rovnovah smíšených koncept rˇ ešení, který se nazývá funkce nejlepší reakce (viz [1]).
7
Kapitola 3
Evoluˇcní dynamika - vývoj spolupráce 3.1
Úvod
V pˇredchozí cˇ ásti jsme si zavedli základní pojmy a v závˇeru i Nashovu rovnováhu, která je konceptem optimální volby pro jednorázovou situaci - hráˇci se potkají a podle užitku˚ se rozhodnou. Pˇrípadný "další vývoj" se neuvažuje. V rámci této práce ale právˇe toto udˇeláme. Co se stane, když danou hru bude hrát daleko víc hráˇcu, ˚ než jen dva (tˇreba nekoneˇcnˇe mnoho)? Jaký nastane vývoj, pokud v této skupinˇe (budeme ji nazývat populací) se situace bude opakovat? Kam spˇeje populace za urˇcitých okolností (to znamená pˇri urˇcité konstelaci užitku) ˚ a které strategie mají z hlediska evoluce nejvˇetší šanci pˇrežít? Pˇresnˇe touto problematikou se zabývá evoluˇcní teorie her a nás bude zajímat pˇredevším vývoj spolupráce a urˇcitý typ her - evoluˇcní hry o spolupráci.
3.2
Evoluˇcní hry - základní vlastnosti
Prukopníkem ˚ myšlenky evoluce byl zcela jistˇe Charles Darwin a jeho myšlenka o "zdatnosti", která urˇcuje další vývoj jedince - cˇ ím vyšší zdatnost, tím vyšší je jeho šance se v prubˇ ˚ ehu cˇ asu prosadit [1]. Možná i proto se v teorii her mluví cˇ asto o zdatnosti místo o užitku, když se pohybujeme v oblasti evoluˇcních her. Nás ale zajímá pˇredevším vývoj spolupráce, a tak si uvedeme následující pojem. Definice 3.2.1 (Evoluˇcní hra o spolupráci). Symetrická statická hra, kde množina strategií S = {spolupracovat(S), nespolupracovat( N )}, kterou hrají cˇ leny populace (ˇci populací) a na základˇe které se rozhoduje o dalším vývoji v cˇ ase, nazýváme evoluˇcní hrou o spolupráci. Jak ale bude konkrétnˇe daná statická hra vypadat?
8
Základní podoba takové hry vypadá následovnˇe: kde
S N
S a c
N b d
a - odmˇena pro oba hráˇce, když spolupracují (v literatuˇre s objevuje také r jako "reward"), b - odmˇena pro rˇ ádkového hráˇce za to, že spolupracuje, i když jeho protˇejšek tak nekoná (objevuje se také s jako "sucker"), c - užitek rˇ ádkového hráˇce v pˇrípadˇe, že neodolá "pokušení" nespolupracovat (objevuje se také t jako "temptation"), d - trest pro oba hráˇce za to, že nespolupracují (objevuje se také p jako "punishment"). Poznámka 3.2.1. Na užitky klademe urˇcité požadavky (viz [3]): (i) a > d - pro hráˇce je lepší, když oba spolupracují, než když nespolupracují (ii) c > b - v pˇrípadˇe, že jen jeden z hráˇcu˚ spolupracuje, tak je lepší nespolupracovat (iii) a > b ∧ c > d - nehledˇe na vlastní volbu je vždy lepší, když druhý hráˇc spolupracuje Z toho plyne následující duležitý ˚ vztah: min{ a, c} > max {b, d}
(3.2.1)
Podíváme-li se na Pˇríklady 2.2.2, 2.2.3, 2.2.4, 2.2.5, tak vidíme, že struktura užitku splnuje ˇ vztah (3.2.1). Samozˇrejmˇe existuje mnoho variací tˇechto her a užitky tedy nemusí být stejné, jako jsme zvolili v této práci. Duležité ˚ je však, aby zmˇenou užitku˚ nedošlo ke zmˇenˇe Nashových rovnovah - pomˇery užitku˚ tedy musí zustat ˚ stejné. Vše podstatné k tˇemto 4 hrám mužeme ˚ shrnout do následující tabulky (viz [3]). pomˇery užitku˚ c>a>d>b a>c>d>b c>a>b>d a>c>b>d
název hry vˇeznovo ˇ dilema lov jelena jestˇrábi a holubice plná spolupráce
zkratka VD LJ JH PS
Nashovy rovnováhy (N;N) (N;N) (S;S) + smíšená (N;S) (S;N) + smíšená (S;S)
Tabulka 3.1: 4 hry o spolupráci - základní vlastnosti Jen na kombinaci strategií, které tvoˇrí Nashovu rovnováhu, vidíme, že od VD smˇerem k PS se postupnˇe zvyšuje stupenˇ spolupráce. I na základˇe této skuteˇcnosti budeme tyto hry dále zkoumat v situaci, kdy bude "propojeno" více populací. Pro nás v tomto ohledu velice cenné je to, že mužeme ˚ bez újmy na obecnosti zvolit a = 1; d = 0 (pro odvození této myšlenky viz [3]). Hodnˇe se nám tak zjednoduší oblast 9
Obrázek 3.1: Znázornˇení pˇrípustných parametru˚ b a c pro hry VD, LJ, JH, PS, pokud zvolíme a = 1; d = 0 parametru, ˚ kterou budeme pozdˇeji zkoumat - pro naše 4 hry je mužeme ˚ znázornit tak, jak to vidíme na Obrázku 3.1. V rámci této práce budeme pozdˇeji zkoumat pro takto "vhodnˇe" zvolené parametry chování cˇ lenu˚ populace. Jde pˇredevším o to, jakou tendenci bude populace mít, to znamená, jestli se bude posouvat spíše ke spolupráci nebo naopak. Na Obrázku 3.2 vidíme ještˇe tˇretí možnost, kde se populace muže ˚ ustálit. Mimo plnou a žádnou spolupráci mužeme ˚ narazit na takzvanou koexistenci, to znamená, že v populaci "žijí" najednou (v našem pˇrípadˇe) spolupracující a nespolupracující. Stane se tak u her o spolupráci se smíšenou Nashovou rovnováhou (viz Tabulka 3.1).
Obrázek 3.2: Hodnoty, na kterých se populace muže ˚ ustálit vˇcetnˇe koexistence
10
Jak ale zjistit, na které strategii se populace ustálí? Tuto otázku rˇ eší rˇ ada konceptu˚ a nˇekolik z nich si pˇredstavíme v následující cˇ ásti.
3.3
Koncepty a modely pro zahrnutí vlivu cˇ asu
V tuto chvíli je tˇreba od sebe odlišit, cˇ eho pˇresnˇe chceme dosáhnout a jaké nástroje k tomu použijeme. My si zde pˇredstavíme 3 možnosti, pˇriˇcemž první dvˇe z nich si naznaˇcíme, zatímco té tˇretí se budeme vˇenovat pozdˇeji podrobnˇe. Pˇredstavíme si následující: (i) Hry s opakováním, (ii) Evoluˇcnˇe stabilní strategie, (iii) Modelování dynamiky populace pomoci diferenciálních rovnic. U her s opakováním platí jednoduchá myšlenka: hráˇci mají pˇred sebou urˇcitou situaci v podobˇe statické hry (napˇr. konstelaci VD). Jak název napovídá, hra se bude opakovat, a my musíme poˇcítat s nejistotou urˇcenou parametrem δ ∈ h0; 1i, který si mužeme ˚ pˇredstavit jako trpˇelivost hráˇcu. ˚ Bude-li δ "vysoké", tak bude hráˇc trpˇelivý a za cenu nižšího užitku bude cˇ ekat, než další hráˇc(i) své rozhodnutí, at’ už z jakéhokoliv duvodu ˚ zmˇení, a on si tím pˇrilepší. Muže ˚ se tak stát, že kombinace strategií, která není Nashovou rovnováhou v "normální"statické hˇre, se stane rovnováhou za podmínek té samé hry s opakováním (více viz [8]). Celá tato myšlenka je pomˇernˇe jednoduchá, ale vadit nám muže ˚ "nejistota" v podobˇe δ - budeme-li chtít modelovat vývoj populace, která se rozhoduje cˇ istˇe podle užitku, ˚ musíme volit jinou možnost. Tou muže ˚ napˇríklad být ta druhá jmenovaná, která také patˇrí k tˇem nejznámˇejším - evoluˇcnˇe stabilní strategie (ESS). Definice 3.3.1. Uvažujme strategii s∗ ∈ S. Tato strategie bude evoluˇcnˇe stabilní, pokud ∀s ∈ S \ {s∗ } bude splnˇena jedna z následujících podmínek (viz [6]): u(s∗ , s∗ ) ≥ u(s, s∗ ) NEBO u(s∗ , s∗ ) = u(s, s∗ ) ∧ u(s∗ , s) > u(s, s) Poznámka 3.3.1. Definici ESS dokážeme vyjádˇrit slovy pˇribližnˇe takto: strategie bude evoluˇcnˇe stabilní, pokud se jedná bud’ o ostrou Nashovu rovnováhu nebo pokud následování jiné strategie s je pro nás nevýhodné - strategie je tím pádem odolná vuˇ ˚ ci invazi. Poznámka 3.3.2. Tato definice platí obecnˇe i pro smíšené strategie. Jsme tedy schopni o urˇcité strategii rˇ íct, jestli je evoluˇcnˇe stabilní, to znamená v dalším prubˇ ˚ ehu cˇ asu už daná populace nebude mít motivaci si zvolit jinou strategii. 11
Budeme-li chtít vidˇet vývoj, než populace dospˇeje (tˇreba) k ESS, tak zas musíme volit jinou možnost. Navíc strategií muže ˚ být víc (budeme-li uvažovat smíšené strategie, tak jich bude napˇríklad nekoneˇcnˇe mnoho) a urˇcit "kandidáta" na ESS nemusí být nutnˇe jednoduché. Ze tˇrí výše jmenovaných možností nám zbyla poslední, kde se do hry dostávají diferenciální rovnice. Avšak právˇe ony nám dovolují modelovat vývoj populace v cˇ ase. Jak ale stanovit podmínky pro to, jak jedinci populace budou cˇ asem své strategie mˇenit? Právˇe to je klíˇcovou otázkou. Dynamik totiž existuje celá rˇ ada a každá z nich muže ˚ mít jiné podmínky pro to, jak se volby strategie v cˇ ase mˇení (viz [4]). V rámci této práce si pozdˇeji ukážeme jednu z nejznámˇejších, takzvanou replikátorovou dynamiku, kterou budeme modifikovat pro použití na grafech.
12
Kapitola 4
Evoluˇcní hry na grafech 4.1
Úvod
V této cˇ ásti se podíváme na evoluci z hlediska teorie her z trochu jiného úhlu pohledu. Doposud jsme uvažovali velkou (spojitˇe aproximovanou) skupinu jedincu, ˚ populaci, kde každý se muže ˚ potkat s každým a všichni se mohou navzájem ovlivnit - v populaci tedy není žádná struktura. Pˇredstavme si nyní situaci, kde má populace jasnˇe danou strukturu, která definuje, které cˇ ásti populace se mohou ovlivnit a které naopak vývojem jiné cˇ ásti jedincu˚ ovlivnˇeny vu˚ bec nejsou. V reálném životˇe se to muže ˚ dít napˇr. na základˇe jazykové bariéry, struktury spoleˇcnosti atd. Stejnˇe, jako jsme schopni zkoumat vývoj nestrukturované populace, tak tu samou problematiku lze pˇrenést i na grafy - strukturované skupiny jedincu. ˚ V této kapitole se tedy seznámíme se základy takzvaných evoluˇcních her na grafech.
4.2
Základní princip
Z pohledu matematiky zde spojíme dvˇe oblasti: • evoluˇcní hry • grafy S první jmenovanou oblastí jsme se seznámili v pˇredcházející kapitole a nás i zde budou pˇrímo zajímat evoluˇcní hry o spolupráci. Pˇripomenme ˇ si tedy definici grafu. Definice 4.2.1 (Graf, vrcholy, hrany). Dvojici G = (V, E), pˇriˇcemž V je množinou koneˇcnou a E ⊂ (V2 ), kde V = {{ x, y} : x, y ∈ V ∧ x 6= y} 2 13
nazýváme neorientovaným grafem. Prvky množiny V budeme nazývat vrcholy nebo také uzly a prvky množiny E hrany (viz [2]). Poznámka 4.2.1. Pro pozdˇejší využití v této práci si zde uvedeme ještˇe další dva pojmy: • graf se nazývá k-regulární, pokud ∀u ∈ V : deg(u) = k, • graf se nazývá úplný, pokud má jako hrany všechny možné neuspoˇrádané dvojice, to znamená, že každý vrchol sousedí s každým. Pˇri |V | = n znaˇcíme takový graf Kn (oba viz [2]). Otázkou je, kde se naše dvˇe jmenované oblasti potkají aneb jak lze evoluˇcní hru spojit s grafem? Pˇripomenme ˇ náš problém, který jsme stanovili v úvodní cˇ ásti této kapitoly: možnost zkoumání vývoje evoluce na strukturované populaci. Je zˇrejmé, že danou strukturu populace znázorníme právˇe grafem - vrcholy tedy budou reprezentovat každého jednotlivého jedince a hrany si mužeme ˚ doslova pˇredstavit jako spojení jedincu. ˚ Právˇe v souvislosti s tímto spojením se objeví i evoluˇcní hry: jsou-li libovolné vrcholy u a v spojeny hranou, tak to znamená, že daní jedinci spolu hrají statickou hru. Užitková matice nám udává užitky jednoho hráˇce pro urˇcitou kombinaci strategií. Jak ale urˇcit užitek jedince, který má víc než jednoho souseda, to znamená dané hry se úˇcastní více hráˇcu˚ než jeden jediný? Na to navazuje další otázka: jak se pak bude každý hráˇc rozhodovat, jakou strategii volit v dalším prubˇ ˚ ehu cˇ asu?
4.3
Užitky a zvolení nových strategií
ˇ Reknˇ eme si tedy nejprve, jak se u grafu˚ urˇcují užitky každého jednotlivého jedince. Uvažujme opˇet naši symetrickou, statickou hru o spolupráci, kde S = {S, N }, v této podobˇe (podrobnˇe viz Definice 3.2.1):
S N
S a c
N b d
Díky užitkové matici víme, jaký užitek budou mít oba hráˇci pro jakoukoli kombinaci strategií. V pˇrípadˇe, že libovolný uzel i bude mít více než jen jednoho souseda, tak bude hrát danou statickou hru s každým svým sousedem. Výsledný užitek bude tedy souˇctem souˇcinu, ˚ který muže ˚ mít následující dvˇe podoby: (i) pokud bude hráˇc na uzlu i hrát strategii S, tak jeho užitek bude: ui = ka + (deg(i ) − k )b, (ii) pokud bude hráˇc na uzlu i hrát strategii N, tak jeho užitek bude: ui = kc + (deg(i ) − k )d, 14
kde k je v obou pˇrípadech poˇcet sousedu˚ hrajících strategii S a a, b, c, d jsou užitky pro urˇcité kombinace strategií (viz užitková matice výše v této cˇ ásti). Urˇcení užitku˚ v praxi si ukážeme na následujícím pˇríkladu. Pˇríklad 4.3.1. Uvažujme užitkovou matici, kterou jsme si pˇripomnˇeli na zaˇcátku této cˇ ásti, a pravidla, která jsme si stanovili pro urˇcení užitku. ˚ Je tedy tˇreba vycházet ze strategie, kterou si daný jedinec ("uzel") volí, a podle toho urˇcit jeho užitek. Jednoduchou kontrolou pak je celkový poˇcet parametru, ˚ který se v celkovém užitku objeví. V rámci znázornˇení si pˇredvedeme tento postup na velmi jednoduchém grafu s pˇeti uzly. Podle toho, jakou strategii daný jedinec hraje, zabarvíme uzel tmavˇe, pokud spolupracuje (to znamená hraje strategii S) nebo necháme bez barvy, pokud nespolupracuje (to znamená hraje strategii N). Užitky jsou pak vepsané do jednotlivých uzlu. ˚
Obrázek 4.1: Graf s 5 uzly - urˇcení užitku˚ Jednorázové urˇcení užitku˚ tedy není pˇríliš velkým problémem, pokud uzly daného grafu nemají pˇríliš vysoký stupen. ˇ Jak ale budeme postupovat dál, to znamená jak urˇcíme, kterou strategii si bude každý jedinec volit? K této problematice najdeme v literatuˇre více konceptu. ˚ My si pˇredstavíme tˇri možné zpusoby, ˚ cˇ i dynamiky, jak urˇcit další vývoj každého jedince, jako je najdeme napˇríklad v literatuˇre [7]: 1. narození-smrt 2. smrt-narození 3. imitace 15
Zjednodušenˇe rˇ eˇceno, každá z tˇechto dynamik má jiné pravidlo pro stanovení nové strategie. První z nich vychází z myšlenky, že v každém cˇ asovém (diskrétním) kroku vybereme jedince, který se bude "rozmnožovat". Tato volba probˇehne v závislosti na užitku (zdatnosti) jedincu˚ a nový (narozený) jedinec nahradí náhodnˇe vybraného souseda. Ve své podstatˇe opaˇcnˇe vypadá i dynamika "smrt-narození", kde nejdˇríve je vybrán (opˇet náhodnˇe) jedinec, který je nahrazen novým, jehož strategie se urˇcí podle užitku˚ sousedu. ˚ V "imitaci" pak je vybrán náhodný jedinec, který bude novˇe volit svoji strategii. Ta se urˇcuje podle sousedu˚ dle velice jednoduchého pravidla: má-li jeden ze sousedu˚ vyšší užitek, než zvolený jedinec, tak "imituje" jeho volbu strategie. V opaˇcném pˇrípadˇe svou volbu mˇenit nebude. Vidíme, že všechna pravidla, jak stojí v [7], zahrnují "náhodný výbˇer". Již v pˇredchozí kapitole jsme ale vyjádˇrili cíl modelovat evoluˇcní vývoj cˇ istˇe podle užitku˚ bez vlivu pravdˇepodobností. Za tímto úˇcelem dokážeme upravit princip "imitace", když nebudeme volit souseda náhodnˇe, ale dané pravidlo aplikujeme na všechny jedince. Tato myšlenka se využívá v evoluˇcních hrách na grafech cˇ asto (najdeme ji tˇreba v zdroji [6]). Z této podoby imitaˇcní dynamiky budeme v této práci dále vycházet a pravidlem pro volbu nové strategie tedy bude, že u každého jedince budeme porovnávat jeho užitek s užitky jeho sousedu˚ - daný jedinec pak imituje tu strategii, která v tomto okolí pˇrináší nejvyšší užitek, at’ už jde o jeho vlastní nebo o jednu ze zkoumaného okolí sousedu. ˚
16
Kapitola 5
Nový model dynamiky spolupráce v grafech 5.1
Úvod
V pˇredchozích kapitolách jsme se podívali na základy evoluˇcní dynamiky a pˇredstavili jsme si koncepty, které nám mohou pomoci urˇcit vývoj jedné populace v cˇ ase. Pozdˇeji jsme zkoumali evoluci pro pˇrípad strukturované populace. Nyní se pokusíme spojit obˇe tyto problematiky do nového modelu - budeme chtít totiž zkoumat situace, kde v jednom grafu již nebudou jednotliví jedinci, nýbrž celé populace. V rámci této práce se pak podíváme detailnˇe na jednoduchý graf a budeme sledovat, jak se budou vyvíjet volby strategií. Pozdˇeji si rˇ ekneme nˇeco o vlastnostech nového modelu pro jiné grafy. Za tímto úˇcelem si napˇred zavedeme známý model pro jednu populaci, než pozdˇeji pˇrejdeme na náš pˇrípad.
5.2
Úplné "nekoneˇcnˇe velké" grafy a aproximace replikátorovými rovnicemi
Uvažujme pro zaˇcátek populaci, kde každý sousedí s každým. Odpovídalo by to tak struktuˇre úplného grafu. Pro velikost této populace jdoucí do nekoneˇcna mužeme ˚ využít jeden z nejznámˇejších modelu˚ v souvislosti evoluˇcních dynamik, takzvanou replikátorovou dynamiku. Tento model má urˇcité vlastnosti (viz níže), které budeme požadovat i po našem modelu, kde spojíme více takovýchto populací do jednoho grafu. Zpˇet ale k replikátorové dynamice. Vychází z již dˇríve zmínˇené teorie zdatnosti a tedy otázky "evoluˇcního vývoje". Podíváme se tedy na samotný model. Definice 5.2.1 (Replikátorová dynamika). Replikátorovou dynamiku definují takzvané replikátorové rovnice - soustava diferenciálních rovnic prvního rˇ ádu následující podoby: x˙i = (u(si , ~x ) − u¯ (~x )) xi , 17
(5.2.1)
kde si - i-tá strategie z množiny všech strategií S = {s1 , s2 , ..., sk } xi - podíl jedincu˚ hrajících i-tou strategii
~x - vyjádˇrení všech typu˚ jedincu˚ v populaci u(si , ~x ) - užitek populace z i-té strategie pˇri zohlednˇení volby ostatních strategií u¯ (~x ) - prumˇ ˚ erný užitek populace Poznámka 5.2.1. Konkrétní odvození popisuje James Webb v této knize [8]. ˇ Ceho vlastnˇe chceme dosáhnout? Mluvili jsme o tom, že bychom chtˇeli modelovat chování populace s postupem cˇ asu. Replikátorová dynamika nám ale navíc napovídá, kdy se vývoj ustálí, to znamená, že nám urˇcí, pro kterou konstelaci podílu˚ xi již nenastane žádný vývoj. Definujme si právˇe v tomto ohledu další duležitý ˚ pojem - pevný bod. Definice 5.2.2 (pevný bod). Konstelaci podílu˚ xi , pro které platí, že x˙i = 0, ∀i, budeme nazývat pevným bodem (viz [8]). Poznámka 5.2.2. Pokud populace dojde do konstelace pevného bodu, tak již nenastane žádný další vývoj. Již dˇríve jsme si stanovili, že budeme sledovat vývoj spolupráce - v cˇ ásti o evoluˇcních hrách a Definici 3.2.1 jsme si rˇ ekli, že námi uvažované hry budou mít právˇe dvˇe strategie - spolupráci a nespolupráci. Budeme-li uvažovat, že jedinci populace mohou vybírat jen ze dvou strategií, tak se nám celý tento model zjednoduší. Poznámka 5.2.3. Uvažujme pro replikátorovou dynamiku evoluˇcní hru a její typickou užitkovou matici v podobˇe
S N
S a c
N b d
Oznaˇcíme-li si podíl spolupracujících v populaci jako x, tak podíl nespolupracující cˇ ásti dokážeme vyjádˇrit jako 1 − x. Tudíž nemusíme sestavovat dvˇe replikátorové rovnice, pokud chceme sledovat pouze vývoj spolupráce, a vystaˇcíme si s jednou. Pˇri zohlednˇení rozdˇelení užitku˚ stanovených v matici výše bude naše jediná rovnice vypadat následovnˇe: x˙ = ( ax + b(1 − x ) − ( ax2 + bx (1 − x ) + cx (1 − x ) + d(1 − x )2 )) x.
(5.2.2)
Po jednoduché úpravˇe získáme následující podobu: x˙ = x (1 − x )( x ( a + d − b − c) + b − d). 18
(5.2.3)
Poznámka 5.2.4. Všimnˇeme si, že z (5.2.3) vyplývá, že pokud mají hráˇci jen dvˇe strategie, mužeme ˚ za pevné body okamžitˇe prohlásit x = 0 a x = 1. Na konkrétním rozdˇelení užitku˚ pak závisí, jestli najdeme i tˇretí pevný bod v podobˇe x=
d−b . a+d−b−c
Jak ale celá dynamika "funguje"? Klíˇcovou roli pro urˇcení budoucího vývoje zde sehrává cˇ ást rovnice (5.2.1), kterou nacházíme v závorce - rozdíl užitku z i-té strategie a prumˇ ˚ erného užitku populace nám dovolí si odvodit duležité ˚ základní vlastnosti tohoto modelu. Nejprve si stanovme "povolené" hodnoty xi . Po modelu chceme, aby nastal "nˇejaký" vývoj a zárovenˇ dosazované hodnoty byly realistické. Podíl populace hrající urˇcitou strategii se tím pádem muže ˚ pohybovat pouze mezi 0 a 1. Otázku, zda volit otevˇrený cˇ i uzavˇrený interval, si zodpovíme pˇri pohledu na rovnici (5.2.1) - pokud bychom volili xi = 0 (pro hru se dvˇema strategiemi i xi = 1 viz (5.2.3)), tak bude x˙i = 0 a máme konstelaci pevného bodu. Proto budeme podíly xi uvažovat v otevˇreném intervalu (0, 1). Pro tyto hodnoty dokážeme odvodit následující: (i) pokud u(si , ~x ) − u¯ (~x ) > 0, to znamená užitek z i-té strategie je vˇetší než prumˇ ˚ erný užitek populace, bude platit též x˙i > 0 a jedincu˚ i-tého typu bude tedy pˇribývat, (ii) pokud u(si , ~x ) − u¯ (~x ) < 0, to znamená užitek z i-té strategie je menší než prumˇ ˚ erný užitek populace, bude platit též x˙i < 0 a jedincu˚ i-tého typu bude tedy ubývat, (iii) pokud u(si , ~x ) − u¯ (~x ) = 0, to znamená užitek z i-té strategie je roven prumˇ ˚ ernému užitku populace, bude platit též x˙i = 0 a jedincu˚ i-tého typu nebude ani ubývat, ani pˇribývat. Pokud toto platí pro všechna i, tak jsme v takovém pˇrípadˇe našli pevný bod.
5.2.1
Populace spojené v grafu - potˇreba nového modelu
Zatímco výpoˇcet užitku z urˇcité strategie a prumˇ ˚ erného užitku je u úplných, co se týká velikosti do nekoneˇcna jdoucích grafu˚ celkem jednoduchou operací, tak už jsme si v pˇredchozí kapitole ukázali, že pro neúplné grafy koneˇcné velikosti se celá vˇec komplikuje. Pro výše uvedené úplné "nekoneˇcnˇe velké" grafy mužeme ˚ celou populaci popsat již uvedenými replikátorovými rovnicemi. Pro grafy neúplné se celá situace ale mˇení - užitek jednoho jedince již nezávisí na celé populaci, ale tˇreba jen na nˇekolika málo dalších jedincích, a pokud graf nebude regulární, tak se sestavení užitku˚ jednotlivých jedincu˚ muže ˚ i výraznˇe lišit. Nyní se pokusíme všechny doposud v této práci uvedené oblasti spojit - budeme sledovat vývoj v situaci, kde spojíme nˇekolik populací do jednoho grafu. Pˇrenesou se nám tak eventuální problémy zmínˇené v pˇredchozím odstavci na náš pˇrípad, jen již nebudeme uvažovat jednotlivé jedince, ale celou populaci. Jak již bylo uvedeno, tak pro populaci v podobˇe "nekoneˇcnˇe velkého" úplného grafu použijeme replikátorové rovnice. Je ale zˇrejmé, že díky jejich spojení se budou populace vzájemnˇe ovlivnovat. ˇ Pro urˇcení užitku populace tedy bude hrát roli i urˇcení užitku˚ v grafu, které jsme si pˇredstavili v pˇredchozí kapitole. 19
Dojde tak k propojení diferenciálních rovnic pro "nekoneˇcnˇe velkou" populaci a "problému" ˚ spojenými s konstrukcí užitku ve hrách na grafech. Pokud stále chceme sledovat vývoj volby urˇcité strategie, tak potˇrebujeme jiný model, než replikátorové rovnice. Musí mít stejné vlastnosti, které byly uvedené v pˇredchozí cˇ ásti, a zárovenˇ musí zohlednit i strukturu, ve které jsou populace spojeny.
5.3
Populace spojené v grafu - nový model spolupráce
V této cˇ ásti se tedy pokusíme o vytvoˇrení nového modelu, který zohlednuje ˇ všechny naše požadavky kladené na vývoj populace pˇri urˇcité konstelaci užitku˚ v okolí. Nejprve si ale nadefinujeme dvˇe okolí, která budeme potˇrebovat pozdˇeji bud’ pˇrímo v této podobˇe nebo v podobném smyslu. První bude množina všech uzlu˚ v, které mají od zvoleného uzlu u vzdálenost 1 a budou tedy jeho sousedi: N1 (u) = {v ∈ V : dist(u, v) = 1}.
(5.3.1)
Druhá množina bude podobná té první s tím, že ted’ bude souˇcástí množiny i samotný uzel u: N≤1 (u) = {v ∈ V : dist(u, v) ≤ 1}. (5.3.2) Poznámka 5.3.1. Nebude-li stanoveno jinak, tak místo výrazu˚ uzel a vrchol budeme používat jednoduše slovo populace. Obrázek 5.1 nám pro pˇríklad grafu v podobˇe cyklu znázornuje, ˇ kterými uzly je (libovolný) uzel i ovlivnˇen, což si objasníme ještˇe pozdˇeji. Zárovenˇ ilustruje pro tento pˇrípad i jednotlivá okolí N≤2 (i ), N≤1 (i ) a N1 (i ). Nyní se dostaneme již k samotnému modelu. Nutno je podotknout, že nejde o "správné" rˇ ešení naší úlohy. Mužeme ˚ to však považovat za koncept, se kterým se pokusíme naše požadavky co nejlépe splnit. Nový model, který splnuje ˇ v pˇredcházející cˇ ásti požadované vlastnosti a který bude sledovat vývoj spolupráce populací v grafu, muže ˚ vypadat takto: x˙i = (ui − u¯i ) xi (1 − xi )( xi − x¯i ),
(5.3.3)
kde i - oznaˇcení uzlu˚ (populací) v grafu (i = 1, 2, 3, ..., |V |), xi - podíl spolupracujících jedincu˚ v i-tém uzlu, ui - užitek populace v i-tém uzlu (viz (5.3.4)), u¯i - prumˇ ˚ er užitku˚ vzhledem k uzlu xi (viz (5.3.8), (5.3.9)), x¯i - prumˇ ˚ er z podílu˚ spolupracujících v okolí N≤1 (i ). Platí, že x¯i =
20
∑ j∈ N≤1 (i) x j . | N≤1 (i )|
Obrázek 5.1: Znázornˇení okolí uzlu i, které má vliv na jeho další vývoj Poznámka 5.3.2. Duležité ˚ je si zde povšimnout jiného znaˇcení oproti replikátorové dynamice (viz (5.2.1)) - významným rozdílem je, že i zde již nepˇredstavuje i-tou strategii, ale i-tý uzel, ui užitek populace na tomto uzlu a xi podíl spolupracujících v i-tém uzlu. Z urˇcitého úhlu pohledu v našem modelu stále poznáme replikátorovou rovnici. Abychom si lépe znázornili rozdíl, mužeme ˚ ui a u¯i rozepsat - právˇe zde dochází k zásadnímu rozdílu mezi naším modelem a replikátorovou dynamikou.
5.3.1
Užitek jedné populace
Je duležité ˚ si uvˇedomit, že cˇ len ui zahrnuje i okolí daného populace. Nastoluje se zásadní otázka, jak napˇríklad pˇresnˇe nastavit vliv sousedu. ˚ I pro tuto problematiku existují koncepty z evoluˇcních her na grafech, které využijeme i pro náš pˇrípad. Vˇenujme se tedy užitku ui . Na základˇe výše uvedeného bude funkcí, která má tuto základní podobu: ui = f ( xi , ~x j ), (5.3.4) kde xi je podíl spolupracujících v i-tém uzlu,
~x j jsou všechna x j pro všechna j ∈ N1 (i ). 21
Tento zpusob ˚ zápisu právˇe má naznaˇcit, že na užitek populace na i-tém uzlu mají vliv všichni její sousedé, podobnˇe jako tomu je u her na grafech. Avšak zde je užitek jedné populace daleko komplexnˇejší. Uvažujme napˇríklad situaci, kde jedna populace bude pˇrevážnˇe spolupracující. Její sousedé však nespolupracují, a tak musí být užitek ze spolupráce logicky menší. Výpoˇcet funkce f ( xi , ~x j ) v našem pˇrípadˇe probˇehne na základˇe souˇcinu jejích argumentu. ˚ Pˇresnou podobu si ihned upˇresníme. Do funkce f ( xi , ~x j ) nyní zahrneme i klasické parametry z evoluˇcních her o spolupráci (viz Definice 3.2.1). Vyjádˇrení z (5.3.4) pak mužeme ˚ rozvinout do podoby ∑ j∈ N1 (i) x j ∑ j∈ N1 (i) (1 − x j ) + bxi deg(i ) deg(i ) ∑ j∈ N1 (i) x j ∑ j∈ N1 (i) (1 − x j ) + c (1 − x i ) + d (1 − x i ) . deg(i ) deg(i )
f ( xi , ~x j ) = axi
(5.3.5)
Poznámka 5.3.3. Výpoˇcet užitku dle rovnice (5.3.5) je obecný postup. V kapitole o evoluˇcní dynamice jsme si ukázali, že bez újmy na obecnosti mužeme ˚ položit a = 1; d = 0. Výpoˇcet se nám tak zjednoduší na podobu: f ( xi , ~x j ) = xi
∑ j∈ N1 (i) x j ∑ j∈ N1 (i) (1 − x j ) ∑ j∈ N1 (i) x j + bxi + c (1 − x i ) . deg(i ) deg(i ) deg(i )
(5.3.6)
V krátkosti si pˇredved’me konstrukci užitku˚ na pˇríkladu. Pˇríklad 5.3.1. Uvažujme graf, kde jsou populace spojené v cyklu. Chceme urˇcit užitek pro populaci (ˇci uzel) i, jehož dva sousedy oznaˇcíme i − 1 a i + 1 (viz Obrázek 5.1). Užitek populace i pak bude mít tuto podobu (pˇri zohlednˇení Poznámky 5.3.6): f ( xi , ~x j ) = xi
x + x i +1 1 − x i −1 + 1 − x i +1 x i −1 + x i +1 + bxi + c (1 − x i ) i −1 . 2 2 2
Jak je i z pˇríkladu zˇrejmé, tak podílu˚ x j bude pˇresnˇe tolik, kolik má uzel i sousedu. ˚ O poˇctu populací j, které mají pˇrímý vliv na užitek populace i, mužeme ˚ tedy rˇ íct, že bude pˇresnˇe roven deg(i ) = | N1 (i )|. (5.3.7) Než se dostaneme k další cˇ ásti, kde se budeme vˇenovat více funkci u¯i , tak se dostaneme k jedné obecné problematice v oblasti evoluˇcních her na grafech. Z (5.3.5) vyvodíme, že pˇri urˇcení užitku populace i využíváme prumˇ ˚ er z podílu˚ spolupracujících sousedu. ˚ Je to jeden ze zpusob ˚ u, ˚ jak u evoluˇcních her na grafech se dvˇema strategiemi pˇristupovat k rozdˇelení užitku. ˚ Mimo zde používaný výpoˇcet prumˇ ˚ erem lze využít i zpusob ˚ agregace. V této práci budeme souˇcty x j prumˇ ˚ erovat, to znamená, že souˇcty x j a 1 − x j vydˇelíme deg(i ) (viz 5.3.5). Pro grafy regulární, tedy ty, které tu pˇrevážnˇe budeme uvažovat, je dokonce jedno, který z dvou konceptu˚ použijeme (viz [3]). 22
5.3.2
Prumˇ ˚ erný užitek v okolí populace
V pˇredchozí cˇ ásti jsme si osvˇetlili konstrukci užitku ui a nˇekteré jeho základní vlastnosti. Dále si zavedeme druhou funkci pro prumˇ ˚ erný užitek v okolí populace i, který je v modelu (5.3.3) znaˇcen jako u¯i : u¯i = g( xi , ~x j ), (5.3.8) kde xi je podíl spolupracujících v i-tém uzlu,
~x j jsou všechna x j pro všechna j ∈ N≤2 (i ) \ {i }. Je zˇrejmé, že prumˇ ˚ erný užitek okolí kolem populace i dokážeme urˇcit jako prumˇ ˚ er z užitku˚ všech populací, které se v daném okolí nachází (tedy vˇcetnˇe populace i). Funkci u¯i tak dokážeme vyjádˇrit pro nás lépe uchopitelným zpusobem: ˚ u¯i =
∑ j∈ N≤1 (i) u j deg(i ) + 1
(5.3.9)
Podobnˇe, jako jsme si postupnˇe stanovili dva zápisy ui , tak jsme provedli totéž pro u¯i . Oba zpusoby ˚ vyjádˇrení prumˇ ˚ erného užitku mají svuj ˚ smysl. Srovnáme-li (5.3.4) a (5.3.8), tak zjistíme, že v prumˇ ˚ erném užitku u¯i vstupují do modelu i populace z množiny N2 (i ) - tedy uzly, které mají od uzlu i vzdálenost 2. Jedná se o velice duležitý ˚ poznatek, který ještˇe využijeme pozdˇeji mimo jiné pˇri urˇcení analytického rˇ ešení. Dále jsme si uvedli rovnici (5.3.9). Tento zpusob ˚ vyjádˇrení prumˇ ˚ erného užitku je vhodnˇejší, pokud se zajímáme o výpoˇcet u¯i . Opˇet zde vycházíme ze skuteˇcnosti, že se populace nachází v grafu a tedy na užitku "jednoho uzlu" mají vliv i jeho sousedé. Když tedy chceme urˇcit prumˇ ˚ erný užitek jedné populace u¯i , tak se nejedná o nic jiného, než prumˇ ˚ er z užitku˚ všech populací z množiny N≤1 (i ). Poznámka 5.3.4. Neménˇe duležité ˚ je zde zamezit nedorozumˇení. Proˇc v souvislosti s populací i mluvíme také o populacích z N2 (i )? Odpovˇed’ nám dá rovnice (5.3.9). Z ní vyplývá, že musíme urˇcit také užitky populací j ∈ N1 (i ). Pro libovolné j má u j dle (5.3.4) podobu u j = f ( x j , x~k ), kde x j je podíl spolupracujících v j-tém uzlu, x~k jsou všechna xk pro všechna k ∈ N1 ( j). Právˇe zde vidíme hledaný duvod ˚ - populace z N2 (i ) vstupují do modelu pˇri výpoˇctu užitku sousedu. ˚ 23
Poznámka 5.3.5. Doposud jsme si uvedli užitky, respektive funkce, pro ui a u¯i . Pojd’me si shrnout doposud získané znalosti o nich ve vztahu na množiny N1 (i ) a N2 (i ): ui - vliv na užitek populace i má pouze nejbližší okolí, to znamená pouze populace z množiny N1 (i ) u¯i - opˇet zde vstupují populace z N1 (i ). Právˇe pˇri výpoˇctu jejich užitku se dostaneme i k populacím z množiny N2 (i ) (viz Poznámka 5.3.4). Populace z množiny N1 (i ) tím pádem mají pˇrímý vliv na užitek populace i, zatímco populace z množiny N2 (i ) hrají roli jen pro prumˇ ˚ erný užitek okolí. V rámci replikátorových rovnic jsme vycházeli z toho, že vliv výhodnˇejší strategie se šíˇrí napˇríˇc všemi jedinci hned od poˇcátku, jelikož celá populace je mezi sebou propojena (uvažujeme úplný "nekoneˇcnˇe velký" graf). Jak to dopadne pro náš model? Urˇcitˇe máme pˇredstavu, jak by to mˇelo fungovat: vývoj, který nastane v populaci i, mohou ovlivnit jen její sousedé a teprve pak se "pˇrípadný vliv" muže ˚ rozšíˇrit do celého grafu k ostatním populacím. Pokud užitek populace i bude vˇetší, než prumˇ ˚ erný užitek jejího okolí, tak se okolí bude snažit danou populaci, co se týká volby strategie, napodobit - v principu tedy stejnˇe, jako tomu je u replikátorové dynamiky. Teprve pak se muže ˚ vývoj rozšíˇrit i do zbytku grafu. Pokud naopak bude užitek populace nižší, než prumˇ ˚ erný užitek jejího okolí, tak naopak tato populace bude mít tendenci se pˇrizpusobit, ˚ a právˇe ona bude mˇenit strategii. Tuto imitaci nám zaruˇcí rozdíl mezi užitkem populace i a prumˇ ˚ erným užitkem (okolí populace i). To odpovídá výrazum ˚ u(si , ~x ) − u¯ (~x ) v replikátorové dynamice (viz (5.2.1)) a ui − u¯i v našem modelu (viz (5.3.3)). Tudíž by základní vlastnosti replikátorové dynamiky mˇely být splnˇeny i v našem modelu. Poznámka 5.3.6. Nesmíme zapomenout na rozdíl mezi replikátorovými rovnicemi a našem modelem. Náš model se vˇenuje vývoji spolupráce v populaci, která je spojena s ostatními v grafu. Oproti tomu jde v replikátorové dynamice o vývoj jedincu˚ urˇcitého typu v jedné populaci.
5.3.3
Zbývající cˇ leny v modelu
Zbývající cˇ ást rovnice (5.3.3) naopak zabranuje ˇ tomu, aby se podíl jedincu˚ v populaci na uzlu i dostal mimo interval (0, 1). Sotva xi dosáhne hranice tohoto intervalu, tak na základˇe konstrukce našeho modelu bude x˙i = 0 a xi už své hodnoty nezmˇení. Dojde na situaci, kde je populace složena bud’ jen ze spolupracujících nebo naopak cˇ istˇe z nespolupracujících. Skuteˇcnost, že pak nedochází k žádnému vývoji, si mužeme ˚ pˇredstavit následovnˇe: pokud bude populace na 100 % spolupracovat, tak žádný z jedincu˚ nemá vzor pro imitaci 24
strategie "nespolupracovat". Daná populace nespolupráci prostˇe nezná a pokud nepˇrijde tato informace od sousedících populací, tak bude volit "spolupráci" i nadále. Stejnou vlastnost má i model replikátorových rovnic (5.2.1), cˇ ili i v tomto ohledu je náš model (5.3.3) "svému vzoru" podobný.
5.4
Analytické urˇcení stabilního rˇešení
Model a jeho základní vlastnosti jsme si již popsali. Nás ale bude nejprve zajímat, kde se jednotlivé populace ustálí, to znamená, pro které podíly xi již nenastane žádný další vývoj. Pokud budeme schopni takovéto podíly urˇcit, tak nás bude zajímat, pro jaké parametry b a c (viz Definice 3.2.1 a Poznámka 5.3.6) budou populace mít tendenci k plné spolupráci nebo naopak žádná z populací spolupracovat nebude. Pˇri pohledu na náš model zjistíme, že se jedná o diferenciální rovnici prvního rˇ ádu - pro z toho vyplývající soustavu budeme postupovat následovnˇe (viz [5]): (i) najdeme stacionární rˇ ešení této soustavy - takže takové podíly xi , které rˇ eší x˙i = 0 (ii) pro nalezená rˇ ešení urˇcíme stabilitu podle prvního pˇriblížení. Které podíly xi ale rˇ eší soustavu? Podívejme se ještˇe jednou na model, ze kterého budeme vycházet. x˙i = (ui − u¯i ) xi (1 − xi )( xi − x¯i ). Pravá strana rovnice je jedním velkým souˇcinem - bude nám proto staˇcit, aby jeden z cˇ initelu˚ se rovnal nule. Proberme tedy každého cˇ initele zvlášt’ s tím, že se pokusíme najít rˇ ešení jednotlivých cˇ initelu: ˚ ui − u¯i = 0, pokud ui = u¯i (toho docílit bude ale obzvlášt’ u velkých grafu˚ složité), xi = 0, 1 − xi = 0, pokud xi = 1, xi − x¯i = 0, pokud xi = x¯i . Tento výraz bude splnˇen, pokud xi =
∑ j∈ N≤1 (i) x j . deg(i )
ˇ Rekli jsme si, že chceme sledovat vývoj populací a konkrétnˇe to, jestli budou mít tendenci k plné spolupráci, tedy ~x = (1, 1, 1, ..., 1) nebo k žádné spolupráci, tedy ~x = (0, 0, 0, ..., 0). Vidíme, že obˇe kombinace podílu˚ jsou stacionárním rˇ ešením. Navíc pˇri pohledu na výraz ∑ j∈ N≤1 (i) x j xi = zjistíme, že bude splnˇen právˇe tehdy, když x1 = x2 = x3 = ... = xn , pokud deg(i ) n = |V |. 25
Do této podmínky zahrneme již dˇríve uvedené podíly ~x pro plnou, respektive žádnou spolupráci a získáme stacionární rˇ ešení, jehož stabilitu podle prvního pˇriblížení urˇcíme v dalším kroku. K tomu potˇrebujeme urˇcit Jacobiho matici, což se muže ˚ projevit obzvlášt’ u velkých grafu˚ jako celkem složitá operace. Podívejme se tedy pˇredtím na to, zda pro x1 = x2 = x3 = ... = xi = ... = xn se nám nˇekteré výrazy v našem modelu nezjednoduší.
5.4.1
Úprava funkcí pro dané stacionární rˇešení
Zaˇcneme na obecném užitku jedné populace ui v této podobˇe (viz Poznámka 5.3.6): f ( xi , ~x j ) = xi
∑ j∈ N1 (i) x j ∑ j∈ N1 (i) (1 − x j ) ∑ j∈ N1 (i) x j + bxi + c (1 − x i ) . deg(i ) deg(i ) deg(i )
Po dosazení našeho stacionárního rˇ ešení dostaneme mnohem jednodušší výraz, který bude platit navíc pro všechny populace v grafu. Pokud místo x1 , x2 , x3 , ... budeme psát jen xi , tak mužeme ˚ zapsat naši funkci jako: f ( xi , ~x j ) = f ( xi ) = xi
deg(i ) xi deg(i ) xi deg(i )(1 − xi ) + bxi + c (1 − x i ) , ∀i ∈ V. deg(i ) deg(i ) deg(i )
f ( xi ) = xi2 + xi (1 − xi )(b + c), ∀i ∈ V.
(5.4.1)
Z toho plynou pro nás dva velice duležité ˚ poznatky: (i) užitek populace za daných podmínek nezávisí na sousedících populacích, (ii) tvar užitkové funkce bude pro všechny populace stejný. Postoupíme dál k prumˇ ˚ ernému užitku v okolí populace u¯i ve tvaru (viz (5.3.9)): u¯i = g( xi , ~x j ) =
∑ j∈ N≤1 (i) u j , ∀ j ∈ N≤2 (i ). deg(i ) + 1
Využijeme již získané znalosti (viz (5.4.1)) a opˇet se nám tvar zjednoduší: g( xi , ~x j ) = g( xi ) =
(deg(i ) + 1) f ( xi ) , ∀i ∈ V. deg(i ) + 1
g( xi ) = f ( xi ), ∀i ∈ V. Bude tedy platit, že f ( xi ) − g( xi ) = 0, ∀i ∈ V.
(5.4.2)
Než postoupíme dál, tak se podíváme na prumˇ ˚ er z podílu˚ spolupracujících v okolí x¯i , který logicky taky pˇrejde na jednoduší tvar: x¯i =
(deg(i ) + 1) xi = xi , ∀i ∈ V. deg(i ) + 1
Z toho plyne opˇet, že xi − x¯i = 0, ∀i ∈ V. 26
(5.4.3)
5.4.2
Urˇcení Jacobiho matice pro dané stacionární rˇešení
Pro urˇcení prvku˚ Jacobiho matice využijeme znalosti získané v pˇredchozí cˇ ásti. Podívejme se nejprve na prvky, které se nachází na diagonále - z hlediska výpoˇctu tušíme, že právˇe ony budou ty nejsložitˇejší. Pˇri derivování musíme mít na zˇreteli, že náš model je souˇcinem dvou souˇcinu. ˚ Budeme-li opˇet vycházet z populace i, tak prvek patˇrící k diagonále Jacobiho matice bude mít podobu: ∂ x˙i ∂ f ( xi ) ∂g( xi ) = (( − ) xi + f ( xi ) − g( xi ))(1 − xi )( xi − x¯i )+ ∂xi ∂xi ∂xi deg(i ) ( f ( xi ) − g( xi )) xi ((1 − xi ) − ( xi − x¯i )), ∀i ∈ V deg(i ) + 1
(5.4.4)
Aplikujme vztahy (5.4.2) a (5.4.3) - prvky na diagonále tím pádem budou všechny nulové, jelikož v obou velkých souˇcinech z (5.4.4) je jeden z cˇ initelu˚ nulový. Celé si to znázorníme na následující (zkrácené) rovnici ∂ x˙i ∂ f ( xi ) ∂g( xi ) = (( − ) xi + f ( xi ) − g( xi ))(1 − xi ) ( xi − x¯i ) + ( f ( xi ) − g( xi )) xi ... | {z } | {z } ∂xi ∂xi ∂xi =0
=0
∂ x˙i = 0, ∀i ∈ V ∂xi
(5.4.5)
Pokraˇcujme nyní u populací z množiny N1 (i ). V parciální derivaci budeme cˇ ást xi (1 − xi ) uvažovat jako konstantu. Pro tyto populace bude mít patˇriˇcný prvek v Jacobiho matici následující tvar: ∂ x˙i ∂ f ( xi ) ∂g( xi ) deg(i ) = xi (1 − xi )( − )( xi − x¯i ) + ( f ( xi ) − g( xi )) , ∀ j ∈ N1 (i ), ∀i ∈ V ∂x j ∂x j ∂x j deg(i ) + 1 (5.4.6) Využijeme zde stejné vztahy, jako pˇredtím, a opˇet bude výsledkem, že tyto prvky Jacobiho matice jsou nulové: ∂ x˙i ∂ f ( xi ) ∂g( xi ) deg(i ) = xi (1 − xi )( − ) ( xi − x¯i ) + ( f ( xi ) − g( xi )) {z } deg(i ) + 1 ∂x j ∂x j ∂x j | {z } | =0
=0
∂ x˙i = 0, ∀ j ∈ N1 (i ), ∀i ∈ V ∂x j
(5.4.7)
Následují sousedící populace z množiny N2 (i ). Pro tyto populace bude pˇríslušný prvek v Jacobiho matici mít ještˇe "jednodušší" podobu: ∂ x˙i ∂g( xi ) = xi (1 − xi )( xi − x¯i )(− ), ∀k ∈ N2 (i ), ∀i ∈ V ∂xk ∂xk 27
(5.4.8)
Okamžitˇe vidíme, že i tyto prvky budou nulové - staˇcí nám k tomu vztah (5.4.3): ∂ x˙i ∂g( xi ) = xi (1 − xi ( xi − x¯i )(− ) | {z } ∂xk ∂xk =0
∂ x˙i = 0, ∀k ∈ N2 (i ), ∀i ∈ V ∂xk
(5.4.9)
Jak budou vypadat ostatní prvky Jacobiho matice? Bez toho, abychom si urˇcovali jejich tvar, jako jsme to dˇelali u populací z množiny N≤2 (i ), mužeme ˚ prohlásit, že budou taktéž nulové. Dokazuje to konstrukce celého modelu - již dˇríve jsme si uvedli, že populace, které jsou v grafu vzdálené více, než dvˇe hrany, se v rovnici pro xi neobjeví (viz Poznámka 5.3.5). Výsledkem tedy je, že pro stacionární rˇ ešení x1 = x2 = x3 = ... = xi = ... = xn bude Jacobiho matice nulová, a tedy není možné uˇcinit jednoznaˇcný závˇer o stabilitˇe tohoto stacionárního rˇ ešení.
5.5
Hledání stabilních rˇešení pro jednoduchý graf
Pro jinou konstelaci podílu, ˚ než v pˇredchozí cˇ ásti, je hledání analytického rˇ ešení pomˇernˇe obtížné. Na pˇríkladu jednoduchého grafu si tak pˇredvedeme, jak hledat stabilní rˇ ešení pomocí numerického výpoˇctu. Ten provedeme v programu MATLAB. Pro hledání takovýchto rˇ ešení využijeme dva typy grafu: ˚ (i) vykreslení takzvané teplotní mapy, která znázorní podíly spolupracujících po zvoleném cˇ ase (ii) vykreslení trajektorií jednotlivých podílu˚ spolupráce pro zvolený cˇ as (pro kontrolu teplotní mapy). Jak ale budeme postupovat, když analyticky nedokážeme urˇcit stabilní rˇ ešení? Budeme se orientovat pˇredevším na oblasti pˇrípustných parametru˚ b a c pro a = 1; d = 0 (viz Obrázek 3.1).
Obrázek 5.2: K3 - úplný graf se tˇremi vrcholy 28
Dále budeme srovnávat naše výsledky s tím, co stojí ve zdroji [3]. Autoˇri našli mimo jiné pro úplný graf K3 (viz Obrázek 5.2), ve kterém jsou na rozdíl od nás spojeni jedinci a ne populace, následující oblasti atrakce (názvy her dle Tabulky 3.1): • plnou spolupráci zasahující do her PS a LJ, • žádnou spolupráci zasahující do oblasti hry VD a vˇetší cˇ ásti oblastí LJ a JH, Navíc v oblastech JH a PS je bílá oblast, kde se zˇrejmˇe nachází urˇcitá koexistence. Pˇresnˇe na to my se pokusíme navázat s naším modelem pro populace. Nebudeme sice hledat oblasti atrakce pro stejnˇe velké podíly, ale mužeme ˚ zkoušet "podobnˇe velké" podíly jako poˇcáteˇcní podmínky. Pokusíme se taky najít v našem modelu koexistenci. Budeme tedy vycházet z grafu K3 . Ukažme si nejprve, že i v našem pˇrípadˇe bude pro oblasti pˇrípustných parametru˚ b a c pˇrevažovat nespolupráce. Pro obrázky v této kapitole platí, že cˇ ervená znamená nespolupráci xi = 0, zelená spolupráci xi = 1 a cˇ erná koexistenci xi ≈ 0, 5.
(a) 1. uzel
(b) 2. uzel
(c) 3. uzel
Obrázek 5.3: Teplotní mapa spolupráce všech populací pro celou oblast parametru˚ b a c poˇcáteˇcní podmínky x1 = 0, 49; x2 = 0, 5; x3 = 0, 51 Na Obrázku 5.3 vidíme velmi podobné výsledky, jako ve zmínˇeném zdroji [3]. Náš model má ale zcela jistˇe horší pˇredpoklad pro spolupráce, nebot’ zdánlivá oblast koexistence sahá do oblasti JH jen z malé cˇ ásti. Pokud chceme mít jistotu, že populace své hodnoty již nezmˇení, dáme do programu simulace zastavovací podmínku, která ukonˇcí simulaci, pokud hodnoty za urˇcitý cˇ as zusta˚ nou s urˇcitou odchylkou stejné. Náš jednoduchý model se typicky ustaloval do cˇ asu t = 10.000, vykreslované hodnoty jsou pro již ustálené stavy v t = 100.000. Podívejme se napˇríklad na libovolnou hodnotu z cˇ erné oblasti druhé populace (viz Obrázek 5.4). Pro nás tedy nemá cenu dukladnˇ ˚ eji zkoumat oblast parametru˚ her VD a LJ, ale budeme se víc vˇenovat té "zajímavé" cˇ ásti - 2. uzel naznaˇcuje výskyt koexistence pro oblast, kde 1. uzel ukazuje nespolupráci a 3. uzel spolupráci. Právˇe na tuto cˇ ást se podíváme blíže a 29
Obrázek 5.4: Trajektorie podílu spolupracujících x2 pro b = 0, 9; c = 1, 4 - poˇcáteˇcní podmínky x1 = 0, 49; x2 = 0, 5; x3 = 0, 51
(a) x1 = 0, 09; x2 = 0, 1; x3 = 0, 11
(b) x1 = 0, 29; x2 = 0, 3; x3 = 0, 31
(c) x1 = 0, 89; x2 = 0, 9; x3 = 0, 91
Obrázek 5.5: Teplotní mapa spolupráce v druhých uzlech pro celou oblast parametru˚ b a c. Poˇcáteˇcní podíly stojí pod pˇríslušným obrázkem vyzkoušíme, zda pro jiné poˇcáteˇcní podmínky vyjde stejný výsledek nebo jestli se naopak oblasti spolupráce zmˇení. Z Obrázku 5.5 dokážeme vyˇcíst dva zajímavé poznatky: • oblast koexistence se pˇri zmˇenˇe poˇcáteˇcních podílu˚ nemˇení, • cˇ ím vˇetší (v tomto pˇrípadˇe) x2 ), tím vˇetší je oblast atrakce pro spolupráci, která zasahuje do oblasti LJ. V prvním pˇríkladu jsme volili poˇcáteˇcní podmínky pˇribližnˇe stejné kolem podílu spolupráce 0,5. Zkusme tedy volit podíl spolupráce, kolem kterého se ostatní poˇcáteˇcní podíly nacházejí, postupnˇe menší a pozdˇeji vˇetší. Vykreslíme si pak teplotní mapu spolupráce pro 30
(a) x1 = 0, 75; x2 = 0, 5; x3 = 0, 25
(b) x1 = 0, 9; x2 = 0, 5; x3 = 0, 1
(c) x1 = 0, 99; x2 = 0, 5; x3 = 0, 01
Obrázek 5.6: Teplotní mapa spolupráce v druhých uzlech pro celou oblast parametru˚ b a c. Poˇcáteˇcní podíly stojí pod pˇríslušným obrázkem populaci, jejíž poˇcáteˇcní podíl leží "mezi" poˇcáteˇcními podíly ostatních. Výsledek vidíme na Obrázku 5.5. Zdá se tedy, že oblast koexistence v našem pˇrípadˇe skuteˇcnˇe existuje. O to cennˇejší je, že se tato oblast nezmenšuje ani nezvˇetšuje, když mˇeníme poˇcáteˇcní podmínky. Navíc model reaguje realisticky v tom ohledu, že pˇri celkovˇe vyšších poˇcáteˇcních podílech spolupráce (teplotní (c) a (d) v Obrázku 5.5) je také oblast atrakce pro spolupráci vˇetší. Fungování modelu jsme prozkoumali pro pˇrípad, kdy jsou jednotlivé podíly spolupracujících xi pˇribližnˇe stejné. Zkusme nyní udˇelat pravý opak a zkoumat vliv rostoucího rozdílu mezi hodnotami xi . V Obrázku 5.6 vidíme již zmínˇenou oblast koexistence, ale pˇredevším vidíme, že rostoucí rozdíl mezi podíly vede k tomu, že se nám v oblasti LJ tvoˇrí zajímavý "pás nespolupráce", který v zdroji [3] k vidˇení není. Zdá se tedy, že se nám pomˇernˇe silnˇe nastavená závislost na sousedech tady projevuje celkem zˇretelnˇe. Když vše shrneme, tak mužeme ˚ rˇ íct, že v porovnání s výsledky ze zdroje [3] "funguje" náš model pˇribližnˇe stejnˇe - oblasti atrakce a koexistence se nachází ve stejných místech. Co se spolupráce týˇce, je, jak zmínˇeno, náš model urˇcitˇe "horší", což závisí i na vysokém vlivu sousedících populací, který je nastaven v tomto modelu. Navíc se zdá být nemˇenná oblast koexistence v podobných místech, jako v literatuˇre [3]. Dosáhli jsme i nových výsledku˚ v podobˇe oblasti atrakce nespolupráce uprostˇred oblasti atrakce spolupráce, která silnˇe závisí na tom, jak volíme poˇcáteˇcní podmínky - cˇ ím ruzno˚ rodˇejší konstelace populací je, tím pestˇrejší je i výsledná teplotní mapa.
31
Kapitola 6
Závˇer V této práci jsme se snažili postupnˇe od základu˚ teorie her dojít k již pomˇernˇe složitým strukturám - zaˇcali jsme na definici pojmu "hra" a na závˇer došli až k modelování chování mezi sebou propojených populací. Pˇredstavili jsme si nejduležitˇ ˚ ejší koncepty a principy, jak teorie her rˇ eší urˇcité situace, kdy dojde k jednorázovému rozhodnutí - v souvislosti s touto problematikou jsme si pˇredstavili Nashovu rovnováhu. Jak bylo rˇ eˇceno v úvodu, tak teorie her nezkoumá jen tyto základní a pomˇernˇe jednoduché úlohy. Podobnˇe jsme pokroˇcili i v této práci a ukázali jsme si na pˇríkladech ze základu, ˚ že podle nich se dá hodnotit z urˇcitého úhlu pohledu i evoluˇcní vývoj. Zamˇerˇ ili jsme se na spolupráci a její vývoj a dostali jsme se tak definitivnˇe do oblasti evoluˇcních dynamik. Evoluce je z cˇ ásti i náhodná, a tak jsme se seznámili s nˇekolika koncepty, které právˇe tento princip zahrnují. Nicménˇe my si ukázali cestu, jak toto "obejít"a vytvoˇrit deterministický, to znamená "pˇredvídatelný" model. Ukázali jsme si taktéž, jak se dá evoluce "pˇredvídat" na grafech - jedna z možností v tomto ohledu je široce využívaná imitaˇcní dynamika. Právˇe ona se stala klíˇcovou v další cˇ ásti této práce, kde jsme si pˇredstavili nový model pro vývoj spolupráce. Pˇredtím jsme si ukázali replikátorovou dynamiku a princip, na kterém je založena. Detailnˇe jsme si rozebrali, jak se u ní urˇcuje již zmínˇený "budoucí" vývoj, a pˇresnˇe na tomto základu jsme postavili náš nový model. Vycházeli jsme z toho, že chceme modelovat chování populací, které jsou spojeny v grafu, a v podstatˇe ze všeho, co jsme si do tohoto okamžiku v práci uvedli, jsme nˇeco pˇrevzali do nového modelu - došlo tak ke spojení modelu pro nekoneˇcnˇe velké populace a oblasti evoluˇcních her na grafech. Patˇriˇcnˇe jsme si pak hotový model popsali, než jsme ho zaˇcali "zkoušet" - nejdˇrív analyticky a pak prakticky. V obou možnostech se skrývají možnosti pro další výzkum. Narazili jsme na zajímavé výsledky a pˇredevším skuteˇcnost, že oblast atrakce nespolupráce byla v nˇekolika pˇrípadech svíraná oblastí spolupráce, což dává podklad pro další zkoumání, napˇríklad: Dá se zmínˇená oblast konkrétnˇe analyticky popsat? Jak to bude vypadat u složitˇejších grafu? ˚
32
Literatura [1] Mark Broom and Jan Rychtár, Game-theoretical models in biology, CRC Press, 2014. ˇ [2] Roman Cada, Zdenˇek Ryjáˇcek, and Tomáš Kaiser, Diskrétní matematika, Západoˇceská univerzita, 2004. [3] Jeremias Epperlein, Stefan Siegmund, and Petr Stehlík, Evolutionary games on graphs and discrete dynamical systems, Journal of Difference Equations and Applications 21 (2015), no. 2, 72–95. [4] Václav Hasenöhrl, Srovnání evoluˇcních dynamik, Bachelor’s thesis, West Bohemia University, 2014. [5] Alois Kufner, Obyˇcejné diferenciální rovnice, Západoˇceská univerzita, 1993. [6] Martin Nowak, Evolutionary dynamics, Harvard University Press, 2006. [7] Hisashi Ohtsuki and Martin A Nowak, Evolutionary games on cycles, Proceedings of the Royal Society B: Biological Sciences 273 (2006), no. 1598, 2249–2256. [8] James Webb, Game theory: decisions, interaction and evolution, vol. 2, Springer Science & Business Media, 2007.
33
