Teorie her a ekonomické rozhodování. 2. Maticové hry

Teorie her a ekonomické rozhodování 2. Maticové hry

2.1 Maticová hra • Teorie her = ekonomická vědní disciplína, která se zabývá studiem konfliktních situací – pomocí matematických modelů

• 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

2.1 Maticová hra • Hra v normálním tvaru je dána: – množinou hráčů {1, 2, …, N} předpokládejme pro jednoduchost, že N = 2

– množinou prostorů strategií {X1, X2, …, XN}, kde Xi označuje prostor strategií i-tého hráče předpokládejme pro jednoduchost prostory X a Y, strategie x a y

– množinou výplatních funkcí {f1(x1, x2, …, xN), f2(x1, x2, …, xN), …, fN(x1, x2, …, xN)} předpokládejme pro jednoduchost f1(x,y) a f2(x,y) Mgr. Jana Sekničková, Ph.D.

3

2.1 Maticová hra • Hráči jsou inteligentní: – Maximalizují užitek (hodnotu své výplatní funkce) – Mají dokonalé informace o hře, tzn. znají • Množinu hráčů • Svůj prostor strategií a svou výplatní funkci • Prostory strategií a výplatní funkce ostatních hráčů

• Všichni provádí rozhodnutí najednou Mgr. Jana Sekničková, Ph.D.

4

2.1 Maticová hra • Antagonistický konflikt = co jeden získá, to druhý ztratí (spolupráce nemá smysl) • Hra s konstantním součtem: 𝑓1 𝑥, 𝑦 + 𝑓2 𝑥, 𝑦 = 𝐾 • Hra s nulovým součtem (ekvivalentní): 𝑓1 𝑥, 𝑦 + 𝑓2 𝑥, 𝑦 = 0, a tedy 𝑓1 𝑥, 𝑦 = −𝑓2 𝑥, 𝑦 ≡ 𝑓 𝑥, 𝑦 Mgr. Jana Sekničková, Ph.D.

5

2.1 Maticová 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í a každé lze přiřadit výhru f(x,y) • Všechny tyto výhry lze uspořádat do matice Mgr. Jana Sekničková, Ph.D.

6

2.1 Maticová hra

• • • •

𝑎11 ⋯ 𝑎1𝑛 ⋮ ⋱ ⋮ 𝐴= 𝑎𝑚1 ⋯ 𝑎𝑚𝑛 1. hráč … xi 2. hráč … yj 1. hráč získá aij 2. hráč získá – aij (ztratí aij) Mgr. Jana Sekničková, Ph.D.

7

2.2 Dominování • Příklad 1

• • • •

1 5 2 𝐴= 2 1 1 5 4 3 Optimální strategie (x , y ) 1. hráč volí řádek: X = {x1, x2, x3} 2. hráč volí sloupec: Y = {y1, y2, y3} Kterou strategii 1. hráč určitě nezvolí? Kterou strategii 2. hráč určitě nezvolí? 3

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

3

8

2.2 Dominování • 1. hráč nebude volit řádek se všemi prvky menšími, než jsou odpovídající prvky v jiném řádku (měl by s jistotou nižší zisk) • 2. hráč nebude volit sloupec se všemi prvky většími, než jsou odpovídající prvky v jiném sloupci (měl by s jistotou vyšší ztrátu) • Hráč nikdy nezvolí silně dominovanou strategii … silná dominovanost Mgr. Jana Sekničková, Ph.D.

9

2.2 Dominování • Slabá dominovanost: – Prvky v odpovídajícím řádku jsou menší nebo rovny prvkům v jiném řádku (1. hráč) či – Prvky v odpovídajícím sloupci jsou větší nebo rovny prvkům v jiném sloupci (2. hráč)

• Využívat budeme pouze silnou dominovanost Mgr. Jana Sekničková, Ph.D.

10

2.2 Dominování • Pomocí silné dominovanosti lze – redukovat rozměr matice hry – najít ve speciálních případech optimální strategii (jen zřídka – viz předchozí případ)


11

2.3 Nashova rovnováha • Nashova rovnováha = návod, jak najít optimální strategie hráčů ve hře (maticové) • John F. Nash, Jr. • 1994 Nobelova cena za ekonomii Mgr. Jana Sekničková, Ph.D.

12

2.3 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ě)


13

2.3 Nashova rovnováha • Nashova rovnováha: 𝑥 𝑜 ∈ 𝑋, 𝑦 𝑜 ∈ 𝑌 • 𝑓1 (𝑥, 𝑦 𝑜 ) ≤ 𝑓1 (𝑥 𝑜 , 𝑦 𝑜 ) a • 𝑓2 (𝑥 𝑜 , 𝑦) ≤ 𝑓2 (𝑥 𝑜 , 𝑦 𝑜 ) • Pro hru s nulovým součtem: • 𝑓1 (𝑥, 𝑦) ≡ 𝑓(𝑥, 𝑦) a 𝑓2 𝑥, 𝑦 ≡ −𝑓(𝑥, 𝑦), a tedy • 𝑓(𝑥, 𝑦 𝑜 ) ≤ 𝑓(𝑥 𝑜 , 𝑦 𝑜 ) a

