Bayesovská hra

Bayesovské hry jsou takové modely teorie her, které nemají omezení předpokladu kompletní informace, tedy nevyžadují úplnou znalost pravidel všemi hráči. Poprvé byly definovány v práci Johna C. Harsanyi.^[1][2][3]

Teorie her z uvedení Bayesovských her silně profitovala, protože ve většině reálných situací hráči nemají kompletní informace o situaci, ve které se nacházejí, ať už se to týká charakteristik ostatních hráčů, informacích o výsledcích her anebo vlastních alternativ v určitém bodě hry. Asymetrie informací je běžným aspektem, který se pomocí běžných konceptů teorie her také nedá simulovat.

Podrobněji

Bayesovský přístup k modelování neurčitosti spočívá v přiřazení subjektivního pravděpodobnostního rozdělení pro charakteristiky, které hráči nejsou s určitostí známé. Každý hráč si takto vytvoří určitý předpoklad o charakteristikách ostatních hráčů. Předpoklady ostatních hráčů o konkrétním hráči jsou mu též neznámé, jinými slovy neví, co vědí hráči ostatní. Vzhledem k tomu, že předpoklady ostatních hráčů představují důležitou informaci, která ovlivňuje chování hráče, musí hráč vytvořit očekávání o očekáváních ostatních hráčů. Chování hráče však není ovlivnitelné pouze očekáváními o charakteristikách ostatních hráčů, očekáváním o očekáváních ostatních hráčů, ale i tím, jaká jsou očekávání o očekáváních o očekáváních ostatních hráčů. Takovýto způsob analýzy by vedl k nekonečné řadě pravděpodobnostních rozdělení a z toho výplývajícím rozsáhlým a komplikovaným modelům.

^[1] Harsanyi jako první představil návrh transformovat hru s nekompletními informacemi na hru s informacemi kompletními, ale nedokonalými. V Bayesovských hrách je neurčitost o určité charakteristice modelována jako její pravděpodobnostní rozdělení. Neurčitost o charakteristikách ostatních hráčů je v Bayesovských hrách vyjádřená pomocí neurčitosti o užitkových funkcích ostatních hráčů. Celkové soukromé informace o charakteristikách hráče ovlivňují jeho užitek a určují jeho typ. V instanci hry pozná každý hráč svůj vlastní typ, ale nepozná typy ostatních hráčů. Společné pravděpodobnostní rozdělení, podle kterého jsou na začátku hry hráčům přiřazené jejich typy, je v Bayesovské hře informací veřejnou. Jestliže o konkrétních typech, které byly přiřazeny hráčům náhodnými tahy na začátku hry, nemají hráči informace, jedná se o typ hry s nedokonalými informacemi. Pravidla pro Bayesovské hry se mírně odlišují od všeobecné definice her:

Bayesovská hra je složena z následujících elementů^[1]:

• množina hráčů ${\displaystyle N=\{1,...,n\}\,\!}$
• akční prostor ${\displaystyle A=A_{1}\times ...\times A_{n}\,\!}$, kde ${\displaystyle A_{i}\,\!}$ představuje množinu akcí hráče ${\displaystyle i\,\!}$ pro ${\displaystyle i\in N}$
• prostor typy ${\displaystyle T=T_{1}\times ...\times T_{n}\,\!}$, kde ${\displaystyle T_{i}\,\!}$ je množina typů hráče ${\displaystyle i\,\!}$ pro ${\displaystyle i\in N}$
• pravděpodobnostní rozdělení typů ${\displaystyle P\in \Delta (T)}$. Konkrétní typ hráče ${\displaystyle T_{i}\,\!}$ bude označovaný jako ${\displaystyle t_{i}\in T_{i}}$
• užitková funkce ${\displaystyle u_{i}(a,t)\,\!}$, která každé uspořádané dvojici ${\displaystyle (a,t)\in A\times T}$ přiřadí hodnotu z ${\displaystyle \mathbb {R} }$ pro ${\displaystyle i\in N}$

