ÚVOD DO TEORIE HER MGR. LENKA PLOHÁKOVÁ RNDR. DAVID BARTL, PH.D

ÚVOD DO TEORIE HER

MGR. LENKA PLOHÁKOVÁ RNDR. DAVID BARTL, PH.D.

ČÍSLO OPERAČNÍHO PROGRAMU: CZ.1.07 NÁZEV OPERAČNÍHO PROGRAMU: OP VZDĚLÁVÁNÍ PRO KONKURENCESCHOPNOST ČÍSLO OBLASTI PODPORY:

ZVYŠOVÁNÍ ODBORNÝCH KOMPETENCÍ AKADEMICKÝCH PRACOVNÍKŮ OSTRAVSKÉ UNIVERZITY V OSTRAVĚ A SLEZSKÉ UNIVERZITY V OPAVĚ REGISTRAČNÍ ČÍSLO PROJEKTU: CZ.1.07/2.2.00/15.0026

OSTRAVA 2013

Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky Recenzent: Ing. Eva Moravcová, CSc.

Název: Autor: Vydání: Počet stran:

Úvod do teorie her Mgr. Lenka Ploháková, RNDr. David Bartl, Ph.D. první, 2013 78

Studijní materiály pro distanční kurz: Úvod do teorie her Jazyková korektura nebyla provedena, za jazykovou stránku odpovídá autor.

© Mgr. Lenka Ploháková, RNDr. David Bartl, Ph.D. © Ostravská univerzita v Ostravě

Úvod do teorie her

Mgr. Lenka Ploháková RNDr. David Bartl, Ph.D.

2013

Úvod do teorie her

Obsah

Obsah Předmluva

3

1 Úvod

6

2 Maticové hry

12

2.1

Příklady maticových her . . . . . . . . . . . . . . . . . . . . . . 21

2.2

Smíšené rozšíření maticových her . . . . . . . . . . . . . . . . . 26

2.3

Symetrické hry . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.4

Dominování v maticových hrách . . . . . . . . . . . . . . . . . . 32

2.5

Vztah maticových her a úloh lineárního programování . . . . . . 34

3 Dvojmaticové hry a obecné hry n hráčů ve strategickém tvaru 38 3.1

Další příklady dvojmaticových her . . . . . . . . . . . . . . . . . 40

3.2

Smíšené rozšíření dvojmaticové hry . . . . . . . . . . . . . . . . 41

3.3

Kompaktní metrické prostory . . . . . . . . . . . . . . . . . . . 43

3.4

Heineho-Borelova pokrývací věta . . . . . . . . . . . . . . . . . 45

3.5

Spernerovo lemma . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.6

Brouwerova věta o pevném bodě . . . . . . . . . . . . . . . . . . 51

3.7

Věta Nikaidô-Isody . . . . . . . . . . . . . . . . . . . . . . . . . 53

4 Kooperativní hry

57

4.1

Kooperativní hry s přenosnou výhrou ve tvaru koaliční funkce . 58

4.2

Kooperativní hry ve tvaru funkce koaliční struktury . . . . . . . 58

4.3

Koncepty řešení kooperativních her s přenosnou výhrou . . . . . 59 4.3.1

Jádro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

4.3.2

Vyjednávací množina . . . . . . . . . . . . . . . . . . . . 62

4.3.3

Kernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

4.3.4

Nukleolus . . . . . . . . . . . . . . . . . . . . . . . . . . 65 2

Úvod do teorie her

Obsah

4.3.5

Shapleyova hodnota

. . . . . . . . . . . . . . . . . . . . 69

4.3.6

Von Neumannovo-Morgensternovo řešení . . . . . . . . . 72

Příloha: Vysvětlivky k používaným symbolům

3

78

Úvod do teorie her

Předmluva

Předmluva Předkládaný text „Úvod do teorie herÿ je určen především jako podpůrný stuœ dijní materiál k předmětu „Teorie herÿ (KMA/TEHER), který probíhá prezeœ nční formou a je zařazen ve studijním plánu zaměření „Optimalizace a operační výzkumÿ oboru Aplikovaná matematika navazujícího magisterského studia na Přírodovědecké fakultě Ostravské univerzity v Ostravě. Uvedený předmět je zařazen rovněž ve studijních plánech některých dalších oborů (Aplikace matematiky v ekonomii ) navazujícího magisterského studia na PřF OU.

Sepsání tohoto studijního textu bylo vyžádáno potřebou nějaký studijní mateœ riál k předmětu „Teorie herÿ vytvořit. Text by měl posloužit také těm studenœ tům, kteří z nějakého důvodu nemohou přednášky z „Teorie herÿ pravidelně navštěvovat. Pokud jde o obsah tohoto studijního materiálu, ten je ovlivněn nyní (jaro/léto 2013) probíhající změnou pojetí uvedeného předmětu. Zatímco ještě donedávna platilo, že studenti Aplikované matematiky a dalších oborů se s teorií her poprvé setkávali až v navazujícím magisterském studiu (a tudíž předmět „Teorie herÿ musel být pojat více elementárně: musel být podán všeœ obecný úvod a zařazena základní teorie maticových her; v dalších oblastech již nebylo lze jít do větších hloubek), nyní už tomu tak není. V současné době se studenti všech matematických oborů PřF OU seznámí se základy maticových her již v povinném předmětu „Úvod do lineárního programování a teorie herÿ (KMA/ULPTH) bakalářského stupně studia.

Předkládaný studijní text tedy vzniká v přechodném období. Protože změna bakalářského studia se v navazujícím studiu projeví až po nějaké době (někœ teří současní studenti navazujícího magisterského studia předmět „Úvod do lineárního programování a teorie herÿ nemuseli absolvovat), je stále zařazena úvodní část týkající se teorie maticových her, které by v budoucnu měly z předœ mětu „Teorie herÿ vymizet. Naopak již jsou zařazeny některé pokročilejší části, například klasická věta Nikaidô-Isody o existenci bodu Nashovy rovnováhy nebo hlubší vztahy mezi koncepty řešení kooperativních her s přenosnou výœ hrou. Zmíněné části teorie her – pokud je autorům tohoto předkládaného textu 4

Úvod do teorie her

Předmluva

známo – nejsou v české (popř. slovenské) literatuře příliš zpracovány. Rovněž je nutné poznamenat, že teorie her je již neuvěřitelně rozsáhlou oblastí, kterou v žádném případě nebude možné pokrýt během jednoho (ani několika) jedœ nosemestrálního kursu. Obsah předmětu „Teorie herÿ je tedy do značné míry ovlivněn volbou přednášejícího. Zájemce o další oblasti teorie her nezbývá než odkázat na samostatné studium další literatury (které je nepřeberné množství). Doporučit lze například monografii • Owen, G. Game Theory. 3rd edition. Academic Press, 1995. ISBN 0-12-531151-6. Širší přehled lze získat z kolektivních prací • Aumann, R. J., Hart, S. (Eds.) Handbook of Game Theory with Economic Applications: Volume 1. Amsterdam: North Holland, 1992. ISBN 0-444-88098-4. • Aumann, R. J., Hart, S. (Eds.) Handbook of Game Theory with Economic Applications: Volume 2. Amsterdam: Elsevier, 1994. ISBN 0-444-89427-6. • Aumann, R. J., Hart, S. (Eds.) Handbook of Game Theory with Economic Applications: Volume 3. Amsterdam: North Holland, 2002. ISBN 0-444-89428-4. Další znalosti lze čerpat z odborných časopisů, například • Games and Economic Behavior, • Journal of Economic Theory nebo • International Journal of Game Theory. Jak vyplývá, právě předkládaný studijní text „Úvod do teorie herÿ je spíše jeho první verzí, která se dozajista bude vyvíjet spolu s vývojem obsahu předmětu „Teorie herÿ (KMA/TEHER). Autoři proto uvítají Vaše upozornění na chyby v textu i jakékoliv další podněty a připomínky. 5

Úvod do teorie her

1

1 Úvod

Úvod

Klíčová slova Teorie her, konfliktní situace, rozhodovací situace, hra, dělení her, hra ve straœ tegickém tvaru, množina hráčů, prostor strategií, výplatní funkce, Nashova rovnováha.

V této části zavedeme základní pojmy potřebné ke studiu.

Teorie her se zabývá studiem modelů konfliktních nebo rozhodovacích situací. Model je popis situace matematickými prostředky (pomocí pojmu množiny, funkce, čísla atd.). Konfliktní situace nastává mezi dvěma nebo více účastníky ve chvíli, kdy jsou zájmy těchto účastníků protichůdné. Rozhodovací situace pak zobecňuje konfliktní situaci v tom smyslu, že zájmy účastníků nemusí být (nutně) protichůdné. Účelem je nalézt nejlepší rozhodœ nutí. Rozhodovací situaci nazýváme hrou a účastníky rozhodovací situace nazýváme hráči. Hry můžeme dělit podle různých kritérií. Pro základní představu, čím se teœ orie her zabývá, zde uvedeme některá základní dělení vycházející z knihy [Maňas - 1991]. Dělení podle dějiště: 1. hry salónní – šachy, dáma, karetní hry apod., 2. hry venkovní – fotbal, hokej, tenis apod.

6

Úvod do teorie her

1 Úvod

Toto dělení má důležité opodstatnění při studiu analogií s reálnými konflikty. Hry salónní jsou k tomuto účelu vhodné, hry venkovní již méně. Vychází to z faktu, že u her salónních můžeme dobře rozlišit jednotlivé fáze hry (při hře v šachy například jednotlivé tahy). Dělení podle počtu hráčů ve hře: 1. hry s jedním hráčem, 2. hry se dvěma hráči, 3. hry n hráčů (kde n je přirozené číslo), 4. hry s nekonečně mnoha hráči. Dělení podle spolupráce: 1. hry nekooperativní (hráči nespolupracují), 2. hry kooperativní (hráči spolupracují) (a) s přenosnou výhrou, (b) s nepřenosnou výhrou. Dělení podle počtu strategií (pouze u nekooperativních her): 1. hry konečné – každý hráč má na výběr pouze z konečně mnoha možností, 2. hry nekonečné – ostatní hry. Dělení podle informovanosti hráčů: 1. hry s úplnou informací – všichni hráči mají úplný přehled o herní situaci (například hra v šachy, dáma), 2. hry s neúplnou informací – některá informace je skryta (například karetní hry).

7

Úvod do teorie her

1 Úvod

V těchto skriptech se budeme zabývat hrami se dvěma nebo více (konečně mnoha) hráči, nekooperativními hrami, konečnými i nekonečnými a kooperaœ tivními hrami s přenosnou výhrou.

V další části se budeme zabývat hrami nekooperativními, a to konkrétně hrami ve strategickém tvaru. Poznámka 1 V literatuře se lze setkat také s pojmenováním hra v normálním tvaru. Ačkoliv obě pojmenování mají stejný význam, v tomto učebním textu používáme pojmenování hra ve strategickém tvar pro jeho větší výstižnost.

Definice 1.1 Hra n hráčů ve strategickém tvaru je zadána: 1. množinou hráčů N = {1, . . . , n}, 2. prostory strategií X1 , . . . , Xn , 3. výplatními funkcemi F1 , . . . , Fn . Množina hráčů N je souborem účastníků dané rozhodovací situace (hráči jsou označeni čísly, např. v případě dvou hráčů N = {1, 2}). Každý z těchto hráčů se může rozhodnout, jak bude jednat. Všechna rozhodœ nutí, která i-tý hráč může učinit, vložíme do množiny Xi , kterou nazýváme prostor strategií i-tého hráče (množina Xi je neprázdná pro i = 1, . . ., n). Hráči jsou v nějakém prostředí a každé rozhodnutí, které hráč (nebo hráči) provedou, působí na toto prostředí i na ostatní hráče. Výsledkem takového rozhodnutí pak je, že i-tý hráč dostane nějakou výplatu (například peníze, poœ chvalu, cement atd.). Pro účely modelu se předpokládá, že výplata je reálné číslo.

Každý hráč i = 1, . . ., n má svou výplatní funkci Fi : Fi :

X1 × X2 × · · · × Xn−1 × Xn −→ R, 7−→ Fi (x1 , x2 , . . . , xn−1 , xn ).

[x1 , x2 , . . . , xn−1 , xn ]

8

Úvod do teorie her

1 Úvod

Hra pak probíhá následovně: 1. každý hráč i zvolí jednu strategii xi ze svého prostoru strategií Xi , 2. hra se sehraje, 3. každý hráč i obdrží svou výplatu Fi (x1 , . . . , xn ). Poznámka 2 Výplata každého hráče i = 1, . . ., n závisí na rozhodnutích všech hráčů, tj., hráči svými rozhodnutími navzájem ovlivňují své výplaty. Uvažujeme, že zadaná hra ve strategickém tvaru je nekooperativní a že každý z hráčů chce určit strategii, která je pro něj nejlepší. Učiníme následující tři předpoklady: 1. každý hráč se rozhoduje samostatně, tj. nezávisle na ostatních, 2. každý hráč se snaží maximalizovat svou vlastní výhru (bez ohledu na ostatní), 3. (princip pomalé reakce) jestliže jediný hráč změní svou strategii, pak ostatní hráči na tuto změnu nereagují, tj., své strategie nemění. Řešením takovéto situace je bod Nashovy rovnováhy. Definice 1.2 Mějme hru ve strategickém tvaru. Řekneme, že bod [x∗1 , x∗2 , . . . , x∗n ] z kartézského součinu X1 ×X2 ×· · ·×Xn všech prostorů strategií je bodem Nashovy rovnováhy právě tehdy, když pro každé xi z prostoru strategií Xi platí, že Fi (x∗1 , . . . , x∗i−1 , xi , x∗i+1 , . . . , x∗n ) ≤ Fi (x∗1 , . . . , x∗i−1 , x∗i , x∗i+1 , . . . , x∗n ), pro každé i = 1, . . ., n.

9

(1)

Úvod do teorie her

1 Úvod

Poznámka 3 To znamená, že jestliže kterýkoli hráč i = 1, . . ., n zvolí jiœ nou strategii xi , pak ostatní hráči na tuto změnu nereagují. Nadále používají strategie x∗1 , . . . , x∗i−1 , x∗i+1 , . . . , x∗n . Potom výplata i-tého hráče poklesne (resp. nevzroste). Tato skutečnost – protože i-tý hráč podle druhého předpokladu chce svou výplatu maximalizovat – jej přiměje vrátit se zpět ke své rovnovážné strategii x∗i . To znamená, že systém se po tomto druhu „vychýleníÿ vrátí zpět do rovnovážného bodu. Poznámka 4 Nashova rovnováha pak představuje koncept řešení nekooperaœ tivních her (her ve strategickém tvaru), a to v tom smyslu, že se herní situace v tomto bodě časem ustálí. Otázka 1 Co se stane, pokud má hra více bodů Nashovy rovnováhy? Pokud existuje více bodů Nashovy rovnováhy, nevíme, kde se hra nakonec ustálí, jelikož každý z hráčů může preferovat jiný bod Nashovy rovnováhy. K řešení takovéto situace využíváme dominující bod Nashovy rovnováhy. ∗∗ Definice 1.3 Bod [x∗∗ 1 , . . . , xn ] je dominujícím bodem Nashovy rovnováhy

právě tehdy, když je bodem Nashovy rovnováhy a zároveň pro každý další bod Nashovy rovnováhy [x∗1 , . . . , x∗n ] platí, že ∗∗ Fi (x∗1 , . . . , x∗n ) ≤ Fi (x∗∗ 1 , . . . , xn )

