Opakované hry

• 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).

Ú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 . 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) . 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ě).

Tabulka 1

		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" .

"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."

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 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.

Tabulka 2

		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:

Tabulka 3

		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.

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 . 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 .

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” . 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: .

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 . 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) a Milinski (1993) , 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) , kteří zjišťovali, zda mají ženy větší tendenci ke kooperaci než muži; či Sabater, Grande a Georgantiziz (2002) , 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í .

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” . 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” .

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) . 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” 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 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):

Tabulka 4 - příklad 1

		Č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):

Tabulka 5 - příklad 2

		Č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}} .