Opakovaná hra

V teorii her je každá situace, ve které se musíme rozhodnout, označována za hru. Posloupnost takovýchto her je potom nazývána opakovanou hrou. Opakované hry většinou vychází z nějakých dobře známých statických her, jako například „vězňovo dilema“, a většinou se také jedná o hry dvou hráčů.

Opakované hry se skládají z jednotlivých kol a tato kola znázorňují rozhodnutí hráčů. V každém kole hráči volí strategii simultánně a jejich strategie je ovlivněna předchozími rozhodnutími. Z krátkodobého hlediska se může zdát, že hráči jednají iracionálně, jelikož se nesnaží v jednotlivých kolech maximalizovat svůj užitek. Z dlouhodobého hlediska (když je stejná hra hrána opakovaně stejnými hráči) však můžeme vidět, že sledování pouze svých zájmů nemusí vždy být ta nejlepší strategie. V opakovaných hrách totiž minulá rozhodnutí hráče mohou výrazně ovlivnit rozhodnutí ostatních hráčů v dalších kolech a objevují se tak termíny jako například spolupráce či odplata.

Definice opakované hry

Uvažujme hru G a množinu hráčů $I=\{1,...,n\}$. Každý hráč i má neprázdný konečný prostor akcí $A_{i}$. Prostor profilů akcí $A$ je kartézským součinem $A_{i}$. Každý hráč má užitkovou funkci $g_{i}$, definovanou jednotlivými výstupy hry $G$. Nechť hra $G$ je hrána opakovaně (konečně nebo nekonečně mnohokrát) a přinese každému hráči výplatu, která je sumou jednotlivých výplat, které hráč obdrží ve všech kolech hry $G$. Potom posloupnost těchto her je nazvána opakovanou hrou, nebo superhrou $G*$.

(Výnosy mezi jednotlivými koly mohou být agregovány různými metodami: Např. sčítáním, nebo průměrováním výnosů jednotlivých kol, sčítáním současné hodnoty výnosů nebo jejich průměrováním)

Ačkoliv v opakovaných hrách jsou jednotlivé akce hráčů jsou ovlivněny předchozími rozhodnutími, prostředí opakovaných her je na historii a čase nezávislé a tedy stacionární. To vyplývá z předpokladů, že:

• Pro každého hráče je v každém kole k dispozici stejná množina akcí, nezávisle na tom, které kolo hry se právě hraje a nezávisle na tom, jaké akce proběhly v minulosti
• Výplaty jednotlivých hráčů v každém kole hry závisí pouze na profilu akcí daného kola a nezávisí na tom, které kolo hry je právě hráno.

V teorii her můžeme opakované hry rozdělit na hry s úplnou informací a hry s neúplnou informací. Opakované hry s úplnou informací můžeme nadále dělit na konečně opakované hry a nekonečně opakované hry. O konečně opakované hry se jedná v případě, že počet opakování $T<\infty$. Pokud $T=\infty$ mluvíme naopak o nekonečně opakovaných hrách.

Konečně opakované hry

Konečně opakované hry můžeme rozdělit do dvou kategorií. Konečně opakované hry, ve kterých známe počet opakování a konečně opakované hry, ve kterých neznáme počet opakování. Jednotlivá kola opakovaných her značíme $t$, kdy první kolo hry je značeno jako $t=0$. Poslední kolo hry je poté značeno jako $T$ a celkový počet kol je tedy $T+1$. Specifickým rysem konečně opakovaných her, ve kterých známe počet kol je ten, že v posledním kole hry hráči ustupují od společensky optimální strategie a chovají stejně racionálně jako při neopakovaných hrách. Tedy upřednostňují svůj „sobecký“ zájem a maximalizují svůj užitek v daném kole. Je to dáno tím, že nenastanou již žádná další kola hry a tedy odpadá hrozba odplaty ze strany ostatních hráčů.

U konečně opakovaných her s neznámým počtem opakování se hráči chovají stejně, jako při nekonečně opakovaných hrách.

Akce a historie opakovaných her

Zatímco v klasických neopakovaných hrách je zvykem volbu konkrétní akce hráče (například spolupracovat či podvádět) označovat za strategii v opakovaných hrách musíme pojmy strategie a akce rozlišovat. Akce je tedy konkrétní volba i-tého hráče v kole $t$ a je značena jako $a_{i}^{t}$. Profil akcí $a^{t}=(a_{1}^{t},a_{2}^{t},...,a_{n}^{t})$ je potom n-tice akcí jednotlivých hráčů v kole t opakované hry $G*$.

Dále se v opakovaných hrách pracuje s pojmem historie, který značí popis volby akcí všech hráčů v předchozích kolech hry. Historii v čase t potom definujeme jako $h^{t}=(a^{0},a^{1},...,a^{t-1})$ a historii celé hry definujeme $h^{T+1}=(a^{0},a^{1},...,a^{T})$.

Důležitým předpokladem v opakovaných hrách je ten, že hráči před každým kolem hry navzájem znají akce, které provedli ostatní hráči v předchozích kolech hry.

Strategie opakovaných her

Strategii hráče $i$ značíme jako $s_{i}$ a můžeme ji popsat jako volbu akcí v jednotlivých kolech hry $S_{i}=(s_{i}^{0},s_{i}^{1},...,s_{i}^{T})$.Profil strategií v kole $t$ je potom $S^{t}=(s_{1}^{t},s_{2}^{t},...,s_{n}^{t})$. Strategii hráče $i$ v kole hry $t$ zapisujeme jako funkci $s_{i}^{t}$, kde $a_{i}^{t}=s_{i}^{t}(h^{t})$. Tak jsme si objasnili vztah akce, historie a strategie.