pro každé i = 1, . . ., n. Cvičení 1.1 Uvažujme hru dvou hráčů (N = {1, 2}) s prostory strategií X1 = {a, b, c} a X2 = {x, y, z}, kde výplaty jsou určeny následující tabulkou: 2. hráč x

1. hráč

y

z

a

4 3

0

1

1

0

b

1 0

5

5

0

1

c

0 1

1

0

3

4

10

Úvod do teorie her

1 Úvod

(Tedy F1 (a, x) = 4, F2 (a, x) = 3, F1 (a, y) = 0 atd.) (a) Určete všechny body Nashovy rovnováhy v této hře. (b) Který z bodů Nashovy rovnováhy je dominující?

11

Úvod do teorie her

2

2 Maticové hry

Maticové hry

Obsah lekce 2.1. Příklady maticových her . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2. Smíšené rozšíření maticových her . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.3. Symetrické hry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.4. Dominování v maticových hrách . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.5. Vztah maticových her a úloh lineárního programování . . . . . . . . . . 34

Klíčová slova Hra s konstantním součtem, hra s nulovým součtem, maticová hra, sedlový bod, smíšené rozšíření, symetrická hra, dominování.

V této kapitole se seznámíme s pojmem maticové hry. Maticové hry jsou speciœ álním případem nekooperativních her ve strategickém tvaru. Podrobněji: maœ ticové hry jsou speciálním případem her dvou hráčů s nulovým součtem, které jsou speciálním případem her n hráčů s konstantním součtem, a tyto jsou speciálním případem nekooperativních her n hráčů. S nekooperativními hrami ve strategickém tvaru jsme se seznámili v předchozí kapitole. Nyní si vysvětlíme zbývající pojmy. Definice 2.1 Hra ve strategickém tvaru (viz definice 1.1 ) má konstantní součet právě tehdy, když pro každé x ∈ X1 × X2 × · · · × Xn platí F1 (x) + F2 (x) + · · · + Fn (x) = c, kde c je konstanta. Definice 2.2 V případě, že se jedná o hru s konstantním součtem s konstantou c = 0, říkáme, že jde o hru s nulovým součtem. 12

Úvod do teorie her

2 Maticové hry

Poznámka 5 Ve hře s nulovým součtem si hráči své výplaty přerozdělí, tj., co jedni vyhrají, druzí prohrají. V této chvíli je vhodné se zamyslet nad existencí vztahu mezi hrami s konœ stantním a nulovým součtem. Definice 2.3 Mějme dvě hry se stejnou množinou hráčů N = {1, . . . , n} a stejnými prostory strategií X1 , . . . , Xn . Dále nechť F1 , . . . , Fn jsou výplatní funkce v první hře a G1 , . . . , Gn jsou výplatní funkce v druhé hře. Pak řekneme, že uvedené hry jsou strategicky ekvivalentní právě tehdy, když pro každé x, y ∈ X1 × · · · × Xn platí F1 (x) ≤ F1 (y) ⇔

G1 (x) ≤ G1 (y)

F2 (x) ≤ F2 (y) ⇔ .. .

G2 (x) ≤ G2 (y)

Fn (x) ≤ Fn (y) ⇔ Gn (x) ≤ Gn (y). Věta 2.1 Každou hru s konstantním součtem lze převést na hru s nulovým součtem, která je s původní hrou strategicky ekvivalentní.

Důkaz Například od každé výplatní funkce Fi stačí odečíst konstanu c/n pro i = 1, . . ., n.



Jak jste si jistě všimli, v předchozích definicích se hovoří o obecné množině hráčů N . Nás ale pro účely maticových her bude zajímat pouze případ hry dvou hráčů, tj. N = {1, 2}. Ve hře dvou hráčů s nulovým součtem je vztah hráčů antagonistický (výhra jednoho je prohrou druhého hráče). Tedy v takovémto případě platí, že F1 = −F2 a naopak F2 = −F1 , proto stačí zadat pouze jednu z těchto výplatních funkcí, například funkci F1 , kterou pak budeme značit pouze F . Prostory strategií X1 resp. X2 budeme značit X resp. Y . Definice 2.4 Hra dvou hráčů s nulovým součtem se nazývá antagonistická hra.

13

Úvod do teorie her

2 Maticové hry

Otázka 2 Co znamená pojem Nashovy rovnováhy v případě hry dvou hráčů s nulovým součtem? Mějme hru dvou hráčů s nulovým součtem s prostory strategií X1 a X2 a výplatními funkcemi F1 a F2 . Položíme X = X1 a Y = X2 . Podle definice 1.2 bod [x∗ , y ∗ ] ∈ X ×Y je bodem Nashovy rovnováhy právě tehdy, když pro každé x ∈ X a každé y ∈ Y platí F1 (x, y ∗ ) ≤ F1 (x∗ , y ∗ ),

(2)

F2 (x∗ , y) ≤ F2 (x∗ , y ∗ ).

(3)

a

Položíme-li F = F1 = −F2 , potom uvedené vztahy (2) a (3) lze ekvivalentně zapsat jako F (x, y ∗ ) ≤ F (x∗ , y ∗ ) ≤ F (x∗ , y). Bod Nashovy rovnováhy tedy ve hře dvou hráčů s nulovým součtem odpovídá sedlovému bodu výplatní funkce F . Definice 2.5 Nechť X a Y jsou množiny, dále nechť F : X ×Y → R je funkce. Bod [x∗ , y ∗ ] nazveme sedlovým bodem funkce F právě tehdy, když pro každé x ∈ X a každé y ∈ Y platí, že F (x, y ∗ ) ≤ F (x∗ , y ∗ ) ≤ F (x∗ , y). Nyní si uvedeme větu týkající se vlastností sedlového bodu. Věta 2.2 (o sedlových bodech) Nechť X a Y jsou množiny a nechť F : X × Y → R je funkce. Jestliže [x∗ , y ∗ ] ∈ X × Y a [x∗∗ , y ∗∗ ] ∈ X × Y jsou sedlové body funkce F , pak body [x∗ , y ∗∗ ] a [x∗∗ , y ∗ ] jsou také sedlové a navíc platí F (x∗ , y ∗ ) = F (x∗ , y ∗∗ ) = F (x∗∗ , y ∗ ) = F (x∗∗ , y ∗∗ ).

14

Úvod do teorie her

2 Maticové hry

Důkaz Víme, že body [x∗ , y ∗ ] a [x∗∗ , y ∗∗ ] jsou sedlové, tedy F (x, y ∗ ) ≤ F (x∗ , y ∗ ) ≤ F (x∗ , y) a F (x, y ∗∗ ) ≤ F (x∗∗ , y ∗∗ ) ≤ F (x∗∗ , y) pro každé x ∈ X a každé y ∈ Y . Odtud plyne, že F (x∗∗ , y ∗ ) ≤ F (x∗ , y ∗ ) ≤ F (x∗ , y ∗∗ ) ≤ F (x∗∗ , y ∗∗ ) ≤ F (x∗∗ , y ∗ ). Tudíž F (x∗∗ , y ∗ ) = F (x∗ , y ∗ ) = F (x∗ , y ∗∗ ) = F (x∗∗ , y ∗∗ ) = F (x∗∗ , y ∗ ). Máme dokázat, že body [x∗ , y ∗∗ ] a [x∗∗ , y ∗ ] jsou sedlové. Na základě předchozího a protože body [x∗ , y ∗ ] a [x∗∗ , y ∗∗ ] jsou sedlové, platí F (x, y ∗∗ ) ≤ F (x∗∗ , y ∗∗ ) = F (x∗ , y ∗∗ ) = F (x∗ , y ∗ ) ≤ F (x∗ , y) a F (x, y ∗ ) ≤ F (x∗ , y ∗ ) = F (x∗∗ , y ∗ ) = F (x∗∗ , y ∗∗ ) ≤ F (x∗∗ , y) pro každé x ∈ X a každé y ∈ Y . Tedy body [x∗ , y ∗∗ ] a [x∗∗ , y ∗ ] jsou také sedlové.



Z této věty vyplývá, že hodnota výplatní funkce F v sedlovém bodě je určena jednoznačně. Definice 2.6 Má-li antagonistická hra dvou hráčů sedlový bod, potom hodœ notu výplatní funkce F v sedlovém bodě nazýváme hodnotou hry. Poznámka 6 Hodnota hry se nazývá také cenou hry. Nyní se již dostáváme k maticovým hrám. Pouze připomeneme, že konečnou hrou rozumíme hru, v níž jsou prostory strategií konečné množiny. To v případě hry dvou hráčů znamená, že X = {1, . . . , m} a Y = {1, . . . , n}. Definice 2.7 Maticovou hrou rozumíme konečnou hru dvou hráčů s nulovým součtem. 15

Úvod do teorie her

2 Maticové hry

Připomeneme, co rozumíme pojmem matice. Definice 2.8 Maticí reálných čísel typu m × n rozumíme zobrazení {1, . . . , m} × {1, . . . , n} −→

A: A:

[i, j]

Matici také můžeme zaznamenat tabulkou  a a12 · · ·  11  a21 a22 · · ·  A= . ..  .. . ···  am1 am2 · · ·

R,

7−→ aij .

a1n



a2n .. .

   .  

amn

V případě maticové hry tedy výplatní funkce F : X × Y → R splývá s pojmem matice. To znamená, že výplaty prvního hráče lze zaznamenat jako matici A = (aij ) , kde aij = F (i, j). Nyní ale vzniká otázka. Otázka 3 Jak najít sedlový bod maticové hry? Jak zjistit, zda sedlový bod maticové hry existuje? Sedlový bod maticové nalezneme následujícím postupem: 1. postupně procházíme všechny řádky matice A a v daném řádku i určíme minimum, tj. min aij , j

resp.

min F (x, y), y∈Y

2. z takto získaných minim vybereme maximum, tj. max min aij , i

j

resp.

max min F (x, y); x∈X y∈Y

3. dále postupně procházíme všechny sloupce matice A a v daném sloupci j určíme maximum, tj. max aij , i

resp. 16

max F (x, y), x∈X

Úvod do teorie her

2 Maticové hry

4. z takto získaných maxim vybereme minimum, tj. min max aij , j

resp.

i

min max F (x, y). y∈Y x∈X

5. Jestliže nastává rovnost min max a max min, tj. max min aij = min max aij , i

j

j

i

resp. max min F (x, y) = min max F (x, y), x∈X y∈Y

y∈Y x∈X

pak sedlový bod existuje a nalezneme jej v průsečících řádků a sloupců, v nichž tato rovnost nastává. 6. Jestliže rovnost nenastává, tj. platí max min aij < min max aij , i

j

j

i

resp. max min F (x, y) < min max F (x, y), x∈X y∈Y

y∈Y x∈X

pak sedlový bod neexistuje. Příklad 2.1 Mějme matici 

1 2 7



  . A= 4 3 5   8 1 9 Naším úkolem je zjistit, zda existuje sedlový bod, a pokud ano, určit jej. 1. Ve všech řádcích matice A určíme minimum: min a1j = 1, j

min a2j = 3, j

min a2j = 1, j

2. z těchto dvou minim určíme maximum: maxi minj aij = 3, 3. dále ve všech sloupcích matice A určíme maximum: max ai1 = 8, i

max ai2 = 3, i

17

max ai2 = 9, i

Úvod do teorie her

2 Maticové hry

4. z těchto dvou maxim určíme minimum: minj maxi aij = 3, 5. nyní už vidíme, že sedlový bod matice A existuje a jeho hodnota je rovna 3, neboť max min aij = 3 = min max aij . i

j

j

i

//

Příklad 2.2 Mějme matici A=

1 −1 −1

! .

1

Naším úkolem je zjistit, zda existuje sedlový bod, a pokud ano, určit jej. 1. V obou řádcích matice A určíme minimum: min a1j = −1, j

min a2j = −1, j

2. z těchto dvou minim určíme maximum: maxi minj aij = −1, 3. dále v obou sloupcích matice A určíme maximum: max ai1 = 1, i

max ai2 = 1, i

4. z těchto dvou maxim určíme minimum: minj maxi aij = 1, 5. nyní už vidíme, že sedlový bod matice A neexistuje, neboť max min aij = −1 6= 1 = min max aij . i

j

j

i

//

18

Úvod do teorie her

2 Maticové hry

Jak si pozorný čtenář jistě všimnul, v předchozím příkladě nastala zvláštní situace, že max min aij < min max aij . i

j

j

i

Podle následující věty vždy platí nerovnost max min aij ≤ min max aij . i

j

j

i

Věta 2.3 Nechť F : X × Y → R je funkce. Pak sup inf F (x, y) ≤ inf sup F (x, y). x∈X y∈Y

y∈Y x∈X

Důkaz Z vlastností suprema a infima víme, že pro každé x¯ ∈ X a každé y¯ ∈ Y platí inf F (¯ x, y) ≤ F (¯ x, y¯) ≤ sup F (x, y¯). y∈Y

x∈X

Odtud pak plyne, že pro každé x ∈ X a každé y ∈ Y platí inf F (x, y) ≤ sup F (x, y), y∈Y

x∈X

ekvivalentně sup inf F (x, y) ≤ inf sup F (x, y). x∈X y∈Y

y∈Y x∈X

 Následující věta podává charakteristiku sedlového bodu funkce F . Věta 2.4 Nechť F : X × Y → R je funkce a nechť bod [x∗ , y ∗ ] ∈ X × Y je zvolen libovolně. Potom následující dva výroky jsou ekvivalentní: 1. bod [x∗ , y ∗ ] je sedlovým bodem funkce F , 2. platí max inf F (x, y) = inf F (x∗ , y) = F (x∗ , y ∗ ) = sup F (x, y ∗ ) = min sup F (x, y). x∈X y∈Y

y∈Y

x∈X

19

y∈Y x∈X

Úvod do teorie her

2 Maticové hry

Poznámka 7 To znamená, že funkce inf y∈Y F (x, y) nabývá svého maxima na množině X v bodě x∗ a že funkce supx∈X F (x, y) nabývá svého minima na množině Y v bodě y ∗ . Důkaz 2. ⇒ 1. Podle předpokladu víme, že sup F (x, y ∗ ) = F (x∗ , y ∗ ) = inf F (x∗ , y), x∈X

y∈Y

a tudíž F (x, y ∗ ) ≤ sup F (x, y ∗ ) = F (x∗ , y ∗ ) = inf F (x∗ , y) ≤ F (x∗ , y) x∈X

y∈Y

pro každé x ∈ X a každé y ∈ Y , což znamená, že bod [x∗ , y ∗ ] je sedlový. 1. ⇒ 2. Podle předpokladu, protože bod [x∗ , y ∗ ] je sedlový, platí F (x, y ∗ ) ≤ F (x∗ , y ∗ ) ≤ F (x∗ , y) pro každé x ∈ X a každé y ∈ Y neboli sup F (x, y ∗ ) ≤ F (x∗ , y ∗ ) ≤ inf F (x∗ , y), x∈X

y∈Y

a tudíž inf sup F (x, y) ≤ sup F (x, y ∗ ) ≤ F (x∗ , y ∗ ) ≤ inf F (x∗ , y) ≤ sup inf F (x, y). y∈Y x∈X

x∈X

y∈Y

x∈X y∈Y

Ovšem nerovnost supx∈X inf y∈Y F (x, y) ≤ inf y∈Y supx∈X F (x, y) platí podle předcházející věty 2.3. Platí tedy rovnost inf sup F (x, y) = sup F (x, y ∗ ) = F (x∗ , y ∗ ) = inf F (x∗ , y) = sup inf F (x, y). y∈Y x∈X