Bayesovská hra je v této podobě rozšířením hry v strategickém tvaru o typy hráčů, rozdělení těchto typů a vyžaduje si i upravení užitkové funkce. Pouze poznamenejme, že odvození Bayesovské hry v extenzivní formě je obdobné.

Strategie představuje vyčerpávající akční plán. V Bayesovských hrách musí tedy každý hráč připravit svojí akci v závislosti na typu, který mu bude v konkrétní instanci hry známý. Strategií se proto v Bayesovských hrách myslí systém uspořádaných dvojic ${\displaystyle (a_{i},t_{i})\,\!}$ pro ${\displaystyle \forall t_{i}\in T_{i}}$, anebo jinak funkcí z prostoru typů do prostoru akcí ${\displaystyle a_{i}=s_{i}(t_{i})\,\!}$.^[4] Důsledkem toho je, že se hráč může chovat v případě různých typů různě. Poněvadž hráč zná svůj vlastní typ ještě předtím, než vykoná svoje rozhodnutí, může se zdát určení akcí pro každý typ zvlášť redundantní. Ale typ určitého hráče není s určitostí znám ostatním hráčům. Proto jsou jejich rozhodnutí závislé na očekávání, jak se bude daný hráč chovat ve všech typech a i na pravděpodobnostním rozdělení těchto typů.

Smíšená strategie hráče ${\displaystyle i\,\!}$ pro Bayesovské hry představuje funkci z prostoru typů ${\displaystyle T_{i}\,\!}$ do pravděpodobnostního rozdělení na množině akcí ${\displaystyle \Delta (A_{i})\,\!}$. Pravděpodobnostní rozdělení při strategii ${\displaystyle \sigma _{i}(t_{i})\,\!}$ a pravděpodobnost hraní akce ${\displaystyle a_{i}\,\!}$ hráčem ${\displaystyle i\,\!}$, který má v dané hře typ ${\displaystyle t_{i}\,\!}$ se bude označovat jako ${\displaystyle \sigma _{i}(a_{i}|t_{i})\,\!}$. Strategický prostor Bayesovské hry je označován jako ${\displaystyle \sum }$.

Očekávaný užitek hráče ${\displaystyle i\,\!}$ pro smíšený strategický profil ${\displaystyle \sigma \,\!}$ a daný profil typů ${\displaystyle t\,\!}$ se vypočítá jako:

${\displaystyle v_{i}(\sigma ,t)=\sum _{a\in A}(\prod _{j\in N-i}\sigma _{j}(a_{j}|t_{j}))\times \sigma _{i}(a_{i})\times u_{i}(a,t)}$

Očekávání hráče ohledně typu ostatních hráčů je vytvářené na základě pravděpodobnostního rozdělení ${\displaystyle \Delta (T_{i})_{i\in N}}$ a pravděpodobnost výskytu profilu typů ${\displaystyle t\,\!}$ se vyjadřuje jako ${\displaystyle p(t)=p(t_{1})\times ...\times p(t_{n})}$. Poněvadž toto rozdělení je všem hráčům známé, předpokládá se, že jsou jejich očekávání navzájem konzistentní. Hráč zná svůj vlastní typ a pravděpodobnostní rozdělení všech typů, takže může pomocí Bayesova pravidla určit pravděpodobnost určité uspořádané (n-1)-tice typů ostatních hráčů: ${\displaystyle p(t_{-i}|t_{i})={\frac {p(t)}{\sum _{t_{-i}\in T_{-i}}p(t_{-i},t_{i})}}}$.

Hráči mají informaci o pravděpodobnosti výskytu typů ostatních hráčů, ale před začátkem hry neznají svůj vlastní typ. Jejich apriorní očekávaný užitek v instanci hry, v které se hráči chovají podle strategického profilu ${\displaystyle \sigma \,\!}$, se dá vyjádřit následovně:

${\displaystyle w_{i}(\sigma )=\sum _{t\in T}p(t)\times v_{i}(\sigma ,t)}$