• −𝑓 𝑥 𝑜 , 𝑦 ≤ −𝑓 𝑥 𝑜 , 𝑦 𝑜 𝑜 𝑜 𝑜 → 𝑓 𝑥 , 𝑦 ≥ 𝑓 𝑥 ,𝑦 Mgr. Jana Sekničková, Ph.D.

14

2.3 Nashova rovnováha • Pro hru s nulovým součtem: • 𝑓(𝑥, 𝑦 𝑜 ) ≤ 𝑓(𝑥 𝑜 , 𝑦 𝑜 ) a • 𝑓 𝑥𝑜, 𝑦 ≥ 𝑓 𝑥𝑜, 𝑦𝑜 • Neboli: 𝒇 𝒙, 𝒚𝒐 ≤ 𝒇 𝒙𝒐 , 𝒚𝒐 ≤ 𝒇 𝒙𝒐 , 𝒚 • Nashova rovnováha (Nashovo rovnovážné řešení, rovnovážné strategie) Mgr. Jana Sekničková, Ph.D.

15

2.3 Nashova rovnováha • Nashovu rovnováhu získáme nalezením Sedlového prvku (sedlového bodu) • Sedlový prvek = číslo největší ve svém sloupci a nejmenší ve svém řádku • Vysvětlení: ve hře s nulovým součtem chce 2. hráč minimalizovat výhru prvého hráče a 1. hráč chce maximalizovat ztrátu druhého Mgr. Jana Sekničková, Ph.D.

16

2.3 Nashova rovnováha • Pokud aij je sedlový prvek – xi je optimální strategie prvého hráče – yj je optimální strategie druhého hráče – aij je cena hry

• Toto řešení nazýváme Nashova rovnováha (Nashovo rovnovážné řešení) v ryzích strategiích … optimální strategii hrajeme ve 100 % případů Mgr. Jana Sekničková, Ph.D.

17

2.3 Nashova rovnováha • Příklad 2

1 2 3

4 1 3

2 1 4

• 1 sedlový bod – (𝑥 𝑜 , 𝑦 𝑜 ) = (𝑥3 , 𝑦1 ) Mgr. Jana Sekničková, Ph.D.

18


1 2 2

• 2 sedlové body –

4 3 3

2 2 4

(𝑥 𝑜 , 𝑦 𝑜 ) = (𝑥2 , 𝑦1 ) (𝑥 𝑜 , 𝑦 𝑜 ) = (𝑥3 , 𝑦1 )


19


1 3 2

4 1 3

2 1 4

• žádný sedlový bod Mgr. Jana Sekničková, Ph.D.

20

2.3 Nashova rovnováha • Maticová hra může mít: – 1 sedlový prvek – rovnovážné strategie přímo – více sedlových prvků – všechny mají stejnou cenu hry a jako optimální strategii mohu volit kteroukoliv navrženou – žá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.

21

2.4 Smíšené rozšíření • Příklad 5 – Kámen – nůžky – papír

𝐾 𝑁 𝑃

𝐾 0 −1 +1

𝑁 +1 0 −1


𝑃 −1 +1 0 22

2.4 Smíšené rozšíření • Hra Kámen – nůžky – papír nemá sedlový prvek • Tzn. nemá Nashovu rovnováhu v ryzích strategiích • Přesto známe optimální strategii hráčů hrát každou z možností Jak vyhrát?s pravděpodobností 1/3 Mgr. Jana Sekničková, Ph.D.

23

2.4 Smíšené rozšíření • Pro každého hráče je tedy rovnovážnou strategií vektor (1/3, 1/3, 1/3) • Čísla představují pravděpodobnosti, se kterými hráč hraje jednotlivé strategie • Takto formulované strategie se nazývají smíšené (pravděpodobnostní) strategie


24

2.4 Smíšené rozšíření • Základní věta maticových her: Každá maticová hra má Nashovo rovnovážné řešení (ve smíšených strategiích)


25

2.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í maticové hry • Smíšené rozšíření použijeme, neexistuje-li řešení v ryzích strategiích (tj. neexistuje-li sedlový prvek)


26

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

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

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

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


27

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

𝑛

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

𝑓 𝒙, 𝒚 = 𝑖=1 𝑗=1

• Hodnota výplatní funkce 2. hráče má pouze opačné znaménko (hra s nulovým součtem) • Ryzí strategie = speciální případ smíšených strategií (jednotkové vektory) Mgr. Jana Sekničková, Ph.D.

