Základy teorie her Rostislav Staněk ESF MU Obsah 1 Teorie her 5 2 Strategické hry a Nashova rovnováha 6 2.1 Strategické hry.......................................... 6 2.2 Příklady strategických her.................................... 6 Vězňovo dilema.......................................... 6 Bach nebo Stravinsky, Bitva pohlaví.............................. 6 Lov jelena............................................. 7 Hlava nebo orel.......................................... 7 2.3 Nashova rovnováha........................................ 7 2.4 Příklady Nashovy rovnováhy .................................. 8 Vězňovo dilema.......................................... 8 Bach nebo Stravinsky (BS) ................................... 8 Hlava nebo orel.......................................... 8 Lov jelena............................................. 8 2.5 Optimální odpověď........................................ 9 2.6 Dominované a dominující akce ................................. 9 2.7 Symetrické hry.......................................... 10 3 Nashova rovnováha: Ilustrace 11 3.1 Modely oligopolu......................................... 11 Cournotův model oligopolu................................... 11 Bertrandův model oligopolu................................... 11 3.2 Aukce............................................... 12 Second-price sealed-bid aukce.................................. 12 First-price sealed-bid aukce................................... 13 3.3 Volební soutěž .......................................... 14 3.4 Odpovědnost za škodu...................................... 14 4 Smíšené strategie 16 4.1 Reprezentace preferencí pomocí očekávané výplaty...................... 16 4.2 Nashova rovnováha ve smíšených strategiích.......................... 16 4.3 Hledání Nashovy rovnováhy ve smíšených strategiích..................... 17 4.4 Příklady Nashovy rovnováhy .................................. 17 Hlava nebo orel.......................................... 17 Expertní posouzení........................................ 18 Dobrý samaritán......................................... 19 4.5 Dominované akce......................................... 19 5 Extenzivní hry s dokonalými informacemi 20 5.1 Definice extenzivní hry...................................... 20 5.2 Nashova rovnováha........................................ 21 5.3 Dokonalá rovnováha vzhledem k podhrám (SPE)....................... 22 5.4 Zpětná indukce.......................................... 24 6 Extenzivní hry: Ilustrace 25 6.1 Ulimátní hra ........................................... 25 6.2 Stacklebergův model oligopolu ................................. 25 6.3 Kupování hlasů.......................................... 26 7 Extenzivní hry: rozšíření 28 7.1 Extenzivní hry se současnými tahy............................... 28 7.2 Extenzivní hry se současnými tahy: Ilustrace......................... 28 Vstup do monopolního odvětví................................. 28 Odchod z upadajícího odvětví.................................. 29 Volební soutěž se strategicky uvažujícími voliči........................ 30 Bertrandův model s volbou kapacit............................... 31 7.3 Exogénni nejistota v extenzivních hrách............................ 32 7.4 Morální hazard v teorii kontraktů................................ 33 Rizikově neutrální agent..................................... 34 Rizikově averzní agent...................................... 34 Omezené ručení................. ......................... 35 8 Strategické hry s nedokonalými informacemi 36 8.1 Definice strategické hry s nedokonalými informacemi..................... 36 Příklad: Bitva pohlaví...................................... 36 8.2 Nashova rovnováha Bayesovských hry ............................. 37 Příklad .............................................. 37 8.3 Informace o informacích..................................... 38 8.4 Aukce............................................... 38 Aukce se soukromým oceněním................................. 38 Aukce se společným oceněním.................................. 39 9 Extenzivní hry s nedokonalými informacemi 40 9.1 Definice extenzivní hry s nedokonalými informacemi..................... 40 Příklad extenzivní hry s nedokonalými informacemi...................... 40 9.2 Nashova rovnováha........................................ 41 9.3 Přesvědčení a sekvenční rovnováha............................... 41 Definice sekvenční rovnováhy.................................. 42 Hledání slabé sekvenční rovnováhy............................... 42 9.4 Signalizace ............................................ 43 10 Opakované hry: Vězňovo dilema 43 10.1 Preference a struktura opakované hry ............................. 44 10.2 Konečné vězňovo dilema..................................... 45 10.3 Nekonečné vězňovo dilema.................................... 45 Strategie v nekonečné hře.................................... 46 Nashovy rovnováhy v nekonečném vězňově dilematu..................... 46 SPE v nekonečném vězňově dilematu.............................. 48 11 Opakované hry: Zobecnění 50 11.1 Nashova rovnováha v nekonečně opakovaných hrách ..................... 50 Minmax výplata......................................... 50 Folk teorém pro Nashovu rovnováhu.............................. 50 11.2 SPE v nekonečně opakovaných hrách.............................. 51 11.3 Aplikace.............................................. 52 Vyjednávání............................................ 52 1 Teorie her Teorie her představuje způsob, jakým můžeme modelovat interakce mezi jednotlivci. Dle charakteru těchto interakcí se liší i forma hry, jenž modeluje tyto interakce. V některých situacích se subjekty rozhodují ve stejný okamžik (jako když hrajete kámen, nůžky, papír), v se rozhodují postupně (jako když hrajete šachy). První typ situací je modelován pomocí tzv. strategických her, druhý je analyzován za pomocí tzv. extenzivních her. Strategické situace se mohou lišit také tím, jaké informace mají jednotlivé subjekty o svém okolí. Ve hrách s dokonalými informacemi mají agenti dokonalé informace o okolí ve kterém se pohybují. Na druhé straně ve hrách s nedokonalými informacemi existuje nejistota o některých veličinách podstatných pro rozhodování (např. firmy nemusí přesně znát náklady svých konkurentů). V ekonomii se teorie her používá při analýze mnoha rozličných problémů, především mikroekonomického charakteru. Mezi nejznámější aplikace teorie her v ekonomii patří • rozhodování firem na oligopolních trzích • vysvětlení organizace firem a jejich kapitálové struktury • analýza politického rozhodování • rozhodování účastníků aukcí • tržní regulace, politika hospodářské soutěže • ekonomická analýza práva Uvedený výčet slouží jen k nastínění širokého pole možných aplikací teorie her. S mnohými z těchto aplikací se podrobněji seznámíte v tomto textu. 2 Strategické hry a Nashova rovnováha 2.1 Strategické hry Pomoci strategických her můžeme modelovat interakce mezi jednotlivci, kteří se rozhodují ve stejný okamžik. Rozhodující se jednotlivce označujeme v teorii her jako hráče. Každý hráč má na výběr z množiny možných akcí. (množinu akcí hráče i značíme Ai) Výsledek hry je dán tím jakou akci si každý hráč zvolil. Seznam akcí jednotlivých hráčů přitom nazýváme profil akcí. (Matematicky budeme profil akcí zapisovat jako uspořádanou n-tici, kde i-tý člen označuje akci i-tého hráče.) Strategické hry nemají časový rozměr. Všichni hráči volí své akce v jeden a stejný okamžik, což znamená, že žádný z hráčů nemá informace o tom, jaké akce v dané hře zvolili ostatní hráči. Definice 1. Strategická a hra se skládá z • množiny hráčů • množiny akcí každého hráče • preferencí každého hráče definovaných nad množinou profilů akcí Stejně jako v teorii racionální volby je zvykem definovat preference hráčů pomocí výplatní (užitkové) funkce, která je reprezentuje. Výplatní funkce je ordinální. Pokud výplatní funkce hráče přiřazuje postupně situacím A, B a C hodnoty 100, 4 a 1, pak to znamená, že hráč preferuje situaci A před B a B před C. (Značíme A y B y C) Neznamená to však, že by jeho preference A před B byla silnější než preference B před C. Výplatní funkce, která uvedeným situacím přiřazuje např. hodnoty 3,2,1 reprezentuje stejné preference. Pojmy výplatní a užitková funkce jsou v tomto textu zaměnitelné. 2.2 Příklady strategických her Vězňovo dilema Zřejmě nejslavnější strategická hra se jmenuje vězňovo dilema (PD). Hra je definována následujícím způsobem. • Hráči jsou dva podezřelí 1 a 2. • Každý hráč má na výběr akce {zradit, spolupracovat} zkráceně {D,C} • Preference podezřelého 1 jsou (D, C) >~ (C, C) >~ (D, D) >~ (C, D), kde např. (D,C) znamená, že hráč 1 zradí zatímco hráč 2 spolupracuje. Preference podezřelého 2 jsou (C, D) >~ (C, C) >~ (D,D) >~ (D,C). Uvedenou hru můžeme jednoduše znázornit v tabulce. Abychom mohli správně reprezentovat preference, musíme pro výplatní funkce hráčů platit u\{D,C) > u\{C,C) > u\{D,D) > u\{C,D) a u2(C,D) > u2(C,C) > u2(D,D) > u2(D,C). Akce hráče 1 uvádíme v řádcích a jeho výplatu udává první číslo v poli. Akce hráče 2 uvádíme ve sloupcích a jeho výplatu udává druhé číslo v poli. D C D 1,1 3,0 C 0,3 2,2 Tabulka 1: Vězňovo dilema Bach nebo Stravinsky, Bitva pohlaví Bach nebo Stravinsky (BS) patří mezi tzv. koordinační hry. Hra může modelovat např. následující situaci. Každý ze dvou partnerů se rozhoduje, zda půjde na koncert Bacha nebo Stravinského. Každý z nich preferuje jiný koncert. Ani jeden z nich si koncert neužije, pokud na něj půjde sám. Hru pak lze zapsat následující tabulkou. B S B 2,1 0,0 S 0,0 1,2 Tabulka 2: Bitva pohlaví Lov jelena Dva lovci (hráčů) mají na výběr ze dvou akcí: lovit jelena (S) nebo zajíce (H). Jelena přitom uloví, jen pokud ho budou lovit oba dva, zajíce dokáže ulovit každý sám. Každý z hráčů preferuje situaci, kdy společně uloví jelena. Nejhorší situací pro hráče je, když jde lovit jelena, ale neuloví ho. S H S 2,2 0,1 H 1,0 1,1 Tabulka 3: Lov jelena Hlava nebo orel Dva lidé si tajně vyberou jednu stranu mince a pak si je ve stejný okamžik ukáží. Na minci je buď orel (T) nebo hlavu (H). Pokud ukáží stejnou stranu zaplatí hráč 2 hráči 1 dohodnutou částku a naopak. Preference hráčů jsou dány jejich peněžním ziskem či ztrátou. Jde o hru s nulovým součtem, což znamená, že zisk jednoho hráče je vždy roven ztrátě druhého hráče. Tento typ her slouží k modelování čistě konfliktních situací. T H T 1,-1 -1,1 H -1,1 1,-1 Tabulka 4: Hlava nebo orel 2.3 Nashova rovnováha Klíčovým pojmem teorie her je řešení hry, které nám umožňuje říci jaké akce si jednotlivý hráči zvolí. Nejpoužívanějším řešením strategických her z dokonalými informacemi představuje Nashova rovnováha. Nashova rovnováha je taková situace, ve kterém žádný z hráčů nemůže zvýšit svou výplatu jednostrannou změnou své strategie. Nashova rovnováha tedy vyžaduje, aby si každý hráč zvolil nejlepší možnou akci. Nejlepší možná akce ale závisí na tom, jaké akce volí ostatní hráči. Můžeme si tedy představit, že každý hráč má nějaké přesvědčení o akcích, které budou hrát ostatní hráči, a na základě těchto přesvědčení si zvolí akci, která je pro něj nejvýhodnější. Nashova rovnováha se potom vyznačuje dvěma znaky: • Každý hráč si volí akci, která mu přináší nejvyšší výplatu při daných přesvědčeních ohledně akcí ostatních hráčů. • Přesvědčení každého hráče o akcích, které budou hrát ostatní, jsou správná. Jak je ale možné, že jsou přesvědčení hráčů v Nashově rovnováze správná, když hráči nemají informace o akcích ostatních hráčů? Ve strategických hrách budeme předpokládat, že hráči mají dostatečně dlouhou zkušenost s analyzovanou hrou a z této zkušenosti vědí, jak typický hráč hru hraje. Abychom mohli definovat Nashovu rovnováhu formálně, zavedeme následující značení: • a je profil akcí při němž každý hráč í hraje akci en • (ai;a_i) je profil akcí při němž hráč i hraje akci ai a každý hráč j kromě hráče i hraje a j (index —í tedy znamená všichni kromě hráče i). • Ui(a) je výplata hráče i při profilu akcí a Definice 2. Profil akcí a* strategické hry je Nashovou rovnováhou, pokud pro každého hráče í a každou jeho akci ai platí Ui{a*) > Ui{ai,a*_^j. Pokud v předchozí definici nahradíme vztah > vztahem > získáme definici tzv. striktní Nashovy rovnováhy. 2.4 Příklady Nashovy rovnováhy Vězňovo dilema Ve vězňově dilematu se objevují 4 možné profily akcí. Postupně ověříme, jestli některé z nich tvoří Nashovu rovnováhu. • (D,D) je Nashovou rovnováhou, protože hráč 1 si nepolepší, pokud si jednostranně zvolí akci C a ani hráč 2 si nepolepší, pokud si jednostranně zvolí akci C. • (C,C) není Nashova rovnováha, protože hráč 1 zvýší svoji výplatu, pokud si jednostranně zvolí akci D (totéž platí pro hráče 2). • (C,D) není Nashova rovnováha, protože hráč 1 zvýší svoji výplatu, pokud si jednostranně zvolí akci D. • (D,C) není Nashova rovnováha, protože hráč 2 zvýší svoji výplatu, pokud si jednostranně zvolí akci D. Bach nebo Stravinsky (BS) Opět prověříme jednotlivé profily akcí a ukážeme, že BS má 2 Nashovy rovnováhy. • (B,B) je Nashovou rovnováhou, protože hráč 1 si nepolepší, pokud si jednostranně zvolí akci S a ani hráč 2 si nepolepší, pokud si jednostranně zvolí akci S. • (S,S) je Nashova rovnováha, protože hráč 1 nezvýší svoji výplatu, pokud si jednostranně zvolí akci B a totéž platí pro hráče 2. • (B,S) není Nashova rovnováha, protože hráč 1 zvýší svoji výplatu, pokud si jednostranně zvolí akci S. Stejně tak hráč 2 zvýší svoji výplatu, pokud si jednostranně zvolí akci B. • (S,B) není Nashova rovnováha, protože hráč 1 zvýší svoji výplatu, pokud si jednostranně zvolí akci B. Stejně tak hráč 2 zvýší svoji výplatu, pokud si jednostranně zvolí akci S. Hlava nebo orel Ověřte, že ani jeden ze 4 profilů akcí ve hře Hlava nebo orel není Nashovou rovnováhou. (Později budeme uvažovat smíšené strategie a ukážeme, že tato hra má Nashovu rovnováhu ve smíšených strategiích) Lov jelena Ve hře lov jelena se dvěma hráči představují Nashovu rovnováhu profily akcí (S,S) a (H,H). Povšimněte si, že oba hráči preferují situaci (S,S) před situací (H,H). To však nemění nic na tom, že (H,H) je Nashova rovnováha, protože žádný z hráčů nemůže zvýšit svou výplatu při dané akci druhého hráče. Představme si, že hru lov jelena hraji více hráčů. Stále přitom platí, že každý z hráčů preferuje situaci, kdy všichni společně uloví jelena před situací, kdy sám uloví zajíce. Tato hra má opět dvě Nashovy rovnováhy. Jednou z nich je profil (S,...,S), v němž všichni hráči loví jelena. Každý hráč totiž preferuje situaci, kdy společně uloví jelena před situací, kdy sám uloví zajíce a proto si žádný z nich nemůže polepšit, pokud zvolí akci H. Druhou rovnováhou je (H,..,H) v němž všichni hráči loví zajíce. Žádný jiný profil není Nashovou rovnováhou, protože vždy existuje hráč který zvolil akci S a ten může zvýšit svoji výplatu, pokud místo ní zvolí akci H. 2.5 Optimální odpověď Nashovu rovnováhu jsme zatím hledali tak, že jsme postupně prošli všechny profily akcí a ověřili, zda splňují podmínku Nashovy rovnováhy. Nashovu rovnováhu můžeme hledat také pomocí tzv. optimální odpovědi (best-response function) každého hráče. Definice 3. Optimální odpověď hráče í označíme jako Bi a definujeme jako Bi(a-i) — {en e Ai : Ui(a,i,a-i) > ul(al,a-l)\/al G Ai} Uvažujme hráče i, který má na výběr z několika akcí. Tyto akce mu při daných akcích ostatních hráčů přináší nějaký užitek. Optimální odpověď potom přiřadí každé kombinaci akcí ostatních hráčů a—i takovou akci hráče i, která mu přinese nejvyšší užitek. Například, ve hře BS si hráč 1 může zvolit mezi akcemi B a S. Akce B je nejlepší (přináší nejvyšší užitek), pokud hráč 2 hraje B. Naopak, akce S je pro hráče 1 nejlepší, pokud hráč 2 hraje S. Optimální odpověď tedy vypadá takto: B\{B) — B;B\{S) — S. Všimněte si, že optimální odpověď nemusí vybírat jedinou akci, ale celou množinu akcí. Matematicky se tudíž jedná o korespondenci. Propozice 1. Profil akcí a* je Nashovou rovnováhou právě tehdy, když akce každého hráče je optimální odpovědí na akce ostatních hráčů. Tedy a* e Bi(a*_i),Ví Uvedené tvrzení nám nabízí další způsob, jak nalézt Nashovu rovnováhu. V Nashově rovnováze žádný hráč nemůže zvýšit svou výplatu změnou akce při daných akcích ostatních hráčů. To znamená, že každý hráč hraje svou optimální odpověď na rovnovážné akce ostatních hráčů. Pokud najdeme optimální odpovědi každého hráče, pak Nashovu rovnováhu nalezneme jako jejich průnik. Tuto metodu si ukážeme na příkladu hry definované tabulkou 5. Optimální odpovědí hráče 1, pokud hráč 2 hraje L je M (hráč 1 má v daném sloupci nejvyšší výplatu), označíme si proto výplatu hráče 1 v tomto poli hvězdičkou. Podobně postupujeme dále. Nakonec se podíváme na pole, v němž jsou obě výplaty označeny hvězdičkou, tato pole udávají Nashovy rovnováhy. V našem případě je tedy Nashovou rovnováhou profil akcí (B,R). L C R T 1,2* 2*,1 1*,0 M 2*,1* 0,1* 0,0 B 0,1 0,0 1*,2* Tabulka 5: 2.6 Dominované a dominující akce Při hledání Nashovy rovnováhy můžeme v některých hrách využít konceptu dominujících a dominovaných akcí. Definice 4. Akce striktně dominuje akci a -, pokud přináší vyšší výplatu bez ohledu na to, jaké akce hrají ostatní hráči, tj. ^(a^a-í) > ^(a^ , a_z),Va_i. je striktně dominovaná akce Je zjevné, že striktně dominovaná akce není optimální odpovědí na žádnou akci ostatních hráčů a tudíž striktně dominovaná akce není nikdy hrána v Nashově rovnováze. Při hledání Nashovy rovnováhy si proto můžeme pomoci eliminace všech striktně dominovaných akcí. Způsob jakým lze opakovaně eliminovat striktně dominované strategie si ukážeme na příkladu hry v tabulce 6. Nejprve si můžeme všimnou, že akce R hráče je striktně dominovaná akcí C. Sloupec s akcí R můžeme tedy vyškrtnout a zůstane tabulka o dvou sloupcích, v této tabulce je ale akce B hráče 1 striktně dominována akcí M. Řádek s akcí B tedy opět vyškrtneme. Zbývá nám tabulka 2x2. Akce C je v této tabulce striktně dominována a můžeme ji opět vyškrtnout. Ze zbývajících profilů akcí je snadné určit, že profil (M, Ľ) je Nashovou rovnováhou. Kromě striktně dominovaných akcí můžeme definovat také slabě dominované a slabě dominující akce. L C R T 1,2 2,1 1,0 2,2 0,1 0,0 0,1 0,3 1,2 M B Tabulka 6: Definice 5. Akce a- slabě dominuje akci a", pokud «i(a-, a_i) ^ Ui(a", a-i), Va_i a zároveň «i(a-, a_i) jí Ui{a'l,a-i), alespoň pro jeden a—i. a" je slabě dominovaná akce. Slabě dominovaná akce není nikdy hrána ve striktní Nashově rovnováze. Při hledání striktní Nashovy rovnováhy můžeme eliminovat slabě dominované akce. Eliminací slabě dominovaných akcí ale můžeme ztratit některé Nashovy rovnováhy. 2.7 Symetrické hry V některých případech chceme modelovat interakce v populaci, v níž jsou všichni jedinci totožní, což znamená, že mají k dispozici stejné akce a mají stejné preference. K takovému účelu slouží symetrické hry. Definice 6. Strategická hra o dvou hráčích je symetrická, pokud množina akcí je stejná a preference hráčů jsou reprezentovány výplatní funkcí pro niž platí 111(0,1,0,2) — u2(a2,ai), V(ai,a2). Přímým důsledkem uvedené definice je skutečnost, že tabulka zadávající symetrickou hru je symetrická. V případě hry o dvou hráčích, v níž má každý z hráčů na výběr ze dvou akcí, má tabulka symetrické hry následující podobu T H T x,x w,z H z,w y,y Tabulka 7: Symetrická hra 3 Nashova rovnováha: Ilustrace 3.1 Modely oligopolu Cournotův model oligopolu Cournotův model popisuje situaci, kdy je stejný výrobek vyráběn n firmami a firmy mohou určovat vyráběné množství. Pokud firma i vyrábí jednotek, pak jsou její náklady dány funkcí Ci(qi), která je rostoucí (pokud vyrábí více má vyšší celkové náklady). Všechny firmy prodávají za stejnou cenu, která je dána průsečíkem poptávky a celkové tržní nabídky. Pokud je tedy P(Q) inverzní poptávková funkce a firma i vyrábí množství pak je cena dána rovnicí P(qi + q2 + ■■■ + qn) a zisk firmy i je ttí — qiP(qi +q2 + ■■■ + qn) — Ci(gi)- Uvedenou situaci můžeme modelovat jako hru, kde firmy jsou hráči, jejich akcemi je množství vyráběného produktu a preference jsou reprezentovány ziskem jednotlivých firem. Řešení Cournotovy oligopolní hry ukážeme na příkladu dvou firem, které mají nákladové funkce Ci — cqi, tj. firmy mají konstantní průměrné náklady. Dále předpokládáme, že poptávková funkce je lineární, tj. P(Q) — a — Q. K nalezení Nashovy rovnováhy využijeme přístupu založeného na optimálních odpovědích. Nejprve musíme vyjádřit zisk firmy 1: tti — qx(a — qi — q2) — cqi- Abychom určili optimální odpověď firmy 1 musíme zjistit jaké množství qi maximalizuje zisk při daném množství q2 (obdobně pro firmu 2). 2gi - 92 - c = 0 2g2 - qi - c = 0 (1) ^(a-c-q2) i(a-c-gi) (2) Nashova rovnováha je dvojice (91,92) Pro n^ platí, že obě firmy hrají své optimální odpovědi, tj. q\ — bi(q2) a q2 — b2(qt). Musíme tedy najít bod, kde se funkce optimálních odpovědí protínají, tzn. vyřešit následující soustavu rovnic qi = ^ (a - c - q2) 92 = ^(a- c - gi) (3) Jejím řešením získáme Nashovu rovnováhu {q\, q2) — (|(a — c), \{ p j Řešení Bertrandova oligopolu si opět ukážeme pro případ dvou firem, lineární poptávky (D(p) — a—p) a konstantních průměrných nákladů (Ci(qi) — cqi). Zisk firmy i se potom rovná: Í(j>i - c)(a - pi) pokud p% < p j \{pt - c){a -pi) pokud pi = pj (5) 0 pokud pi > p j Stejně jako v předchozím případě je možné hru řešit pomocí optimálních odpovědí. Někdy je však možné hry řešit více neformálně pomocí úvahy. Pro každou z firem je výhodnější mít cenu nižší než konkurence, dokud je cena nad úrovní průměrných nákladů. Naopak, pokud cena klesne pod průměrné náklady, pak bude pro firmu výhodnější, stanovit vyšší cenu než konkurence, což ji zajistí nulový zisk. Jediný profil akcí, kdy nemá ani jedna z firem důvod měnit cenu a tudíž naším kandidátem na Nashovu rovnováhu je profil (j)\,p2) — (c, c). Nyní musíme ukázat, že tento profil akcí je skutečně Nashovou rovnováhou. V Nashově rovnováze si žádná z firem nemůže polepšit změnou akce. V situaci {p\ ,píj) — (c, c) je zisk obou firem 0, žádná z firem ale nemůže dosáhnou vyššího zisku změnou akce. Pokud stanoví vyšší cenu než c, pak firma nic neprodá a její zisk zůstává 0, pokud stanoví nižší cenu, pak bude její zisk záporný. Navíc můžeme ukázat, že žádný jiný profil není Nashovou rovnováhou. Kromě výše uvedeného profilu připadají v úvahu tyto situace: • Pokud pi < c nebo P2 < c pak je zisk firmy, jejíž cena je nižší, záporný a tato firma si může polepšit, pokud zvýší cenu svého výrobku na c. • Pokud pi < c,p2 > c, pak firma 1 může zvýšit svůj zisk, pokud stanoví cenu vyšší než c a nižší než p2. (Obdobně pokud p2 < c, pi > c) • Pokud pi > c,p2 > c, pak předpokládejme, že pi > P2- Firma 1 může zvýšit svůj zisk, pokud sníží cenu těsně pod p2- Profil akcí (pí,^) — (c;c) Je tedy jedinou Nashovou rovnováhou Bertrandova oligopolu. Srovnejme uvedený výsledek s rovnováhou Cournotova oligopolu. Vidíme, že celková produkce a cena velmi záleží na tom, zdali se firmy rozhodují o ceně či množství. Která z her lépe odpovídá skutečnosti, záleží na kontextu situace. Uvedené řešení modelu Bertrandova oligopolu ale závisí na předpokladu, že firmy mají konstantní mezní náklady a neomezené kapacity. Později uvidíme, jak se celá situace změní, pokud je firma omezena svými kapacitami. 3.2 Aukce Aukce jsou mechanismem, jak alokovat zdroje, tomu kdo je ochoten zaplatit nejvíce. Pravidla jednotlivých aukcí se přitom mohou významně lišit. Teorie her nám umožňuje pochopit, jak pravidla aukce ovlivňují chování účastníků aukce. Ukážeme dva základní typy aukcí first-price sealed-bid aukci (aukce probíhá obálkovou metodou a vítěz zaplatí, to co nabídl) a second-price sealed-bid aukci (opět obálkovou metodou, ale vítěz zaplatí druhou nej vyšší nabídku) Second-price sealed-bid aukce Struktura hry modelující second-price aukci je následující: • Hráči: n hráčů-účastníků aukce, kde n ^ 2. Každý hráč i si cení dražený objekt na ví. Předpokládáme, že Vi > v2 > ... > vn • Množina akcí: možné nabídky každého hráče. Nabídku hráče i značíme bi a předpokládáme, že bi ^ 0 • Preference: jsou dány výplatní funkcí Vi — b, pokud hráč i nabídl nejvyšší nabídku, b značí nejvyšší nabídku z nabídek ostatních hráčů. V jiném případě je výplata hráče i 0. Pokud více hráčů předloží stejnou nabídku, pak objekt získává hráč s nejnižším indexem. Uvedená hra má mnoho Nashových rovnováh. Sami můžete ověřit, že např. profily akcí (61, ...,bn) — (vi, 0,0) nebo {b\, ...,bn) — (v2, v\, 0,0) jsou Nashovými rovnováhami. Všimněte si také, že ve druhém případě nezíská objekt účastník, který si ho cení nejvíce. Tato rovnováha je však velmi křehká, protože hráč 2 hraje akci v\, která je slabě dominovaná akcí v2. Není příliš pravděpodobné, že by hráči hráli akce, které jsou slabě dominované. Budeme se proto ptát, zda existuje Nashova rovnováha, ve které žádný hráč nehraje slabě dominovanou akci. V second-price aukci platí, že akce bi — ví (tj. hráč nabídne přesně tolik, nakolik si dražený objekt cení) slabě dominuje ostatní akce. Důkaz tohoto tvrzení je obsažen v následujících tabulkách. Nejprve porovnejme výplaty z akce v níž hráč nabídne bi < ví oproti ví (tab. 8). Výplata hráče závisí na nejvyšší z nabídek ostatních hráčů b. b S h bi < b < Vi b>Vi bi < ví ví- b 0 0 Vi Vi- b Vi- b 0 Tabulka 8: Second-price aukce Z tabulky 8 je zjevné, že si hráč nikdy nemůže polepšit tím, že nabídne méně než je jeho ocenění. Z tabulky 9 je zřejmě, že to samé platí i pro akci, kdy hráč nabídne více než je jeho ocenění. (Stejný argument je graficky znázorněn na obr. 85.1 v Osborne) b^ Ví bi > b > Vi b>bi bi > vt Ví - b Vi - b(< 0) 0 Ví Ví - b 0 0 Tabulka 9: Second-price aukce Přestože má second-price aukce mnoho rovnováh, rovnováha kdy každý hráč nabídne přesně své ocenění (bi,b2,bn) — {v1}v2, ...,vn) je výjimečná, protože každý hráč hraje akci, která slabě dominuje ostatní. First-price sealed-bid aukce First-price aukce se od second-price aukce liší pouze v tom, že hráč s nejvyšší nabídkou zaplatí svou nabídku, a nikoliv druhou nejvyšší nabídku. Výplata vítězného hráče tedy je ví — bi. Ve first-price aukci se všechny Nashovy rovnováhy vyznačují tím, že objekt obdrží hráč, který si jej cení nejvíce. Představme si profil akcí ve kterém b2 > bi, tzn. některý z hráčů (hráč 2) nabídne více než hráč s nej vyšším oceněním (hráč 1). Pokud je b2 > v2, pak je výplata hráče 2 záporná a hráč 2 si může polepšit, pokud nabídne b2 — 0. Naopak, pokud b2 < v2, pak může hráč 1 zvýšit svou výplatu na vi — bi tím, že nabídne v\ > bi > b2. Zároveň ve všech Nashových rovnováhách musí platit, že hráč 1 nabídne stejnou částku jako byla druhá nejvyšší nabídka V opačném případě by totiž mohl hráč 1 snížit svou nabídku tak, aby stále vyhrál aukci ale zaplatil méně. Pokusme se nyní opět nalézt Nashovu rovnováhu, ve které žádný hráč nehraje slabě dominovanou akci. Můžeme tvrdit, že ve first-price aukci je akce bi > ví slabě dominována akcí bi < ví (Akce bi > ví nikdy nepřináší kladnou výplatu, naopak akce bi < ví přináší buď nulovou nebo kladnou výplatu). Naopak jakákoliv akce bi < ví není slabě dominovaná žádnou jinou akcí. Nyní víme, že V Nashově rovnováze, kde žádný z hráčů nehraje slabě dominovanou akci musí všichni hráči nabídnou méně než je jejich ocenění a hráče 1 bi musí být stejná jako je druhá nejvyšší nabídka. Takový profil akcí ale nemůže být Nashovou rovnováhou, protože hráč může nabídnout v2 > b2 > bi, čímž zvýší svou výplatu. Nashovu rovnováhu, ve které žádný z hráčů nehraje slabě dominovanou akci, můžeme ale nalézt, pokud omezíme možnosti hráčů v tom smyslu, že jim dovolíme přihazovat jen nějakou diskrétní částku e, např. 1 haléř. V takovém případě je profil akcí (v2 — e,v2 — e, 63, ...,bn), kde bi < Ví Nashovou rovnováhu, v níž žádný z hráčů nehraje slabě dominovanou akci. Pokud nyní e snižujeme k 0, pak se limitně blížíme profilu (v2,v2,b^...,bn), kde bi 5= ví. V této hře jsme tedy schopni nalézt jednu výjimečnou (i když poněkud ad hoc zvolenou) rovnováhu, v níž žádný hráč nehraje slabě dominovanou akci. Vidíme, že oba dva typy aukcí mají mnoho Nashových rovnováh. U obou her jsme ale našli jednu výjimečnou Nashovu rovnováhu, přičemž v obou těchto rovnováhách získává dražitel (prodejce) stejný výnos. 3.3 Volební soutěž Představme si situaci, kdy několik politických stran soutěží o hlasy voličů. Voliči vždy volí tu stranu, která je nejbližší jejím preferencím. Každá ze stran přitom vybírá, kam se zařadí na pravolevém politickém spektru a jejím cílem je přilákat více voličů než ostatní a vyhrát volby. Uvedenou situaci budeme modelovat pomocí Hotellingova modelu volební soutěže. • Hráči: politické strany, jejichž počet je n • Množinu akcí každé strany představuje množina pozic, které si může strana zvolit. Předpokládáme, že pozice stran, a tím pádem i preference voličů, lze reprezentovat čísly mezi 0 a 1 (což lze udělat vždy, protože výplatní funkce jsou ordinální). Pozici strany i označíme Xi • Preference stran jsou dány výplatní funkcí, která přiřadí výplatu n jediné vítězné straně, výplatu n — k straně, která se dělí o první místo s k soupeři a 0 straně, která nevyhrála. Ukážeme, si jak bude vypadat Nashova rovnováha pro případ dvou stran. Všimněte si, že neděláme žádné předpoklady o tom jak jsou rozděleny voličské preference podél intervalu [0,1]. Podstatné je pouze to že, preference mají jednu dimenzi (pravice nebo levice). Důležité postavení v našem modelu má volič s mediánovými preferencemi, označme tedy jeho pozici m. Nashovu rovnováhu můžeme nají pomocí optimálních odpovědí. Jak bude vypadat optimální odpověď strany 1 na danou pozici x2 strany 2. Pokud strana 2 zaujme pozici nalevo od mediánu, tj. x2 < m, pak bude chtít strana 1 zaujmout pozici blíže středu. Obdobně pro případ, kdy se strana 2 postaví napravo od středu. Když strana 2 zaujme pozici v mediánu x2 — m, pak je optimální odpovědí strany 1 zaujmout stejnou pozici, protože při zaujetí jakékoliv jiné pozice by prohrála. Optimální odpovědi obou stran tedy vypadají následovně: Průsečík optimálních odpovědí se nachází v bodě (m,m). Profil akcí (xi,x2) — (m,m) je tedy jedinou Nashovou rovnováhou Hotellingovy volební hry pro dvě strany. Hotellingův model přitom nemusí použit jen k analýze volební soutěže, ale také k analýze situace, kdy si firmy konkurují diferenciací svého produktu. 3.4 Odpovědnost za škodu Teorie her se používá také v oblasti Law and Economics k analýze různých právních pravidel. Vynikající shrnutí k tomuto tématu nabízejí Benoit, Kronhauser (2002). V této kapitola si ukážeme, jak pomocí teorie her modelovat situaci, kdy jeden člověk může způsobit škodu jinému člověku. Bude nás přitom zajímat, jak různé zákony určující míru odškodnění ovlivňuji chování účastníků a jaká pravidla produkují společensky žádoucí chování. Uvažujme interakci mezi viníkem (hráč 1) a obětí (hráč 2). Skoda, kterou oběť utrpí, je závislá na péči, {xi : 1 - x2 xi x2} {x2 : xi x2 1 - xi} pokud x2 m pokud x2 — m pokud x2~>im pokud xi m pokud xi — m pokud xi jí m (6) kterou oba hráči vyvinou, aby škoda nenastala. Označme očekávanou ztrátu jako L(a\,a,2) > 0. Zákon stanoví jakou část škody uhradí viník oběti. Označme tuto část jako p(a\,a,2) <= [0,1]. Hra modelující tuto situaci je definována následovně • Hráči 1 (viník) a 2 (oběť) • Množina akcí každého hráče je množina možných hodnot péče a,i e R+. Předpokládejme, že péče je měřena v peněžních částkách. • Preference hráče 1 jsou dány výplatní funkcí u\(a\, 02) — — a\ — p(a\,a2)L(a\, a\. Zbývá, nám tedy rozhodnout, zda se viníkovi nevyplatí nižší úroveň péče. V takovém případě musí viník uhradit oběti celou škodu a jeho výplata je —a\ — L{a\,a2)- Předpokládali jsme ovšem, že společensky optimální úroveň péče (aíjCJí;) maximalizuje výraz —a\ — 0,2 — L(a\,o,2)- Z toho ovšem plyne, že a\ maximalizuje výraz —ai — a*2 — L(a\,o£)- Protože a*2 je konstanta, a\ maximalizuje rovněž výraz —a\ — L(a\,a*£), což je výplata viníka pokud a\ < a\. Tím jsme ukázali, že akce a\ přináší viníkovi vyšší výplatu než jakákoliv akce cli < a\. Podívejme se nyní na optimální odpověď oběti na akci viníka a\. V případě, kdy je akce viníka a\, oběť nikdy neobdrží kompenzaci. Výplata oběti, je tím pádem «2(^1,^2) — ^«2 — L{a\,a,2)- Můžeme argumentovat stejně jako v případě viníka. Víme, že (a^a^) maximalizuje součet výplat —a\ —0,2 — L(a,\,a,2). Z toho ovšem plyne, že a\ maximalizuje rovněž výraz — 0,2 — L(a\,a,2)- Akce a\ tedy přináší oběti vyšší výplatu než jakákoliv akce 0,2 7^ aíj. Profil akcí (a^aíl) je tudíž Nashovou rovnováhou této hry. 1 pokud ai < a 02 > X2 0 pokud ai > X\ a 0,2 < X2 4 Smíšené strategie Prozatím jsme se soustředili na hry, kdy hráči deterministicky hrají jednu akci. Nyní dovolíme, aby hráči mohli hrát tzv. smíšené strategie, tj. aby mohli volit své akce podle určitého pravděpodobnostního rozdělení. Předpokládejme např., že hráč volí mezi akcemi A a B, pak hráč může hrát smíšenou strategii, kdy hraje akci A s pravděpodobností p a akci B s pravděpodobností (1 — p). Na základě platnosti zákona velkých čísel můžeme Uvedenou strategii interpretovat také tak, že v populaci jsou hráči, kteří vždy hrají A a jejich podíl v celé populaci je p. Zbylá část populace (1 — p) jsou hráči, kteří vždy hrají B. 4.1 Reprezentace preferencí pomocí očekávané výplaty Při smíšených strategiích není výsledkem hry jediná situace, ale různé situace mohou nastávat s různou pravděpodobností. Takový výsledek označujeme jako loterii. Víme, že preference ohledně deterministických situací můžeme reprezentovat pomocí výplatní funkce. Jakým způsobem ale můžeme reprezentovat preference ohledně loterií? Představme si, že existují tři možné situace a, b a c . Dále uvažujme loterie P a Q, přičemž u loterie P nastává situace a s pravděpodobností p(a), situace s p(b) a situace c s p(c). Obdobně loterie Q přiřazuje výsledkům pravděpodobnosti q(a), q(b) a q(c). Pokud hráč preferuje loterii P před loterií Q, pak (za předpokladu platnosti tzv. axiomu nezávislosti) existují čísla Ui(a), Ui(b) a Ui{c) taková že platí p{a)ui{a) + p(b)ui(b) + p(c)ui(c) > q{a)ui{a) + q{b)ui{b) + q(c)ui(c) To znamená, že vždy najdeme takovou výplatní funkci nad jednotlivými situacemi, že preference hráčů ohledně loterií lze reprezentovat pomocí očekávané hodnoty této výplatní funkce. Očekávanou hodnotu můžeme obecně zapsat jako Y^k=iP(ak)ui(a-k), kde ak jsou jednotlivé situace a p(ak) je pravděpodobnost, že nastane situace ak a Ui(ak) je výplata hráče v situaci ak- Preference hráčů ohledně loterií nazýváme von Neumann-Morgensternovy preference (vNM) a výplatní funkce ohledně jednotlivých situací, které reprezentují vNM preference, nazýváme Bernoulliho výplatní funkce. Dříve jsem řekli, že jedny a ty samé preference jsou reprezentovány všemi výplatními funkcemi, které zachovávají pořadí preferovaných situací. Také jedny a ty samé vNM preference mohou být reprezentovány více Bernoulliho funkcemi. Nyní ovšem nestačí, aby Bernoulliho funkce zachovávali pořadí. Pokud mají Bernoulliho výplatní funkce reprezentovat stejné vNM preference, pak musí zachovat očekávanou hodnotu loterie, což je ekvivalentní tomu, že jsou si navzájem lineární transformací. Řečeno formálněji: Máme Bernoulliho výplatní funkce u(x) a v(x). Jejich očekávaná hodnota reprezentuje ty stejné vNM preference, právě tehdy když existují čísla a a b taková, že u(x) — a + bv(x) pro každé x. 4.2 Nashova rovnováha ve smíšených strategiích Nyní budeme definovat hru se smíšenými strategiemi a její Nashovu rovnováhu. Pokud umožníme hráčům hrát smíšené strategie, pak budeme požadovat, aby hráči měli vNM preference nad loteriemi složenými z profilů akcí. Definice 7. Strategická hra s vNM preferencemi se skládá z • množiny hráčů • množiny akcí každého hráče • preferencí každého hráče definovaných nad množinou loterií složených z profilů akcí Definice 8. Smíšenou strategií hráče ve strategické hře je pravděpodobnostní rozdělení nad množinou jeho akcí. Značíme jej on, cti(ai) je pravděpodobnost jakou připisuje strategie cti hráče í akci a,i- Definice 9. Profil smíšených strategií a* ve strategické hře s vNM preferencemi je Nashovou rovnováhou, pokud pro každou smíšenou strategii cti každého hráče i platí Ui(a*) > Ui{cti,a*_Ä, kde Ui(a) představuje očekávanou výplatu hráče i ze smíšeného profilu akcí a. Vidíme, že Nashova rovnováha je definována velmi podobně jako u čistých strategických her. Žádný z hráčů nemůže jednostrannou změnou strategie zvýšit svoji výplatu. Oproti čistým strategickým hrám ale nyní platí, že každá hra s vNM preferencemi, ve které má každý z hráčů konečně mnoho akcí, má Nashovu rovnováhu ve smíšených strategiích. Toto tvrzení nám ale nijak nepomůže při hledání rovnováh, pouze víme, že ve smíšených strategiích vždy nějaká existuje. 4.3 Hledání Nashovy rovnováhy ve smíšených strategiích I u her se smíšenými strategiemi můžeme použít k hledání Nashových rovnováh metodu optimálních odpovědí. U složitějších her však existuje účinnější metoda, jak nalézt Nashovu rovnováhu. Tato metoda je založena na určité vlastnosti smíšených Nashových rovnováh, kterou nyní ukážeme. Podívejme se nejprve na hru dvou hráčů s dvěma akcemi, která je dána tabulkou 10. Hráč 1 si volí mezi akcemi T a B, přičemž jeho strategie a\ připisuje akci T pravděpodobnost p a akci B pravděpodobnost (1 — p). Hráč 2 si volí mezi akcemi L a R. Při své strategii «2 hraje akci L s pravděpodobností q a akci R s pravděpodobností (1 — q). Pole tabulky tentokrát označují s jakou pravděpodobností nastává daný výsledek. L(q) R(l-q) T(P) pq p(l - q) B(l-p) (í-p)q (í-p)(í-q) Tabulka 10: Očekávanou výplatu hráče 1 tak můžeme zapsat jako pqu^T, L) + p(l - q)Ul(T, R) + q(l - p)Ul(B, L) + (1 - p)(l - q)Ul(B, R) což lze také zapsat jako p[gui(T, L) + (1 - q)Ul(T, R)} + (1 - pftqu^B, Ľ) + (1 - q)Ul(B, R)} Výraz v první hranaté závorce představuje očekávanou hodnotu výplaty hráče 1, když hraje akci T a hráč 2 hraje strategii «2- Výraz v druhé hranaté závorce představuje očekávanou hodnotu výplaty hráče 1, když hraje akci B a hráč 2 hraje strategii «2- Označme tyto očekávané výplaty hráče 1 jako E{u\(T,ct2)) a E{u\{B,ct2))- Celkově tedy můžeme očekávanou výplatu hráče 1 při strategii ct\ zapsat jako pE(ui(T, «2)) + (1 — p)E(ui(B, «2)), tj. jako vážený průměr výplat z čistých akcí. Uvedený příklad lze zobecnit. Platí, že očekávaná výplata ze smíšené strategie je vážený průměr očekávaných výplat připsaných profilům smíšených strategií typu (ai, a-i), kde vahami jsou pravděpodobnosti cti(a,i), které smíšená strategie hráče i připisuje jeho jednotlivým akcím. Symbolicky zapsáno je výplata hráče i: Ui(a) — Yľj=i ai(aj)Ei(a,j,ct-i). Tato skutečnost vede k následujícímu tvrzení. Propozice 2. Ve hře s vNM preferencemi v níž má každý hráč konečně mnoho akcí je profil smíšených strategií a* Nashovou rovnováhou právě tehdy, když • očekávaná výplata každé akce, které připisuje strategie a* kladnou pravděpodobnost, je při daných strategiích a*_i stejná • očekávaná výplata každé akce, které připisuje strategie a* nulovou pravděpodobnost, není pří daných strategiích a*_i vyšší než očekávaná výplata akce, které je připsána kladná pravděpodobnost. Toto tvrzení nám přináší důležitý poznatek. Hráč, který volí určité strategie ve smíšené rovnováze s pozitivní pravděpodobností, musí být indiferentní mezi všemi těmito strategiemi, tj. každá smíšená Nashova rovnováha je neostrá. Jinými slovy, všechny akce zvolené s pozitivní pravděpodobností mu musejí přinášet stejnou výplatu. Tato výplata je větší nebo roven výplatě, který přinášejí ty akce, které s kladnou pravděpodobností voleny nejsou. V následujícím příkladu si ukážeme, jak se tohoto tvrzení dá využít při hledání Nashovy rovnováhy. 4.4 Příklady Nashovy rovnováhy Hlava nebo orel Hra hlava nebo orel je definována tabulkou 4. Označme ph a p0 pravděpodobnost s jakou hráč 1 hraje akce hlava a orel. Obdobně qu a q0 označuje pravděpodobnost s jakou hráč 2 hraje akce hlava nebo orel. Samozřejmě musí platit qu + q0 — 1 Víme, že hra nemá rovnováhu v čistých strategiích. Víme tedy že hráč hraje obě akce s kladnou pravděpodobností a výše uvedené tvrzení říká, že výplata z obou akcí musí být při dané strategii druhého hráče stejná. Pro hráče 1 tedy musí platit: u\(H, q) — u\(0, q), obdobně pro hráče 2 u2(p, H) — u2(p, O). Po dosazení získáme soustavu rovnic: qh- qa = -qh + qa -Ph +Po=Ph-Po qh + qa = í Ph+Po=í Její řešení je ph — 1/2, p0 — 1/2, qh — 1/2, qQ — 1/2, V Nashově rovnováze tedy oba dva hráči hrají každou z akcí s pravděpodobností 1/2. Expertní posouzení Hra expertní posouzení má dva hráče - zákazníka a experta. Zákazníkovi se pokazí nějaká cenná věc (např. auto), vyhledá proto experta (automechanika), který závadu posoudí a doporučí opravu. Závada přitom může být velká nebo malá, což ale pozná a ví jen expert. Pravděpodobnost, že je závada velká označíme r. Předpokládejme, že expert získá zisk ir, ať už opravuje velkou či malou závadu. Expert má však také možnost označit malou závadu za velkou a opravit ji jako velkou, v takovém případě získá zisk ir' a platí ir' > ir. Pokud zákazník přijme expertovu diagnózu, tak zaplatí expertovi E za velkou opravu a / za malou opravu. Pokud ale expert doporučí velkou opravu, pak nemusí zákazník expertovi důvěřovat a může vyhledat dalšího experta, který věc znovu posoudí. V tomto případě jsou jeho náklady E' v případě, že druhý expert doporučí velkou opravu a ľ v opačném případě. Platí přitom: E' > E > ľ > I. Výplaty jsou potom dány tabulkou [?], kde p a q opět označují pravděpodobnost, s níž jsou hrány odpovídající akce. Přijme(q) Odmítne (1-q) Pravda(p) 7T, — rE — (1 — r)I (1 -r)7r, -rE' - (1 -r)I Lež(l-p) m + (l- r)ir', -E 0, -rE' + (1 - r)ľ Tabulka 11: Expertní odhad Pro r e (0,1) hra nemá čistou rovnováhu (Ověřte). Jak vypadá rovnováha ve smíšených strategiích? Opět vyjdeme z toho, že výplaty z akcí, jenž jsou hrány s pozitivní pravděpodobností musí být, při dané strategii druhého hráče, stejné. Očekávaná výplata experta z akce, kdy mluví pravdu tak musí být stejná jako výplata z akce, kdy lže. qir + (1 — q)(l — r)ir — qrir + q(í — r)ir' Stejná úvaha platí i pro zákazníka. Jeho očekávaná výplata v situaci, kdy důvěřuje musí být stejná jako v situaci, kdy expertovi nedůvěřuje. p(-rE - (1 - r)I) + (1 - p){-E) = p(-rE' - (1 - r)I) + (1 - p){-rE' + (1 - r)ľ) Po algebraických úpravách získáme následující hodnoty p* a q* a tím pádem i Nashovu rovnováhu. , E - (rE' + (1 - r)ľ) P (í-r)(E-ľ) 1 = — 7T Promyslete, jak rovnovážné strategie a Nashova rovnováha závisí na parametrech r,ir,E a ľ. Dobrý samaritán Následující hra má mnoho možných interpretací. Palfrey, Rosentahl (1984) pomocí této hry modelují situaci, kdy se každý ze skupiny n individuí rozhoduje, zda přispěje fixní částkou na veřejný statek (nebo na charitu). V naší interpretaci půjde o situaci, kdy se každý svědek zločinu rozhoduje, zda zavolá policii. Hra je definována následovně • n hráčů • Množina akcí každého hráče Ai — {volat, nevolat} • Preference každého hráče jsou reprezentovány výplatní funkcí, která připisuje hodnotu 0 situaci, kdy nikdo nezavolá. Pokud někdo zavolá získá hráč výplatu v. Pokud hráč sám zavolá, nese náklady ve výší c, kde c < v. Tzn. jeho výplata je v — c > 0. Je zjevné, že hra má několik Nashových rovnováh, ve kterých právě jeden hráč zavolá a ostatní nikoliv. Tyto situace jsou pareto-efektivní. V případě, že bychom tuto hru interpretovali jako přispívání na veřejný statek, znamená tato rovnováha, že veřejný statek může být soukromě poskytnut. Je ovšem otázka, jakým způsobem se jedinci mohou zkoordinovat na této rovnováze. V případě hlášení zločinu může tuto rovnováhu zajistit určitá sociální norma (např. policii volá nejstarší), v případě přispívání na veřejné statky je obtížné si takovou normu představit. Důvodem proč je tato rovnováha pochybná, je její asymetrie. Ve hře se objevuje n hráčů ze stejné populace, kteří se ale ve stejné situaci nechovají stejně. Podívejme se proto, jak vypadá symetrická rovnováha. Je snadné ověřit, že neexistuje žádná symetrická rovnováha v čistých strategiích. Uvažujme nejprve situaci, kdy všichni hráči volají. V takové situaci se vyplatí kterémukoliv z nich nevolat, protože zvýší svoji výplatu z v — c na v. Pokud nikdo z hráčů nezavolá, pak se každému hráči vyplatí zavolat, protože zvýší svoji výplatu z 0 na v — c. Symetrickou rovnováhu tedy nalezneme jen ve smíšených strategiích. Jak bude vypadat smíšená rovnováha? Pro rovnovážnou smíšenou strategii musí platit, že hráč je indiferentní mezi akcemi, které hraje s nenulovou pravděpodobností. V naší hře tudíž musí platit v - c = (1 - p)n_10 + (1 - (1 - j3)™-> =*(1 - PT'1 = - v kde p označuje pravděpodobnost, že daný hráč zavolá. Z tohoto výrazu můžeme vyjádřit rovnovážnou pravděpodobnost zavolání v Jak se mění pravděpodobnost zavolání v závislosti na velikosti skupiny? Čím vyšší je n, tím menší je l/(n — 1) a tím větší je (^)™=i. Pravděpodobnost p je tedy klesající v n, Pravděpodobnost, že daný hráč zavolá, tudíž klesá s počtem lidí ve skupině. Zajímavější je ovšem otázka, jak se s velikostí skupiny mění pravděpodobnost, že alespoň jeden člověk zavolá. Pravděpodobnost, že nikdo nezavolá, můžeme jednoduše vyjádřit jako Prjnikdo nezavolá} — Pr{i nezavolá}Prjnikdo jiný nezavolá} — (1 — p)(l — p)"^1 Dosadíme-li do tohoto výrazu rovnovážnou pravděpodobnost zavolání, získáme C 1 C C n Pr{nikdo nezavolá} — (-)^^t- = (_)tt=t v v v Tato pravděpodobnost je rostoucí v n. Čím větší je tedy skupina, tím menší je pravděpodobnost, že někdo zavolá a nahlási zločin. Pokud bychom interpretovali tuto hru jako přispívání na veřejné statky, pak vidíme, že veřejné statky budou soukromě poskytnuty spíše v malé než ve velké skupině. 4.5 Dominované akce Koncept dominovaných akcí nám může usnadnit řešení hry, protože platí, že ostře dominovaná akce není v žádné Nashově rovnováze hrána s kladnou pravděpodobností. Pokud tedy hledáme smíšené Nashovy rovnováhy můžeme předtím eliminovat ostře dominované akce. Definice 10. Ve strategické hře s vNM preferencemi hráčova strategie ai ostře dominuje jeho akci o!it pokud pro všechny akce ostatních hráčů a—i platí V\(ai, a_j) > «i(a-,a_i). Akce o!i je ostře dominovaná. 5 Extenzivní hry s dokonalými informacemi Ve strategických hrách předpokládáme, že rozhodnutí hráčů jsou prováděna ve stejný okamžik. V extenzivních hrách tento předpoklad opustíme a zaměříme se na situace, kdy se hráči rozhodují sekvenčně, tj. jeden po druhém. Jako příklad extenzivní hry si můžeme představit šachy nebo piškvorky. Je přirozené, že v extenzivních hrách bude volba akce ovlivněna předchozím průběhem hry. 5.1 Definice extenzivní hry Abychom popsali extenzivní hru, potřebujeme, stejně jako ve strategické hře, specifikovat hráče a jejich preference. Navíc ale musíme říci v jakém pořadí hráči hrají a jaké akce mají hráči k dispozici v každém okamžiku hry. Za tímto účelem definujeme množinu všech sekvencí akcí, které se mohou ve hře objevit. Každou takovou sekvenci označujeme jako konečnou historii. Dále musíme říci, který hráč táhne v kterém bodě každé sekvence. To zajistí tzv. hráčská funkce, což je funkce, která každému bodu v každé konečné historii přiřadí hráče, který právě hraje. Abychom si lépe představili, co je konečná historie, podívejme se na hru znázorněnou diagramem 1. Vyzyvatel 2,1 0,0 Obrázek 1: Hra o vstup do odvětví Tato hra znázorňuje situaci, kdy se jedna firma (vyzyvatel) rozhoduje o vstupu do odvětví, ve kterém působí jiná firma (monopolista). Pokud tato firma vstoupí do odvětví (Vstup), pak firma, která v odvětví již působí může začít konkurenční boj (B) nebo se situací smíří (S). Uvedená hra má tři konečné historie (Vstup,Smířit se)(Vstup,Boj) a (Ven). Konečná historie je tedy série akcí, které si hráči volí a která vede od počátku hry až k jejímu konci. Každá konečná historie má tzv. vlastní podhistorie, což jsou podmnožiny konečné historie, které vedou od počátku hry, ale nevedou až k jejímu konci. Formálně řečeno, pokud sekvence akcí (ai, a2,am) je konečná historie, pak sekvence akcí (ai, a2,ak), kde k < m a prázdná sekvence 0 jsou jejími vlastními podhistoriemi. V našem příkladu pak konečná historie (Vstup,Smířit se) obsahuje vlastní podhistorie 0 a (Vstup). Definice 11. 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í Stejně jako u strategických her, také u extenzivních her můžeme preference reprezentovat pomocí výplatní funkce. Klíčovým konceptem extenzivních her je strategie. Strategie říká hráči, kterou akci má hrát v každém okamžiku, kdy na něj přijde řada. Definice 12. 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 z množiny A{h), tj. množiny akcí dostupných po historii h. Co to strategie vlastně je, nám může přiblížit následující příklad na obrázku 2. Můžeme vidět, že hráč 1 se rozhoduje jen na začátku hry, tj. hráčská funkce P{z) — 1, a má na výběr jen ze dvou akcí C a D. Má tedy na výběr jen ze dvou možných strategií, jedna připisuje prázdné historii akci C a druhá připisuje prázdné historii akci D. Zapisujeme si(0) — C resp. si(0) — D. Naopak hráč 2 hraje, jak po akci C, tak po akci D, přičemž může volit z akcí i? a F po historii C a akcí G a H po historii D. Celkově má tedy hráč 2 na výběr z následujících čtveřice strategií • s2(C)=E, s2(D) = G 2,1 3,0 0,2 1,3 Obrázek 2: příklad • s2(C)=E, s2(D) = H . s2(C) = F, a2(D) = G • a2(C) = F, a2(F) = F Zkráceně můžeme tyto strategie značit jako EG, EH, FG, FH. Při tomto zkráceném zápisu uvádíme nejprve akce, které jsou v herním diagramu blíže začátku hry a v případě, že se objevují na stejném stupni postupujeme zleva doprava dle toho, jak jsou akce zapsány v herním diagramu. Strategii si lze tedy představit jako popis toho, jak bude hráč ve hře postupovat. V mnoha případech nám však strategie říká více než jak ve hře postupovat - říká nám, 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 nebo jako přesvědčení ostatních hráčů o tom, jakou akci daný hráč zvolí. Ukažme si tuto skutečnost na příkladě. 1,2 0,0 Obrázek 3: Strategie Uvažujme hru na obrázku 3. Hráč 1 má 4 strategie CG, CH, DG, DH. Je ovšem jasné, že po akci D hrané na začátku hry se hráč nemůže dostat do bodu, kde se rozhoduje mezi akcemi F a G. Jak tedy můžeme chápat strategie DH a DG? Možnosti jsou dvě. Za prvé si můžeme představit, že hráč 1 někdy udělá chybu a dostane se k rozhodování mezi akcí F a G. Strategie potom specifikuje jakou akci by si hráč vybral. Za druhé můžeme strategie interpretovat jako očekávání druhého hráče. Strategii DH tedy můžeme vyložit tak, že hráč 1 hraje na začátku hry akci D. Hráč 2 přitom očekává, že v případě rozhodování mezi akcí F a G si hráč 1 vybere akci F. Strategie jednotlivých hráčů jasně determinují výsledek hry, tj. konečnou historii, a tudíž i výplaty hráčů. Konečnou historii, která se objeví při profilu strategií a, označme O(s). V našem příkladu tedy např: 0(D, EG) — (DG), tzn. pokud hráč hraje strategii D a hráč 2 strategii FG, pak výsledkem hry je konečná historie DG. Výplatu, kterou obdrží hráč i při profilu strategií a, můžeme zapsat jako uí(0(s)). 5.2 Nashova rovnováha Definice 13. V extenzivní hře s dokonalými informacemi je profil strategií s* Nashovou rovnováhou, jestliže pro každého hráče í a každou strategii platí, že 0(s*) je alespoň tak preferováno jako 0((ri, s*_j)) neboli Ui(0(s*)) > ul(0(rl,s*_l)). Nashova rovnováha v extenzivních hrách tedy představuje takový profil strategií, kdy se při daných strategiích ostatních hráčů nevyplatí žádnému hráči odchýlit se. Jedním ze způsobů, jak nalézt Nashovu rovnováhu v hrách s konečných počtem strategií je vypsat všechny strategie a jim příslušné výplaty do tabulky, která je pak označována jako strategická forma extenzivní hry. V ní je možné nalézt Nashovu rovnováhu stejným způsobem jako ve strategické hře. Ukážeme si tento postup na příkladu z obrázku 2. Ukázali jsem, že hráč 1 má na výběr ze strategií C a D, zatímco hráč má k dispozici strategie EG, EH, FG, FH. Strategická forma této extenzivní hry je tedy dána tabulkou 12. C D EG 2,1 0,2 EH 2,1 1,3 FG 3,0 0,2 FH 3,0 1,3 Tabulka 12: Strategická forma extenzivní hry z příkladu 2 Nyní je již snadné určit, že Nashova rovnováha je profil strategií(D,EH). Všimněme si, že tento profil akcí nám říká nejen to, že hráč 1 hraje v Nashově rovnováze akci D a hráč 2 na to reaguje akcí H, ale také to, že hráč 2 by hrál E, kdyby hráč 1 hrál akci C. Takový závazek daného hráče ale nemusí být vždy kredibilní. Co tato nekredibilita znamená? Představme si, že hráči hrají nějakou extenzivní hru. Na začátku hry hráči popíší pomocí svých strategií, jak budou v průběhu hry postupovat. Nashova rovnováha je potom taková situace, kdy si žádný hráčů nemůže polepšit tím, že nahlásí na začátku hry jinou strategii při dané strategii ostatních hráčů. Je ovšem možné, že v některých okamžicích kdy je hráč na tahu, nemusí být pro hráče výhodné držet se své strategie a bude se chtít odchýlit. Nekredibilitu určitého závazku lze demonstrovat příkladu hry o vstup do odvětví, [obrázek 1]. Tuto hru lze zapsat ve strategické formě dané tabulkou 13 Smířit se Boj Vstup 2,1 0,0 Ven 1,2 1,2 Tabulka 13: Strategická forma extenzivní hry vstup do odvětví Vidíme, že hra má dvě Nashovy rovnováhy (Vstup, Smířit se) a (Ven, Boj). Problém v tomto případě vyvstává u rovnováhy (Ven, Boj). Tento profil strategií znamená, že vstupující firma (vyzyvatel) nevstoupí do odvětví, ale kdyby vstoupil, tak v odvětví působící firma (monopolista) se zavázala hrát akci Boj. Pokud by se ale firma dostala do této situace, pak je pro ni výhodnější hrát akci smířit se. Závazek hrát akci Boj je tudíž nekredibilní. Skutečnost, že profil akcí (Ven, Boj) je problematickou rovnováhou, lze zdůvodnit i jinak. Ve strategických hrách interpretujeme Nashovu rovnováhu jako situaci, kdy hráči, díky svým zkušenostem se hrou, správně očekávají akce ostatních hráčů a hrají svou nejlepší odpověď na tyto akce. Ve hře o vstup do odvětví, ale vstupující firma hrající Ven, nikdy nepozoruje akci firmy působící v odvětví, protože tato firma se nikdy nedostane ke hře. Jak ale potom může být přesvědčena, že bude hrát akci Boj? Z tohoto problému můžeme uniknout, když budeme Nashovu rovnováhu v extenzivní hře interpretovat tak, že ve vzácných případech hráči podnikají nerovnovážné akce (např. omylem). V našem příkladu to tedy znamená, že vstupující firma výjimečně zahraje akci Vstup a pak může pozorovat, co dělá firma působící v odvětví. Při této interpretaci se ale v našem příkladu znovu objevuje problém. Po akci Vstup je totiž pro firmu působící v odvětví lepší, když hraje akci Smířit se. Nashova rovnováha (Ven, Boj) tudíž není robustní a závazek firmy působící v odvětví hrát Boj po akci Vstup není kredibilní. 5.3 Dokonalá rovnováha vzhledem k podhrám (SPE) V předchozím odstavci jsme viděli, že Nashova rovnováha není vhodným konceptem rovnováhy pro některé extenzivní hry, protože ignoruje sekvenční strukturu hry a umožňuje, aby hráči na začátku přijímali nekredibilní závazky. Tento problém odstraníme zavedením konceptu dokonalé rovnováhy vzhledem k podhrám (subgame perfect equilibrium - SPE). Nejprve definujeme podhru. Definice 14. T 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 T, definujeme podhru T (ti) následující po historii h jako extenzivní hru, kde • Hráči jsou stejní jak hráči ve hře T • Konečné historie tvoří množina všech sekvencí akcí h! takových, že sekvence (h, h') je konečnou historií hry T. • Každý hráč preferuje h! před h", právě tehdy když preferuje (h, h') před (h, h") Podhra je tedy část hry, která následuje poté, co už byla část hry odehrána. Všimněte si, že v každé hře je vlastní podhistorii také prázdná historie 0 a podhra, která po ní následuje je celou hrou. Jednou z podher každé hry je tedy hra samotná. Podíváme-li se na hru znázorněnou na obrázku 2, pak tato hra má 3 podhry: celou hru a dvě podhry znázorněné na obrázku4: 2 2 g/\h 2,1 3,0 0,2 1,3 Obrázek 4: vlastní podhry hry 2 Idea dokonalé rovnováhy vzhledem k podhrám (SPE) je založena na myšlence, že hráči se chovají optimálně v každé podhře. Neformálně můžeme říci, že SPE je profil strategií, pro něž platí, že při daných strategiích ostatních hráčů si v žádné podhře nemůže hráč polepšit jednostrannou změnou strategie. Formálně lze SPE definovat následovně: Definice 15. Profil strategií s* je dokonalou rovnováhou vzhledem k podhrám, jestliže pro každého hráče í, každou historii h, po které hráč í hraje, a každou strategii hráče i platí, že konečná historie Oh(s*) generovaná strategiemi s* po historii h je alespoň tak preferovaná jako konečná historie 0/i(rj, s!_j) generovaná strategiemi rj,s!_j po historii h, tj. Ui(Oh(s*)) > Ui(Oh(fi,s*_j)) Podstatnou změnou oproti Nashově rovnováze je požadavek, že hráčova strategie musí být optimální po každé historii po níž hráč hraje, nejen na začátku hry. SPE můžeme interpretovat jako neměnný stav, ve kterém hráči ve výjimečných okamžicích hrají nerovnovážné akce, což umožňuje ostatním hráčům, aby si utvořili správná očekávání ohledně, toho jak se hráči chovají v každé podhře. Za těchto očekávání se žádný hráč v SPE nechce odchýlit od své strategie ani na začátku hry, ani v průběhu hry. Z definice SPE navíc plynou dvě vlastnosti: 1. Každá SPE je Nashovou rovnováhou. 2. SPE odpovídá Nashově rovnováze v každé podhře. To znamená, že profil strategií, který je SPE, je také Nashovu rovnováhou v každé podhře a zároveň profil strategií, který je Nashovou rovnováhou v každé podhře, tvoří SPE. Na závěr se podívejme, jak vypadají SPE ve hře vstup do odvětví [2]. Víme, že hra má dvě Nashovy rovnováhy (Vstup, Smířit se) a (Ven, Boj). Z vlastností SPE víme, že žádné jiné SPE ve hře být nemohou. Uvažujme nejprve profil s* — (Ven, B). Vezměme si monopolistu a podhru následující po historii h — Vstup. Strategie monopolisty vede ke konečné historii Oh(s*) — (Vstup, B). Výplata monopolisty pro tuto historii je um(Vstup, B) — 0, zatímco um(Vstup, S) — 1. Monopolista si tak může v podhře následující po akci vstup polepšit a uvedený profil proto netvoří SPE. Naopak profil s* — (Vstup, S) je SPE, protože: • v podhře po historii h — 0, tj. na začátku hry, je strategie vyzyvatele optimální, protože strategie s* vede ke konečné historii Oh(s*) — (Vstup, S) a uv(Vstup, S) — 2, zatímco uv(Ven, S) — 1. • v podhře po historii h — Vstup, je strategie monopolisty optimální, protože strategie s* vede ke konečné historii Oh(s*) — (Vstup, S) a um(Vstup, S) — 1, zatímco um(Vstup, B) — 0. 5.4 Zpětná indukce V předchozí kapitole jsme viděli jeden z možných způsobů, jak nalézt SPE - nalézt Nashovy rovnováhy a poté zkontrolovat, zdali se jedná o SPE. Pro extenzivní hry s konečným horizontem naštěstí existuje jednoduchý algoritmus, jak nalézt SPE jednodušeji, tzv. zpětná indukce. Zpětnou indukci můžeme popsat následovně: • Pro každou podhru délky 1 (poslední podhra) najděte optimální akce hráče, který je na tahu. Označme S*(l) množinu optimálních akcí podhry j. (Pokud existuje jediná nejoptimálnější akce, pak S*(l) obsahuje jediný člen.) • 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 získáme profily strategií pro podhry délky, označme je S f (2). • Takto pokračujeme, dokud nedojdeme na začátek hry. Profily strategií, které takto získáme tvoří SPE. Zpětná indukce tedy funguje tak, že začneme na konci hry a najdeme optimální akce v posledních podhrách. Poté postoupíme výše za předpokladu, že hráči budou v posledních podhrách hrát své optimální akce a najdeme optimální akce hráče, který táhne o úroveň výše. Takto postupujeme, až na začátek hry. Zpětnou indukci můžeme ilustrovat na příkladu 5 • Hra má jen jednu podhru délky 1, v níž hraje hráč 1 a má na výběr akce G a H. Akce G je přitom zjevně optimální, protože mu přinese vyšší výplatu než akce H. • Podhra délky 2 je opět jen jedna a první je v ní na tahu hráč 2. Předpokládáme, že pokud bude hrát E, pak hráč 1 hraje G a hráč 2 získá výplatu 2. Akce F mu oproti tomu přináší výplatu 1. Akce E je tudíž pro něj optimální • Na začátku hraje hráč 1 a volí mezi akcí C a D. Akce C vede ke konečné historii (C,E,G), která mu přináší výplatu 1. Akce D přináší výplatu 2 a je tudíž optimální. SPE této hry je profil akcí ((A G), (E)). 1,2 0,0 Obrázek 5: Zpětná indukce Na závěr kapitoly zmiňme dvě důležitá tvrzení Propozice 3. Množina dokonalých rovnováh vzhledem k podhrám je ekvivalentní množině profilů strategiích generovaných algoritmem zpětné indukce. Propozice 4. Každá extenzivní hra s konečným horizontem a dokonalými informacemi má dokonalou rovnováhu vzhledem k podhrám. 6 Extenzivní hry: Ilustrace 6.1 Ulimátní hra Ultimátní hra je velmi známou hrou z ekonomických experimentů. Vypadá tak, že jeden z hráčů, (např. hráč 1) dostane určitou částku c a tu rozdělí na dvě části, jednu z části nabídne druhému hráči. Pokud tento hráč částku přijme, pak oba hráči získají příslušnou částku. Pokud částku odmítne, pak nikdo nezíská nic. Formálně můžeme hru zapsat takto: • Hráči: 1,2 • Konečné historie: Množina sekvencí (x, Z), kde x je částka nabídnutá hráči 2, přičemž 0 5= x 5= c. Z nabývá hodnot y(přijme) nebo ^(odmítne). • Hráčská funkce: P(0) = 1, P{x) = 2 • Preference: Výplata hráče je dána částkou, kterou obdrží, tj. u\{x, Y) — c—x, u2(x, Y) — x, u\{x, N) — 0, u2(x,N) = 0 Jelikož se jedná o hru s konečným horizontem můžeme k hledání SPE použít zpětnou indukci. Nejprve uvažujme podhru délky 1, ve které se hráč 2 rozhoduje, zda přijmout či odmítnout. Pokud je x > 0, pak optimální akcí hráče 2 je nabídku přijmout. Pokud je x — 0, pak hráč 2 je indiferentní mezi přijmutím a odmítnutím akce a může nabídku jak přijmout, tak odmítnout. Nyní se zaměřme na celou hru. Pro každou kombinaci optimálních akcí hráče 2, hledáme optimální strategii hráče 1. Existují dvě možnosti: 1. Hráč 2 přijme jakékoli x ^ 0, pak je optimální odpovědí hráče 1 nabídnout x — 0. 2. Hráč přijme jakékoli x > 0 a odmítne x — 0, pak hráč 1 nemá optimální strategii, protože pro jakékoliv x lze nalézt nabídku, která bude nižší a hráč 2 ji stále akceptuje. Jedinou SPE je tedy profil strategií, kdy hráč 1 nabídne i = 0a hráč 2 akceptuje každou nabídku. Může se zdát podivné, proč by měl hráč 2 akceptovat i nulovou nabídku, když v případě jejího odmítnutí obdrží stejnou výplatu. Hráč 2 však bude akceptovat jakkoliv malou nenulovou nabídkou. Taková nabídka ovšem neexistuje, protože množina nabídek striktně větších než nula je otevřená a nemá tudíž minimum, což znamená, že jakákoliv nabídka je dominována nějakou nižší nabídkou. Například nabídnutí částky 0,1 je dominováno nabídnutím částky 0,01, což je dominováno nabídnutím částky 0, 001 atd. Tento problém ale zmizí pokud předpokládáme, že peníze nejsou nekonečně dělitelné. Představme si, že dovolíme hráči 1, aby dával nabídky pouze v celých haléřích. V případě kdy hráč 2 akceptuje jen x > 0, je optimální strategií hráče 1 nabídnout nejmenší možnou nenulovou částku, tedy 1 haléř. Akceptace nulové nabídky je tudíž jen artefakt toho, že jsme modelovali možné nabídky jako spojitou proměnou. V každé takové hře, kdy je hráč indiferentní mezi přijmutím a odmítnutím nějaké nabídky, můžeme bez komplikací předpokládat, že hráč tuto nabídku akceptuje. (V opačném případě by totiž dostal o trochu vyšší nabídku, kterou by již striktně akceptoval.) 6.2 Stacklebergův model oligopolu U Cournotova a Bertnardova modelu oligopolu jsme předpokládali, že firmy se rozhodují současně, nyní budeme předpokládat, že se firmy rozhodují o objemu produkce postupně. Nejprve se rozhoduje firma 1 a poté firma 2. Firma 1 své rozhodnutí nemůže následně měnit. Tento model oligopolu je znám jako Stacklebergův oligopol. Formálně můžeme hru Stacklebergova duopolu zadat následovně: • Hráči: Firmy 1 a 2 • Konečné historie: Množina sekvencí (qi, q2), kde qi je produkce firmy i • Hráčská funkce: P(0) = 1, P{qx) = 2 • Preference: Výplatní funkce firmy i je dána jejím ziskem, tj. qiP(qi + q2) — Ci(qi), kde P(qi + q2) je tržní cena, pokud je na trh dodáno množství qi + q2. Ci(qi) jsou náklady firmy při výrobě množství qi. SPE nalezneme opět pomocí zpětné indukce. Musíme tedy nejprve vyřešit, jak se rozhoduje firma 2 v podhře o délce 1. A poté najdeme optimální strategii firmy 1 na začátku hry při dané strategii firmy 2. 1. V podhře po historii h — (qi) zná firma 2 produkci firmy 1 a volí takovou produkci q2, aby maximalizovala svůj zisk. Množství produkce firmy 2 je tedy dáno optimální odpovědí firmy 2 stejně jako v Cournotově oligopolu. Označme toto množství jako q2, tj. b2(qi) — q2 2. V podhře po historii h — 0 volí firma 1 q±, které maximalizuje její zisk. Víme přitom, že pokud firma vyrobí qi, pak firma 2 vyrobí b2(qi) a cena bude P(qi + b2(qi)). Firma 1 tedy v SPE maximalizuje výraz qiP(qi +b2(qi)) — C\(qi). Označíme-li řešení tohoto problému jako q{, můžeme říci, že SPE tvoří profil strategií (qt,q2) Pro lepší představu se podívejme, jak bude vypadat SPE v případě konstantních průměrných nákladů a lineární poptávkové křivky. Předpokládejme, že funkce nákladů Ci(qi) — cqi pro i — 1,2 a poptávková křivka je P(Q) — a — Q. Zadání je tedy stejné jako v našem případě Cournotova oligopolu. Za těchto podmínek má firma 2 tuto optimální odpověď (odvozeno o Cournotova oligopolu) h(qi) = ^(a- c - gi) Firma 1 vyrábí v SPE takové qi, aby maximalizovala svůj zisk tti = qi(a - (gi + ^(a - c-qi)) - Ci) = ^qi(a -c-qi) maximum nalezneme, pokud výraz zderivujeme podle qi položíme rovno nule d7ri lí \ n dq-r~2{a-C)-qi^° Řešením těchto dvou rovnic získáváme produkci firem v SPE Srovnejme tento výsledek s Cournoutovým oligopolem. V Cournotově hře dosahovaly obě firmy stejného výstupu. Nyní ale vidíme, že produkce firmy 1 je vyšší. V návaznosti na to dosahuje firma 1 také vyššího zisku. Firma, která si volí svůj výstup jako první, je na tom ve Stacklebergově hře lépe než kdyby se hrála Cournotova hra. Dokonce můžeme tvrdit, že pokud máme jakoukoliv poptávkovou křivku a jakoukoliv nákladovou funkci, při nichž má firma 2 jedinečnou nejlepší odpověď na každý výstup firmy 1, pak na tom firma 1 nemůže být ve Stacklebergově oligopolu hůře než v Cournotově oligopolu. Argument pro toto tvrzení je prostý. Jednou možností firmy 1 ve Stackelbergově hře je zvolit výstup, který odpovídá Nashově rovnováze v Cournotově hře. To jí za předpokladu jedinečné nejlepší odpovědi firmy 2 zajistí stejný zisk, jaký by dosáhla v Cournotově oligopolu. Pokud bude volit jiný výstup, pak jistě jen takový, který ji zajistí vyšší zisk. 6.3 Kupování hlasů V tomto příkladu budeme modelovat situaci, kdy dvě lobbistické skupiny uplácí zákonodárce, jako extenzivní hru. Označme lobbistické skupiny X a Y. Každá z nich lobuje za jiný protichůdný zákon. Zákonodárný sbor má lichý počet členů k. Obě skupiny mohou dát každému z k zákonodárců určitou částku peněz, označme je x i a y i. Každý zákonodárce volí pro ten návrh skupiny, která mu dala více peněz. Skupina X si svého návrhu cení na Vx, skupina Y na 1^. Tuto situaci můžeme zapsat jako extenzivní hru, kde • Hráči: skupiny X a Y • Konečné historie: Množina sekvencí (x,y), kde x je seznam plateb skupiny X zákonodárcům, tj. x — (xi, ...Xk). Obdobně pro y. • Hráčská funkce: P(0) = X, P(x) = Y • Preference: Preference skupiny X jsou dány výplatní funkcí Vx — (xi + x2 + ... + Xk) pokud je přijat zákon X — (xi + x2 + ... + Xk) pokud je přijat zákon Y Predpokladáme, že zákon Y je přijat, pokud yi > xí alespoň v případě \ (k +1) zákonodárců. Preference skupiny Y jsou analogické. K nalezení SPE použijeme zpětnou indukci. Nalezneme tedy nejlepší odpověď skupiny Y na jakoukoliv strategii x skupiny X. Označme \i libovolnou většinu zákonodárců, tj. [i — \(k + 1). Dále označme mx jako součet \i nejmenších složek vektoru x. mx je tedy nejmenší částka, kterou skupina X vyplatila nadpoloviční většině zákonodárců. Pokud chce skupina Y prosadit svůj návrh, pak musí vyrovnat částku zaplacenou skupinou X u \i zákonodárců, tj. musí celkově zaplatit alespoň mx. Nejlepší odpovědí skupiny Y v SPE tedy bude • vyrovnat platbu skupiny X u \i zákonodárců, kterým skupina X zaplatila nejméně, pokud mx < Vy • neplatit nic, pokud mx > Vy • vyrovnat platbu skupiny X u \i zákonodárců, kterým skupina X zaplatila nejméně nebo neplatit nic, pokud mx — Vy Pokud víme, jak se bude chovat skupina Y, můžeme se podívat, co by měla dělat skupina X. Chce-li skupina X prosadit svůj návrh, musí každému zákonodárci zaplatit alespoň mx ^ —, potom se skupině Y nevyplatí zákonodárce přeplatit, protože by musela zaplatit více než v Vy. Skupina X v takovém případě zaplatí mx — k-^. Tato akce přinese skupině X kladnou výplatu jen pokud je Vx > k-^. V opačném případě se skupině X nevyplatí zaplatit zákonodárcům tolik, aby skupinu Y odradila a nemůže tak prosadit svůj návrh. V takovém případě maximalizuje skupina X svou výplatu při akci mx — (0,.., 0). V takovém případě je výplata skupiny X nulová, zatímco při jakékoliv jiné akci by byla záporná. Optimální akcí skupiny X tedy bude • mx = (0,.., 0), pokud Vx < k^ . ma. = (^,...,^), pokud Vx >k^ 7 Extenzivní hry: rozšíření 7.1 Extenzivní hry se současnými tahy Zatím jsme předpokládali, že po každé historii je na tahu jen jediný hráč. Nyní popíšeme obecnější model, ve kterém po některých historiích volí hráči své akce současně, přičemž hráči znají minulé akce ale neznají současné akce ostatních hráčů. Jedná se tedy o jakousi kombinaci extenzivní a strategické hry. Definice 16. Extenzivní hra s dokonalými informacemi a současnými akcemi se 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 • množiny akcí Ai(h) definovaných pro každou vlastnípodhistorii h nějaké konečné historie a pro každého hráče, který je připsán hráčskou funkcí podhistorii h • preferencí definovaných nad množinou konečných historií Zároveň platí, že konečné historie, hráčská funkce a množiny akcí jsou navzájem konzistentní. Všimněte si, že u extenzivních her jsme nemuseli definovat množinu dostupných akcí každého hráče přímo, protože tyto byly odvoditelné z konečných historií. U extenzivních her se současnými akcemi to však již možné není. Definici hry je tudíž nutné doplnit o množiny dostupných akcí. Ukázku extenzivní hry se současnými tahy můžeme vidět na obrázku 6. Všimněte si ovšem, že podobné grafické znázornění je možné jen v případě, kdy se současné tahy objevují až těsně před koncem konečné historie. 2,2 B S 3,1 0,0 0,0 1,3 Obrázek 6: Extenzivní hra se současnými tahy Hráčova strategie je definována stejně jako u extenzivních her bez současných tahů. Strategie specifikuje akce, které si hráč volí po každé historii, kdy je na tahu. U hry na obrázku 6 specifikuje strategie hráče 1 jeho akci jak na začátku hry, tak po historii Concert. Hráč 1 má tudíž čtyři strategie (Concert, B), (Concert, S), (Book, B) a (Book, S). Hráč 2 hraje jen po akci Concert a má dvě strategie B a S. Definice Nashovy rovnováhy a SPE pro extenzivní hry se současnými tahy zůstává stejná jako v předchozí kapitole a stejný je také způsob jejich nalezení. Při hledání Nashovy rovnováhy přepíšeme extenzivní hru do její strategické formy a v takové tabulce nalezneme Nashovy rovnováhy. Ověřte, že hra na obrázku 6 má tyto Nashovy rovnováhy: ((Concert, B), B), ((Book, B), S) a ((Book, S), S). Při hledání SPE u her s konečným horizontem můžeme opět použít zpětnou indukci. Jak tedy vypadají SPE ve hře z obrázku 6? V podhře po historii Concert jsou 2 Nashovy rovnováhy (S,S) a (B,B). Uvažujme tedy nejprve rovnováhu (S,S). V takovém případě je optimální volbou hráče 1 na začátku hry akce Book. Pokud budeme naopak uvažovat rovnováhu (B,B) po historii Concert, pak je optimální akcí hráče 1 na začátku hry Concert. Hra má tedy 2 SPE ((Concert, B),B) a ((Book, S),S). 7.2 Extenzivní hry se současnými tahy: Ilustrace Vstup do monopolního odvětví Představme si odvětví ve kterém působí jediná firma (monopolista) a druhá firma (vyzyvatel) zvažuje vstup, který je spojen s náklady /. Pokud vyzyvatel nevstoupí, pak je jeho zisk nula. Pokud se rozhodne vstoupit, pak se firmy současně rozhodují o množství vyráběného produktu, tj. hrají Cournotovu hru. Tuto situaci můžeme modelovat jako následující extenzivní hru se současnými tahy: • Hráči: stávající firma (monopolista) a vyzyvatel • Konečné historie: (In,(qi,q2)), (Out,qi) kde In a Out značí zda vyzyvatel vstoupí nebo ne, qi je výstup stávající firmy a q2 je výstup vyzyvatele • Hráčská funkce: P(0) = 2, P{In) = 1,2, P (Out) = 1 • Akce: A2(0) = /n, Owt, Ai(Jn) = A^Out) = A2(/n) = {q\q ^ 0} • Preference: jsou dány ziskem. Po historii (In, (qi,q2)) je zisk stávající firmy qiD(qi + q2) — Ci(gi) a zisk vyzyvatele je q2D(qi + q2) — C2(q2) — /. Po historii (Out, qi) je zisk stávající firmy (monopolisty) qiD(qi) — Ci(qi) a zisk vyzyvatele je 0, kde C značí nákladovou funkci a D inverzní poptávkovou funkci. Předpokládejme, stejně jako v kapitole 2.1.1, že průměrné náklady firem jsou konstantní a poptávka je lineární. SPE najdeme pomocí zpětné indukce. Podívejme se tedy na rovnováhu podhry po historii In. V kapitole 2.1.1 jsme viděli, že v rovnováze této podhry obě firmy vyrábí množství |(a —c). Zisk stávající firmy je potom \(ct — c)2 a zisk vyzyvatele je |(a — c)2 — /. V podhře po historii Out je stávající firma v roli monopolisty a bude vyrábět množství \(a — c). Nyní se musíme podívat na podhru po historii 0. Vyzyvatel získá zisk 0 pokud nevstoupí a zisk |(a — c)2 — / pokud vstoupí. Je zjevné, že SPE tak závisí na nákladech vstupu /. Mohou nastat 3 situace: • Pokud / > Ua - c)2, pak SPE je (Out, \(a- c)) • Pokud / < |(a - c)2, pak SPE je (In, (|(a - c), |(a - c)) • Pokud f — |(a — c)2, pak má hra 2 SPE uvedené v předchozích odrážkách. Odchod z upadajícího odvětví Představme si odvětví, ve kterém momentálně působí dvě firmy, jedna velká a druhá malá. Tržní poptávka v odvětví neustále klesá. Kdy odejde firma z odvětví? Která z firem odejde první? Tyto a další otázky nám pomůže odpovědět následující model. Čas chápeme jako diskrétní, označme Pt(Q) tržní cenu v období t, pokud firmy vyrábějí dohromady množství Q a předpokládejme, že cena v průběhu času klesá tak jako na obrázku 7, tj. Pt(Q) < Pt-\(Q) pro každé Q. Firma, která jednou trh opustí se již nemůže vrátit. Vzhledem k tomu, že se zajímáme jen o to zda firma na trhu zůstane (akce S) nebo ho opustí (akce E), budeme předpokládat, že firma vyrábí fixní výstup ki s náklady cki. Předpokládejme, že ki > k2. Hraje definována následovně: • Hráči: Firma 1 a 2 • Konečné historie: Všechny konečné sekvence (X1, ...X1), kde Xs — (S,S) al' = (E,E) nebo Xs — (S, E) pro nějaké saľ = (E, S). Nekonečná sekvence (X1, X2,...), kde Xs = (S, S) • Hráčská funkce: P(h) — 1, 2 po každé historii h, ve které žádná firem neodešla z trhu. P(h) — 1, pokud během historie h firma 2 odešla z trhu a naopak • Akce: Ai — {S, E}, pokud je firma na tahu • Preference: Jsou dány celkovým součtem zisků během doby, kdy firma působila na trhu Jak vypadá SPE této hry? Nejprve se podívejme, jestli v SPE může nastat nekonečná historie, v níž alespoň jedna firma zůstává na trhu nekonečně dlouho. Pokud ne, pak víme, že hra má v SPE konečnou historii a můžeme použít zpětnou indukci. V období, kdy Pt(ki) < c, firma utrpí ztrátu, i když působí na trhu sama. Pokud však poptávka stále klesá, tak jako na obrázku 7, pak musí takové období přijít. Označme tedy poslední období, kdy je pro firmu i výhodné zůstat na trhu, pokud na něm působí sama, jako ti, tj. ti je nej větší hodnota t pro níž platí Pt(ki) ^ c. (Na obrázku 7 je t\ — 2 a t2 — 4). Jelikož víme, že obě firmy odejdou v SPE z trhu nejpozději v období U + l můžeme použit zpětnou indukci k nalezení SPE. Všimněme si nejprve, že větší firma se dostane jako monopolista do ztráty dříve než menší firma, tj. ti 5= t2. Uvažujme proto období t\. Pokud firma 2 v tomto období odejde, pak je její následný zisk roven 0. Pokud firma 2 zůstane a firma 1 odejde, pak firma 2 vydělá ve všech obdobích od t\ do t2 kladný zisk a poté odejde. Pokud obě firmy zůstanou, pak může být zisk firmy 2 v tomto období záporný, ale v obdobích od íi +1 do t2 bude její zisk kladný, protože firma 1 s jistotou odejde nejpozději v období t\ +1. Předpokládejme, že zisk firmy 2 v dalších obdobích je větší než ztráta, kterou firma může utrpět v období t\. V takovém případě v SPE firma 2 zůstane v období t\ na trhu a firma 1 trh opustí. (Teoreticky je možné, že v období t\ mohou být na trhu obě firmy ziskové, v takovém případě opustí firma 1 trh až v následujícím období.) Postupujeme zpětnou indukcí do období t\ — 1. Pokud firma 2 zůstane na trhu, Obrázek 7: Pokles poptávky ve hře odchod z odvětví pak obdrží kladný zisk v obdobích t\ až t2, protože firma 1 opustí v období ti trh (a pokud na něm v období íi zůstane, pak jen v případě, že obě firmy získají v období ti kladný zisk). V období ti — 1 může firma 2 utrpět ztrátu, pokud firma 1 zůstane na trhu, ale tato ztráta je jistě menší než ztráta, kterou mohla utrpět v období ti v případě, že by obě firmy byli na trhu. A o této ztrátě jsme předpokládali, že je převýšena zisky z dalších období. Firma 2 tak zůstane v období ti — 1 na trhu bez ohledu na to, co udělá firma 1. Firma 1 by měla v tomto období opustit trh, pokud Ptl-i{kx + k2) < c, v opačném případě by měla zůstat. Stejnou logiku můžeme aplikovat na všechna předchozí období. Období, ve kterém mohou být obě firmy ziskové působí-li na trhu spolu, označme jako to- V to tedy platí, že Pt0(ki + k2) ^ c. SPE hry o odchod z odvětví vypadá následovně: větší firma opustí trh v období to + 1, menší firma zůstane v odvětví až do období t2. Volební soutěž se strategicky uvažujícími voliči V sekci 2.3 jsem viděli jak vypadá Hotellingův model voleb. V tomto modelu nefigurovali voliči jako hráči, protože vždy volili dle svých preferencí a ne strategicky. Představme si nyní hru, ve které se kandidáti nejprve současně rozhodnou zda kandidovat a o své pozici na pravolevém spektru. Poté se voliči současně rozhodují o tom koho volí. Uvedená hra má následující strukturu: • Hráči: kandidáti k\,...kn a voliči o\,...,on • Konečné historie: Sekvence (x,v), kde x je vektor pozic jednotlivých kandidátů a v vektor volebních rozhodnutí voliče, tj. seznam kandidátů, které jednotlivý voliči volili • Hráčská funkce: P{z) — k\,kn, P(x) — o\,on • Akce: Množina akcí dostupných kandidátům je dána akcí Out a množinou možných pozic. Množina akcí dostupných voličům je dána množinou kandidátů k\,...kn • Preference: Preference kandidátů jsou dány výplatní funkcí, která připisuje hodnotu n historii, kdy kandidát vyhraje, hodnotu n — k historii, kdy vyhraje spolu s k dalšími kandidáty, hodnotu 0 historii, kdy nekandiduje a hodnotu -1, kdy kandidát prohraje. Preference voličů jsou dány vzdáleností mezi jeho preferencemi a pozicí kandidáta. Předpokládejme, stejně jako u Hotellingova modelu, že preference lze reprezentovat čísly na intervalu < 0,1 >. Ukážeme si řešení hry pro případ dvou kandidátů a libovolného počtu voličů. SPE hledáme opět pomocí zpětné indukce. Podívejme se tedy na rovnováhy podhry po historii h — (x). Tato podhra má mnoho Nashových rovnováh. Např. každý profil akcí ve kterém všichni voliči volí stejného kandidáta je Nashovou rovnováhou. Tato mnohost Nashových rovnováh nám umožňuje konstruovat SPE pro každou pozici dvou kandidátu. (Ověřte, že profil strategií, ve kterém si kandidáti zvolí pozice (xi,x2) a všichni voliči poté volí pro kandidáta 1, tj. Vi(xi,x2) — ki : Vz, představuje SPE) Většina takových rovnovah však není příliš robustní, protože volba méně preferovaného kandidáta je slabě dominována volbou více preferovaného kandidáta. Předpokládejme, že voliči nehrají slabě dominovanou akci, tj. volí kandidáta, který je nejblíže jejich preferencím. V takovém případě je řešení této hry stejné jako řešení Hotellingova modelu v sekci 2.3. Jedinou SPE, ve které některý z hráčů nehraje slabě dominovanou akci, je profil akcí, ve kterém kandidáti zaujmou místo dle preferencí mediánového voliče a voliči volí preferovanějšího kandidáta. Bertrandův model s volbou kapacit Kreps, Scheinkman (1984) pomocí níže uvedeného modelu ukazují, že existence kapacitních omezení může výrazně změnit rovnováhu Bertandova modelu. Uvažujme situaci, ve které jsou na trhu dvě firmy, které nejprve investují do svých kapacit při konstantních jednotkových nákladech a následně si konkurují svou cenou. Předpokládáme přitom, že poptávka je lineární, tj. D{p) — a — p. Dále musíme specifikovat, jak vypadá poptávka po produkci firmy s vyšší cenou. Předpokládáme, že firma s nižší cenou prodává spotřebitelům s nejvyšším oceněním (tzv. pravidlo maximalizující přebytek - surplus maximizing ra-tioning rule). Jak bude vypadat tržní rovnováha? Bude stejná jako v Bertandově modelu? Hra modelující tuto situaci může být definována následovně • Hráči: firma 1 a firma 2 • Konečné historie: sekvence ((qi, q2), (pi,P2)), kde qi jsou kapacity firmy i a Pí je cena firmy í • Hráčská funkce: P{0) = {1, 2} a P{qi,q2) = {1,2} • Množina akcí: Ai(0) — qi, qi e R+ a Ai{q\, q2) — pi, pi e R+ • Preference jsou dány ziskovou funkcí PíXí — cqi, kde Xi je množství, které firma prodá. Množství, které firma prodá je rovno SPE budeme hledat tradičně zpětnou indukcí. V prvním kroku tedy ukážeme jak vypadají rovnovážné ceny pro jakoukoliv úroveň kapacit a v druhém kroku vezmeme do úvahy tento výsledek, abychom nalezli rovnovážnou úroveň kapacit. 1. V podhře, ve které firmy volí cenu, je Nashovou rovnováhou dvojice cen {p\,p2) taková, že p\ — p2 — ® — qi — 92- Cena tedy bude taková, že obě firmy prodají veškeré své kapacity. Abychom toto tvrzení dokázali, uvažujme, zdali se firmě 1 vyplatí stanovit vyšší nebo nižší cenu. • Pokud firma 1 stanoví pi < p\, pak bude její zisk n(pi) — p\q\ — cqi, což je jistě nižší než zisk n(p£) — p\qi — cqi. Výsledek je intuitivní, pokud totiž firma sníží cenu, pak stejně neprodá více než jsou její kapacity. • Co když firma 1 stanoví cenu pi > p\l Na základě pravidla maximalizujícího přebytek je reziduálni poptávka firmy 1 x\ — D(pi) — q2 — a—p\ — q2. Je zřejmé, že prodané množství x\ < q\. Zisk při tomto odchýlení můžeme vyjádřit jako n(pi) — p\Xx — cqi — pi(a — pi — q2) — cq\. Na firmu 1 nyní můžeme pohlížet jako na monopolistu, který čelí reziduálni množství a volí optimální cenu, aby maximalizoval svoje zisky. Podmínka prvního řádu maximalizace zisku je J^j- — a — 2p\— q2 — a — 2(a — x\ — q2) — q2, kde poslední rovnost dostaneme, když za pi dosadíme z reziduálni poptávky. Navíc víme, že x\ < qi. Pokud tedy pro kapacity platí q\ < a/3 a q2 < a/3, pak je < 0 a zisková funkce je klesající. Firmě se pak nevyplatí účtovat vyšší cenu než p\ 2. Nyní se podívejme, jak se firmy rozhodují o kapacitách, pokud anticipují výsledek předchozí podhry. Každá z firem se tedy rozhoduje o svých kapacitách, aby maximalizovala anticipovaný zisk Pí(pi) — (pi — c)(a — gi — q2). Tento maximalizační problém je ale stejný jako problém, který řeší firmy v Cournotově modelu. Rovnovážné kapacity jsou tedy {qi,q2) — (^jp, pp)- Všimněme si ,že rovnovážné kapacity jsou skutečně nižší než požadovaných a/3. Kreps, Scheinkman (1984) dokonce ukazují, že uvedená rovnováha je jedinou rovnováhou hry i pro obecnější tvary poptávky. Tento model nám ukazuje další možnou interpretaci Cournotova modelu. Cournotův model můžeme chápat rovnováhu situace, kdy si firmy sice konkurují cenou, ale jsou svázány kapacitami, které si v minulosti zvolily. 7.3 Exogénni nejistota v extenzivních hrách Model extenzivní hry, tak jak ho známe, může být jednoduše rozšířen o náhodné události, které se v průběhu hry mohou stát. Definice 17. Extenzivní hra s náhodnými událostmi je extenzivní hra s dokonalými informacemi, ve které • hráčská funkce připisuje historiím nejen hráče hry ale také "náhodu" • pravděpodobnosti, které náhoda připisuje jednotlivým historiím, jsou přesně specifikovány • preference hráčů jsou definovány nad loteriemi složených z konečných historií Myšlenka skrývající se za touto definicí je prostá. V určitém uzlu může do hry vstoupit nějaká náhodná událost, která je modelována jako dodatečný hráč zvaný "náhoda". Náhoda se o ničem nerozhoduje, ale způsobí, že s určitou pravděpodobností se hra ubírá nějakým směrem. Tyto pravděpodobnosti jsou přitom známé. Příklad takové hry je vidět na obrázku 8. Náhoda je na obrázku označme jako hráč c (chance). Vidíte, že po tahu hráče 1 náhoda s pravděpodobností \ ukončí hru s výplatami 3, 0 a s pravděpodobností \ táhne hráč 2. 0,1 1,0 Obrázek 8: Extenzivní hra s náhodnou událostí Hry s náhodnou událostí se často používají k modelování skutečnosti, že hráči mohou dělat během hry chyby. Předpoklad o tom, že hráči dělají chyby může být velmi užitečný, pokud se chceme zbavit nerobustních rovnováh (Selten 1975). Mnohdy se totiž ukáže, že některé rovnováhy nejsou imunní ani proti minimální možnosti chyby. To znamená, že stačí, aby hráči dělali chyby s velmi malou pravděpodobností a tyto situace přestávají být rovnováhami. Rovnováhy, které jsou robustní i při určité malé možnosti chyby, se nazývají jako perfektní vzhledem k třesoucí se ruce (trembling-hand perfect). Ukážeme si tento princip na jednoduchém příkladu. A B A 1,1 2,0 B 0,2 2,2 Tabulka 14: Příklad Vezmeme si strategickou hru znázorněnou tabulkou 14. Je zjevné, že uvedená hra má 2 Nashovy rovnováhy (A,A) a (B,B). Nyní však předpokládejme, že hráči dělají chyby. S pravděpodobností Pi < \ hráč hraje jinou akci než zamýšlel. S pravděpodobností 1 — Pí potom hraje akci, kterou skutečně chtěl hrát. Takovou situaci můžeme modelovat jako následující hru. • Hráči 1 a 2 • Konečné historie: Všechny sekvence ((W,X)Y,Z), kde W,X,Y a Z jsou buď akce A nebo B. W značí akci, kterou si zvolil hráč 1 a X akci zvolenou hráčem 2. Y a Z jsou akce, které hráčům přidělila náhoda. • Hráčská funkce: P(0) = 1,2, P(W, X) = c, P((W, X),Y) = c • Akce: A,B • Pravděpodobnosti dané náhodou: Po historii (W,X) zvolí náhoda W s pravděpodobností 1 — pi a opačnou akci hráče 1 s pravděpodobností p\. Po historii ((W, X),Y) zvolí náhoda X s pravděpodobností 1 — p2 a opačnou akci hráče 2 s pravděpodobností pi. • Preference jsou dány očekávanou hodnotou Bernoulliho výplatní funkce zadané tabulkou 14 Jelikož se hráči rozhodují současně musí být každá Nashova rovnováha také SPE. K nalezení SPE nám tedy stačí nalézt Nashovy rovnováhy. Nashovy rovnováhy nalezneme tak, zkonstruujeme strategickou formu této hry. Každý hráč má na výběr ze dvou akcí A a B. Předpokládejme, že oba hráči si vyberou akci A. Jak bude vypadat výplata hráče 1? Situace (A, A) nastává s pravděpodobností (1 — pi)(l — pi) s touto pravděpodobností obdrží hráč výplatu 1. Situace (A,B) nastává s pravděpodobností p\(l — pi) s touto pravděpodobností obdrží hráč 1 výplatu 0. V situacích (A, B) a (B, B) získá hráč 1 výplatu 2. Tyto situace nastanou s pravděpodobností p2- Očekávaná výplata hráče 1 z profilu akcí (A, A) je tedy (1 — pi)(l — P2) + 2p2. Postupujme-li takto dále získáme tabulku 15. A B A 1 - Pl + P2 + PlP2, Í-P2+P1- \-p1P2 2- P2 - P1P2, 2pi "f P2 + PlP2 B 2p2 +Pi+ P1P2, 2-px- pxP2 2- 2P2 + P1P2, 2 - 2pi + P1P2 Tabulka 15: Strategická forma hry Pro pi — 0 a P2 — 0 získáváme původní hru z tabulky 14, která má 2 Nashovy rovnováhy. Pokud je ale alespoň jedno z pi > 0, pak je rovnováhou jen profil akcí (A, A), protože 2 — pi —piPj > 2 — 2pi+piPj (za předpokladu, že pi < \ a P2 < \). Vidíme tedy, že stačí velmi malá pravděpodobnost chyby a profil akcí (B, B) přestává být rovnováhou. Touto vlastností se vyznačují všechny rovnováhy ve slabě dominovaných akcích (ale nejen ony). 7.4 Morální hazard v teorii kontraktů Jako morální hazard se v ekonomii označuje jedna ze situací, kdy mají agenti asymetrické informace. Konkrétně se jedná o situaci, kdy dvě strany (často nazývané jako principál a agent) spolu uzavírají kontrakt, přičemž jedna ze stran může učinit akci, která není pozorovatelná druhou stranou, ale ovlivní její výplatu. V rámci tzv. teorie kontraktů potom řešíme, jaké smlouvy jsou v případě asymetrických informací optimální. Jako příklad morálního hazardu může sloužit situace, kdy zaměstnavatel uzavírá smlouvu se zaměstnancem, přičemž není schopen kontrolovat jeho pracovní úsilí. Podobný konflikt může vznikat mezi akcionářem firmy a manažery nebo věřiteli firmy a jejími akcionáři. Je dobré si uvědomit, že morální hazard se stává problémem pro ekonomickou efektivnost pouze tehdy, když mají obě strany kontraktu odlišnou výplatní funkci. V opačném případě není morální hazard problém. Pokud maximalizuje zaměstnanec stejnou výplatní funkci jako zaměstnavatel, pak je jedno, zda je či není jeho chování pozorovatelné. Hra modelující situaci s morálním hazardem může být definována následujícím způsobem • 2 hráči: principál P a agent A • Konečné historie (w(q),X, e, q(e)), kde w je mzda, kterou principál nabídne agentovi, X značí přijmutí nebo odmítnutí kontraktu, e je snaha, kterou agent vyvine a q(e) je produkce, kterou agent vytvoří. • Hráčská funkce: P(0) = P, P(w) = A, P(w, X) = A, P(w, X, e) = N • Výplaty jsou v případě uzavření kontraktu Up(w,q) — S(q) — w(q), UA(w,q) — u(w(q)) — C(e). V případě odmítnutí kontraktu obdrží agent rezervační užitek U. S(q) je peněžní hodnota produkce q. Z definice hry je zřejmé pořadí tahů. Nejprve principál nabídne agentovi kontrakt charakterizovaný mzdou, která závisí na množství realizované produkce. Všimněte si, že mzda nezávisí na snaze, kterou agent vyvine, protože tato snaha je nepozorovatelná. Poté se agent rozhodne, zda kontrakt přijme a jakou snahu vyvine. Na závěr náhoda rozhodne jaká bude výsledná produkce. Pro jednoduchost budeme předpokládat, že snaha i výsledná produkce agenta může být vysoká nebo nízká. Pokud je snaha vysoká, pak pravděpodobnost, že produkce bude také vysoká, je py. Pokud je snaha nízká, pak pravděpodobnost, že produkce bude také vysoká je pn, přičemž py > pn- Označme peněžní hodnotu vysoké produkce jako Š a nízkou produkci jako S_. Mzdu při vysoké produkci označme jako w a mzdu při nízké produkci jako w. Obdobně označme náklady při vysoké a nízké snaze jako C a C. Hru můžeme řešit zpětnou indukcí. Podívejme se nejprve na podhru, ve které se agent rozhoduje o své snaze. Porovnává svůj užitek při vysoké snaze U (V) — py(u(w) — C) + (1 — py)(u(w) — C) s užitkem při nízké snaze U(N) — pn(u(w) — q + (1 — pn)(u(w) — C). Pokud chce principál přimět agenta, aby vyvinul vysokou snahu (což se principálovi vyplatí, pokud jsou náklady na vynucení vyšší snahy nižší než zisk z vyššího úsilí, který je dán (py — pn)(S — S_)), pak musí platit tzv. motivační omezení (incentive constraint), které udává, že se agentovi vyplatí vyvinout vyšší snahu pv(u(w) - Č) + (1 - pv)(u(w) -C)> pN(u(w) - C) + (1 - pN)(u(w) - C) V předchozí podhře se agent rozhoduje, zda kontrakt přijme. Pokud ho odmítne, pak obdrží rezervační užitek Ú. Agent tedy přijme kontrakt, pokud platí tzv. participační omezení (participation constraint) pv(u(w) -Č) + (í-pv)(u(w) -C)>Ú Na začátku se principál snaží stanovit takovou úroveň mzdy při vyšší produkci w a takovou úroveň mzdy při nižší produkci w, která maximalizuje jeho užitkovou funkci a splňuje obě omezení. Jelikož principálova užitková funkce je klesající v w i v w, nastaví principál nejnižší úroveň mzdy, kterou mu omezení umožní. Participační a motivační omezení tudíž budou splněny jako rovnosti. Rizikově neutrální agent Rizikově neutrální agenti mají lineární Bernoulliho užitkovou funkci u(w). Vzhledem k tomu, že užitková funkce je ordinální, můžeme C a rezervační užitek normalizovat na hodnotu 0. V takovém případě potom motivační a participační omezení nabývají následující podoby. Pv(w — C) + (1 — pv)(w — č) — pnw + (1 — pn)w pv(w -C) + (l-pv)(w - C) = 0 Řešením těchto dvou rovnic získáme řešení a podmínky optimálního kontraktu. PnC w —-- Pv - Pn _ (I-Pn)C w — - Pv - Pn Všimněme si několika vlastností tohoto řešení. Agent získá přesně svůj rezervační užitek, což znamená, že informační výhoda nepřinese agentovi vyšší užitek než jsou jeho náklady obětované příležitosti. Očekávaný transfer od principála k agentovi je WFB = pvw + (l-pv)w = Pvi^^) + (1 -Pv)(-py_pJV) = C, což je přesně stejná platba, kterou by musel principál zaplatit agentovi, kdyby ho chtěl motivovat k vysokému úsilí a zároveň mohl jeho úsilí kontrolovat. Proto se toto řešení nazývá jako first best řešení. Dále si všimněte, že agent nese veškeré riziko, že produkce bude i přes vysoké úsilí nízká. Agent je ovšem rizikově neutrální, což znamená, že agent nevyžaduje za toto riziko odškodnění. Morální hazard tedy nezpůsobuje žádnou ztrátu efektivnosti, pokud je agent rizikově neutrální. Optimální kontrakt definovaný podmínkami pro w a w může být implementován mnoha způsoby. Typickou implementací je udělat z agenta vlastníka projektu. Platba agentovi je dána v takovém případě dána jako w — S_ — Fa,w — Š — F, kde F je předem dohodnutá platba náležející principálovi. F je stanoveno tak, aby participační omezení bylo splněno jako rovnost, tj. py§ + (1 — pv)S_ — C — F — 0. Rizikově averzní agent Z předchozího výkladu je zřejmé, že efektivní řešení problému morálního hazardu závisí na tom, že agent je neutrální k riziku. Pokud tento předpoklad opustíme, uvidíme jaký problém morální hazard přináší. Jedním ze způsobů, jak modelovat averzi k riziku je předpokládat, že Bernoulliho užitková funkce u(w) je konkávni. Motivační a participační omezení nabývají následující podoby. Pv(uw — č) + (1 — pv)(uw — C) — PnVv5 + (1 — Pn)\/w Pv(uw — C) + (1 — Pv){uw_ — C) — 0 Řešením těchto dvou rovnic získáme podmínky optimálního kontraktu. _i/ PnC w — u {--) Pv - Pn -1,(1 -Pn)C w — u (-) Pv - Pn Je možné ukázat, že očekávaný transfer od principála k agentovi je v tomto případě větší než platba, kterou by musel principál zaplatit agentovi, kdyby ho chtěl motivovat k vysokému úsilí a zároveň mohl jeho úsilí kontrolovat. Proto se toto řešení nazývá jako second best řešení. Platí tedy, že WSB > C. Tato skutečnost má dva důsledky. Zaprvé, morální hazard způsobuje neefektivnost, pokud principálův zisk z vyššího úsilí (pv — Pn)(S — 5) leží v intervalu mezi [WFB, WSB]. Za předpokladu dokonalých informací by se principálovi vyplatilo vynutit si vyšší úsilí, ovšem při nepozorovatelném úsilí to neudělá. Zadruhé, existuje zde trade-off mezi motivací agenta a pojištěním agenta. Motivace k vyššímu úsilí si vynucuje větší rozdíl mezi mzdou při vyšší a nižší produkci. Na druhé straně rizikově averzní agent musí být za tento rozdíl odškodněn, což zvyšuje principálovi náklady. Omezené ručení V případě V předchozím případě jsme viděli, že optimální mzda w je záporná (Obecně je taková, že při realizaci nižší produkce získá agent menší než rezervační užitek). Můžeme tedy předpokládat, že agent není ochoten toto riziko nést a w musí být vyšší než určitá částka L < 0. Alternativně lze také tuto podmínku interpretovat tak, že agent nemá dostatek aktiv aby uhradil principálovi případný negativní transfer. Optimální kontrakt nyní musí splňovat nejen motivační a participační omezení, ale také omezení omezeného ručení w>L. V předchozí kapitole jsme odvodili velikost w bez omezeného ručení. Pokud je tato hodnota menší než L, tj. pokud platí PnC < Pv - Pn ~ pak bude podmínka omezeného ručení svazující a participační omezení nebude svazující (tj. bude splněno jako nerovnost) a výsledek je v tomto případě dán řešením následujících dvou rovnic Pv(w — Č) + (1 — pv)(w — C) — pnw + (1 — pn)w w — L Řešení této soustavy rovnic je následující w — L aw — L+ pvCLPN ■ Toto řešení se často nazývá jako tzv. second best řešení. Opět se podíváme na několik vlastností tohoto kontraktu. Nejprve se zeptejme jaký je agentův užitek? Dosadíme-li řešení do agentovi užitkové funkce získáme U b — Pv(L+ pvCLPN — C) + (1 — pv)(L — č) — L + pjHPN C > 0, kde poslední nerovnost plyne z toho, že participační omezení není svazující. Vidíme tedy, že agent obdrží větší užitek než je jeho rezervační užitek. Tento rozdíl je dán jeho informační výhodou a nazývá se informační renta. Nyní vyjádříme očekávaný transfer od principála k agentovi WSB = pvw + (1 - pv)w — L + —C = L + C+ PN C > C Pv - Pn Pv - Pn Je vidět, že náklady principála na vynucení si vyššího úsilí jsou větší než v případě s dokonalými informacemi (s pozorovatelným úsilím). Pokud principálův zisk z vyššího úsilí (pv — Pn)(S — S) leží v intervalu mezi [WFB, WSB], pak vede k neoptimální situaci. Za předpokladu dokonalých informací by se principálovi vyplatilo vynutit si vyšší úsilí, ovšem při nepozorovatelném úsilí to neudělá. 8 Strategické hry s nedokonalými informacemi Ve strategických hrách jsme předpokládali, že hráči mají dokonalé informace, tj. znají počet hráčů, svoje možné akce, možné akce ostatních hráčů a preference všech hráčů. Nyní budeme předpokládat, že hráči neznají strukturu hry úplně dokonale. K modelování nedokonalých informací nám bude sloužit množina tzv. stavů světa a signální funkce. Množina stavů světa představuje popis možných aspektů světa, které mohou nastat a o kterých má některý z hráčů nedokonalé informace. Signální funkce potom určuje mezi kterými stavy světa není hráč schopen rozlišit. Signální funkce tedy rozdělí množinu stavů světa do určitého počtu podmnožin. Hráč potom ví, ve které podmnožině se nachází, ale není schopen rozlišit mezi stavy světa v dané podmnožině. Zároveň předpokládáme, že hráči znají pravděpodobnosti s jakou jednotlivé stavy světa nastávají. 8.1 Definice strategické hry s nedokonalými informacemi Definice 18. Strategická hra s nedokonalými informacemi (Bayesiánská hra) se skládá z: • Množina hráčů • Množina stavů světa fl • Množina akcí každého hráče • Pro každého hráče množina možných signálů {ti} a signální funkce tÍ} která stavu světa přiřazuje určitý signál • Pro každého hráče a pro každý signál systém přesvědčení ohledně stavů světa konzistentní se signálem, tj. rozdělení pravděpodobností nad množinou stavů světa konzistentních se signálem • Bernoulliho výplatní funkce nad množinou (a, uj), kde a je profil akcí a lo je stav světa V definici strategické hry s nedokonalými informacemi požadujeme, aby systém přesvědčení ohledně stavů světa byl konzistentní se signálem, který hráč obdrží. Co přesně ale tato konzistence znamená? Přesvědčení hráče označíme za konzistentní, pokud je hráč upravuje podle Bayesova vzorce. Budeme tedy předpokládat, že systém přesvědčení lze definovat pomocí apriorní pravděpodobnosti, kterou hráči připisují jednotlivým stavům světa. Po obdržení signálu upravují své apriorní pravděpodobnosti dle Bayesova vzorce AP{uj) M " Euer-1(ťl)APM) kde P(lo) značí posteriorní pravděpodobnost, kterou hráč připisuje stavu světa lo po obdržení signálu U a AP je apriorní pravděpodobnost, kterou hráč připisuje stavu světa lo před obdržením signálu U. Stavům světa, které nepatří do množiny t_1(íj) je připsána nulová pravděpodobnost. Z tohoto důvodu se strategické hry s nedokonalou informací často označují jako Bayesovské hry. V dalším výkladu budeme předpokládat, že všichni hráči mají stejné apriorní přesvědčení, které odpovídá objektivní pravděpodobnosti, že daný stav světa nastane. Příklad: Bitva pohlaví Význam uvedené definice si ukážeme na následujícím příkladu. Mějme hru bitva pohlaví, ve které hráč 2 nechce hráče 1 s pravděpodobností p potkat. Hráč 1 přitom neví, jestli ho chce hráč 2 potkat nebo jestli se mu chce vyhnout. Hráči tedy hrají vždy jednu z níže uvedených her, přičemž hráč 1 neví kterou. B S B S B 2,1 0,0 B 2,0 0,2 S 0,0 1,2 S 0,1 1,0 Tabulka 16: potkat se, pravděpodobnost p Tabulka 17: vyhnout se, pravděpodobnost 1 — p Tato hra by byla formálně definována následujícím způsobem: • Hráči 1 a 2 • Množina stavu světa {P, V} • Množina akcí {B,S} pro hráče 1 i 2 • Signální funkce n (P) = n(V) = X, t2(P) = P, t2(V) = V • Hráč připisuje stavu V pravděpodobnost Pi(V) — p a stavu P pravděpodobnost P2(P) — l—p (Alternativně můžeme říci, že apriorní přesvědčení každého hráče připisuje stavu potkat se pravděpodobnost Pí a vyhnout se 1—pi). • Bernoulliho výplatní funkce jsou dány výše uvedenými tabulkami, kde tabulka 8.1 odpovídá stavu světa P a tabulka 8.1 odpovídá stavu světa V. Stavy světa obsahují popis těch aspektů hry o kterých nemají hráči dokonalé informace. V tomto případě hráč 1 nezná preference hráče 2. Hráč 2 může být dvou "typů" v závislosti na signálu, který obdrží. Může se chtít potkat s hráčem 1 nebo se mu může chtít vyhnout. Množina stavů světa proto obsahuje dva prvky P a V. Signální funkce hráče 1 potom každému stavu světa přiřazuje stejný signál. To znamená, že hráč 1 není schopen na základě signálu, který pozoruje mezi jednotlivými stavy světa rozlišit. Hráč 2 naopak na základě svého signálu ví, zda se nachází ve stavu P nebo V. 8.2 Nashova rovnováha Bayesovských hry Ve strategické hře si každý hráč volí svou akci. V bayesovské hře se každý hráč může rozhodovat jinak v závislosti na signálu, který obdrží. Volí si tak ne jednu akci, ale n-tici akcí - jednu pro každý signál, který může obdržet. Nashova rovnováha Bayesovské hry je potom situace, kdy pro každého hráče v každém typu platí, že akce jím zvolená je optimální při daných akcích všech ostatních hráčů ve všech typech. Při hledání Nashovy rovnováhy v Bayesovských hrách budeme postupovat tak, že s každým hráčem různého typu budeme zacházet jako se samostatným hráčem. Takovým způsobem zkonstruujeme strategickou hru s dokonalými informacemi, kde je počet hráčů dán původním počtem hráčů a počtem signálů každého hráče, a najdeme Nashovu rovnováhu této hry. Definice 19. Nashova rovnováha Bayesovské hry je Nashova rovnováha následující strategické hry: • Hráči jsou dáni množinou [i, ti) • Množina akcí hráče {i, ti) je množina akcí hráče i v Bayesovské hře • Bernoulliho výplatní funkce hráče {i, t i) je dána následovně: Výplata hráče i typu U je tedy dána jeho akcí bi kde P (b) označuje cenu, kterou hráč zaplatí v závislosti na pravidlech aukce a bidech (Ve first-price aukci tedy zaplatí svou nabídku a v second-price aukci druhou nejvyšší nabídku) a m je počet hráčů s nej vyšším bidem. V second-price aukci můžeme pomocí stejného argumentu jako u aukcí s dokonalými informacemi ukázat, že akce, kdy hráč nabídne své vlastní ocenění slabě dominuje ostatní akce. Tento argument je shrnut v tabulkách 8 a 9. Podíváme se proto jak vypadá Nashova rovnováha ve first-price aukci. Abychom si situaci zjednodušili budeme předpokládat, že F (v i) má rovnoměrné rozdělení a ví e [0,1]. Již víme, že ve first-price aukci je každá akce bi > ví slabě dominovaná akcí bi — ví. Hráči tedy nenabízejí více než je jejich ocenění. Budeme předpokládat, že ostatní hráči nabízejí nějaký násobek svého ocenění b-i — av-i, kde a e [0,1]. Ukážeme, že pokud se ostatní hráči řídí podle této strategie, pak se určitý hráč bude také řídit pomocí této strategie. Tato strategie je tudíž nejlepší odpovědí sama na sebe a profil těchto strategií tak tvoří Nashovu rovnováhu. Každý hráč se snaží maximalizovat očekávaný zisk z aukce. Označme p pravděpodobnost, že hráč nabídne nejvyšší bid. Hráč potom maximalizuje následující funkci max.p(bi)(v - bi) Ostatní hráči se řídí podle strategie 6_i — av-i. Bid hráče i je tedy vyšší než bid jiného hráče, pokud bi > av-i => v-i < ^. Jelikož víme, že ocenění hráče mají rovnoměrné rozdělení, pak pravděpodobnost, že bid hráče i je vyšší než bid jiného hráče je ^. Obdobně pravděpodobnost, že bid hráče i je vyšší než bid N — 1 ostatních hráčů je (^)JV_1- Optimalizační problém hráče i potom můžeme zapsat jako 6, a Řešením tohoto problému najdeme optimální bid bi — ^j^ví. Pokud tedy za parametr a dosadíme hodnotu získáme Nashovu rovnováhu. Všimněte si, že bid hráče i je očekávaná hodnota druhého nejvyššího ocenění za předpokladu, že ocenění hráče i je nejvyšší. Toto platí i pro jiná pravděpodobnostní rozdělení ocenění, nejen pro rovnoměrné rozdělení. Zároveň z toho, plyne, že očekávaná prodejní cena ve first-price i second-price aukci je stejná. Aukce se společným oceněním V aukcích se společným oceněním si hráči cení draženého objektu stejným způsobem. Hráči však nemají dokonalé informace a tak neví jakou hodnotu objekt přesně má. Každý hráč má určitou informaci o hodnotě objektu. Uvedenou hru můžeme modelovat jako akci, kdy každý hráč obdrží nějaký signál (informaci o kvalitě objektu). Hráčovo ocenění objektu přitom nezávisí jen na signálu, který obdrží, ale také na signálech, které obdrží ostatní hráči. Příkladem aukce se společným oceněním může být dražba ropného pole, IPO, aukce digitálních frekvencí nebo aukční prodej firmy. Aukci se společným oceněním můžeme definovat takto: • Hráči: l,...,n • Stavy světa: sekvence všech profilů (ti,...,tn), • Akce: Množina možných bidů, tj. kladných čísel • Signály: Tj(íi, ...,tn) = U • Přesvědčení: Signál každého hráče je nezávislý na signálech ostatních hráčů. Hráč i připisuje pravděpodobnost F(ti) x F(í2) x ... x F(tn) stavu, kdy ocenění každého hráče j je nanejvýš tj. • Výplatní funkce: „ lh 1+ + W - ) ",í""1' -'*")) ~ P(b))/m pokud b j ^ bt pokud b j > bi kde P (b) označuje cenu, kterou hráč zaplatí v závislosti na pravidlech aukce a bidech (ve ŕirst-price aukci tedy zaplatí svou nabídku a v second-price aukci druhou nejvyšší nabídku) a m je počet hráčů s nejvyšším bidem. Všimněte si, že ocenění Vi je funkcí signálů všech hráčů. Podívejme se, jak vypadá Nashova rovnováha v second-price aukci se dvěma hráči. Předpokládejme, že ocenění každého hráče je dáno funkcí ví — aU + 7Í7, kde a ^ 7 ^ 0. Náhodná veličina U G [0,1] má rovnoměrné rozdělení. Za těchto podmínek nabídne hráč částku (a + 7)^ Abychom toto ověřili, předpokládejme, že hráč 2 nabídne tuto částku a podívejme se jak vypadá optimální odpověď hráče 1. Výplata hráče 1 je dána následujícím: • Pravděpodobností, že hráč 1 vyhraje. Hráč 1 vyhraje, pokud b\ ^ (a + ~/)t2 => t2 = Protože t2 má rovnoměrné rozdělení, pak víme, že P(t2 S ~^+^) — Tato pravděpodobnost je tedy • Očekávanou cenou, kterou hráč 1 zaplatí. Hráč 1 zaplatí bid hráče 2 za podmínky, že hráč 1 vyhraje, zajímá nás tedy E(b2\b2 < bi). Nabídka druhého je násobkem signálu, který má rovnoměrné rozdělení. Podmíněné b2 má tedy také rovnoměrné rozdělení mezi 0 a b\. Z čehož plyne, že E(b2\b2 < bi) — \b\ • Očekávanou hodnotou signálu hráče 2 za předpokladu, že hráč 1 vyhraje. Hráč 1 vyhraje, pokud bi ^ (a + 7)Í2 => í2 S Zajímá nás tedy E(t2\t2 ^) = Dosazením těchto výsledků do funkce udávající ocenění, pak získáme očekávanou výplatu hráče 1: bi , h 1, , a + 7 2 (a + 7) 2 Nyní zbývá najít maximum této funkce pro b\. Derivací tohoto výrazu a jeho položením rovno 0 zjistíme, že maxima je dosaženo pro bi — (a + 7)íi- 9 Extenzivní hry s nedokonalými informacemi K popsání extenzivní hry s nedokonalými informacemi potřebujeme množinu hráčů, hráčskou funkci, množinu možných historií a preference hráčů. Pokud chceme popsat extenzivní hru s nedokonalými informacemi, pak musíme navíc přesně specifikovat informace každého hráče ohledně toho, co se stalo ve hře před jeho tahem. Množinu možných historií, po kterých je hráč i na tahu, Hi rozdělíme do tzv. informačních množin li. 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. 9.1 Definice extenzivní hry s nedokonalými informacemi Extenzivní hra s nedokonalými informacemi se skládá z: • Množiny hráčů • Množiny konečných historií • Hráčské funkce • Funkce, která připisuje každé historii, při níž je na tahu náhoda, určitou pravděpodobnost • Rozdělení množiny historií, po níž je hráč i na tahu, do informačních množin li takových, že historie h a h! mohou být ve stejné informační množině jen tehdy, když Ai(K) — Ai(h') • Preferencí nad množinou konečných historií reprezentované Bernoulliho výplatní funkcí Strategie v extenzivní hře s nedokonalými informacemi je funkce, která každé informační množině hráče li připisuje akci z množiny A(Ii). (resp. pravděpodobnostní rozdělení nad množinou A(Ii)) Příklad extenzivní hry s nedokonalými informacemi Smysl předchozí definice můžeme ilustrovat na příkladu hry Vstup do odvětví. Firma 1 může na začátku hry zůstat venku z odvětví (V), může vstoupit připravena (P) nebo nepřipravena (N). Firma 2 se po historiích P nebo N rozhoduje, zda bude s firmou 1 bojovat nebo se s jejím vstupem smíří. Firma 2 pozoruje, jestli firma 1 vstoupila na trh nebo ne, nedokáže ale rozlišit, zda vstoupila připravena nebo nepřipravena (Na grafu je to vyznačeno přerušovanou čárou). Množina historií po kterých je firma 2 na tahu {P,N} se tedy skládá z jediné informační množiny I2 — {P, N}, která obsahuje obě historie. Firma 2 tedy není schopna rozlišit, zda firma 1 vstoupila připravena nebo nepřipravena. 1 Obrázek 10: Vstup do odvětví Ve hře vstup do odvětví má firma 1 strategie V,N a P. Firma 2 má jen dvě možné strategie B a S, protože má jen jednu informační množinu. Ve hře s dokonalými informacemi by měla strategie (B,B), (B,S), (S,B)a(S,S). 9.2 Nashova rovnováha Nsahova rovnováha v extenzivní hře s nedokonalými informacemi je definována stejně jako v předchozích případech. Nashova rovnováha je situace, kdy pro každého hráče i a pro každou strategii cti platí, že očekávaná výplata E(u(a*, a*_i)) > E{u{cti,ct*_i)). Způsoby jejího hledání jsou opět podobné jako v případě extenzivní hry s dokonalými informacemi. Sestavíme tabulku strategické formy extenzivní hry a v této tabulce najdeme Nashovu rovnováhu. V našem příkladu hry vstup do odvětví je strategická forma hry daná tabulkou 19. Je zjevné, že hra má S B P 3,3 1,1 N 4,3 0,2 V 2,4 2,4 Tabulka 19: Vstup do odvětví 2 Nashovy rovnováhy (N,S) a (V,B). Stejně jako u extenzivní s dokonalými informacemi není rovnováha (V,B) perfektní vzhledem k podhrám, protože akce B hráče 2 není kredibilní (Po historii P či N preferuje hráč 2 akci S). Nashova rovnováha tudíž není úplně vhodný koncept řešení pro extenzivní hry s nedokonalými informacemi. 9.3 Přesvědčení a sekvenční rovnováha Nashova rovnováha je implicitně charakterizována dvěma požadavky: každý hráč se rozhoduje optimálně vzhledem k jeho přesvědčením a jeho přesvědčení jsou správná. V SPE jsme navíc vyžadovali, aby toto platilo v každé podhře. Stejné požadavky chceme vznést také na koncept rovnováhy používaný v extenzivních hrách s nedokonalými informacemi. Na rozdíl od her s dokonalými informacemi, ale nyní musíme explicitně stanovit přesvědčení hráčů. (Ve hrách s dokonalými informacemi toto nebylo nutné, protože přesvědčení byla implicitně definována strategiemi ostatních hráčů.) Než definujeme koncept sekvenční rovnováhy uděláme krátkou technickou poznámku. V předchozí kapitole jsem definovali strategii hráče. V kontextu sekvenční rovnováhy je výhodnější vyjádřit strategie jako tzv. behaviorální strategie. Behaviorální strategie hráče i je funkce, která každé informační množině li připisuje pravděpodobnostní rozdělení nad akcemi A{Ii). Systém přesvědčení v extenzivní hře je funkce, která každé informační množině připisuje pravděpodobnostní rozdělení nad množinou historií v této informační množině. Definice sekvenční rovnováhy Ohodnocení extenzivní hry se skládá z profilu behaviorálních strategií ft a systému přesvědčení /i. Ohodnocení je rovnováha, pokud splňuje dvě podmínky. • 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. Oii (j3, n) ^ Oii(('ji, P-i), /z) pro každou behaviorální strategii 7. • Konzistence přesvědčení se strategiemi. Přesvědčení každého hráče je konzistentní s profilem strategií. Tento požadavek vyžaduje, aby v rovnováze měli hráči správná očekávání ohledně strategií ostatních hráčů. Pokud tedy rovnovážný profil strategií vede s kladnou pravděpodobností k historii, která spadá do informační množiny li, pak přesvědčení hráče i ohledně pravděpodobnosti výskytu historie h* v této informační množině je Pr(h* dle strategie j3) ^2hei Pr^h dle strategie j3) Pokud rovnovážný profil strategií nevede do určité informační množiny, pak přesvědčení hráče v této informační množině nejsou determinovaná a mohou být libovolná. Takovou rovnováhu nazýváme slabá sekvenční rovnováha (WSE) O WSE platí, že: • 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. Hledání slabé sekvenční rovnováhy Tyto dvě vlastnosti WSE nám nabízí metody, jak WSE najít. Jednou z možností je najít všechny Nashovy rovnováhy a poté prověřit, která z nich je WSE. Druhou možností je kombinace zpětné indukce a metod hledání Nashovy rovnováhy. První podmínka nám totiž říká, že v těch částech hry, kde mají hráči dokonalé informace můžeme při hledání WSE použít zpětnou indukci. Druhou ze zmíněných metod si nyní ukážeme na příkladu z obrázku 11. Nejprve se podíváme, jestli 1 Obrázek 11: můžeme použít zpětnou indukci. Je zjevné, že po historii (C,F) bude hráč 1 hrát akci J. Dále již nemůžeme zpětnou indukci použít. Nejprve se podíváme, jestli existuje rovnováha, ve které hráč 1 hraje na začátku hry C nebo D s kladnou pravděpodobností. Poté zjistíme, jestli existuje rovnováha, ve které hráč hraje akci E. • Předpokládejme, že hráč 1 hraje C s pravděpodobností p a D s pravděpodobností q. Musíme nyní zjistit "Jaká jsou přesvědčení hráče 2?" a "Jaká je optimální odpověď hráče 2?". Přesvědčení hráče jsou jednoznačně dány požadavkem konzistence. V rovnováze hráč připisuje pravděpodobnost p j (p + q) historii C a pravděpodobnost q/(p + q) historii D. Pokud p^ q, pak je optimální odpovědí hráče 2 akce G. Pokud p 5= g, pak je optimální odpovědí hráče 2 akce F. Nyní musíme zjistit, zda je strategie hráče 1 na začátku hry sekvenčně racionální při dané odpovědi hráče 2. Pokud p^ q, pak hraje hráč 2 akci G. V takovém případě je optimální odpovědí hráče 1 behaviorální strategie, která připisuje pravděpodobnost 1 akci D, tj. q — 1, což je ale spor s požadavkem p ^ q. Pokud hraje hráč 2 akci F, pak optimální odpovědí hráče 1 je hrát C s pravděpodobností 1, což je ale opět spor s podmínkou p 5= q. Hra tedy nemá žádnou WSE ve které je hráno C nebo D. • Předpokládejme, že hráč 1 hraje na začátku hry akci E. V takovém případě nejsou přesvědčení hráče 2 nijak omezena. Musíme tedy odpovědět na dvě otázky: "Existuje strategie hráče 2, při které je E optimální?" a "Existuje přesvědčení, které činí takovou strategii hráče 2 optimální?" Pokud dokážeme na obě otázky odpovědět kladně, pak jsem našli WSE. Vidíme, že E slabě dominuje D. Hráč 1 tedy preferuje E před D. V jakém případě ale E dává vyšší výplatu než C? Je zjevné, že E je optimální, právě tehdy, když hráč 2 hraje akci F s pravděpodobností 2/3 nebo nižší. V opačném případě by hráč 1 mohl zvýšit svoji výplatu volbou akce C. Při jakých přesvědčeních bude hráč 2 volit akci F s pravděpodobností nanejvýš 2/3. Označme b pravděpodobnost, kterou připisuje hráč 2 akci C a 1 — b pravděpodobnost, kterou připisuje akci D. (b a 1 — b je systém přesvědčení). Očekávaná výplata hráče 2 z akce F je tedy 60 + (1 — 6)1 a očekávaná výplata hráče 2 z akce G je bl + (1 — 6)0. Je zjevné, že akce G je optimální pokud b > 1/2. Uvedeným způsobem jsem tedy našli WSE ve kterém je strategie hráče 1 EJ a hráč 2 má přesvědčení, že b > 1/2 a volí G nebo b — 1/2 a volí akci F s pravděpodobností nanejvýš 2/3. 9.4 Signalizace V podobě morálního hazardu jsme si představili situaci s asymetrickými informacemi. Jiný typ situace s asymetrickými informacemi představuje tzv. nepříznivý výběr. Na rozdíl od morálního hazardu se asymetrická informace netýká akce jednoho z hráčů, ale nějakého aspektu reality (např. produktivity pracovníka, kvality prodávaného zboží atd.). Obvykle takovou situaci modeluje se jako tah náhody a následně pomocí informační množiny. V signalizačních hrách si ukážeme, jak může informovaný hráč pomocí své zvolené akce signalizovat svou informaci neinformovanému hráči. Toto samozřejmě předpokládá, že hráč s informací hraje před hráčem bez informace a má tak možnost signalizovat svou informaci. Obvykle budeme předpokládat, že informovaný hráč může být různých typů a svou akcí může signalizovat jakého je typu. V signalizačních hrách nás potom zajímají dva druhy rovnováh • separační rovnováha je rovnováha ve které hráči různých typů volí jinou akci a neinformovaný hráč je tudíž umí rozlišit. • společná rovnováha ve které hráči různých typů volí stejnou akci a neinformovaný hráč je tudíž neumí rozlišit. Představme si situaci, kdy na trhu působí firmy, které produkují zboží o vysoké kvalitě H, a firmy, které produkují o nízké kvalitě L. Zatímco firmy kvalitu produktů znají, zákazníci zjistí kvalitu zboží až po prvním nákupu. Firmy se na začátku hry rozhodují o ceně p a množství sponzorských darů, reklamy či jiných výdajů E. Zákazníci se poté rozhodnou, zda zboží koupí K či nekoupí N. Ve druhém kole firma stanoví cenu a zákazníci, kteří koupili produkt v prvním kole, se opět rozhodnou o koupi, přičemž již znají kvalitu zboží. Pokud zákazník nekoupil zboží v prvním kole, nekoupí jej ani ve druhém kole. Označme H a L rezervační cenu zákazníka ze spotřeby zboží vysoké a nízké kvality. Náklady firem na produkci vysokého, resp. nízkého zboží jsou ch a cl, obdobně pu a pl značí cenu zboží vysoké a nízké kvality. Platí L — 0, cl — 0. Firma nemůže ovlivnit, zda produkuje zboží nízké nebo vysoké kvality, o tom rozhoduje náhoda. Ukážeme si, jestli může firma úrovní sponzoringu signalizovat, zda produkuje zboží nízké nebo vysoké kvality. Celá hra je zachycena na obrázku 12. Podívejme se na řešení této hry. Ve druhém kole se jedná o hru s dokonalými informacemi a můžeme použít zpětnou indukci. Podívejme se nejprve na situaci, kdy je zboží vysoké kvality. Firma stanovuje cenu a zákazník se poté rozhodne zda zboží koupí. Tato situace odpovídá ultimátní hře a firma tedy stanoví cenu ve výši zákazníkovi rezervační ceny, tj. p2 — H. Pokud je zboží nízké kvality, pak zákazník koupí zboží jen v případě, kdy bude jeho cena nulová. Firma vyrábějící zboží L může ve druhém období stanovit jakoukoliv cenu, její zisk ve druhém období však bude nulový. Nyní se podívejme, zda ve hře existuje separační rovnováha. V separační rovnováze volí obě firmy odlišnou úroveň sponzorských výdajů. Předpokládejme, že firma H volí úroveň E*H a firma L investuje do reklamy částku E*L. Přesvědčení zákazníků musí být v rovnováze konzistentní s akcemi firem. Pokud tedy zákazníci pozorují sponzorské výdaje ve výši E*H, věří, že se jedná o firmu H. Pokud naopak pozorují sponzorské výdaje ve výši E*L, věří, že se jedná o firmu L. Přesvědčení pro jiné úrovně E nejsou determinovaná (z definice WSE) Zdá se ovšem přirozené předpokládat, že pokud zákazníci pozorují úroveň -E, O 1 Pi, E 1 Pi, E Pi - E - cH, H - pi Pi - E - ch + p2 - ch, 2H -pi- p^ Pi - E - cL,L - px Pi - E - cL + p\ - cL, 2L - px - p\ Obrázek 12: Sponzoring výdajů vyšší než EH, pak jsou přesvědčeni, že se jedná o firmu vyrábějící kvalitní produkt a naopak. Jaká jsou optimální reakce firem v separační rovnováze? Firma L stanoví E*L — 0, cena firmy L je libovolná a zisk firmy L je nulový. Firma H stanoví cenu p\n — H. Aby byl uvedený profil akcí a přesvědčení separační rovnováhou, pak musí platit, že firma L nemá motivaci napodobit chování firmy H a naopak. Musí tedy platit následující dvě podmínky: 1. H — E*H < 0 (firma L nezvýší svůj zisk pokud stanoví E*L — E*H a pil — H) 2. 2H — E*H — 2ch > 0 (firma H nezvýší svůj zisk pokud stanoví E*H — 0) Pokud z obou podmínek vyjádříme rovnovážnou úroveň sponzorských výdajů firmy vyrábějící kvalitní produkt, pak zjistíme, že E*H e [H, 2H — 2ch\- Sponzorské výdaje tedy mohou plnit signalizační funkci. Jejich výše přitom musí být dostatečně velká, aby je byla ochotna podstoupit jen firma, která očekává, že bude na trhu působit delší dobu. 10 Opakované hry: Vězňovo dilema V dalších dvou kapitolách se podíváme na situace, kdy hráči interagují opakovaně. V této kapitole si ukážeme základní vlastnosti opakovaných her na nám již známém vězňově dilematu (tabulka 20). V další kapitole zde představené poznatky zobecníme. Hlavní ideou teorie opakovaných her je představa, že hráči mohou v opakovaných hrách dosáhnout jiných rovnováh než v jednorázových (one-shot) hrách. Hráči v opakovaných hrách totiž mohu být odrazeni od snahy dosáhnou krátkodobé výhody na úkor dlouhodobého zisku tím, že si mohou navzájem vyhrožovat a trestat se odepřením spolupráce v budoucích kolech. (Ve vězňově dilematu můžete druhého hráče potrestat tím, že v dalších kolech budete hrát akcí D namísto C). D C D 1,1 3,0 C 0,3 2,2 Tabulka 20: Vězňovo dilema 10.1 Preference a struktura opakované hry Opakovaná hra se skládá z určitého počtu, konečného nebo nekonečného, opakování nějaké strategické hry. Podívejme se, jak lidé oceňují výstup takové opakované hry? Budeme předpokládat, že lidé oceňují výsledek opakované hry pomocí diskontované sumy výplat z jednotlivých strategických her. Řečeno formálněji, mějme hráče i s výplatní funkcí pro danou strategickou hru Ui a diskontním faktorem Si G< 0,1 >. Takový hráč oceňuji sekvenci profilů akcí (a1, a2, ...,aT) následujícím způsobem: T u^a1) + Slul(a2) + S2ul(a3) + ... + ST~1ul(aT) = ^ S^u^a1) t=i U nekonečných her budeme místo sumy výplat budeme častěji používat diskontovaný průměr výplat. Předpokládejme sekvenci výplat z jednotlivých her (w1 ,w2...), diskontovanou sumu těchto výplat označme V, tj. V — YltLi ^*_lw*- Pro jakoukoliv sekvenci (w1, w2...) chceme najít sekvenci konstantních výplat (c, c,...) takovou, že hráč je indiferentní mezi těmito sekvencemi. Diskontovaná suma sekvence (c, c,...) je Y^g. Hráč je tedy indiferentní mezi těmito dvěma sekvencemi, pokud c — (1 — S)V. Hodnotu (1 — S)V — (1 — 5) YltĹi ^*_lw* nazveme diskontovaným průměrem výplat. Následující definice opakované hry nám říká, že na opakovanou hru se můžeme dívat jako na extenzivní hru, ve které se stále opakuje jedna a tatáž strategická hra. Definice 20. G je strategická hra. Označme množinu hráčů N a množinu akcí a výplat hráče í jako Ai a uí. Opakovaná hra pro pro T období a diskontní faktor S je extenzivní hra s dokonalými informacemi a současnými tahy ve které: • Množina hráčů je N • Množina konečných historií je množina sekvencí (a1, a2, ...,aT), kde a* je profil akcí v G • Hráčská funkce připisuje každé historii (a1,a*) všechny hráče • Množina akcí dostupná každému hráči po jakékoliv historii je Ai • Hráči hodnotí konečnou historii (a1, a2,aT) dle své sumy výplat YÍt=i ^l^1 uÁat) ne^° diskonto-vaného průměru výplat (1-S) Ef=i^_1«i(ať) Nekonečná hra je definována obdobně s tím rozdílem, že množina konečných historií je nekonečná sekvence (a1,a2,...) a výplata hráče í po konečné historii (a1,a2,...) je diskontovaný průměr výplat Y^tLi Sl^1ui(at). V obou případech jsou konečné historie nazývány rovněž trajektorie výsledků. Diskontní faktor, kterým hráči diskontují výplaty v různých kolech může mít několik různých interpretací, nám říká, že hráči preferují výplatu v současnosti před stejně velkou výplatou v budoucnosti. Existují tři běžná vysvětlení proč by tomu tak mělo být. Diskontní faktor může vyjadřovat • psychologickou netrpělivost hráčů. • pravděpodobnost, že hra bude v následujícím kole ukončena (např. proto, že hráč zemře) • časovou hodnotu peněz, pokud jsou výplaty měřeny v peněžních jednotkách. 10.2 Konečné vězňovo dilema Strategie v extenzivní hře specifikuje pro jakou akci se hráč rozhodne po jakékoliv historii, a protože opakovaná hra je určitou formou extenzivní hry, tak také strategie v konečné opakované hře specifikuje jakou akci hráč hraje na začátku hry a po jakékoliv sekvenci (a1, ...,a*). Konkrétně v případě vězňova dilematu nám strategie hry řekne, zda hráč po dané historii hraje akci D nebo C. Nyní si ukážeme, že konečně opakované vězňovo dilema má pouze jedinou Nashovu rovnováhu a tou je profil strategií v němž každý hráč hraje D v každém období. Konečnou historií generovanou těmito strategiemi tedy je ((£), D)1,(D, D)T). Skutečnost, že se jedná o Nashovu rovnováhu je zřejmá. Pokud jeden z hráčů hraje stále D, pak si druhý hráč nemůže polepšit, pokud bude hrát něco jiného než D. Ukážeme si proto nyní, proč se jedná o jedinou Nashovu rovnováhu. Předpokládejme, že (si,«2) je profil strategií ve kterém akce alespoň jednoho z hráčů v alespoň jednom období není D. Označme t poslední období, ve kterém profil akcí není (D, D). Předpokládejme, že hráč 1 hraje v tomto období C, pak hráč 1 může zvýšit svoji výplatu, když místo strategie s\ bude hrát strategii s[, která se od si liší pouze v tom, že v období t hraje hráč akci D. Tato strategie zvyšuje výplatu hráče, protože hráč 2 nemůže hráče za akci D v období t nijak potrestat - od t dále už stejně hraje D. Stejný argument však můžeme opakovat tak dlouho, dokud oba hráči nehrají akci D ve všech obdobích. Pokud bychom chtěli hledat SPE, pak se nám nabízí jediný kandidát. Víme totiž, že SPE musí být zároveň Nashovou rovnováhou. Zároveň víme, že každá extenzivní konečná hra s dokonalými informacemi má SPE. Strategie ve které oba hráči hrají vždy D je tudíž také SPE. 10.3 Nekonečné vězňovo dilema Viděli jsme, že v konečném vězňově dilematu se známým koncem nebudou hráči v rovnováze spolupracovat. Nyní se podíváme jak se situace změní, pokud hráči hrají nekonečně dlouho. Alternativně můžeme nekonečně opakovanou hru chápat jako hru, jejíž konec není hráčům znám. Hráči však mohou vědět, že hra skončí v každém kole s určitou pravděpodobností. Pravděpodobnost nepokračování hry se potom promítne do hodnoty diskontního faktoru. Strategie v nekonečné hře Strategie v nekonečné hře mohou být velmi komplexní a složité. Proto se většinou uvažují jen strategie, které jsou stacionární, tj. reagují na určitou akci či sekvenci akcí soupeřů vždy stejně bez ohledu na to ve kterém období jsou hrány. Často se takovým strategiím říká "automata", protože fungují jako kdyby se místo hráče rozhodoval stroj podle jasně daného algoritmu. Takové strategie můžeme znázorňovat pomocí diagramu. Uvažujme například strategii, která je definována takto: Sj(0) — Ca, Si(a}, ...,at) = < ( pokud (a1,a*) — (C,C) jinak Hráč hrající tuto strategii začíná hrát akci C a hraje ji tak dlouho, dokud i druhý hráč hraje C. V jakémkoliv jiném případě, tj. pokud druhý hráč zahraje D, hraje navždy jen D. Tato strategie je nazývána grim trigger. Tuto strategii můžeme nahlížet jako složenou ze dvou stavů v jednom označovaném C hraje hráč akci C, ve druhém D hraje akci D. Na začátku hry je nastaven stav C. Do stavu D strategie přejde, pokud druhý hráč zahraje akci D a zůstane v něm navždy. Tuto strategii lze jednoduše zakreslit diagramem z obrázku 13, kde (•, D) značí profil akcí ve kterém hráč 2 hraje D a hráč 1 hraje cokoliv. C:C I-A V: D 1-1 (,D) 1-1 Obrázek 13: Grim trigger strategie Obrázek 14 ukazuje strategii, která na rozdíl od grimm trigger netrestá po zbytek hry, ale po 3 kolech odpouští a vrací se do stavu C. Na obrázku 15 je ukázána strategie tit for tat. V tomto případě závisí délka trestu na chování druhého hráče. Pokud druhý hráč zahraje C, pak strategie přestává v dalším období trestat a přechází do stavu C. Jinými slovy, strategie tit for tat říká: "Udělej to, co udělal protihráč v předchozím období". Po: C (■-D) P\: D all P2:D all P3:D outcomes outcomes Obrázek 14: Strategie odpouštějící po 3 kolech ' :-,c) C:C -* V: D 1-1 (vD) Obrázek 15: Tit for tat strategie Nashovy rovnováhy v nekonečném vězňově dilematu Na začátku kapitoly jsme řekli, že hráči mohou v opakovaných hrách dosáhnout i méně ponurých rovnováh než je profil akcí (D,D) pomocí systému trestů a odepírání spolupráce. Uvedený princip si ukážeme na následujícím problému. Může být profil strategií ve kterém oba hráči hrají grim trigger strategii Nashovou rovnováhou? Pokud má být takový profil Nashovou rovnováhou, pak opět musí platit, že žádný z hráčů nemůže zvýšit svoji výplatu jednostranným odchýlením od strategie. Předpokládejme, že hráč 1 hraje grim trigger. Pokud hráč 2 hraje tu samou strategii, pak je výsledkem hry v každém období profil akcí (C,C) a hráč 2 tudíž obdrží sekvenci výplat (2,2,2,...), jejíž diskontovaný průměr je 2. Jestliže se hráč 2 odchýlí, pak v některém období zahraje D, na což hráč 1 reaguje tím, že hraje D po zbytek hry. Pro hráče 2 je pak nejvýhodnější hrát také D ve všech následujících obdobích. V takovém případě získá vektor výplat (3,1,1,...). Diskontovaný průměr těchto výplat je (1 - S)(3 + S + S2 + S3 + ...) = (1 - S)(3 + ---) = 3(1 - S) + S l — o Hráči 2 se tedy vyplatí odchýlit se, pokud 3(1 — S) + S 5= 2. Profil grim trigger strategií tedy tvoří Nashovu rovnováhu, pokud S ^ \. Podobných Nashových rovnováh bychom mohli v opakované hře najít velké množství. Podívejme se proto na Nashovy rovnováhy v nekonečně opakovaném vězňově dilematu z trochu jiného úhlu. Bude nás zajímat, jaké průměrné diskontované výplaty mohou být dosaženy v Nashových rovnováhách. Nejprve ukážeme jakých průměrných diskontovaných výplat vůbec mohou hráči v nekonečně opakovaném vězňově dilematu dosáhnout bez ohledu na to zda strategie, které hrají, tvoří Nashovu rovnováhu. Pokud budou hráči v každém období hrát akce (D,D), pak dosáhnou průměrné diskontované výplaty (1,1). Obdobně jsou jim při profilech akcí (C, C,), (C, D) a (D, C) dostupné průměrné diskontované výplaty (1,1), (3,0) a (0, 3). Hráči však nemusí hrát stále stejné akce, ale mohou střídat libovolné sekvence čtyř uvedených profilů. Průměrná výplata z jakékoliv konečné sekvence výstupů je vážený průměr jednotlivých výplat, přičemž váhy jsou dány počtem výskytů daného výstupu. Definujme tedy množinu dosažitelných výplat jako množinu všech vážených průměrů výplat z jednotlivých profilů akcí strategické hry. Prostor dosažitelných výplat ve vězňově dilematu je znázorněn na obrázku 16. Pro jakoukoliv strategickou hry (nejen pro vězňovo dilema) potom platí, že pokud je diskontní faktor dostatečně blízko 1, pak je množina možných průměrných diskontovaných výplat nekonečné hry přibližně rovna množině dosažitelných výplat. V případě vězňova dilematu to znamená, že pokud jsou hráči dostatečně trpěliví (tj. diskontní faktor je blízko 1), pak může být profil průměrných diskontovaných výplat v nekonečné hře jakákoliv dvojice čísel z prostoru zobrazeného na obrázku 16. Nyní se zamysleme, jakých výplat mohou trpělivý hráči dosáhnout v Nashově rovnováze nekonečně opakovaného vězňova dilematu. Podívejme se, znovu na obrázek 16 a zamysleme se, zda všechny dostupné výplaty mohou být výplatami v Nashově rovnováze. Je zjevné, že např. výplata (0,3) nemůže být výsledkem rovnovážných strategiích. Tato výplata totiž může nastat jedině v případě, kdy hráč 1 hraje v každém kole akci C, zatímco hráč 2 hraje vždy akci D. Takový profil strategií ale není Nashovou rovnováhou, protože hráč 1 si může v každém kole polepšit tím, že zahraje akci D. Tuto úvahu můžeme T m 3 payoff (0,3) (2,2) (1,1) (3,0) 2 3 ľs payoff Obrázek 16: Dosažitelně výplaty použít na jakýkoliv bod, ve kterém je průměrná diskontovaná výplata jednoho z hráčů menší než 1. V takovém případě si totiž daný hráč může polepšit tím, že začne hrát v každém kole akci D. Pomocí této úvahy jsme zúžili množinu výplat dostupných hráčům při rovnovážných strategiích na prostor na obrázku 17. T 2's 3 payoff 0 12 3 ľs payoff —> Obrázek 17: Výplaty dosažitelné v Nashově rovnováze Žádné další zúžení však není možné, všechny zobrazené výplaty mohou být podpořeny rovnovážnými strategiemi. K důkazu tohoto tvrzení použijeme následující argument. Označme (xi,x2) dvojici diskon-tovaných průměrných výplat v nekonečném vězňově dilematu pro něž platí, že Xi > Ui(D, D). Z definice dosažitelných výplat víme, že můžeme najít takovou sekvenci profilů akcí (a1,...,afe) pro než platí, že průměrná diskontovaná výplata trpělivého hráče i je blízko Xj. Nyní uvažujme trajektorii výstupů v nekonečně opakované hře, která se skládá z opakování sekvence (a1,...,afe). Označme tuto trajektorii (b1^2...), kde bqk+t — a* pro q — 0,1,... a t — í,...,k. Můžeme ukázat, že pokud všichni hráči hrají následující strategii sl{h1 pokud hj jinak K pro r ,í-l pak je tato situace Nashovou rovnováhou. Uvedená strategie říká, že každý hráč hraje takové akce, aby se opakovala trajektorie výstupů (b1, b2...) tak dlouho, dokud se ostatní hráči chovají také tak. Pokud se některý z hráčů odchýlí, pak všichni hráči začnou hrát akci D. Abychom dokázali, že profil těchto strategií tvoří Nashovu rovnováhu, musíme ukázat, že žádnému z hráčů se nevyplatí jednostranně se odchýlit od této strategie. Argument je stručně shrnut v tabulce 21. Předpokládejme, že hráč se 1 odchýlí od své strategie s± v periodě l. V této periodě obdrží výplatu 1,Z — 1 l l + í,...,k l,...,k l,...,k odchýlení ui(al) ui(al+1),ui(ak) v1 Ul(D,D),...,Ul(D,D) >u1(D,D) ui(D,D) >u1(D,D) ui(D,D) Tabulka 21: Nashova rovnováha v nekonečně opakované hře v1. Od následující periody je jeho výplata u\(D, D). V období, kdy se odchýlil, a v následujících k — l obdobích do konce sekvence si může hráč číslo 1 odchýlením polepšit oproti strategii s\. Ale jeho průměrná diskontovaná výplata v následující cyklech (a1,ak) je v případě odchýlení nižší než v případě strategie s\. Pokud je diskontní faktor hráče dostatečně blízko 1, pak tyto ztráty převýší potencionální zisk z období l a následujících k — l období. Propozice 5. Folk teorém pro nekonečně opakované vězňovo dilema. G označuje vězňovo dilema. • Pro jakýkoli diskontní faktor je průměrná diskontovaná výplata každého hráče v Nashově rovnováze alespoň uí(D, D). • (xi,x2) je dosažitelný pár výplat v G, pro který platí x i > uí(D,D). Vždy existuje S < 1, taková že pro každé S > S má nekonečně opakované vězňovo dilema Nashovu rovnováhu ve které průměrná diskontovaná výplata hráče i je Xj. SPE v nekonečném vězňově dilematu Při studiu extenzivních her jsme viděli, že Nashova rovnováha dovoluje hráčům podléhat nekredibilním hrozbám. Stejný problém se objevuje i u Nashovy rovnováhy v nekonečných hrách. Tento problém řeší koncept SPE. K nalezení SPE v nekonečných hrách využijeme následující vlastnost. Definice 21. Vlastnost jedné odchylky (one-deviation). Profil strategie splňuje vlastnost jedné odchylky, pokud žádný hráč nemůže zvýšit svoji výplatu změnou akce na začátku každé podhry, ve které je na tahu jako první, při daných strategiích ostatních hráčů a zbytku své strategie. Propozice 6. Profil strategií v konečné hře a nekonečné hře s diskontním faktorem menším než 1 je SPE právě tehdy, když splňuje vlastnost jedné odchylky. Použití vlastnosti jednoho odchýlení si ukážeme na příkladu vězňova dilematu (tabulka 20) a profilu strategií (si,«2), kde Si označuje strategii tit-for-tat. Při této strategii závisí chování pouze na tom, co se stalo v předchozím kole. Ve hře se mohou objevit celkem 4 různé podhry. Ke zjištění, zdali profil strategií tit-for-tat tvoří SPE musíme vyšetřit, zda se v těchto podhrách hráči vyplatí jednostranné odchýlení. • Podhra po historii končící (C,C): Pokud se hráč drží své strategie, pak obdrží diskontovanou průměrnou výplatu 2. Pokud se na začátku podhry odchýlí, pak je výsledek v následujícím kole (D,C). Hráči se dále drží svých strategií a výsledek hry se proto střídá mezi (C,D) a (D,C). Tit-fot-tat je proto v této podhře optimální odpověď, pokud 2 ^ (1 - S)(3 + 3S2 + 3S4 + ...) = ^S^\ l + o 2 • Podhra po historii končící (C,D): Pokud se hráč drží své strategie, pak v dalším kole hraje D a dále se střídají výsledky (D,C) a (C,D). Pokud se hráč od své strategie na začátku podhry odchýlí, pak je při dané strategii druhého hráče a zbytku jeho strategie ve všech dalších obdobích výsledek (C,C). Tit-fot-tat je proto v této podhře optimální odpověď, pokud (1 - S)(3 + 3S2 + 3S4 + ...) = > 2 S < i • Podhra po historii končící (D,C): Pokud se hráč drží své strategie, pak v dalším kole hraje C a dále se při dané strategii druhého hráče střídají výsledky (C,D) a (D,C). Pokud se hráč od své strategie na začátku podhry odchýlí a hraje D, pak je při dané strategii druhého hráče a zbytku jeho strategie ve všech dalších obdobích výsledek (D,D). Tit-fot-tat je proto v této podhře optimální odpověď, pokud (1 - S)(3S + 3S3 + 3S5 + ...) = ^ 1 => S ^ i l + o 2 • Podhra po historii končící (D,D): Pomocí stejného argumentu ukážeme, že aby tit-for-tat bylo optimální v této podhře, pak musí platit 1 > (1 - S)(3S + 3S3 + 3S5 + ...) = => S < ^ ~ í + 6 ~ 2 Kombinací uvedených podmínek, zjistíme, že tit-for-tat tvoří SPE v nekonečně opakovaném vězňově dilematu právě tehdy, když S — \ Stejně jako v případě Nashovy rovnováhy můžeme formulovat folk teorém také pro SPE. Důkaz folk teorému je v případě SPE založen na stejné strategii jako v případě Nashovy rovnováhy. Stačí pouze ukázat, že v podhře po jiné historii než (b1,6t_1) se hráči na začátku podhry nevyplatí odchýlení od jeho strategie. Propozice 7. Folk teorém pro nekonečně opakované vězňovo dilema. G označuje vězňovo dilema. • Pro jakýkoli diskontní faktor je průměrná diskontovaná výplata každého hráče v SPE alespoň uí(D, D). • (xi,x2) je dosažitelný pár výplat v G, pro který platí xí > uí(D,D). Vždy existuje S < 1, taková že pro každé S > Š má nekonečně opakované vězňovo dilema SPE ve které průměrná diskontovaná výplata hráče í je xí. 11 Opakované hry: Zobecnění 11.1 Nashova rovnováha v nekonečně opakovaných hrách Minmax výplata V předchozí kapitole jsem ukázali, že nekonečně opakované vězňovo dilema má mnoho rovnováha a folk teorém nám řekl jakých výplat mohou hráči v těchto rovnováhách dosahovat. Nyní se pokusíme folk teorém zobecnit pro jakoukoliv strategickou hru. Ve vězňově dilematu nemohl žádný z hráčů získat menší průměrnou diskontovanou výplatu než 1. Toto byla totiž nejnižší výplata k jaké mohl být určitý hráč akcemi ostatních hráčů přinucen. Obecně můžeme takovou výplatu označit jako tzv. minmax výplatu. Jak můžeme takovou výplatu obecně najít? Racionální hráč ve strategické hře hraje svoji optimální odpověď, tj. vybírá si akci, tak aby splňovala max uAclí, a-A ateAt Nyní hledáme minimální výplatu z této množiny. Ostatní hráči totiž mohou chtít daného hráče potrestat za odchýlení od určité strategie, a to udělají tak, že budou hrát akce, které danému hráči přinesou co nejmenší výplatu. Minmax výplatu tedy definujeme následovně: min m&x Ui(a>i, a-i) Všimněte si, že není nutné, aby hodnota minmax výplaty byla stejná pro každého hráče (jako se stalo ve vězňově dilematu, kde byla tato hodnota rovna 1). Taková situace je výjimečná. Obecně jsou hodnota minmax výplaty a akce generující minmax výplatu pro každého hráče různé. Folk teorém pro Nashovu rovnováhu Je zjevné, že v rovnováze nekonečně opakované hry nemůže výplata žádného hráče klesnou pod jeho minmax výplatu. V takovém případě by totiž hráč mohl zvýšit svoji výplatu, pokud by hrál max^g^i Ui(a,i,a-i), tj. v každém kole by hrál svou optimální odpověď na akce ostatních v tomto kole. Stejně jako v případě vězňova dilematu může ale být jakýkoliv jiný výsledek vygenerován rovnovážným profilem strategií. Konkrétně ukážeme, že jakákoliv sekvence profilů akcí (b,b,...), kde Ui(b) je větší než minmax výplata, může být Nashovou rovnováhou. Uvažujme následující strategii, kde (p-j)i označuje takovou strategii hráče i, která přináší hráči j minmax výplatu: Sj(0) — bi a bi pokud (a1, ...a* 1) — (b, ...,b) (p-j)i pokud (a1, ...a*-1) ^ (b, ...,b) a hráč j je prvním hráčem, který se sám odchýlil Jedná se tedy vlastně o obdobu grim-trigger strategie, která trestá hráče, který se jako první sám odchýlí. Všimněte si, že strategie nespustí trest pokud se odchýlí více hráčů. To nám však nijak nevadí, protože Nashova rovnováha vyžaduje pouze, aby se jednotlivému hráči nevyplatilo odchýlit se. Profil takových strategií tvoří Nashovu rovnováhu. Hráč, který se drží strategie, obdrží v každém období výplatu Ui(b). Pokud se hráč odchýlí, tak si může v prvním období polepšit, ale v každém dalším období získá jen minmax výplatu. A pokud je diskontní faktor dostatečně blízko 1, pak se odchýlení hráči nevyplatí. (Stejný argument platí i v případě, že se výsledky hry střídají v určitých cyklech, tak jako jsem ukázali u vězňova dilematu). Propozice 8. Folk teorém pro Nashovu rovnováhu. • Pro jakýkoliv diskontní faktor je průměrná diskontovaná výplata každého hráče v Nashově rovnováze alespoň jeho minmax výplata. • x je dosažitelný profil výplat v G, pro který platí, že xí je větší než minmax výplata hráče í. Pak vždy existuje S < 1, taková že pro každé S > S má nekonečně opakovaná hra Nashovu rovnováhu ve které průměrná diskontovaná výplata hráče í je xí. 11.2 SPE v nekonečně opakovaných hrách Ve vězňově dilematu byl přechod od Nashovy rovnováhy k SPE jednoduchý. Stejná strategie, kterou jsem použili při důkazu folk teorému pro Nashovu rovnováhu jsme použili i v případě SPE. Obecně to však takto jednoduché být nemusí. Důvodem je skutečnost, že v případě vězňova dilematu je profil akcí vedoucí k minmax výplatě zároveň Nashovou rovnováhou. Toto ale neplatí vždy. Hráči pak při trestání deviantního hráče mohou hrát akci, která není jejich optimální odpovědí na akci deviantního hráče. V takovém případě je hrozba hráčů, že budou takto trestat po celý zbytek hry, nekredibilní. Stejně jako v předchozím případě ukážeme, jakým způsobem může být v SPE dosaženo výsledku (a, a,...), kde Ui(a) je větší než minmax výplata hráče i. (rozšíření na výsledky, které nejsou stejné, se provede stejně jako v případě vězňova dilematu). Dále označme p j jako akci hráče i, která přináší hráči j jeho minmax výplatu. Pro jednoduchost předpokládejme dva hráče. Profil akcí (p2,Pi) značí, že se hráči navzájem trestají. Vezmeme si nyní strategii z obrázku 18. Tato strategie říká hráči, aby na začátku hrál a,i dokud je výsledek hry v každém kole a. V opačném případě začne hrát pj a bude ji hrát po k period, pokud druhý hráč hraje pi. Pokud druhý hráč přestane během této doby trestat, tj. nezahraje pi, pak se trest začne odvíjet znova a opět trvá k období. Všimněte si, že tato strategie trestá nejen odchýlení se od akce en, ale také to, že druhý hráč přestane s trestem příliš brzo. I I not p I not Obrázek 18: SPE strategie Nyní ukáži, že je možné najít S a funkci k takové, že pro S > S a k — k (ô) tvoří profil těchto strategií SPE. Musím tedy ukázat, že platí vlastnost jednoho odchýlení. • Podhra vedoucí do stavu N. Pokud se hráč odchýlí, pak v první periodě může získat svou maximální výplatu ve hře, označme ji Tíi. Po k period poté získá výplatu Ui(p), která je nižší nebo rovna minmaxové výplatě. Pokud se hráč drží své strategie, pak v každé z k + 1 period získá Ui(a). Ve zbytku hry není mezi odchýlením a dodržením strategie rozdíl. Podmínka optimality strategie v této podhře je tedy Ui(a)(l + 5 + ... + 5k) ^ul+ ul(p)(5 + ... + 5k) Což můžeme vyjádřit jako (S + ... + Sk)(ui(a) — Ui(p)) ^ Tíi — Ui(a) • Podhra vedoucí do některého ze stavů p. Pokud hráč dodrží strategii, pak získá Ui(p) v následujících k — l + 1 periodách a dále získá Ui(a). Pokud se odchýlí, pak v prvním období získá minmax výplatu rrii, v k obdobích Ui(p) a poté Ui(a). Podmínka optimality je tudíž Ui(p)(l + 5 + ... + 5k-1) + Ul(a)(5k-l+1 + ... + 5k) ^m, + u,{p){\ + 5 + ... + 5k) Pokud je tato podmínka splněna, pro 1 = 1, pak je jistě splněna také pro l > 1. Můžeme ji tedy vyjádřit jako ôk(ul(a) - Ui(p)) ^ml- Ui(p) Pro S = 1 jistě existuje dostatečně velké k* takové, že obě podmínky jsou splněny. Tudíž jistě existuje S' < 1 taková, že pro k = k* a S > S' jsou obě podmínky splněny. Uvedený profil strategií pak tvoří SPE a my můžeme formulovat následující folk teorém. Propozice 9. Folk teorém pro SPE. • Pro jakýkoli diskontní faktor je průměrná diskontovaná výplata každého hráče v SPE alespoň jeho minmax výplata. • x je dosažitelný profil výplat v G, pro který platí, že xí je větší než minmax výplata hráče í. Pak vždy existuje Š < 1, taková že pro každé S > S má nekonečně opakovaná hra SPE ve které průměrná diskontovaná výplata hráče í je xí. 11.3 Aplikace Vyjednávání V této části si ukážeme tzv. Rubinsteinův model vyjednávání. Tento model má podobu nekonečně se opakující hry ve které se dvě vyjednávači strany střídají v tom, kdo dává návrh na rozdělení určité peněžní částky normované na hodnotu 1. Přičemž hra končí, když druhá strana s návrhem souhlasí. Formálně je hra definována následujícím způsobem • Hráči 1 a 2 • Konečné historie mají formu buď konečné sekvence (x\, N, x2, N, ...x\, Y) nebo nekonečné sekvence (x1, N, x2, N,...), kde xí značí nabídku hráče i, N značí odmítnutí nabídky a y je přijetí nabídky • Hráčská funkce P(0) = 1, P^1) = 2, P^1, N) = 2 atd. • Preference jsou dány užitkovou funkcí Ui(..., x\,Y) = 5t^1x\ a Uj{...,x\,Y) = 5t_1(l — x\). V případě, že se hráči nikdy neshodnou je jejich výplata 0. Jelikož má hra nekonečný horizont nemůžeme použít zpětnou indukci k nalezení SPE. Předpokládejme ovšem, že hráči se v rovnováze okamžitě dohodnou a zároveň předpokládejme, že rovnováha je stacionární (tj. v rovnováze se oba hráči v každé periodě chovají stejně). Pokud má mít hra takovou rovnováhu, pak si hráč nemůže polepšit tím, že odmítne nabídku druhé strany a v dalším kole dá svou rovnovážnou nabídku. Označme rovnovážnou nabídku hráče 1 a 2 jako x\ a x\. Jelikož hráči si dělí částku o velikosti 1, musí platit tyto dvě podmínky (í — xl) = ô2x*2 a (1 — x*2) = 5\x\. Řešením soustavy těchto dvou rovnic získáme rovnovážné nabídky. Rovnováha hry je potom následující dvojice strategií • Hráč 1 nabízí x\ a akceptuje nabídku x2 právě tehdy když 1 — x2 > Sixl • Hráč 2 nabízí x2 a akceptuje nabídku x\ právě tehdy když 1 — x\ > S2x2 • Kue x1 — 1_sió2 a x2 — 1_SlS,2 Uvedené tvrzení lze dokázat, pokud ověříme, že uvedená dvojice strategií splňuje vlastnost jednoho odchýlení. Uvažujme tedy postupně všechny podhry, které začínají nabídkou hráče 1 a odpovědí hráče 1 na nabídku hráče 2. 1. Uvažujme nejprve podhru, která začíná nabídkou hráče 1. Je zjevné ,že si hráč 1 nepolepší, pokud nabídne x < x\. Předpokládejme, že se hráč 1 jednou odchýlí a nabídne x > x\, pak hráč 2 nabídku odmítne. V dalším kole hráč 2 nabídne x2 a hráč 1 tuto nabídku akceptuje. Jeho výplata je 5i(l— x2) < 2. Uvažujme podhru, která začíná odpovědí hráče 1 na rovnovážnou nabídku hráče 2. Předpokládejme, že se hráč 1 jednou odchýlí a nabídku odmítne. V dalším kole hráč 1 nabídne x\ a hráč 2 tuto nabídku akceptuje. Výplata hráče je potom 5\x\ = (1 — x2). Hráči 1 se tudíž nevyplatí se odchýlit. 3. Uvažujme podhru, která začíná odpovědí hráče 1 na nabídku hráče 2x2 > x2. Stejně jako v předchozím případě můžeme ukázat, že hráči se nevyplatí takovou nabídku odmítnout. 4. Uvažujme podhru, která začíná odpovědí hráče 1 na nabídku hráče 2 x2 > x2. Předpokládejme, že se hráč 1 jednorázově odchýlí od své strategie a nabídku přijme. Potom získá výplatu 1 — x2. Pokud by se držel hráč 1 své strategie, pak by v dalším kole získal výplatu 5\x\ > 1 — x2. Hráči 1 se tudíž nevyplatí odchýlit se od své strategie. Symetrické argumenty fungují také pro podhry, které začínají nabídkou hráče 2 a odpovědí hráče 2. Dá se dokázat, že právě představená rovnováha je jedinou rovnováhu této vyjednávači hry. Tato rovnováha má tři zajímavé vlastnosti. Zaprvé, vyjednávání je efektivní, tzn. že hráči se dohodnou hned na začátku hry a nedochází ke ztrátám způsobeným pozdní dohodou. Za druhé, čím trpělivější hráč je, tím větší část si vyjedná pro sebe. Za třetí, hráč, který začíná, má ve vyjednávání výhodu.