Po zvolení typu hráče může hráč vypočítat svůj aposteriorní očekávaný užitek:

${\displaystyle w_{i}(\sigma |t_{i})=\sum _{t_{-i}\in T_{-i}}pi(t_{-i}|ti)\times v_{i}(\sigma ,t)}$.

Bayesovo-Nashovo ekvilibrium

Tento koncept slouží k řešení Bayesovských statických her. I naproti odlišné struktuře těchto her se základní idea Nashova ekvilibria nemění. Každá strategie v tomto ekvilibriu musí být nejlepší odpovědí hráče na strategii ostatních hráčů. Bayesovo-Nashovo equilibrium ve hře H s neúplnou informací je Nashovo equilibrium ve hře H s nejistou informací, která je reprezentací původní hry H.^[5]

Strategický profil ${\displaystyle \sigma \,\!}$ je Bayesovo-Nashovým ekvilibriem, jestliže platí jedna z dvou podmínek^[2]:

• ${\displaystyle w_{i}(\sigma *)\geq w_{i}(\sigma _{i},\sigma _{-i}^{*})}$                pro ${\displaystyle \forall \sigma \in \sum _{i}\forall i\in N}$
• ${\displaystyle w_{i}(\sigma *|t_{i})\geq w_{i}(\sigma _{i},\sigma _{-i}^{*}|t_{i})}$    pro ${\displaystyle \forall t_{i}\in T_{i}\sum \sigma _{i}\in \sum _{i}\forall i\in N}$

Z definice vyplývá, že Bayesovo-Nashovo ekvilibrium se dá určit dvěma způsoby. Průběh Bayesovké hry je charakteristický výběrem typů jednotlivých hráčů na jejím začátku. Po úvodní sérii pravděpodobnostních tahů je každému hráči přiřazeny jeho typ a hráči hrají dále stejně jako v standardní statické hře. Poněvadž hráči znají svůj vlastní typ, ale neznají typ ostatních hráčů, tak nevědí s určitostí, v které hře se právě nacházejí. Vědí určit pravděpodobnostní rozdělení her na základě jejich přesvědčení vzhledem k typům ostatních hráčů. Bayesovo-Nashovo ekvilibrium představuje takový strategický profil, v kterém žádný z hráčů nemůže dosáhnout lepší očekávaný užitek ani pro jeden ze svých typů. Každá konečná hra s neúplnou informací má alespoň jedno Bayesovo-Nashovo equilibrium.^[5]

Příklad - souboj pohlaví

Bayesovo-Nashovo ekvilibrium si můžeme demonstrovat na známé hře souboj pohlaví. Nejdřív si ukažme standardní situaci (nalevo) řešenou pomocí Nashova equilibria. Manželská dvojice se rozhoduje, jak stráví večer. Má dvě možnosti: jít na hokejový zápas nebo do divadla. Oba manželé preferují společně strávený večer, ovšem ON dává přednost hokeji, zatímco ONA by raději zvolila návštěvu divadla. V tabulce ve tvaru dvoumatice jsou zaznamenány preference manželů v podobě výplat (uspokojení ze zvolené činnosti). U této hry bychom Nashova ekvilibria nalezli dvě (2, 3) a (3, 2) tedy trávit čas společně.

Tabulka "preferuje samotu" ukazuje druhý typ hráče ON. Vyznačuje se stejnou užitkovou funkcí pro hráče ONA, ale ON tu má preference jiné. ON sice stále preferuje hokej před divadlem, nicméně v tomto případě chce jít sám. Hráč ONA nemá informace o tom jaký typ v této hře ON představuje, nicméně má přesvědčení, že ON z 80% preferuje společný večer a z 20% samotu. Tato hra se dá znázornit jako asociovaná hra v strategickém tvaru.^[6]

Zde nalezneme 2 čistá Nashova equilibria a to (1.6, 2.8) a (2.6, 2.2). Ty představují tyto dva stavy:

