Extenzivní hry s nedokonalými informacem Rostislav Staněk
April 8, 2013
Nedokonalé informace
Hráči nevědí, co se stalo ve hře před jejich tahem.
Historie rozdělíme do tzv. informačních množin.
Hráč přitom ví, ve které informační množině se nachází, ale neví, která historie z informační množiny byla realizována.
Rostislav Staněk
Definice hry
• Množina hráčů
• Množina konečných historií
• Hráčská funkce
• Informační rozdělení množiny historií, po níž je hráč na tahu, do informačních množin lj takových, že historie h a h' mohou být ve stejné informační množine jen tehdy, když A(h) = A(h')
• Preference nad množinou konečných historií reprezentované Bernoulliho výplatní funkcí
Rostislav Staněk
Příklad
i
Figure: Vstup do odvětví
Rostislav Staněk
Strategie
Strategie v extenzivní hře s nedokonalými informacemi je funkce, která každé informační množině // přiřadí akci z množiny A(l;) (resp. pravděpodobnostní rozdělení nad množinou A(l;))
Rostislav Staněk
Nashova rovnováha
Nashova rovnováha je situace, kdy pro každého hráče ; a pro každou strategii a; platí E(u(a*,a*_;)) > E{u{a-na*_;))
Způsoby hledání Nashovy jsou podobné jako v případě extenzivní hry s nedokonalými informacemi. Sestavím strategickou formu hry a najdeme Nashovu rovnováhu.
Rostislav Staněk
Přesvědčení
Ve hrách s dokonalými informacemi jsme nemuseli mluvit o přesvědčeních hráčů explicitně (v rovnováze byla dána akcemi ostatních hráčů).
Nyní nemusí být přesvědčení v některých podhrách determinována akcemi ostatních hráčů. Musíme mluvit o přesvědčení hráčů explicitně.
Přesvědčení v extenzivně hře je funkce, která každé informační množině připisuje pravděpodobnostní rozdělení nad historiemi v této množině.
Rostislav Staněk
Behaviorální strategie
Behaviorální strategie je hráče / je funkce, která každé informační množině // připisuje pravděpodobnostní rozdělení nad akcemi A(l;).
Kuhnův teorém: Pro každou smíšenou strategii existuje behaviorální strategie, která generuje stejné pravděpodobnostní rozdělení nad konečnými historiemi (pokud se hra vyznačuje tzv. Perfect recall )
Behaviorální strategie umožňují kratší zápis a jsou lehce porovnatelné s přesvědčením hráčů.
Rostislav Staněk
Rovnováha
Ohodnocení extenzivní hry se skládá z profilu behaviorálních strategií (3 a systému přesvědčení /x. Ohodnocení je rovnováh pokud splňuje dvě podmínky.
• Sekvenční racionalita.
• Konzistence přesvědčení se strategiemi.
Rostislav Staněk
Sekvenční racionalita
Strategie každého hráče je optimální, kdykoliv je hráč na tahu (tj. v každé podhře) při daném přesvědčení hráče a strategiích ostatních hráčů. Tj. 0/;(/3,/i) ^ 0/;((7/,/?-;),/i) pro každou behaviorální strategii 7.
Rostislav Staněk
Konzistence
Pokud rovnovážný profil strategií vede s kladnou pravděpodobností k historii, která spadá do informační množiny /,-, pak přesvědčení hráče ; ohledně pravděpodobnosti výskytu historie h* v této informační množině je
Pr(h* dle strategie /3) J2hei- Pr(h ^e strategie (3)
Rostislav Staněk
Slabá sekvenční rovnováha
WSE splňuje sekvenční racionalitu a konzistenci, ale neklade žádné požadavky na přesvědčení hráčů v informačních množinách, které nejsou dosaženy.
V extenzivních hrách s dokonalými informacemi je každá slabá sekvenční rovnováha zároveň SPE.
Každá slabá sekvenční rovnováha je zároveň Nashovou rovnováhou.
Rostislav Staněk
Příklad
WS E
O Lze použít zpětnou indukci? Po historii (C,F) bude hráno J.
© Předpokládejme, že hráč 1 hraje C s pravděpodobností p a D s pravděpodobností q. Existuje taková WSE?
© Předpokládejme, že hráč 1 hraje na začátku hry akci E. Existuje taková WSE?
Rostislav Staněk