Extenzivní hry Rostislav Staněk March 6, 2014 Definice Extenzivní hra se tedy skládá z • množiny hráčů • množiny konečných historií • hráčské funkce, která každé sekvenci, která je vlastní podhistorií, připisuje určitého hráče • preferencí definovaných nad množinou konečných historií Konečná historie je sekvence akcí (ai,a„), která se může ve hře objevit a která vede od počátku hry až k jejímu konci. 1 -O0.O Rostislav Staněk Vstup do odvětví Vyzyvatel Vstup Ven Monopolista B/\S 2,1 0,0 Figúre: Hra o vstup do odvetví Rostislav Staněk Strategie Strategie hráče / v extenzivní hře s dokonalými informacemi je funkce, která každé historii h, po níž je hráč na tahu, přiřadí akci množiny A(h), tj. množiny akcí dostupných po historii h. Strategie hráčů determinují výsledek hry, tj. konečnou historii, a tudíž i výplaty hráčů. Konečnou historii, která se objeví při profilu strategií s, označme O(s) Jak vypadají strategie ve hře Vstup do odvětví? Rostislav Staněk < □ ► < flP ► 4 -E t 4 -E > Strategie - příklad 1 C 2 C ] L C 2 C ] L C 2 C S S S s s s 1,0 0,2 3,1 2,4 5,3 4,6 Figuře: Stonožka Rostislav Staněk Strategie - interpretace Strategii si lze tedy představit jako popis toho, jak bude hráč ve hře postupovat. Strategie ale říká také, co hrát i po takových historiích, které nejsou konzistentní s naší vlastní strategií. Takové části strategie lze interpretovat jako • reakce na chyby • přesvědčení ostatních hráčů o tom, co budu dělat Rostislav Staněk < □ ► •« flí ► 4 -E t 4 -E > Nashova rovnováha V extenzivní hře s dokonalými informacemi je profil strategií Nashovou rovnováhou, jestliže pro každého hráče / a každou strategii r, platí, že 0(s*) je alespoň tak preferováno jako 0(r;,s*ř) neboli u/(0(s*)) ^ ^(0(^,5*,.)) Rostislav Staněk Nashova rovnováha - příklad 2,1 3,0 0,2 C D EG 2,1 0,2 EH 2,1 1,3 FG 3,0 0,2 FH 3,0 1,3 1,3 Table: Strategická forma extenzivní hry 4 □ ► 4 flP ► < Rostislav Staněk Nashova rovnováha - problémy Smířit se Boj Vstup 2,1 0,0 Ven 1,2 1,2 Table: Strategická forma extenzivní hry vstup do odvětví • Strategie hráčů nemusí být optimální pro ty historie, které nejsou konzistentní se strategiemi hráčů. Hráči mohou tvořit nekredibilní hrozby. • Nashova rovnováha předpokládá, že máme správná očekávání o strategiích ostatních hráčů. Jak si může hráč vytvořit správná očekávání ohledně toho, co dělají ostatní hráči po historiích, které nejsou konzistentní se strategiemi hráčů? Rostislav Staněk Podhra ľ je extenzivní hra s dokonalými informacemi a hráčskou funkcí P Pro každou vlastní podhistorii h nějaké konečné historie extenzivní hry ľ, definujeme podhru V(h) následující po historii h jako extenzivní hru, kde • Hráči jsou stejní jak hráči ve hře ľ • Konečné historie tvoří množina všech sekvencí akcí H takových, že sekvence (h, h') je konečnou historií hry l~. • Každý hráč preferuje h' před h", právě tehdy když preferuje {h, h') před {h, h") Rostislav Staněk Subgame perfect equilibrium Profil strategií s* je dokonalou rovnováhou vzhledem k podhrám, jestliže pro každého hráče /', každou historii h po niž hráč / hraje a každou strategii ry hráče / platí, že konečná historie 0/,(s*) generovaná strategiemi s* po historii h je alespoň tak preferovaná jako konečná historie 0/,(r,-, s* () generovaná strategiemi ry,s*(- po historii h, tj. u;{Oh{s*)) ^ u/ÍO^r/.s*,.)) Rostislav Staněk < □ ► •« rjí ► 4 -E t 4 -E > Subgame perfect equilibrium Platí O Každá SPE je Nashovou rovnováhou © SPE odpovídá Nashově rovnováze v každé podhře © Každá extenzivní hra s konečným horizontem a dokonalými informacemi má dokonalou rovnováhu vzhledem k podhrám. Dva způsoby jak najít SPE Prošetřit každou Nashovou rovnováhou © Zpětnou indukci Rostislav Staněk < □ ► < flP ► 4 -E t 4 -E > Zpětná indukce • Pro každou podhru délky 1 (poslední podhra) najděte optimální akce hráče, který je na tahu. Označme SJ(1) množinu optimálních akcí podhry j. • Vezměte jednu akci z každé množiny Sí(l) a pro tuto kombinaci akcí najděte v každé podhře délky 2 optimální akci hráče, který v podhře táhne jako první. • Takto pokračujeme, dokud nedojdeme na začátek hry. Profily strategií, které takto získáme tvoří SPE. Rostislav Staněk SPE - Stonožka SPE je profil strategií ((S,S,S)(S,S,S)) V experimentech lidé často hrají jinak (Rosenthal(1981)). Je SPE prediktivní? Nagel, Tang (1998) pokud jsou v populaci altruisté, vyplatí se hrát jinak. Parco et al. (2002) vyšší odměny tlačí hráče do rovnováhy Volij (2009) šachoví hráči hrají S Rostislav Staněk Ultimátní hra • Hráči: 1,2 • Konečné historie: Množina sekvencí (x, Z), kde x je částka nabídnutá hráči 2, 0 ^ c ^ c, a Z nabývá hodnot Y(přijme) nebo /V(odmítne). • Hráčská funkce: P(0) = 1, P(x) = 2 • Preference: Výplata hráče je dána částkou, kterou obdrží, tj. Ul(x, Y) = c-x, u2{x, Y) = x, u1(x, N) = 0, u2(x, N) = 0 Rostislav Staněk Hra o důvěře • Hráči: 1,2 • Konečné historie: Množina sekvencí (/,x). / je investovaná částka, přičemž W > I. x je částka nabídnutá hráči 1, 0 S x ú /(l + r). • Hráčská funkce: P(0) = 1, P(/) = 2 • Preference: Výplata hráče je dána částkou, kterou obdrží, tj ui(/,x) = W-l+x, u2(/,x) = /(l + r)-x Rostislav Staněk < □ ► •« flí ► 4 -E t 4 E > Hra o důvěře Figuře IA. hmesíinenl and rgpeymtnt in a lnut ptm. Source: BastÁ tm Berg, Dicktwui, Stacklebergův model oligopolu • Hráči: Firmy 1 a 2 • Konečné historie: Množina sekvencí (qi,q2), kde q, je produkce firmy / • Hráčská funkce: P(0) = 1, P(qi) = 2 • Preference: Výplatní funkce firmy / je dána jejím ziskem, tj. qiP{qi + 92) - Ci(qi), kde P{q\ + 92) je tržní cena, pokud je na trh dodáno množství q\ + «72- Q(<7/) jsou náklady firmy při výrobě množství q,. 1 -O0.O Rostislav Staněk Stacklebergův model oligopolu Figuře: Stacklbergův duopol 4 □ ► 4 flP ► 4 : > 4 E > 1 'O^O Rostislav Staněk