Teorie her a ekonomické rozhodování. 3. Dvoumaticové hry (Bimaticové hry)

Teorie her a ekonomické rozhodování 3. Dvoumaticové hry (Bimaticové hry)

3.1 Neantagonistický konflikt • Hra – v normálním tvaru – hráči provedou jediné rozhodnutí a to všichni najednou – v rozvinutém tvaru – řada po sobě následujících tahů, přičemž hráči se v tazích střídají

Mgr. Jana Sekničková, Ph.D.

2

3.1 Neantagonistický konflikt • Antagonistický konflikt = co jeden získá, to druhý ztratí (spolupráce nemá smysl) – hra s konstantním součtem

• Neantagonistický konflikt = zájmy hráčů nejsou v přímém protikladu – hra s nekonstantním součtem – výhra prvého hráče není prohrou druhého Mgr. Jana Sekničková, Ph.D.

3

3.1 Neantagonistický konflikt • V případě neantagonistického konfliktu: – nekooperativní hra = hráči nemohou spolupracovat – kooperativní hra = hráči mohou spolupracovat


4

3.2 Nekooperativní hra • • • •

Konečný prostor strategií obou hráčů 1. hráč X = {x1, x2, …, xm} 2. hráč Y = {y1, y2, …, yn} Celkem tedy existuje m x n možných kombinací strategií • Každé kombinaci lze přiřadit výhru prvního hráče 𝑓1 (𝑥, 𝑦) a výhru druhého 𝑓2 (𝑥, 𝑦) Mgr. Jana Sekničková, Ph.D.

5

3.2 Nekooperativní hra • Hodnoty lze opět uspořádat do matice • Mezi hodnotou výplatní funkce 1. a 2. hráče však není definovaný přímý vztah • Proto jsou třeba matice dvě – A pro prvního hráče – B pro druhého hráče

• Dvoumaticová (dvojmaticová, bimaticová) hra Mgr. Jana Sekničková, Ph.D.

6

3.2 Nekooperativní hra 𝑎11 ⋮ 𝐀= 𝑎𝑚1

• • • •

⋯ ⋱ ⋯

𝑎1𝑛 𝑏11 ⋮ ⋮ ,𝐁 = 𝑎𝑚𝑛 𝑏𝑚1

⋯ ⋱ ⋯

𝑏1𝑛 ⋮ 𝑏𝑚𝑛

1. hráč … xi 2. hráč … yj 1. hráč získá aij … hodnota výplatní funkce 1. hráče 2. hráč získá bij … hodnota výplatní funkce 2. hráče Mgr. Jana Sekničková, Ph.D.

7

3.2 Nekooperativní hra Nashova rovnováha • Pokud se některý z hráčů odchýlí od své optimální strategie (zatímco soupeř se své optimální strategie držet bude), nepolepší si • Tzn. pokud se hráč nedrží optimální strategie, pohorší si (a v nejlepším případě na tom bude stejně) Mgr. Jana Sekničková, Ph.D.

8

3.2 Nekooperativní hra Nashova rovnováha • Dvojici strategií 𝑥 𝑜 ∈ 𝑋, 𝑦 𝑜 ∈ 𝑌 nazveme Nashovo rovnovážné řešení, pokud platí • 𝑓1 (𝑥, 𝑦 𝑜 ) ≤ 𝑓1 (𝑥 𝑜 , 𝑦 𝑜 ) a • 𝑓2 (𝑥 𝑜 , 𝑦) ≤ 𝑓2 (𝑥 𝑜 , 𝑦 𝑜 )


9

3.3 Nashova rovnováha • Nashovu rovnováhu získáme nalezením sedlového prvku (sedlového bodu) • Sedlový prvek – největší ve svém sloupci v matici A a – největší ve svém řádku v matici B Mgr. Jana Sekničková, Ph.D.

10

3.3 Nashova rovnováha • Vytvoříme tedy dvojmatici: 𝑎11 , 𝑏11 ⋯ 𝑎1𝑛 , 𝑏1𝑛 ⋮ ⋱ ⋮ 𝑎𝑚1 , 𝑏𝑚1 ⋯ 𝑎𝑚𝑛 , 𝑏𝑚𝑛 • V každém sloupci označíme všechny maximální hodnoty z prvních prvků • V každém řádku označíme všechny maximální hodnoty z druhých prvků Mgr. Jana Sekničková, Ph.D.

