Difference between revisions of "Repeated games/cs"
m (Vytvoření referencí na ostatní pojmy na této WIKI) |
|||
| (11 intermediate revisions by the same user not shown) | |||
| Line 4: | Line 4: | ||
*'''předmět:''' 4IT495 Simulace systémů | *'''předmět:''' 4IT495 Simulace systémů | ||
| − | Opakované hry jsou součástí mnohem širší problematiky nazývané jako teorie her. Nenechme se ovšem zmýlit - s hraním her mají jen pramálo společného. Pro pochopení opakovaných her je nezbytné osvojit si znalosti her jednorázových (statických). | + | Opakované hry jsou součástí mnohem širší problematiky nazývané jako [[Game theory/cs |teorie her]]. Nenechme se ovšem zmýlit - s hraním her mají jen pramálo společného. Pro pochopení opakovaných her je nezbytné osvojit si znalosti [[One-shot game/cs |her jednorázových (statických)]]. |
=Úvod= | =Úvod= | ||
| − | Opakované hry jsou takové hry, při kterých je jednorázová či vícekolová hra stejnými hráči řešena opakovaně. Tito hráči mají přístup k výsledkům předcházejících her a mají možnost rozvrhnout si své tahy dopředu. Vzniká zde tedy široký prostor pro plánování všemožných strategií, které mohou nejen reagovat na tahy soupeře (učení se), ale hráč má zároveň možnost vytvářet strategie, kterými může svého soka přelstít a maximalizovat tak svou výplatu (užitek). V kapitole se budeme zabývat jevy jako jsou kooperace, výhružky či odplata. | + | Opakované hry jsou takové [[Games/cs |hry]], při kterých je [[One-shot game/cs |jednorázová]] či vícekolová hra stejnými [[Player/cs |hráči]] řešena opakovaně. Tito hráči mají přístup k výsledkům předcházejících her a mají možnost rozvrhnout si své tahy dopředu. Vzniká zde tedy široký prostor pro plánování všemožných [[Strategy/cs |strategií]], které mohou nejen reagovat na tahy soupeře ([[Learning/cs |učení se]]), ale hráč má zároveň možnost vytvářet strategie, kterými může svého soka přelstít a maximalizovat tak svou [[Utility/cs |výplatu (užitek)]]. V kapitole se budeme zabývat jevy jako jsou [[Cooperation in game theory/cs |kooperace]], [[Threats in game theory/cs |výhružky]] či [[Revenge in game theory/cs |odplata]]. |
| − | Opakované hry mají tedy mnohem blíže k fungování reálného světa tak, jak ho známe, kde spolu jednotlivé strany často soupeří více než jen jednou. Každá ze stran si je přitom vědoma vlivu svého rozhodnutí na chování svého protihráče. | + | Opakované hry mají tedy mnohem blíže k fungování [[Real world/cs |reálného světa]] tak, jak ho známe, kde spolu jednotlivé strany často soupeří více než jen jednou. Každá ze stran si je přitom vědoma vlivu svého rozhodnutí na chování svého protihráče. |
=Plán= | =Plán= | ||
| − | Každý hráč musí mít předem stanovený plán hry, který bude jasně definovat, jak se zachová v konkrétních situacích, jež mohou během hry nastat. Tyto strategie se nazývají meta-strategie. Aby byla strategie rovnovážná, musí být nejlepší odpovědí na všechny možné tahy ostatních hráčů ve hře. | + | Každý hráč musí mít předem stanovený [[Meta strategy/cs |plán hry]], který bude jasně definovat, jak se zachová v konkrétních situacích, jež mohou během hry nastat. Tyto strategie se nazývají [[Meta strategy/cs |meta-strategie]]. Aby byla strategie [[Equilibrium strategy/cs |rovnovážná]], musí být nejlepší odpovědí na všechny možné tahy ostatních hráčů ve hře. |
| − | Pozorovateli takové hry by mohlo připadat, že hráči v opakované hře v jednotlivých kolech nemaximalizují svůj užitek, tedy že jednají iracionálně. To je důsledkem toho, že maximalizace vlastního užitku v jednom kole nutně nemusí vést k maximalizaci užitku v dlouhodobém horizontu. | + | Pozorovateli takové hry by mohlo připadat, že hráči v opakované hře v jednotlivých kolech [[Utility maximalization/cs |nemaximalizují svůj užitek]], tedy že jednají [[Irataional behavior/cs |iracionálně]]. To je důsledkem toho, že maximalizace vlastního užitku v jednom kole nutně nemusí vést k maximalizaci užitku v [[Long-term horizon/cs |dlouhodobém horizontu]]. |
| − | |||
| − | |||
=Základní dělení= | =Základní dělení= | ||
| − | Opakované hry jsou dle délky trvání děleny na hry nekonečné a konečné, přičemž konečně opakované hry dále dělíme na konečné s neznámým koncem a konečné se známým koncem | + | Opakované hry jsou dle délky trvání děleny na hry [[Infinite and indefinite games/cs |nekonečné]] a [[Finite games/cs |konečné]], přičemž konečně opakované hry dále dělíme na [[Indefinite/cs |konečné s neznámým koncem]] a [[Finite games/cs |konečné se známým koncem]] <ref name="gibbons" />. Pokud je hra opakována nekonečněkrát, hráči se domnívají, že konec hry nenastane a své strategie přizpůsobují této informaci. Pokud je však předem znám počet opakování hry, jedná se o hru konečnou se známým, předem stanoveným koncem. Takovéto hry se pak řeší pomocí zpětné indukce. Mezi těmito dvěma variantami pak leží konečně opakované hry s neznámým koncem, kde si jsou hráči vědomi toho, že hra je konečná, nemají však informaci o tom, kdy doopravdy skončí. Operují tak pouze s [[Probability/cs |pravděpodobností]], že hra bude mít ještě další kolo. Konečně opakované hry s neznámým koncem proto řadíme do kategorie nekonečných her. |
=Konečně opakované hry se známým koncem= | =Konečně opakované hry se známým koncem= | ||
| − | Aby byla hráčem zvolená strategie rovnovážnou strategií, musí být nejlepší možnou odpovědí na zvolené strategie druhého hráče v každém opakování hry. Každé jednotlivé opakování hry je přitom podhrou (subgame) celé hry, je tedy zřejmé, že budeme hledat Nashovo rovnovážné řešení podrhy (subgame perfect Nash equilibrium; SPNE) | + | Aby byla hráčem zvolená strategie [[Equilibrium strategy/cs |rovnovážnou strategií]], musí být nejlepší možnou odpovědí na zvolené strategie druhého hráče v každém opakování hry. Každé jednotlivé opakování hry je přitom [[Subgame/cs |podhrou (subgame)]] celé hry, je tedy zřejmé, že budeme hledat [[Subgame Perfect Nash Equilibrium/cs |Nashovo rovnovážné řešení podrhy (subgame perfect Nash equilibrium; SPNE)]] <ref name="slamova" />. Protože posledním kolem konečně opakované hry je konkrétní podhra, je možné za cílem nalezení SPNE využít [[Backward induction/cs |zpětné indukce]]. |
| − | Mnozí z vás se již jistě setkali s takzvaným vězňovo dilematem. Jen krátké přípomenutí: mějme dva od sebe oddělené vězně obviněné ze spáchání společného zločinu. Každý z nich má stejné možnosti volby strategií - přiznat se, tedy nekooperovat (P) a nepřiznat se, tedy kooperovat (N). Jednotlivé výplaty jsou znázorněny v matici níže (čím vyšší číslo, tím větší osobní užitek pro daného vězně). | + | Mnozí z vás se již jistě setkali s takzvaným [[Prisonners Dilemma/cs |vězňovo dilematem]]. Jen krátké přípomenutí: mějme dva od sebe oddělené vězně obviněné ze spáchání společného zločinu. Každý z nich má stejné možnosti volby strategií - přiznat se, tedy nekooperovat (P) a nepřiznat se, tedy kooperovat (N). Jednotlivé výplaty jsou znázorněny v matici níže (čím vyšší číslo, tím větší osobní užitek pro daného vězně). |
{| class="wikitable" | {| class="wikitable" | ||
| Line 39: | Line 37: | ||
|} | |} | ||
| − | Jak už jistě víte, Nashovým rovnovážným řešením statického jednokolového vězňova dilematu je {P,P} (pokud vám není jasné, jak jsme na toto přišli, doporučuji vrátit se zpět k problematice Nashovi rovnováhy). V konečně opakované verzi této hry nás zpětná indukce zavede ke stejnému výsledku, tedy že strategie {P,P} bude strategií obou hráčů ve všech kolech konečně opakované hry. Toto na první pohled nelogické řešení je často nazýváno paradoxem zpětné indukce. | + | Jak už jistě víte, Nashovým rovnovážným řešením statického jednokolového vězňova dilematu je ''{P,P}'' (pokud vám není jasné, jak jsme na toto přišli, doporučuji vrátit se zpět k problematice [[Nash Equilibrium/cs |Nashovi rovnováhy]]). V konečně opakované verzi této hry nás zpětná indukce zavede ke stejnému výsledku, tedy že strategie ''{P,P}'' bude strategií obou hráčů ve všech kolech konečně opakované hry. Toto na první pohled nelogické řešení je často nazýváno [[Backward Induction paradox/cs |paradoxem zpětné indukce]]. |
==Důkaz zpětné indukce== | ==Důkaz zpětné indukce== | ||
| − | Ve statické verzi vězňova dilematu je strategie {P,P} (ve skutečnosti se jedná o vektor strategií jednotlivých hráčů, kde první P znázorňuje volbu prvního hráče a druhé P druhého hráče, pro snažší pochopení budeme vektor takovýchto strategií nazývat souhrně "strategií [hry]") dominantní strategií, kooperace není Nashovým rovnovážným řešením (NE). U konečně opakovaných her můžeme k vyřešení vězňova dilematu použít zpětné indukce. Ta se nejprve pokusí určit, jak se hráči zachovájí v posledním kole a následně postupuje vždy o jeden krok zpět až na úplný začátek hry. | + | Ve statické verzi vězňova dilematu je strategie ''{P,P}'' (ve skutečnosti se jedná o [[Strategy set/cs |vektor strategií jednotlivých hráčů]], kde první ''"P"'' znázorňuje volbu prvního hráče a druhé ''"P"'' druhého hráče, pro snažší pochopení budeme [[Vector/cs |vektor]] takovýchto strategií nazývat souhrně ''"strategií [hry]"'') [[Dominant strategy/cs |dominantní strategií]], kooperace není Nashovým rovnovážným řešením (NE). U konečně opakovaných her můžeme k vyřešení vězňova dilematu použít zpětné indukce. Ta se nejprve pokusí určit, jak se hráči zachovájí v posledním kole a následně postupuje vždy o jeden krok zpět až na úplný začátek hry. |
| − | Předpokládejme, že hra má 10 opakování. Při aplikaci zpětné indukce se tedy nejprve přeneseme do desáté hry, která pro oba hráče vypadá jako hra statická. Proč? Protože oba vědí, že další hra nebude už následovat, tím pádem není možné potrestat druhého hráče za to, že nebude kooperovat. Jejich cílem je tedy nalézt NE a to zahrát, zvolí tedy {P,P}. V předposlední fázi hry, tedy v devátém kole, oba hráči vědí, že v posledním desátém kole zahrají {P,P} a proto nemají důvod ani nyní kooperovat, tedy zahrát {N,N}. Budou tedy opět volit strategii {P,P}. To samé platí i pro osmé kolo, kdy oba hráči ze stejných důvodů opět zahrají {P,P}. Tento proces se opakuje až do prvního kola, kdy hráči vědí, že všechna následující kola zahrají {P,P} a budou tedy i v prvním kole volit strategii {P,P}. SPNE všech kol opakované hry je tedy přiznání obou hráčů k trestnému činu. | + | Předpokládejme, že hra má 10 opakování. Při aplikaci zpětné indukce se tedy nejprve přeneseme do desáté hry, která pro oba hráče vypadá jako hra statická. Proč? Protože oba vědí, že další hra nebude už následovat, tím pádem není možné potrestat druhého hráče za to, že nebude kooperovat. Jejich cílem je tedy nalézt ''NE'' a to zahrát, zvolí tedy ''{P,P}''. V předposlední fázi hry, tedy v devátém kole, oba hráči vědí, že v posledním desátém kole zahrají ''{P,P}'' a proto nemají důvod ani nyní kooperovat, tedy zahrát ''{N,N}''. Budou tedy opět volit strategii ''{P,P}''. To samé platí i pro osmé kolo, kdy oba hráči ze stejných důvodů opět zahrají ''{P,P}''. Tento proces se opakuje až do prvního kola, kdy hráči vědí, že všechna následující kola zahrají ''{P,P}'' a budou tedy i v prvním kole volit strategii ''{P,P}''. ''SPNE'' všech kol opakované hry je tedy přiznání obou hráčů k trestnému činu. |
==Výplata konečně opakovaných her== | ==Výplata konečně opakovaných her== | ||
| − | Výplata pro hry s konečným opakováním je vypočítána jako součet všech dosažených výplat v jednotlivých kolech. V případě desetikolového vězňova dilematu z matice výše by celková výplata obou hráču byla 10 | + | [[Pay-off/cs |Výplata]] pro hry s konečným opakováním je vypočítána jako součet všech dosažených výplat v jednotlivých kolech. V případě desetikolového vězňova dilematu z matice výše by celková výplata obou hráču byla 10 krát 1, tedy 10. |
=Nekonečně opakované hry a konečně opakované hry s neznámým koncem= | =Nekonečně opakované hry a konečně opakované hry s neznámým koncem= | ||
| − | Paradox zpětné indukce lze eliminovat zavedením nejistoty ohledně užitku některého z hráču, jeho racionality nebo ohledně samotného konce opakované hry. Teorii budeme ilustrovat právě na případu posledně zmíněného, tedy nejasného konce hry. | + | Paradox zpětné indukce lze eliminovat zavedením nejistoty ohledně užitku některého z hráču, jeho [[Rational behavior/cs |racionality]] nebo ohledně samotného konce opakované hry. Teorii budeme ilustrovat právě na případu posledně zmíněného, tedy nejasného konce hry. |
| − | Tento stav předpokládá, že ani jeden z hráčů přesně neví, kdy hra skončí (ačkoliv se její konec očekává) nebo věří, že hra neskončí nikdy. Tento výchozí stav vede k tomu, že kooperace, tedy vektor strategií {N,N} se najednou stává rovnovážným řešením obou hráčů. Jak už asi správně hádáte, nebude to tak jednoduché jak se na první pohled zdá. Problém nyní nastává s tím, že neexistuje pouze jediné rovnovážné řešení, ale rovnovážných řešení je více. Tento jev je nazýván jako "folk theorem" | + | Tento stav předpokládá, že ani jeden z hráčů přesně neví, kdy hra skončí (ačkoliv se její konec očekává) nebo věří, že hra neskončí nikdy. Tento výchozí stav vede k tomu, že kooperace, tedy vektor strategií ''{N,N}'' se najednou stává rovnovážným řešením obou hráčů. Jak už asi správně hádáte, nebude to tak jednoduché, jak se na první pohled zdá. Problém nyní nastává s tím, že neexistuje pouze jediné rovnovážné řešení, ale rovnovážných řešení je více. Tento jev je nazýván jako [[Folk Theorem/cs |''"folk theorem"'']] <ref name="osborneold" />. |
| − | "První tzv. | + | "První tzv. ''"folk teorém"'' tvrdí, že jakýkoliv dosažitelný individuálně racionální výplatní vektor může být Nashovou rovnováhou opakované hry. Druhý ''"folk teorém"'' říká, že dosažitelný výplatní vektor, který [[Pareto domination/cs |Paretovsky dominuje]] jakýkoliv výplatní vektor statické rovnováhy jednorázové hry, může být SPE opakované hry." <ref name="slamova" /> |
| − | Jelikož pro určení rovnovážného řešení hry nyní nemůžeme využít zpětné indukce, hráči se | + | |
| + | Jelikož pro určení rovnovážného řešení hry nyní nemůžeme využít zpětné indukce, hráči se místo dozadu dívají dopředu a pro každou možnou strategii určují její celkovou výplatu. Díky tomu je do jednotlivých strategií hráčů nyní možné zakomponovat i takové prvky jako jsou [[Reward in game theory/cs |odměny]], [[Threats in game theory/cs |výhružky]] či [[Revenge in game theory/cs |odplaty]]. | ||
==Strategie== | ==Strategie== | ||
| − | Podívejme se opět na matici Vězňova dilematu z předešlé sekce. I u takto jednoduchého problému je v případě her specifikovaných v této kapitole možné volit z téměř nekonečného množství možných meta-strategií. Ty nejznámější si nyní vyjmenujeme | + | Podívejme se opět na matici Vězňova dilematu z předešlé sekce. I u takto jednoduchého problému je v případě her specifikovaných v [[#Konečně opakované hry se známým koncem |této kapitole] možné volit z téměř nekonečného množství možných meta-strategií. Ty nejznámější si nyní vyjmenujeme <ref name="slamova" /> a později si jednu i podrobněji popíšeme: |
| − | *Vždy podvádět (Always Defect) | + | *[[Always Defect Strategy/cs |Vždy podvádět (Always Defect)]] |
| − | *Vždy spolupracovat (Always Cooperate) | + | *[[Always Cooperate Strategy/cs |Vždy spolupracovat (Always Cooperate)]] |
| − | *Naivní Grim Trigger | + | *[[Naive Grim Trigger Strategy/cs |Naivní Grim Trigger]] |
| − | *Grim Trigger | + | *[[Grim Trigger Strategy/cs |Grim Trigger]] |
| − | *Oko za ok, zub za zub (Tit for Tat) | + | *[[Tit for Tat Strategy/cs |Oko za ok, zub za zub (Tit for Tat)]] |
| − | *Omezená odplata (Limited Retaliation) | + | *[[Limited Retaliation Strategy/cs |Omezená odplata (Limited Retaliation)]] |
| − | *Strategie Win-Stay, Lose-Shift (WS-LS) | + | *[[WS-LS Strategy/cs |Strategie Win-Stay, Lose-Shift (WS-LS)]] |
| − | *Jednou se odchýlit (Deviate Once) | + | *[[Deviate Once Strategy/cs |Jednou se odchýlit (Deviate Once)]] |
| − | *Grim Deviate Once | + | *[[Grim Deviate Once Strategy/cs |Grim Deviate Once]] |
==Představení konečně opakované hry s neznámým koncem pomocí příkladu== | ==Představení konečně opakované hry s neznámým koncem pomocí příkladu== | ||
| − | Mějme dva vězně - Petra a Martina - kteří jsou oba zastánci Grim Trigger strategie a jsou postaveni před opakovanou hru vězňova dilematu. Grim Trigger strategie je taková strategie, kdy hráč v prvním kole kooperuje a pokračuje v kooperaci až do té doby, dokud všichni hráči v předešlém kole kooperovali. Jakmile některý z hráčů přestane kooperovat, ten druhý automaticky také přestane kooperovat a takto pokračují dále bez jakékoliv další změny. Nyní je tedy i jasné, proč se tato strategie nazývá nepromíjející strategií - přísně trestá jakýkoliv prohřešek druhého hráče. | + | Mějme dva vězně - Petra a Martina - kteří jsou oba zastánci [[Grim Trigger Strategy/cs |Grim Trigger]] strategie a jsou postaveni před opakovanou hru vězňova dilematu. Grim Trigger strategie je taková strategie, kdy hráč v prvním kole [[Cooperation in Game Theory/cs |kooperuje]] a pokračuje v kooperaci až do té doby, dokud všichni hráči v předešlém kole kooperovali. Jakmile některý z hráčů přestane kooperovat, ten druhý automaticky také přestane kooperovat a takto pokračují dále bez jakékoliv další změny. Nyní je tedy i jasné, proč se tato strategie nazývá nepromíjející strategií - přísně trestá jakýkoliv prohřešek druhého hráče. |
Nyní se skrze analýzu výplat obou hráčů pokusíme odpovědět na otázku, zda Grim Trigger strategie skutečně vede ke vzájemné spolupráci. | Nyní se skrze analýzu výplat obou hráčů pokusíme odpovědět na otázku, zda Grim Trigger strategie skutečně vede ke vzájemné spolupráci. | ||
| Line 87: | Line 86: | ||
|} | |} | ||
| − | Nejprve se na hru podíváme z pohledu Petra. Jaká by měla být jeho volba, pokud věří, že Martin dodržuje strategii Grim Trigger? Pokud bude kooperovat, jeho očekávaná výplata bude 3 a další 3 získá za každé další odehrané kolo. Nyní mějme fixní pravděpodobnost P, P | + | Nejprve se na hru podíváme z pohledu Petra. Jaká by měla být jeho volba, pokud věří, že Martin dodržuje strategii Grim Trigger? Pokud bude kooperovat, jeho očekávaná výplata bude ''3'' a další ''3'' získá za každé další odehrané kolo. Nyní mějme fixní pravděpodobnost <math>P</math>, <math>P \in (0, 1)</math>, která nám říká, s jakou pravděpodobností hra bude pokračovat i druhým kolem. Poté pravděpodobnost, že hra bude pokračovat třetím je <math>P^2</math>, čtvrtým <math>P^3</math> atd. Petrova očekávaná výplata ze spolupráce (<math>OV_{spoluprace}</math>) s Martinem je tedy: |
| − | + | <math>OV_{spoluprace} = 3 + 3P + 3P^2 + 3P^3 + 3P^4 + ... 3P^n = \sum_{n=0}^{n = \infty} 3P^n = \frac{3}{1 - P} </math> | |
| − | Pokud však Petr odmítne spolupracovat a vědomě (či vinou chyby) poruší kooperaci, získá jednorázovou výplatu v hodnotě 4 a poté již samé 1. Petrova očekávaná výplata z porušení | + | Pokud však Petr odmítne spolupracovat a vědomě (či vinou chyby) poruší kooperaci, získá jednorázovou výplatu v hodnotě ''4'' a poté již samé ''1''. Petrova očekávaná výplata z porušení spolupráce (<math>OV_{nespoluprace}</math>) s Martinem hned po prvním kole je tedy: |
| − | + | <math>OV_{nespoluprace} = 4 + P + P^2 + P^3 + P^4 + ... P^n = 4 + \sum_{n=0}^{n = \infty} P^n = 4 + \frac{P}{1 - P} </math> | |
| + | |||
| + | Z výše uvedeného jasně vyplývá, že má-li se Petr držet spolupráce, musí pro něj být výhodnější než její porušení. V našem případě musí být konkrétně <math>P</math>, tedy pravděpodobnost dalšího pokračování hry, vyšši než <math>\frac{1}{3}</math>. Postup výpočtu je uveden níže: | ||
| + | |||
| + | <math>\frac{3}{1-P} > 4 + \frac{1P}{1-P}</math> | ||
| + | |||
| + | <math>3 > 4(1-P) + 1P</math> | ||
| + | |||
| + | <math>3 - 4 > P(1-4)</math> | ||
| − | + | <math>\frac{1}{3} < P </math> | |
| − | |||
Abychom byli schopni toto aplikovat na jakýkoliv příklad, vytvořili jsme následující obecnou matici: | Abychom byli schopni toto aplikovat na jakýkoliv příklad, vytvořili jsme následující obecnou matici: | ||
| Line 114: | Line 120: | ||
|} | |} | ||
| − | přičemž platí, že c>a>d>b | + | přičemž platí, že <math>c > a > d > b</math> |
| + | |||
| + | Pravděpodobnost, že hra bude pokračovat i dalším kolem je stále <math>P</math>. Oba hráči se i nadále drží strategie Grim trigger. Pokud oba hráči kooperují, mohou až do konce hry očekávat výplatu v podobě ''"a"''. <math>OV_{spoluprace}</math> je tedy: | ||
| + | |||
| + | <math>OV_{spoluprace} = a + aP + aP^2 + aP^3 + aP^4 + ... aP^n = \sum_{n=0}^{n = \infty} aP^n = \frac{a}{1 - P} </math> | ||
| + | |||
| + | Pokud kdokoliv z hráčů přestane spolupracovat, získá jednorázový zisk ve výši ''"c"'' a dále už jen ''"d"''. <math>OV_{nespoluprace}</math> je tedy: | ||
| − | + | <math>OV_{nespoluprace} = c + dP + dP^2 + dP^3 + dP^4 + ... dP^n = c + \sum_{n=0}^{n = \infty} dP^n = c + \frac{dP}{1 - P} </math> | |
| − | + | Jestliže mají oba hráči spolupracovat, je nutné, aby <math>OV_{spoluprace}</math> bylo vyšší než <math>OV_{nespoluprace}</math>, tedy: | |
| − | + | <math> | |
| − | + | \frac{a}{1-P} & > c + \frac{dP}{1-P} \\ | |
| + | \\ | ||
| + | a & > c(1-P) + dP = c - cP + dP \\ | ||
| + | \\ | ||
| + | a - c & > P(d-c) \\ | ||
| + | </math> | ||
| − | + | A protože víme, že <math>a - c < 0 </math> a že <math>d - c < 0</math>, můžeme rovnici zjednodušit na: | |
| − | + | <math>\frac{a-c}{d-c} < P </math> | |
| − | + | Tato podmínka je platná pro všechny hry vězňova dilematu. <ref name="car" /> | |
| − | + | Nyní můžeme stanovit hraniční hodnotu <math>P</math>, <math>P^*</math>, u které platí, že je-li <math>P >\frac{a-c}{d-c} = P^*</math>, nemá ani jeden z hráčů potřebu odchýlit se od spolupráce a ke spolupráci tak dojde ve všech opakováních hry <ref name="car" />. Můžeme tedy říci, že pokud je hodnota <math>P</math> dostatečně vysoká, existuje ve vězňově dilematu takové SPNE, které vede u Grim Trigger strategie ke spolupráci. | |
==Nekonečně opakované hry== | ==Nekonečně opakované hry== | ||
| − | V případě nekonečně opakovaných her je jasné, že, jak už z názvu vyplývá, není možné počítat s pravděpodobností P, která nám v sekci výše určovala pravděpodobnost, že se hra dostane do dalšího kola. Hráči totiž vždy věří, že hra bude pokračovat. | + | V případě nekonečně opakovaných her je jasné, že, jak už z názvu vyplývá, není možné počítat s pravděpodobností <math>P</math>, která nám v[[#Představení konečně opakované hry s neznámým koncem pomocí příkladu |sekci výše]] určovala pravděpodobnost, že se hra dostane do dalšího kola. Hráči totiž vždy věří, že hra bude pokračovat. |
| − | Aby však mohli plánovat své budoucí výplaty, musí začít uvažovat diskontovanou současnou hodnotu budoucích výplat. Současná hodnota budoucí výplaty "X" získané za "n" období se spočítá jako jako X | + | Aby však mohli plánovat své budoucí výplaty, musí začít uvažovat [[Disconted future value/cs |diskontovanou současnou hodnotu]] budoucích výplat. Současná hodnota budoucí výplaty ''"X"'' získané za ''"n"'' období se spočítá jako jako <math>\frac{X}{(1+r)^n}</math>, přičemž ''"r"'' označuje úrokovou míru a <math>\frac{1}{1+r}</math> je diskontní faktor. Každý si nyní jistě vzpomíná na hodiny [[Economics/cs |ekonomie]], kde nám bylo do hlavy vtloukáno, že hodnota peněz získaných nyní je vyšší než hodnota toho samého objemu peněz získaných v budoucnu. A nyní toto pravidlo aplikujeme i u teorie her. |
| − | Očekávaný výnos ze spolupráce vypočítáme jako: | + | '''Očekávaný výnos ze spolupráce vypočítáme jako:''' |
| + | |||
| + | <math>OV_{spoluprace} = a + a\frac{1}{1-r} + a\frac{1}{(1-r)^2} + a\frac{1}{(1-r)^3} + a\frac{1}{(1-r)^4} + ... a\frac{1}{(1-r)^N} ...</math> | ||
| − | Nahrazením 1 | + | |
| + | '''Nahrazením \frac{1}{1-r} diskontním faktorem <math>F</math> získáme:''' | ||
| + | |||
| + | <math>OV_{spoluprace} = a + aF + aF^2 + aF^3 + aF^4 + ... aF^N = \sum_{n=0}^{n = \infty} aF^n = \frac{a}{1 - F} </math> | ||
| + | |||
| − | Při porušení spolupráce získáváme obdobné: | + | '''Při porušení spolupráce získáváme obdobné:''' |
| + | |||
| + | <math>OV_{spoluprace} = c + d\frac{1}{1-r} + d\frac{1}{(1-r)^2} + d\frac{1}{(1-r)^3} + d\frac{1}{(1-r)^4} + ... d\frac{1}{(1-r)^N} ...</math> | ||
| + | |||
| + | '''Nahrazením \frac{1}{1-r} diskontním faktorem <math>F</math> poté získáme:''' | ||
| − | + | <math>OV_{spoluprace} = c + dF + dF^2 + dF^3 + dF^4 + ... dF^N = \sum_{n=0}^{n = \infty} dF^n = c + \frac{dF}{1 - F} </math> | |
| − | |||
| − | + | Je tedy zřejmé, že jediný rozdíl mezi nekonečně opakovanými hrami a hrami s konečným opakováním s neznámým koncem je záměna pravděpodobnosti dalšího pokračování hry, <math>P</math>, s diskontním faktorem <math>F</math>, <math>F \in (0,1)</math>. | |
| − | |||
| − | + | '''O tom, zda pokračovat ve spolupráci nebo se od ní odchýlit pak tedy opět rozhoduje výsledná výplata obou možnosti, neboli:''' | |
| − | + | <math> \frac{a}{1 - F} > c + \frac{dF}{1 - F} </math> | |
| − | Jak už bylo napsáno na začátku této kapitoly, Grim trigger strategie není jedinou meta-strategií, která při řešení vězňova dilematu vede ke vzájemné kooperaci obou hráčů v rámci nekonečně nebo konečně opakovaných her s neznámým koncem. Kooperace může být dosaženo například aplikováním strategie Oko za oko, zub za zub, která nespolupráci trestá nespoluprácí a ke spolupráci se vrací až v moment, kdy se ke spolupráci opět vrátí i trestaný hráč. Podobných kombinací však existuje nespočet | + | |
| + | '''Což můžeme zjednodušit na:''' | ||
| + | |||
| + | <math> \frac{a - c}{d - c} < F </math> | ||
| + | |||
| + | |||
| + | Pokud je tedy <math>F</math> dostatečně vysoké (budoucí hodnota peněz se nule blíží jen velice pomalu), mají oba hráči zájem na tom spolupracovat. Můžeme tedy opět říci, že v takovém případě existuje ve vězňově dilematu takové SPNE, které vede u Grim Trigger strategie ke spolupráci. | ||
| + | |||
| + | Z výše zmíněného vyplývá, že ''"spolupracovat"'' je nejlepší odpovědí na strategii ''"spolupracovat"'' druhé hráče. Jak je to však s výhružkou Grim trigger strategie, která říká, že jakmile druhý hráč přestane kooperovat, bude ukončena kooperace i ze strany prvního hráče? Je strategie ''"nespolupracovat"'' nejlepší odpovědí na strategii ''"nespolupracovat"''? Pokud by tato hrozba nebyla [[Credible threats in game theory/cs |kredibilní]], nemohla by Grim trigger strategie vůbec být SPNE. | ||
| + | |||
| + | Pokud je <math>P</math> (či <math>F</math>) vyšší než požadovaná kritická hodnota, je strategie ''"nespolupracovat"'' opravdu nejlepší odpovědí na strategii ''"nespolupracovat"''. Ve statických hrách se totiž jedná o Nashovu rovnováhu a u her s nekonečným opakováním (případně u her s konečným opakováním a neznámým koncem) není možné, aby se hráč dodržující Grim trigger strategy záměrně odchýlil od spolupráce, aniž by se jednalo o reakci na předchozí akci (odchýlení od kooperace) jeho protihráče. | ||
| + | |||
| + | Vezměme si výše zmíněný příklad z pohledu Martina. Pokud se Petr bezdůvodně odchýlil od spolupráce, nenásleduje Grim trigger strategii. Martin nemůže očekávat, že Petr bude v dalších kolech opět spolupracovat. Následuje tedy svou vlastní Grim trigger strategii a potrestá Petra trvalým přerušením spolupráce. Pokud by snad Petr udělal chybu, hned v dalším kole se vrátil zpět ke spolupráci a Martin mu tuto chybu odpustil, Petr by zjistil, že Martin nehraje Grim trigger strategii a nic by mu nebránilo v dalším kole opět přerušit spolupráci. Nebo také z jiného pohledu - protože Martin nehraje Grim trigget strategii (Petra nepotrestal), nemůže si Petr být jistý, že Martin v dalším kole sám nepřeruší spolupráci a tak raději rovnou spolupráci v dalším kole opět přeruší. | ||
| + | |||
| + | Jak už bylo napsáno na [[#Strategie |začátku této kapitoly]], Grim trigger strategie není jedinou meta-strategií, která při řešení vězňova dilematu vede ke vzájemné kooperaci obou hráčů v rámci nekonečně nebo konečně opakovaných her s neznámým koncem. Kooperace může být dosaženo například aplikováním strategie [[Tit for Tat Strategy/cs |''"Oko za oko, zub za zub"'']], která nespolupráci trestá nespoluprácí a ke spolupráci se vrací až v moment, kdy se ke spolupráci opět vrátí i trestaný hráč. Podobných kombinací však existuje nespočet <ref name="osborneold" />. | ||
=Závěr a odkazy na výzkumy týkající se aplikací teorie her v reálném světě= | =Závěr a odkazy na výzkumy týkající se aplikací teorie her v reálném světě= | ||
| − | Z Folk theorému vyplývá, že nekonečně a konečně opakované hry s neznámým koncem mají více rovnovážných řešení a je tedy téměř nemožné určit, k jakým výsledkům takové hry povedou. Jak jsme však ukázali v této kapitole, dá se předpokládat, že u takových her bude alespoň v jejich části dosaženo vzájemné spolupráce. Uvažováním nejistoty ohledně konce opakované hry jsme změnili vhodné strategie a z nich plynoucí výplaty. Hračí u takovýchto her mají větší vůli kooperovat, protože nekooperace již není | + | Z Folk theorému vyplývá, že nekonečně a konečně opakované hry s neznámým koncem mají více rovnovážných řešení a je tedy téměř nemožné určit, k jakým výsledkům takové hry povedou. Jak jsme však ukázali v této kapitole, dá se předpokládat, že u takových her bude alespoň v jejich části dosaženo vzájemné spolupráce. Uvažováním nejistoty ohledně konce opakované hry jsme změnili vhodné strategie a z nich plynoucí výplaty. Hračí u takovýchto her mají větší vůli kooperovat, protože nekooperace již není jediným [[Subgame perfect equilibrium/cs |subgame rovnovážným řešením]]. |
| − | Shrnutí významných prací zabývajících se aplikací teorie opakovaných her v reálném světě představuje Martin J. Osborne ve své knize “An introduction to Game Theory” | + | Shrnutí významných prací zabývajících se aplikací teorie opakovaných her v reálném světě představuje Martin J. Osborne ve své knize ''“An introduction to Game Theory”'' <ref name="osbornenew" />. Z první části jeho shrnutí vyplává, že mnoho simulací vyhrála strategie ''“Oko za oko, zub za zub”'' (Tit-for-tat). Konkrétní zprávy je možné přečíst v: <ref name="Axelrod1980a" /><ref name="Axelrod1980b" /><ref name="Axelrod1984" />. |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| + | S teorií, že zvířata opakovaně čelí problémům svou strukturou podobným vězňově dilematu přišel Robert L. Trivers v roce 1971 <ref name="Trivers" />. Při pokusu provedeným s rybami (konkrétně [http://cs.wikipedia.org/wiki/Koljuška_tř%C3%ADostná koljuškami]), pozoroval, že ty také využívají strategie ''"Tit-for-tat"''. Výsledky této studie se později pokouší vyvrátit Lazarus a Metcalfe (1990) <ref name="Lazarus" /> a Milinski (1993) <ref name="Milinski" />, který tvrdí, že koljušky nenásledují strategii ''“Oko za oko, zub za zub”'', nýbrž strategii zvanou [[Pavlov Game Strategy/cs |''"Pavlov"'']]. | ||
| − | Mason | + | Z novějších studií jmenujme např. Mason, Phillips a Redington (1991) <ref name="Mason" />, kteří zjišťovali, zda mají ženy větší tendenci ke kooperaci než muži; či Sabater, Grande a Georgantiziz (2002) <ref name="Sabater" />, kteří se věnovali vlivu averze k riziku na pravděpodobnost, že daný subjekt bude kooperovat. |
| − | |||
| + | Všechny studie mají však jeden velký nedostatek – jsou prováděny v umělém prostředí a pozorované subjekty vědí, že nastane konec simulace (a tedy i simulované hry). A to platí i v případech, kdy subjekty nevěděly, kdy přesně daný konec nastane. To vedlo subjekty k tomu, že předpokládaly, že každá hra je tou poslední <ref name="roth" />. | ||
=Další studium= | =Další studium= | ||
==Podrobný rozbor jednotlivých strategií== | ==Podrobný rozbor jednotlivých strategií== | ||
| − | Podrobný rozbor vybraných strategií vyjmenovaných v sekci Strategie provedl Martin J. Osborne ve své knize “An introduction to Game Theory” | + | Podrobný rozbor vybraných strategií vyjmenovaných v sekci [[#Strategie |Strategie]] provedl Martin J. Osborne ve své knize “An introduction to Game Theory” <ref name="osbornenew" />. Konkrétně se jedná o: [[Grim Trigger Strategy/cs |''“Grim trigger strategies”'']], [[Limited Retaliation Strategy/cs |“Limited punishment”]] a [[Tit for Tat Strategy/cs |''“Tit-for-tat”'']]. Zbylé strategie pak méně podrobně rozebírá Alena Skálová ve své diplomové práci na téma “Opakované hry” <ref name="slamova" />. |
==Asymetrické informace při řešení vězňova dilematu u her s konečným opakováním== | ==Asymetrické informace při řešení vězňova dilematu u her s konečným opakováním== | ||
| − | Další řešení zpětné indukce přinesli Kreps, Milgrom, Roberts a Wilson (1982) | + | Další řešení zpětné indukce přinesli Kreps, Milgrom, Roberts a Wilson (1982) <ref name="kreps" />. Ve své práci provedli analýzu vězňova dilematu s konečným opakováním, avšak s tou změnou, že racionalita a/nebo užitek jednoho z hráčů nebyly známé pro toho druhého. To dává za vznik mnoha zajímavým strategiím, kdy se jeden hráč snaží toho druhého přelstít. |
==Komplexita rovnovážných strategií== | ==Komplexita rovnovážných strategií== | ||
| − | Martin J. Osborne se ve své knize “A Course in Game Theory” | + | Martin J. Osborne se ve své knize “A Course in Game Theory” <ref name="osborneold" /> zaobírá komplexitou rovnovážných řešení. Rozšiřuje tak skupinu výsledků prezentovaných v rámci [[Folk theorem/cs |Folk theorem]]. Vychází z toho, že čím složitější je zvolená strategie, tím více je pro hráče nákladná. Požadavkem každého hráče by tak měla být co nejjednodušší strategie. |
==Obrácená implementace== | ==Obrácená implementace== | ||
| − | Ve té samé knize Martin J. Osborne podrobně rozebírá i obrácený postup řešení opakované hry. V první fázi je definován požadovaný soubor výstupů a až poté se hledá hra, která tyto výsledky produkuje. | + | Ve té samé knize <ref name="osborneold" /> Martin J. Osborne podrobně rozebírá i obrácený postup řešení opakované hry. V první fázi je definován požadovaný soubor výstupů a až poté se hledá hra, která tyto výsledky produkuje. |
==Vícekolové hry== | ==Vícekolové hry== | ||
| − | S teorií opakovaných her úzce souvisí i vícekolové hry. Představme si třeba známý příklad dvou obchodních řetězců, kde jeden má již na trhu stabilní pozici a druhý teprve uvažuje o vstupu na trh. Pokud by takové rozhodování probíhalo např. v rámci několika měst, jednalo by se o opakovanou hru. Více o této problematice je možné nastudovat na stránce Vícekolové hry. | + | S teorií opakovaných her úzce souvisí i vícekolové hry. Představme si třeba známý příklad dvou obchodních řetězců, kde jeden má již na trhu stabilní pozici a druhý teprve uvažuje o vstupu na trh. Pokud by takové rozhodování probíhalo např. v rámci několika měst, jednalo by se o opakovanou hru. Více o této problematice je možné nastudovat na stránce [[Multistage games/cs |Vícekolové hry]]. |
=Příklady k procvičení= | =Příklady k procvičení= | ||
==Příklad 1: Kartel== | ==Příklad 1: Kartel== | ||
| − | Na trhu existují pouze dva podniky daného | + | Na trhu existují pouze dva podniky daného typu. Vědí, že jim zbývají jen 4 dny do doby, než se trh otevře zbylým konkurenčním podnikům. Své ceny mohou stanovit vždy pouze ráno a ceny poté drží celý den. Rozhodnutí o změně cen tedy provedou ještě celkem čtyřikrát. Mohou nastavit dvě úrovně cen: ''"vysoké"'' a ''"nízké"''. |
Jakou strategii podniky zvolí, když matice jejich výplat vypadá následovně (čím vyšší hodnota, tím vyšší výplata pro daný podnik): | Jakou strategii podniky zvolí, když matice jejich výplat vypadá následovně (čím vyšší hodnota, tím vyšší výplata pro daný podnik): | ||
| Line 212: | Line 242: | ||
==Příklad 2: Otevření trhu v nedohlednu== | ==Příklad 2: Otevření trhu v nedohlednu== | ||
| − | Uvažujme totožnou situaci jako v příkladu 1, pouze s tím rozdílem, že podniky neví, kdy k otevření trhu dojde (pouze předpokládají, že k němu dojde). Výplatní matice vypadá následovně (čím vyšší hodnota, tím vyšší výplata pro daný podnik): | + | Uvažujme totožnou situaci jako v [[#Příklad 1: Kartel |příkladu 1]], pouze s tím rozdílem, že podniky neví, kdy k otevření trhu dojde (pouze předpokládají, že k němu dojde). Výplatní matice vypadá následovně (čím vyšší hodnota, tím vyšší výplata pro daný podnik): |
{| class="wikitable" | {| class="wikitable" | ||
| Line 227: | Line 257: | ||
|} | |} | ||
| − | Mějme P jako pravděpodobnost, že | + | Mějme <math>P</math> jako pravděpodobnost, že hra se bude opakovat i následující den (nedojde tedy k otevření trhu). Oba podniky jsou vyznavači [[Grim Trigger strategy/cs |Grim trigger strategií]]. Určete hodnotu <math>P</math> a <math>P^*</math>, kde<math>P>P^*</math>, která povede ke kooperaci obou podniků. |
=Řešení příkladů k procvičení= | =Řešení příkladů k procvičení= | ||
== Řešení příkladu 1: Kartel == | == Řešení příkladu 1: Kartel == | ||
| − | Pro řešení tohoto příkladu využijeme zpětné indukce. V poslední, čtvrtý den je oboum podnikům jasné, že již k dalšímu opakování hry nedojde a druhý podnik je tedy nemůže potrestat za nespolupráci. Nashovo rovnovážné řešení tedy bude {nízké ceny, nízké ceny}. Třetí den si jsou oba podniky vědomi toho, že poslední den zvolí {nízké ceny, nízké ceny}, trest pro ně tedy není hrozbou a proto opět zvolí NE {nízké ceny, nízké ceny}. Druhý den se opakuje to samé co den třetí. Oba podniky vědí, že další den zvolí strategii nizkých cen, a proto zvolí i druhý den tu samou strategii. Stejně tak první den, kdy oba podniky volí NE {nízké ceny, nízké ceny}. | + | Pro řešení tohoto příkladu využijeme zpětné indukce. V poslední, čtvrtý den je oboum podnikům jasné, že již k dalšímu opakování hry nedojde a druhý podnik je tedy nemůže potrestat za nespolupráci. Nashovo rovnovážné řešení tedy bude ''{nízké ceny, nízké ceny}''. Třetí den si jsou oba podniky vědomi toho, že poslední den zvolí ''{nízké ceny, nízké ceny}'', trest pro ně tedy není hrozbou a proto opět zvolí NE ''{nízké ceny, nízké ceny}''. Druhý den se opakuje to samé co den třetí. Oba podniky vědí, že další den zvolí strategii nizkých cen, a proto zvolí i druhý den tu samou strategii. Stejně tak první den, kdy oba podniky volí NE ''{nízké ceny, nízké ceny}''. |
== Řešení příkladu 2: Otevření trhu v nedohlednu== | == Řešení příkladu 2: Otevření trhu v nedohlednu== | ||
| − | Dosazením hodnot z matice do vzorečku z kapitoly | + | Dosazením hodnot z matice do vzorečku z kapitoly [[#Představení konečně opakované hry s neznámým koncem pomocí příkladu |konečně opakované hry s neznámým koncem]] získáme: |
| − | |||
| − | |||
| − | Oba podniky by tedy měly spolupracovat vždy, když dojde ke splnění podmínky: | + | <math>OV_{spoluprace} = \frac{5}{1-5}</math> |
| − | 5 | + | |
| + | <math>OV_{nespoluprace} = 10 + \frac{2P}{1-P}</math> | ||
| + | |||
| + | |||
| + | '''Oba podniky by tedy měly spolupracovat vždy, když dojde ke splnění podmínky:''' | ||
| + | |||
| + | <math>\frac{5}{1-P} > 10 + \frac{2P}{1-P}</math> | ||
neboli | neboli | ||
| − | |||
| − | Pokud tedy P dosahuje hodnoty vyšší než 5/ | + | <math>\frac{5-10}{2-10} < P</math> |
| + | |||
| + | Pokud tedy <math>P</math> dosahuje hodnoty vyšší než <math>\frac{5}{8}</math>, je pro dva podniky dodržující Grim trigger strategii racionálním řešením spolupracovat. Kritická hodnota <math>P^*</math> je tedy <math>\frac{5}{8}</math>. | ||
=Zdroje= | =Zdroje= | ||
| − | + | <references> | |
| − | + | <ref name="gibbons">Gibbons, R. (2006) "A Primer in Game Theory", Financial Times, str. 82-114</ref> | |
| − | + | <ref name="slamova">Skálová, A. (2007) "Opakované hry", diplomová práce, obhájeno na Vysoké škole ekonomické v Praze</ref> | |
| − | + | <ref name="osbornenew">Osborne, M. J. (2004) "An Introduction to Game Theory", Oxford University Press, str. 389-420</ref> | |
| − | + | <ref name="car">Carmichael, F. (2005) "A Guide to Game Theory", Financial Times, str. 197-234</ref> | |
| − | + | <ref name="osborneold">Osborne, M. J., Rubinstein, A. (1998) "A Course in Game Theory", The MIT Press, páté vydání, str. 113-162</ref> | |
| − | + | <ref name="roth">Roth, A. E., Murnigham, J. K. (1978) "Equilibrium behaviour and repeated play of the prisoners’ dilemma", Journal of Mathematical Psychology, str. 189–98</ref> | |
| + | <ref name="kreps">Kreps, D. M., Milgrom, P., Roberts, J. and Wilson, R. (1982) "Rational cooperation in the finitely repeated prisoners’ dilemma", Journal of Economic Theory, 27, pp. 245–52.</ref> | ||
| + | |||
| + | <ref name="Axelrod1980a">Axelrod, R. (1980a), “Effective choice in the Prisoner’s Dilemma”, Journal of Conflict Resolution 24, str. 3–25.</ref> | ||
| + | <ref name="Axelrod1980b">
Axelrod, R. (1980b), "More effective choice in the Prisoner’s Dilemma”, Journal of Conflict Resolution 24, str. 379–403.</ref> | ||
| + | <ref name="Axelrod1984">Axelrod, R. (1984), "The evolution of cooperation". New York: Basic Books.</ref> | ||
| + | |||
| + | <ref name="Trivers">Trivers, R. L. (1971), “The evolution of reciprocal altruism”, Quarterly Reviewof Biology 46, str. 35–57.</ref> | ||
| + | <ref name="Lazarus">Lazarus, J., Metcalfe, N. B. (1990), "Tit-for-tat cooperation in sticklebacks: a critique of Milinski”, Animal Behaviour 39, str. 987–988.</ref> | ||
| + | <ref name="Milinski">Milinski, Manfred (1993), "Cooperation wins and stays”, Nature 364, str. 12–13.</ref> | ||
| + | |||
| + | <ref name="Mason">Mason, C. F., Phillips, O. R., Redington, D. B. (1991) "The role of gender in a non-cooperative game", Journal of Economic Behaviour and Organisation, 15, str. 215–35.</ref> | ||
| + | <ref name="Sabater">Sabater-Grande, G., Georgantzis, N. (2002) "Accounting for risk aversion in repeated prisoners’ dilemma games: An experimental test", Journal of Economic Behaviour and Organization, 48, str. 37–50.</ref> | ||
| + | |||
| + | </references> | ||
Latest revision as of 23:59, 20 June 2012
- typ práce: kapitola učebnice
- autor: Ladislav Dyntar
- předmět: 4IT495 Simulace systémů
Opakované hry jsou součástí mnohem širší problematiky nazývané jako teorie her. Nenechme se ovšem zmýlit - s hraním her mají jen pramálo společného. Pro pochopení opakovaných her je nezbytné osvojit si znalosti her jednorázových (statických).
Contents
Úvod
Opakované hry jsou takové hry, při kterých je jednorázová či vícekolová hra stejnými hráči řešena opakovaně. Tito hráči mají přístup k výsledkům předcházejících her a mají možnost rozvrhnout si své tahy dopředu. Vzniká zde tedy široký prostor pro plánování všemožných strategií, které mohou nejen reagovat na tahy soupeře (učení se), ale hráč má zároveň možnost vytvářet strategie, kterými může svého soka přelstít a maximalizovat tak svou výplatu (užitek). V kapitole se budeme zabývat jevy jako jsou kooperace, výhružky či odplata.
Opakované hry mají tedy mnohem blíže k fungování reálného světa tak, jak ho známe, kde spolu jednotlivé strany často soupeří více než jen jednou. Každá ze stran si je přitom vědoma vlivu svého rozhodnutí na chování svého protihráče.
Plán
Každý hráč musí mít předem stanovený plán hry, který bude jasně definovat, jak se zachová v konkrétních situacích, jež mohou během hry nastat. Tyto strategie se nazývají meta-strategie. Aby byla strategie rovnovážná, musí být nejlepší odpovědí na všechny možné tahy ostatních hráčů ve hře.
Pozorovateli takové hry by mohlo připadat, že hráči v opakované hře v jednotlivých kolech nemaximalizují svůj užitek, tedy že jednají iracionálně. To je důsledkem toho, že maximalizace vlastního užitku v jednom kole nutně nemusí vést k maximalizaci užitku v dlouhodobém horizontu.
Základní dělení
Opakované hry jsou dle délky trvání děleny na hry nekonečné a konečné, přičemž konečně opakované hry dále dělíme na konečné s neznámým koncem a konečné se známým koncem [1]. Pokud je hra opakována nekonečněkrát, hráči se domnívají, že konec hry nenastane a své strategie přizpůsobují této informaci. Pokud je však předem znám počet opakování hry, jedná se o hru konečnou se známým, předem stanoveným koncem. Takovéto hry se pak řeší pomocí zpětné indukce. Mezi těmito dvěma variantami pak leží konečně opakované hry s neznámým koncem, kde si jsou hráči vědomi toho, že hra je konečná, nemají však informaci o tom, kdy doopravdy skončí. Operují tak pouze s pravděpodobností, že hra bude mít ještě další kolo. Konečně opakované hry s neznámým koncem proto řadíme do kategorie nekonečných her.
Konečně opakované hry se známým koncem
Aby byla hráčem zvolená strategie rovnovážnou strategií, musí být nejlepší možnou odpovědí na zvolené strategie druhého hráče v každém opakování hry. Každé jednotlivé opakování hry je přitom podhrou (subgame) celé hry, je tedy zřejmé, že budeme hledat Nashovo rovnovážné řešení podrhy (subgame perfect Nash equilibrium; SPNE) [2]. Protože posledním kolem konečně opakované hry je konkrétní podhra, je možné za cílem nalezení SPNE využít zpětné indukce.
Mnozí z vás se již jistě setkali s takzvaným vězňovo dilematem. Jen krátké přípomenutí: mějme dva od sebe oddělené vězně obviněné ze spáchání společného zločinu. Každý z nich má stejné možnosti volby strategií - přiznat se, tedy nekooperovat (P) a nepřiznat se, tedy kooperovat (N). Jednotlivé výplaty jsou znázorněny v matici níže (čím vyšší číslo, tím větší osobní užitek pro daného vězně).
| Vězeň 1 | |||
|---|---|---|---|
| N | P | ||
| Vězeň 2 | N | 3, 3 | 0, 4 |
| P | 4, 0 | 1, 1 | |
Jak už jistě víte, Nashovým rovnovážným řešením statického jednokolového vězňova dilematu je {P,P} (pokud vám není jasné, jak jsme na toto přišli, doporučuji vrátit se zpět k problematice Nashovi rovnováhy). V konečně opakované verzi této hry nás zpětná indukce zavede ke stejnému výsledku, tedy že strategie {P,P} bude strategií obou hráčů ve všech kolech konečně opakované hry. Toto na první pohled nelogické řešení je často nazýváno paradoxem zpětné indukce.
Důkaz zpětné indukce
Ve statické verzi vězňova dilematu je strategie {P,P} (ve skutečnosti se jedná o vektor strategií jednotlivých hráčů, kde první "P" znázorňuje volbu prvního hráče a druhé "P" druhého hráče, pro snažší pochopení budeme vektor takovýchto strategií nazývat souhrně "strategií [hry]") dominantní strategií, kooperace není Nashovým rovnovážným řešením (NE). U konečně opakovaných her můžeme k vyřešení vězňova dilematu použít zpětné indukce. Ta se nejprve pokusí určit, jak se hráči zachovájí v posledním kole a následně postupuje vždy o jeden krok zpět až na úplný začátek hry.
Předpokládejme, že hra má 10 opakování. Při aplikaci zpětné indukce se tedy nejprve přeneseme do desáté hry, která pro oba hráče vypadá jako hra statická. Proč? Protože oba vědí, že další hra nebude už následovat, tím pádem není možné potrestat druhého hráče za to, že nebude kooperovat. Jejich cílem je tedy nalézt NE a to zahrát, zvolí tedy {P,P}. V předposlední fázi hry, tedy v devátém kole, oba hráči vědí, že v posledním desátém kole zahrají {P,P} a proto nemají důvod ani nyní kooperovat, tedy zahrát {N,N}. Budou tedy opět volit strategii {P,P}. To samé platí i pro osmé kolo, kdy oba hráči ze stejných důvodů opět zahrají {P,P}. Tento proces se opakuje až do prvního kola, kdy hráči vědí, že všechna následující kola zahrají {P,P} a budou tedy i v prvním kole volit strategii {P,P}. SPNE všech kol opakované hry je tedy přiznání obou hráčů k trestnému činu.
Výplata konečně opakovaných her
Výplata pro hry s konečným opakováním je vypočítána jako součet všech dosažených výplat v jednotlivých kolech. V případě desetikolového vězňova dilematu z matice výše by celková výplata obou hráču byla 10 krát 1, tedy 10.
Nekonečně opakované hry a konečně opakované hry s neznámým koncem
Paradox zpětné indukce lze eliminovat zavedením nejistoty ohledně užitku některého z hráču, jeho racionality nebo ohledně samotného konce opakované hry. Teorii budeme ilustrovat právě na případu posledně zmíněného, tedy nejasného konce hry.
Tento stav předpokládá, že ani jeden z hráčů přesně neví, kdy hra skončí (ačkoliv se její konec očekává) nebo věří, že hra neskončí nikdy. Tento výchozí stav vede k tomu, že kooperace, tedy vektor strategií {N,N} se najednou stává rovnovážným řešením obou hráčů. Jak už asi správně hádáte, nebude to tak jednoduché, jak se na první pohled zdá. Problém nyní nastává s tím, že neexistuje pouze jediné rovnovážné řešení, ale rovnovážných řešení je více. Tento jev je nazýván jako "folk theorem" [3].
"První tzv. "folk teorém" tvrdí, že jakýkoliv dosažitelný individuálně racionální výplatní vektor může být Nashovou rovnováhou opakované hry. Druhý "folk teorém" říká, že dosažitelný výplatní vektor, který Paretovsky dominuje jakýkoliv výplatní vektor statické rovnováhy jednorázové hry, může být SPE opakované hry." [2]
Jelikož pro určení rovnovážného řešení hry nyní nemůžeme využít zpětné indukce, hráči se místo dozadu dívají dopředu a pro každou možnou strategii určují její celkovou výplatu. Díky tomu je do jednotlivých strategií hráčů nyní možné zakomponovat i takové prvky jako jsou odměny, výhružky či odplaty.
Strategie
Podívejme se opět na matici Vězňova dilematu z předešlé sekce. I u takto jednoduchého problému je v případě her specifikovaných v [[#Konečně opakované hry se známým koncem |této kapitole] možné volit z téměř nekonečného množství možných meta-strategií. Ty nejznámější si nyní vyjmenujeme [2] a později si jednu i podrobněji popíšeme:
- Vždy podvádět (Always Defect)
- Vždy spolupracovat (Always Cooperate)
- Naivní Grim Trigger
- Grim Trigger
- Oko za ok, zub za zub (Tit for Tat)
- Omezená odplata (Limited Retaliation)
- Strategie Win-Stay, Lose-Shift (WS-LS)
- Jednou se odchýlit (Deviate Once)
- Grim Deviate Once
Představení konečně opakované hry s neznámým koncem pomocí příkladu
Mějme dva vězně - Petra a Martina - kteří jsou oba zastánci Grim Trigger strategie a jsou postaveni před opakovanou hru vězňova dilematu. Grim Trigger strategie je taková strategie, kdy hráč v prvním kole kooperuje a pokračuje v kooperaci až do té doby, dokud všichni hráči v předešlém kole kooperovali. Jakmile některý z hráčů přestane kooperovat, ten druhý automaticky také přestane kooperovat a takto pokračují dále bez jakékoliv další změny. Nyní je tedy i jasné, proč se tato strategie nazývá nepromíjející strategií - přísně trestá jakýkoliv prohřešek druhého hráče.
Nyní se skrze analýzu výplat obou hráčů pokusíme odpovědět na otázku, zda Grim Trigger strategie skutečně vede ke vzájemné spolupráci.
| Petr | |||
|---|---|---|---|
| N | P | ||
| Martin | N | 3, 3 | 0, 4 |
| P | 4, 0 | 1, 1 | |
Nejprve se na hru podíváme z pohledu Petra. Jaká by měla být jeho volba, pokud věří, že Martin dodržuje strategii Grim Trigger? Pokud bude kooperovat, jeho očekávaná výplata bude 3 a další 3 získá za každé další odehrané kolo. Nyní mějme fixní pravděpodobnost Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P \in (0, 1)} , která nám říká, s jakou pravděpodobností hra bude pokračovat i druhým kolem. Poté pravděpodobnost, že hra bude pokračovat třetím je Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P^2} , čtvrtým Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P^3} atd. Petrova očekávaná výplata ze spolupráce (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle OV_{spoluprace}} ) s Martinem je tedy:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle OV_{spoluprace} = 3 + 3P + 3P^2 + 3P^3 + 3P^4 + ... 3P^n = \sum_{n=0}^{n = \infty} 3P^n = \frac{3}{1 - P} }
Pokud však Petr odmítne spolupracovat a vědomě (či vinou chyby) poruší kooperaci, získá jednorázovou výplatu v hodnotě 4 a poté již samé 1. Petrova očekávaná výplata z porušení spolupráce (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle OV_{nespoluprace}} ) s Martinem hned po prvním kole je tedy:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle OV_{nespoluprace} = 4 + P + P^2 + P^3 + P^4 + ... P^n = 4 + \sum_{n=0}^{n = \infty} P^n = 4 + \frac{P}{1 - P} }
Z výše uvedeného jasně vyplývá, že má-li se Petr držet spolupráce, musí pro něj být výhodnější než její porušení. V našem případě musí být konkrétně Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P} , tedy pravděpodobnost dalšího pokračování hry, vyšši než Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{1}{3}} . Postup výpočtu je uveden níže:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{3}{1-P} > 4 + \frac{1P}{1-P}}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 3 > 4(1-P) + 1P}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 3 - 4 > P(1-4)}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{1}{3} < P }
Abychom byli schopni toto aplikovat na jakýkoliv příklad, vytvořili jsme následující obecnou matici:
| Hráč 1 | |||
|---|---|---|---|
| spolupracovat | nespolupracovat | ||
| Hráč 2 | spolupracovat | a, a | b, c |
| nespolupracovat | c, b | d, d | |
přičemž platí, že Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c > a > d > b}
Pravděpodobnost, že hra bude pokračovat i dalším kolem je stále Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P} . Oba hráči se i nadále drží strategie Grim trigger. Pokud oba hráči kooperují, mohou až do konce hry očekávat výplatu v podobě "a". Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle OV_{spoluprace}} je tedy:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle OV_{spoluprace} = a + aP + aP^2 + aP^3 + aP^4 + ... aP^n = \sum_{n=0}^{n = \infty} aP^n = \frac{a}{1 - P} }
Pokud kdokoliv z hráčů přestane spolupracovat, získá jednorázový zisk ve výši "c" a dále už jen "d". Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle OV_{nespoluprace}} je tedy:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle OV_{nespoluprace} = c + dP + dP^2 + dP^3 + dP^4 + ... dP^n = c + \sum_{n=0}^{n = \infty} dP^n = c + \frac{dP}{1 - P} }
Jestliže mají oba hráči spolupracovat, je nutné, aby Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle OV_{spoluprace}} bylo vyšší než Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle OV_{nespoluprace}} , tedy:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{a}{1-P} & > c + \frac{dP}{1-P} \\ \\ a & > c(1-P) + dP = c - cP + dP \\ \\ a - c & > P(d-c) \\ }
A protože víme, že Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a - c < 0 } a že Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle d - c < 0} , můžeme rovnici zjednodušit na:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{a-c}{d-c} < P }
Tato podmínka je platná pro všechny hry vězňova dilematu. [4]
Nyní můžeme stanovit hraniční hodnotu Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P^*} , u které platí, že je-li Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P >\frac{a-c}{d-c} = P^*} , nemá ani jeden z hráčů potřebu odchýlit se od spolupráce a ke spolupráci tak dojde ve všech opakováních hry [4]. Můžeme tedy říci, že pokud je hodnota Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P} dostatečně vysoká, existuje ve vězňově dilematu takové SPNE, které vede u Grim Trigger strategie ke spolupráci.
Nekonečně opakované hry
V případě nekonečně opakovaných her je jasné, že, jak už z názvu vyplývá, není možné počítat s pravděpodobností Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P} , která nám vsekci výše určovala pravděpodobnost, že se hra dostane do dalšího kola. Hráči totiž vždy věří, že hra bude pokračovat.
Aby však mohli plánovat své budoucí výplaty, musí začít uvažovat diskontovanou současnou hodnotu budoucích výplat. Současná hodnota budoucí výplaty "X" získané za "n" období se spočítá jako jako Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{X}{(1+r)^n}} , přičemž "r" označuje úrokovou míru a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{1}{1+r}} je diskontní faktor. Každý si nyní jistě vzpomíná na hodiny ekonomie, kde nám bylo do hlavy vtloukáno, že hodnota peněz získaných nyní je vyšší než hodnota toho samého objemu peněz získaných v budoucnu. A nyní toto pravidlo aplikujeme i u teorie her.
Očekávaný výnos ze spolupráce vypočítáme jako:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle OV_{spoluprace} = a + a\frac{1}{1-r} + a\frac{1}{(1-r)^2} + a\frac{1}{(1-r)^3} + a\frac{1}{(1-r)^4} + ... a\frac{1}{(1-r)^N} ...}
Nahrazením \frac{1}{1-r} diskontním faktorem Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F}
získáme:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle OV_{spoluprace} = a + aF + aF^2 + aF^3 + aF^4 + ... aF^N = \sum_{n=0}^{n = \infty} aF^n = \frac{a}{1 - F} }
Při porušení spolupráce získáváme obdobné:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle OV_{spoluprace} = c + d\frac{1}{1-r} + d\frac{1}{(1-r)^2} + d\frac{1}{(1-r)^3} + d\frac{1}{(1-r)^4} + ... d\frac{1}{(1-r)^N} ...}
Nahrazením \frac{1}{1-r} diskontním faktorem Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F}
poté získáme:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle OV_{spoluprace} = c + dF + dF^2 + dF^3 + dF^4 + ... dF^N = \sum_{n=0}^{n = \infty} dF^n = c + \frac{dF}{1 - F} }
Je tedy zřejmé, že jediný rozdíl mezi nekonečně opakovanými hrami a hrami s konečným opakováním s neznámým koncem je záměna pravděpodobnosti dalšího pokračování hry, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P}
, s diskontním faktorem Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F}
, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F \in (0,1)}
.
O tom, zda pokračovat ve spolupráci nebo se od ní odchýlit pak tedy opět rozhoduje výsledná výplata obou možnosti, neboli:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{a}{1 - F} > c + \frac{dF}{1 - F} }
Což můžeme zjednodušit na:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{a - c}{d - c} < F }
Pokud je tedy Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F}
dostatečně vysoké (budoucí hodnota peněz se nule blíží jen velice pomalu), mají oba hráči zájem na tom spolupracovat. Můžeme tedy opět říci, že v takovém případě existuje ve vězňově dilematu takové SPNE, které vede u Grim Trigger strategie ke spolupráci.
Z výše zmíněného vyplývá, že "spolupracovat" je nejlepší odpovědí na strategii "spolupracovat" druhé hráče. Jak je to však s výhružkou Grim trigger strategie, která říká, že jakmile druhý hráč přestane kooperovat, bude ukončena kooperace i ze strany prvního hráče? Je strategie "nespolupracovat" nejlepší odpovědí na strategii "nespolupracovat"? Pokud by tato hrozba nebyla kredibilní, nemohla by Grim trigger strategie vůbec být SPNE.
Pokud je Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P} (či Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F} ) vyšší než požadovaná kritická hodnota, je strategie "nespolupracovat" opravdu nejlepší odpovědí na strategii "nespolupracovat". Ve statických hrách se totiž jedná o Nashovu rovnováhu a u her s nekonečným opakováním (případně u her s konečným opakováním a neznámým koncem) není možné, aby se hráč dodržující Grim trigger strategy záměrně odchýlil od spolupráce, aniž by se jednalo o reakci na předchozí akci (odchýlení od kooperace) jeho protihráče.
Vezměme si výše zmíněný příklad z pohledu Martina. Pokud se Petr bezdůvodně odchýlil od spolupráce, nenásleduje Grim trigger strategii. Martin nemůže očekávat, že Petr bude v dalších kolech opět spolupracovat. Následuje tedy svou vlastní Grim trigger strategii a potrestá Petra trvalým přerušením spolupráce. Pokud by snad Petr udělal chybu, hned v dalším kole se vrátil zpět ke spolupráci a Martin mu tuto chybu odpustil, Petr by zjistil, že Martin nehraje Grim trigger strategii a nic by mu nebránilo v dalším kole opět přerušit spolupráci. Nebo také z jiného pohledu - protože Martin nehraje Grim trigget strategii (Petra nepotrestal), nemůže si Petr být jistý, že Martin v dalším kole sám nepřeruší spolupráci a tak raději rovnou spolupráci v dalším kole opět přeruší.
Jak už bylo napsáno na začátku této kapitoly, Grim trigger strategie není jedinou meta-strategií, která při řešení vězňova dilematu vede ke vzájemné kooperaci obou hráčů v rámci nekonečně nebo konečně opakovaných her s neznámým koncem. Kooperace může být dosaženo například aplikováním strategie "Oko za oko, zub za zub", která nespolupráci trestá nespoluprácí a ke spolupráci se vrací až v moment, kdy se ke spolupráci opět vrátí i trestaný hráč. Podobných kombinací však existuje nespočet [3].
Závěr a odkazy na výzkumy týkající se aplikací teorie her v reálném světě
Z Folk theorému vyplývá, že nekonečně a konečně opakované hry s neznámým koncem mají více rovnovážných řešení a je tedy téměř nemožné určit, k jakým výsledkům takové hry povedou. Jak jsme však ukázali v této kapitole, dá se předpokládat, že u takových her bude alespoň v jejich části dosaženo vzájemné spolupráce. Uvažováním nejistoty ohledně konce opakované hry jsme změnili vhodné strategie a z nich plynoucí výplaty. Hračí u takovýchto her mají větší vůli kooperovat, protože nekooperace již není jediným subgame rovnovážným řešením.
Shrnutí významných prací zabývajících se aplikací teorie opakovaných her v reálném světě představuje Martin J. Osborne ve své knize “An introduction to Game Theory” [5]. Z první části jeho shrnutí vyplává, že mnoho simulací vyhrála strategie “Oko za oko, zub za zub” (Tit-for-tat). Konkrétní zprávy je možné přečíst v: [6][7][8].
S teorií, že zvířata opakovaně čelí problémům svou strukturou podobným vězňově dilematu přišel Robert L. Trivers v roce 1971 [9]. Při pokusu provedeným s rybami (konkrétně koljuškami), pozoroval, že ty také využívají strategie "Tit-for-tat". Výsledky této studie se později pokouší vyvrátit Lazarus a Metcalfe (1990) [10] a Milinski (1993) [11], který tvrdí, že koljušky nenásledují strategii “Oko za oko, zub za zub”, nýbrž strategii zvanou "Pavlov".
Z novějších studií jmenujme např. Mason, Phillips a Redington (1991) [12], kteří zjišťovali, zda mají ženy větší tendenci ke kooperaci než muži; či Sabater, Grande a Georgantiziz (2002) [13], kteří se věnovali vlivu averze k riziku na pravděpodobnost, že daný subjekt bude kooperovat.
Všechny studie mají však jeden velký nedostatek – jsou prováděny v umělém prostředí a pozorované subjekty vědí, že nastane konec simulace (a tedy i simulované hry). A to platí i v případech, kdy subjekty nevěděly, kdy přesně daný konec nastane. To vedlo subjekty k tomu, že předpokládaly, že každá hra je tou poslední [14].
Další studium
Podrobný rozbor jednotlivých strategií
Podrobný rozbor vybraných strategií vyjmenovaných v sekci Strategie provedl Martin J. Osborne ve své knize “An introduction to Game Theory” [5]. Konkrétně se jedná o: “Grim trigger strategies”, “Limited punishment” a “Tit-for-tat”. Zbylé strategie pak méně podrobně rozebírá Alena Skálová ve své diplomové práci na téma “Opakované hry” [2].
Asymetrické informace při řešení vězňova dilematu u her s konečným opakováním
Další řešení zpětné indukce přinesli Kreps, Milgrom, Roberts a Wilson (1982) [15]. Ve své práci provedli analýzu vězňova dilematu s konečným opakováním, avšak s tou změnou, že racionalita a/nebo užitek jednoho z hráčů nebyly známé pro toho druhého. To dává za vznik mnoha zajímavým strategiím, kdy se jeden hráč snaží toho druhého přelstít.
Komplexita rovnovážných strategií
Martin J. Osborne se ve své knize “A Course in Game Theory” [3] zaobírá komplexitou rovnovážných řešení. Rozšiřuje tak skupinu výsledků prezentovaných v rámci Folk theorem. Vychází z toho, že čím složitější je zvolená strategie, tím více je pro hráče nákladná. Požadavkem každého hráče by tak měla být co nejjednodušší strategie.
Obrácená implementace
Ve té samé knize [3] Martin J. Osborne podrobně rozebírá i obrácený postup řešení opakované hry. V první fázi je definován požadovaný soubor výstupů a až poté se hledá hra, která tyto výsledky produkuje.
Vícekolové hry
S teorií opakovaných her úzce souvisí i vícekolové hry. Představme si třeba známý příklad dvou obchodních řetězců, kde jeden má již na trhu stabilní pozici a druhý teprve uvažuje o vstupu na trh. Pokud by takové rozhodování probíhalo např. v rámci několika měst, jednalo by se o opakovanou hru. Více o této problematice je možné nastudovat na stránce Vícekolové hry.
Příklady k procvičení
Příklad 1: Kartel
Na trhu existují pouze dva podniky daného typu. Vědí, že jim zbývají jen 4 dny do doby, než se trh otevře zbylým konkurenčním podnikům. Své ceny mohou stanovit vždy pouze ráno a ceny poté drží celý den. Rozhodnutí o změně cen tedy provedou ještě celkem čtyřikrát. Mohou nastavit dvě úrovně cen: "vysoké" a "nízké".
Jakou strategii podniky zvolí, když matice jejich výplat vypadá následovně (čím vyšší hodnota, tím vyšší výplata pro daný podnik):
| Černý podnik | |||
|---|---|---|---|
| Nízké ceny | Vysoké ceny | ||
| Bílý podnik | Nízké ceny | 2, 2 | 10, 0 |
| Vysoké ceny | 0, 10 | 5, 5 | |
Příklad 2: Otevření trhu v nedohlednu
Uvažujme totožnou situaci jako v příkladu 1, pouze s tím rozdílem, že podniky neví, kdy k otevření trhu dojde (pouze předpokládají, že k němu dojde). Výplatní matice vypadá následovně (čím vyšší hodnota, tím vyšší výplata pro daný podnik):
| Černý podnik | |||
|---|---|---|---|
| Nízké ceny | Vysoké ceny | ||
| Bílý podnik | Nízké ceny | 2, 2 | 10, 0 |
| Vysoké ceny | 0, 10 | 5, 5 | |
Mějme Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P} jako pravděpodobnost, že hra se bude opakovat i následující den (nedojde tedy k otevření trhu). Oba podniky jsou vyznavači Grim trigger strategií. Určete hodnotu Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P} a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P^*} , kdeFailed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P>P^*} , která povede ke kooperaci obou podniků.
Řešení příkladů k procvičení
Řešení příkladu 1: Kartel
Pro řešení tohoto příkladu využijeme zpětné indukce. V poslední, čtvrtý den je oboum podnikům jasné, že již k dalšímu opakování hry nedojde a druhý podnik je tedy nemůže potrestat za nespolupráci. Nashovo rovnovážné řešení tedy bude {nízké ceny, nízké ceny}. Třetí den si jsou oba podniky vědomi toho, že poslední den zvolí {nízké ceny, nízké ceny}, trest pro ně tedy není hrozbou a proto opět zvolí NE {nízké ceny, nízké ceny}. Druhý den se opakuje to samé co den třetí. Oba podniky vědí, že další den zvolí strategii nizkých cen, a proto zvolí i druhý den tu samou strategii. Stejně tak první den, kdy oba podniky volí NE {nízké ceny, nízké ceny}.
Řešení příkladu 2: Otevření trhu v nedohlednu
Dosazením hodnot z matice do vzorečku z kapitoly konečně opakované hry s neznámým koncem získáme:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle OV_{spoluprace} = \frac{5}{1-5}}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle OV_{nespoluprace} = 10 + \frac{2P}{1-P}}
Oba podniky by tedy měly spolupracovat vždy, když dojde ke splnění podmínky:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{5}{1-P} > 10 + \frac{2P}{1-P}}
neboli
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{5-10}{2-10} < P}
Pokud tedy Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P} dosahuje hodnoty vyšší než Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{5}{8}} , je pro dva podniky dodržující Grim trigger strategii racionálním řešením spolupracovat. Kritická hodnota Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P^*} je tedy Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{5}{8}} .
Zdroje
- ↑ Gibbons, R. (2006) "A Primer in Game Theory", Financial Times, str. 82-114
- ↑ 2.0 2.1 2.2 2.3 Skálová, A. (2007) "Opakované hry", diplomová práce, obhájeno na Vysoké škole ekonomické v Praze
- ↑ 3.0 3.1 3.2 3.3 Osborne, M. J., Rubinstein, A. (1998) "A Course in Game Theory", The MIT Press, páté vydání, str. 113-162
- ↑ 4.0 4.1 Carmichael, F. (2005) "A Guide to Game Theory", Financial Times, str. 197-234
- ↑ 5.0 5.1 Osborne, M. J. (2004) "An Introduction to Game Theory", Oxford University Press, str. 389-420
- ↑ Axelrod, R. (1980a), “Effective choice in the Prisoner’s Dilemma”, Journal of Conflict Resolution 24, str. 3–25.
- ↑ Axelrod, R. (1980b), "More effective choice in the Prisoner’s Dilemma”, Journal of Conflict Resolution 24, str. 379–403.
- ↑ Axelrod, R. (1984), "The evolution of cooperation". New York: Basic Books.
- ↑ Trivers, R. L. (1971), “The evolution of reciprocal altruism”, Quarterly Reviewof Biology 46, str. 35–57.
- ↑ Lazarus, J., Metcalfe, N. B. (1990), "Tit-for-tat cooperation in sticklebacks: a critique of Milinski”, Animal Behaviour 39, str. 987–988.
- ↑ Milinski, Manfred (1993), "Cooperation wins and stays”, Nature 364, str. 12–13.
- ↑ Mason, C. F., Phillips, O. R., Redington, D. B. (1991) "The role of gender in a non-cooperative game", Journal of Economic Behaviour and Organisation, 15, str. 215–35.
- ↑ Sabater-Grande, G., Georgantzis, N. (2002) "Accounting for risk aversion in repeated prisoners’ dilemma games: An experimental test", Journal of Economic Behaviour and Organization, 48, str. 37–50.
- ↑ Roth, A. E., Murnigham, J. K. (1978) "Equilibrium behaviour and repeated play of the prisoners’ dilemma", Journal of Mathematical Psychology, str. 189–98
- ↑ Kreps, D. M., Milgrom, P., Roberts, J. and Wilson, R. (1982) "Rational cooperation in the finitely repeated prisoners’ dilemma", Journal of Economic Theory, 27, pp. 245–52.