x∈X

y∈Y

x∈X y∈Y

Vidíme, že infimum funkce supx∈X F (x, y) resp. supremum funkce inf y∈Y F (x, y) se nabývá v bodě y ∗ resp. x∗ jako minimum resp. maximum. Dohromady doœ stáváme, že max inf F (x, y) = inf F (x∗ , y) = F (x∗ , y ∗ ) = sup F (x, y ∗ ) = min sup F (x, y). x∈X y∈Y

y∈Y

x∈X

y∈Y x∈X

 20

Úvod do teorie her

2 Maticové hry

Cvičení 2.1 Postupem z odpovědi na otázku 3 rozhodněte, zda maticová hra zadaná maticí



9 1 8 3



   4 3 5 7    5 2 2 3 má sedlový bod, a určete jej. Cvičení 2.2 Postupem z odpovědi na otázku 3 rozhodněte, zda maticová hra zadaná maticí



9 1 8 3



   4 3 5 3    5 3 2 3 má sedlový bod, a určete jej. Cvičení 2.3 Postupem z odpovědi na otázku 3 rozhodněte, zda maticová hra zadaná maticí



1 2 3 4



   2 3 4 1    3 4 1 2 má sedlový bod, a určete jej.

2.1

Příklady maticových her

V této podkapitole uvedeme základní příklady maticových her. Příklad 2.3 (Blotto hry) 1. Vojenská interpretace: • Jedná se o hru dvou generálů, z nichž každý má k dispozici a resp. b jednotek. Bojují o n území o hodnotách v1 , . . . , vn tak, že každý z nich na dané území vyšle určitý počet jednotek. Ten, který pošle jednotek více, dané území získá, v případě shody se území dělí naœ půl. 21

Úvod do teorie her

2 Maticové hry

Formálně se hra zavádí takto: • množina hráčů N = {1, 2}, • prostory strategií M1 = {x ∈ Rn ; x1 + · · · + xn = a, x1 , . . . , xn ≥ 0, x1 , . . . , xn ∈ N0 }, M2 = {y ∈ Rn ; y1 + · · · + yn = b, y1 , . . . , yn ≥ 0, y1 , . . . , yn ∈ N0 }, • výplatní funkce:

F1 (x, y) =

n X i=1

F2 (x, y) =

    vi jestliže xi > yi

vi jestliže xi = yi 2    0 jestliže x < y i i

  vi jestliže yi > xi n   X i=1

vi jestliže yi = xi 2    0 jestliže y < x i i

Jedná se o hru s konstantním součtem. Lze ji převést na hru s nuœ lovým součtem. Tato hra obecně nemá sedlový bod. 2. Ekonomická interpretace – aukce obálkovou metodou: • Hráči jsou dva investoři, z nichž každý má k dispozici a resp. b peněžních prostředků. • V aukci je n budov o hodnotách v1 , . . . , vn . • Investor napíše svou peněžní nabídku za jednotlivé budovy na papír, který zalepí do obálky. Obálku doručí komisi, která obálky rozlepí a danný objekt připadne tomu, kdo za něj nabídl více peněz, v případě rovnosti rozhodne los. 3. Získání zakázek na trzích: • Hráči jsou dvě firmy, které se ucházejí o zakázky na n trzích. • Na těchto trzích je možné získat zakázky o hodnotách v1 , . . . , vn . • Výši získaných zakázek lze ovlivnit vynaložením peněz na propagaci. 22

Úvod do teorie her

2 Maticové hry

• První resp. druhá firma má k dispozici a resp. b peněžních proœ středků určených na propagaci. • Zakázky na daném trhu se rozdělí mezi firmy v tom poměru, v jakém na daném trhu investovaly do propagace. //

Příklad 2.4 (Hide and attack (napadení konvoje)) • Za druhé světové války byla Velká Británie zásobována konvoji lodí z USA přes Atlantik. Německé ponorky se snažily konvoj potopit. • Konvoj může volit svou trasu (např. A, B nebo C), přičemž ponorky mohou čekat na různých místech (A, B nebo C). • V případě, že se minou, konvoj dopluje, pokud se potkají, je konvoj poškozen. • Výplatní matice hry (kde číslo pi , 0 ≤ pi ≤ 1, znamená míru poškození konvoje): konvoj A

B

C

p1

0

0

B

0 p2

0

C

0

A ponorky

0 p3

• Jedná se o diagonální matici. • Nemá sedlový bod. //

23

Úvod do teorie her

2 Maticové hry

Příklad 2.5 (Prstová hra Morra) • Tato hra má dlouhou tradici. Pochází z antiky a v Itálii je populární dodnes. • Hrají dva hráči. • Oba hráči ve stejném okamžiku ukáží určitý počet prstů 1, . . . , n a vysloví číslo 1, . . . , n udávající počet prstů, které si myslí, že protihráč ukáže. • V případě, že oba hráči hádají správně nebo oba špatně, výplaty jsou nulové. • V opačném případě hráč, který hádal špatně, zaplatí protihráči tolik zápalek, kolik činí součet ukázaných prstů. • Výplatní matice (pro n = 2, kde a/b znamená, že hráč ukazuje a a b prstů hádá): 2. hráč 1/1

1/2

2/1

2/2

1/1

0

2

−3

0

1/2

−2

0

0

3

2/1

3

0

0

−4

2/2

0

3

−4

0

1. hráč

//

24

Úvod do teorie her

2 Maticové hry

Příklad 2.6 (Model protivzdušné obrany) • Za druhé světové války probíhaly nálety na města pomocí bombardérů. Tato města se proti těmto náletům bránila stíhačkami. • Hráči jsou velitel bombardérů, který chce provést nálet na město, a velitel stíhaček, který chce město ubránit. • Velitel bombardérů se může rozhodnout, zda provede nálet v malé nebo velké výšce. • Velitel stíhaček se může rozhodnout, zda bude očekávat nálet v malé nebo velké výšce. • Úspěšnost náletu (resp. obrany) závisí na tom, zda se bombardéry a stíhačky potkají ve stejné výšce. • Matice hry (pro úspěšnost náletu): stíhačky vysoko nízko vysoko

10 %

70 %

nízko

100 %

40 %

bombardéry

• Tato hra nemá sedlový bod. //

Příklad 2.7 (Operace zraněného) • Do nemocnice přivezli zraněného. • Zranění může být X, Y nebo Z. Na přesné vyšetření není čas. • Lékaři mohou operovat způsobem A nebo B. 25

Úvod do teorie her

2 Maticové hry

• Uspěšnost zákroku: příroda X

Y

Z

A

70 % 50 %

60 %

B

60 % 30 % 100 %

lékaři

• V tomto případě jde o rozhodování za nejistoty, neboť neznáme (nebylo uvedeno) rozdělení pravděpodobnosti, jímž se výskyt jevů X, Y nebo Z řídí. Kdybychom toto rozdělení znali, hovořili bychom o rozhodování při riziku. V obou případech jde o takzvané hry proti přírodě, která je doœ plněna jako druhý hráč bez výplatní funkce. • Jeden z možných způsobů jejího řešení je ji jako antagonistickou hru pojmout, pak hledáme sedlový bod. • Obecněji lze použít princip minimaxu, kdy hledáme max min F (x, y). x∈X y∈Y

//

2.2

Smíšené rozšíření maticových her

Mějme maticovou hru s maticí hry A ∈ Rm×n , s prostory strategií X = {1, . . . , m} a Y = {1, . . . , n} a s výplatní funkcí F (i, j) = aij . Tato maticová hra nemusí mít sedlový bod. Tuto situaci řešíme tak, že budeme uvažovat smíšené rozšíření této maticové hry.

26

Úvod do teorie her

2 Maticové hry

Definice 2.9 Smíšeným rozšířením maticové hry s maticí hry A ∈ Rm×n rozumíme hru s prostory strategií ¯ = {x ∈ Rm ; x> e = 1, x ≥ 0} X a Y¯ = {y ∈ Rn ; f > y = 1, y ≥ 0}, kde e je vektor m jedniček a f je vektor n jedniček, a výplatní funkcí F¯ (x, y) = x>Ay =

m X n X

xi aij yj .

i=1 j=1

Poznámka 8 Smíšené rozšíření v sobě vždy obsahuje původní hru: čistým strategiím i ∈ X = {1, . . . , m} resp. j ∈ Y = {1, . . . , n} odpovídají kanonické jednotkové vektory ei resp. fj . Vektor ei resp. fj má celkem m resp. n složek, a to jedničku na i-tém resp. j-tém místě a nuly na ostatních m − 1 resp. n − 1 místech. Lemma 2.1 Sedlový bod smíšeného rozšíření maticové hry se nezmění, jestliže ke všem prvkům matice A přičteme stejnou konstantu c. Důkaz Nechť [x∗ , y ∗ ] je sedlový bod smíšeného rozšíření maticové hry, tedy ¯ a každé y ∈ Y¯ platí pro každé x ∈ X x>Ay ∗ ≤ x∗ >Ay ∗ ≤ x∗ >Ay. Naším úkolem je dokázat, že x> (A + cE)y ∗ ≤ x∗ > (A + cE)y ∗ ≤ x∗ > (A + cE)y, kde E ∈ Rm×n je matice samých jedniček. ¯ a y¯ ∈ Y¯ platí Pro libovolné x¯ ∈ X x¯> (A + cE)¯ y = x¯>A¯ y + c¯ x> E y¯ = P Pn = x¯>A¯ y+c m i=1 j=1 xi 1yj = P P m = x¯>A¯ y + c i=1 xi nj=1 yj = = x¯>A¯ y + c, 27

(4)

Úvod do teorie her

2 Maticové hry

tedy máme dokázat, že x>Ay ∗ + c ≤ x∗ >Ay ∗ + c ≤ x∗ >Ay + c, což ale plyne ze vztahu (4) přičtením konstanty c.



¯ × Y¯ je sedlovým bodem smíšeného rozšíření Lemma 2.2 Bod [x∗ , y ∗ ] ∈ X maticové hry s maticí A a v = x∗ >Ay ∗ je hodnota hry právě tehdy, když jsou splněny soustavy Ay ∗ ≤ ev

vf > ≤ x∗ >A.

a

Důkaz Nejdříve ukážeme směr zleva doprava. Mějme sedlový bod [x∗ , y ∗ ]. ¯ a každé y ∈ Y¯ platí Tedy víme, že pro každé x ∈ X x>Ay ∗ ≤ x∗ >Ay ∗ ≤ x∗ >Ay. Tato nerovnost platí i pro jednotkové vektory x = e1 , . . . , em , tj.  ∗ ∗> ∗  e> Ay ≤ x Ay = v  1  .. Ay ∗ ≤ ev. .   e> Ay ∗ ≤ x∗ >Ay ∗ = v  m

Analogicky pro jednotkové vektory y = f1 , . . . , fn platí  v = x∗ >Ay ∗ ≤ x∗ >Af1    .. vf > ≤ x∗ >A. .   v = x∗ >Ay ∗ ≤ x∗ >Af  n

Nyní ukážeme směr zprava doleva. Víme, že platí nerovnosti Ay ∗ ≤ ev

vf > ≤ x∗ >A,

a

neboli ∗ e> ≤ v, 1 Ay .. . ∗ e> ≤ v, m Ay

28

(5)

Úvod do teorie her

2 Maticové hry

a v ≤ x∗ >Af1 , .. .

(6)

v ≤ x∗ >Afn . ¯ a každé y ∈ Y¯ platí Máme dokázat, že pro každé x ∈ X x>Ay ∗ ≤ v ≤ x∗ >Ay, ¯ o složkách x1 , . . . , xm , pak vynásobením a že v = x∗ >Ay ∗ . Nechť je dáno x ∈ X nerovnic (5) tímto x, tj. i-tou nerovnici násobíme číslem xi , získáme ∗ x1 e> 1 Ay

≤ x1 v, .. .

∗ ≤ xm v, xm e> m Ay

po sečtení m X

∗ xi e> i Ay

≤

i=1

m X

xi v,

i=1

ekvivalentně x>Ay ∗ ≤ v. Analogicky nechť je dáno y ∈ Y¯ o složkách y1 , . . . , yn , pak vynásobením neœ rovnic (6) tímto y, tj. j-tou nerovnici násobíme číslem yj , získáme vy1 ≤ x∗ >Af1 y1 , .. . vyn ≤ x∗ >Afn yn , po sečtení v

n X

yj ≤ x∗ >A

j=1

n X

fj yj ,

j=1

ekvivalentně v ≤ x∗ >Ay. Tedy získáváme, že x>Ay ∗ ≤ v ≤ x∗ >Ay ¯ a všechna y ∈ Y¯ . Volbou x = x∗ a y = y ∗ dostáváme pro všechna x ∈ X x∗ >Ay ∗ ≤ v ≤ x∗ >Ay ∗ , tedy v = x∗ >Ay ∗ . 29



Úvod do teorie her

2 Maticové hry

Nyní můžeme vyslovit hlavní větu maticových her. Věta 2.5 (hlavní maticových her). Smíšené rozšíření maticové hry má vždy alespoň jeden sedlový bod. Důkaz Mějme dánu maticovou hru s maticí hry A ∈ Rm×n . Máme dokázat, ¯ × Y¯ takový, že pro každé x ∈ X ¯ a každé y ∈ Y¯ že existuje bod [x∗ , y ∗ ] ∈ X platí x>Ay ∗ ≤ x∗ >Ay ∗ ≤ x∗ >Ay. Podle lemmatu 2.1 se sedlový bod nezmění, když ke všem prvkům matice A přičteme stejnou konstantu c > 0. Bez újmy na obecnosti budeme předpokládat, že již A > 0. ¯ y ∗ ∈ Y¯ a v ∈ R tak, aby platilo Pak podle lemmatu 2.2 stačí nalézt x∗ ∈ X, Ay ∗ ≤ ev

vf > ≤ x∗ >A.

a

Budou-li uvedené soustavy platit, bude nutně v > 0. Číslem v tedy můžeme dělit a dostáváme

Ay ∗ ≤e v Nyní provedeme substituci p∗ =

y∗ v

f> ≤

a

a

q∗ =

x∗ >A . v x∗ . v

Naším úkolem je nyní vyřešit následující soustavy: Ap∗ ≤ e, p∗ ≥ 0

q ∗ >A ≥ f >

a

q∗

≥ 0

a

f > p∗ = q ∗ > e.

Budeme tedy řešit následující úlohy lineárního programování (P ) max f > p

(D) min q > e q >A ≥ f >

Ap ≤ e p ≥ 0

q

≥ 0.

Obě úlohy (P ) a (D) jsou přípustné – v úloze (P ) stačí uvažovat např. bod p = 0 a v úloze (D) stačí uvažovat např. bod q = eK pro K → +∞ – a podle 30

Úvod do teorie her

2 Maticové hry

věty o existenci optimálních řešení mají obě úlohy optimální řešení p∗ a q ∗ . Podle principu duality platí, že f > q ∗ = q ∗ > e, a zřejmě platí, že f > p∗ = q ∗ > e > 0. (Jistě je f > p∗ = q ∗ > , neboť p∗ ≥ 0 i q ∗ ≥ 0, e ≥ 0. Kdyby q ∗ > e = 0, muselo by být q ∗ = 0, což není možné.) Stačí tedy položit v=

1 1 = ∗> > ∗ f p q e

a

x∗ = q ∗ v, y ∗ = p∗ v.

Pak bod [x∗ , y ∗ ] je sedlovým bodem zadané maticové hry.



Cvičení 2.4 Napište smíšené rozšíření hry modelu protivzdušné obrany (viz příklad 2.6 ).