28

2.4 Smíšené rozšíření • Podle ZVMH 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.

29

2.4 Smíšené rozšíření • Označme cenu hry 𝑣 = 𝐱 𝐨𝐓 𝐀𝐲 𝐨 • Přičtení konstanty c ke všem prvkům v matici nezmění optimální strategie – strategicky ekvivalentní hry

• Změní však cenu hry na v + c • Tento trik umožňuje např. převést hru s konstantním součtem na hru s nulovým součtem Mgr. Jana Sekničková, Ph.D.

30

2.4 Smíšené rozšíření • Pokud jsou všechny prvky matice A kladné, můžeme pokračovat v řešení • Jsou-li některé prvky nekladné, je třeba přičíst vhodnou konstantu tak, aby se všechny prvky staly kladnými


31

2.4 Smíšené rozšíření • Příklad 6 1 −1 2 0 2 1 −1 −2 1 1 0 −1

−1 2 4 2 2 1 +3= 3 5 −2 1 2 1

5 4 4

A co dál? Jak najít optimální strategie? Mgr. Jana Sekničková, Ph.D.

32

2.4 Smíšené rozšíření • Hledáme Nashovu rovnováhu ve smíšených strategiích: 𝐱 𝐓 𝐀𝐲 𝐨 ≤ 𝐱 𝐨𝐓 𝐀𝐲 𝐨 ≤ 𝐱 𝐨𝐓 𝐀𝐲 • Uvedené vztahy ale musí platit i pro ryzí strategie 𝐱 𝐓 = 1,0, … , 0 , 𝐱 𝐓 = 0,1, … , 0 , … , 𝐱 𝐓 = 0,0, … , 1

• 𝐱 𝐓 𝐀𝐲 𝐨 ≤ 𝒗 + 𝒄: 𝑎11 𝑦 𝑜 1 + 𝑎12 𝑦 𝑜 2 + ⋯ + 𝑎1𝑛 𝑦 𝑜 𝑛 ≤ 𝑣 + 𝑐 ⋮ 𝑎𝑚1 𝑦 𝑜 1 + 𝑎𝑚2 𝑦 𝑜 2 + ⋯ + 𝑎𝑚𝑛 𝑦 𝑜 𝑛 ≤ 𝑣 + 𝑐 Mgr. Jana Sekničková, Ph.D.

33

2.4 Smíšené rozšíření 𝑎11 𝑦 𝑜 1 + 𝑎12 𝑦 𝑜 2 + ⋯ + 𝑎1𝑛 𝑦 𝑜 𝑛 ≤ 𝑣 + 𝑐 ⋮ 𝑎𝑚1 𝑦 𝑜 1 + 𝑎𝑚2 𝑦 𝑜 2 + ⋯ + 𝑎𝑚𝑛 𝑦 𝑜 𝑛 ≤ 𝑣 + 𝑐 • Zajistili jsme, že 𝑣 + 𝑐 > 0, můžeme tedy všechny nerovnice vydělit výrazem 𝑣 + 𝑐 • Substituce 𝑞𝑗 =

𝑦𝑜𝑗 𝑣+𝑐

𝑞𝑗 ≥ 0


34

2.4 Smíšené rozšíření 𝑎11 𝑞1 + 𝑎12 𝑞2 + ⋯ + 𝑎1𝑛 𝑞𝑛 ≤ 1 ⋮ 𝑎𝑚1 𝑞1 + 𝑎𝑚2 𝑞2 + ⋯ + 𝑎𝑚𝑛 𝑞𝑛 ≤ 1 𝑞𝑗 ≥ 0

• Omezující podmínky – úloha lineárního programování • Obdobný postup pro druhou nerovnost Mgr. Jana Sekničková, Ph.D.

35

2.4 Smíšené rozšíření • Hledáme Nashovu rovnováhu ve smíšených strategiích: 𝐱 𝐓 𝐀𝐲 𝐨 ≤ 𝐱 𝐨𝐓 𝐀𝐲 𝐨 ≤ 𝐱 𝐨𝐓 𝐀𝐲 • Uvedené vztahy ale musí platit i pro ryzí strategie 𝐲 𝐓 = 1,0, … , 0 , 𝐲 𝐓 = 0,1, … , 0 , … , 𝐲 𝐓 = 0,0, … , 1

• 𝒗 + 𝒄 ≤ 𝐱 𝐨𝐓 𝐀𝐲: 𝑥 𝑜 1 𝑎11 + 𝑥 𝑜 2 𝑎21 + ⋯ + 𝑥 𝑜 𝑚 𝑎𝑚1 ≥ 𝑣 + 𝑐 ⋮ 𝑥 𝑜 1 𝑎1𝑛 + 𝑥 𝑜 2 𝑎2𝑛 + ⋯ + 𝑥 𝑜 𝑚 𝑎𝑚𝑛 ≥ 𝑣 + 𝑐 Mgr. Jana Sekničková, Ph.D.

