Teorie her a ekonomické rozhodování. 4. Hry v rozvinutém tvaru

Teorie her a ekonomické rozhodování 4. Hry v rozvinutém tvaru

4.1 Hry v rozvinutém tvaru • 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

4.1 Hry v rozvinutém tvaru • Hra v rozvinutém tvaru = hra v explicitním tvaru = tahová hra – např. šachy, poker, dáma, go, kostky, … – lze ji zobrazit pomocí stromu hry


3

4.1 Hry v rozvinutém tvaru • Strom hry – souvislý graf (množina uzlů a hran) – s jedním počátečním uzlem (kořen) a – několika koncovými uzly (listy), které reprezentují konec hry – rozhodovací uzly – okamžiky, v nichž dělají hráči svá rozhodnutí


4

4.1 Hry v rozvinutém tvaru • Příklad 1 – Hra Stonožka • Je dán počet tahů (stonožka = 100) • Na začátku hry 1. hráč vyhrává více než dvojnásobek výhry druhého hráče • Hráč na tahu může – buď výhru přijmout – hra končí – nebo výhru nepřijmout – hra pokračuje tak, že se výhry zdvojnásobí a vymění mezi hráči Mgr. Jana Sekničková, Ph.D.

5

4.1 Hry v rozvinutém tvaru Hráči se dohodnou na 5 tazích P 1) n1 = 4; n2 = 1 N kořen: 1 koncové uzly: 6 v1 = 4; v2 = 1 2) n1 = 2; n2 = 8 rozhodovací uzly: 5 v1 = 2; v2 = 8

1) n1 = 16; n2 = 4

v1 = 16; v2 = 4

2) n1 = 8; n2 = 32

v1 = 8; v2 = 32

1) n1 = 64; n2 = 16

v1 = 64; v2 = 16 Mgr. Jana Sekničková, Ph.D.

v1 = 32; v2 = 128 6

4.1 Hry v rozvinutém tvaru • Jak hru řešit? – Zpětnou indukcí – Hru rozložíme na podhry (= část hry, která je sama o sobě hrou) – Začneme posledním rozhodnutím – Označíme optimální volbu a pokračujeme o úroveň výš Mgr. Jana Sekničková, Ph.D.

7

4.1 Hry v rozvinutém tvaru • červeně označená hrana = 1) n1 = 4; n2 = 1 dokonalá rovnováha podhry • racionální je ukončit hru v1 = 4; v2 = 1 2) n1 = 2; n2 = 8 okamžitě (paradox) P

N

v1 = 2; v2 = 8

1) n1 = 16; n2 = 4

v1 = 16; v2 = 4

2) n1 = 8; n2 = 32

v1 = 8; v2 = 32

1) n1 = 64; n2 = 16

v1 = 64; v2 = 16 Mgr. Jana Sekničková, Ph.D.

v1 = 32; v2 = 128 8

4.1 Hry v rozvinutém tvaru • • • • •

Příklad 2 – Ruská ruleta Dva hráči Šestiranný revolver Jediný ostrý náboj (právě jeden) Hráč na tahu může – odstoupit (prohrát) – hra končí – nebo vystřelit (smrt či pokračování hry) Mgr. Jana Sekničková, Ph.D.

9

4.1 Hry v rozvinutém tvaru Je třeba zadat užitky v = 0 … prohra (žije) v = 1 … výhra (žije) v = −10 … smrt (prohra)

1. hráč Odstoupení v1 = 0; v2 = 1

Výstřel

p1 = 1/6 (smrt) v1 = − 10; v2 = 1

p2 = 5/6 (žije) 2. hráč

Odstoupení v1 = 1; v2 = 0

Výstřel p1 = 1/5 (smrt) v1 = 1; v2 = − 10


p2 = 4/5 (žije) 1. hráč 10

4.1 Hry v rozvinutém tvaru • Pravděpodobnosti (smrt, žije) jsou: – – – – – –

1. výstřel: p = (1/6, 5/6) 2. výstřel: p = (1/5, 4/5) 3. výstřel: p = (1/4, 3/4) 4. výstřel: p = (1/3, 2/3) 5. výstřel: p = (1/2, 1/2) 6. výstřel: p = (1, 0) Mgr. Jana Sekničková, Ph.D.

11

4.1 Hry v rozvinutém tvaru konec grafu (2 kulky)

1. hráč


𝐸𝑈(1) = 𝑝1 𝑢1 + 𝑝2 𝑢2 1 1 = −10 + 1 2 2 Výstřel = −𝟒, 𝟓

p1 = 1/2 (smrt) v1 = − 10; v2 = 1

p2 = 1/2 (žije) 2. hráč


Výstřel

p1 = 1 (smrt) v1 = 1; v2 = − 10 Mgr. Jana Sekničková, Ph.D.