2.3

Symetrické hry

Tato podkapitola se zabývá speciálním druhem hry dvou hráčů s nulovým součtem. Tato hra je speciální v tom, že oba hráči mají stejné prostory strategií a antisymetrické výplatní funkce. Nyní symetrickou hru zavedeme formálně. Definice 2.10 Hra dvou hráčů s nulovým součtem se nazývá symetrická právě tehdy, když prostory strategií splývají, tj. X = Y , a výplatní funkce je antisyœ metrická, tj., pro každé x ∈ X a každé y ∈ Y platí F (x, y) = −F (y, x). Poznámka 9 V případě maticové hry s maticí hry A ∈ Rm×n je hra symeœ trická právě tehdy, když je matice hry A antisymetrická, tj., platí, že m = n a A = −A> . Věta 2.6 Má-li symetrická hra sedlový bod [x∗ , y ∗ ], pak body [y ∗ , x∗ ], [x∗ , x∗ ] a [y ∗ , y ∗ ] jsou také sedlové a společná hodnota hry je rovna nule.

31

Úvod do teorie her

2 Maticové hry

Důkaz Pro sedlový bod platí, že F (x, y ∗ ) ≤ F (x∗ , y ∗ ) ≤ F (x∗ , y), tudíž −F (y ∗ , x) ≤ −F (y ∗ , x∗ ) ≤ −F (y, x∗ ), F (y, x∗ ) ≤

F (y ∗ , x∗ ) ≤

F (y ∗ , x),

tedy bod [y ∗ , x∗ ] je sedlovým bodem a podle věty 2.2 o sedlových bodech jsou body [x∗ , x∗ ] a [y ∗ , y ∗ ] také sedlovými. Dále platí, že F (x∗ , y ∗ ) = F (y ∗ , x∗ ) = −F (x∗ , y ∗ ), a tedy F (x∗ , y ∗ ) = 0. 

2.4

Dominování v maticových hrách

Dominování v maticových hrách nám umožňuje zmenšit matici hry v případě, že se v této matici vyskytují řádky resp. sloupce, které odpovídají strategiím, které si žádný z hráčů nezvolí. Mějme maticovou hru s maticí hry 

···

a1n



  a21 a22 · · ·  A= . ..  .. . ···  am1 am2 · · ·

a2n .. .

   .  

a11

a12

amn

Pak 1. první hráč se snaží maximalizovat svou výhru, tedy pokud ai 1 j ≤ ai 2 j pro nějaká i1 , i2 a pro každé j = 1, . . . , n, lze řádek i1 vynechat a zmenšit tak matici A, 32

Úvod do teorie her

2 Maticové hry

2. druhý hráč se snaží minimalizovat svou prohru, tedy pokud aij1 ≤ aij2 pro nějaká j1 , j2 a pro každé i = 1, . . . , m, lze sloupec j2 vynechat a zmenšit tak matici A. Definice 2.11 Říkáme, že řádek i1 z předchozího odstavce je dominován řádœ kem i2 , a sloupec j2 z předchozího odstavce je dominován sloupcem j1 . Uvedený postup lze po zmenšení matice A opakovat. Definice 2.12 (obecněji) Uvažujeme-li smíšené rozšíření, pak 1. řádek i1 je dominován konvexní kombinací ostatních řádků, existují-li čísla x1 , . . . , xi1 −1 , xi1 +1 , . . . , xm ≥ 0 taková, že x1 + · · · + xi1 −1 + xi1 +1 + · · · + xm = 1 a ai 1 j ≤

m X

xi aij

i=1 i6=i1

pro každé j, 2. sloupec j2 je dominován konvexní kombinací ostatních sloupců, existují-li čísla y1 , . . . , yj2 −1 , yj2 +1 , . . . , yn ≥ 0 taková, že y1 + · · · + yj2 −1 + yj2 +1 + · · · + yn = 1 a

n X

aij yj ≤ aij2

j=1 j6=j2

pro každé i. Příklad 2.8 V matici hry 



1 2 3    4 5 6    7 8 9 je druhý a třetí sloupec dominován prvním sloupcem (lze je vynechat), první a druhý řádek je dominován třetím řádkem (lze je vynechat). Zůstává matice typu 1 × 1 obsahující pouze prvek 7. Matice A má sedlový bod – průsečík třetího řádku a prvního sloupce – a hodnta hry je 7. 33

//

Úvod do teorie her

2 Maticové hry

Příklad 2.9 V matici hry 



1 9 1 10    7 7 7 11    9 1 9 12 je čtvrtý sloupec dominován např. třetím sloupcem (resp. libovolnou konvexní kombinací prvních tří sloupců; čtvrtý sloupec lze vynechat) a druhý řádek je dominován např. aritmetickým průměrem prvního a třetího řádku (lze jej vynechat).

//

Cvičení 2.5 Zmenšete matici hry 



0 0 0 3    A=  0 1 0 1  1 0 1 1

vynecháním dominovaných řádku a sloupců.

Cvičení 2.6 Zmenšete matici hry 

2 4 4 6



   A= 3 7 8 9   1 2 0 3 vynecháním dominovaných řádku a sloupců. Uvažujte smíšené rozšíření.

2.5

Vztah maticových her a úloh lineárního programování

Z hlavní věty maticových her (viz věta 2.5 ) víme, že řešením úloh lineárního programování lze nalézt sedlový bod smíšeného rozšíření maticové hry. Otázka 4 Lze nalezením sedlového bodu vyřešit úlohy lineárního programoœ vání? 34

Úvod do teorie her

2 Maticové hry

Mějme úlohy lineárního programování. (P ) max c> x

(D) min y > b y >A ≥ c>

Ax ≤ b x ≥ 0

y

≥ 0.

Věta 2.7 Nechť (¯ x, y¯, z¯) je rovnovážný vektor ve hře s maticí hry   0 −A> c    A . 0 −b   > > −c b 0 Jestliže z¯ > 0, potom x∗ = x¯/¯ z , a y ∗ = y¯/¯ z jsou optimální řešení úloh (P ) a (D). Věta 2.8 Nechť x∗ a y ∗ jsou optimální řešení úloh (P ) a (D). Potom (¯ x, y¯, z¯) je rovnovážný vektor ve hře s maticí hry   > 0 −A c    A 0 −b  ,  −c> b> 0 kde x¯ = x∗ z¯,

y¯ = y ∗ z¯

a

z¯ =

1 . 1 + e > x∗ + y ∗ > f

Důkazy obou vět jsou velice snadné. Dokazují se pomocí lemmatu 2.2 Příklad 2.10 Uvažujme úlohy lineárního programování (P ) max 8x + 6y

(D) min 12u + 10v

3x + 4y ≤ 12 ,

3u + 5v ≥ 8 ,

5x + 2y ≤ 10 ,

4u + 2v ≥ 6 ,

x, y ≥ 0 ,

u, v ≥ 0 .

Poměrně snadno určíme, že optimální řešení uvedených úloh jsou x∗ =

8 , 7

y∗ =

15 7

a 35

u∗ = 1 ,

v∗ = 1 .

Úvod do teorie her

2 Maticové hry

čtenář nechť ihned ověří optimalitu obou řešení užitím věty o slabé dualitě (přípustnost řešení a rovnost hodnot cílových funkcí)! Výše uvedeným úlohám (P ) a (D) odpovídá symetrická hra s maticí hry   0 0 −3 −5 8    0  0 − 4 − 2 6     A˜ =  3 4 0 0 −12 .    5  2 0 0 −10   −8 −6 12 10 0 Podle věty 2.8 určíme hodnotu 1 7 1 = = z¯ = 8 15 ∗ ∗ ∗ ∗ 1+x +y +u +v 44 1+ 7 + 7 +1+1 a další hodnoty 8 x¯ = x∗ z¯ = , 44 Tedy vektor

y¯ = y ∗ z¯ =

15 , 44

u¯ = u∗ z¯ =

7 , 44

v¯ = v ∗ z¯ =

7 . 44

    8/44 x¯     y¯ 15/44         u¯ =  7/44     v¯  7/44     7/44 z¯ ˜ čtenář je vektorem rovnovážných smíšených strategií ve hře s maticí hry A. nechť tuto skutečnost ihned ověří řešením soustav podle lemmatu 2.2 ! Obráceně, víme-li, že 

 8/44   15/44      7/44    7/44   7/44 ˜ potom je vektorem rovnovážných smíšených strategií ve hře s maticí hry A, položíme z¯ = 7/44 (poslední souřadnice vektoru) a, protože z¯ > 0, podle věty 2.7 určíme řešení úloh (P ) a (D) takto: x∗ =

x¯ 8 = , z¯ 7

y∗ =

y¯ 15 = , z¯ 7

u∗ = 36

u¯ = 1, z¯

v∗ =

v¯ = 1. z¯

Úvod do teorie her

2 Maticové hry

čtenář ověří, že řešení jsou přípustná a optimální (porovnáním hodnot cílových funkcí v těchto řešeních).

//

Korespondenční úkol 1 Vypočtěte rovnovážné smíšené strategie prstové hry Morra.

37

Úvod do teorie her

3

3 Dvojmaticové hry

Dvojmaticové hry a obecné hry n hráčů ve strategickém tvaru

3.1. Další příklady dvojmaticových her . . . . . . . . . . . . . . . . . . . . . . . . 40 3.2. Smíšené rozšíření dvojmaticové hry . . . . . . . . . . . . . . . . . . . . . . . 41 3.3. Kompaktní metrické prostory . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.4. Heineho-Borelova pokrývací věta . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.5. Spernerovo lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.6. Brouwerova věta o pevném bodě . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.7. Věta Nikaidô-Isody . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

Klíčová slova Dvojmaticová hra, vězňovo dilema, smíšené rozšíření, simplex, barycentrické souřadnice, Spernerovo lemma, pevný bod, Brouwerova věta o pevném bodě, konvexní hra, věta Nikaidô-Isody.

S příkladem dvojmaticové hry jsme se setkali již ve cvičeni 1.1 na konci úvodní kapitoly. Pojem dvojmaticové hry je obecnější než pojem hry maticové v tom smyslu, že každá maticová hra je zároveň hrou dvojmaticovou. Na rozdíl od maticových her vztah hráčů ve dvojmaticové hře nemusí být antagonistický, tj., výhra jednoho hráče nemusí znamenat prohru druhého hráče. Může tedy dojít například ke smírnému řešení, kdy každý z hráčů vyhraje, nebo k situaci, v níž oba hráči prohrají.

Uvedený jev ilustrujeme pomocí následujícího příkladu. Příklad 3.1 (Vězňovo dilema) Předpokládejme, že dva lupiči byli dopadeni po zločinu a nyní jsou vyslýchání, přičemž každý z nich může postupovat jedním z následujících způsobů: 38

Úvod do teorie her

3 Dvojmaticové hry

1. přizná se (P), 2. bude zapírat (Z). Pak důsledky jednotlivých rozhodnutí obou lupičů můžeme zaznamenat do následující tabulky: 2. hráč

P

P

Z

−5 −5

10 −10

1. hráč Z

−10

10

5

5

Dvojicí rovnovážných strategií je poněkud překvapivě [P, P], ačkoliv pro oba účastníky by bylo výhodnější volit [Z, Z].

//

Nyní formálně zavedeme definici dvojmaticových her. Definice 3.1 Dvojmaticovou hrou rozumíme konečnou hru dvou hráčů.

Poznámka 10 Dvojmaticová hra je tedy zadána množinou dvou hráčů N = {1, 2}, prostory strategií X = {1, . . . , m} a Y = {1, . . . , n} a výplatními funkœ cemi F1 , F2 : X × Y → R. S ohledem na definici 2.8 vidíme, že výplatní funkce F1 a F2 splývají s pojmem matice. To znamená, že výplaty prvního resp. druœ hého hráče lze zaznamenat jako matici A = (aij )

resp.

kde aij = F1 (i, j) resp. bij = F2 (i, j).

39

B = (bij ) ,

Úvod do teorie her

3.1

3 Dvojmaticové hry

Další příklady dvojmaticových her

Příklad 3.2 (Manželský spor) V manželském páru probíhá spor o trávení společného volného času. Manželka má zájem predevším o kulturu (K), kdežto manžel převážne o sport (S). V případě, že se oba hráči zúčastní kulturní akce, manžel bude mít nižší užitek. V opačném případě, kdy se zúčastní akce sportovní, má nižší užitek manželka. Dalším řešením je rozdělení manželů, kdy se každý zúčastní akce, která jej zajímá, přičemž tato situace má za následek rozladění účastníků a žádný užitek. Situaci shrnuje následující tabulka. manžel K

S

K

2 1

0 0

S

0 0

1 2

manželka

Dvojice [K, K] a [S, S] zřejmě tvoří rovnovážné strategie. Jak se ale hráči mezi těmito strategiemi rozhodnou, v případě nekooperativním záleží pouze na nich a v rámci čistých strategií jim nelze poskytnout žádný racionální návod k jednání.

//

Příklad 3.3 (Konflikt typu kuřata) Dva mladíci se baví tím, že se proti sobě rozjedou v autech středem vozovky a první z hráčů, který uhne (U), oproti druhému, který neuhne (N), ztratí prestiž. V případe, že oba mladíci zvolí strategii neuhnout, skončí zábava havárií. Situaci popisuje následující tabulka. 2. hráč U

N

U

0

N

5 −5

−5

0

5

1. hráč −100 −100

40

Úvod do teorie her

3 Dvojmaticové hry

Tato hra má opět dva rovnovážné body a to [N, U] a [U, N] a v rámci čistých strategií hráčům nelze poskytnout žádný racionální návod k jednání.

3.2

//

Smíšené rozšíření dvojmaticové hry

Mějme dvojmaticovou hru s maticemi A a B typu m × n. Z předchozích kaœ pitol víme, že hra nemusí mít bod Nashovy rovnováhy. V takovém případě využíváme tzv. smíšeného rozšíření. Definice 3.2 Smíšeným rozšířením dvojmaticové hry s maticemi A a B roœ zumíme hru s prostory strategií ¯ = {x ∈ Rm ; x> e = 1, x ≥ 0}, X Y¯ = {y ∈ Rn ; f> y = 1, y ≥ 0}, kde e resp. f je vektor m resp. n jedniček, a výplatními funkcemi F¯1 (x, y) = x> Ay a F¯2 (x, y) = x> By.

Věta 3.1 Smíšené rozšíření dvojmaticové hry má vždy alespoň jeden bod Nashovy rovnováhy.

Důkaz Tvrzení této věty je důsledkem věty Nikaidô-Isody, kterou uvedeme později.



Důkazy následujích dvou lemmat jsou snadné. Věta 3.2 se pak snadno dokáže pomocí obou lemat. Důkazy proto neuvádíme. Čtenář se může pokusit dokázat uvedená tvrzení samostatně.

41

Úvod do teorie her

3 Dvojmaticové hry

Lemma 3.1 Rovnovážný bod smíšeného rozšíření dvojmaticové hry se neœ změní, jestliže ke všem prvkům matice A resp. B přičteme stejnou konstantu c resp. d. ¯ Y¯ je nějaký bod z prostoru strategií. Položme Lemma 3.2 Nechť [x∗ , y ∗ ] ∈ X× u = x∗> Ay ∗

a

v = x∗> By ∗ .

Potom bod [x∗ , y ∗ ] je rovnovážným bodem právě tehdy, když Ay ∗ ≤ eu

x∗> B ≤ vf> .

a zároveň

