Doprovodné texty ke kurzu Teorie her

Doprovodné texty ke kurzu Teorie her

Martin Hrubý Fakulta informaˇcn´ıch technologi´ı Vysoké uˇcen´ı technické v Brnˇe

zimn´ı semestr, akad. rok 2010/11

1

Contents 1

2

3

4

´ Uvod do Teorie her 1.1 Hern´ı situace . . . . . . . . . . . . . . . . . . . . 1.1.1 Rozdˇelen´ı her . . . . . . . . . . . . . . . . 1.1.2 Jak se hraje nekooperativn´ı strategická hra? 1.2 Informace ve hˇre . . . . . . . . . . . . . . . . . . 1.3 Analýza hry . . . . . . . . . . . . . . . . . . . . . 1.3.1 Dominance mezi strategiemi ve hˇre . . . . 1.4 Vˇezˇnovo dilema . . . . . . . . . . . . . . . . . . . 1.5 Rovnovázˇ ný stav ve hˇre (ekvilibrium) . . . . . . . 1.5.1 Intiutivn´ı algoritmus nalezen´ı PNE . . . . . 1.6 Iterativn´ı eliminace dominovaných strategi´ı . . . . 1.6.1 Strategická ekvivalence her . . . . . . . . . 1.6.2 Algoritmus eliminace . . . . . . . . . . . . 1.7 Efektivita profilu a Pareto dominance . . . . . . .

. . . . . . . . . . . . .

4 4 7 8 9 10 11 12 14 15 16 16 16 17

. . . .

18 19 22 24 24

. . . . .

26 27 28 29 30 31

Problém existence ekvilibria ve hrách s nenulovým souˇctem 4.1 Kompaktn´ı a konvexn´ı mnoˇzina . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32 32

˚ model oligopolu Cournotuv 2.1 Cournotovo ˇreˇsen´ı duopolu . . . . . . . . . . . ˇ sen´ı oligopol˚u . . . . . . . . . . . . . . . . 2.2 Reˇ 2.3 Bertrand˚uv model oligopolu (1883) . . . . . . 2.4 Závˇer kapitoly o Cournotovˇe modelu oligopolu

. . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

Hry bez Nashova ekvilibria v ryz´ıch strategi´ıch 3.1 Sm´ısˇené rozˇs´ıˇren´ı nekooperativn´ı hry . . . . . . . . . . . . . . . . 3.2 Smysl a interpretace sm´ısˇených strategi´ı . . . . . . . . . . . . . . 3.3 Výpoˇcet sm´ısˇené rovnováhy – hledán´ı pr˚useˇc´ıku reakˇcn´ıch kˇrivek 3.4 Výpoˇcet sm´ısˇené rovnováhy – obecný algoritmus . . . . . . . . . 3.5 Vˇeta o existenci sm´ısˇeného Nashova ekvilibria . . . . . . . . . . .

2

. . . . . . . . . . . . .

. . . .

. . . . .

. . . . . . . . . . . . .

. . . .

. . . . .

. . . . . . . . . . . . .

. . . .

. . . . .

. . . . . . . . . . . . .

. . . .

. . . . .

. . . . . . . . . . . . .

. . . .

. . . . .

. . . . . . . . . . . . .

. . . .

. . . . .

. . . . . . . . . . . . .

. . . .

. . . . .

. . . . . . . . . . . . .

. . . .

. . . . .

. . . . . . . . . . . . .

. . . .

. . . . .

4.2 4.3 4.4 4.5 4.6 4.7 5

6

Ryze kvazi-konkávn´ı funkce . . . . . . . . . . . . . . . . Existence Nashova ekvilibria ve hrách se spojitými Si . . . Sm´ısˇená best-response hrácˇ e ve sm´ısˇeném profilu . . . . . Pevný bod korespondence . . . . . . . . . . . . . . . . . Kakutani’s fixed point theorem . . . . . . . . . . . . . . . D˚ukaz Nashovy vˇety o existenci MNE v koneˇcných hrách .

Nekooperativn´ı hry s nulovým souˇctem 5.1 Vztah nulového a konstantn´ıho souˇctu . . . . . . . . 5.2 Zápis 0-sum hry . . . . . . . . . . . . . . . . . . . . 5.3 Chován´ı hrácˇ e v 0-sum hˇre . . . . . . . . . . . . . . 5.4 Rovnovázˇ né strategie tvoˇr´ıc´ı ekvilibrium ve hˇre . . . 5.5 Sedlový bod (saddle point) . . . . . . . . . . . . . . 5.6 Ekvilibrium 0-sum her ve sm´ısˇených strategi´ıch . . . 5.7 Grafické ˇreˇsen´ı maticových her ve tvaru (2,n) strategi´ı Korelované ekvilibrium v nekooperativn´ıch hrách 6.1 Motivaˇcn´ı pˇr´ıklad . . . . . . . . . . . . . . . . . 6.2 Definice korelovaného ekvilibria . . . . . . . . . 6.3 Výpoˇcet CE obecnˇe (LP-úloha) . . . . . . . . . . 6.4 Princip CE obecnˇe – analytický efekt G-matice . 6.5 Optimalizovaný výpoˇcet CE ve hˇre (Hrubý, 2008) 6.5.1 Redukce G-matice v naˇsem pˇr´ıkladˇe . . .

3

. . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . .

32 33 33 34 35 36

. . . . . . .

39 40 41 42 43 44 45 46

. . . . . .

49 49 51 52 54 54 55

Chapter 1 ´ Uvod do Teorie her Tato kapitola je základem pro studium hern´ıch situac´ı. Bude definován pojem hra, informace ve hˇre a ekvilibrium.

1.1

Hern´ı situace

Hrou se rozum´ı strategická interaktivn´ı situace zahrnuj´ıc´ı alespoˇn dva hrácˇ e, kde kaˇzdý sleduje své vlastn´ı c´ıle a projevuje tak svou individuáln´ı racionalitu. Hry jsou matematické modely situac´ı, kdy hrácˇ i zúcˇ astnˇen´ı v situaci jsou nuceni provést nˇejaké rozhodnut´ı. Nezkoumáme, zda-li se hrácˇ u˚ m l´ıb´ı být u´ cˇ astn´ıky dané situace, zda chtˇej´ı hrát nebo nechtˇej´ı. Hra je model, a proto je zjednoduˇsen´ım situace na nˇekolik základn´ıch prvk˚u, které situaci popisuj´ı. Jsou to tyto prvky: 1. Hrácˇ i zúcˇ astnˇen´ı ve hˇre. Od nich se oˇcekává proveden´ı jejich rozhodnut´ı. 2. Popis moˇzných akc´ı, které hrácˇ i mohou provést. Pojem akce, strategie, alternativa jsou zde pouˇz´ıvány jako synonyma. Pokud bychom pˇresto chtˇeli mezi nimi rozliˇsovat, pak ˇrekneme, zˇ e literatura pouˇz´ıvá pojem strategie jako formáln´ı vyjádˇren´ı hrácˇ ova rozhodnut´ı a pojem akce, pokud chce zd˚uraznit, zˇ e strategie vede k nˇejaké aktivitˇe hrácˇ e. 3. Vyjádˇren´ı d˚usledk˚u akc´ı hrácˇ u˚ . Budeme zde mluvit o uˇzitkových nebo výplatn´ıch funkc´ıch. 4. Model m´ıry informace, jakou hrácˇ i maj´ı o zkoumané situaci. Tento fakt je ve hrách zásadn´ı. Budeme definovat pojmy spoleˇcná znalost (angl. common knowledge) a u´ plná informace (angl. complete information) o hˇre. 5. Pˇredpokládaný pr˚ubˇeh hry. V zásadˇe existuje dvoj´ı pˇr´ıstup k odehrán´ı hry – hra jedno-tahová a v´ıce-tahová. O v´ıce-tahových hrách bude pojednávat kapitola ”Hry v rozˇs´ıˇrené formˇe”. 6. Moˇznosti komunikace hrácˇ u˚ a tvorby spoleˇcné dohody o volbˇe strategie. 4

Obecnˇe se hry dˇel´ı na kooperativn´ı (angl. cooperative games) a nekooperativn´ı (angl. noncooperative games) podle toho, jak mohou hrácˇ i spolupracovat, resp. komunikovat pˇri volbˇe své akce. V obou pˇr´ıpadech vˇsak pˇredpokládáme u vˇsech hrácˇ u˚ naprosto striktnˇe jejich orientaci na optimalizaci vlastn´ıho zisku ze situace. Literatura cˇ asto také hovoˇr´ı o sobeckém chován´ı hrácˇ u˚ (selfish agents), ovˇsem zde nelze pojem sobeckosti chápat jako nˇeco negativn´ıho v mezilidských vztaz´ıch, sp´ısˇe jako zd˚uraznˇen´ı ryz´ı individuáln´ı racionality. Pokud budeme pˇresto zkoumat interaktivn´ı situace, kde lze u nˇekterých hrácˇ u˚ pozorovat uspokojen´ı ze zisku jejich protihrácˇ u˚ (napˇr. situace rodiˇc verus d´ıtˇe), pak je toto uspokojen´ı zahrnuto v zisku rodiˇce a dále pak zkoumáme tohoto hrácˇ e z hlediska jeho individuáln´ı racionality. Kooperativn´ı a nekooperativn´ı hry jsou naprosto odliˇsné v pojet´ı strategie a zp˚usobu proveden´ı hry. U nekooperativn´ıch her vid´ıme hrácˇ e, jejich strategie a uˇzitkové funkce. Pˇredpokládáme, zˇ e hrácˇ i o hˇre nekomunikuj´ı, ale pˇresto pˇremýsˇl´ı o tahu svých protivn´ık˚u. Studiem tˇechto her dojdeme posléze k poznán´ı, zˇ e výsledek hry by pro vˇsechny zúcˇ astnˇené hrácˇ e mohl být (mnohdy i znaˇcnˇe) lepˇs´ı, pokud by se domluvili na spoleˇcné akci. Otv´ıraj´ı se tak moˇznosti komunikace, vyjednáván´ı a kooperace. U kooperativn´ıch her uvid´ıme, zˇ e v sobˇe obsahuj´ı nekooperativn´ı podstatu a zˇ e kooperace je moˇzná pouze pokud vˇsichni hrácˇ i vid´ı pˇr´ıpadné zlepˇsen´ı svého moˇzného výsledku hry plynouc´ı z komunikace. V teorii volby (pˇredchoz´ı kapitola) jsme zavedli hrácˇ ovy akce (strategie) a jejich moˇzné d˚usledky. Ukázali jsme hrácˇ ovy preference, aˇt uˇz na mnoˇzinˇe strategi´ı nebo na mnoˇzinˇe uˇzitk˚u. V hernˇe teoretické praxi je cˇ astˇejˇs´ı vn´ımat preference na mnoˇzinˇe uˇzitk˚u, které jsou kvatifikovány do cˇ´ısel a intuitivnˇe porovnatelné. Proto budeme nadále jiˇz mluvit o strategi´ıch a uˇzitkových funkc´ıch. Zavedeme si nyn´ı formáln´ı definici nekooperativn´ı hry N hrácˇ u˚ . Podotknˇeme, zˇ e symbol N bude v tomto textu pouˇz´ıván výhradnˇe pro oznaˇcen´ı poˇctu hrácˇ u˚ ve hˇre. Definice 1. Strategická nekooperativn´ı hra N hrácˇ u˚ je (2N + 1)-tice Γ = (Q; S1 , S2 , ..., SN ; U1 , U2 , ..., UN ) kde: • Q = {1, 2, ..., N } je koneˇcná mnoˇzina hrácˇ u˚ ve hˇre. • Si , i ∈ Q jsou (koneˇcné) mnoˇziny ryz´ıch strategi´ı hrácˇ u˚ i ∈ Q. • Ui : S1 × S2 × ... × SN → U jsou funkce uˇzitku hrácˇ u˚ . Symbolem Q bude vˇzdy oznaˇcována mnoˇzina hrácˇ u˚ . Symbolem Si bude vˇzdy oznaˇcována mnoˇzina strategi´ı hrácˇ e i ∈ Q. Vˇsimnˇeme si nyn´ı funkc´ı uˇzitku Ui . V této definici má kaˇzdý hrácˇ svoji funkci uˇzitku. Alternativnˇe je moˇzno psát U : S1 ×S2 ×...×SN → UR , ovˇsem tento zápis nen´ı zaveden, ponˇevadˇz cˇ asto pracujeme 5

s jednotlivými uˇzitky hrácˇ u˚ . Podstatným faktem uˇzitkové funkce je jej´ı definiˇcn´ı obor definovaný jako kartézský souˇcin mnoˇzin strategi´ı vˇsech hrácˇ u˚ : S = S1 × S2 × ... × SN coˇz také cˇ asto p´ısˇeme zkrácenˇe jako S=

Y

Si

i∈Q

Mnoˇzina S je významným popisem hry, neboˇt modeluje veˇskeré moˇzné výsledky hry. Tuto mnoˇzinu nazýváme mnoˇzinou strategických profil˚u hry a jej´ı prvky (s1 , s2 , ..., sN ) pak strategickými profily. Uˇzitkové funkce hrácˇ u˚ jsou definovány na mnoˇzinˇe profil˚u proto, zˇ e uˇzitek hrácˇ e nen´ı dán pouze jeho rozhodnut´ım s∗i ∈ Si , ale i tahy jeho protihrácˇ u˚ s∗−i ∈ S−i . Vedle mnoˇziny S je velmi významnou (a v budouc´ım textu cˇ asto citovanou) mnoˇzinou mnoˇzina sub-profil˚u. Mnoˇzinou sub-profil˚u z hlediska hrácˇ e i je S−i = S1 × S2 × ... × Si−1 × Si+1 × ... × SN tedy zkrácenˇe S−i =

Y

Sj

j∈Q\{i}

Sub-profil s−i ∈ S−i modeluje kontext rozhodován´ı hrácˇ e i. Je to vektor konkrétn´ıch tah˚u jeho protihrácˇ u˚ . Zápisem (si , s−i ) budeme rozumˇet sloˇzen´ı strategie si hrácˇ e i s kontextem protihrácˇ u˚ s−i – tedy (si , s−i ) ∈ S. Oborem hodnot uˇzitkové funkce hrácˇ e m˚uzˇ e být jakési univerzum U, ale ve vˇetˇsinˇe pˇr´ıpad˚u klademe U = R a uˇzitky povaˇzujeme za reálná cˇ´ısla. T´ım je dáno i vn´ımán´ı preferenc´ı hrácˇ u˚ nad dosaˇzitelnými uˇzitky. V dalˇs´ım textu zavedeme jisté stochastické rozˇs´ıˇren´ı nekooperativn´ı hry a tud´ızˇ i novou formu strategi´ı. Abychom rozliˇsili tyto výsˇe uvedené strategie a ty budouc´ı rozˇs´ıˇrené, zavedeme pˇresnˇejˇs´ı oznaˇcen´ı strategi´ı hrácˇ u˚ – budou to tak zvané ryz´ı strategie (angl. pure strategies). Pokud bude v dalˇs´ım textu pouˇzit pojem strategie, pak je závislý na daném kontextu textu, implicitnˇe vˇsak je m´ınˇena ryz´ı strategie. T´ımto jsme zavedli definici nejobecnˇejˇs´ıho pojet´ı strategické hry. Veˇskeré následuj´ıc´ı hry (s nulovým/nenulovým souˇctem, sekvenˇcn´ı, kooperativn´ı, aukce, volby, trhy, evoluce) budou varianty této definice.

6

1.1.1

Rozdˇelen´ı her

M˚uzˇ e být praktické jiˇz v poˇca´ tku provést rozdˇelen´ı hern´ıch situac´ı do kategori´ı. Základn´ım dˇelen´ım je pohled kooperativnosti: • Nekooperativn´ı hry – vyjadˇrujeme strategie hrácˇ u˚ a jejich uˇzitkové funkce. – Hry v normáln´ı formˇe (strategické hry, maticové hry) ∗ ... s nenulovým souˇctem. ∗ ... s nulovým souˇctem. – Hry v rozˇs´ıˇrené formˇe (extensive-form games, dynamické hry, sekvenˇcn´ı hry). • Kooperativn´ı hry dané charakteristickou funkc´ı v – vyjadˇrujeme moˇzné koalice hrácˇ u˚ z mnoˇziny 2Q a ohodnocen´ı jednotlivých koalic daný tak zvanou charakteristickou funkc´ı v : 2Q → R, tedy uˇzitek, který koalice z´ıská t´ım, zˇ e se zformuje z hrácˇ u˚ . V dalˇs´ım dˇelen´ı tˇechto her nacház´ıme: – Hry s pˇrenositelným uˇzitkem (angl. transferable utility, TU-games). – Hry s nepˇrenositelným uˇzitkem (tyto ovˇsem v THE nebudeme studovat). Aby bylo uˇz od poˇca´ tku jasné, co znamená nulovost/nenulovost souˇctu, zavedeme definici hry s konstantn´ım souˇctem a na jej´ım základˇe hru s nulovým souˇctem: Definice 2. Mˇejme strategickou hru Γ = (Q; {Si }i∈Q ; {Ui }i∈Q ). Hru Γ nazveme hrou s konstantn´ım souˇctem, pokud existuje k ∈ R takové, zˇe ∀s ∈ S :

X

Ui (s) = k

i∈Q

Pokud je hra s konstantn´ım souˇctem k = 0, pak se hra nazývá hrou s nulovým souˇctem. Podotknˇeme, zˇ e pokud je hra s konstantn´ım souˇctem k 6= 0, pak je moˇzno ji pˇrevést na strategicky ekvivalentn´ı hru s nulovým souˇctem (v´ıce v kapitole o hrách s nulovým souˇctem). Pokud neexistuje k takové, aby platila výsˇe zm´ınˇená definice, pak se jedná o hru s P nenulovým souˇctem. Jinak ˇreˇceno souˇcet i∈Q Ui (s) je v kaˇzdém profilu s hry obecnˇe jiný1 . 1

Studenti obˇcas mylnˇe uvad´ı, zˇ e hra s nenulovým souˇctem je hra se souˇctem k 6= 0.

7

1.1.2

Jak se hraje nekooperativn´ı strategická hra?