p2 = 0 (žije) 12

4.1 Hry v rozvinutém tvaru

střed grafu (4 kulky)

𝐸𝑈(2) 𝐸𝑈(1) = 𝑝1 𝑢1 + 𝑝2 𝑢2 1 23 𝟖 𝟕 = −10 + 1 = − 34 34 𝟑 𝟒 Víme, že zde 1. hráč zvolí odstoupení, tzn. v1 = 0; v2 = 1

1. hráč


Výstřel

p1 = 1/4 (smrt) v1 = − 10; v2 = 1

p2 = 3/4 (žije) 2. hráč


Výstřel

p1 = 1/3 (smrt) v1 = 1; v2 = − 10 Mgr. Jana Sekničková, Ph.D.

p2 = 2/3 (žije) v1 = 1; v2 =13− 10

4.1 Hry v rozvinutém tvaru

začátek grafu (6 kulek) 1. hráč Odstoupení v1 = 0; v2 = 1

𝐸𝑈(2) = 𝑝1 𝑢1 + 𝑝2 𝑢2 𝐸𝑈(1) 1 4 𝟔 5 𝟓 = −10 + 1 = − 5 5 𝟓 6 6 𝟔 Víme, že zde 1. hráč zvolí odstoupení, tzn. v1 = 0; v2 = 1

Výstřel

p1 = 1/6 (smrt) v1 = − 10; v2 = 1

p2 = 5/6 (žije) 2. hráč


Výstřel

p1 = 1/5 (smrt) v1 = 1; v2 = − 10 Mgr. Jana Sekničková, Ph.D.

p2 = 4/5 (žije) v1 = 1; v2 =14− 10

4.1 Hry v rozvinutém tvaru • Výsledek záleží na zvoleném užitku • Při zadaných užitcích je zřejmé, že racionální je ruskou ruletu nehrát a odstoupit při nejbližší možné příležitosti • Užitky mohou však vypadat jinak • Navíc každý z hráčů může mít užitky jiné


15

4.2 Salónní hry • Patří sem zejména kostky, poker a šachy • Nejjednodušší hra NIM (z německého nehmen = brát) – První publikace o hře NIM obecný je z roku 1902 – libovolný počet hráčů – daný počet hromádek – v každé hromádce daný počet kamenů Mgr. Jana Sekničková, Ph.D.

16

4.2 Salónní hry • Příklad 3 – NIM obecný (NIM 2x2) – předpokládejme pro jednoduchost 2 hráče, 2 hromádky, každou s 2 kameny – hráč na tahu si vybere hromádku, která není prázdná a odebere z ní libovolný počet kamenů • minimálně jeden • maximálně všechny, které jsou v dané hromádce • odebírá vždy jen z jedné hromádky

– hráč, který odebere poslední kámen, prohrál Mgr. Jana Sekničková, Ph.D.

17

4.2 Salónní hry na pořadí hromádek nezáleží

1) 2 a 2

2) 2 a 1

1) 2 a 0

2) 1 a 0

0 a 0 (2)

0 a 0 (1)

2) 2 a 0

1) 1 a 1

1) 0 a 1

1) 1 a 0

2) 1 a 0

0 a 0 (1)

0 a 0 (1)

0 a 0 (2)

číslo v závorce = hráč, který odebral poslední kámen a tak tedy prohrál


0 a 0 (2)

18

4.2 Salónní hry zpětná indukce

1) 2 a 2

2) 2 a 1 1) 2 a 0

2) 1 a 0

0 a 0 (1)

2) 2 a 0

1) 1 a 1

1) 0 a 1

1) 1 a 0

2) 1 a 0

0 a 0 (1)

0 a 0 (1)

0 a 0 (2)

• Ať 1. hráč zvolí jakoukoliv 0 a 0 (2) 0 a 0 (2) počáteční strategii, prohraje • Může si jen zvolit, jakým • Toto není typický rozhodovací uzel Ph.D. = průchozí uzel Mgr. Jana Sekničková, 19 způsobem chce prohrát

4.2 Salónní hry • Jedinou dobrou strategií 1. hráče je hru nehrát • Přidání hromádek nebo přidání kamenů jen zvětší rozhodovací strom • Při úplné informaci o hře však známe vítěze (poraženého) předem


20

4.2 Salónní hry • Šachy – Mnohem složitější, než NIM – Po prvním tahu obou hráčů 400 různých pozic – Rozhodovací strom je tedy ohromný (a není ho tedy možné sestavit – ani pomocí počítačů) – Nicméně z herního pohledu jsou stejně nudnou hrou jako NIM – Už před začátkem by hráči měli vědět výsledek Mgr. Jana Sekničková, Ph.D.

21