Věta 3.2 Nechť A a B jsou matice typu m×n s kladnými členy, dále [x∗ , y ∗ ] je libovolný bod a u, v > 0 jsou libovolná čísla. Potom bod [x∗ , y ∗ ] je rovnovážným bodem a platí u = x∗> Ay ∗ a v = x∗> By ∗ právě tehdy, když pro vektory p = x∗ v1 a q = y ∗ u1 platí p> B ≤ f>

Aq ≤ e q ≥ 0

p

≥

0

q 6= 0

p

6=

0

za podmínek p> (Aq − e) = 0

(p> B − f> )q = 0.

Poznámka 11 Bod [p, q] řešící LCP (linear complementarity problem) uveœ dený v předchozí větě je ekvivalentně netriviálním řešením úlohy kvadratického programování:



p> q>



0 A+B 0

!

0

p q

! −



p> q>

e



o

!

  − o f>

za podmínek p> B ≤ f>

Aq ≤ e q

≥ 0

p

≥

q

6= 0

p

6= 0.

42

0

p q

! → max

Úvod do teorie her

3.3

3 Dvojmaticové hry

Kompaktní metrické prostory

Tato podkapitola se věnuje kompaktním metrickým prostorům a jejich vlastœ nostem nutným pro vyslovení Heineho-Borelovy pokrývací věty. Tu využijeme později v důkazu věty Nikaidô-Isody, která mj. zaručuje, že smíšené rozšíření dvojmaticové hry má alespoň jeden bod Nashovy rovnováhy.

Definice 3.3 Metrickým prostorem rozumíme dvojici (X, ρ), kde X je liboœ volná množina a ρ je metrika, tj. zobrazení ρ : X × X → R, které pro libovolná x, y, z ∈ X splňuje následující axiomy. 1. Axiom nezápornosti: ρ(x, y) ≥ 0. 2. Axiom totožnosti: ρ(x, y) = 0 ⇔ x = y. 3. Axiom symetrie: ρ(x, y) = ρ(y, x). 4. Trojúhelníková nerovnost: ρ(x, z) ≤ ρ(x, y) + ρ(y, z). Definice 3.4 Vzdáleností bodu x ∈ X od množiny K ⊆ X rozumíme ρ(x, K) = inf{ρ(x, k); k ∈ K}. Definice 3.5 Uzávěrem množiny K ⊆ X rozumíme množinu cl(K) = {x ∈ X; ρ(x, K) = 0}.

Definice 3.6 Podmnožinu K metrického prostoru X nazveme hustou právě tehdy, když jejím uzávěrem je celý metrický prostor.

Definice 3.7 Metrický prostor X nazveme separabilním právě tehdy, když má hustou spočetnou podmnožinu. 43

Úvod do teorie her

3 Dvojmaticové hry

Definice 3.8 Báze metrického prostoru je soustava otevřených množin taœ ková, že každou otevřenou množinu lze napsat jako stejdnocení prvků báze.

Věta 3.3 Nechť X je metrický prostor. Následující vlastnosti jsou ekvivaœ lentní. a) Metrický prostor X je separabilní. b) Metrický prostor X má spočetnou bázi. c) Z každého pokrytí metrického prostoru X otevřenými množinami lze vybrat spočetné podpokrytí.

Definice 3.9 Metrický prostor X se nazývá úplný, jestliže každá jeho cauchyœ ovská posloupnost je konvergentní.

Definice 3.10 Metrický prostor X se nazývá totálně omezený, jestliže ke kaœ ždému ε > 0 existuje konečná množina Kε ⊆ X taková, že pro každé x ∈ X platí ρ(x, Kε ) < ε.

Pozorování 1 Kompaktní metrický prostor je totálně omezený.

Pozorování 2 Každý totálně omezený metrický prostor je separabilní.

Věta 3.4 V totálně omezeném metrickém prostoru lze z každé posloupnosti vybrat posloupnost cauchyovskou.

Věta 3.5 Metrický prostor je kompaktní právě tehdy, když je úplný a totálně omezený.

44

Úvod do teorie her

3 Dvojmaticové hry

Definice 3.11 Bod x ∈ M je hromadným bodem podmnožiny M metrického prostoru (X, ρ) právě tehdy, když v každém okolí bodu x existuje bod y ∈ M takový, že y 6= x.

Pozorování 3 Metrický prostor (X, ρ) je kompaktní právě tehdy, když každá nekonečná množina má hromadný bod.

Definice 3.12 Nechť K je množina. Pak pokrytím množiny K rozumíme sysœ S tém množin {Gα ; α ∈ A} takový, že α∈A Gα ⊇ K. V případě, kdy jsou všechny množiny systému {Gα ; α ∈ A} otevřené, hovoříme o otevřeném pokrytí množiny K.

Definice 3.13 Nechť K je množina. Dále mějme otevřené pokrytí {Gα ; α ∈ A} této množiny. Pak konečným podpokrytím pokrytí {Gα ; α ∈ A} rozumíme systém množin {Gβ ; β ∈ B} takový, že B je konečná podmnožina množiny A a je sám pokrytím množiny K.

3.4

Heineho-Borelova pokrývací věta

V této části vyslovíme Heineho-Borelovu pokrývací větu, kterou využijeme při důkazu věty Nikaidô-Isody.

Věta 3.6 (Heineho-Borelova pokrývací) Metrický prostor (X, ρ) je komœ paktní právě tehdy, když z každého jeho otevřeného pokrytí lze vybrat konečné podpokrytí.

45

Úvod do teorie her

3 Dvojmaticové hry

Důkaz U obou směrů použijeme důkaz sporem. Předpokládejme, že metrický prostor není kompaktní. Tedy existuje nekonečná množina M taková, že pro každé x ∈ X platí, že x není hromadným bodem množiny M . Tedy ke každému x ∈ X existuje okolí Ux takové, že |Ux ∩ M | ≤ 1, to znamená, že mají společný nejvýše jeden bod (bod x). Systém {Ux ; x ∈ X} je pokrytím a můžeme z něj vybrat konečné podpokrytí {Ux1 , . . . , Uxn } tedy platí M ⊆X⊆

