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áčů
- akční prostor , kde představuje množinu akcí hráče pro
- prostor typy , kde je množina typů hráče pro
- pravděpodobnostní rozdělení typů . Konkrétní typ hráče bude označovaný jako
- užitková funkce , která každé uspořádané dvojici přiřadí hodnotu z pro
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 pro , anebo jinak funkcí z prostoru typů do prostoru akcí .[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 pro bayesovské hry představuje funkci z prostoru typů do pravděpodobnostního rozdělení na množině akcí . Pravděpodobnostní rozdělení při strategii a pravděpodobnost hraní akce hráčem , který má v dané hře typ se bude označovat jako . Strategický prostor bayesovské hry je označován jako .
Očekávaný užitek hráče pro smíšený strategický profil a daný profil typů se vypočítá jako:
Očekávání hráče ohledně typu ostatních hráčů je vytvářené na základě pravděpodobnostního rozdělení a pravděpodobnost výskytu profilu typů se vyjadřuje jako . 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áčů: .
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 , se dá vyjádřit následovně:
Po zvolení typu hráče může hráč vypočítat svůj aposteriorní očekávaný užitek:
.
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 je Bayesovo-Nashovým ekvilibriem, jestliže platí jedna z dvou podmínek[2]:
- pro
- pro
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í
ON Hokej | ON Divadlo | |
---|---|---|
ONA Hokej | 2, 3 | 0, 0 |
ONA Divadlo | 1, 1 | 3, 2 |
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ě.
ON Hokej | ON Divadlo | |
---|---|---|
ONA Hokej | 2, 1 | 0, 2 |
ONA Divadlo | 1, 3 | 3, 0 |
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]
ON HokejHokej | ON HokejDivadlo | ON DivadloHokej | ON DivadloDivadlo | |
---|---|---|---|---|
ONA Hokej | 2, 2.6 | 1.6, 2.8 | 0.4, 0.2 | 0, 0.4 |
ONA Divadlo | 1, 1.4 | 1.4, 0.8 | 2.6, 2.2 | 3, 1.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ě určité přesvědčení o tom, s jakou pravděpodobností se nacházejí ve vrcholu . 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í . 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í . 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:
pro .
Při ekvilibriových strategiích je důležitou vlastností konzistentnost přesvědčení vzhledem na Bayesovu větu. je pravděpodobnost, že vrchol bude dosáhnutý, pokud se budou hráči chovat podle behaviorálního strategického profilu . Podobně je pravděpodobnost dosáhnutí informační množiny, v které se nachází, při hraní strategického profilu .
Dokonalé Bayesové ekvilibrium je přiřazení , které splňuje následující podmínky:
- je sekvenčně racionální v každém vrcholu
- přesvědčení jsou konzistentní vzhledem na Bayesovu větu vždy, když je to možné
- strategický profil je vzhledem na pod-hry dokonalý
Reference
- ↑ a b c HARSANYI, John C. Games with incomplete information played by "Bayesian" Players, Part I. The Basic Model. U.S.A: Management Science Vol. 14, No. 3, 1967. (anglicky)
- ↑ a b HARSANYI, John C. Games with incomplete information played by "Bayesian" Players, Part II. Bayesian Equilibrium Points. U.S.A: Management Science Vol. 14, No. 5, 1968. (anglicky)
- ↑ HARSANYI, John C. Games with incomplete information played by "Bayesian" Players, Part III. The Basic probability distribution of the game. U.S.A: Management Science Vol. 14, No. 7, 1968. (anglicky)
- ↑ MYERSON, Roger B. Game Theory: Analysis of Conflict. Cambridge, Massachusetts AND London: England: Harvard University Press, 1991. Dostupné online. (anglicky)
- ↑ a b HYKŠOVÁ, Magdalena. Teorie her & optimální rozhodování - výukový text [online]. [cit. 2009-01-23]. Dostupné v archivu pořízeném dne 2018-10-12.
- ↑ PEKÁR, Ján. Teória nekooperatívnych hier [online]. [cit. 2009-01-23]. Dostupné online. [nedostupný zdroj]
- ↑ GIBBONS, Robert. Game Theory for Applied Economists. Princeton: New Jersey: Princeton Universsity Press, 1992. Dostupné online. (anglicky)