11

3.3 Nashova rovnováha • Sedlový bod = prvek, který má označenou – první složku (1. hráčem) a zároveň – druhou složku (2. hráčem)

• Nashova rovnováha = Nashovo rovnovážné řešení v ryzích strategiích


12

3.3 Nashova rovnováha • Příklad 1

1,5 2,1 3,2

4,2 1,9 3,1

2,3 1,4 4,0

• Nekooperativní hra může mít 1 sedlový prvek – optimální strategie získáme přímo Mgr. Jana Sekničková, Ph.D.

13


1,2 2,5 3,2

4,3 1,3 3,1

2,2 6,4 4,1

• Nekooperativní hra může mít více sedlových prvků Mgr. Jana Sekničková, Ph.D.

14

3.3 Nashova rovnováha • Uvedená úloha má dva sedlové body

1,2 4,3 2,2 2,5 1,3 6,4 3,2 3,1 4,1 • Na rozdíl od antagonistického konfliktu nejsou hodnoty výplatních funkcí stejné • Pokud máJak úloha jediný nedominovaný vybrat optimální strategii? sedlový prvek –Mgr.optimální strategie přímo Jana Sekničková, Ph.D.

15


1,2 2,3 3,6

5,3 1,4 3,4

2,1 4,5 4,2

Jak vybrat optimální strategii? • Nekooperativní hra může mít více sedlových prvků – alespoň 2 jsou vzájemně nedominované Mgr. Jana Sekničková, Ph.D. 16

3.3 Nashova rovnováha • Nekooperativní hra může mít více sedlových prvků • Pokud je jediný z nich nedominovaných, pak přímo určuje rovnovážné řešení v ryzích strategiích • Pokud jsou alespoň 2 vzájemně nedominované, pak se oba hráči mohou dostat do vzájemně nepříznivé situace Mgr. Jana Sekničková, Ph.D.

17


1,2 2,5 3,2

4,3 1,3 3,3

2,5 6,4 4,1

• Tato nekooperativní hra nemá žádný sedlový prvek – nemá Nashovo rovnovážné řešení v ryzích Mgr. strategiích Jana Sekničková, Ph.D. 18

3.3 Nashova rovnováha • Dvojmaticová hra může mít: – 1 sedlový prvek – rovnovážné strategie přímo – více sedlových prvků • jediný nedominovaný – rovnovážné strategie přímo • alespoň 2 nedominované – problém

– žádný sedlový prvek – neexistuje Nashova rovnováha v ryzích strategiích Pro hráče neexistují žádné rovnovážné strategie? Mgr. Jana Sekničková, Ph.D.

19

3.4 Smíšené rozšíření • Základní věta dvojmaticových her: Každá dvojmaticová hra má alespoň jedno rovnovážné řešení (ve smíšených strategiích)


20

3.4 Smíšené rozšíření • Postup hledání Nashova rovnovážného řešení ve smíšených strategiích se nazývá smíšené rozšíření dvojmaticové hry • Smíšené rozšíření použijeme, neexistuje-li řešení v ryzích strategiích (tj. neexistuje-li sedlový prvek)


21

3.4 Smíšené rozšíření • 𝑋 = {𝐱; 𝐱 𝐓 = (𝑥1 ; 𝑥2 ; … ; 𝑥𝑚 ); 𝑚

𝑥𝑖 = 1; 𝐱 ≥ 𝟎} 𝑖=1

• 𝑌 = {𝐲; 𝐲 𝐓 = (𝑦1 ; 𝑦2 ; … ; 𝑦𝑛 ); 𝑛

𝑦𝑗 = 1; 𝐲 ≥ 𝟎} 𝑗=1


22

3.4 Smíšené rozšíření • Hodnota výplatní funkce 1. hráče: 𝑚

𝑛

𝑥𝑖 𝑎𝑖𝑗 𝑦𝑗 = 𝐱 𝐓 𝐀𝐲

𝑓1 𝒙, 𝒚 = 𝑖=1 𝑗=1

• Hodnota výplatní funkce 2. hráče: 𝑚

𝑛