n [

Uxi .

i=1

Víme, že M je nekonečná, ale množin Uxi je jen konečně mnoho, tedy mohou pokrýt jen konečně mnoho bodů množiny M (neboť |Ux ∩ M | ≤ 1), ale M je pokrytá celá, čímž se dostáváme ke sporu.

Předpokládejme, že X je kompaktní a zároveň existuje pokrytí, z něhož nelze vybrat konečné podpokrytí. Jelikož je X kompaktní, pak je separabilní, a tedy lze vybrat spočetné podpokrytí. Označme jej U1 , U2 , . . . , Un , . . . Bez újmy na obecnosti budeme z tohoto pokrytí vybírat jiné pokrytí V1 , . . . , Vk tak, že V1 bude první neprázdné Un , položíme n1 = n, dále budeme volit Vk+1 = Un tak, aby Unk+1 6⊆ V1 ∪ · · · ∪ Vk a nk+1 > nk . Tedy V1 , V2 , . . . , Vk , . . . je opět pokrytí a navíc Vk+1 \

k [

Vl 6= ∅.

l=1

Označme symbolem xk prvek z tohoto doplňku, tj. xk ∈ Vk+1 \

k [

Vl .

l=1

Pak {xk } je nekonečná množina, a má tedy hromadný bod x ∈ X, který byl pokryt. Existuje tedy n ∈ N takové, že platí x ∈ Vn , ale Vn neobsahuje žádné xk pro k > n což znamená, že Vn obsahuje jen konečně mnoho bodů xk , tedy existuje ε0 > 0 takové, že Ω(x, ε0 ) ∩ Vn = {x}, 46

Úvod do teorie her

3 Dvojmaticové hry

což je spor.

3.5



Spernerovo lemma

Nejprve zavedeme několik pojmů, abychom v další části mohli vyslovit a doœ kázat Spernerovo lemma. To uplatníme při elementárním důkazu Brouwerovy věty o pevném bodě, kterou rovněž využijeme v důkazu již předesílané věty Nikaidô-Isody. Definice 3.14 Konvexním obalem množiny V ⊆ Rn rozumíme množinu všech konvexních kombinací bodů množiny V , tj. v1, . . . , vN

∈ V

conv V = {x1 v 1 + · · · + xN v N ; N ∈ N, x1 , . . . , xN

≥ 0

x1 + · · · + xN = 1

}.

Pojmem N -simplex rozumíme konvexní obal N + 1 bodů v 0 , v 1 , . . . , v N , tj. M = conv{v 0 , v 1 , . . . , v N }, tj. M = {x0 v 0 + x1 v 1 + · · · + xN v N ;

x0 , x1 , . . . , xN

≥ 0

x 0 + x1 + · · · + xN = 1

}

O bodech v 0 , v 1 , . . . , v N hovoříme jako o vrcholech simplexu M .

Hraničním elementem simplexu M rozumíme množinu bodů x0 , x1 , . . . , xN 0

1

≥ 0

N

Mp1 ...ps = {x0 v + x1 v + · · · + xN v ; x0 + x1 + · · · + xN = 1 xp 1 = · · · = xp s

= 0

},

kde 1 ≤ s ≤ N a p1 , . . . , ps jsou navzájem různá čísla od 0 do N . Poznámka 12 Jestliže s = N , pak Mp1 ...ps je vrcholem simplexu M , jestliže s = N − 1, pak Mp1 ...ps je hranou simplexu M atd. Pro s = 1 je Mp1 fasetou (tj. boční stěnou) simplexu M . 47

Úvod do teorie her

3 Dvojmaticové hry

Nechť n ≥ 1 je přirozené číslo. Pak n-tým barycentrickým podrozdělením simœ plexu M rozumíme množinu DM,n = {

∈ N0 k0 0 k1 1 kN N k0 , k1 , . . . , kN v + v + ··· + v ; n n n k0 + k1 + · · · + kN = n

}.

O bodech množiny DM,n hovoříme jako o vrcholech n-tého barycentrického podrozdělení simplexu M .

Nyní nechť každý vrchol x z n-tého barycentrického podrozdělení DM,n simœ plexu M je označen přirozeným číslem m(x) od 0 do N , a to tak, že jestliže x ∈ Mp1 ...ps , potom m(x) ∈ {0, 1, . . . , N } \ {p1 , . . . , ps }. Uvažujme n-té barycentrické podrozdělení DM,n simplexu M . Pak N1 -buňkou tohoto podrozdělení, kde 1 ≤ N1 ≤ N , rozumíme konvexní obal N1 sousedních bodů tohoto rozdělení x1

= .. .

xN1 =

k01 0 v n

+

k11 1 v n

1 kN vN , n

N

N

N

k0 1 0 v n

+ ··· +

+

k1 1 1 v n

+ ··· +

kN 1 N v , n

kde i k0i , k1i , . . . , kN

k0i

+

k1i

+ ··· +

∈ N0 , i kN

= n,

takových, že j i − kN |≤1 |k0i − k0j |, |k1i − k1j |, . . . , |kN

pro i, j = 1, . . ., N1 . O bodech x1 , . . . xN hovoříme jako o vrcholech a říkáme, že daná N1 -buňka je jimi tvořena.

Uvažujeme N1 -buňku n-tého barycentrického podrozdělení tvořenou vrcholy x1 , . . . , xN1 , které jsou označeny čísly m(x1 ), . . ., m(xN1 ). Potom typem této buœ ňky rozumíme množinu všech N1 -prvkových sekvencí, které lze z čísel m(x1 ), . . ., 48

Úvod do teorie her

3 Dvojmaticové hry

   m(xN1 ) vytvořit, tj. m(x1 ), . . . , m(xN1 ) = (m(x1 ), . . . , m(xN1 )), . . . , (m(xN1 ), . . . , m(x1 ) – tato množina obsahuje nejvýše N1 ! sekvencí. Sekvence (m(x1 ), . . . , m(xN1 )) je reprezentantem typu uvažované buňky. To znamená – jestliže m01 , m001 , . . ., m0N1 , m00N1 ∈ {0, 1, . . . , N } – že dva reprezentanti resp. sekvence (m01 , . . . , m0N1 ) a (m001 , . . . , m00N1 ) jsou ekvivalentní právě tehdy, když každé číslo obsahují se stejnou četností, avšak na pořadí těchto čísel v sekvenci nezáleží, tedy [m01 , . . . , m0N1 ] = [m001 , . . . , m00N1 ]. Nechť m1 , . . . , mN1 ∈ {0, 1, . . . , N }. Potom jako F (m1 , . . . , mN1 ) označíme počet buněk n-tého podrozdělení takových, že (m1 , . . . , mN1 ) je reprezentanœ tem jejich typu. Neboli F (m1 , . . . , mN1 ) je počet buněk typu [m1 , . . . , mN1 ]. Lemma 3.3 (Spernerovo) Počet F (0, 1, . . . , N ) je lichý. Důsledek F (0, 1, . . . , N ) ≥ 1. Důkaz (Spernerovo lemma) K důkazu Spernerova lemmatu využijeme maœ tematickou indukci. 1. N = 1 Máme dokázat, že počet F (0, 1) je lichý. Zabývejme se buňkami typu [0]. Nechť Fu (0) je počet buněk typu [0], které jsou uvnitř simplexu M (tj., nejsou jeho hraničními elementy), a nechť Fh (0) je počet buněk typu [0], které jsou jeho hraničními elementy. Snadno si uvědomíme, že 2F (0, 0) + F (0, 1) = 2Fu (0) + Fh (0), protože buňka typu [0, 0] resp. [0, 1] obsahuje dvě resp. jednu buňku typu [0]. Zatímco buňka typu [0], která je obsažena v hraničním elementu simœ plexu M , je započítána jednou, buňky typu [0], které jsou uvnitř simplexu M , jsou započítány dvakrát, neboť jsou sdíleny dvěma buňkami. Je ovšem zřejmé, že Fh (0) = 1, protože 1-simplex má právě dva hraniční elementy, z nichž jeden musí být označen číslem 0 a druhý číslem 1. 0r

r

r

49

r

r1

Úvod do teorie her

3 Dvojmaticové hry

Platí tedy vztah F (0, 1) = 2Fu (0) − 2F (0, 0) + 1, z nějž vyplývá, že číslo F (0, 1) je liché. 2. Předpokládejme, že tvrzení Spernerova lemmatu platí pro přirozené číslo N ≥ 1. 3. N + 1 Máme dokázat, že počet F (0, 1, . . . , N, N + 1) je lichý. Zabývejme se buœ ňkami typu [0, 1, . . . , N ]. Nechť Fu (0, 1, . . . , N ) resp. Fh (0, 1, . . . , N ) je počet buněk typu [0, 1, . . . , N ], které nejsou resp. jsou obsaženy v nějaœ kém hraničním elementu simplexu M . Snadno si uvědomíme, že N X

2F (0, 1, . . . , N, m) + F (0, 1, . . . , N, N + 1) =

m=0

= 2Fu (0, 1, . . . , N ) + Fh (0, 1, . . . , N ), protože každá buňka typu [0, 1, . . . , N, m] obsahuje dvě buňky typu [0, 1, . . . , N ] – jednou jako [0, 1, . . . , N ] („podstavuÿ) a jednou jako [0, 1, . . . , m − 1, m+1, . . . , N, m] („boční stěnuÿ) – a každá buňka typu [0, 1, . . . , N, N + 1] obsahuje pouze jednu buňku typu [0, 1, . . . , N ]. Opět platí, že buňka typu [0, 1, . . . , N ], která je obsažena v hraničním elementu simplexu M , je započítána jednou a že buňky typu [0, 1, . . . , N ], které leží uvnitř simœ plexu M , jsou započítány dvakrát (tvoří „hraniční stěnuÿ mezi sousedœ ními buňkami, které jsou započítány). Ovšem buňky typu [0, 1, . . . , N ], které leží v hraničním elementu simplexu M , leží v hraničním elementu MN +1 . Ten je ovšem N -simplexem, a proto počet Fh (0, 1, . . . , N ) je lichý podle indukčního předpokladu. Tedy F (0, 1, . . . , N, N + 1) = = 2Fu (0, 1, . . . , N ) −

N X

F (0, 1, . . . , N, m) + Fh (0, 1, . . . , N ),

m=0

kde Fh (0, 1, . . . , N ) je liché číslo, a tudíž počet F (0, 1, . . . , N, N + 1) je lichý.  50

Úvod do teorie her

3.6

3 Dvojmaticové hry

Brouwerova věta o pevném bodě

Brouwerova věta o pevném bodě je poměrně slavným výsledkem, který se poœ dařilo dokázat na počátku 20. století. Její původní důkaz byl značně obtížný. Během pozdějších let se podařilo nalézt celou řadu dalších důkazů Brouwerovy věty. Zde uvedeme její zcela elementární (kombinatorický) důkaz založený na použití Spernerova lemmatu. To lze pokládat za jakousi diskrétní analogii Brouwerovy věty o pevném bodě. Čtenář nalezne další důkazy Brouwerovy věty o pevném bodě ve čtivé knížce [Franklin - 2002], z níž jsme zde uváděný elementární důkaz převzali. Nejdříve připomeneme definici pevného bodu. Definice 3.15 Nechť f : M → M je libovolné zobrazení. Pak jeho pevným bodem rozumíme bod x ∈ M , který se v zobrazení f zobrazí sám na sebe, tj. f (x) = x. Věta 3.7 (Brouwerova o pevném bodě) Nechť M je N -simplex v eukliœ dovském prostoru Rn . Mějme spojité zobrazení f : M → M . Pak zobrazení f má alespoň jeden pevný bod x∗ = f (x∗ ) ∈ M . Důkaz K důkazu Brouwerovy věty o pevném bodě využijeme Spernerova lemmatu a provedeme jej sporem. Zvolme x ∈ M takové, že x = x0 v 0 +x1 v 1 +· · ·+xN v N . Dále položme y = f (x), pak y = y0 v 0 + y1 v 1 + · · · + yN v N a pro spor předpokládejme, že x 6= y, tedy  můžeme definovat index m(x) např. jako m(x) = min j ∈ {0, 1, . . . , N }; xj > yj . Index m(x) navíc splňuje podmínku, že když x ∈ Mp1 ...ps , pak m(x) ∈ {0, 1, . . . , N } \ {p1 . . . ps }. Dále vytvoříme n-té barycentrické podrozdělení DM,n . Prvky tohoto podrozœ dělení označíme čísly m(x). Spernerovo lemma nám zaručuje, že existuje buňka, jejíž vrcholy jsou označeny všemi čísly 0, 1, . . ., N . Vrcholy této buňky oznaœ číme x0 (n), x1 (n), . . . , xN (n) tak, aby


m x0 (n) = 0, m x1 (n) = 1, . . . , m xN (n) = N. 51

Úvod do teorie her

3 Dvojmaticové hry

Co nám toto říká o funkci y = f (x)? Podle definice indexu m(x) platí, že x0

> y0

ve vrcholu x0 (n)

x1

> y1

ve vrcholu x1 (n)

·

·

· ve vrcholu xN (n).

xN > y N

Pro velká n jsou všechny vrcholy buňky blízko sebe, jelikož průměr buňky je

∆ →0 pro n → ∞, max xp (n) − xq (n) = 0≤p
pro s → ∞

a pro každé j = 0, 1, . . . , N . Ale barycentrické souřadnice bodu x spojitě zᜠvisejí na x. Tedy, jestliže x0 , . . . , xN jsou barycentrické souřadnice bodu x∗ a y0 , . . . , yN jsou barycentrické souřadnice bodu y ∗ = f (x∗ ), pak získáme nerovœ nosti x0

≥ y0

v limitě x∗

x1

≥ y1

v limitě x∗

·

·

· v limitě x∗ .

xN ≥ y N Tedy xj ≥ y j

(j = 0, 1, . . . , N ).

Což v barycentrických souřadnicích dává, že x∗ = y ∗ , protože x0 + x1 + · · · + xN = 1 = y0 + y1 + · · · + yN .  52

Úvod do teorie her

3.7

3 Dvojmaticové hry

Věta Nikaidô-Isody

Teorie nekooperativních her zkoumá tu otázku, zda zadaná hra ve strategickém tvaru má alespoň jeden bod Nashovy rovnováhy. Ten nemusí vždy existovat – viz první jednoduché příklady z podkapitoly 2.1. Dále jsme viděli, že smíšené rozšíření maticové hry alespoň jeden sedlový bod (tj. bod Nashovy rovnováhy) má – viz hlavní větu 2.5 maticových her. Naproti tomu dokázat analogické tvrzení pro dvojmaticové hry (resp. obecnou konečnou hru n hráčů) je nepoœ měrně obtížnější. Původní Nashův důkaz [Nash - 1950] z roku 1950 využívá Kakutaniho větu o pevném bodě. Zde uvedeme klasickou větu Nikaidô-Isody z roku 1955, která umožňuje dokázat existenci Nashovy rovnováhy v širší třídě konvexních her. čtenář může prostudovat původní důkaz věty Nikaidô-Isody v článku [Nikaidô, Isoda - 1955]. Nejdříve zavedeme pojem konvexní hry. Definice 3.16 Konvexní hrou rozumíme hru n hráčů ve strategickém tvaru, která má následující vlastnosti. 1. Prostor strategií i-tého hráče je neprázdná kompaktní konvexní množina Xi v euklidovském lineárním prostoru konečné dimenze. 2. Výplata i-tého hráče Fi (x1 , . . . , xi , . . . , xn ) je konkávní v proměnné xi ∈ Xi , když ostatní proměnné x1 , . . . , xi−1 , xi+1 , . . . , xn jsou pevné. 3. Součet výplat hráčů

P

i

Fi (x1 , . . . , xi , . . . , xn ) je spojitý.

4. Pro každé pevné xi je výplata Fi (x1 , . . . , xi−1 , xi , xi+1 , . . . , xn ) spojitá v proměnných x1 , . . . , xi−1 , xi+1 , . . . , xn . Ve zbývající části kapitoly uvažujeme konvexní hru, pro kterou nyní zavedeme speciální označení. Nechť x = [x1 , . . . , xn ] a y = [y1 , . . . , yn ] jsou dvě nezávislé proměnné ze stejného prostoru X = X1 × · · · × Xn , který je kompaktní a konvexní. Pak funkce ϕ daná předpisem ϕ(x, y) =

n X

Fi (x1 , . . . , xi−1 , yi , xi+1 , . . . , xn )

i=1

53

Úvod do teorie her

3 Dvojmaticové hry

je konkávní v proměnné y ∈ X. Pak můžeme vyslovit následující lemma. Jeho důkaz je snadný, proto jej přeœ necháme čtenáři. Lemma 3.4 Bod x∗ = [x∗1 , x∗2 , . . . , x∗n ] ∈ X je bodem rovnováhy dané hry právě tehdy, když funkce ϕ(x∗ , y) nabývá svého maxima v bodě y = x∗ .

Věta 3.8 (Nikaidô-Isody) Konvexní hra má vždy alespoň jeden bod Naœ shovy rovnováhy. Důkaz Našim úkolem je ukázat, že pro konvexní hru existuje bod x∗ ∈ X taœ kový, že ϕ(x∗ , x∗ ) ≥ ϕ(x∗ , y) pro každé y ∈ X. Pro spor budeme předpokládat, že takové x∗ neexistuje. Pak ke každému x ∈ X existuje y ∈ X takové, že ϕ(x, x) < ϕ(x, y). Položme Gy =



x ∈ X; ϕ(x, x) < ϕ(x, y)



pro každé y ∈ X. Pak množiny

Gy jsou otevřené podle definice konvexní hry (podmínky 3. a 4.) a navíc platí, že X⊆

[

Gy .

y∈X

Tedy s ohledem na kompaktnost množiny X můžeme podle Heineho-Borelovy pokrývací věty nalézt konečnou množinu A = {a1 , a2 , ..., as } ⊆ X takovou, že X⊆

s [

Gaj .

j=1

Což implikuje, že ϕ(x, x) < maxj ϕ(x, aj ) pro všechna x ∈ X. Nyní položme   fj (x) = max ϕ(x, aj ) − ϕ(x, x), 0

(j = 1, 2, . . . , s).

Všechny tyto funkce jsou spojité (podle podmínek 3. a 4.) a splňují fj (x) ≥ 0, Ps j=1 fj (x) > 0 pro každé x ∈ X.

54

Úvod do teorie her

3 Dvojmaticové hry

Definujme spojité zobrazení Ps j=1 fj (x)aj x 7→ Ps , j=1 fj (x) které zobrazuje prostor X do konvexního obalu conv(A) množiny A, a tedy protože conv(A) ⊆ X, zobrazuje konvexní obal conv(A) sám do sebe. Jelikož conv(A) je simplex v konečněrozměrném euklidovském prostoru, existuje zde podle Brouwerovy věty o pevném bodě pevný bod. Označme jako x∗ jeden z těchto bodů. Pak máme Ps ∗ j=1 fj (x )aj x∗ = Ps ∈ conv(A) ⊆ X. ∗ j=1 fj (x ) Ps

 ∗ ∗ f (x ) > 0, musí existovat j splňující f (x ) = max ϕ(x∗ , aj ) − j j j=1  ϕ(x∗ , x∗ ), 0 > 0, a tudíž ϕ(x∗ , aj ) > ϕ(x∗ , x∗ ). Jelikož funkce ϕ(x, y) je konœ Protože

kávní v proměnné y, platí ∗

Ps fj (x∗ )aj
ϕ x , Pj=1 ≥ s ∗ j=1 fj (x ) Ps ∗ ∗ Pϕ(x ,aj ) j=1 fj (x ) sj=1 fj (x∗ ) Ps ∗ ∗ ∗ Pϕ(x ,x ) j=1 fj (x ) sj=1 fj (x∗ )

∗

∗

ϕ(x , x ) = ≥ >

> ≥ ϕ(x∗ , x∗ ),

protože ϕ(x∗ , aj ) > ϕ(x∗ , x∗ ) pro všechna j taková, že fj (x∗ ) > 0, zatímco člen ϕ(x∗ , aj ) resp. ϕ(x∗ , x∗ ) se nezapočítává, jestliže fj (x∗ ) = 0; platí tedy ϕ(x∗ , x∗ ) > ϕ(x∗ , x∗ ), což je spor. Konvexní hra tedy alespoň jeden bod Naœ shovy rovnováhy má.



Cvičení 3.1 Určete, která z následujících her je věznovým dilematem.

(a)

S

Z

S

8 8

2 5

Z

5 2

3 3

(c)

(b)

S

Z

S

5 5

8 3

Z

3 8

2 2

S

Z

S

5 5

2 8

Z

8 2

3 3

55

Úvod do teorie her

3 Dvojmaticové hry

Cvičení 3.2 Určete, která z následujících her je věznovým dilematem.

(a)

S

Z

S

3 3

2 5

Z

5 2

1 1

(b)

S

Z

S

3 3

1 5

Z

5 1

2 2

S

Z

S

5 5

3 1

Z

1 3

2 2

(c)

Cvičení 3.3 Určete, která z následujících her je věznovým dilematem.

(a)

S

Z

S

3 3

5 2

Z

2 5

1 1

(c)

(b)

S

Z

S

2 2

5 1

Z

1 5

3 3

S

Z

S

3 3

1 5

Z

5 1

2 2

Korespondenční úkol 2 Vytvořte matici smíšeného rozšíření dvojmaticové hry manželský spor (viz příklad 3.2) a najděte její rovnovážné strategie.

56

Úvod do teorie her

4

4 Kooperativní hry

Kooperativní hry

Obsah lekce 4.1. Kooperativní hry s přenosnou výhrou ve tvaru koaliční funkce . . . . 58 4.2. Kooperativní hry ve tvaru funkce koaliční struktury . . . . . . . . . . . 58 4.3. Koncepty řešení kooperativních her s přenosnou výhrou . . . . . . . . . 59

Klíčová slova Koalice, koaliční funkce, koaliční struktura, hra s přenosnou výhrou, výplatní vektor, imputace, jádro hry, kernel, nukleolus, Shapleyova hodnota.

Kooperativní hry jsou založeny na vzájemné spolupráci hráčů. Hráči mezi seœ bou vytvářejí tzv. koalice a v rámci těchto koalic spolupracují. Z nekoopeœ rativních her zůstává zachován předpoklad, že každý hráč maximalizuje svou výplatu. Kooperativní hry máme dvojího typu: s výhrou přenosnou a výhrou nepřenosœ nou. Zde se budeme zabývat pouze hrami s výhrou přenosnou. Kooperativní hry vyšetřujeme nejčastěji ve tvaru koaliční funkce (zavedeme níže). Lze je zkoumat také ve tvaru funkce koaliční struktury (zavedeme také), ve strateœ gickém tvaru (viz předchozí kapitoly) aj. Nejdříve vyslovíme definici koalice. Definice 4.1 Mějme množinu hráčů N = {1, 2, . . . , n}. Pak koalicí rozumíme libovolnou podmnožinu K ⊆ N množiny hráčů. Poznámka 13 Celkový počet koalic je 2n . Koalice K = ∅ je prázdná a koalice K = N se nazývá velká.

57

Úvod do teorie her

4.1

4 Kooperativní hry

Kooperativní hry s přenosnou výhrou ve tvaru koaliční funkce

Poznámka 14 Potenční množinou množiny N rozumíme množinu všech jejích podmnožin P(N ) = 2N = {K; K ⊆ N }. Tedy rozumíme jí množinu všech koalic, které mohou vzniknout.

Definice 4.2 Koaliční funkcí rozumíme libovolnou funkci (zobrazení) v:

P(N ) →

R

7→ v(K)

K takovou, že v(∅) = 0.

Z definice vidíme, že kooperativní hra s přenosnou výhrou ve tvaru koaliční funkce je zadána koaliční funkcí, kde číslo v(K) je výplata koalice K v případě, že tato koalice vznikne. Na rozdíl od her ve strategickém tvaru se u her ve tvaru koaliční funkce neœ zkoumá, jakým způsobem koalice K svého zisku v(K) dosáhne. Předpokládá se, že koalice K ví, jak svého zisku dosáhnout.

4.2

Kooperativní hry ve tvaru funkce koaliční struktury

Definice 4.3 Koaliční strukturou rozumíme rozklad množiny N , tj. kolekci S = {S1 , S2 , . . . , Sr } koalic takových, že 1.

Sr

k=1

Sk = N ,

2. Sk ∩ Sl = ∅ pro k 6= l, 3. Sk 6= ∅.

58

Úvod do teorie her

4 Kooperativní hry

Poznámka 15 Počet koaličních struktur se určuje pomocí principu inkluze a exkluze. Jestliže se určí, že koaliční struktura bude mít r koalic o velikosti j1 , . . . , jr ≥ 0, kde j1 +· · ·+jr = n, pak jejich počet je multinomické kombinační číslo



n j1 . . . jr

 =

n! . j1 ! · · · jr !

Definice 4.4 Funkcí koaliční struktury rozumíme funkci v:

S → {vS : S → R} S 7→

vS ,

kde vS :

S

→

R

K 7→ vS (K). Tedy S je množina všech možných koaličních struktur a vS je koaliční funkce definovaná na dané koaliční struktuře S ∈ S.

Poznámka 16 Můžeme si všimnout, že hodnota koalice K v tomto případě závisí také na celkové koaliční struktuře.

4.3

Koncepty řešení kooperativních her s přenosnou výhrou

Definice 4.5 Hrou s přenosnou výhrou rozumíme následující situaci: vzniklá koalice K = {i1 , . . . , ik } dostane celkovou výplatu P , kterou je možné v rámci koalice přerozdělit mezi hráče. Hráči v koalici o konkrétním způsobu přerozœ dělení jednají, např. jestliže ai1 , . . . , aik jsou výplaty hráčů i1 , . . ., ik , pak Pn k=1 aik ≤ P .

59

Úvod do teorie her

4 Kooperativní hry

Mějme tedy kooperativní hru s přenosnou výhrou, která je zadána množinou hráčů N = {1, 2, . . . , n} a koaliční funkcí v : P(N ) → R. Dále předpokládáme, že již vznikla koaliční struktura S = {S1 , . . . , Sr } a že tato struktura je dána pevně. Výplaty koalic v této koaliční struktuře jsou v(S1 ), . . . , v(Sr ). Nyní zkoumáme jak si hráči výplatu přerozdělí. Způsob rozdělení výher je popsán výplatním vektorem. Definice 4.6 Výplatním vektorem rozumíme libovolnou, uspořádanou n-tici reálných čísel a ∈ Rn , tj.



a1



   a=  

a2 .. .

     

an

kde ai je výplata i-tého hráče (i = 1, . . . , n). Otázka 5 Jaké vlastnosti by měly výplaty hráčů splňovat? 1. Přípustnost X

ai ≤ v(Sk )

pro Sk ∈ S,

i∈Sk

tedy v rámci koalice nelze rozdělit více než má koalice k dispozici. 2. Kolektivní racionálnost X

ai ≥ v(Sk )

pro Sk ∈ S,

i∈Sk

tedy hráči maximalizují svůj individuální zisk. 3. Individuální racionálnost ai ≥ v({i})

pro i ∈ N,

tedy každý hráč má dostat alespoň tolik, kolik si je schopen sám zajistit vytvořením jednoprvkové aliance.

60

Úvod do teorie her

4 Kooperativní hry

Poznámka 17 Při bližším pohledu na vlastnosti přípustnosti a kolektivní racionálnosti nikomu jistě neujde, že jejich spojením získáme jednu jedinou vlastnost výplatního vektoru, a to X ai = v(Sk )

pro Sk ∈ S.

i∈Sk

Definice 4.7 Výplatní vektor a, který splňuje výše uvedené vlastnosti se naœ zývá imputace vzhledem ke koaliční struktuře S. Definice 4.8 Množinou imputací rozumíme množinu X  X = a ∈ Rn ; ai = v(Sk ) pro Sk ∈ S, ai ≥ v({i}) pro i ∈ N . i∈Sk

Nyní si uvedeme základní koncepty řešení kooperativních her. Koncept řešení je předpis, který koaliční funkci v a koaliční struktuře S přiřadí množinu výœ platních vektorů (jádro, vyjednávací množina atd.), popř. množinu množin výplatních vektorů (von Neumannovo-Morgensternovo řešení), popř. jeden výœ platní vektor (Shapleyova hodnota). V dalších oddílech uvedeme následující koncepty řešení kooperativních her s přenosnou výhrou: 1. jádro, 2. vyjednávací množina, 3. kernel, 4. nukleolus, 5. Shapleyova hodnota, 6. von Neumannovo-Morgensternovo řešení. 4.3.1

Jádro

Jádro hry je důležitým pojmem v oblasti kooperativních her, nyní zavedeme jeho formální definici.

61

Úvod do teorie her

4 Kooperativní hry

Definice 4.9 Jádrem hry vzhledem ke koaliční struktuře S = {S1 , . . . , Sr } rozumíme množinu všech dělení zisku, které splňují podmínku přípustnosti a podmínku skupinové stability, tj. X X C = {a ∈ Rn ; ai ≤ v(Sk ) pro Sk ∈ S, ai ≥ v(K) pro K ∈ P(N )}. i∈Sk

Podmínka

P

i∈K

i∈K

ai ≥ v(K) pro K ∈ P(N ) vyskytující se v jádru hry se naœ

zývá podmínka skupinové stability. Tato podmínka říká, že pokud by se našla P koalice K ∈ P(N ) \ S, pro kterou by platila negace i∈K ai < v(K), potom by tato koalice vznikla (neboť po svém vzniku dosáhne většího zisku v(K), než který má dohromady nyní), což by mělo za následek zhroucení původní koaœ liční struktury S. Pro K ∈ S ovšem druhá podmínka vyjadřuje tzv. podmínku kolektivní racionálnosti, což znamená, že všichni hráči maximalizují své indiviœ duální zisky, tedy zisk v(Sk ) své koalice si mezi sebe přerozdělí celý: dostáváme P rovnost i∈Sk ai = v(Sk ) pro Sk ∈ S. 4.3.2

Vyjednávací množina

Vyjednávací množina je konceptem řešení definovaným pomocí námitek a proœ tinámitek. Definice 4.10 Mějme kooperativní hru. Nechť v koalici S z koaliční struktury S jsou hráči k a l, přičemž k 6= l. Námitkou hráče k proti hráči l při imputaci a rozumíme dvojici (b, K), kde K je libovolná koalice taková, že k ∈ K a zároveň P l 6∈ K, a b ∈ RK je dělení zisku takové, že i∈K bi = v(K) a navíc bi > ai

pro i ∈ K.

Definice 4.11 Mějme kooperativní hru. Nechť (b, K) je námitka hráče k proti hráči l při imputaci a. Protinámitkou hráče l proti hráči k k námitce (b, K) rozumíme dvojici (c, L), kde L je libovolná koalice taková, že l ∈ L a zároveň P k 6∈ L, a c ∈ RL je dělení zisku takové, že i∈L ci = v(L) a navíc ci ≥ bi pro i ∈ L ∩ K, ci ≥ ai pro i ∈ L \ K.

62

Úvod do teorie her

4 Kooperativní hry

Definice 4.12 Vyjednávací množinou rozumíme množinu všech imputací taœ kových, že ke každé námitce existuje protinámitka, tedy Mi1 = {a ∈ X; každá námitka při a má protinámitku}. Tvrzení 4.1 Nechť a je imputace z jádra C. Potom k této imputaci neexistuje námitka. Věta 4.1 Pro vyjednávací množinu Mi1 a jádro C platí vztah C ⊆ Mi1 . Důkaz Aby C bylo podmnožinou Mi1 , musí mít každá námitka při imputaci a protinámitku. Protože ale víme, že k prvkům z jádra neexistuje žádná námitka, je tvrzení zřejmé.

4.3.3



Kernel

Kernel je koncept řešení, který se definuje pomocí přebytku hráčů. Definice 4.13 Mějme kooperativní hru. Nechť K ⊆ N je koalice a a ∈ Rn je imputace. Potom excesem koalice K při imputaci a nazýváme hodnotu e(a, K), která je definována vztahem e(a, K) = v(K) −

X

ai .

i∈K

Definice 4.14 Mějme kooperativní hru. Přebytkem hráče k proti hráči l při imputaci a nazýváme hodnotu sk,l (a) = max e(a, K). K⊆N k∈K, l6∈K

63

Úvod do teorie her

4 Kooperativní hry

Definice 4.15 Mějme kooperativní hru. Nechť S = {S1 , . . . , Sr }. Potom Kernel K je množina všech imputací a ∈ Rn , pro které platí, že pro každé dva různé hráče k a l z téže koalice Si ∈ S platí sk,l (a) > sl,k (a) =⇒ al = v({l}), tedy  K = a ∈ X; ∀k, l ∈ Si ∈ S, k 6= l : sk,l (a) > sl,k (a) =⇒ al = v({l}) Poznámka 18 V dalším textu pro stručnost používáme následující označení, které je v literatuře obvyklé. Pro výplatní vektor a ∈ Rn a koalici K ⊆ N klademe a(K) =

X

ai .

i∈K

Věta 4.2 Pro kernel K a vyjednávací množinu Mi1 platí vztah K ⊆ Mi1 . Důkaz Chceme ukázat, že jestliže imputace a ∈ K, pak ke každé námitce při a existuje protinámitka. Nechť (b, K) je námitka hráče k proti hráči l při imputaci a, tj. k ∈ K, l 6∈ K a bh > ah pro všechna h ∈ K. Protože a je imputace, platí al ≥ v({l}). Rozlišíme dva případy: buď al = v({l}), nebo al > v({l}). • Jestliže al = v({l}), pak uvažujeme jednoprvkovou koalici L = {l} a dělení zisku cl = v({l}). Tedy l ∈ L, k 6∈ L, c(L) = v(L), ch ≥ bh pro h ∈ L ∩ K a ch ≥ ah pro h ∈ L \ K. Tedy (c, L) je protinámitka hráče l proti hráči k při námitce (b, K). • Jestliže al > v({l}), potom, jelikož a ∈ K, platí, že sl,k (a) ≥ sk,l (a). Můžeme psát sl,k (a) ≥ =

sk,l (a) max v( K) − v(a)

K⊆Q k∈K, l6∈K

≥ v(K) − a(K) = b(K) − a(K). 64

Úvod do teorie her

4 Kooperativní hry

Dále nechť koalice L je právě ta koalice, ve které hráč l získá maximální možnou výhru bez účasti hráče l při imputaci a. Tedy sl,k (a) = v(L) − a(L). Pak v(L) − a(L) ≥ v(K) − a(K) = b(K) − a(K). Po úpravě v(L) ≥ b(K ∩ L) + b(K \ L) + a(L \ K) − a(K \ L). Jelikož předpokládáme, že bh > ah pro všechny hráče z koalice K, pak platí v(L) ≥ b(K ∩ L) + b(K \ L) + a(L \ K) − a(K \ L) > b(K ∩ L) + a(L \ K). Můžeme tedy zlepšit zisk hráčům, kteří jsou v K ∩L a i těm, kteří jsou v L\K. Tedy existuje vektor c pro který platí c(L) = v(L), ch

≥

ah

pro h ∈ L \ K,

ch

≥

bh

pro h ∈ L ∩ K.

Což znamená, že ke každé námitce (b, K) existuje protinámitka (c, L).

4.3.4



Nukleolus

Nukleolus je koncept řešení, který hledá vyhovující rozdělení zisku pomocí excesů. Připomeneme, že excesem koalice K při imputaci a nazýváme hodnotu e(a, K), která je definována vztahem e(a, K) = v(K) −

X

ai .

i∈K

Pro imputaci a máme v kooperativní hře celkem 2n excesů. Tyto excesy seřaœ díme podle velikosti sestupně, bude tedy platit e(a, K1 ) ≥ · · · ≥ e(a, K2n ). 65

Úvod do teorie her

4 Kooperativní hry

Z takto seřazených excesů koalic můžeme vytvořit vektor θ(a) ∈ Rn násleœ dovně:

  θ(a) =  

e(a, K1 )



···

 . 

e(a, K2n )

Koalici K na k-tém místě vektoru θ(a) označíme Kk,a . K definici nukleolu je třeba zavést pojem lexikografického uspořádání. Definice 4.16 1. Řekneme, že vektor θ(a) je lexikograficky menší než vektor θ(b) právě tehdy, když θ(a) 6= θ(b) a zároveň první nenulová složka θ(a) − θ(b) je menší než nula. Tento vztah značíme θ(a)
Poznámka 19 Obdobně definujeme vztahy lexikograficky větší a lexikograficky větší nebo rovno.

Definice 4.17 Mějme kooperativní hru. Pak nukleolem N rozumíme množinu N =



a ∈ X; ∀b ∈ X : θ(a) ≤lex θ(b) .

Excesem rozumíme míru nespokojenosti koalice K se stávajícím dělením a. Vektor θ(a) je vektor excesů seřazených sestupně, tedy nejvíce nespokojené koalice jsou na prvních místech, jejich nespokojenost se následně lexikograficky minimalizuje. To znamená, že nukleolus minimalizuje celkovou nespokojenost koalic se stávajícím dělením zisku. Věta 4.3 Jestliže je množina imputací X neprázdná, potom nukleolus je také neprázdný.

66

Úvod do teorie her

4 Kooperativní hry

Věta 4.4 Jestliže je množina imputací X neprázdná a kompaktní, potom nukleolus obsahuje právě jeden prvek.

Věta 4.5 Nechť je jádro hry C neprázdné. Potom pro nukleolus N a jádro hry C platí vztah N ⊆ C.

Důkaz Nechť je jádro hry C neprázdné. Ukážeme, že imputace, která není v jádru C, není ani v nukleolu N . Nechť a 6∈ C. Potom existuje koalice K taková, že platí a(K) < v(K), neboli e(a, K) = v(K) − a(K) > 0. Z předpokladu neprázdnosti jádra C vyplývá, že imputace b, pro kterou platí e(b, L) ≤ 0 pro libovolnou koalici L. Tedy θ(b) je jistě lexikograficky menší než θ(a), proto imputace a neleží v nukleolu N .



Poznámka 20 Jestliže je C = ∅ a X 6= ∅, pak N udává implicitní polohu jádra.

Věta 4.6 Pro nukleolus N a kerenel K platí vztah N ⊆ K.

Důkaz Naším úkolem bude dokázat, že imputace, která není v kernelu K, není ani v nukleolu N . Nechť a 6∈ K. Potom existuje dvojice hráčů k, l tak, že buď sl,k (a) < sk,l (a) a al < v({l}), nebo sl,k (a) < sk,l (a) a al > v({l}). V prvním případě je porušena podmínka individuální racionality, budeme tedy uvažovat pouze o případě druhém. Nechť sl,k (a) =

max e(a, K) <

K⊆N l∈K, k6∈K

max e(a, K) = sk,l (a) a zároveň al >

K⊆N k∈L, l6∈L

v({l}). Existuje tedy hodnota α > 0 taková, že můžeme hráči l zisk při imputaci 67

Úvod do teorie her

4 Kooperativní hry

a o tuto hodnotu snížit a stále bude splněna podmínka individuální racionality. Hráči k můžeme naopak zisk o α zvýšit. Uvažujeme tedy imputaci b následovně bh =

ah

pro h ∈ N, , h 6= k, l

bk = ak + α, bl = al − α. Hodnotu α vybere tak, aby platilo sl,k (b) = max K⊆N

max

K⊆N k∈L, l6∈L


v(L)−b(L) +α < sk,l (b) =

l∈K, k6∈K
v(K) − b(K) = v(K) − a(K) − α. Vybereme minimální index k¯ ∈

{1, . . . , 2N } tak, aby e(a, Kk,a ¯ ). ¯ ) 6= e(b, Kk,a V koalici Kk,a ¯ je hráč k bez hráče l. Nyní rozlišíme dvě možnosti. • Pokud jsou excesy v θ(a) rovny e(a, Kk,a ¯ ) pouze pro koalice s hráčem k bez hráče l, pak platí pro k˜ < k¯ platí e(a, Kk,a ¯ ), ˜ ) = e(b, Kk,a pro k˜ = k¯ platí e(a, K˜ ) > e(b, Kk,a ¯ ), k,a

pro k˜ > k¯ platí e(b, Kk,a ¯ ). ˜ ) ≤ e(b, Kk,a Tedy θ(b) je lexikograficky menší než θ(a), a proto a není v nukleolu. • Pokud pro nějakou koalici s oběma hráči nebo s ani jedním z hráčů k, l nabývá exces také hodnoty e(a, Kk,a ¯ ), potom stačí seřadit excesy ve vekœ torech θ(a), θ(b) tak, aby tyto koalice předcházely koalicím obsahujícím jen hráče k. Po seřazení a přeindexování vybereme znovu index k¯ tak, aby byl minimální a platil výše uvedený vztah. Tím se opět dostaneme k situaci v bodě výše, a tedy imputace a není v nukleolu.  Věta 4.7 N ⊆ K ⊆ Mi1 . Důkaz Tvrzení je důsledkem vět 4.2 a 4.6.

68



Úvod do teorie her

4 Kooperativní hry

Důsledek Jestliže X 6= ∅, potom K 6= ∅ i Mi1 6= ∅. Důkaz Tvrzení je důsledkem vět 4.3 a 4.7.



Důsledek Jestliže C 6= ∅, potom C ∩ K 6= ∅ i C ∩ Mi1 6= ∅. Důkaz Tvrzení je důsledkem vět 4.3, 4.5 a 4.7.

4.3.5



Shapleyova hodnota

Shapleyova hodnota je jedním z konceptů řešení kooperativních her s přenosœ nou výhrou. Nejdříve si ukážeme postup výpočtu Shepleyovy hodnoty. Mějme množinu hráčů N = {1, 2, . . . , n} a předpokládejme vznik velké koalice S = {N } 1. Zvolíme i-tého hráče. 2. Tento hráč může nebo nemusí být členem koalice K ⊆ N , budeme předœ pokládat, že není, tj. i 6∈ K. 3. Pak přínos hráče i ke koalici K je v(K ∪ {i}) − v(K). 4. Předpokládejme, že velká koalice vznikla postupně, tj. příchodem jedœ notlivých hráčů po jednom v určitém pořadí. Je-li toto pořadí dáno, pak jsou dány i přínosy hráču. Mějme permutaci π : N → N , pak například hráč, který přistupuje první, je π1 , hráč, který přistupuje druhý, je π2 atd. Pak přínos hráče i, který přistupuje jako j-tý, tj. i = πj −1 , je v({π1 , . . . , πj−1 , πj }) − v({π1 , . . . , πj−1 }).

69

Úvod do teorie her

4 Kooperativní hry

Definice 4.18 Mějme množinu hráčů N = {1, 2, . . . , n} a předpokládejme vznik velké koalice S = {N }. Pak Shapleyova hodnota ϕ bude vektor   ϕ1    ϕ2    ϕ =  . ,  ..    ϕn kde ϕi je střední hodnota přínosu i-tého hráče, tj. n 1 X X v(K) − v(K \ {i})
. ϕi = n−1 N k=1 K⊆N k−1 |K|=k

Poznámka 21 Ukážeme si, jak lze odvodit Shapleyovu hodnotu. 1. Mějme množinu hráčů N = {1, 2, . . . , n}. Z této množiny hráčů pevně zvolíme jednoho hráče i ∈ N . 2. Nyní uvažujeme různé permutace π, kde π:

N → N

π:

r

7→ i,

tj. πr = i (i-tý hráč přistupuje jako r-tý). 3. Nyní zafixujeme pořadí, v jakém hráč přichází, tj. r ∈ N . 4. Uvažujeme všechny permutace π takové, že πr = i. 5. Pak přínos hráče i ke koalici K = {π1 , . . . , πr }, kde |K| = r, je v(K) − v(K \ {πr }). 6. Koalice K je zadána, i-tý hráč přichází jako poslední, koalici K lze tedy vytvořit (r − 1)! způsoby. Takto vytvořenou koalici lze doplnit na velkou koalici (n − r)! způsoby. To znamená, že přínos i-tého hráče ke koalici K je přičten celkem (r − 1)! (n − r)! krát, a tedy hodnota tohoto součtu je
v(K) − v(K \ {πr }) (r − 1)! (n − r)! pro K ⊆ N , |K| = r, i ∈ K. 70

Úvod do teorie her

4 Kooperativní hry

7. Dále je potřeba pro různé koalice K a různá r takto získané přínosy sečíst a vydělit n!, z čehož již dostáváme vzorec pro Shepleyovu hodnotu, tj. n 1 X X v(K) − v(K \ {πi })
ϕi = . n−1 N k=1 K⊆N k−1 |K|=k

Definice 4.19 Hra se nazývá superaditivní právě tehdy, když pro každé dvě disjunktní koalice K a L platí, že v(K) + v(L) ≤ v(K ∪ L), kde v je koaliční funkce. Následující věta je poměrně jednoduchá. Čtenář nechť její důkaz vypracuje jako cvičení. Věta 4.8 Jestliže je koaliční funkce hry superaditivní, potom je Shapleyova hodnota hry imputací. Poznámka 22 Axiomy pro Shapleyovu hodnotu: Uvažujme koaliční strukturu S = {N }. Shapleyovu hodnotu ϕ přiřazenou koœ aliční funkci v označíme ϕ(v). Pak Shapleyova hodnota má následující vlastœ nosti: 1. koncept řešení je jednobodová množina {ϕ(v)}, 2. eficience:

n X

ϕi (v) = v(N ),

i=1

3. symetrie: jestliže hráči i, j ∈ N jsou symetričtí, tj., pro každé K ⊆ N platí, že i, j 6∈ K implikuje v(K ∪ {i}) = v(K ∪ {j}), pak ϕi (v) = ϕj (v), 4. nepřínosnost: jestliže i je nepřínosných hráč, tj., pro každé K ⊆ N platí, že v(K ∪ {i}) − v(K) = 0, pak ϕi (v) = 0. 5. aditivita: pro každé v, w : P(N ) → R splňující v(∅) = w(∅) = 0, pro které (v + w)(K) = v(K) + w(K), platí, že ϕ(v + w) = ϕ(v) + ϕ(w). 71

Úvod do teorie her

4 Kooperativní hry

Věta 4.9 Existuje právě jeden koncept řešení kooperativních her splňující axiomy 1. − 5., a to právě Shapleyova hodnota.

Definice 4.20 Hra se nazývá konvexní právě tehdy, když v(S ∪ T ) − v(S ∩ T ) ≥ v(S) + v(T ), pro libovolné S, T ⊆ N .

Věta 4.10 Jádro konvexní hry je neprázdné.

Věta 4.11 Mějme konvexní hru s koaliční strukturou S = {N }. Potom Shaœ pleyova hodnota hry ϕ je rovna aritmetickému průměru vrcholů jádra.

4.3.6

Von Neumannovo-Morgensternovo řešení

Koncept von Neumannova-Morgensternova řešení je založen na výběru přijaœ telných imputací pomocí dominování imputací. Definice 4.21 Nechť a a b jsou imputace. Řekneme, že imputace a dominuje b právě tehdy, když existuje koalice K ⊆ N taková, že ai P

i∈K

>

bi

ai ≤ v(K).

pro i ∈ K,

.

Tento vztah značíme a dom b.

Definice 4.22 Množinou všech imputací dom V rozumíme množinu dom V = {a ∈ X; ∃b ∈ V : b dominuje a}, kde V ⊆ X.

Pozorování 4 Nechť U, V ⊆ X. Jestliže U ⊆ V , potom domU ⊆ domV .

72

Úvod do teorie her

4 Kooperativní hry

Definice 4.23 Množina V ⊆ X je von Neumannovým-Morgensternovým řešením právě tehdy, když jsou splněny následující podmínky: 1. Vnitřní stabilita. V množině V neexistuje imputace, která by domiœ novala jiné imputaci z množiny V , tj., jestliže a, b náleží do množiny V , pak imputace a nedominuje imputaci b. 2. Vnější dominance. Každá imputace, která není obsažena v množině V , je dominována nějakou imputací z množiny V , tj., ke každému a ∈ X \ V existuje b ∈ V takové, že b dominuje a. Věta 4.12 Množina imputací V ⊆ X je von Neumannovým-Morgensternoœ vým řešením právě tehdy, když V = X \ dom V. Věta 4.13 Nechť C je jádro hry. Potom platí C ⊆ X \ dom X. Důkaz Dokážeme, že domX ⊆ X \ C. Nechť a ∈ domX, tedy X ∃b ∈ X : ∃K ⊆ N : bi > ai a bi ≤ v(K), a tudíž

P

ai < v(K), tedy a 6∈ C.



Věta 4.14 Nechť C je jádro hry a V je von Neumannovo-Morgensternovo řešení. Potom platí C ⊆ V. Důkaz Von Neumannovo-Morgesternovo řešení je podmožinou množiny imœ putací X, a tedy platí, že dom V ⊆ dom X, neboli X \ dom V ⊇ X \ dom X, což znamená, že V = X \ dom V ⊇ X \ dom X ⊇ C.  73

Úvod do teorie her

4 Kooperativní hry

Věta 4.15 Jestliže je hra konvexní, potom pro jádro hry C a von Neumannoœ vo-Morgesternovo řešení V platí vztah C = V.

Věta 4.16 Mějme superaditivní hru s koaliční strukturou S = {N }. Pak imputace a se nachází v jádru hry C právě tehdy, když a není dominována žádnou jinou imputací, tj. C = X \ dom X.

Cvičení 4.1 V kooperativní hře šesti hráčů 1, . . . , 6 došlo ke vzniku koaliční  struktury {1, 4}, {2, 5}, {3, 6} . Hodnoty koalic jsou: v({1, 4}) = 10 ,

v({2, 5}) = 20 ,

v({3, 6}) = 30 ,

v({1}) = 1 , v({2}) = 2 , v({3}) = 3 , v({4}) = 1 , v({5}) = 2 , v({6}) = 3 . Které z následujících dělení zisků, popsaných výplatními vektory, je přípustné a individuálně racionální?   8    3       5  ,  (a)    8     3    5



(b)

          



3





2

5

     ,     

          

 5    8  . 2    5   8

2 3 5 2

(c)

Cvičení 4.2 V kooperativní hře šesti hráčů 1, . . . , 6 došlo ke vzniku koaliční  struktury {1, 4}, {2, 5}, {3, 6} . Hodnoty koalic jsou: v({1, 4}) = 10 ,

v({2, 5}) = 20 ,

v({3, 6}) = 30 ,

v({1}) = 1 , v({2}) = 2 , v({3}) = 3 , v({4}) = 1 , v({5}) = 2 , v({6}) = 3 .

74

Úvod do teorie her

4 Kooperativní hry

Které z následujících dělení zisků, popsaných výplatními vektory, není příœ pustné a individuálně racionální (tj., není přípustné nebo není individuálně racionální)? 

(a)

          

3





8

     ,     

          

5 3 8 5

(b)



8





2

3

     ,     

          

 5    8  . 8    5   2

2 8 3 2

(c)

Korespondenční úkol 3 Katedra matematiky a katedra informatiky se přou o výuku předmětu Kódování a kryptografie. Obě tyto katedry jej potřebují, neboť čím více mají studentů, tím více dostanou peněz. Katedra informatiky má odborníka na danou oblast, a tedy katedra matematiky může tuto službu využít – studenti matematiky budou chodit na přednášky informatiků (a kaœ tedry se mezi sebou mohou dohodnout na přerozdělení peněz). Naopak katedra matematiky nemá odborníka, ale má hodně studentů, kteří o tento předmět mají zájem, a tak bude mít možnost najít a zaplatit externího odborníka. Máme tedy následující situaci: • hráč č. 1 – katedra informatiky, • hráč č. 2 – katedra matematiky, • výplata, pokud se předmět bude vyučovat pouze na katedře informatiky a studenti matematiky budou chodit na přednášky informatiků, v({1, 2}) = 8, • výplaty, pokud se předmět rozdělí mezi obě katedry, tj., pokud každá katedra učí svůj předmět samostatně, v({1}) = 3, v({2}) = 2. Uvažujte koaliční strukturu S = {1, 2} a spočtěte jádro této hry. 75

Úvod do teorie her

Řešení cvičení

Řešení cvičení 1. cvičení 1.1: (a) [a, x], [b, y], [c, z], (b) [b, y], 2. Cvičení 2.1: ano má sedlový bod, číslo 3 v průniku druhého řádku a druhého sloupce, 3. Cvičení 2.2: ano má čtyři sedlové body, čísla 3 v průnicích druhého a třetího řádku s druhým a čtvrtým sloupcem, 4. Cvičení 2.3: nemá sedlový bod,   >  1 1 ¯ ¯ 5. Cvičeni 2.4: X = ,Y = 2 2 6. Cvičení 2.5: A¯ =

0 1 0

A¯ =

3 8 9

1 4

!

1 0 1

7. Cvičení 2.5: 1 0 3

8. Cvičení 3.1: (c), 9. Cvičení 3.2: (b), 10. Cvičení 3.3: (a), 11. Cvičení 4.1: (c), 12. Cvičení 4.2: (b).

76

!

3 4

> 

a F¯ (x, y) = 55,

Úvod do teorie her

Reference

Reference [Franklin - 2002] Franklin Joel N. Methods of Mathematical Economics: Linear and Nonlinear Programming, Fixed-Point Theorems. SIAM, New York, 2002. ISBN 0-89871-509-1. [Chobot, Turnovec, Ulašín - 1991] Chobot M., Turnovec F., Ulašín V. Teória hier a rozhodovania. Alfa, Bratislava, 1991. ISBN 80-05-00702-7. [Maňas - 1991] Maňas M. Teorie her a její aplikace. SNTL, Praha, 1991. ISBN 80-03-00358-X. [Nash - 1950] Nash, J. F. Equilibrium Points in n-Person Games. Proceedings of the National Academy of Sciences of the United States of America. 1950, Vol. 36, No. 1, pp. 48–49. [Nikaidô, Isoda - 1955] Nikaidô, H., Isoda, K. Note on Noncooperative Convex Games. Pacific Journal of Mathematics. 1955, Vol. 5, Suppl. 1, pp. 807–815. [Pustková - 2009] Pustková V. Koncepty rešení kooperativních her. Ostravœ ská univerzita v Ostravě, 2009. Diplomová práce.

77

Úvod do teorie her

Příloha: Vysvětlivky k používaným symbolům

Příloha: Vysvětlivky k používaným symbolům Průvodce studiem – vstup autora do textu, specifický způœ sob, kterým se studentem komunikuje, povzbuzuje jej, doœ plňuje text o další informace. Příklad – objasnění nebo konkretizování problematiky na přikladu ze života, praxe, společenské reality apod. Pojmy k zapamatování. Shrnutí – předcházející látky, kapitoly. Literatura – použitá ve studijním materiálu, pro doplnění a rozšíření poznatků. Kontrolní otázky a úkoly – prověřují, do jaké míry studuœ jící text a problematiku pochopil, zapamatoval si podstatné a důležité informace a zda je dokáže aplikovat při řešení proœ blémů. Úkoly k textu – je potřeba je splnit neprodleně, neboť poœ máhají dobrému zvládnutí následující látky. Korespondenční úkoly – při jejich plnění postupuje studuœ jící podle pokynů s notnou dávkou vlastní iniciativy. Úkoly se průběžně evidují a hodnotí v průběhu celého kursu. Úkoly k zamyšlení. Část pro zájemce – přináší látku a úkoly rozšiřující úroveň základního kursu. Pasáže a úkoly jsou dobrovolné. Testy a otázky – ke kterým řešení, odpovědi a výsledky studující najde v rámci studijní opory. Řešení a odpovědi – vážou se na konkrétní úkoly, zadání a testy.

78