K tomu, abychom mohli specifikovat strategii pro opakované hry, je zapotřebí definovat jednotlivé akce hráčů pro každé kolo hry, a pro jejich veškeré možné historické akce. V případě nekonečně opakovaných her to však máme nekonečně mnoho možných kol i jejich historií a proto to není jednoduchý úkol. Níže jsou uvedeny některé příklady strategií tak, jak je uvádí Slantchev (viz Zdroje).

Always defect (vždy podvádět)

Tato strategie předepisuje hráči podvádět při jakékoliv historii hry a nezávisle na tom, co udělali ostatní hráči.

Always cooperate (vždy spolupracovat)

Tato strategie předepisuje hráči spolupracovat při jakékoliv historii hry a nezávisle na tom, co udělali ostatní hráči.

Naive Grim Trigger

Tato strategie předepisuje hráči spolupracovat v případě, že ostatní hráči také spolupracují. V případě, že ostatní hráči přestanou spolupracovat (i když se to stane pouze jednou), od té doby předepisuje tato strategie hráči stále podvádět. Strategie Naive Grim Trigger tak je velice „tvrdá“, jelikož po jakémkoliv selhání trestá už napořád.

Grim Trigger

Tato strategie je ještě tvrdší, než strategie předchozí, jelikož kromě soupeřových selhání trestá zároveň i selhání vlastní. To znamená, vždy když v předchozím kole jakýkoliv hráč podváděl. Strategie Grim Trigger tedy předepisuje spolupracovat v prvním kole a poté spolupracovat do té doby, dokud všichni hráči v minulém kole spolupracovali. V jiných případech předepisuje podvádět.

Tit-for-Tat (Půjčka za oplátku)

Tato strategie předepisuje spolupracovat v prvním kole a poté hrát stejně tak, jako hrál druhý hráč v předchozím kole. To znamená podvádět, pokud druhý hráč v předchozím kole podváděl a spolupracovat, pokud druhý hráč v předchozím kole také spolupracoval. Toto je nejpřívětivější strategie, jelikož obnovuje spolupráci ihned po tom, co druhý hráč začne také spolupracovat.

Limited Retaliation / Forgiving Trigger (omezená odplata)

Tato strategie předepisuje spolupracovat v prvním kole hry a následně $K$ kol podvádět za každý podvod všech hráčů. Po tomto následuje návrat ke spolupráci bez ohledu na to, co se dělo ve fázi trestu.

Fáze 1: Spolupracuj a přepni do fáze 2

Fáze 2: Spolupracuj tak dlouho, dokud někdo z hráčů nezačne podvádět v předchozím kole. Pokud se tak stane, přepni do fáze 3 a nastav $T=0$

Fáze 3: jestliže $T\leq k$ nastav $T=T+1$ a podváděj, v opačném případě přepni do fáze 1.

Win-Stay, Lose-Shift

Tato strategie předepisuje spolupráci v prvním kole a poté spolupracovat po všech historiích, kde poslední výsledek byl buď spolupráce-spolupráce, nebo podvod-podvod. V opačném případě hráč bude podvádět. Název Win-Stay, Lose-Shift značí, že v případě, kdy výsledek poslední hry byl pro hráče relativně dobrý (Win) má zůstat u stejné akce. V případě, že výsledek poslední hry byl relativně špatný (Lose), má naopak akci změnit.

Deviate Once

Tato strategie předepisuje použít strategii Tit for Tat do kola $L$, a poté podvádět v kole $L$. Dále spolupracovat v kole $L+1$ a poté opět hrát strategii Tit for Tat, tentokráte až do konce.

Grim DEVIL

Tato strategie předepisuje použít strategii Grim Trigger do kola $L$ a poté podvádět v kole $L$ a v každém dalším kole.

Výplatní funkce

Jak již bylo řečeno dříve, výplatní funkce u konečně opakovaných her může být agregována například jako součet či průměr výplat v jednotlivých kolech hry. Pro nekonečně opakované hry zavádíme pojem diskontní faktor $\delta \in (0,1)$, který můžeme chápat například jako míru netrpělivosti jednotlivých hráčů. Diskontní faktor se může lišit jak mezi jednotlivými hráči, tak i pro jednoho hráče v rozdílných časech (kolech) hry.

Uvažujme nějaký profil strategií s v čase hry $t$, $s^{t}(h^{t})$ a užitkovou funkci hráče $i$, $g_{i}(s^{t}(h^{t}))$. Výplatní funkci hráče $i$ pro opakovanou hru poté definujeme jako $u_{i}(s)=\sum _{t=0}^{T}\delta ^{t}g_{i}(s^{t}(h^{t}))$. Můžeme si všimnout, že užitková funkce $g_{i}$ není závislá na čase ,což je dáno tím, že prostředí opakovaných her je stacionární.

Nashova rovnováha v opakovaných hrách

„Profil strategií s opakované hry (v pojetí $s_{i}=(s_{i}^{0},s_{i}^{2},...,s_{i}^{t})$) je Nashovou rovnováhou, jestliže $s_{i}$ je nejlepší odezvou hráče $i$ vůči chování oponentů, za předpokladu, že ostatní hráči se drží svých strategií v s ." (citace SKÁLOVÁ).

Literatura

• RATLIFF J., Repeated Games, 1996, [on-line] http://virtualperfection.com/gametheory/5.1.RepeatedGamesIntro.1.0.pdf
• SKÁLOVÁ A., Opakované hry, Diplomová práce, 2007, VŠE Praha fakulta informatiky a statistiky
• SLANTCHEV B., Game Theory: Repeated Games, 2004 [on-line] http://slantchev.ucsd.edu/courses/gt/07-repeated-games.pdf Archivováno 30. 6. 2010 na Wayback Machine.