36

2.4 Smíšené rozšíření 𝑥 𝑜 1 𝑎11 + 𝑥 𝑜 2 𝑎21 + ⋯ + 𝑥 𝑜 𝑚 𝑎𝑚1 ≥ 𝑣 + 𝑐 ⋮ 𝑥 𝑜 1 𝑎1𝑛 + 𝑥 𝑜 2 𝑎2𝑛 + ⋯ + 𝑥 𝑜 𝑚 𝑎𝑚𝑛 ≥ 𝑣 + 𝑐 • Zajistili jsme, že 𝑣 + 𝑐 > 0, můžeme tedy všechny nerovnice vydělit výrazem 𝑣 + 𝑐 • Substituce 𝑝𝑖 =

𝑥𝑜𝑖 𝑣+𝑐

𝑝𝑖 ≥ 0


37

2.4 Smíšené rozšíření 𝑎11 𝑝1 + 𝑎21 𝑝2 + ⋯ + 𝑎𝑚1 𝑝𝑚 ≥ 1 ⋮ 𝑎1𝑛 𝑝1 + 𝑎2𝑛 𝑝2 + ⋯ + 𝑎𝑚𝑛 𝑝𝑛 ≥ 1 𝑝𝑖 ≥ 0 • Omezující podmínky – úloha lineárního programování • Uvedené úlohy = duálně sdružené (vhodná formulace účelových funkcí) Mgr. Jana Sekničková, Ph.D.

38

2.4 Smíšené rozšíření • Primární problém •

𝑛 𝑗=1 𝑎𝑖𝑗 𝑞𝑗

≤ 1, ∀𝑖

• 𝑞𝑗 ≥ 0, ∀𝑗 • max

𝑛 𝑗=1 𝑞𝑗

• Duální problém •

𝑚 𝑖=1 𝑎𝑖𝑗 𝑝𝑖

≥ 1, ∀𝑗

• 𝑝𝑖 ≥ 0, ∀𝑖 • min


𝑚 𝑖=1 𝑝𝑖

39

2.4 Smíšené rozšíření • Řešíme tedy klasickou úlohu LP (např. simplexovou metodou) • Oba sdružené problémy mají stejnou 1 hodnotu účelové funkce =𝑧 𝑣+𝑐

• Primární úloha: optimum pro 2. hráče • Duální úloha: optimum pro 1. hráče (stínové ceny) Mgr. Jana Sekničková, Ph.D.

40

2.4 Smíšené rozšíření • Zpětná substituce • 𝑞𝑗 = • 𝑝𝑖 =

𝑦𝑜 𝑗

𝑣+𝑐 𝑥𝑜𝑖 𝑣+𝑐

→

𝑦𝑜

𝑗

= 𝑣 + 𝑐 𝑞𝑗 =

→ 𝑥 𝑜 𝑖 = 𝑣 + 𝑐 𝑝𝑖 =

𝑞𝑗

𝑧 𝑝𝑖 𝑧

• Podobně hodnota účelové funkce •

1 𝑣+𝑐

=𝑧

→

1 𝑧

𝑣 = −𝑐

→


𝑐𝑒𝑛𝑎 ℎ𝑟𝑦

41

2.4 Smíšené rozšíření • Příklad 6 1 −1 0 2 −1 −2

2 1 1

→

4 2 5 3 5 4 2 1 4

4𝑞1 + 2𝑞2 + 5𝑞3 ≤ 1 3𝑞1 + 5𝑞2 + 4𝑞3 ≤ 1 2𝑞1 + 1𝑞2 + 4𝑞3 ≤ 1 𝑞1 , 𝑞2 , 𝑞3 ≥ 0 max 𝑧 = 𝑞1 + 𝑞2 + 𝑞3 Mgr. Jana Sekničková, Ph.D.

42

2.4 Smíšené rozšíření Řešení: • 𝐪𝐓 = 0.21, 0.07, 0 • 𝐩𝐓 = 0.14, 0.14, 0 • 𝑧 = 0.28 Po substituci: 𝐓

• 𝐲 =

3 1 , ,0 4 4

𝐓

𝐱 =

1 −1 2 0 2 1 −1 −2 1 1 1 , ,0 2 2


𝑣 = 0.57 43

2.4 Smíšené rozšíření • Poznámky: – – – –

prvky upravené matice A jsou kladné obě úlohy mají přípustné řešení obě úlohy mají optimální řešení řešení duální úlohy v simplexové tabulce primární úlohy pod přídatnými proměnnými (stínové ceny)


44

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

45

Teorie her a ekonomické rozhodování. 2. Maticové hry

Recommend Documents