𝑥𝑖 𝑏𝑖𝑗 𝑦𝑗 = 𝐱 𝐓 𝐁𝐲

𝑓2 𝒙, 𝒚 = 𝑖=1 𝑗=1


23

3.4 Smíšené rozšíření • Podle ZVDMH existují optimální strategie (𝐱 𝐨 , 𝐲 𝐨 ) ve smíšeném rozšíření, neboli existuje Nashova rovnováha • Musí tedy platit: 𝐱 𝐓 𝐀𝐲 𝐨 ≤ 𝐱 𝐨𝐓 𝐀𝐲 𝐨 𝐱 𝐨𝐓 𝐁𝐲 ≤ 𝐱 𝐨𝐓 𝐁𝐲 𝐨 • Hledáme tedy (𝐱 𝐨 , 𝐲 𝐨 ) splňující uvedené nerovnosti Mgr. Jana Sekničková, Ph.D.

24

3.4 Smíšené rozšíření • max

•

•

𝑚 𝑖=1

𝑛 𝑗=1 𝑝𝑖 𝑞𝑗 𝑎𝑖𝑗 − 𝑚 𝑖=1 𝑝𝑖 −

+ 𝑏𝑖𝑗 − 𝑛 𝑗=1 𝑞𝑗

𝑛 𝑗=1 𝑎𝑖𝑗 𝑞𝑗 ≤ 1, ∀𝑖 𝑚 𝑖=1 𝑏𝑖𝑗 𝑝𝑖 ≤ 1, ∀𝑗

• 𝑞𝑗 ≥ 0, ∀𝑗 • 𝑝𝑖 ≥ 0, ∀𝑖 Mgr. Jana Sekničková, Ph.D.

25

3.4 Smíšené rozšíření • max 𝐩T 𝐀 + 𝐁 𝐪 − 𝐞T 𝐩 − 𝐟 𝐓 𝐪 • • • •

𝐀𝐪 ≤ 𝐞 𝐁T 𝐩 ≤ 𝐟 𝐩≥𝟎 𝐪≥𝟎


26

3.4 Smíšené rozšíření • Úloha kvadratického programování • Postup odvození je obdobný postupu v maticových hrách • Je třeba zajistit kladné prvky v maticích A a B • Symboly e a f označují vektory jedniček


27

3.4 Smíšené rozšíření • Zpětná substituce •𝑦 •

𝑜

𝑥𝑜

𝑗 𝑖

= =

𝑞𝑗 𝑛 𝑞 𝑗=1 𝑗

𝑝𝑖

𝑚 𝑝 𝑖=1 𝑖

𝐨

neboli

𝐲 =

neboli

𝐱𝐨

=

𝐪 𝐟T𝐪 𝐩 𝐞T 𝐩

• Takto nalezneme jedno optimální řešení (pomocí softwaru) • Úloha jich však může mít více (možnost: nastavit různá výchozí řešení) Mgr. Jana Sekničková, Ph.D.

28

3.5 Typické konflikty • Vězňovo dilema • Dva vězni jsou odděleně uvězněni • Každý má možnost se přiznat nebo nepřiznat • Pokud se jeden přizná a druhý ne, dostane první nižší trest (volný) a druhý vyšší • Nepřiznají-li se oba, dostanou nižší trest • Přiznají-li se oba, dostanou vyšší trest Mgr. Jana Sekničková, Ph.D.

29

3.5 Typické konflikty • Vězňovo dilema

𝑃 𝑁

𝑃 6,6 10,0

𝑁 0,10 2,2

• Správně záporná znaménka – záporný užitek Mgr. Jana Sekničková, Ph.D.

30


𝑃 𝑁

𝑃 −6, −6 −10,0

𝑁 0, −10 −2, −2

• Optimální pro oba je se přiznat • Pokud by se ani jeden nepřiznal, dopadli by oba lépe Mgr. Jana Sekničková, Ph.D.

31


𝑃 𝑁

𝑃 −6, −6 −10,0

𝑁 0, −10 −2, −2

• (P,P) je sice rovnovážné řešení, ale není Paretovsky rovnovážné (všichni si změnou mohou polepšit, aniž by byl někdo poškozen) Mgr. Jana Sekničková, Ph.D.

32