ˇ Casem zavedeme nekooperativn´ı hry v tak zvané rozˇs´ıˇrené formˇe, kde se hrácˇ i stˇr´ıdaj´ı ve svých taz´ıch jako napˇr´ıklad ve hˇre v sˇachy. Uvid´ıme vˇsak, zˇ e takovou hru lze pˇrevést na nejobecnˇejˇs´ı vyjádˇren´ı nekooperativn´ı strategické hry. Nekooperativn´ı strategická hra je také cˇ asto nazývána jako hra v normáln´ı formˇe (angl. normalform game). Dalˇs´ı synonymum je hra v maticové formˇe, protoˇze uˇzitky ve strategických hrách zapisujeme pˇrehlednˇe do N-dimensionáln´ıch matic. Tato hra je modelem situace, kde hrácˇ i provedou pouze jedno rozhodnut´ı a t´ım je volba jejich strategie. Podstatné je, zˇ e o své volbˇe hrácˇ i nevedou zˇ a´ dná vyjednáván´ı a nejsou schopni pozorovat tahy svých protihrácˇ u˚ . Modelujeme to jako souˇcasné proveden´ı akc´ı u vˇsech hrácˇ u˚ . ˇ Pro názornou pˇredstavu zavedme nezávislého soudce (arbitra), kterému hrácˇ i i ∈ Q pˇredaj´ı zprávu ∗ o svém zvolené strategii si ∈ Si v zalepené dopisn´ı obálce, to znamená zp˚usobem, který nedovoluje ostatn´ım pozorovat, co protihrácˇ i zvolili. V okamˇziku, kdy má arbitr obálky od vˇsech hrácˇ u˚ , obálky otevˇre a oznám´ı strategický profil s∗ = (s∗i )i∈Q , který hrácˇ i zvolili (ten je pˇrece sloˇzen ze strategi´ı s∗i vˇsech hrácˇ u˚ i ∈ Q). Podle zvoleného profilu a uˇzitkových funkc´ı hrácˇ u˚ hrácˇ i i obdrˇz´ı zisk Ui (s∗ ). T´ımto je hra ukonˇcena. Vˇsimnˇeme si nyn´ı, zˇ e nen´ı moˇzná zˇ a´ dná oprava zvolených strategi´ı. Pˇredpokládáme, zˇ e hrácˇ i tento fakt chápou a vol´ı svou strategii uvázˇ enˇe2 . Proces u´ vahy o volbˇe strategie m˚uzˇ e být velmi sloˇzitý. Výsledný profil by mˇel být jedn´ım z moˇzných rovnovázˇ ných bod˚u hry (ekvilibrium). Výsledný profil hry budeme nazývat výsledek/výstup hry (angl. outcome). Ekvilibrium je matematický model výsledného chován´ı hrácˇ u˚ , nˇeco na zp˚usob predikce výsledku zkoumané situace. Bylo by dobré jiˇz v poˇca´ tku studie her pˇrijmout poznán´ı, zˇ e teorie her nen´ı obecnˇe schopna predikovat výsledek chován´ı hrácˇ u˚ v kaˇzdé reálné situaci. Pˇrinásˇ´ı ale nástroje analýzy hry a návod k pochopen´ı zkoumané situace. Vazbou mezi teoretickou podobou teorie her a reálným zkoumán´ım opravdového chován´ı hrácˇ u˚ se zabývá experimentáln´ı teorie her. Ta také ukazuje, kde se teorie liˇs´ı od praxe a za jakých okolnost´ı jsou teoretické výsledky shodné s prax´ı. The Ultimatum game Jednou takovou znaˇcnˇe zkoumanou strategickou situac´ı je tak zvaná Ultimatum game. Pˇredpokládejme dva hrácˇ e A a B. Hrácˇ A má za u´ kol navrhout rozdˇelen´ı deseti minc´ı mezi hrácˇ e sebe a hrácˇ e B. Pokud hrácˇ B s rozdˇelen´ım souhlas´ı, obdrˇz´ı oba dle dohody své mince. Pokud hrácˇ B s rozdˇelen´ım nesouhlas´ı, mince propadnou a nikdo nemá nic. Teoreticky by mˇel hrácˇ B souhlasit s jakýmkoliv 2

Tento fakt je zdrojem mnohých zklamán´ı v bˇezˇ ném zˇ ivotˇe. Z experiment˚u s reálnými respondenty mnohdy vyplývá, zˇ e reáln´ı jedinci pˇri volbˇe strategie nejsou schopni pochopit fakt, zˇ e se situace uˇz nebude opakovat. Model je vˇsak zjednoduˇsen´ı, a proto u strategických her striktnˇe pˇredpokládáme natolik d˚ukladnou racionalitu, která fakt jednotahovosti respektuje.

8

rozdˇelen´ım, které mu urˇc´ı nenulový poˇcet minc´ı. Dokonce je ekvilibriem v této hˇre rozdˇelen´ı 9 minc´ı pro A a 1 pro B. Experimenty s reálnými lidmi ukazuj´ı, zˇ e B návrh odm´ıtne, pokud nedostane alespoˇn 40% rozdˇelovaného majetku. Je takovou perliˇckou, zˇ e opice se v´ıce bl´ızˇ´ı teoretickému ekvilibriu, neboˇt opice B vˇzdy pˇrijme 1 minci a nˇekteré druhy opic dokonce v polovinˇe pˇr´ıpad˚u i souhlas´ı s nulovým pod´ılem (logicky, pokud mám dostat nula z rozhodnut´ı protihrácˇ e nebo svým odm´ıtnut´ım, pak jsem indiferentn´ı v˚ucˇ i obˇema alternativám a rozhoduji náhodnˇe s rovnomˇernou pravdˇepodobnostn´ı distribuc´ı nad strategiemi – tady taky dostáváme prvn´ı pˇr´ıklad onˇech zm´ınˇených sm´ısˇených strategi´ı). Obecnˇe plat´ı, zˇ e cˇ´ım je zkoumaný inteligentn´ı tvor jednoduˇssˇ´ı, t´ım v´ıce jeho chován´ı odpov´ıdá matematickým model˚um. To jenom potvrzuje pˇredpoklad, zˇ e hern´ı model je zjednoduˇsen´ı rozhodovac´ı situace.

1.2

Informace ve hˇre

V rozhodovac´ıch situac´ıch je pochopitelnˇe kl´ıcˇ ovým faktem m´ıra znalost´ı hrácˇ u˚ o situaci. Abychom správnˇe modelovali postup hrácˇ e pˇri jeho racionáln´ı u´ vaze, mus´ıme vytvoˇrit i validn´ı model jeho informovanosti o situaci. Co vˇsechno by mˇel hrácˇ vˇedˇet, aby se mohl rozhodnout, respektive, abychom my byli schopni predikovat jeho rozhodnut´ı? Nab´ız´ı se, zˇ e mus´ı vˇedˇet o svých protivn´ıc´ıch, mus´ı znát jejich strategie a mus´ı znát svoje a jejich uˇzitkové funkce. Staˇc´ı to vˇsak na to, aby jeho znalost o hˇre byla jaksi kompletn´ı? Zavede si nyn´ı pomocný pojem spoleˇcná znalost (angl. common knowledge). Formáln´ı definici je moˇzno naj´ıt v cˇ lánku3 , my se zde spokoj´ıme s ponˇekud volnˇejˇs´ım objasnˇen´ım pojmu common knowledge: Definice 3. Mˇejme dva hrácˇ e A a B. Událost E je pro hrácˇ e {A, B} common knowledge, pokud: • ... hrácˇ i {A, B} oba v´ı o události E, • ... hrácˇ A v´ı, zˇe B v´ı o události E, • ... hrácˇ B v´ı, zˇe A v´ı o události E, • ... hrácˇ A v´ı, zˇe B v´ı, zˇe A v´ı o události E, • ... hrácˇ B v´ı, zˇe A v´ı, zˇe B v´ı o události E, • takto aˇz do nekoneˇcného zanoˇren´ı. ˇ Jako pˇr´ıklad common knowledge si uvedme situaci dvou vojev˚udc˚u, kteˇr´ı jsou se svými tábory rozloˇzeni na protilehlých kopc´ıch. Vojev˚udci by se rádi se svými armádami utkali, ale v´ı, zˇ e pokud 3

Aumann, R: Agreeing to Disagree, The Annals of Statistics, Vol. 4, No. 6. (Nov., 1976), pp. 1236-1239.

9

jeden sestoup´ı do u´ dol´ı a druhý z˚ustane na kopci, tak ten sestoupivˇs´ı bude ve strategické nevýhodˇe. Mohou se tedy utkat jedinˇe za pˇredpokladu, zˇ e sestoup´ı oba souˇcasnˇe. Proto se mus´ı informovat o m´ıstˇe a cˇ asu bitvy. Vojev˚udce A tedy vyˇsle k vojev˚udci B posla s oznámen´ım o z´ıtˇrejˇs´ı bitvˇe. Vojev˚udce ovˇsem nev´ı, zda-li posel k protihrácˇ i dorazil. Zat´ım je tedy ve stavu, zˇ e on sám je informován ˇ o události E. Reknˇ eme, zˇ e posel dorazil k druhému vojev˚udci a informoval o E. Nyn´ı oba v´ı o stavu E. Ovˇsem vojev˚udce A instruuje posla, aby se vrátil s potvrzen´ım od vojev˚udce B o tom, zda-li B souhlas´ı s plánem E. Dokud mu to posel nepotvrd´ı, nelze mluvit o dohodˇe. Posel ovˇsem na cestˇe od B k A m˚uzˇ e dezertovat, a tak i B má zájem vˇedˇet, zda-li se A dozvˇedˇel o jeho potvrzen´ı. S kaˇzdým pˇrebˇehnut´ım mezi vojev˚udci nar˚ustá jejich jistota, zˇ e oba událost E akceptovali. Aby vˇsak jistota dosáhla stavu common knowledge, musel by posel bˇehat nekoneˇcnˇe krát. Pojem common knowledge pouˇzijeme pro definici u´ plné informace ve hˇre (angl. complete information). Definice 4. Mˇejme hru Γ = (Q; {Si }i∈Q ; {Ui }i∈Q ). Pokud jsou pro vˇsechny zúcˇ astnˇené hrácˇ e Q následuj´ıc´ı informace common knowledge: • struktura hry Γ (tedy mnoˇziny Q a {Si }i∈Q ), • výplatn´ı (uˇzitkové) funkce Ui ; i ∈ Q, • zp˚usob hran´ı hry a forma hern´ıho ekvilibria, a souˇcasnˇe tento fakt samotný je common knowledge, pak maj´ı hrácˇ i kompletn´ı informaci o hˇre. U her v rozˇs´ırˇené formˇe nav´ıc zavedeme pojem dokonalá (angl. perfect) a nedokonalá (angl. imperfect) informace ve hˇre. Pojmy common knowledge, complete information a perfect information tak bude vyˇcerpáno zkoumán´ı informovanosti hrácˇ u˚ o situaci.

1.3

Analýza hry

Chceme nyn´ı zkoumat pohled jednotlivých hrácˇ u˚ na hru. Elementem zkoumán´ı hry je volba strategie v situaci, kdy protihrácˇ vol´ı konkrétn´ı strategii. Dostáváme se tak na u´ roveˇn prvn´ı kapitoly, t.j. na teorii volby. V situaci, kdy protihrácˇ i vol´ı konkrétn´ı strategie s−i , hrácˇ i vˇzdy vol´ı takovou strategii, která mu v této situaci pˇrinese maximáln´ı zisk. Je to hrácˇ ova nejlepˇs´ı odpovˇedˇ (angl. best-response) na danou situaci. Zavedeme si proto formálnˇe pojem best-response. Definice 5. Uvaˇzujme hru Γ = (Q; {Si }i∈Q ; {Ui }i∈Q ), hrácˇ e i ∈ Q a konkrétn´ı sub-profil s−i ∈ S−i . Nejlepˇs´ı odpovˇedˇ hrácˇ e i v situaci s−i je BRi (s−i ) = arg max[Ui (si , s−i )] si ∈Si

10

Vid´ıme, zˇ e BRi (s−i ) je maximáln´ı mnoˇzina na mnoˇzinˇe strategi´ı Si z pohledu uˇzitk˚u {Ui (si , s−i )}si ∈Si . Je tˇreba znovu zd˚uraznit, zˇ e best-response je mnoˇzina4 . Formálnˇe jsou tedy definiˇcn´ı obor a obor hodnot BRi definovány takto: BRi : S−i → 2Si \ {∅} ˚ zeme Racionáln´ı hrácˇ vˇzdy hraje strategii, která je best-response v situaci s−i . Tento fakt muˇ ´ brát jako základn´ı stavebn´ı kámen následuj´ıc´ıch uvah. Nen´ı proto pˇrekvapuj´ıc´ı, zˇ e od ekvilibria ve hˇre budeme oˇcekávat, zˇ e bude vzájemným best-response vˇsech hrácˇ u˚ , tedy formálnˇe: Definice 6. Uvaˇzujme hru Γ = (Q; {Si }i∈Q ; {Ui }i∈Q ). Profil s∗ ∈ S je tak zvaným rovnovázˇným stavem hry (ekvilibriem ve hˇre), pokud plat´ı ∀i ∈ Q : s∗i ∈ BRi (s∗−i ) Neˇz se vˇsak dostaneme k obvyklejˇs´ı formˇe definice ekvilibria a dalˇs´ım poznatk˚um, které se ho týkaj´ı, m˚uzˇ eme strategickou situaci dále zkoumat bez potˇreby okamˇzitˇe nalézt body rovnováhy.

1.3.1

Dominance mezi strategiemi ve hˇre

Je zcela jisté, zˇ e pokud má hrácˇ strategii, která mu vˇzdy pˇrinese horˇs´ı uˇzitek neˇz jeho ostatn´ı strategie, nebude takovou strategii ve hˇre uvaˇzovat. Taková strategie nemá pro hrácˇ e smysl. Pˇredpokládáme, zˇ e i jeho protihrácˇ i si takové strategie vˇsimnou. Celkovˇe tud´ızˇ ve hˇre nebude uvaˇzována. Budeme nyn´ı zkoumat tak zvané dominantn´ı (angl. dominant) a dominované (angl. dominated) strategie5 . ˇ Definice 7. Uvaˇzujme hru Γ = (Q; {Si }i∈Q ; {Ui }i∈Q ). Rekneme, zˇe strategie s1i ∈ Si striktnˇe dominuje nad strategi´ı s2i ∈ Si , pokud plat´ı: ∀s−i ∈ S−i : Ui (s1i , s−i ) > Ui (s2i , s−i ) Situace, kdy jedna strategie (s1i ) striktnˇe dominuje nad jinou (s2i ) strategi´ı hrácˇ e má pro hru velkou vypov´ıdac´ı hodnotu. Strategie s2i se zde nazývá strategi´ı striktnˇe dominovanou strategi´ı s1i . Racionáln´ı hrácˇ bude vˇzdy preferovat s1i pˇred s2i . Z toho plyne také, zˇ e pokud existuje alespon jedna strategie s1i , která striktnˇe dominuje nad s2i , tak hrácˇ s2i nikdy nebude hrát. Odliˇsujme ale mezi pojmy ”striktnˇe dominantn´ı strategie” a ”strategie striktnˇe dominuj´ıc´ı nad jinou strategi´ı”. 4

Pokud to chce nˇekdo brát opravdu programátorsky, pak je best-response funkce, která má na vstupu sub-profil s−i ∈ S−i a vrac´ı mnoˇzinu strategi´ı, která je podmnoˇzinou Si . 5ˇ Ceský výraz ”dominovaný” moˇzná nen´ı z pohledu spisovné cˇ eˇstiny u´ plnˇe správný. M˚uzˇ e být, zˇ e správným výrazem by bylo ”dominuj´ıc´ı”, tedy strategie x dominuje strategii y. Osobnˇe bych preferoval výraz ”dominovaný”, tzn. strategie x je dominovaná strategi´ı y.

11

Vˇsimnˇeme si, zˇ e striktn´ı dominance je forma preference hrácˇ e nad strategiemi ve hˇre. Ovˇsem pouze forma, neboˇt z principu nen´ı tato relace u´ plná (nelze ˇr´ıct pro kaˇzdé dvˇe r˚uzné strategie s1i , s2i ∈ Si , zˇ e budˇ s1i striktnˇe dominuje nad s2i nebo naopak). Definice 8. Uvaˇzujme hru Γ = (Q; {Si }i∈Q ; {Ui }i∈Q ). Strategie s2i ∈ Si hrácˇ e i je ve hˇre striktnˇe dominovaná, pokud pro vˇsechny strategie s1i ∈ Si \ {s2i } plat´ı, zˇe s1i striktnˇe dominuje nad s2i . Racionáln´ı hrácˇ nikdy nebude striktnˇe dominovanou strategii hrát. Opakem striktnˇe dominované strategie je strategie striktnˇe dominantn´ı (tj. neexistuje jiná strategie hrácˇ e, která by ji striktnˇe dominovala). Pokud hrácˇ má striktnˇe dominantn´ı strategii, bude ji vˇzdy hrát (nav´ıc je z principu jediná) a je zˇrejmé, zˇ e jeho protihrácˇ i budou volit best-response na tuto strategii. Pokud maj´ı vˇsichni hrácˇ i striktnˇe dominantn´ı strategii (kterou tedy pochopitelnˇe hraj´ı), výsledek hry se pak nazývá ekvilibrium striktnˇe dominantn´ıch strategi´ı. Jako pˇr´ıklad takové situace si uvedeme slavné Vˇezˇnovo dilema, které je fenoménem teorie her a bohuˇzel i naˇseho reálného svˇeta. Pro u´ plnost zavedeme jeˇstˇe slabou dominanci mezi strategiemi. Definice 9. Uvaˇzujme hru Γ = (Q; {Si }i∈Q ; {Ui }i∈Q ). Strategie s1i ∈ Si slabˇe (weakly) dominuje nad strategi´ı s2i ∈ Si , pokud plat´ı: ∀s−i ∈ S−i : Ui (s1i , s−i ) ≥ Ui (s2i , s−i ) a souˇcasnˇe ∃s0−i ∈ S−i : Ui (s1i , s0−i ) > Ui (s2i , s−i ) Zopakujme si pojmy spojené s dominanc´ı: • Dominovat – jedna strategie dominuje nad druhou. Je to vztah dvou konkrétn´ıch strategi´ı x a y, kdy napˇr´ıklad x je dominantn´ı nad y a y je dominovaná x. • Být dominantn´ı (bez uveden´ı dvojice strategi´ı) – dominantn´ı strategie dominuje nad vˇsemi ostatn´ımi strategiemi. • Být dominovaný (bez uveden´ı dvojice strategi´ı) – strategie x je dominovaná, pokud vˇsechny ostatn´ı nad n´ı dominuj´ı.

1.4

ˇ Vˇeznovo dilema

Vˇezˇnovo dilema (angl. Prisoner’s dilemma) poprvé pˇredstavili pánové Merrill Flood a Melvin Dresher v roce 1950, tehdy pracuj´ıc´ı pro americkou instituci RAND (tam se také sdruˇzovala vˇetˇsina amerických hern´ıch teoretik˚u). Pˇr´ıbˇeh o vˇezn´ıch pozdˇeji dodal Albert W. Tucker. 12

