Hra s neúplnými informacemi

Bayesovská hra nebo neúplná informační hra v teorii her je charakterizována neúplnými informacemi o soupeřích ( jejich možných strategiích a přínosech), zatímco hráči mají o této nejistotě přesvědčení . Bayesovská hra může být přeměněna na hru úplných , ale nedokonalých informací, pokud se předpokládá běžná předchozí distribuce. Na rozdíl od neúplných informací, nedokonalé informace zahrnují znalost soupeřových strategií a výplat, ale historie hry (předchozí akce protivníků) není dostupná všem účastníkům.

John Harsanyi popsal Bayesovské hry následovně [1] . Kromě skutečných účastníků hry se objeví i virtuální hráč „ Příroda “. Příroda obdarovává každého ze skutečných účastníků náhodnou proměnnou , jejíž hodnoty se nazývají typy . Rozdělení ( hustota nebo pravděpodobnostní funkce ) typů pro každého z hráčů je známé. Na začátku hry si příroda „vybírá“ typy hráčů. Typ zejména definuje výplatní funkci účastníka. Neúplnost informací v Bayesovské hře je tedy neznalostí alespoň jednoho hráče typu nějakého jiného účastníka. Hráči mají přesvědčení o typech protivníků; víra je rozdělení pravděpodobnosti přes sadu možných typů. Jak hra postupuje, přesvědčení se aktualizují podle Bayesova teorému .

Definice

Hra je definována následovně: , kde $G=\langle N,\Omega ,\langle A_{i},u_{i},T_{i},\tau _{i},p_{i},C_{i}\rangle _{i \in N}\rangle$

$N$ - mnoho hráčů.
$\Omega$ - mnoho přírodních stavů. Příklad přírodního stavu: pořadí balíčku v karetní hře.
$A_{i}$ je soubor akcí hráče . Nechte _ $i$ ${\displaystyle A=A_{1}\times A_{2}\times \dotsb \times A_{N))$
$T_{i}$ je soubor typů hráčů . Typ je určen pravidlem . $i$ ${\displaystyle \tau _{i}\colon \Omega \rightarrow T_{i))$
${\displaystyle C_{i}\subseteq A_{i}\times T_{i))$ definuje dostupné akce pro hráče , který má nějaký typ v . $i$ $T_{i}$
$u_{i}\colon \Omega \times A\rightarrow R$ výplatní funkce hráče . Formálněji, nechte , a . $i$ $L=\{(\omega ,a_{1},\dotsc ,a_{N})\mid \omega \in \Omega ,\forall i,(a_{i},\tau _{i}( \omega ))\in C_{i}\}$ $u_{i}\colon L\rightarrow R$
$p_{i}$ rozdělení pravděpodobnosti na pro každého hráče , to znamená, že každý hráč jinak vyhodnocuje pravděpodobnosti přírodních stavů; během hry ho neznají. $\Omega$ $i$

Čistá strategie musí uspokojit všechny . Strategie každého hráče závisí pouze na jeho typu, protože typy ostatních hráčů jsou pro něj skryté. Očekávaná odměna hráče s tímto strategickým profilem je . ${\displaystyle s_{i}\dvojtečka T_{i}\rightarrow A_{i))$ ${\displaystyle (s_{i}(t_{i}),t_{i})\in C_{i))$ $t_{i}$ $i$ $u_{i}(S)=E_{\omega \sim p_{i}}[u_{i}(\omega ,s_{1}(\tau _{1}(\omega )),\dotsc ,s_{N}(\tau _{N}(\omega )))]$

Nechť je soubor čistých strategií, $S_{i}$ $S_{i}=\{s_{i}\dvojtečka T_{i}\rightarrow A_{i}\mid (s_{i}(t_{i}),t_{i})\in C_{i },\forall t_{i}\}.$

Bayesovská rovnováha hry je definována jako Nashova rovnováha hry (možná ve smíšených strategiích) . Pokud je hra konečná, Bayesovská rovnováha vždy existuje. $G$ ${\hat {G}}=\langle N,{\klobouček {A}}=S_{1}\times S_{2}\times \dotsb \times S_{N},{\klobouček {u} }=u\rangle$ $G$

Příklady

Šerifovo dilema

Šerif čelí podezřelému. Oba se musí současně rozhodnout, zda budou či nebudou střílet.

