POL 203 8.3. 2018 Klasická teorie her I.- Dominantní strategie. •POL 203 GT ve filmu: The Bride a dokonalá informace •POL 203 •„As I said before, I've allowed you to keep your wicked life for two reasons. And the second reason is so you can tell him [Bill] in person everything that happened here tonight. I want him to witness the extent of my mercy by witnessing your deformed body. I want you to tell him all the information you just told me. I want him to know what I know. I want him to know I want him to know. And I want them all to know they'll all soon be as dead as O-Ren.“ Klasická teorie her ¨Počíná se prací Theory of Games and Economic Behavior Morgensterna a von Neumanna (1944) ¨Analyzuje převážně jednorázové (one shot) hry, v nichž se hráči tahají simultánně. One shot hra může být tvořená i sekvencí tahů, důležité je, aby se tato sekvence neopakovala, pak by byla opakovaná (repeated) ¨Zkoumá se zejména způsob, pomocí kterého hráči vybírají své strategie. ¨Morgenstern a Neumann původně zkoumali hry s nulovým součtem (zero sum games), některé jejich závěry pak byly rozšířeny na hry s nenulovým součtem (non zero sum games). •POL 203 Zero sum vs. non-zero sum games ¨Ve hrách s nulovým součtem musí vše, co někdo vyhraje, někdo prohrát. Součet zisků a ztrát v těchto hrách je 0. ¨V případě her dvou hráčů s nulovým součtem jde o hry čistého soutěžení ¨V případě her více hráčů s nulovým součtem může existovat zájem některých hráčů na spolupráci/ koordinaci strategií s cílem zvýšit zisk na úkor dalších hráčů. ¨Ve hrách dvou či více hráčů s nenulovým součtem obvykle existují pobídky k soutěžení i spolupráci, neboť ztráty hráčů se automaticky nerovnají jejich ziskům. ¨ •POL 203 Zero sum games a sociální situace ¨Příklady ZSG (sudá-lichá, kámen-nůžky papír, penalty v kopané). ¨Zdá se, že ZSG nejsou dobrým reprezentantem sociálních situací (sociální situace jsou obvykle zakotvené (nested), výsledek jedné z nich ovlivní řadu dalších. ¨Př: Je souboj dvou kandidátů v jednomandátovém obvodě 2PZSG? •POL 203 Příklad ZSG •POL 203 Hráč 2 Může odpovídat Nemůže odpovídat Hráč 1 Může odpovídat (0,0) (1,-1) Nemůže odpovídat (-1,1) (0,0) http://i.ytimg.com/vi/z07iUgy0bWQ/default.jpg Kooperativní a nekooperativní hry ¨Kooperativní hry- hry, v nichž existuje možnost hráčů uzavírat (před hrou) závazné dohody, že zvolí určitou strategii. ¨ ¨Nekooperativní hry- hry individuálních hráčů, v nichž je jejich případná spolupráce umožněna pouze pravidly hry a jejich sebezájmem. ¨ ¨Z hlediska teorie her jsou důležitější nekooperativní hry, neboť mnohem jednoznačněji ukazují podmínky, za nichž hráči spolupracují (a za nichž ne). ¨Kooperativní teorie naopak příliš neřeší otázku možného porušování či vynucování dohod během hry (obtížné najít sociální situace, které jim odpovídají). •POL 203 Jak hrát hru: „Dominantní strategie“ a „nejlepší odpovědi“ (Morrow 77-78) ¨V následující hře: ¨ ¨ Hráč 2 Hráč 1 S1 S2 S1 -1,1 2,-2 S2 4,-4 3,-3 •disponuje každý z hráčů dvěma „čistými“ strategiemi (S1 a S2). V tomto případě je pro hráče 1 výhodnější zvolit S2, protože mu vždy zajišťuje lepší výsledek než S1 bez ohledu na to, jestli hráč 2 zvolí S1 nebo S2. •S2 je pro hráče 1 dominantní strategie, protože mu vždy zajišťuje lepší výsledek než S1. Měl by jí proto v této hře vždy hrát (resp. v one-shot hře zvolit se 100% pravděpodobností). •Tady (ve sloupcích) hledá své optimální strategie Hráč 1 •Tady (v řádcích) hledá své optimální strategie Hráč 2 •POL 203 Jak hrát hru: „Dominantní strategie“ a „nejlepší odpovědi“ (Morrow 77-78) Hráč 2 Hráč 1 S1 S2 S1 -1,1 2,-2 S2 4,-4 3,-3 •Hráč 2 dominantní strategii nemá. Pokud hráč 1 hraje S1, pak hráč 2 preferuje S1, pokud hráč 1 hraje S2, pak hráč 2 preferuje S2. Protože však hráč 1 má dominantní strategii S2, volí hráč 2 S2, která je nejlepší odpovědí na strategii S2 hráče 1. Pár strategií (S2,S2) je stabilní, ani jeden z hráčů nemá pobídky změnit svou strategii, pokud ví, kterou strategii zvolil druhý hráč, protože by si tak zhoršil svůj výsledek ve hře. Pár strategií S2,S2 tvoří v této hře tzv. Nashovo ekvilibrium •POL 203 Příklad: nalezněte Nashovo ekvilibrium v souboji DocHolidaye a Ike Clantona ve Springerville, Arizona 1887 (http://www.egwald.com/operationsresearch/gameintroduction.php) ¨Souboj dvou hráčů, oba se musí rozhodnout, z jaké vzdálenosti vystřelit, jejich schopnosti se liší podle vzdálenosti: ¨ Ike Dlouhá Střední (krátká, pokud Doc už střílel) Krátká Doc Dlouhá -2,2 -7,7 -7,7 Střední (krátká, pokud Ike už střílel) 0,0 2,-2 6,-6 Krátká 0,0 -2,2 0,0 Doc Holliday and friends •POL 203 Kill Probability Long Range Middle Range Close Range Ike Clanton 0.5 0.6 1.0 Doc Holliday 0.3 0.8 1.0 • Předchozí hra v extenzivní formě ¨ ¨ ¨ Doc Holliday's Game Tree •POL 203 Aplikace na politiku: soutěž dvou kandidátů ¨ ¨ ¨ KANDIDÁT 2 pravice střed levice KANDIDÁT1 pravice (50,50) (30,70) (55,45) střed (70,30) (50,50) (80,20) levice (45,55) (20,80) (50,50) •POL 203 Příklad s odpadky (Více McCain) •POL 203 HRÁČ 2 vysypávat najmout popeláře HRÁČ 1 vysypávat (4000, 4000) (5000, 3500) najmout popleláře (3500, 5000) (4500, 4500) Sociální dilemata •POL 203 ¨Situace, kdy dominantní strategie a nejlepší výsledek pro oba hráče (získaný kooperativním řešením) nejsou shodné. ¨ ¨Vězňovo dilema, Tragédie obecní pastviny, Veřejné statky, Férovost... John Nash: „if we all go for the blonde“ Hráč 2 Blondýna Brunety Hráč 1 Blondýna (0,0) (3,1) Brunety (1,3) (2,2) •“If everyone competes for the blonde, we block each other and no one gets her. So then we all go for her friends. But they give us the cold shoulder, because no one likes to be second choice. Again, no winner. But what if none of us go for the blonde. We don’t get in each other’s way, we don’t insult the other girls. That’s the only way we win.” http://t2.gstatic.com/images?q=tbn:ANd9GcSMZqgNO6hVKLBWkWgRAx3Xw6pp89A2b-2WS8u3dFsSdsg3tmkWLMOhv2ly Sg Pokud hledáme dominantní strategie, zjistíme ovšem, že (Bruneta, Bruneta) není nejlepším párem odpovědí vůči sobě navzájem, ani Nashovým ekvilibriem, a že hra má ekvilibrium tvořeno smíšenými strategiemi! Smíšené strategie (Morrow 81-88) Hráč 2 Hráč 1 S1 S2 S1 -1,1 1,-1 S2 1,-1 -1,1 •Některé hry (i tato) nemají pár dominantních strategií tvořené čistými strategiemi. Pokud by např. hráč 2 věděl, že hráč 1 chce hrát S1, zvolil by rovněž S1. Pokud chce hráč 1 zabránit tomu, aby jeho soupeř mohl zvolit čistou strategii, musí S1 a S2 vhodně „namixovat“- v tomto případě (0.5S1,0.5S2). Totéž musí učinit i druhý hráč. Ekvilibrium této hry je (0.5S1,0.5S2; 0.5S1,0.5S2), tj. oba hráči volí „náhodně“ či „se stejnou pravděpodobností“ S1 nebo S2, případně „signalizují“ stejně silně, že budou hrát S1 či S2, neboť jedině tak zabrání, aby jejich soupeř mohl z jejich strategie nějak profitovat. •Smíšené strategie mají pro studium politiky značný význam. •V hrách dvou hráčů s nulovým součtem, existuje pro hráče1 smíšená strategie, která garantuje, že hráč 1 získá minimálně x a zároveň smíšená strategie hráče 2, která garantuje, že hráč 1 získá maximálně x. Tyto smíšené strategie jsou v ekvilibriu (tzv. minmax teorém). • Umíme to míchat? (Palacios-Huerta-Volij 2008) •POL 203 ¨Fotbalisté (brankáři a útočníci z Primera a Segunda Division) a UG studenti ¨ ¨Hráli obdobu sudá-lichá (komplikovanější), opakovaně (100-150x) ¨ ¨Výsledek: Fotbalisté téměř dominantní strategie, studenti se odlišovali (špatný poměr voleb, „vzorce“) Piráti ¨Pět pirátů si dělí poklad (100 zlaťáků). Dělení probíhá následujícím způsobem: ¨Nejstarší pirát navrhne ostatním, jak poklad rozdělit, načež se o jeho návrhu hlasuje. Pro schválení je potřeba nadpoloviční většina (nelze se zdržet, při rovnosti rozhoduje navrhovatel). Pokud je návrh schválen, je poklad rozdělen, pokud ne, hodí ostatní nejstaršího piráta do moře a v navrhování pokračuje druhý nejstarší stejnou procedurou. ¨Všichni piráti mají následující (hierarchické) preference: 1.Chtějí přežít 2.Chtějí získat co nejvíce z pokladu 3.Líbí se jim, pokud mohou někoho jiného hodit přes palubu ¨ ¨Jaký návrh učiní první pirát ostatním, aby maximalizoval svůj zisk? ¨Jak hru řešit? ¨ main •POL 203 Řešení hry- zpětná indukce (backwards induction) ¨Zpětná indukce je koncept, pomocí kterého se často řeší hry s více tahy. Předpokládá dokonalou informaci všech hráčů o hře. Začíná se závěrečnými uzly a jejich řešením se postupuje zpětně k počátku hry. ¨V případě Pirátů je řešení pomocí ZI následující: 1.Zůstanou-li dva piráti, navrhovatel navrhne rozdělení (100,0) a sám si ho schválí 2.Zůstanou-li tři hráči, navrhovatel navrhne dělení (99,0,1), pro které hlasuje on a poslední hráč 3.Zůstanou-li ve hře čtyři hráči, navrhovatel navrhne dělení (99,0,1,0), pro které hlasuje on a čtvrtý hráč 4.Řešením hry je návrh prvního piráta (98,0,1,0,1), pro který hlasuje on, třetí a pátý hráč. ¨Řešení souvisí s konceptem subgame perfection (ekvilibrium ve všech tazích hry). •POL 203 Zpětná indukce v politice- strategické hlasování ¨Existují tři alternativy (x,y,z) a tři hráči, kteří mezi nimi vybírají. Volba probíhá nejdříve mezi alternativami x a y , vítěz se následně utká se z a vítězná alternativa je zvolena. ¨Hráči mají následující preference: ¨A: XpYpZ ¨B: YpZpX ¨C: ZpXpY ¨Jak volba dopadne a jak budou hráči hlasovat? •POL 203 Řešení- zpětná indukce ¨Pokud se v posledním kole hry utká Z s X, zvítězí Z, pokud se Z utká s Y, zvítězí Y. ¨Provedou-li tuto kalkulaci všichni hráči, má C pobídku k tomu, aby se v posledním kole utkalo Z s X (a vyhrálo), B pobídku k tomu, aby se Z utkalo s Y (a prohrálo). Strategicky zajímavá je situace hráče A, který na jednu stranu chce vítězství X, ale ví, že v souboji se Z ho není možné dosáhnout. ¨Hráč A proto v prvním kole nevolí upřímně, ale strategicky (alternativu y, kterou preferuje méně nežx) a zajistí si tak lepší výsledek druhého kola (tj. lepší celkový výsledek). •POL 203