Vˇezˇnovo dilema je neslavnˇejˇs´ı strategická situace, která kdy byla v teorii her zkoumána. Ukazuje, zˇ e lidé nejsou schopni kooperace, ani pokud jim nekooperace pˇrinese znaˇcné ztráty. Toto dilema je modelem mnoha kaˇzdodenn´ıch lidských situac´ı. Vˇezˇnovo dilema je pro teorii her natolik významný model, zˇ e znalost této strategické situace je nutno povaˇzovat za znalost naprosto základn´ı. R˚uzn´ı autoˇri podávaj´ı tuto hru v r˚uzných hodnotách uˇzitku, veˇskeré instance této hry jsou vˇsak strategicky ekvivalentn´ı s následuj´ıc´ım modelem. Pˇredstavme si, zˇ e policie zatkne dva podezˇrelé – Petera a Johna, a obvin´ı je napˇr´ıklad z ozbrojené loupeˇze. Bohuˇzel vˇsak policie nemá d˚ukazy o jejich zloˇcinu a proto je uvede do následuj´ıc´ı situace. Obˇema spoleˇcnˇe oznám´ı následuj´ıc´ı pravidla a bezprostˇrednˇe poté je um´ıst´ı do oddˇelených cel tak, zˇ e Peter a John spolu nemohou komunikovat. Oznámen´ı je takové: • Pokud se pˇriznásˇ a pˇrizná se i tv˚uj komplic, p˚ujdete oba na deset let do vˇezen´ı. • Pokud se pˇriznásˇ (tzn. budeˇs vypov´ıdat), ale tv˚uj komplic se nepˇrizná, pak ty budeˇs osvobozen (0 let vˇezen´ı) a tv˚uj komplic si odsed´ı za oba dvacet let. • Pokud budete oba mlˇcet, máme na vás pouze nezákonné drˇzen´ı zbranˇe, která se u vás naˇsla a dostanete kaˇzdý jeden rok vˇezen´ı. • Pokud se nepˇriznásˇ a tv˚uj komplic bude vypov´ıdat, viz. výsˇe symetricky. Tato situace je rozhodnˇe pro oba komplice dilema. Lze pˇredpokládat ze znalosti bˇezˇ né praxe, zˇ e zloˇcinci se vzájemnˇe kryj´ı, ovˇsem tady pˇredpokládáme individuáln´ı racionalitu, zˇ a´ dné postrann´ı dohody a t´ım ménˇe jejich vymahatelnost a obavu z výsledku, kdy se komplic pˇrizná a já ne. Souˇcasnˇe pˇredpokládáme u hrácˇ u˚ kompletn´ı informaci o hˇre, tj. hrácˇ i znaj´ı oba podm´ınky hry a souˇcasnˇe tento fakt o sobˇe navzájem v´ı. Peter/John pˇriznat se zatloukat pˇriznat se -10,-10 0,-20 zatloukat -20,0 -1,-1 Figure 1.1: Maticová hra pro Vˇezˇnovo dilema Uˇzitek ve formˇe let ve vˇezen´ı vyjadˇrujeme záporným cˇ´ıslem, aby bylo moˇzno intuitivnˇe porovnávat výstupy a t´ım definovat preferenci. Z analýzy hry plyne, zˇ e pro Petera je strategie ”pˇriznat se” striktnˇe dominantn´ı, neboˇt mu vˇzdy garantuje striktnˇe lepˇs´ı výsledek neˇz strategie ”zatloukat”. Symetricky je to u Johna. Hra ma tud´ızˇ ekvilibrium ve striktnˇe dominantn´ıch strategi´ıch, oba podezˇrel´ı se pˇriznaj´ı a jdou na deset let do vˇezen´ı. Pokud budeme chápat strategii ”pˇriznat se” jako strategii zradit a strategii ”zatloukat” jako strategii spolupracovat (kooperovat), dostáváme se k modelu mnoha lidských zˇ ivotn´ıch situac´ı. 13

Pokud bysme pˇrepokládali moˇznost podezˇrelých si pˇredem dohodnout spoleˇcnou volbu strategie a následnˇe je zase od sebe odlouˇcili, pak jejich chován´ı stejnˇe sklouzne k ekvilibriu ve striktnˇe dominantn´ıch strategii. Prostˇe obava ze zrady bude silnˇejˇs´ı neˇz v´ıra v kooperaci. Aby byla kooperace uvˇeˇritelná, mus´ı existovat d˚uvˇeryhodná hrozba trestu, který bude v pˇr´ıpadˇe zrady znaˇcnˇe pˇrevyˇsovat nejhorˇs´ı moˇzný výsledek ve hˇre (napˇr´ıklad hrozba ve formˇe pomsty kumpán˚u Petera a Johna). V dalˇs´ıch kapitolách znovu povoláme Vˇezˇnovo dilema k dalˇs´ımu zkoumán´ı, napˇr´ıklad v kapitole o opakovaných hrách.

1.5

Rovnovázˇ ný stav ve hˇre (ekvilibrium)

Rovnovázˇ ný bod ve hˇre neboli ekvilibrium je jedn´ım z nejvˇetˇs´ıch problém˚u teorie her. Je totiˇz velmi jednoduˇse definován, ale pˇresto je jeho zjiˇstˇen´ı extremné obt´ızˇ ný algoritmický u´ kol. Ekvilibrium v nekooperativn´ıch strategických hrách zavedl John Nash v roce 1950 ve svém cˇ lánku [1]. Do té doby bylo známo pouze ekvilibrium v tak zvaných nekooperativn´ıch hrách s nulovým souˇctem, které zavedl matematik John von Neumann [2] a publikoval ve slavné knize spoleˇcnˇe s Oskarem Morgensternem – Theory of Games and Economic Behavior. John Nash na jejich práci navázal ve svém postgraduáln´ım studiu, kde zkoumal obecné pojet´ı nekooperativn´ıch her s vazbou na vyjednáván´ı a kooperativn´ı hry. Ekvilibrium ve hrách je od doby Nashova pr˚ulomu v teorii her nazýváno Nashovo ekvilibrium (NE). Nashovo ekvilibrium má specifický význam, neboˇt popisuje racionáln´ı pnut´ı (incentives) ve vˇsech formách her a jeho význam tak pˇresahuje teorii nekooperativn´ıch her. Pˇr´ınos Johna Nashe je tak pro teorii her nepopiratelný. M˚uzˇ eme sice naj´ıt v jeˇstˇe dávnˇejˇs´ı historii pˇr´ıklady hernˇe-teoretických u´ vah (Cournotovo ˇreˇsen´ı oligopolu), m˚uzˇ eme za otce (a matku) teorie her povaˇzovat von Neumanna nebo Morgensterna, reálnˇe vˇsak teorie her zaˇcala existovat právˇe myˇslenkou Johna Nashe. Pˇredvedeme si nyn´ı formáln´ı definici Nashova ekvilibria: Definice 10. Uvaˇzujme hru Γ = (Q; {Si }i∈Q ; {Ui }i∈Q ). Strategický profil s∗ ∈ S je ryz´ım Nashovým ekvilibriem (PNE) ve hˇre, pokud plat´ı pro vˇsechny hrácˇ e i ∈ Q: ∀si ∈ Si : Ui (s∗i , s∗−i ) ≥ Ui (si , s∗−i ) ˇ ıká, zˇ e pokud hrácˇ i hraj´ı profil s∗ , tak zˇ a´ dný hrácˇ nem˚uzˇ e Tato definice je pro teorii her kl´ıcˇ ová. R´ zvýsˇit sv˚uj uˇzitek pˇrechodem do jiné strategie si ∈ Si , si 6= s∗i , to znamená, zˇ e uˇzitek Ui (si , s∗−i ) m˚uzˇ e být pˇrinejlepˇs´ım stejnˇe dobrý jako Ui (s∗ ). D˚uleˇzité je vˇsak pochopit, zˇ e výsledek hrácˇ u˚ v ekvilibriu nen´ı jejich maximáln´ım ziskem, ale pouze optimáln´ım nebo také stabiln´ım. Vlastnost rovnováhy vede hrácˇ e mnohdy k neefektivn´ım výsledk˚um hry (jak je zˇrejmé napˇr´ıklad u Vˇezˇnova dilematu). Definice 10 zavád´ı Nashovo ekvilibrium v ryz´ıch strategi´ıch. Budeme se ekvilibrii dále podrobnˇeji zabývat, v tomto okamˇziku se vˇsak sluˇs´ı uvést nˇekolik zásadn´ıch fakt˚u o ekvilibri´ıch (zat´ım bez nárok˚u na podrobnˇejˇs´ı pochopen´ı): 14

• Hra m˚uzˇ e m´ıt v´ıce Nashových ekvilibri´ı v ryz´ıch strategi´ıch. M˚uzˇ eme pak zkoumat, které z nich hrácˇ i zvol´ı. • Existuj´ı hry, které nemaj´ı zˇ a´ dné Nashovo ekvilibrium v ryz´ıch strategi´ıch. • Kaˇzdá koneˇcná hra má alespoˇn jedno ekvilibrium ve sm´ısˇených strategi´ıch (probereme v dalˇs´ıch kapitolách).

1.5.1

Intiutivn´ı algoritmus nalezen´ı PNE

V malých hrách m˚uzˇ eme snadno zjistit ryz´ı Nashova ekvilibria z definice 10 tak, zˇ e si pro kaˇzdý profil poloˇz´ıme otázku, zda-li pro vˇsechny hrácˇ e splˇnuje definovanou podm´ınku. Dále m˚uzˇ eme pro kaˇzdého hrácˇ e i ∈ Q a kaˇzdý moˇzný sub-profil s−i ∈ S−i vyhodnoti hrácˇ ovu nejlepˇs´ı odpovˇedˇ BRi (s−i ) a poznaˇcit si profily, kde BRi (s−i ) nastala. Pak z definice 6 vyhodnot´ıme pr˚unik takových profil˚u, tedy: BRpnei =