• pokud jde ON při společenské náladě na hokej a při nespolečenské do divadla je pro hráče ONA racionální jít na hokej
• pokud jde ON při společenské náladě do divadla a při nespolečenské na hokej je pro hráče ONA racionální jít do divadla

Dokonalé Bayesovo ekvilibrium

^[7] Dokonalé Bayesovo ekvilibrium je vylepšením Nashova ekvilibria pro případ dynamických her s nedokonalými informacemi. Dynamické hry jsou hry v extenzivním tvaru. Kvůli tomu, aby se ekvilibrium nemuselo omezovat pouze na sekvenční podmínky v rámci pod-her, byl zaveden pojem přesvědčení. Přesvědčení přiřazuje pravděpodobnost vrcholu v rámci jedné informační množiny, což umožňuje výpočet očekávaného užitku i pro podstromy začínající ve vrcholu patřícímu do více početné informační množiny. Explicitní určení přesvědčení umožňuje ne jen stanovení dodatečných formálních požadavků vylepšující racionalitu ekvilibria, ale i posouzení přípustnosti ekvilibria s ohledem na dodatečné kritérium a jejich opodstatnění v realitě. Strategický profil se dá chápat jako scénář a pravděpodobnost scénáře by měla korespondovat s přesvědčeními zodpovídajícími danému ekvilibriovému profilu.

Hráči mají v každé informační množině ${\displaystyle I\,\!}$ určité přesvědčení o tom, s jakou pravděpodobností se nacházejí ve vrcholu ${\displaystyle x\in I(x)\,\!}$. Přesvědčení je tedy funkce, která přiřazuje každému vrcholu v informační množině číslo z intervalu [0;1]. Přitom platí, že součet pravděpodobností pro vrcholy v jedné informační množině se rovná 1. Pravděpodobnostní rozdělení pro všechny informační množiny vytvářejí systém přesvědčení ${\displaystyle \mu \,\!}$. Přesvědčení jsou explicitně určené jako součást ekvilibria a spolu se takto uspořádaná dvojice složená ze systému přesvědčení a ze strategického profilu bude označovat jako přiřazení ${\displaystyle (\mu ,b)\,\!}$. Sekvenční racionalita, která je základní vlastností tohoto ekvilibria, intuitivně znamená, že každé rozhodnutí musí být součástí ekvilibria pro zbytek hry a to pro začátek z kteréhokoliv vrcholu stromu hry pro dané přesvědčení. Teda i z vrcholů, které leží ve více početných informačních množinách. Formálně se sekvenční racionalita dá vyjádřit následující podmínkou:

${\displaystyle U_{i}((\mu ,b)|I_{i})\geq U_{i}((\mu ,(b_{-i},b'_{i}))|I_{i})}$      pro ${\displaystyle \forall i\in N,\forall I_{i}}$.

Při ekvilibriových strategiích je důležitou vlastností konzistentnost přesvědčení vzhledem na Bayesovu větu. ${\displaystyle P(x|b)\,\!}$ je pravděpodobnost, že vrchol ${\displaystyle x\,\!}$ bude dosáhnutý, pokud se budou hráči chovat podle behaviorálního strategického profilu ${\displaystyle b\,\!}$. Podobně ${\displaystyle p(I(x)|b)\,\!}$ je pravděpodobnost dosáhnutí informační množiny, v které se ${\displaystyle x\,\!}$ nachází, při hraní strategického profilu ${\displaystyle b\,\!}$.

Dokonalé Bayesové ekvilibrium je přiřazení ${\displaystyle (\mu ,b)\,\!}$, které splňuje následující podmínky:

• ${\displaystyle (\mu ,b)\,\!}$ je sekvenčně racionální v každém vrcholu
• přesvědčení ${\displaystyle \mu \,\!}$ jsou konzistentní vzhledem na Bayesovu větu vždy, když je to možné
• strategický profil ${\displaystyle b\,\!}$ je vzhledem na pod-hry dokonalý

Reference