4.2 Salónní hry • Šachy – Kde je tedy problém? – Zatím se nikomu nepodařilo výsledek spočítat – Platí věta:

Každá konečná hra v rozvinutém tvaru s dokonalou informací má řešení v ryzích strategiích Mgr. Jana Sekničková, Ph.D.

22

4.2 Salónní hry • Šachy – Typická tahová hra v rozvinutém tvaru s dokonalou informací – Každý hráč zná svou pozici i předchozí tahy – Ví tedy, kde v rozhodovacím stromě se nachází – Hra je konečná (opakování tahu v šachu je ošetřeno = 3x opakovaná pozice znamená remízu) Mgr. Jana Sekničková, Ph.D.

23

4.2 Salónní hry • Šachy – Nastane jedna ze 3 možností: • Bílý má vítěznou strategii (1. hráč vyhrává) • Černý má vítěznou strategii (2. hráč vyhrává) • Hra skončí remízou

– Zatím nevíme, která možnost je správná – Ze zkušeností není pravděpodobné, že vítěznou strategii má černý hráč Mgr. Jana Sekničková, Ph.D.

24

4.2 Salónní hry • Šachy – jak je hraje počítač? – Ani počítač nezná strom hry – Konstruuje pouze části stromu – Nezná konec stromu, nemůže tedy hledat řešení pomocí zpětné indukce – Každý uzel se tedy vyhodnocuje pomocí vyhodnocovací funkce


25

4.2 Salónní hry • Šachy – jak je hraje počítač? – Každá pozice je oceněna číslem podle počtu figurek a jejich postavení – Počítač zvolí tah, který vede k pozici s nejvyšším oceněním


26

4.3 Duopol • Příklad 4 – Duopol • Na trhu operují dvě dominantní firmy • První firma vzhledem k hospodářské ztrátě zvažuje tři možnosti – Investovat do reklamy v televizi – Problém neřešit a vyčkat – Uhradit dluhy a ukončit činnost Mgr. Jana Sekničková, Ph.D.

27

4.3 Duopol • Druhá firma na základě dostupných informací zvažuje také své jednání – Investovat do reklamy v tisku – Na zprávy nereagovat a vyčkat

• Zisky obou firem jsou zadány formou dvoumatice • Optimální strategie závisí na časovém faktoru Mgr. Jana Sekničková, Ph.D.

28

4.3 Duopol

𝑇𝑉 𝑁 𝑈

𝑇𝑖𝑠𝑘 −3, −3 −2, +12 +0, +1 Mgr. Jana Sekničková, Ph.D.

𝑁 +9, −2 +7, +9 +8, +7 29

4.3 Duopol Případ 1: Obě firmy realizují svá rozhodnutí současně a nesmí spolupracovat

𝑇𝑉 𝑁 𝑈


𝑁 +9, −2 +7, +9 +8, +7 30

4.3 Duopol Případ 2: Obě firmy realizují svá rozhodnutí současně a smí spolupracovat

𝑇𝑉 𝑁 𝑈


𝑁 +9, −2 +7, +9 +8, +7 31

4.3 Duopol Případ 3: Nejprve se rozhodne první firma a pak zareaguje druhá firma

𝑇𝑉 𝑁 𝑈


𝑁 +9, −2 +7, +9 +8, +7 32

Optimální strategie: 1) TV 2) Nic Zisky +9, –2

4.3 Duopol 1. firma

Ukončit

TV

Nic

2. firma

2. firma

Tisk

-3, -3

Nic +9, -2

Tisk

-2, +12

Nic

+7, +9


2. firma

Tisk

+0, +1

Nic

+8, +7 33

4.3 Duopol Případ 4: Nejprve se rozhodne druhá firma a pak zareaguje první firma

𝑇𝑉 𝑁 𝑈


𝑁 +9, −2 +7, +9 +8, +7 34

Optimální strategie: 1) Ukončit 2) Tisk Zisky +0, +1 Tisk

4.3 Duopol 2. firma

Nereagovat

1. firma

TV -3, -3

Nic

1. firma

Ukončit

-2, +12

+0, +1

TV +9, -2


Nic

Ukončit

+7, +9

+8, +7

35

2. firma 4.3 Duopol • Případ 1: rozhodnutí současně – 1. firma: – 2. firma: – Zisky:

Investovat do TV Případ 2: spolupráce Nereagovat 1. firma: +9, –2 Nedělat nic

• Případ 4: rozhodnutí po sobě – 1. firma: – 2. firma: – Zisky:

2. firma: Nereagovat Zisky: +7, +9

Ukončit činnost Investovat do tisku +0, +1 Mgr. Jana Sekničková, Ph.D.

36

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

37

Teorie her a ekonomické rozhodování. 4. Hry v rozvinutém tvaru

Recommend Documents