[

{(si , s−i )|si ∈ BRi (s−i )}

s−i ∈S−i

P NE =

\

BRpnei

i∈Q

U vˇetˇs´ıch her jiˇz vycház´ı tyto algoritmy jako neefektivn´ı, specificky pokud hledáme ekvilibria ve sm´ısˇených strategi´ı (bude vysvˇetleno dále). Býva proto vhodné redukovat hru na jej´ı strategický ekvivalent s menˇs´ım poˇctem strategi´ı hrácˇ u˚ . Vhodná m˚uzˇ e být následuj´ıc´ı technika známá jako iterativn´ı eliminace dominovaných strategi´ı. Co znamená ekvilibrium pro reálný zˇ ivot? V pˇredmˇetu THE zavedeme nˇekolik tak zvaných zjemnˇen´ı nebo take zpˇresnˇen´ı ekvilibria (angl. refinements) a také jedno zobecnˇen´ı ve formˇe korelovaného ekvilibria. Veˇskeré zpˇresˇnuj´ıc´ı refinements ovˇsem budou stále plnit podm´ınku Nashe a v pˇr´ıpadˇe zobecnˇen´ı bude platit, zˇ e vˇsechna Nashova ekvilibria budou zároveˇn i korelovaná ekvilibria. Co pˇresto znamená ekvilibrium v chápán´ı reálných situac´ı a lze v˚ubec vˇeˇrit, zˇ e reáln´ı hrácˇ i pochop´ı, kde leˇz´ı ve hˇre rovnovázˇ ný stav? Pˇrednˇe, ekvilibrium je algoritmický popis nalezen´ı rovnováhy, která hrácˇ u˚ m ukazuje optimáln´ı výsledek hry. Je to zat´ım jediný algoritmicky popsaný postup a pokud budeme nˇekdy implementovat simulaˇcn´ı modely s prvky hry, impelemtaci ekvilibria se nevyhneme. Experimentáln´ı teorie her ukazuje, zˇ e vˇetˇsinou hrácˇ i ve zkoumaných situac´ıch jaksi do rovnovázˇ ného stavu dokonverguj´ı. Stane se to budˇ opakovanými hrami, kde hrácˇ i maj´ı zpˇetnou vazbu a intuitivnˇe

15

se do ekvilibria cˇ asem dostanou nebo u´ vahu s opakován´ım situace jsou schopni provést ve svých hlavách.

1.6

Iterativn´ı eliminace dominovaných strategi´ı

S nedávno zavedeným pojmem dominantn´ı a dominované strategie souvis´ı následuj´ıc´ı technika redukce hry na strategicky ekvivalentn´ı hru bez dominovaných strategi´ı, která m˚uzˇ e vést aˇz k nalezen´ı ekvilibria. Potˇrebujeme zavést nejdˇr´ıve pojem strategické ekvivalence her a redukce hry na jej´ı strategický ekvivalent.

1.6.1

Strategická ekvivalence her

Na strategickou ekvivalenci dvou her je moˇzno pohl´ızˇ et z mnoha u´ hl˚u a zavádˇet rozliˇcné definice. Strategickou ekvivalenci dvou her Γ a Γ0 m˚uzˇ eme intuitivnˇe chápat jako stav, kdy v obou hrách hrácˇ i vykazuj´ı stejné chován´ı. Vidˇeno pˇres PNE, hry mohou být nazvány strategicky ekvivalentn´ımi, pokud maj´ı stejná PNE. Nejdˇr´ıve pochop´ıme následuj´ıc´ı fakt: Definice 11. Hra Γ = (Q, {Si }i∈Q , {Ui }i∈Q ) je ekvivalentn´ı s hrou Γ0 = (Q, {Si }i∈Q , {Ui0 }i∈Q ), pokud existuj´ı pro kaˇzdého hrácˇ e i ∈ Q reálná cˇ´ısla Ai , Bi , kde Ai > 0 a plat´ı ∀s ∈ S: Ui0 (s) = Ai Ui (s) + Bi Definice ˇr´ıká, zˇ e pokud jsou uˇzitkové funkce Ui0 lineárn´ımi kombinacemi funkc´ı Ui , pak jsou hry ekvivalentn´ı. Pokud tedy ke vˇsem zisk˚um jednoho hrácˇ e pˇriˇcteme konkrétn´ı jedno cˇ´ıslo, strategický charakter jeho chován´ı se nezmˇen´ı. Pokud odebereme ze hry nˇejakou strategii, vytváˇr´ıme tak podhru hry (pozor, v sekvenˇcn´ıch hrách bude podhra, angl. sub-game, oznaˇcuje jiný problém).

1.6.2

Algoritmus eliminace

Algoritmus iterativn´ı eliminace dominovaných strategi´ı pracuje v kroc´ıch, kdy v kaˇzdém kroku ze hry eliminuje striktnˇe dominované strategie hrácˇ u˚ . Po eliminaci docház´ıme k redukované hˇre, kde ovˇsem strategie, které byly ponechány, nyn´ı se novˇe mohou stát striktnˇe dominovanými. Iterativn´ı proces konˇc´ı se hrou, která uˇz neobsahuje u zˇ a´ dného hrácˇ e striktnˇe dominovanou strategii. Poznamenejme, zˇ e tento algoritmus je moˇzno uplatnit i s pouˇzit´ım slabé dominance. Mohou tak ovˇsem ze hry vypadnout strategie, které by tvoˇrily Nashova ekvilibria.

16

1.7

Efektivita profilu a Pareto dominance

V teorii volby jsme zkoumali preference nad akcemi hrácˇ e, ve hrách jsme zavedli preference z hlediska dominance strategi´ı a nyn´ı probereme preference nad strategickými profily. Efektivita profilu je forma statistiky vypov´ıdaj´ıc´ı o celkovém dosaˇzeném uˇzitku pˇri hran´ı profilu. Zjednoduˇsenˇe efektivitu profilu definujme jako E(s) =

X

Ui (s)

i∈Q

Je pochopitelné, zˇ e pokud hrácˇ i posuzuj´ı dva profily s, s0 ∈ S a E(s) > E(s0 ), tak je velká sˇance, zˇ e daj´ı pˇrednost profilu s (napˇr´ıklad pokud jsou s, s0 PNE ve hˇre). Tento pohled ovˇsem negarantuje celkovou spokojenost vˇsech hrácˇ u˚ s efektivnˇejˇs´ım profilem. Vilfredo Pareto (1848–1923), italský slavny ekonom, zavedl pojem Pareto dominance, který si nyn´ı definujme: Definice 12. Uvaˇzujme hru Γ = (Q; {Si }i∈Q ; {Ui }i∈Q ). Profil s ∈ S pareto dominuje nad profilem s0 ∈ S, pokud plat´ı, zˇe ∀i ∈ Q : Ui (s) ≥ Ui (s0 ) a souˇcasnˇe ∃i ∈ Q : Ui (s) > Ui (s0 ) Vˇsimnˇeme si, zˇ e definice pareto dominance je totoˇzná s definic´ı slabé dominance nad strategiemi jednoho hrácˇ e. Pokud tedy vˇsichni hrácˇ i v dominantn´ım profilu z´ıskávaj´ı alespoˇn stejnˇe hodnˇe jako v dominovaném, tak nejsp´ısˇ ti striktnˇe lepˇs´ı hrácˇ i budou dominantn´ı profil preferovat a ostatn´ı hrácˇ i budou spolupracovat (napˇr´ıklad proto, zˇ e oˇcekávaj´ı striktnˇe lepˇs´ı hrácˇ e hrát dominantn´ı profil a pˇrizp˚usob´ı svou best-response). Na pojem dominance (tzn. jisté formy preference) navazuje pojem koneˇcné efektivity, tedy forma maximáln´ı mnoˇziny a tedy i optima: Definice 13. Uvaˇzujme hru Γ = (Q; {Si }i∈Q ; {Ui }i∈Q ). Profil s ∈ S je pareto efektivn´ı, pokud neexistuje jiný profil s0 ∈ S takový, zˇe by s0 pareto dominoval nad s. Pochopitelnˇe nezkoumáme pareto dominanci nad vˇsemi profily, ale obvykle nad profily, které tvoˇr´ı PNE. Na závˇer této kapitoly poznamenejme, zˇ e v reálných situac´ıch mohou vznikat r˚uzné dohody mezi hrácˇ i, které zp˚usob´ı, zˇ e hrácˇ i souhlas´ı s pro nˇe horˇs´ım profilem, pokud se dohodnou na jiném pˇrerozdˇelen´ı zisku (vede to na kooperativn´ı hry s pˇrenositelným uˇzitkem, viz dále). 17

Chapter 2 ˚ model oligopolu Cournotuv Matematické ˇreˇsen´ı oligopoln´ıch trh˚u byl historicky prvn´ı pokus odvodit matematicky chován´ı hrácˇ u˚ ve strategické situaci. M´ırnˇe zde zabrous´ıme do mikroekonomických teori´ı, ale na u´ rovni, která nevyˇzaduje hlubˇs´ı znalosti ekonomie1 . Pro zaˇca´ tek prostudujeme situaci na trhu s jedn´ım konkrétn´ım druhem výrobku (komoditou), kde pˇredpokládáme, zˇ e výrobek m˚uzˇ e pocházet od r˚uzných výrobc˚u, ale pro zákazn´ıka jsou vˇsechny kvalitativnˇe shodné a rozliˇsuj´ı produkci r˚uzných výrobc˚u pouze cenou výrobku (homogenn´ı produkt). M˚uzˇ eme mluvit napˇr´ıklad o standardizovaném rohl´ıku – ten vˇsichni znaj´ı a zkoumaj´ı pouze jeho cenu. Pˇredpokládejme, zˇ e cena výrobku vznikne p˚usoben´ım trˇzn´ıch sil na trhu vlivem zákon˚u nab´ıdky a poptávky, které pop´ısˇeme rovnic´ı: p=M −q kde p znaˇc´ı maximáln´ı dosaˇzitelnou cenu, q je mnoˇzstv´ı dodané na trh a M je specifická konstantna daná trhem. Bude nás zaj´ımat cena výrobku na trhu a mnoˇzstv´ı, které jsou za tˇechto okolnost´ı výrobci ochotni dodat na trh. Budeme zkoumat situaci danou jedn´ım výrobcem s monopoln´ım postaven´ım, situac´ı se dvˇema výrobci (duopol) a situac´ı s v´ıce výrobci (oligopol). Oligopol sám je definován jako situace na trhu s komoditou, kterou dodává dva a v´ıce hrácˇ u˚ , kdy kaˇzdý je svou trˇzn´ı/výrobn´ı silou schopen ovlivnit cenu komodity na trhu. Duopol je tedy specifický pˇr´ıpad oligopolu, ale my budeme odliˇsovat situaci dvou hrácˇ u˚ a situaci obecnˇe v´ıce (tˇri a v´ıce) hrácˇ u˚ 2 . Monopolista na trhu bude maximalizovat sv˚uj zisk, tedy hledat extrém funkce: u(q) = p · q − c · q = M q − q 2 − cq kde c bude v následuj´ıc´ım textu vˇzdy vyjadˇrovat výrobn´ı náklady spojené s produkc´ı jednotky ˇ Kapitola vycház´ı z pˇrednásˇek Magdalény Hykˇsové z FD CVUT Obecnˇe v teorii her jsou dramaticky odliˇsné modely dvou hrácˇ u˚ a modely s v´ıce hrácˇ i, zejména z pohledu jejich sloˇzitosti. V´ıcehrácˇ ovou hrou se vˇzdy rozum´ı hra tˇr´ı a v´ıce hrácˇ u˚ . 1

2

18

komodity (cena výroby jednoho rohl´ıku). Funkce vyjadˇruje rozd´ıl trˇzeb a výrobn´ıch náklad˚u, coˇz je pro nás nyn´ı zisk výrobce z prodeje. Hledáme extrém uˇzitkové funkce (bod, ve kterém je prvn´ı derivace nulová): 1 (M − c) 2 ∗ Maximáln´ıho zisku dosáhne monopolista pˇri výrobˇe qmon mnoˇzstv´ı komodity, cena bude ∗ u0 (q) = M − 2q − c = 0 ⇒ qmon =

1 1 1 1 ∗ p∗mon = M − qmon = M − (M − c) = M + c = (M + c) 2 2 2 2 Zisk je koneˇcnˇe dán vztahem u∗mon

=

∗ u(qmon )

=

∗ qmon (p∗mon

1 − c) = (M − c) 2

2

Pokud pˇridáme dalˇs´ıho výrobce (hrácˇ e), oˇcekáváme pak, zˇ e se cena výrobku sn´ızˇ´ı a mnoˇzstv´ı dodané na trh se zvýsˇ´ı. V oligopoln´ı situaci, kdy se poˇcet hrácˇ u˚ limitnˇe bl´ızˇ´ı k nekoneˇcnu, uvid´ıme, zˇ e hrácˇ i produkuj´ı s nulovým ziskem. Následuj´ıc´ı model sestavil Augustine Cournot a je znám jako Cournot˚uv model duopolu/oligopolu. Pro hern´ı teoretiky je zaj´ımavé zjiˇstˇen´ı, zˇ e Cournot odvodil Nashovo ekvilibrium jako pr˚useˇc´ık tak zvaných reakˇcn´ıch kˇrivek hrácˇ u˚ – coˇz jsou pro nás best-response kˇrivky. Z pohledu her je Cournot˚uv model oligopolu strategická nekooperativn´ı hra s nekoneˇcnˇe mnoha strategiemi, resp. se strategiemi tvoˇrenými spojitými (omezenými nebo neomezenými) intervaly – tady pˇredpokládáme, zˇ e mnoˇziny strategi´ı hrácˇ u˚ jsou Si = (0, ∞).

2.1

Cournotovo rˇ eˇsen´ı duopolu

Mˇejme tedy dva hrácˇ i-výrobce, coˇz znamená, zˇ e hledáme q1 , q2 pˇri výrobn´ıch nákladech c. Maximáln´ı dosaˇzitelná cena komodity na trhu je podobnˇe dána rovnic´ı dávaj´ıc´ı do vztahu cenu a dodané mnoˇzstv´ı: p = M − q1 − q 2 Hrácˇ i nejsp´ısˇ vol´ı mnoˇzstv´ı (svou mnoˇzstevn´ı strategii) z intervalu h0, M i, to znamená, zˇ e jejich mnoˇzstevn´ı strategie jsou nekoneˇcné ohraniˇcené mnoˇziny: S1 = S2 = h0, M i Výplatn´ı funkce jiˇz nyn´ı závis´ı na hraném profilu (máme tady hru): u1 (q1 , q2 ) = (p − c)q1 = (M − q1 − q2 − c)q1 19

u2 (q1 , q2 ) = (p − c)q2 = (M − q1 − q2 − c)q2 Zkoumejme pohled prvn´ıho duopolisty. Pohled druhého duopolisty je totiˇz obdobný. Pro kaˇzdou strategii soupeˇre q2 hledá takové mnoˇzstv´ı q1 = R1 (q2 ), aby hodnota u1 (q1 , q2 ) byla maximáln´ı (je to jeho best-response). Funkci R1 (q2 ) ˇr´ıkáme reakˇcn´ı kˇrivka. Matematicky vzato (lépe ˇreˇceno, z matematické analýzy) hledáme extrém funkce v´ıce promˇenných podle promˇenné q1 , coˇz vede na parciáln´ı derivaci (ostatn´ı mnoˇzstevn´ı promˇenné zde vystupuj´ı jako konstanty): ∂u1 = M − c − q2 − 2q1 = 0 ∂q1 Hrácˇ bude hrát takovou strategii q1 , aby byla best-response na protihrácˇ ovu q2 , to znamená hledá bod extrému, který nastává v bodˇe q1 takovém, zˇ e M − c − q2 − 2q1 = 0 Strategie q2 je pro rozhodován´ı prvn´ıho hrácˇ e sub-profilem (tzn. s−i ), tedy konstantou a hrácˇ jedna hledá svou best-response mezi svými S1 . Proto klademe rovnost: 1 q1 = R1 (q2 ) = (M − c − q2 ) 2

(2.1)

Analogicky druhý hrácˇ vol´ı: 1 q2 = R2 (q1 ) = (M − c − q1 ) 2 ∗ ∗ Kde je rovnovázˇ ný bod (q1 , q2 )? Cournot jej navrhl jako pr˚useˇc´ık reakˇcn´ıch kˇrivek, tedy v hernˇe teoretickém pojet´ı jako vzájemnou best-response hrácˇ u˚ . Hledáme (q1∗ , q2∗ ) tak, zˇ e R1 (q2∗ ) = R2 (q1∗ ): q2∗ =

1 (M − c − R1 (q1∗ )) 2

coˇz je q2∗

1 = 2

1 ∗ M − c − (M − c − q2 ) 2

a po zjednoduˇsen´ı dostáváme vztah pro q2∗ : 1 q2∗ = (M − c) 3 Po dosazen´ı (2.2) do (2.1) z´ıskáme: 1 q1∗ = (M − c) 3 20

(2.2)

Figure 2.1: Cournotovo ˇreˇsen´ı oligopolu – grafické vyjádˇren´ı pr˚useˇc´ık˚u reakˇcn´ıch kˇrivek [pouˇzito z pˇrednásˇek M. Hykˇsové] Cena dosaˇzená na trhu vycház´ı z p˚uvodn´ı rovnice mezi cenou a mnoˇzstv´ım na trhu: 2 1 2 p∗D = M − q = M − q1∗ − q2∗ = M − (M − c) = M + c 3 3 3 Zisk pro kaˇzdého je u1 (q1∗ , q2∗ )

=

u2 (q1∗ , q2∗ )

2 1 = (M − c) 3

A celkový zisk hrác˚u v situaci je menˇs´ı neˇz zisk monopolisty: 2 [(M − c)]2 9 Vyrobeno a dodáno na trh je celkovˇe, coˇz je v´ıce neˇz u monopolisty: u1 (q1∗ , q2∗ ) + u2 (q1∗ , q2∗ ) =

2 q1∗ + q2∗ = (M − c) 3 Celkovˇe je vidˇet, zˇ e duopoln´ı situace je pro zákazn´ıky lepˇs´ı neˇz monopoln´ı, neboˇt duopolisté prodávaj´ı vˇetˇs´ı mnoˇzstv´ı výrobk˚u za niˇzsˇ´ı cenu neˇz monopolista. Lze tedy i oˇcekávat, zˇ e s kaˇzdým dalˇs´ım výrobcem se situace na trhu z pohledu zákazn´ıka zlepˇs´ı.

´ ˚ ymi výrobn´ımi náklady c1 6= c2 hrácˇ u˚ Uvaha s ruzn´ Pokud oˇcekáváme, zˇ e výrobn´ı náklady hrácˇ u˚ jsou rozd´ılné, pak docház´ıme k následuj´ıc´ımu ekvilibriu:

21

1 q1∗ = (M + c2 − 2c1 ) 3 1 q2∗ = (M + c1 − 2c2 ) 3 Uplatn´ı se tedy v´ıce hrácˇ s niˇzsˇ´ımi náklady, coˇz nen´ı nijak pˇrekvapivé.

´ Uvaha o tajné dohodˇe duopolistu˚ ∗ jako monopolista? Mohou se duopolisti dohodnout a vyrábˇet pouze qmon Dostáváme se tak mimo rovnovázˇ ný bod. V takovém bodˇe je situace nestabiln´ı, protoˇze kaˇzdý z hrácˇ u˚ m˚uzˇ e vyboˇcit z profilu a krátkodobˇe si zisk navýsˇit. Pokud pˇripouˇst´ıme kooperativnost (napˇr. formou vyjednáván´ı), pak studujeme rozsáhlejˇs´ı oblast ˇreˇsen´ı. V´ıce v pˇrednásˇce o kooperativn´ıch hrách.

2.2

ˇ sen´ı oligopolu˚ Reˇ

Uvaˇzujme n hrácˇ u˚ , kde kaˇzdý hledá svoji strategii qi . Zisky jsou opˇet dány pro hrácˇ e i ∈ Q symetricky: ui (q1 , q2 , ..., qn ) = (p − c)qi = (M − c − q1 − q2 − ... − qn )qi Rovnovázˇ ný bod z´ıskáme m´ırnˇe komplikovanˇejˇs´ım odvozován´ım neˇz u duopolu, ale postup je v principu shodný: ∂ui = M − c − q1 − q2 − ... − 2qi − ... − qn = 0 ∂qi Z obecného pˇredpisu obdrˇz´ıme soustavu rovnic a tu ˇreˇs´ıme analyticky: 2q1 + q2 + ... + qn = M − c q1 + 2q2 + ... + qn = M − c .. q1 + q2 + ... + 2qn = M − c ˇ sen´ım soustavy obdrˇz´ıme Reˇ q1∗ = q2∗ = ... = qn∗ = Oligopolisté dohromady vyrob´ı:

22

M −c n+1

∗

q =

n X

qi∗ = n

i=1

M −c n = (M − c) n+1 n+1

Z toho je patrné, zˇ e s rostouc´ım poˇctem hrácˇ u˚ roste i mnoˇzstv´ı dodaného produktu a klesá jeho cena (a zisk firem). p∗ =

n 1 M+ c n+1 n+1

u∗ =

n (M − c)2 2 (n + 1)

Kdyˇz jde n k nekoneˇcnu, dostáváme se do situace, která se nazývá dokonalá soutˇezˇ (konkurence), kdy na trhu soupeˇr´ı velké mnoˇzstv´ı srovnatelných firem, kde zˇ a´ dná z nich nemá moc významnˇe ovlivnit mnoˇzstv´ı na trhu. Velmi zaj´ımavé je zjiˇstˇen´ı, zˇ e dodané mnoˇzstv´ı na trh je v situaci dokonalé konkurence: n (M − c) = M − c n→∞ n + 1 coˇz souvis´ı i s cenou poˇzadovanou za výrobek (nem˚uzˇ eme oˇcekávat, zˇ e by klesla pod náklady výroby): lim

p∗ = M − (M − c) = c Celkový zisk oligopolist˚u v dokonalé konkurenci: u∗ = 0 ˇ Pro srovnán´ı situac´ı monopolu, duopolu, oligopolu a oligopolu v dokonalé konkurenci uvedme pˇrehledovou tabulku na Obrázku 2.2.

Monopol Duopol Oligopol Dok. soutˇezˇ

Celkové mnoˇzstv´ı q ∗ 1 (M − c) 2 2 (M − c) 3 n (M − c) n+1 (M − c)

Cena za jednotku p∗ 1 M + 21 c 2 1 M + 32 c 3 1 n M + n+1 c n+1 c

Celkový zisk u∗ 1 (M − c)2 4 2 (M − c)2 9 n (M − c)2 (n+1)2 0

Figure 2.2: Srovnán´ı r˚uzných trˇzn´ıch situac´ı

23

2.3

˚ model oligopolu (1883) Bertranduv

Je zjevné, zˇ e oligopol nevede v realitˇe ani náznakem k dokonalé konkurenci, která se vyznaˇcuje cenou na u´ rovni výrobn´ıch náklad˚u a nulovým provozn´ım ziskem. M˚uzˇ eme to zkoumat na komoditách kaˇzdodenn´ı spotˇreby, kde lze jednoduˇse mˇenit dodavatele a produkt je v´ıceménˇe srovnatelný. Nejv´ıc typické je to u telefonn´ıch nebo bankovn´ıch sluˇzeb. Bertrand˚uv model oligopolu nen´ı z pohledu teorie her tak pˇrelomový, jako byl ten Cournot˚uv. Bertrand revidoval závˇer Cournota s tvrzen´ım, zˇ e jiˇz u duopolist˚u se m˚uzˇ e rozbˇehnout dokonalá konkurence, neboˇt jejich mnoˇzstevn´ı ekvilibrium nemus´ı být stabiln´ı. Pˇripusˇtme, zˇ e duopolisté hraj´ı (q1∗ , q2∗ ) = 31 (M − c) za shodnou cenu p∗ = 13 M + 23 c. Pˇri této cenˇe tvoˇr´ı nenulový zisk z výroby a prodeje. Pˇri stejné cenˇe maj´ı rovný mnoˇzstevn´ı pod´ıl na prodeji. Najednou jeden z hrácˇ u˚ zmˇen´ı svou cenu p∗i := p∗ − ∆, kde ∆ je libovolnˇe malé. Podle logiky trhu by mˇel hrácˇ i vyprodat veˇskerou svou produkci a po nˇem aˇz draˇzsˇ´ı hrácˇ . Plyne z toho, zˇ e hrácˇ i nesoutˇezˇ´ı mnoˇzstv´ım, ale cenou, která m˚uzˇ e j´ıt aˇz na u´ roveˇn náklad˚u, tedy implikuj´ıc´ı nulový zisk. Z faktu, zˇ e to tak v realitˇe nen´ı, plyne tzv. Bertrand˚uv paradox Dneˇsn´ı ekonomie jiˇz zná pojem cenová válka, který je z pohledu strategické interakce triviáln´ı. Pˇredstavme si napˇr´ıklad tˇri hrácˇ e Q = {A, B, C} na trhu s homogenn´ım produktem, jehoˇz cena se ustálila na pi = p0 a pod´ıl výrobc˚u qi na trhu je rovnomˇernˇe rozloˇzen na tˇretiny, tzn. qi = 31 (M − p0 ). Pokud se výrobce j ∈ Q rozhodne uhnout z cenového ekvilibria, pak by podle logiky trhu mˇel na sebe pˇretáhnout veˇskerou poptávku trhu aˇz do výsˇe svých výrobn´ıch kapacit a m˚uzˇ e tak zvýsˇit sv˚uj zisk. Ostatn´ı výrobci jsou nuceni sn´ızˇ it svou cenu tak, aby se vyrovnali aktuáln´ı cenˇe hrácˇ e j, pˇr´ıpadnˇe j´ıt jeˇstˇe n´ızˇ e. Rozloˇzen´ı poptávky mezi výrobce se tak zˇrejmˇe opˇet srovná a výsledkem je stejné rozloˇzen´ı výroby s t´ım významným rozd´ılem, zˇ e uˇz s menˇs´ımi trˇzbami. Proto nelze nikdy oˇcekávat, zˇe si budou hrácˇ i konkurovat cenou. Budou zákazn´ık˚um stále dokazovat, zˇ e jejich produkt je lepˇs´ı neˇz konkurenˇcn´ı (bonusy, vˇernostn´ı programy, ...), ale nikdy nesn´ızˇ´ı cenu. K cenové válce m˚uzˇ e doj´ıt pouze pˇri vstoupen´ı nového hrácˇ e na trh, ovˇsem na dobu velmi krátkou. Nav´ıc by nemˇelo nikoho pˇrekvapit, kdyˇz je novˇe pˇr´ıchoz´ı pouze virtuáln´ı identitou jiˇz zavedeného hrácˇ e, která pouze zvyˇsuje dojem konkurence na trhu.

2.4

Závˇer kapitoly o Cournotovˇe modelu oligopolu

Studium Cournotova modelu je pro nás d˚uleˇzité ze tˇr´ı hlavn´ıch d˚uvod˚u: 1. Cournot˚uv model oligopolu je historicky prvn´ı ukázka ˇreˇsen´ı strategické rovnováhy v nekooperativn´ıch hrách. Znalost Cournotova modelu je pro teorii her chápána jako znalost základn´ı. 2. Corunot˚uv model je ukázka analytického hernˇe-teoretického modelu. Dalˇs´ı modely (napˇr. ekonomické) jsou koncipovány podobným zp˚usobem. 24

3. Cournot˚uv model je hrán v nekoneˇcných mnoˇzinách strategi´ı (resp. nekoneˇcných ohraniˇcených mnoˇzinách) a je to pro nás myˇslenkový pˇrechod od ryz´ıch strategi´ı smˇerem ke sm´ısˇeným strategi´ım. Na Cournot˚uv model navázˇ eme v kapitole o hrách v rozˇs´ıˇrené formˇe modelem podle Stackelberga, který odliˇsuje mezi výrobci cenového v˚udce a jeho následovn´ıky.

25

Chapter 3 Hry bez Nashova ekvilibria v ryz´ıch strategi´ıch Zavedli jsme koncept Nashova ekvilibria v ryz´ıch strategi´ıch (PNE) a nyn´ı je potˇreba zkoumat, zda-li kaˇzdá (avˇsak koneˇcná) hra má PNE nebo ne. Tento problém rozhodneme nalezen´ım alespoˇn jedné hry, která PNE nemá. Jako ukázkový model poslouˇz´ı klasická hra Matching Pennies na Obrázku 3.1 (u nás známe jej´ı m´ırnˇe sloˇzitˇejˇs´ı variantu Kámen-n˚uzˇ ky-pap´ır). A/B heads tails heads 1,-1 -1,1 tails -1,1 1,-1 Figure 3.1: Matice zisk˚u ve hˇre Matching Pennies Z matice zisk˚u je evidentn´ı, zˇ e hra nemá PNE. Znamená to vˇsak, zˇ e nemá ˇreˇsen´ı? Pokud by nemˇela ˇreˇsen´ı, pak by ji hrácˇ i nedokázali hrát a to je nesmysl. Ukázˇ eme, zˇ e racionáln´ı strategi´ı hrácˇ e je hrát v této hˇre strategii ”heads” s pravdˇepodobnost´ı 50 % a podobnˇe strategii ”tails”. Pokud zde budeme mluvit o pravdˇepodobnostech, tak t´ım nem´ın´ıme zˇ a´ dnou nejistotu hrácˇ e pˇri rozhodován´ı, jako je tomu u rozhodován´ı za nejistoty (ve hrách proti pˇr´ırodˇe), nebo-li u rozhodován´ı nad loteriemi. Pravdˇepodobnosti budou modelovat indiferenci hrácˇ e nad nˇekterými jeho strategiemi. Vyjedeme z potˇreby hrácˇ e se rozhodnout v situaci dané následuj´ıc´ı uˇzitkovou funkc´ı: volba

a

b

zisk

10 20

c

d

30 40

Je zde zjevné, zˇ e hrácˇ dosahuje svého maxima pˇri volbˇe strategie d. Jakou strategii ovˇsem hrácˇ zvol´ı v následuj´ıc´ı, m´ırnˇe modifikované situaci: volba

a

b

zisk

10 20 26

c

d

40 40

Vid´ıme, zˇ e hrácˇ dostane shodný výsledek pˇri volbˇe strategie c i d. Hrácˇ je tedy indiferentn´ı mezi c a d. Je mu tedy jedno, zda-li zvol´ı c nebo d. Racionáln´ı hrácˇ tento fakt pochop´ı1 a najde si zaˇr´ızen´ı, které mu vygeneruje náhodnou veliˇcinu v potˇrebné pravdˇepodobnostn´ı distribuc´ı. V naˇsem pˇr´ıpadˇe si jedinec po staru ”hod´ı korunou”. Pˇri zobecnˇen´ı distribuce náhodné veliˇciny je modelem jeho rozhodovac´ı situace pravdˇepodobnostn´ı distribuce (0, 0, 0.5, 0.5). Nyn´ı si poloˇzme tuto otázku: je distribuce (0, 0, 0.4, 0.6) projevem indiference mezi c a d? Jak tuto situaci interpretujeme? Jak by mohla vzniknout? Pokud t´ım jedinec dává najevo, zˇ e je v zásadˇe indiferentn´ı mezi strategiemi s nenulovou pˇriˇrazenou pravdˇepodobnost´ı, ale tak nˇejak se mu d l´ıb´ı o kousek v´ıc, pak t´ımto zp˚usobem rozhodován´ı nemodelujeme. Pochopme, zˇ e postoj d c d je logicky nekonzistentn´ı. Ve hrách ovˇsem bude postoj (0, 0, 0.4, 0.6) pˇr´ıpustný, neboˇt bude vyjadˇrovat naˇse oˇcekáván´ı zisku. Oˇcekávaný zisk bude závislý na podobnˇe pravdˇepodobnostn´ım postoji protihrácˇ u˚ . Násˇ hrácˇ bude indiferentn´ı nad strategiemi, kterým pˇriˇrazuje nenulovou pravdˇepodobnost, protoˇze oˇcekávané zisky pˇri jejich hran´ı budou totoˇzné.

3.1

Sm´ısˇené rozˇs´ırˇ en´ı nekooperativn´ı hry

Navázˇ eme na definici nekooperativn´ı hry hrané v diskrétn´ıch mnoˇzinách strategi´ı (koneˇcná hra). Zavedeme tak zvané sm´ısˇené rozˇs´ıˇren´ı hry. Definice 14. Mˇejme hru Γ = (Q; {Si }i∈Q ; {Ui }i∈Q ). Hru Γm = (Q; {∆i }i∈Q ; {πi }i∈Q ) nazveme sm´ısˇeným rozˇs´ırˇen´ım hry Γ, pokud ∀i ∈ Q: ˇ ıslo σi (si ) • ∆i je mnoˇzina sm´ısˇených strategi´ı hrácˇ e i (vektory délky |Si |) s prvky σi ∈ ∆i . C´ Q oznaˇcuje pravdˇepodobnost pˇriˇrazenou ryz´ı strategii si ∈ Si ve strategii σi . Celkovˇe ∆ = i ∆i . )