Podezřelý má dva možné typy: „zločinec“ a „dodržující zákon“. Šerif má jen jeden typ. Podezřelý zná svůj typ, ale šerif ne. Ve hře jsou tedy neúplné informace, patří do Bayesovské třídy. Podle šerifa je s pravděpodobností p podezřelý zločinec, s pravděpodobností 1-p - zákonný občan. Hodnoty p a 1-p jsou oběma hráčům známy, protože se předpokládá společné předchozí rozdělení. Právě to umožňuje přeměnit tuto hru na hru úplných, ale nedokonalých informací.

Šerif raději střílí, pokud podezřelý střílí, a jinak se střelbě vyhýbá (i když je podezřelý skutečně zločinec). Zločinec má sklony střílet (i když šerif nestřílí), zatímco zákonodárný občan se chce konfliktu jakkoli vyhnout (i když šerif střílí). Výplatní matice závisí na typu podezřelého:

Typ = "Dodržování zákonů"		Akce šerifa
Typ = "Dodržování zákonů"		oheň	Nestřílej
Akce podezřelého	oheň	-3, -1	-12
Akce podezřelého	Nestřílej	-2, -1	0, 0

Typ = "zločinec"		Akce šerifa
Typ = "zločinec"		oheň	Nestřílej
Akce podezřelého	oheň	0, 0	2, -2
Akce podezřelého	Nestřílej	-2, -1	-1.1

Pokud mají oba společné znalosti o racionalitě hráčů (hráč 1 je racionální; hráč 1 ví, že hráč 2 je racionální; hráč 1 ví, že hráč 2 ví, že hráč 1 je racionální atd. ad infinitum), bude hra probíhat podle následující scénář rovnováhy (dokonalá Bayesovská rovnováha) [2] [3] :

Když je podezřelý typ, který dodržuje zákony, dominantní strategií je nestřílet, když je kriminálník, dominantní strategií je střílet. Silně dominované strategie mohou být vyloučeny z úvahy. Pokud pak šerif střílí, dostane 0 s pravděpodobností p a -1 s pravděpodobností 1-p. Jeho očekávaná výplata je p-1. Pokud šerif nestřílí, má nárok na -2 s pravděpodobností p a 0 s pravděpodobností 1-p; očekávaná výplata je -2p. Šerif bude střílet vždy, když p-1 > -2p, tedy když p > 1/3.

Viz také

Poznámky

↑ Harsanyi, John C., 1967/1968. "Hry s neúplnými informacemi hrané Bayesianskými hráči, I-III." Management Science 14 (3): 159-183 (část I), 14 (5): 320-334 (část II), 14 (7): 486-502 (část III).
↑ Coursera . _ Coursera . Staženo: 16. června 2016.
↑ Hu, Yuhuang; Čau, Chu Kiong. Zobecněný kvantově inspirovaný model rozhodování pro inteligentního agenta // The Scientific World Journal : deník. - 2014. - 17. března ( roč. 2014 ). - ISSN 1537-744X . - doi : 10.1155/2014/240983 . — PMID 24778580 .

Literatura

Gibbons, Roberte. Teorie her pro aplikované ekonomy (neopr.) . - Princeton University Press , 1992. - S. 144-152.
Levin, Jonathan Games with Incomplete Information (2002). Staženo: 25. srpna 2016. (neurčitý)

Herní teorie
Základní pojmy	Vzájemná a společná znalost Hráč Hierarchie vír Iracionální zesílení strategie ( dominance ) Reverzní indukce
Typy her	Simultánní , sekvenční a opakující se Nekooperativní a kooperativní S úplnými , neúplnými , dokonalými a nedokonalými informacemi V normální i rozšířené podobě Antagonistický Rozdíl Stochastické Bitva pohlaví Lov na jelena
Koncepce řešení	Riziková dominance Korelovaná rovnováha Rovnováha třesoucí se ruky Nashova rovnováha Dokonalá rovnováha podhry Racionalizovatelnost Sekvenční rovnováha silná rovnováha Vlastní bilance Evolučně stabilní strategie Epsilon-rovnováha Paretova účinnost Jádro
Příklady her	Vězňovo dilema Úkol baru "El Farol" Model Bertrand Cournotův model Stackelbergův model Orlyanka Tragédie sdílených zdrojů jestřábi a holubice
Epistemická teorie her Konstrukce mechanismu Spravedlivé rozdělení