Opakovaná hra

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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)[editovat | editovat zdroj]

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)[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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)[editovat | editovat zdroj]

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)[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

„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Á).

Zdroje[editovat | editovat zdroj]