( ∆i =

σi ∈ h0, 1imi |

X

σi (si ) = 1 ; mi = |Si |

si ∈Si

• Výplatn´ı funkce hrácˇ e i (tzv. oˇcekávaný uˇzitek hrácˇ e) je v kaˇzdém sm´ısˇeném profilu σ ∈ ∆: ! πi (σ) =

X

Ui (s) ·

s∈S

Y

σi (si )

i∈Q

ˇ sen´ım sm´ısˇeného rozˇs´ıˇren´ı hry je sm´ısˇené ekvilibrium. Dohodnˇeme se, zˇ e nebudeme striktnˇe Reˇ psát ryz´ı ekvilibrium v koneˇcné hˇre a sm´ısˇené ekvilibrium ve sm´ısˇeném rozˇs´ıˇren´ı koneˇcné hry – 1

Tento moment m˚uzˇ e být pro jedince velmi obt´ızˇ ný. Vzpomeˇnme na bajku o oslovi, který chc´ıpl hlady, neboˇt se nedokázal rozhodnout mezi levou a pravou otýpkou sena.

27

budeme rozumˇet existenci sm´ısˇeného rozˇs´ırˇen´ı jaksi implicitnˇe a dále budeme mluvit o hrách s ˇreˇsen´ım v ryz´ıch strategi´ıch nebo ve sm´ısˇených strategi´ıch. Nashovo ekvilibrium ve sm´ısˇených strategi´ıch bude m´ıt fakticky stejnou definici jako pro PNE, ovˇsem se zaveden´ım oˇcekávaného zisku (pouze zobecnˇen´ı). Definice 15. Mˇejme hru Γm = (Q; {∆i }i∈Q ; {πi }i∈Q ). Sm´ısˇený profil σ ∗ ∈ ∆ nazveme sm´ısˇené Nashovo ekvilibrium ve hˇre Γm , pokud plat´ı pro vˇsechny hrácˇ e i ∈ Q a vˇsechny moˇzné sm´ısˇené strategie σi ∈ ∆i : ∗ ) πi (σ ∗ ) ≥ πi (σi , σ−i

Dále nebudeme zd˚urazˇnovat, zˇ e sm´ısˇené ekvilibrium je definováno v Γm , ale implicitnˇe ho budeme chápat jako moˇzné ˇreˇsen´ı Γ. Dopln´ıme si jeˇstˇe pojem sm´ısˇená doména mnoˇziny strategi´ı hrácˇ e (snad vhodný pˇreklad anglického pojmu support). S t´ım si zavedeme i notaci σi (si ) vyjadˇruj´ıc´ı pravdˇepodobnost, kterou pˇriˇrazuje sm´ısˇená strategie σi hrácˇ e i jeho ryz´ı strategii si ∈ Si . Definice 16. Mˇejme hru Γm = (Q; {∆i }i∈Q ; {πi }i∈Q ) a sm´ısˇenou strategii σi hrácˇ e i. Sm´ısˇenou doménou mnoˇziny strategi´ı hrácˇ e i (zkrácenˇe doménou strategi´ı) nazveme podmnoˇzinu strategi´ı suppi (σi ) = {si ∈ Si |σi (si ) > 0}

3.2

Smysl a interpretace sm´ısˇených strategi´ı

Uvaˇzujme následuj´ıc´ı hru: a

b

c

3,2

1,3

d

-1,4 2,1

Neˇz si ukázˇ eme postup výpoˇctu sm´ısˇeného Nashova ekvilibria (MNE), ukázˇ eme si, jaká pozorován´ı maj´ı v bodˇe MNE oba hrácˇ i. Mˇejme následuj´ıc´ı sm´ısˇený profil: ∗

σ =

(σ1∗ , σ2∗ )

=

3 1 , 4 4

1 4 , , 5 5

∗ Jaké jsou ryz´ı BR1 (σ−1 )? Jestliˇze sloupcový hrácˇ hraje ryz´ı strategii a s pravdˇepodobnost´ı strategii b s pravdˇepodobnost´ı 45 , pak ˇra´ dkový hrácˇ muˇze oˇcekávat zisk pˇri hran´ı c následuj´ıc´ı:

π1 (c, σ2∗ ) = 3 ·

1 4 7 +1· = 5 5 5

Pokud by hrál ryze d, pak: 28

1 5

a

1 4 7 +2· = 5 5 5 Toto je prvn´ı d˚uleˇzitá vlastnost sm´ısˇeného Nashova ekvilibria: π1 (d, σ2∗ ) = −1 ·

Pokud hrácˇ i hraj´ı sm´ısˇené Nashovo ekvilibrium σ ∗ , pak je kaˇzdý hrácˇ i indiferentn´ı ve svém oˇcekáván´ı mezi vˇsemi svými ryz´ımi strategiemi, kterým jeho sm´ısˇená strategie σi∗ pˇriˇrazuje nenulovou pravdˇepodobnost. Toto pochopitelnˇe v MNE plat´ı vzájemnˇe. Co pˇresnˇe ovˇsem znaˇc´ı ta pravdˇepodobnostn´ı distribuce? Pokud trváme na tom, aby se ˇra´ dkový hrácˇ v naˇs´ı hˇre rozhodl a zvolil nˇejaký konkrétn´ı ryz´ı tah, pak se hrácˇ hraj´ıc´ı σ1∗ s pravdˇepodobnost´ı 43 rozhodne pro c a s pravdˇepodobnost´ı 41 rozhodne pro d. ˇ Pojdme ovˇsem dále. Nˇekdo m˚uzˇ e nam´ıtnout, zˇ e pro sloupcového hrácˇ e je pravdˇepodobnˇejˇs´ı hrát b, a proto bude hrát b vˇzdy. Pokud by sloupcový hrál sm´ısˇenˇe (0, 1), tedy strategii b s pravdˇepodbnost´ı 1, pak je jeho oˇcekávaný zisk: 43 3 + 14 1 = 2.5 (je horˇs´ı neˇz π2 (σ ∗ )). Pokud by ˇra´ dkový hrácˇ z´ıskal dojem, zˇ e sloupcový bude hrát (0, 1), pak je jeho BR hrát (0, 1), coˇz m˚uzˇ eme snadno na matici hry ovˇeˇrit. Na to ovˇsem zareaguje sloupcový pˇresunut´ım se do levého sloupce, kde je strategie a. Pokud tedy hrácˇ i nepˇristupuj´ı k rovnováze sm´ısˇenˇe, hra hraná v ryz´ıch strategi´ıch nenajde rovnovázˇ ný bod. Stability to dosáhne aˇz v σ ∗ , kdy jsou oba hrácˇ i indiferentn´ı mezi {a, b}, resp. {c, d} a je pravdˇepodobné, zˇ e sloupcový zvol´ı b a ˇra´ dkový c, kde dosáhnou uˇzitku (1, 3) (m´ısto (1.4, 2.7)). Poznamenejme na závˇer, zˇ e toto je pouze demonstraˇcn´ı pˇr´ıklad. Neplat´ı tedy obecnˇe, zˇ e hrácˇ i ve sm´ısˇeném ekvilibriu pˇriˇrazuj´ı vˇsem svým ryz´ım strategi´ım nenulovou pravdˇepodobnost.

3.3

˚ c´ıku reakˇcn´ıch Výpoˇcet sm´ısˇené rovnováhy – hledán´ı pruseˇ kˇrivek

Mˇejme následuj´ıc´ı hru: a

b

c

3,2

1,3

d

-1,4 2,1

P´ısmenem p budeme znaˇcit pravdˇepodobnost hran´ı strategie a rˇa´ dkového hrácˇ e, tzn. zˇ e 1 − p urˇcuje pravdˇepodobnost hran´ı b. Podobnˇe s p´ısmenem q pro sloupcového hrácˇ e. 1 Funkce πi je funkce v promˇenných p a q. Hledán´ım jej´ıho extrému podle p, tzn. ∂π z´ıskáváme ∂p náhled na nejlepˇs´ı odpovˇedˇ ˇra´ dkového hrácˇ e v sub-profilu (q, 1 − q) hran´ı protihrácˇ e.

29

π1 = 3pq + 1p(1 − q) − 1(1 − p)q + 2(1 − p)(1 − q) = 5pq − p − 3q + 2 Funkce π1 udává oˇcekávaný zisk ˇra´ dkového hrácˇ e v závislosti na hran´ı jeho a protivn´ıkovy sm´ısˇené strategie. Poloˇz´ıme prvn´ı derivaci funkce rovnou nule a z´ıskáváme bod, ve kterém funkce dosahuje extrému (zˇrejmˇe maxima, coˇz m˚uzˇ eme ovˇeˇrit na druhé derivaci): 1 ∂π1 = 5q − 1 ⇒ q = ∂p 5 Funkce π1 dosahuje extrému v bodech (p, q) takových, zˇ e q = 15 . Podobnˇe u funkce π2 : π2 = 2pq + 3p(1 − q) + 4(1 − p)q + (1 − p)(1 − q) = −4pq + 2p + 3q + 1 ∂π2 3 = −4p + 3 ⇒ p = ∂q 4 Sm´ısˇené Nashovo ekvilibrium tedy nastává ve sm´ısˇeném profilu ∗

σ = ((p, 1 − p), (q, 1 − q)) =

3.4

(σ1∗ , σ2∗ )

=

3 1 , 4 4

1 4 , , 5 5

Výpoˇcet sm´ısˇené rovnováhy – obecný algoritmus

Mˇejme stejnou hru jako v posledn´ım pˇr´ıkladu. Vycház´ıme z poznán´ı indiference mezi a a b pˇri hran´ı sm´ısˇené (p, 1 − p) versus sm´ısˇené (q, 1 − q). Budeme tedy pˇredpokládat u hrácˇ u˚ domény (supports) supp1 = {c, d} a supp2 = {a, b}. Z pˇredpokladu indiference ˇra´ dkového hrácˇ e mezi vˇsemi jeho ryz´ımi strategiemi z domény pak pro ˇra´ dkového hrácˇ e vycház´ı uˇzitek: U1 (c, a) · q + U1 (c, b) · (1 − q) = U1 (d, a) · q + U1 (d, b) · (1 − q) 3q + 1(1 − q) = −1q + 2(1 − q) 3q = −q + (1 − q) q=

1 5

Podobnˇe sloupcový: 2p + 4(1 − p) = 3p + (1 − p) ⇒ p = 43 Tento postup je základem algoritmu hledán´ı sm´ısˇených ekvilibri´ı silou. V tomto algoritmu zkoumáme vˇsechny moˇzné domény jednoho hrácˇ e proti vˇsem moˇzným doménám druhého hrácˇ e. Pro kaˇzdou iteraci z´ıskáváme soustavu rovnic, které jsou v pˇr´ıpadˇe dvouhrácˇ ových her lineárn´ı a v pˇr´ıpadˇe v´ıce-hrácˇ ových her nelineárn´ı. Tento algoritmus i urˇcuje cˇ asovou sloˇzitost výpoˇctu sm´ısˇeného Nashova

30

ekvilibria, která je obecnˇe exponenciáln´ı2 . Výsˇe zm´ınˇený algoritmus3 pracuje správnˇe pouze u nedegenerovaných her, které si v zápˇet´ı definujeme: Definice 17. Dvouhrácˇ ová hra je tak zvanˇe nedegenerovaná, pokud zˇa´ dná sm´ısˇená strategie s doménou (support) velikosti k nemá u protihrácˇ e v´ıce neˇz k ryz´ıch best-response. Tuto vlastnost snadno poznáme – pokud má hra na ryz´ı strategii jednoho hrácˇ e dvˇe (a v´ıce) ryz´ıch best-response protihrácˇ e, je degenerovaná. Plyne z toho, zˇ e kterékoliv Nash ekvilibrium (s∗1 , s∗2 ) nedegenerované dvouhrácˇ ové hry má domény stejné délky.

3.5

Vˇeta o existenci sm´ısˇeného Nashova ekvilibria

Vˇeta 1 (Vˇeta o existenci MNE v koneˇcných hrách). Kaˇzdá koneˇcná hra má vˇzdy alespoˇn jedno rˇeˇsen´ı ve sm´ısˇených strategi´ıch. John Nash (1950) Tato vˇeta je nejvýznamnˇejˇs´ım výsledkem Johna Nashe a základem studia nekooperativn´ıch hern´ıch situac´ı. D˚ukaz této vˇety bude proveden v následuj´ıc´ıch kapitolách. Vˇeta 2. Kaˇzdá koneˇcná nedegenerovaná hra má vˇzdy lichý poˇcet ekvilibri´ı (tzn. PNE+MNE). D˚usledek: pokud najdu ve hˇre pouze 1 PNE, je pouze 1 ekvilibrium. Pokud najdu 2 PNE, pak existuje tˇret´ı ekvilibrium, které je MNE (a bude nad tˇemi PNE ukazovat jejich váhu).

2

Christos Papadimitriou dokázal, zˇ e je ve sloˇzitostn´ı tˇr´ıdˇe PPAD Pro dalˇs´ı studium doporuˇcuji: Nisan et al.: Algorithmic Game Theory (link na stránce THE), specificky kapitolu: Bernhard von Stengel: Equilibrium Computation for Two-Player Games in Strategic and Extensive Form 3

31

Chapter 4 Problém existence ekvilibria ve hrách s nenulovým souˇctem Kdyˇz Nash definoval své ekvilibrium v nekooperativn´ıch hrách s nenulovým souˇctem, bylo nutno nav´ıc ukázat, zda-li jeho koncept plat´ı ve vˇsech myslitelných hrách.

4.1

Kompaktn´ı a konvexn´ı mnoˇzina

Definice 18. Mnoˇzina A ⊆ Rn je kompaktn´ı, pokud je ohraniˇcená (existuje cˇ´ıslo b takové, zˇe ∀a ∈ A : ||a|| < b) a uzavˇrená (jej´ı doplnˇek Rn \ A je otevˇrená mnoˇzina). Definice 19. Mnoˇzina A ⊆ Rn je konvexn´ı, pokud pro kaˇzdé dva jej´ı prvky x, y ∈ A a kaˇzdé reálné cˇ´ıslo λ ∈ h0, 1i plat´ı: λx + (1 − λ)y ∈ A Tzn., kaˇzdý bod na u´ seˇcce mezi body x a y patˇr´ı do mnoˇziny A, coˇz je domonstrováno na obrázku 4.1.

4.2

Ryze kvazi-konkávn´ı funkce

Definice 20. Funkce f (x) : A → R1 (kde A je konvexn´ı mnoˇzina) je ryze kvazi-konkávn´ı, jestliˇze f (λx + (1 − λ)y) > t pro vˇsechna x, y ∈ A, x 6= y, λ ∈ (0, 1) a jakékoliv t ∈ R1 takové, zˇe f (x) ≥ t a f (y) ≥ t. Definice ˇr´ıká, zˇ e funkce (napˇr. uˇzitková funkce, resp. preferenˇcn´ı) nem˚uzˇ e na intervalu (x, y) takovém, zˇ e pro oba ohraniˇcuj´ıc´ı body je f (·) slabˇe lepˇs´ı neˇz hodnota t, tvrdit, zˇ e pˇripouˇst´ı bod z ∈ (x, y), který by nebyl striktnˇe lepˇs´ı neˇz t nebo dokonce horˇs´ı. Naopak, vˇsechny body z ∈ (x, y) mus´ı být striktnˇe lepˇs´ı (striktnˇe preferovány nad) neˇz t. 32

Figure 4.1: Ukázka konvexn´ı a nekonvexn´ı mnoˇziny

4.3

Existence Nashova ekvilibria ve hrách se spojitými Si

Vˇeta 3. Nashovo ekvilibrium hry v normáln´ı formˇe Γ = (Q; {Si }i∈Q ; {Ui }i∈Q ) existuje, pokud jsou splnˇeny následuj´ıc´ı podm´ınky: 1. Si , ∀i ∈ Q je konvexn´ı a kompaktn´ı podmnoˇzina Euklidovského prostoru. 2. Ui (si , s−i ) : S → R1 jsou spojité funkce u vˇsech hrácˇ u˚ i ∈ Q. 3. pro vˇsechny hrácˇ e i ∈ Q a vˇsechny s−i ∈ S−i je funkce Ui (si , s−i ) ryze kvazi-konkávn´ı na mnoˇzinˇe Si . D˚ukaz této vˇety pˇr´ıliˇs nepotˇrebujeme. Vˇeta v podstatˇe stanovuje podm´ınky, které jsou demonstrovány v Cournotovˇe modulu duopolu, tzn. mnoˇziny strategi´ı jsou spojité mnoˇziny (konvexn´ı a kompaktn´ı), uˇzitkové funkce jsou spojité a kvazi-konkávn´ı.

4.4

Sm´ısˇená best-response hrácˇ e ve sm´ısˇeném profilu

Pˇripomeˇnme definici sm´ısˇeného Nashova ekvilibria (MNE): Definice 21. Sm´ısˇený profil σ ∗ ∈ ∆ je ekvilibrium ve hˇre Γm , pokud plat´ı pro vˇsechny i ∈ Q: ∗ ) σi∗ ∈ BRi (σ−i

BRi (σ−i ) = arg max πi (σi , σ−i ) σi ∈∆i

Pˇredpokládáme, zˇ e výsledkem operace BRi (σ−i ) je podmnoˇzina ∆i . Mnoˇzina ∆i má jiný charakter neˇz Si ! V diskrétn´ıch (ryz´ıch) strategi´ıch je výsledek best-response diskrétn´ı mnoˇzina, ve sm´ısˇených

33

strategi´ıch je to nˇejaká podmoˇzina mnoˇziny ∆i a my následnˇe ukázˇ eme, zˇ e je kompaktn´ı a konvexn´ı. Z best-response plyne, zˇ e hrácˇ i je v kontextu sub-profilu σ−i indiferentn´ı mezi vˇsemi σi ∈ BRi (σ−i ). To nás pˇrivád´ı k otázce: Jak je velká mnoˇzina BRi (σ−i )? Mˇejme hru: a

b

c

3,2

1,3

d

-1,4 2,1

Prohlás´ıme, zˇ e jej´ı sm´ısˇené ekvilibrium je: MNE =

(σ1∗ , σ2∗ )

=

3 1 , 4 4

1 4 , , 5 5

Funkce π1 udává oˇcekávaný uˇzitek ˇra´ dkového hrácˇ e v závislosti na hraném sm´ısˇeném profilu daném pravdˇepodobnostmi p a q. π1 = 5pq − p − 3q + 2 Funkce best-response je tedy hledán´ı maxima pˇres vˇsechny sm´ısˇené profily ˇra´ dkového hrácˇ e ∆1 = {(p, 1 − p)|p ∈ h0, 1i} tedy zkrácenˇe pˇres vˇsechna p ∈ h0, 1i: BR1 (σ−1 = (q, 1 − q)) = max [π1 (p, q)] p∈h0,1i

Experimentálnˇe tedy m˚uzˇ eme doj´ıt k tˇemto závˇer˚um: 1 9 , 10 ) = maxp∈h0,1i [−0.5p + 1.7] ⇒ p := 0 BR1 ( 10 9 1 BR1 ( 10 , 10 ) = maxp∈h0,1i [3.5p − 0.7] ⇒ p := 1 BR1 ( 51 , 45 ) = maxp∈h0,1i [5p · 0.2 − p − 3 · 0.2 + 2] = 1.4 Zde jiˇz BR nen´ı závislé na p, tzn. BR1 (q = 0.2) = ∆1 . Avˇsak pouze pro jeden bod v ∆1 je to podobnˇe u sloupcového. Kdybychom funkce BR1 a BR2 vynesli do grafu, pak je bod rovnováhy v m´ıstˇe, kde se obˇe kˇrivky (reakˇcn´ı kˇrivky) protnou.

4.5

Pevný bod korespondence

V pˇredchoz´ı kapitole bylo vidˇet, zˇ e funkce best-response nen´ı funkc´ı v pravém slova smyslu – na jeden vstup m˚uzˇ e vrátit obecnˇe v´ıce výstup˚u (coˇz je tedy obecná vlastnost best-response). Striktnˇe matematicky vzato proto nem˚uzˇ eme mluvit o funkci best-response, ale o tak zvané korespondenci best-response. Co znamená pojem korespondence? 34

Definice 22. Korespondence c : A →→ B je zobecnˇená totáln´ı funkce nebo multi-value funkce, která kaˇzdému a ∈ A pˇriˇrazuje (neprázdnou) podmnoˇzinu B. Alternativnˇe m˚uzˇ eme korespondenci zapisovat jako funkci c : A → 2B , s vlastnost´ı ∀a ∈ A : c(a) 6= ∅. Pˇri zkoumán´ı best-response korespondence nás bude zaj´ımat, jestli rekurzivn´ı proces hledán´ı ekvilibria se m˚uzˇ e obecnˇe vzato nˇekdy zastavit. Programátorsky si to pˇredstavme jako volán´ı funkce BR na nˇejaký náhodnˇe zvolený profil. Ekvilibrium je pak dáno posloupnost´ı volán´ı σ ∗ = BR(BR(BR(BR(...)))) a nás zaj´ımá, zda-li je tato posloupnost koneˇcná a zda-li m˚uzˇ e doj´ıt do stavu, kdy ∀i ∈ Q : σi∗ = ∗ BRi (σ−i ). Proto je nyn´ı d˚uleˇzitý pojem pevného bodu. Definice 23. Mˇejme korespondenci c : A →→ A. Pevný bod (fixed-point) korespondence c je takový bod x∗ ∈ A, zˇe x∗ ∈ c(x∗ ) ∗ ) pro vˇsechny i ∈ Q. Je to Nashovo ekvilibrium je strategický profil σ ∗ takový, zˇ e σi∗ ∈ BRi (σ−i tedy pevný bod BR-korespondence:

BR(σ) = (BR1 (σ−1 ), BR2 (σ−2 ), . . . , BRN (σ−N )) Pokud dokázˇ eme, zˇ e kterákoliv BR-korespondence m˚uzˇ e m´ıt pevný bod, pak existuje MNE pro kteroukoliv hru. Existuje vˇeta (Kakutani’s fixed-point theorem), která stanovuje podm´ınky, aby korespondence mˇela pevný bod. Pokud ukázˇ eme, zˇ e BR splˇnuje tyto podm´ınky, pak má pevný bod, tzn. hra má ekvilibrium. Ukázˇ eme si Kakutaniho theorém a Nash˚uv d˚ukaz.

4.6

Kakutani’s fixed point theorem

Shizuo Kakutani (1911–2004) stanovil ve své vˇetˇe o pevném bodu korespondence následuj´ıc´ı podm´ınky, aby zadaná korespondence mˇela pevný bod. Tento teorém nás bude zaj´ımat, protoˇze s jeho pomoc´ı dokázˇ eme, zˇ e sm´ısˇená best-response korespondence má z principu vˇzdy pevný bod a tud´ızˇ sm´ısˇené Nashovo ekvilibrium existuje obecnˇe pro kaˇzdou hru. Vˇeta 4. Korespondence r : A →→ A má pevný bod, pokud plat´ı: 1. A je kompaktn´ı, konvexn´ı, neprázdná podmnoˇzina (koneˇcnˇe-rozmˇerného) Euklidovského prostoru, 2. r(a) je neprázdná pro vˇsechny a ∈ A, 35

3. r(a) je konvexn´ı pro vˇsechny a ∈ A, 4. r(·) je shora hemispojitá (ekv. s podm´ınkou, zˇe má uzavˇrený graf).

4.7

˚ Dukaz Nashovy vˇety o existenci MNE v koneˇcných hrách

V d˚ukazu budeme vyˇsetˇrovat funkci

BRi (σ−i ) = arg max π(σi , σ−i ) σi ∈∆i

a následnˇe BR(σ) = (BR1 (σ−1 ), BR2 (σ−2 ), ..., BRN (σ−N )) Jejich zkoumán´ım dojdeme k závˇeru, zda-li naplˇnuj´ı nezbytné podm´ınky Kakutaniho, aby mohly formovat sm´ısˇené Nashovo ekvilibrium.

Berge’s Theorem of the Maximum Vˇeta 5. Nechtˇ X ⊂ Rd , M ⊂ Rz jsou kompaktn´ı a konvexn´ı mnoˇziny. Nechtˇ je funkce f (x, m) : X × M → R1 spojitá na X a M . Korespondence c : M →→ X definovaná jako c(m) = arg max[f (x, m)] x∈X

je neprázdná pro kaˇzdé m ∈ M a shora hemispojitá. Na funkci f (x, m) m˚uzˇ eme pohl´ızˇ et jako na hodnot´ıc´ı funkci optimalizátoru, kde m je vstupn´ı specifikace problému a ˇreˇsen´ı se hledá pˇres vˇsechny x ∈ X. Vˇsimnˇete si podobnosti s BR-korespondenc´ı.

V koneˇcných hrách jsou Si koneˇcné (diskrétn´ı) mnoˇziny. Jejich sm´ısˇené rozˇs´ırˇen´ı ∆i jsou ovˇsem kompaktn´ı a konvexn´ı mnoˇziny (a rozhodnˇe neprázdné). Tzn., prvn´ı podm´ınka Kakutaniho byla splnˇena. Z definice hry plyne, zˇ e πi (·) jsou lineárn´ı funkce a proto spojité na ∆i . Z Bergova theorému o maximu proto plyne, zˇ e BRi (σ−i ) je proto neprázdná pro vˇsechny σ−i ∈ ∆−i a shora hemispojitá. Druhá a cˇ tvrtá Kakutaniho podm´ınka splnˇena.

36

Definice lineárn´ı funkce (zobrazen´ı) Definice 24. Nechtˇ X ⊆ Rm a Y ⊆ Rn . Zobrazen´ı F : X → Y se nazývá lineárn´ı, pokud pro vˇsechny x, y ∈ Rm a q ∈ R plat´ı souˇcasnˇe: 1. F (x + y) = F (x) + F (y) 2. F (q · x) = q · F (x)

Protoˇze πi (σi , σ−i ) je lineárn´ı pro libovolné σ−i , pak najdeme-li dva body σi0 , σi00 takové, zˇ e πi (σi0 , σ−i ) = πi (σi00 , σ−i )

(4.1)

tzn. σi0 , σi00 ∈ BRi (σ−i ), pak (z linearity): πi (λσi0 + (1 − λ)σi00 , σ−i ) = = λπi (σi0 , σ−i ) + (1 − λ)πi (σi00 , σ−i ) = = λπi (σi0 , σ−i ) + πi (σi00 , σ−i ) − λπi (σi00 , σ−i )

(4.2)

Protoˇze pˇredpokládáme (4.1), pak m˚uzˇ eme v (4.2) pro snadˇejˇs´ı cˇ ten´ı provést substituci A = πi (σi0 , σ−i ) = πi (σi00 , σ−i ) a cˇ´ıst (4.2) jako λA + A − λA = A To znamená, zˇ e πi (λσi0 + (1 − λ)σi00 , σ−i ) = πi (σi0 , σ−i ) pro libovolné λ ∈ h0, 1i. Jinak rˇeˇceno, oˇcekávaný zisk ve vˇsech bodech BRi (σ−i je stejný a funkce BR vrac´ı mnoˇzinu, která je rozhodnˇe konvexn´ı. Tˇret´ı podm´ınka Kakutaniho byla splnˇená.

Podm´ınky Kakutaniho vˇety byly splnˇeny, t´ım pádem je BR(σ) korespondence s pevným bodem, tzn.

37

má-li σ ∗ být rovnovázˇ ný bod ve sm´ısˇených strategi´ıch, pak rozhodnˇe plat´ı, zˇ e σ ∗ ∈ BR(σ ∗ ) Tak J. Nash v roce 1950 (zasláno k recenzi Nov 1949) v cˇ lánku Equilibrium Points in N-person Games dokázal univerzáln´ı ˇreˇsitelnost koneˇcných nekooperativn´ıch her. Tento cˇ lánek je rozhodnˇe pozoruhodný a zaslouˇz´ı si, aby se s n´ım kaˇzdý student Teorie her seznámil.

38

Chapter 5 Nekooperativn´ı hry s nulovým souˇctem Nekooperativn´ı hry s nulovým souˇctem1 jsou speciáln´ım pˇr´ıpadem strategických nekooperativn´ıch her s nenulovým souˇctem. Jejich ˇreˇsen´ı pˇriˇslo historicky dˇr´ıve (von Neumann, Vˇeta o minimaxu), protoˇze jsou koncepˇcnˇe i výpoˇcetnˇe jednoduˇssˇ´ı. Dˇr´ıve se i vˇeˇrilo, zˇ e veˇskeré strategické konflikty jsou charakteru nulového souˇctu, coˇz pozdˇeji John Nash vyvrátil svým ˇreˇsen´ım ve hrách s nenulovým souˇctem. Zopakujme si definici hry s konstantn´ım, respektive nulovým souˇctem: ˇ Definice 25. Mˇejme hru Γ. Rekneme, zˇe Γ je hra s konstantn´ım souˇctem k ∈ R, pokud plat´ı ∀s ∈ S :

X

Ui (s) = k

i∈Q

Pokud je k = 0, pak je Γ hra s nulovým souˇctem. Hry s nulovým souˇctem bývaj´ı pro sv˚uj strategický charakter nazývány strictly competitive games. M´ıra výhry jednoho znaˇc´ı m´ıru prohry druhého. V sociáln´ıch vˇedách jsou tyto hry známy také pod názvem antagonistické hry (konflikty). Definice 26. Antagonistický konflikt je rozhodovac´ı situace N hrácˇ u˚ , kteˇr´ı se po volbˇe svých rozhodnut´ı rozdˇel´ı o pevnˇe stanovenou cˇ a´ stku, jej´ızˇ výsˇe nezávis´ı na tom, jaká rozhodnut´ı zvolili. Pˇr´ıklad Dvˇe firmy (Perrier, Apollinaris) soupeˇr´ı na trhu s mineráln´ı vodou. Jejich marketingové oddˇelen´ı ˇreˇs´ı problém, jestli zvolit vysokou cenu ($2) nebo n´ızkou cenu ($1) za jednu lahev minerálky. Obˇe firmy v´ı, zˇ e pˇri cenˇe $2 se prodá 5000 lahv´ı (trˇzba $10.000) a pˇri cenˇe $1 se prodá 10000 lahv´ı (trˇzba $10.000). Pˇri stejné cenˇe obou se hrácˇ i rovnomˇernˇe podˇel´ı o trh. Pokud je jeden levnˇejˇs´ı, z´ıská celý trh. Fixn´ı náklady firem, tzn. bez ohledu na realizovanou produkci/prodej jsou $5000 za dané obdob´ı. Hru dokumentuje matice uˇzitk˚u zapsaná dle obvyklé konvence na obrázku 5.1. 1

ˇ Kapitola byla zpracována s pouˇzit´ım pˇrednásˇek Magdaleny Hykˇsové z FD CVUT

39

Perrier/Appollinaris $1 $1 0,0 $2 -5000,5000

$2 5000,-5000 0,0

Figure 5.1: Hra mezi Perrierem a Appollinarisem Je vidˇet i pˇri zápisu dvou uˇzitk˚u dvou hrácˇ u˚ , zˇ e suma uˇzitk˚u v kaˇzdém profilu je nulová a zˇ e tud´ızˇ pracujeme se hrou s nulovým souˇctem.

5.1

Vztah nulového a konstantn´ıho souˇctu

Abychom od poˇca´ tku pracovali s vˇedom´ım, zˇ e hry s konstantn´ım souˇctem jsou vˇsechny v podstatˇe hrami s nulovým souˇctem, vyslov´ıme následuj´ıc´ı vˇetu: Vˇeta 6. Nechtˇ Γk je hra s konstantn´ım souˇctem k ∈ R. Potom existuje hra Γ0 s nulovým souˇctem taková, zˇe je strategicky ekvivalentn´ı s Γk . D˚ukaz bude zaloˇzen na nalezen´ı Ai , Bi koeficient˚u pro strategickou ekvivalenci a pˇredvedeme si to pouze na pˇr´ıkladˇe. Pˇr´ıklad: pˇrevod k-sum hry na 0-sum hru Mˇejme hru s konstantn´ım souˇctem (k = 2): a

b

c

0,2

1,1

d

-1,3 2,0

Hledáme koeficienty transformace A1 , A2 , B1 , B2 na strategicky ekvivalentn´ı hru s nulovým souˇctem. Tyto koeficienty jsou pro nás tud´ızˇ neznámé v následuj´ıc´ıch rovnic´ıch: 0 0 U11 = 0A1 + B1 U21 = 2A2 + B2 0 0 U12 = A1 + B1 U22 = A2 + B2 0 0 U13 = −A1 + B1 U23 = 3A2 + B2 0 0 U14 = 2A1 + B1 U24 = 0A2 + B2 Uˇzitky Uij0 ; i ∈ {1, 2}, j ∈ {1, 2, 3, 4} jsou taky neznámé. Máme zat´ım 12 neznámých a pouze 8 rovnic. Dále pˇridáme rovnice vyˇzaduj´ıc´ı nulovost souˇctu uˇzitk˚u v jednotlivých profilech: 0 0 =0 ∀j ∈ {1, 2, 3, 4} : U1j + U2j 0 0 Pokud tedy sledujeme rovnosti U1j + U2j = 0, pak obdrˇz´ıme soustavu lineárn´ıch rovnic o cˇ tyˇrech neznámých:

40

B1 + 2A2 + B2 = 0 A1 + B1 + A2 + B2 = 0 −A1 + B1 + 3A2 + B2 = 0 2A1 + B1 + B2 Nebo vyjádˇrenou jej´ı maticovou formou:      

0 1 −1 2

1 1 1 1

2 1 3 0

1 1 1 1

      ·    





A1 B1 A2 B2

    =    

0 0 0 0

     

Máme homogenn´ı soustavu rovnic, kde jsou ovˇsem lineárn´ı závislosti, tzn. vede na nekoneˇcnˇe mnoho ˇreˇsen´ı (to nás nepˇrekvapuje, neboˇt to oˇcekáváme). Navrhnˇeme A1 = A2 = 1, tzn.: B1 + B2 = −2 a zvolme B1 = B2 = −1. P˚uvodn´ı hra se tedy transformuje na hru: a

b

c

-1,1

0,0

d

-2,2 1,-1

Stejnˇe tak s jinými transformaˇcn´ımi koeficienty Ai = 1, B1 = 0, B2 = −2 na:

5.2

a

b

c

0,0

1,-1

d

-1,1 2,-2

Zápis 0-sum hry

Pokud plat´ı, zˇ e ∀s ∈ S : U1 (s) + U2 (s) = 0, pak lze psát pouze jednu matici U (s) a definovat U1 (s) = U (s), U2 (s) = −U (s). 2,-2 5,-5

0,0

2

5

0

3,-3 1,-1 2,-2 ⇒ 3

1

2

4,-4 3,-3 6,-6

3

6

4

Hru dvou hrácˇ u˚ s nulovým souˇctem s koneˇcnými mnoˇzinami strategi´ı S1 = {s11 , s12 , ..., s1m } a S2 = {s21 , s22 , ..., s2n } lze zadat pomoc´ A vyjadˇruj´ıc´ı zisky prvn´ıho hrácˇ e:  ı matice   a11 a12 . . . a1n U1 (s11 , s21 ) U1 (s11 , s22 ) . . . U1 (s11 , s2n )      a21 a22 . . . a2n   U1 (s12 , s21 ) U1 (s12 , s22 ) . . . U1 (s12 , s2n )      A= =  . . . . . .     1 2 1 2 1 2 am1 am2 . . . amn U1 (sm , s1 ) U1 (sm , s2 ) . . . U1 (sm , sn ) 41

Definice 27. Hra dvou hrácˇ u˚ s nulovým souˇctem je Γ = (Q; S1 , S2 ; U ), kde • Q = {1, 2} je mnoˇzina hrácˇ u˚ . • S1 a S2 jsou mnoˇziny ryz´ıch strategi´ı hrácˇ u˚ . • U : S → R je výplatn´ı funkce ve hˇre. Uˇzitkem hrácˇ e jedna je U1 (s) = U (s), U2 (s) = −U (s). Oba hrácˇ i maj´ı shodné vn´ımán´ı preference v tom smyslu, zˇ e preferuj´ı uˇzitek x pˇred y, právˇe tehdy kdyˇz x > y. To znamená pro sloupcového hrácˇ e, zˇ e preferuje napˇr´ıklad −2 nad −10. ˇ Casto budeme 0-sum hru zapisovat matic´ı hry A, pak by hra byla struktura Γ = (Q; S1 , S2 ; A). Jistˇe m˚uzˇ e být 0-sum hra s v´ıce hrácˇ i (interpretace uˇzitk˚u). Zde budeme rozv´ıjet výhradnˇe dvouhrácˇ ové 0-sum hry.

5.3

Chován´ı hrácˇ e v 0-sum hˇre

Mˇejme hru zadanou matic´ı A takto: 2

5

0

A= 3

1

2

4

3

6

Kaˇzdý hrácˇ v´ı, zˇ e na kaˇzdý jeho pˇr´ıpadný tah bude protihrácˇ reagovat svou best-response strategi´ı. ˇ adkový tud´ızˇ v´ı, zˇ e sloupcový bude na ˇra´ dku hledat minimum, coˇz je jeho BR – hrácˇ takto miniR´ malizuje svou prohru. Minimum na ˇra´ dku je pro ˇra´ dkového tud´ızˇ d˚uleˇzité. M˚uzˇ e ovˇsem zvolit takové minimum, které je mezi vˇsemi ˇra´ dky nejlepˇs´ı (nejvˇetˇs´ı). Je to hledán´ı maxima mezi minimy. • Minimum prvn´ıho ˇra´ dku: 0, • druhého: 1, • tˇret´ıho: 3, Závˇer: pokud bude rˇa´ dkový hrácˇ hrát tˇret´ı ˇra´ dek, pak dostane nejh˚uˇr zisk 3. Mus´ı pˇredpokládat racionalitu sloupcového hrácˇ e. Hledán´ı minima na ˇra´ dku nen´ı paranoidn´ı chován´ı, pouze pˇredpoklad racionality u sloupcového hrácˇ e. ˇ adkovému hrácˇ i rˇ´ıkáme maxminimizer. R´

42

Volba sloupcového Sloupcový pˇremýsˇl´ı podobnˇe a pˇritom opaˇcnˇe. V prvn´ım sloupci je sice jeho nejlepˇs´ı zisk 2 (tzn. −2), ale mus´ı poˇc´ıtat s t´ım, zˇ e ˇra´ dkový bude hrát tˇret´ı ˇra´ dek (jako svou BR). Pro prvn´ı sloupec je tud´ızˇ jeho nejvyˇssˇ´ı moˇzná ztráta 4 (druhý: 5, tˇret´ı: 6). Sloupcový hrácˇ minimalizuje svoji ztrátu, proto vol´ı prvn´ı sloupec. Sloupcový hrácˇ tud´ızˇ hledá maximum ve sloupci a globálnˇe minimum mezi maximy. Sloupcovému hrácˇ i ˇr´ıkáme minimaximizer.

5.4

Rovnovázˇ né strategie tvoˇr´ıc´ı ekvilibrium ve hˇre

Pˇripomeˇnme definici rovnovázˇ ného bodu (s∗1 , s∗2 ) v dvouhrácˇ ové hˇre. Definice 28. Profil (s∗1 , s∗2 ) pˇredstavuje rovnovázˇné strategie hrácˇ u˚ , pokud plat´ı: U1 (s1 , s∗2 ) ≤ U1 (s∗1 , s∗2 ) U2 (s∗1 , s2 ) ≤ U2 (s∗1 , s∗2 ) pro vˇsechny s1 ∈ S1 , s2 ∈ S2 . Uˇzitkové funkce definujeme U1 (·) = U (·), U2 (·) = −U (·). Pak p´ısˇeme, zˇ e v rovnovázˇ ném bodˇe mus´ı platit pro ˇra´ dkového hrácˇ e: U (s1 , s∗2 ) ≤ U (s∗1 , s∗2 )

(5.1)

Z pohledu sloupcového to je −U (s∗1 , s2 ) ≤ −U (s∗1 , s∗2 ) coˇz vede na (násoben´ı nerovnice zápornou konstantou se mˇen´ı smˇer nerovnosti): U (s∗1 , s2 ) ≥ U (s∗1 , s∗2 )

(5.2)

Z pˇredchoz´ıch vztah˚u (5.1) a (5.2) plyne celkovˇe: U (s1 , s∗2 ) ≤ U (s∗1 , s∗2 ) ≤ U (s∗1 , s2 ) Jinak ˇreˇceno, uˇzitek pro ˇra´ dkového hrácˇ e je jeho dosaˇzitelné maximum a pro sloupce dosaˇzitelné cˇ´ıselné minimum (které je jeho maximem). Hodnota U (s∗1 , s∗2 ) se nazývá cena hry (taky hodnota hry, angl. game value).

43

5.5

Sedlový bod (saddle point)

Definice 29. Mˇejme dvoumaticovou hru Γ = (Q; S1 , S2 ; U ). Ve hˇre definujeme minimax a maximin takto: m = min

s2 ∈S2

s1 ∈S1

m = max

s1 ∈S1

max U (s1 , s2 ) min U (s1 , s2 )

s2 ∈S2

Pro hru: 2 5

0

U (s1 , s2 ) = 3 1

2

4 3

6

to je m = 4 a m = 3. ˇ adkový by tud´ızˇ hrál tˇret´ı ˇra´ dek, sloupcový prvn´ı sloupec. Jaký je ovˇsem zisk hrácˇ u˚ v profilu s R´ ˇ adkový dostane o jedna lépe neˇz cˇ ekal, sloupcový o jedna h˚uˇr (kdyˇz to tedˇ vid´ı, hrál indexy (3, 1)? R´ by druhý sloupec). Sloupcový má tud´ızˇ tendenci zmˇenit svoji strategii na druhý sloupec (pak dostane ˇ adkový by pak zmˇenil na prvn´ı ˇra´ dek...a stability hra nedosáhne. 3). R´ Závˇer: profil (3, 1) nen´ı rovnovázˇ ný bod (nen´ı stabiln´ı). Kdy ovˇsem bude volba hrácˇ u˚ vedouc´ı ke stabiln´ımu profilu? Definice 30. Mˇejme 0-sum hru Γ. Profil s∗ je sedlovým prvkem, pokud plat´ı, zˇe:

U (s ) = max min U (s1 , s2 ) = min max U (s1 , s2 ) ∗

s1

s2

s2

s1

tzn. U (s∗ ) = m = m To znamená, zˇ e sedlový bod má výplatu nejmenˇs´ı na ˇra´ dku a souˇcasnˇe nejvyˇssˇ´ı ve sloupci. Sedlový bod pˇredstavuje rovnovázˇ ný stav (ryz´ı ekvilibrium) ve hˇre. Hodnota uˇzitku v sedlovém bodˇe se nazývá cena hry (value). Sedlový bod je ekvivalent PNE ve hrách s nenulovým souˇctem. Podobnˇe i tady nemus´ı v ryz´ıch strategi´ıch existovat. Stejnˇe jako u her s nenulovým souˇctem jsou tedy hry s: • 0 sedlovými body, • 1 sedlovým bodem, • n > 1 sedlovými body. Pˇripomeˇnme, zˇ e 0-sum hry jsou speciáln´ım pˇr´ıpadem her s nenulovým souˇctem, tzn. analytické postupy ve hrách s nenulovým souˇctem mohou být pouˇzity i ve 0-sum hrách. 44

Pˇr´ıklad: Mˇejme hru: 1

1

8

5

2

4

7

0

0

pak jej´ı maxmin a minmax jou m=m=2 a tud´ızˇ stejné. Hra má tedy rovnovázˇ ný bod v ryz´ıch strategi´ıch.

5.6

Ekvilibrium 0-sum her ve sm´ısˇených strategi´ıch

Sm´ısˇenou strategii v dvouhrácˇ ových hrách s nulovým souˇctem jenom m´ırnˇe modifikujeme: Definice 31. Sm´ısˇená strategie hrácˇ e i ve hˇre Γ je vektor pi = (pi1 , ..., pimi ), kde 1. mi = |Si | 2. ∀j ∈ {1, ..., mi } : pij ∈ h0, 1i 3.

Pmi

j=1

pij = 1

Definice 32. Mˇejme dvouhrácˇ ovou hru s nulovým souˇctem Γ = (Q; S1 , S2 ; U ). Sm´ısˇeným rozˇs´ırˇen´ım této hry nazveme hru s prostory strategi´ı ( S1s =

p, p = (p1 , ..., pm )|

m X

) pj = 1, ∀j ∈ {1, ..., m} : pj ∈ h0, 1i

j=1

( S2s =

q, q = (q1 , ..., qn )|

n X

) qk = 1, ∀k ∈ {1, ..., n} : qk ∈ h0, 1i

k=1

a výplatn´ı funkc´ı (A je matice hry) P Pn T π(p, q) = m j=1 k=1 pj U (sj , sk )qk = pAq Vˇeta 7 (Minimax theorem, John von Neumann). V kaˇzdé koneˇcné 0-sum hˇre existuje rˇeˇsen´ı ve formˇe sm´ısˇených strategi´ı. Origináln´ı znˇen´ı von Neumanna v jeho historickém kontextu2 bylo: 2

J. von Neumann: Zur Theorie der Gesellschaftsspiele, In: Math. Annalen, vol. 100, 1928, pp. 295–320

45

For every two-person, zero-sum game with finite strategies, there exists a value V and a mixed strategy for each player, such that (a) Given player 2’s strategy, the best payoff possible for player 1 is V, and (b) Given player 1’s strategy, the best payoff possible for player 2 is -V. Jiné znˇen´ı: Vˇeta 8. Vˇzdy existuj´ı sm´ısˇené strategie (p∗ , q ∗ ) takové, zˇe plat´ı: π(p∗ , q ∗ ) = max min π(p, q) = min max π(p, q) p

q

q

p

Hledáme tedy vektory p∗ , q ∗ takové, zˇ e plat´ı: pAq ∗T ≤ p∗ Aq ∗T ≤ p∗ Aq T pro vˇsechny p ∈ S1s , q ∈ S2s .

5.7

Grafické rˇ eˇsen´ı maticových her ve tvaru (2,n) strategi´ı

Pro jednoduchost se omez´ıme na hry, kde ˇra´ dkový hrácˇ má pouze dvˇe strategie a sloupcový jich má neomezenˇe. Oˇcekávaný zisk hrácˇ e 1 ve sm´ısˇených strategi´ıch (p, 1 − p) je pˇri ryz´ıch strategi´ıch hrácˇ e 2 dán: gj (p) = pa1j + (1 − p)a2j

j = 1, 2, ..., n

Hledáme (sloupcový hledá takové j, zˇ e gj (p) je minimáln´ı):

∗

p = arg max

min gj (p)

j=1,2,...,n

p∈h0,1i

Nejprve budeme hledat funkci ϕ(p) :=

min gj (p)

j=1,2,...,n

Tato funkce je konkávn´ı, po cˇ a´ stech lineárn´ı a snadno lze nalézt bod jej´ıho maxima. Hledaná cena hry je pak: v = ϕ(p∗ ) := max ϕ(p) p∈h0,1i

Nastává-li extrém v bodˇe p∗ , kde gj (p∗ ) = gk (p∗ ) = v pro jednoznaˇcnˇe urˇcené strategie j, k, pak sloˇzky sm´ısˇené rovnovázˇ né strategie hrácˇ e 2 s indexy r˚uznými od j, k jsou rovny nule. Sloˇzky, které mohou být nenulové, z´ıskáme vyˇreˇsen´ım soustavy: a1j qj + a1k qk = v qj + qk = 1 qj ≥ 0, qk ≥ 0

46

nebo a2j qj + a2k qk = v qj + qk = 1 qj ≥ 0, qk ≥ 0 Demo výpoˇctu sm´ısˇeného rˇ eˇsen´ı 0-sum hry Mˇejme maticovou hru 5 5/2 3 4 8 6

!

g1 (p) = 5p + 4(1 − p) = p + 4 g2 (p) = 52 p + 8(1 − p) = − 11 p+8 2 g3 (p) = 3p + 6(1 − p) = −3p + 6 Pˇripomeˇnme, zˇ e gj (p) vyjadˇruje oˇcekávaný zisk hrácˇ e 1 pro pˇr´ıpady, kdy hrácˇ 2 hraje strategie j. M´ıra výhry hrácˇ e 1 znaˇc´ı m´ıru prohry hrácˇ e 2. Hrácˇ 2 proto bude volit takové j, zˇ e gj (p), p ∈ h0, 1i bude minimáln´ı. ϕ(p) nabývá maxima v p = 12 , hodnota maxima je v = 4.5.

Figure 5.2: Reakˇcn´ı kˇrivky v pˇr´ıkladˇe [obrázek pˇrevzat z pˇrednásˇek M. Hykˇsové] Maximum bylo nalezeno jako pr˚useˇc´ık g1 (p) a g3 (p), tzn. j, k = 1, 3. Dále ˇreˇs´ıme soustavu rovnic (jeˇstˇe nás zaj´ımá q): 5q1 + 3q3 = 4.5 q1 + q3 = 1

47

s omezen´ımi q1 ≥ 0, q3 ≥ 0. Z´ıskáváme rˇeˇsen´ı q1 = 0.75, q3 = 0.25. ˇ sen´ı hry je tedy sm´ısˇený rovnovázˇ ný bod Reˇ ∗

∗

(p , q ) =

1 1 , 2 2

3 1 , , 0, 4 4

Oˇcekávaný uˇzitek hrácˇ e 1 je: π(p∗ , q ∗ ) =

13 11 13 11 5+ 3+ 4+ 6= 24 24 24 24

1 3 1 15 + 3 + 12 + 6 36 3 = = 4.5 = 5+ 3+ 4+ 6= 8 8 8 8 8 8 V´ıme, zˇ e hrácˇ hraj´ıc´ı sm´ısˇenou strategii je indiferentn´ı v˚ucˇ i vˇsem svým ryz´ım strategi´ım s nenulovou pravdˇepodobnost´ı jako best-response na sm´ısˇenou strategii protivn´ıka. Hrácˇ 1 oˇcekává strategii q ∗ u protivn´ıka, pak je mu jedno, jakou svoji strategii zvol´ı (obˇe maj´ı nenulovou pravdˇepodobnost). π((1, 0), q ∗ ) = 5 34 + 3 41 = 15+3 = 18 = 4 12 4 4 π((0, 1), q ∗ ) = 4 34 + 6 41 = 12+6 = 18 = 4 12 4 4 Pokud hrácˇ 2 uhne ze své strategie ( 43 , 0, 14 ) na strategii (0, 1, 0) pˇri pˇredpokladu, zˇ e hrácˇ 1 stále hraje p∗ , pak π(p∗ , (0, 1, 0)) = 52 12 + 8 12 = 5.25 a to je pro hrácˇ e 2 horˇs´ı výsledek (vˇetˇs´ı ztráta). Ekvilibrium ve sm´ısˇených strategi´ıch vyjadˇruje optimáln´ı oˇcekávaný zisk u obou hrácˇ u˚ . Pokud hrácˇ 2 odhal´ı sm´ısˇenou strategii p∗ protivn´ıka, pak se rozhoduje mezi strategiemi 1 a 3, protoˇze by jeho oˇcekávaný zisk pˇri hran´ı prostˇredn´ıho sloupce byl 21 52 + 8 = 5.25.

Bude-li hrácˇ 1 hrát jinou strategii neˇz p∗ = dosáhnou horˇs´ıho uˇzitku.

1 1 , 2 2

nebo hrácˇ 2 jinou neˇz q ∗ =

3 , 0, 14 4

, pak

Logika ekvilibria: Doufáme, zˇ e hrácˇ i tuto u´ vahu provedou a pochop´ı, zˇ e ekvilibrium pojmou za svoje chován´ı.

48

Chapter 6 Korelované ekvilibrium v nekooperativn´ıch hrách Korelované ekvilibrium je hern´ı koncept, který zobecˇnuje Nashovo ekvilibrium. Poprvé bylo definováno Robertem Aumannem (Nobel. cena, 2005) v cˇ lánku ”Aumann, R. (1974) Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics 1:67-96”. Korelované ekvilibrium (CE) je zaloˇzeno na myˇslence, zˇ e hrácˇ vol´ı svou strategii na základˇe pozorován´ı nˇejakého veˇrejnˇe známého signálu (signál je common knowledge). NE pˇredpokládá, zˇ e hrácˇ se rozhoduje pouze dle specifikace hry. Vedle toho, signál hrácˇ i ”napov´ı” tah. Pokud hrácˇ uvˇeˇr´ı, zˇ e vˇsichni protihrácˇ i hraj´ı dle CE a vid´ı, zˇ e by si pohorˇsil hran´ım jiného tahu (neˇz je ten napovˇezený), pak je profil tvoˇrený tˇemito nápovˇedami korelované ekvilibrium. Ve hˇre m˚uzˇ e existovat aˇz nekoneˇcná mnoˇzina takových profil˚u. Budeme dále pˇredpokládat racionalitu hrácˇ u˚ a volbu unikátn´ıho pareto dominantn´ıho profilu. Neˇcekáme, zˇ e existuje ”centráln´ı autorita”, která by hrácˇ u˚ m vyˇreˇsila jejich problém a navrhla jim ˇreˇsen´ı. Sp´ısˇe t´ım modelujeme fakt, zˇ e hrácˇ i zˇ ij´ı ve spoleˇcném informaˇcn´ım kontextu (ˇctou stejné noviny) a je jim spoleˇcná (je to common knowledge) racionalita ve smyslu snahy maximalizovat spoleˇcný prospˇech z volby strategického profilu. To povede také k tomu, zˇ e budeme pˇri výpoˇctu korelovaného ekvilibria maximalizovat spoleˇcenský uˇzitek (efektivitu) vybraného profilu.

6.1

Motivaˇcn´ı pˇr´ıklad

Uvaˇzujme hru: a

b

A

9,9

6,10

B

10,6

0,0

Hra má dvˇe ryz´ı Nashova ekvilibria a jedno sm´ısˇené: 49

• PNE (A, b) s daným ziskem (6, 10). • PNE (B, a) s daným ziskem (10, 6). • MNE (( 76 , 17 ), ( 67 , 17 )) s oˇcekávaným ziskem (8.57, 8.57). Pˇrepodpokládejme, zˇ e nˇekdo hod´ı minc´ı (padne H nebo T), coˇz je ten avizovaný veˇrejnˇe pozorovatelný signál. Hrácˇ i souhlas´ı (a je to common-knowledge), zˇ e budou hrát: • (A, b) v pˇr´ıpadˇe H, • (B, a) v pˇr´ıpadˇe T. Pˇri této dohodˇe a s pˇredpokladem synchrozniaˇcn´ıho signálu je oˇcekávaný zisk ve hˇre (8, 8), coˇz je oˇcekávaný uˇzitek hrácˇ u˚ pravdˇepodobnostnˇe váhovaný 6 · 0.5 + 10 · 0.5. M˚uzˇ e hra skuteˇcnˇe takto probˇehnout? Budou hrácˇ i respektovat pˇr´ıchoz´ı stav signálu? Co Bestresponse hrácˇ u˚ ? • Padne-li H, hrácˇ 1 v´ı, zˇ e hrácˇ 2 bude hrát b (A je tedy Best-response) • Padne-li T, hrácˇ 1 v´ı, zˇ e hrácˇ 2 bude hrát a (B je tedy Best-response) Oˇcekávané zisky nyn´ı mohou výt vyˇssˇ´ı neˇz v MNE (pokud napˇr. zmˇen´ıme v (A, a) zisky na (8, 8)). Pˇredpokládajme dále, zˇ e signál nemus´ı být aˇz tak informaˇcnˇe u´ plný. Poˇza´ dáme arbitra, aby hodil kostkou (výsledek n zˇ a´ dný z hrácˇ u˚ nevid´ı). • Oznám´ıme hrácˇ i 1, zda-li n padlo do {1, 2} nebo do {3, 4, 5, 6}. • Oznám´ıme hrácˇ i 2, zda-li n padlo do {1, 2, 3, 4} nebo do {5, 6}. Dohoda je podobná, jako v pˇredcházej´ıc´ı konfiguraci, tedy: • Hrácˇ 1 hraje B, pokud n ∈ {1, 2} nebo A pˇri n ∈ {3, 4, 5, 6}. • Hrácˇ 2 hraje a, pokud n ∈ {1, 2, 3, 4} nebo b pˇri n ∈ {5, 6}. Oˇcekávaný zisk v této konfiguraci se zmˇen´ı na (8.333, 8.333), coˇz m˚uzˇ eme ovˇeˇrit na BR1 : • Pokud oznám´ıme hrácˇ i 1, zˇ e n ∈ {1, 2}, pak hrácˇ v´ı, zˇ e hrácˇ 2 bude hrát a. Pak je jeho BR1 jednoznaˇcnˇe hrát B. • Pokud se hrácˇ 1 dozv´ı, zˇ e hod padl do intervalu 3-6, tedy n ∈ {3, 4, 5, 6}, je situace m´ırnˇe sloˇzitˇejˇs´ı. Hrácˇ 2 nemá jistotu mezi hran´ım a a b, proto bude hrát ( 21 , 12 ). Pak je BR1 hrát A. Celkovˇe je oˇcekávaný zisk prvn´ıho hrácˇ e (s pravdˇepodobnost´ı pravdˇepodobnost´ı 64 bude sloupcový hrát sm´ısˇenˇe ( 21 , 12 )): 2 4 1 1 π1 = 10 + ( 9 + 6) = 8.333 6 6 2 2 50

2 6

hra skonˇc´ı v profilu (B, a) a s

6.2

Definice korelovaného ekvilibria

Mˇejme hru Γ = (Q; {Si }i∈Q ; {Ui }i∈Q ). CE je od Nashova ekvilibria definováno odliˇsnˇe v tom ˇ sen´ım hry z smyslu, zˇ e pˇriˇrazuje kaˇzdému profilu s ∈ S pravdˇepodobnostn´ı ohodnocen´ı π(s). Reˇ pohledu CE je tedy vektor π = (π(s))s∈S . Definice 33. Mˇejme hru Γ = (Q; {Si }i∈Q ; {Ui }i∈Q ) a vektor π = (π(s))s∈S takový, zˇe: 1. π(s) ∈ h0, 1i ∀s ∈ S 2.

P

s∈S

π(s) = 1

Vektor π je korelovaným ekvilibriem ve hˇre Γ, pokud plat´ı pro vˇsechny hrácˇ e i ∈ Q a kaˇzdé dvˇe strategie si , di ∈ Si , di 6= si : X

π(si , s−i ) · (Ui (si , s−i ) − Ui (di , s−i )) ≥ 0

s−i ∈S−i

Bylo by dobré si nyn´ı rozebrat, co tato definice rˇ´ıká o chován´ı hrácˇ u˚ . Vyplyne z toho i logika výpoˇctu CE v zadané hˇre. Mnoˇzina nerovnic modeluje, co hrácˇ rozhodnˇe nikdy nepˇripust´ı – co neudˇelá. Výraz (Ui (si , s−i ) − Ui (di , s−i )) vyhodnocuje zmˇenu uˇzitku hrácˇ e i, pokud by v sub-profilu s−i pˇreˇsel ze své strategie si na di . Tento pˇrechod (deviace) je pochopitelnˇe moˇzný pouze z profil˚u, kde hrácˇ i hraje si , tedy kaˇzdá nerovnice modeluje zlepˇsen´ı/zhorˇsen´ı hrácˇ ova oˇcekávaného uˇzitku pro jednu konkrétn´ı dvojici strategi´ı si , di . Hrácˇ pˇripust´ı takovou deviaci pouze v pˇr´ıpadˇe, zˇ e v sumˇe P apornému oˇcekávanému zisku. Pokud s−i ∈S−i π(si , s−i ) · (Ui (si , s−i ) − Ui (di , s−i )) ≥ 0 vede k nez´ tedy tato má být platná pouze v pˇr´ıpadˇe, zˇ e promˇenné {π(si , s−i )}s−i ∈S−i jsou nulové, pak jsou tyto pravdˇepodobnosti nulové globálnˇe a tedy pro vˇsechny hrácˇ e a celou hru. Tato sada nerovnic konstruuje v pravdˇepodobnostn´ım prostoru dimenze |S| konvexn´ı mnohoúheln´ık (angl. polytope), nˇeco jako vyjednávac´ı prostor, kde vˇsechny body tohoto prostoru jsou pro hrácˇ e pˇr´ıpustné a dosaˇzitelné (feasible) a hledáme jejich racionáln´ı bod dohody (pareto efektivn´ı), tedy opˇet nˇekde na ohraniˇcen´ı této mnoˇziny. Hledán´ı pareto optimáln´ıho korelovaného ekvilibria je LP-úloha maximalizuj´ıc´ı spoleˇcný uˇzitek. Korelované ekvilibrium je zobecnˇen´ım MNE, tedy kaˇzdé MNE je CE, ale naopak to neplat´ı. Vztah MNE a CE dokumentuje následuj´ıc´ı vˇeta (jej´ı d˚ukaz je dostupný na stránkách THE): ∗ Vˇeta 9. Je-li σ ∗ MNE, pak π = ΠN e ekvilibrium. i=1 σ (si ) s∈S je korelovan´ Korelované ekvilibrium je z nepochopitelných d˚uvod˚u na okraji zájm˚u hern´ıch teoretik˚u, i pˇresto, zˇ e je sympatické z mnoha d˚uvod˚u: • CE je nadmnoˇzina MNE, tzn. vˇsechny MNE jsou souˇcasnˇe CE. Plyne z toho, zˇ e CE vˇzdy existuje. Nash dokázal, zˇ e MNE vˇzdy existuje, proto vˇzdy existuje CE. 51

• Christos Papadimitriou dokázal (ˇclánek ”Computing correlated equilibria in multi-player games”, In: 37th ACM Symposium on Theory of computing), zˇ e výpoˇcet CE je v polynomické cˇ asové sloˇzitostn´ı tˇr´ıdˇe, coˇz je znaˇcný posuv od obecnˇe exponenciáln´ı sloˇzitosti výpoˇctu sm´ısˇeného Nashova ekvilibria. Pˇripomeˇnme, zˇ e pro výpoˇcet MNE ve v´ıce-hrácˇ ových hrách prakticky neexistuje algoritmus jejich výpoˇctu (natoˇz pak nˇejakého efektivn´ıho výpoˇctu). • Martin Hrubý navrhl algoritmus efektivn´ıho výpoˇctu CE se zapojen´ım paralelismu (ˇclánek ”Algorithmic Approaches to Game-Theoretical Modeling and Simulation, In: AUCO Czech Ecomomic Review, on-line: auco.cuni.cz). Tento algoritmus je obvzlásˇˇt efektivn´ı pˇri souˇcasné potˇrebˇe vyˇc´ıslovat uˇzitky U (s) v profilech s nˇejakým dalˇs´ım modelem. ˇ ıdka a M. Hrubého. • Existuje efektivn´ı nástroj výpoˇctu CE pod názvem CE-Solver1 autor˚u S. Z´ • Výpoˇcet CE je zaloˇzen na lineárn´ım programován´ı. Algoritmus jeho výpoˇctu je jednoduchý, jednoznaˇcný a bez výjimek. Algoritmus neodliˇsuje mezi dvouhrácˇ ovou a v´ıce-hrácˇ ovou hrou.

6.3

´ Výpoˇcet CE obecnˇe (LP-uloha)

Mnoˇzina korelovaných ekvilibri´ı pro zadanou hru je obecnˇe nekoneˇcná (je to podprostor vymezený nerovnicemi z definice CE). Budeme z této mnoˇziny vyb´ırat unikátn´ı Pareto efektivn´ı profil, který má CE vlastnost. To znamená, zˇ e maximalizujeme souhrnný uˇzitek Z(s) v CE profilu Z: M AX : Z =

X

π(s)Z(s)

s∈S

Z(s) =

X

wi · Ui (s)

i∈Q

Teoreticky m˚uzˇ eme vliv hrácˇ u˚ váhovat nˇejak vhodnˇe zvolenými koeficienty wi , ale pokud hrácˇ i nejsou silnˇe nesymetriˇct´ı, nebudou m´ıt tyto koeficienty valný vliv na volbu profilu. Promˇenné v této LP-úloze budou pravdˇepodobnosti jednotlivých profil˚u hry: π(s) ∈ h0, 1i ; ∀s ∈ S Omezuj´ıc´ı podm´ınky (constraints) jsou dány principem pravdˇepodobnostn´ıho charakteru CE: X

π(s) = 1

s∈S

A dalˇs´ı omezen´ı jsou dány matic´ı uˇzitk˚u (obecnˇe): 1

Dostupný na http://perchta.fit.vutbr.cz/CE-Solver/

52

G · πT ≥ 0 Matice G je definována takto: ˇ adky matice G jsou indexovány i, j, k, kde i ∈ Q, j, k ∈ Si . Matice G Má tud´ızˇ • R´ (|Si | − 1) ˇra´ dk˚u.

PN

i=1

|Si | ·

• Sloupce jsou indexovány strategickými profily, je tud´ızˇ S sloupc˚u v matici. • Prvek matice Gi,j,k v profilu s ∈ S je dán:  U (j, s ) − U (k, s ) s = j i −i i −i i Gi,j,k (s) = 0 jinak P T ˇ s´ıme LP-úlohu s promˇennými π(s) a omezuj´ıc´ımi podm´ınkami ( Reˇ s∈S π(s) = 1, G · π ≥ 0). Maximalizujeme Z. Výsledkem je naplnˇen´ı promˇenných π(s) pravdˇepodobnostmi profil˚u. D˚uleˇzité je si uvˇedomit, zˇe tento postup výpoˇctu vyhodnocuje jedno Pareto efektivn´ı CE. Nen´ı tud´ızˇ pravda, zˇ e existuje pouze jedno CE a to je jednoznaˇcnou odpovˇed´ı na otázku ”co hrácˇ i udˇelaj´ı?”. Tento algoritmus nijak nen´ı omezen poˇctem hrácˇ u˚ nebo jejich strategi´ı – pouze výslednou cˇ asovou a pamˇeˇtovou sloˇzitost´ı. Demonstraˇcn´ı pˇr´ıklad výpoˇctu CE Mˇejme zadanou hru: A/B

c

d

a

10,2 8,4

b

5,4

7,3

Jej´ı profily jsou S = {(a, c), (a, d), (b, c), (b, d)} G-matice (ˇra´ dky modeluj´ı moˇzné deviace hrácˇ u˚ , sloupce jsou vˇsechny profily ve hˇre): j → k/s

ac

ad

a→b

5

1

b→a c→d

bc

bd

−5 −1 −2

d→c

1 2

53

−1

Maximalizace Z =

P

s∈S

π(s)Z(s). Systém nerovnic G · π T ≥ 0 je následuj´ıc´ı: 5π(ac) + π(ad) ≥ 0 −5π(bc) − π(bd) ≥ 0 −2π(ac) + π(bc) ≥ 0 2π(ad) − π(bd) ≥ 0

Druhá nerovnice jasnˇe vede k π(bc) = π(bd) = 0. Z toho plyne: −2π(ac) + 0 · π(bc) ≥ 0 plat´ı pouze pro π(ac) = 0. P Zbývá π(ad) ≥ 0 ∧ π(s) = 1, tzn. π(ad) = 1. CE v této hˇre je tedy vektor (0, 1, 0, 0). Monohoúheln´ık v pravdˇepodobnostn´ım prostoru ˇreˇsen´ı je tedy pouze singleton obsahuj´ıc´ı bod (0, 1, 0, 0). Hra má tedy unikátn´ı CE, které je souˇcasnˇe unikátn´ı PNE.

6.4

Princip CE obecnˇe – analytický efekt G-matice

Mnoˇzina nerovnic G · π T ≥ 0 modeluje hrácˇ ovy tendence pˇrecházet mezi strategiemi. Pokud je ˇra´ dek Gi,j,k (s) celý záporný (resp. Gi,j,k (s) ≤ 0; ∀s ∈ S a souˇcasnˇe ∃s ∈ S : Gi,j,k (s) < 0), pak strategie k striktnˇe dominuje nad j (pˇrechodem z j na k se zhorˇs´ı hrácˇ u˚ v uˇzitek). Pokud je ˇra´ dek nulový, pak jsou strategie ekvivalentn´ı. Takový ˇra´ dek m˚uzˇ e být z LP-constraints vypuˇstˇen, neboˇt nemá zˇ a´ dný efekt. Pokud existuj´ı kladné i záporné koeficienty Gi,j,k (s), pak nelze nic o strategi´ıch j, k ˇr´ıct. Pokud existuj´ı pouze kladné a nulové koeficienty, pak strategie j slabˇe dominuje nad k (nelze ˇr´ıct, zˇ e dominuje striktnˇe). Matice G zde vystupuje jako zaj´ımavý analytický nástroj s velmi jednoduchou datovou strukturou. V následuj´ıc´ım algoritmu této vlastnosti vyuˇzijeme pro iterativn´ı eliminaci dominovaných strategi´ı.

6.5

Optimalizovaný výpoˇcet CE ve hˇre (Hrubý, 2008)

Tento algoritmus byl vyvinut pro výpoˇcet CE ve v´ıcehrácˇ ových hrách s mnoha strategiemi. Publikován byl ve formˇe volnˇe sˇ´ıˇritelného nástroje pojmenovaného CE-Solver. Nástroj lze vyuˇz´ıt pro výpoˇcet CE v zadané hˇre nebo pˇrinejmenˇs´ım k redukci prostoru profil˚u hry na menˇs´ı hru (vede pak na menˇs´ı LP-úlohu). Specificky je nástroj výhodný v tˇech situac´ıch, kdy uˇzitky hrácˇ u˚ v profilu s nejsou pˇredem známy (jak to obvykle popisujeme tou matic´ı uˇzitk˚u), ale je nutno je na poˇza´ dán´ı vypoˇc´ıtat nˇejakou funkc´ı, zde referovanou jako cellM odel(s). Pokud výpoˇcet této funkce nen´ı z hlediska cˇ asové nároˇcnost algoritmu triviáln´ı, je nutno se zamyslet nad poˇctem volán´ı cellM odel, které mus´ıme pro dokonˇcen´ı výpoˇctu CE absolvovat. Mˇejme hru Γ = (Q; {Si }i∈Q ; {Ui }i∈Q ) a poˇc´ıtaˇcový model (proceduru) cellM odel : S → RN pro výpoˇcet uˇzitk˚u U (s) := cellM odel(s). Pˇredpokládejme, zˇ e výpoˇcet cellM odel(s) je hlavn´ı cˇ asovou

54

zátˇezˇ´ı na výpoˇcet. Chceme omezit poˇcet invokac´ı cellM odel na minimum, tzn. hledáme minimáln´ı Sr ⊆ S potˇrebnou pro vyhodnocen´ı CE. Sestavujeme redukovanou hru, tzn. redukovanou Sr ⊆ S.

6.5.1

Redukce G-matice v naˇsem pˇr´ıkladˇe

Postup redukce je popsán na obrázku 6.1. ac 5

ad 1

bc

a→b

ab 5

ad 1

bd

a→b b→a −5 −1 c → d −2 1 d→c 2 −1 ˇRádek b → a je celý záporný, tud´ızˇ strategie b je striktnˇe dominovaná strategi´ı a. Dalˇs´ı výpoˇcty v profilech bc a bd jiˇz nebudou vyˇzadovány.

c → d −2 d→c 2 V tomto kontextu redukce hry vypadává ˇra´ dek c → d a s n´ım i profil ab.

ad a→b 1 d→c 2 Zbývá pouze profil ad a t´ım i eliminace konˇc´ı s vyhodnoceným ekvilibriem (dle pˇredchoz´ıch poznatk˚u je ekvilibrium neeliminovatelné pˇri eliminaci striktnˇe dominovaných strategi´ı). Figure 6.1: Iterativn´ı eliminace dominovaných strategi´ı v pˇr´ıkladu CE-Solveru

55

Bibliography [1] Nash, J.: Non-cooperative Games, Annals op Mathematics Vol. 54, No. 2, 1951 [2] von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behavior, 1944

56

Doprovodné texty ke kurzu Teorie her

Recommend Documents