3.5 Typické konflikty • Konflikt Kuře • Dvě auta jedou proti sobě, kdo uhne, je „kuře“ a jeho reputace klesne • Oba neustoupí (neuhnou) – srážka • Oba uhnou – oba jsou slabí a reputace se jim nezvýší


33

3.5 Typické konflikty • Konflikt Kuře

𝑈 𝑁

𝑈 0,0 1, −1

𝑁 −1,1 −2, −2

• Problém dvou vzájemně nedominovaných sedlových bodů – situace skončí tragicky Mgr. Jana Sekničková, Ph.D.

34

3.5 Typické konflikty • Manželský spor (bitva pohlaví) – BoS • Manželé jdou večer na koncert – rozhodují se mezi Bachem a Stravinským • Muž preferuje Bacha, žena Stravinského • Každý chce jít na koncert a nejraději půjdou spolu • Pokud spolu nepůjdou, nebudou mít žádný užitek Mgr. Jana Sekničková, Ph.D.

35

3.5 Typické konflikty • Manželský spor (bitva pohlaví)

muž/žena 𝐵𝑎𝑐ℎ 𝑆𝑡𝑟𝑎𝑣𝑖𝑛𝑠𝑘𝑖

𝐵𝑎𝑐ℎ 𝑆𝑡𝑟. 2,1 0,0 0,0 1,2

• Opět problém vzájemně nedominovaných sedlových prvků Mgr. Jana Sekničková, Ph.D.

36

3.5 Typické konflikty • Problém několika vzájemně nedominovaných prvků řeší tzv. ústřední rovnováha • Pokud je dána jakási nápověda, který z rovnovážných bodů zvolit, hráči ho zvolí • Manželský spor: pokud se jedná o poslední koncert Bacha ve městě apod. (fotbal vs. nákupy ve skriptech atd.) Mgr. Jana Sekničková, Ph.D.

37

3.6 Kooperativní hra • Předpokládejme nyní, že hráči mohou spolupracovat (ale nemusí) • Před volbou mohou uzavírat závazné dohody • Spolupracovat budou, pokud je to pro ně výhodné – oba mají větší výhru, než když spolupracovat nebudou Mgr. Jana Sekničková, Ph.D.

38

3.6 Kooperativní hra • Příklad 5

1,5 2,2 3,4

4,2 1,9 3,1


2,3 1,4 4,0

39

3.6 Kooperativní hra • Zaručená výhra = kolik hráč získá bez spolupráce – Rovnovážná zaručená výhra – hráči uzavřou dohodu a předpokládají, že ji oba dodrží – Maximinová zaručená výhra – hráči uzavřou dohodu, ale může se stát, že ji někdo poruší


40

3.6 Kooperativní hra • Rovnovážná zaručená výhra – – – –

hráči by se dohodli, že spolupracovat nebudou zvolí tedy sedlový prvek – Nashovu rovnováhu zaručená výhra 1. hráče v(1) zaručená výhra 2. hráče v(2)


41


1,5 2,2 3,4

4,2 1,9 3,1

2,3 1,4 4,0

• v(1) = 3 • v(2) = 4 Mgr. Jana Sekničková, Ph.D.

42

3.6 Kooperativní hra • Maximinová zaručená výhra – hráči se dohodnou, že spolupracovat budou, ale co když protihráč dohodu nedodrží? – kolik dokáže hráč získat, i když mu protihráč bude dělat „naschvály“ – zaručená výhra 1. hráče 𝑣 1 = max𝑖 min𝑗 𝑎𝑖𝑗 – zaručená výhra 2. hráče 𝑣 2 = max𝑗 min𝑖 𝑏𝑖𝑗 Mgr. Jana Sekničková, Ph.D.

43


1,5 2,2 3,4

4,2 1,9 3,1

2,3 1,4 4,0

• v(1) = 3 • v(2) = 2 2

1

0


1 1 3

44

3.6 Kooperativní hra • Symbolem v(1,2) označíme celkovou výhru hráčů při spolupráci • Spolupráce se vyplatí, pokud Kdy se vyplatí spolupracovat? 𝑣 1,2 > 𝑣 1 + 𝑣(2) Jak určit výhru při spolupráci?


45


• 1. hráč: 𝑥2 • 2. hráč: 𝑦3

1,5 2,2 3,4

4,2 1,9 3,1

