1 Domácí úkol 1. Příklad 1.1 Uvažte následující hru dvou hráčů v normální formě Muž H B Žena H (1, a) (c, 1) B (1, b) (d, 1) Určete hodnoty parametrů a, b, c, d tak, aby hra měla Nashovu rovnováhu (B, B). Pro jaké parametry je to jediná Nashova rovnováha? Kdy jde o řešení vzniklé opakovanou eliminací dominovaných strategií? Řešení 1.1 Aby strategický profil (B, B) tvořil Nashovu rovnováhu, musí platit, že žádný z hráčů si nemůže jednostrannou změnou akce polepšit, tedy zvýšit svůj užitek. To znamená, že užitek ženy, pokud hraje B a muž hraje B musí být větší než užitek, kdyby hrála H zatímco muž by stále hrál B. Podobně pro muže. Musí tedy platit, že c d, b 1 O jedinou Nashovu rovnováhu půjde v případě, že žádný další strategický profil ((H, B), (H, H), (B, H)) nebude tvořit Nashovu rovnováhu. V případě, že předchozí podmínky c d, b 1 jsou splněny s ostrou nerovností, profily ((H, B), (B, H)) nemohou tvořit Nashovu rovnováhu, neboť jeden z hráčů (ten hrající H) si polepší hraním B. Pokud by ale například c = d, musí platit a > 1, aby (H, B) netvořilo Nashovu rovnováhu. Pokud b = 1, pak by (B, H) tvořilo Nashovu rovnováhu, neboť Žena by hraním H získala stejně jako hraním B (tedy 1, nepolepšila by si). Aby (H, H) netvořilo NR, pak musí platit, že a < 1, protože žena je indiferentní mezi H a B když Muž hraje H. To je ovšem ve sporu s požadavkem na a pro případ c = d. To znamená, že pokud c = d, tak (B, B) jedinou Nashovu rovnováhu tvořit nemůže. Tedy (B, B) tvoří jedinou NR pokud c < d, a < 1, b < 1. Strategický profil (B, B) lze získat opakovanou eliminací pokud lze nejprve eliminovat H pro ženu (muže) a pak H pro může (ženu). * Nejprve eliminovat strategii H pro ženu je možné, je-li dominovaná strategií B bez ohledu na strategii muže. Uvažujeme-li striktně dominované strategie (jestliže explicitně nestanovíme, že uvažujeme slabě dominované strategie, pak tomu tak je), pak tato možnost nikdy nenastane, protože Žena je indiferentní mezi H a B pokud muž hraje H. Při eliminaci slabě dominovaných strategií by bylo potřeba jen c < d. Po eliminaci H pro ženu by muselo být optimální eliminovat H pro muže, tedy b < 1. * Strategii H je pro muže optimální eliminovat1 pokud a < 1, b < 1. Pro ženu je pak optimální eliminovat H pokud c < d. Kombinací podmínek dohromady získáme možnost současného odstranění strategie H pro muže i ženu. Příklad 1.2 Formulujte následující problém jako hru dvou hráčů v normální formě a ukažte, že v každé Nashově rovnováze hra končí okamžitě. Dva hráči vedou spor o daný objekt. Hodnoty předmětu jsou v1 a v2. Čas je spojitá proměnná se začátkem v 0 a jdoucí až do nekonečna. Každý hráč má možnost odstoupit ze sporu. V takovém případě spor končí a předmět získává druhý hráč. Vedení sporu je náročné. Za každou jednotku času vedení sporu se užitek obou hráčů snižuje o 1. Pokud odstoupí oba hráči najednou, každý z nich získá daný předmět s 50% pravděpodobností. Řešení 1.2 Je důležité si uvědomit, že čas je spojitá proměnná, kterou budeme označovat t. Strategie každého hráče je pak čas ti R0+, ve kterém se rozhodne ze sporu odstoupit. Kromě hráčů (1, 2) a těchto jejich strategií ještě musíme popsat užitky hráčů (výsledek hry). Ten je ui(ti, tj) = vi - ti pro ti < tj -tj pro tj < ti 1 2 (vi - ti) pro ti = tj 1Pro eliminaci strategie jako slabě dominované stačí, aby platila jedna nerovnost ostře a druhá neostře. 1 kde i = j, i, j {1, 2}. Ukážeme sporem, že neexistuje Nashova rovnováha, ve které by hra nekončila okamžitě. Předpokládejme, že hra končí v okamžiku t > 0 a je to hráč i, kdo odstoupí ze sporu. Pokud zároveň odstoupil i hráč j = i, pak si hráč i může polepšit tím, že ze sporu odstoupí o později (a totéž platí i pro hráče j). Pokud odstoupí jen hráč i, pak si může polepšit tím, že odstoupí dříve, čímž sice stejně nezíská daný předmět, ale zvýší si užitek proto, že bude čekat méně. Takže nemůže jít o Nashovu rovnováhu. Příklad 1.3 Následující situaci zapište jako poziční hru dvou hráčů s neúplnou informací a nalezněte všechny její Nashovu rovnováhy v čistých i smíšených strategiích. První hráč obdrží kartu, která má budťo černou (kříže, piky) nebo červenou (srdce, káry) barvu, se stejnou pravděpodobností. Hráč 2 nevidí barvu této karty. První hráč může přiznat, že je karta červená a pak zaplatí 100Kč druhému hráči. Alternativně může tvrdit, že karta je černá. Druhý hráč pak muže tuto informaci přijmout a zaplatit 100Kč prvnímu hráči. Druhý hráč ale může také trvat na tom, aby mu první hráč kartu ukázal. Pokud byla černá, pak musí prvnímu hráči zaplatit 400Kč. V opačném případě od prvního hráče tyto peníze dostane. Analyzujte rovněž sekvenčně racionální rovnováhy a WPBE. Řešení 1.3 Hru popisuje následující strom: ˇ 0 Černá p=0.5 %%LLLLLLLLLLL Červená p=0.5 yyrrrrrrrrrrr ˇ 1 R vvnnnnnnnnnnnnn B %%JJJJJJJJJJJJ ˇ B ((PPPPPPPPPPPPPPPP 1 (-100, 100) ˇ _____________2 V zzuuuuuuuuuu N $$IIIIIIIIII ˇ 2 V N ''OOOOOOOOOOOOOO (100, -100) (-400, 400) (100, -100) (400, -400) Příroda nejprve volí typ karty, každý typ s pravděpodobností 50 procent. Pokud je karta černá, pak první hráč oznámí, že je černá.2 Pokud je karta červená, pak to může první hráč přiznat a zaplatit 100Kč, nebo lhát. Druhý hráč může chtít kartu vidět. Pokud zjistí, že první hráč lhal, dostane od něj 400Kč, jinak 400Kč zaplatí. Pro Nashovu rovnováhu musíme specifikovat strategie prvního a druhého hráče. Protože první hráč musí oznámit černá (B), pokud je karta černá, stačí zvažovat jeho strategie v případě, že je karta červená. Strategie druhého hráče specifikují, zda bude věřit (V ) nebo ne (N). Máme tedy celkem 4 potenciální kandidáty na rovnováhu a postupně ověříme, zda může jít o čistou NR: * Strategický profil (R, V ) netvoří Nashovu rovnováhu, protože první hráč si může polepšit tím, že by hrál B. * Strategický profil (R, N) netvoří Nashovu rovnováhu, protože pro druhého hráče je lepší věřit. Kdykoliv totiž první hráč zahraje B tak má opravdu černou kartu. Kdyby hráč 2 věřil, tak by zaplatil jen 100Kč, ale takto, protože nevěří, zaplatí 400Kč. * Strategický profil (B, N) netvoří Nashovu rovnováhu. Pokud by první hráč zahrál R když má červenou kartu, tak by sice zaplatil 100Kč, ale to je lepší (v průměru) než 400Kč protože druhý hráč nevěří. * Strategický profil (B, V ) netvoří Nashovu rovnováhu, protože druhý hráč prohraje 100Kč (s jistotou), zatímco kdyby nevěřil, tak by dosáhl 0. Vidíme, že neexistuje čistá NR. Ve smíšených strategiích označíme p pravděpodobnost, se kterou první hráč zahraje R když má červenou kartu a q pravděpodobnost, že druhý hráč zahraje V . Volby p, q musejí maximalizovat užitky hráčů, takže pro prvního hráče3 max p q(1 - p)(100) - (1 - p)(1 - q)400 - p100 2Zadání nespecifikuje, že by mohl oznámit, že je červená a jak by hra dopadla. Tuto možnost bylo možné zakreslit do obrázku a pak argumentovat, proč není nikdy optimální ji hrát. 3Všimněte si, že následující rovnice popisuje jen tu část informačního stromu, kde se první hráč rozhoduje. Tam, kde se nerozhoduje, jeho rozhodnutí o q neovlivňuje jeho výhru. 2 Podmínky prvního řádu (vzhledem k p) dávají q = 3 5 , max q 1 2 (q(1 - p)(-100) + (1 - p)(1 - q)(400)) + 1 2 (-100q + (1 - q)(-400) Podmínky prvního řádu dávají p = 2 5 . Smíšená Nashova rovnováha je tedy p = 2 5 , q = 3 5 . Nyní budeme řešit WPBE. Očekávaný výnos je -100 když hraje věřit, protože hráč 2 vždy zaplatí 100Kč. V případě , že nevěří, vyhraje 400 když je v levé částí informační množiny (když první hráč má červenou kartu) a prohraje -400 v pravé části informační množiny. Očekávaný výnos z V je větší než očekávaný výnos N -100 > 400r - 400(1 - r), což vede na podmínku r < 3 8 . Hra vždy vede do příslušné informační množiny, takže Bayesovo pravidlo lze použít vždy. To znamená, že když první hráč hraje B s pravděpodobností p když má červenou kartu, tak očekávání druhého hráče musí být (r = P(L|I) = 1-p 2-p , P(R|I) = 1 2-p ). V případě, že r < 3 8 , druhý hráč preferuje " věřit", pokud je r > 3 8 , pak preferuje " nevěřit". V případě r = 3 8 je daný hráč indiferentní. Nechť nejprve druhý hráč hraje " věřit". Zřejmě pak první hráč bude chtít hrát R s co největší pravděpodobností (p = 1), takže nemůže jít o rovnováhu. Pokud naopak druhý hráč hraje " nevěřit", pak první hráč chce hrát R. Ani zde nemůže jít o rovnováhu, jak jsme diskutovali v čistých NR. Jediná možnost tedy je, že druhý hráč volí náhodně mezi " věřit" a " nevěřit". Označme q pravděpodobnost, že hraje " věřit". Protože druhý hráč musí být indiferentní mezi " věřit" a " nevěřit", musí platit, že jeho očekávání, že se nachází v levé části informační množiny je r = 3 8 . To znamená, že první hráč musí hrát B s pravděpodobností p = 2 5 . To je pro něj optimální tehdy, když max p q(1 - p)(100) - (1 - p)(1 - q)400 - p100 Podmínka prvního řádu je identická s podmínkami prvního řádu při výpočtů smíšených Nashových rovnováh a tak vyjde taktéž q = 3 5 . Smíšená Nashova rovnováha je v tomto případě stejná jako WPBE s příslušnými očekáváními (3 8 , 5 8 ). Pro výpočet sekvenční rovnováhy je dobré si všimnout, že behaviorální a smíšené strategie jsou v tomto případě identické a Bayesův vzorec lze použít vždy. Nechť p je opět pravděpodobnost, že první hráč hraje R, q pravděpodobnost, že druhý hráč hraje V a očekávání jsou (r, 1 - r). Aby druhý hráč mohl hrát čistě smíšenou strategii, musí být indiferentní mezi V a N. Jeho očekávání tak musí být r = 3 8 . Hodnota p, která vede k tomuto očekávání je 3 5 (použijte Bayesovo pravidlo pro odvození) a optimální strategie druhého hráče pak musí být q = 2 5 . Dříve odvozená smíšená strategie je tak, společně s očekáváním x = 3 8 , tvoří sekvenčně racionální rovnováhu i WPBE. To, že WPBE a sekvenční rovnováhy jsou identické je zde způsobeno tím, že hra se vždy dostane do příslušné informační množiny. Příklad 1.4 Ve městě X jsou dva týmy v nejvyšší fotbalové lize, označené A a B. Lístek na zápas týmu A stojí PA, a PB pro tým B. Při těchto cenách je množství prodaných lístků na zápasy na hřišti týmu A roven 21 - 2PA + PB a 21 - 2PB + PA pro tým B. Interpretujte znaménka u cen v poptávkových funkcích. Nalezněte Nashovu rovnováhu v cenách. Řešení 1.4 Znaménka určují, jak poptávka reaguje na nárůst cen. Zdražení zápasů na stadionu daného týmu vede k poklesu prodaných lístků na daném stadionu, ale vede k nárůstu počtu prodaných lístku na stadionu druhého týmu. Takové situaci říkáme, že jde o substituty. Jde ale o substituty nedokonalé, protože různé ceny nevedou na nulovou poptávku statku (zde lístků) s nižší cenou. Nashovu rovnováhu v cenách zjistíme tak, že budeme uvažovat maximalizační problém každého hráče, za podmínky že cena lístku na stadionu druhého hráče je fixní. Tedy řešíme problémy max PA (21 - 2PA + PB)PA (1) max PB (21 - 2PB + PA)PB (2) 3 Podmínky prvního řádu jsou pak 21 - 4PA + PB = 0 (3) 21 - 4PB + PA = 0 (4) Odečtením těchto podmínek získáme PA = PB a zpětným dosazením do libovolné znich pak PA = 7 = PB. Toto je Nashova rovnováha v cenách.4 Příklad 1.5 Předpokládejte, že k výrobě jedné jednotky mosazi je potřeba jedna jednotka mědi a jedna jednotka zinku. Trh vyrábějící mosaz je dokonale konkurenční a výroba směsi nic nestojí, takže cena mosazi je rovna součtu cen mědi a zinku. Na trhu mědi existuje jediný výrobce (monopol) s nulovými výrobními náklady a totéž platí i pro zinek. Poptávka po mosazi je q = 900 - 2p, kde q je poptávané množství mosazi při její cenně p. Pro měď a zinek neexistuje žádné jiné využití než pro výrobu mosazi. Oba výrobci volí cenu. Nalezněte Nashovu rovnováhu jejich strategiích. Řešení 1.5 Označme cenu jednotky mědi pm a cenu jednotky zinku pz. Protože trh s mosazí je dokonale konkurenční a jediné výrobní náklady jsou pořizovací náklady vstupních surovin (jednotky mědi a zinku), platí, že p = pm +pz. Maximalizující chování každého dodavatele pak vede na řešení těchto problémů max pm pm(900 - 2(pm + pz)) (5) max pz pz(900 - 2(pm + pz)) (6) Problém je opět zcela symetrický, takže intuitivně očekáváme symetrické řešení. Skutečně, podmínky prvního řádu vedou na pm = pz a zpětným dosazením dostaneme pm = pz = 150. 4Formálně je potřeba ověřit, že skutečně jde o maximum. To je zde triviální. 4