2,3 1,4 4,0

Kolik celkem získají? 1+4=5 Mgr. Jana Sekničková, Ph.D.

46


1,5 4,2 2,3 2,2 1,9 1,4 3,4 3,1 4,0

6 𝐀+𝐁= 4 7

6 10 4

5 5 4

• 𝑣 1,2 = max𝑖 max𝑗 (𝑎𝑖𝑗 +𝑏𝑖𝑗 ) = 10 Mgr. Jana Sekničková, Ph.D.

47

3.6 Kooperativní hra • Rovnovážná zaručená výhra v(1) = 3 𝟏𝟎 > 𝟑 + 𝟒 v(2) = 4 spolupráce se vyplatí • Maximinová zaručená výhra v(1) = 3 𝟏𝟎 > 𝟑 + 𝟐 v(2) = 2 spolupráce se vyplatí • Výhra při spolupráci Vyplatí se spolupráce? v(1,2) = 10 Mgr. Jana Sekničková, Ph.D.

48


1,5 4,2 2,3 2,2 1,9 1,4 3,4 3,1 4,0

6 A+B= 4 7

6 10 4

5 5 4

• 𝑥 𝑜 , 𝑦 𝑜 = (𝑥2 , 𝑦2 ) … v(1,2) = 10 Mgr. Jana Sekničková, Ph.D.

49

3.6 Kooperativní hra • Zbývá rozhodnout, jak se mají hráči o výhru podělit • Celková výhra musí být rozdělena mezi hráče: 𝒂𝟏 + 𝒂𝟐 = 𝒗(𝟏, 𝟐) • 1. hráč musí dostat hodnotu 𝑎1 , která bude alespoň rovna zaručené výhře: 𝒂𝟏 ≥ 𝒗(𝟏) • 2. hráč musí dostat hodnotu 𝑎2 , která bude alespoň rovna zaručené výhře: 𝒂𝟐 ≥ 𝒗 𝟐 Mgr. Jana Sekničková, Ph.D.

50

3.6 Kooperativní hra a2

• • • •

10

4

0

𝒂𝟏 + 𝒂𝟐 = 𝒗 𝟏, 𝟐 = 𝟏𝟎 𝒂𝟏 ≥ 𝒗 𝟏 = 𝟑 𝒂𝟐 ≥ 𝒗 𝟐 = 𝟒 jádro hry = všechny dvojice (𝑎1 , 𝑎2 ), které splňují uvedené vztahy a1

3

10 Mgr. Jana Sekničková, Ph.D.

51

3.6 Kooperativní hra a2

• 𝒂𝟏 + 𝒂𝟐 = 𝒗(𝟏, 𝟐) • 𝒂𝟏 ≥ 𝒗(𝟏) • 𝒂𝟐 ≥ 𝒗 𝟐

v(1,2)

Kterou možnost z jádra hry vybrat?

v(2)

0

v(1)

a1 v(1,2) Mgr. Jana Sekničková, Ph.D.

52

3.6 Kooperativní hra • Jednou z možností je: – prvnímu hráči dát jeho zaručenou výhru v(1) – druhému hráči dát jeho zaručenou výhru v(2) – zbytek rozdělit mezi hráče rovným dílem 𝑣 1,2 − 𝑣 1 − 𝑣 2 𝑎1 = 𝑣 1 + 2 𝑣 1,2 − 𝑣 1 − 𝑣 2 𝑎2 = 𝑣 2 + 2 Mgr. Jana Sekničková, Ph.D.

53

3.6 Kooperativní hra • 𝒂𝟏 + 𝒂𝟐 = 𝒗 𝟏, 𝟐 = 𝟏𝟎 • 𝒂𝟏 ≥ 𝒗 𝟏 = 𝟑, • 𝒂𝟐 ≥ 𝒗 𝟐 = 𝟒

a2 10

10 − 3 − 4 𝑎1 = 3 + = 4,5 2 10 − 3 − 4 𝑎2 = 4 + = 5,5 2

5,5 4

0

a1 3 4,5

10 Mgr. Jana Sekničková, Ph.D.

54

KONEC Mgr. Jana Sekničková, Ph.D.

55

Teorie her a ekonomické rozhodování. 3. Dvoumaticové hry (Bimaticové hry)

Recommend Documents