VYSOKÁ ŠKOLA EKONOMICKÁ V PRAZE FAKULTA INFORMATIKY A STATISTIKY Obor: Statistika a ekonometrie
Název bakalářské práce
Model tahové hry s finančními odměnami
Autor: Vedoucí bakalářské práce: Rok: 2009
Markéta Erbsová Doc. Ing. Mgr. Martin Dlouhý, Dr., MSc.
Prohlášení: Prohlašuji, že jsem bakalářskou práci na téma „Model tahové hry s finančními odměnami“ zpracovala samostatně. Veškerou použitou literaturu a další podkladové materiály uvádím v seznamu použité literatury.
Praha, 15.5.2009
Markéta Erbsová
Poděkování: Na tomto listu bych ráda poděkovala Doc. Ing. Mgr. Martinu Dlouhému, Dr., MSc. za jeho odborné vedení při utváření mé bakalářské práce. Dále svému tátovi za spoluautorství hry Výměna a všem hráčům, kteří kdy tuto hru hráli a hrát budou.
Obsah OBSAH ....................................................................................................................................................... 4 1.
ÚVOD ................................................................................................................................................ 5
2.
TEORIE HER................................................................................................................................... 6 2.1 2.2 2.3 2.4
3.
HRA V EXPLICITNÍM TVARU ................................................................................................. 17 3.1 3.2 3.3
4.
ZÁKLADNÍ POJMY ...................................................................................................................... 6 TYPY ROZHODOVACÍCH SITUACÍ................................................................................................ 7 ANTAGONISTICKÉ HRY ............................................................................................................ 10 NEANTAGONISTICKÉ HRY ........................................................................................................ 12 2.4.1 Nekooperativní hra dvou hráčů.......................................................................................13 2.4.2 Kooperativní hra dvou hráčů..........................................................................................15
ZÁKLADNÍ CHARAKTERISTIKY HRY V EXPLICITNÍM TVARU ..................................................... 17 HRA STONOŽKA ...................................................................................................................... 18 HRA RUSKÁ RULETA............................................................................................................... 19
HRA VÝMĚNA ............................................................................................................................. 21 4.1. 4.2. 4.3. 4.4. 4.5. 4.6.
CHARAKTERISTIKA HRY VÝMĚNA ........................................................................................... 21 PRAVIDLA HRY VÝMĚNA ......................................................................................................... 22 MATEMATICKÉ VYJÁDŘENÍ HRY VÝMĚNA PRO JISTÁ KOLA ..................................................... 25 JISTÁ KOLA HRY VÝMĚNA A JEJICH GRAFICKÉ VYJÁDŘENÍ ...................................................... 29 NEJISTÁ KOLA HRY VÝMĚNA A JEJICH GRAFICKÉ VYJÁDŘENÍ.................................................. 31 VÝDEJ, PŘEDÁNÍ, ZHODNOCENÍ POUKÁZEK A OPTIMÁLNÍ ŘEŠENÍ HRY VÝMĚNA ..................... 33
5.
ZÁVĚR ............................................................................................................................................ 38
6.
LITERATURA ............................................................................................................................... 39
4
1. Úvod Když se řekne teorie her, pravděpodobně to v každém z nás evokuje dětství a bezstarostný svět. Než však přistoupím k samotné hře, uvedu základní pojmy, které teorie her při zkoumání a popisu užívá. Neboť každá vědecká disciplína, stejně tak teorie her, je postavena na pevných základech, z nichž při popisu konkrétních situací vycházíme. Pokusím se vyložit základní typy rozhodovacích situací a kritéria podle kterých se tyto situace třídí. Postupně se omezím na tahové hry. Vždyť šachy, dámu nebo go snad každý zná a většina je hrála nebo alespoň hrát se pokoušela. Mým záměrem není objasnit tyto známé hry, ale pokusit se popsat a analyzovat původní hru Výměna, která se o principy tahových her opírá. Hra Výměna je hrou původní a její myšlenka vznikla v roce 2007. Smyslem této tahové hry by mělo být především pobavení, ale cílem může být i praktické uplatnění. Jako tahová hra s finančními odměnami by mohla být použita v rámci finančnictví a s ním spjatých subjektů a oborů. Toto je však pouze předpoklad, který v praxi nebyl potvrzen ani vyvrácen. Hlavním cílem této práce je tedy teoretický rozbor hry Výměna, kterou popíši herními pravidly, v nichž bude hra rozložena na dvě části. První část bude vycházet z modelového případu tahové hry Stonožka a druhá část se bude držet principů tahové hry Ruská ruleta. Matematicky a graficky se pokusím vyjádřit první část hry. Druhou část pak popíši grafickým schématem. V neposlední řadě hru jako takovou dle teorie charakterizuji a představím.
5
2. Teorie her 2.1 Základní pojmy Teorie her zkoumá a pomocí matematického aparátu modeluje rozhodovací situace v nichž dochází ke konfliktu mezi subjekty, ke hře mezi hráči. Rozhodovacích situací je v našem světě nespočet, své rozhodnutí v nich volí subjekt „hráč“ anebo více subjektů „hráči“. Subjektem se pak myslí aktivní účastník rozhodovací situace. Může jím být fyzická osoba, právnická osoba, instituce nebo náhodný mechanismus. Takovouto situací je karetní hra, dělba státního rozpočtu mezi jednotlivé instituce anebo boj o místo v potravním řetězci. Každý hráč vybírá z množiny svých strategií pro něj tu nejvýhodnější, optimální strategii, dle hodnoty výplatní funkce. Na každou ze strategií přitom připadá jedna výplatní funkce, která určuje výsledek hry . Hráč svým rozhodnutím pro danou strategii ovlivňuje nejen svou výplatní funkci, ale také výplatní funkce svých protihráčů. A naopak, protihráči rovněž svým rozhodnutím ovlivňují hráčovu výplatní funkci. Pro hráče hodnota výplatní funkce znamená zisk, výhru nebo užitek a je tvořena kombinacemi rozhodnutí všech účastníků hry. Výhra nemusí být vždy kladně ohodnocena, je-li tomu tak, pak výsledkem je záporná výhra, nebo-li prohra. Stanovíme-li, že je hráč inteligentní, znamená to, že jeho chování bude směřovat k maximalizaci zisku, výhry nebo užitku. Inteligentní hráč, by neměl vstoupit do rozhodovací situace s vidinou prohry. Pokud tak učiní, nenazveme jej inteligentním. Teorie her volí za základní logický prvek konflikt a pomocí jednoduchého matematického zobrazení jej formalizuje. Jedná se o základní matematický model teorie her, o „Hru v normálním tvaru“, která popisuje konflikt pomocí tří množin.
1. Q = {1, 2, ... , N} Q je množina konečného počtu hráčů, kde hráči jsou označeni čísly 1,2, .. , N.
2. Xi = {X1, X2, ... , XN} Xi je množina prostoru strategií i-tého hráče, pro kterou platí i ∈ Q .
6
3. Mi(x) = {M1(x), M2 (x), ... , MN(x)} x je uspořádaná N-tice strategií, kterou volí jednotliví hráči. Mi(x) je výplatní funkcí i-tého hráče, která mu při zvolené strategii přiřadí danou výplatu. Pro Mi(x) ≤ 0, hovoříme o prohře. Naopak pro Mi(x) ≥ 0 se jedná o výhru. Zjednodušený zápis hry v normálním tvaru, popíšeme následně: {Q; X1, X2, …, XN; M1(x), M2(x), …, MN(x)}
Pokud se účastníci rozhodovacích situací mohou seskupovat do koalic a je to pro ně z hlediska zvýšení výhry výhodné, pak použijeme matematický model hry ve tvaru charakteristické funkce. Charakteristická funkce hry přiřazuje výplaty nikoliv hráčům, ale koalicím a je tvořena součtem výher členů koalice.
Pokud hrajeme hru v normálním tvaru a je založena na po sobě jdoucích tazích, užijeme matematický model hry v explicitním tvaru. O tomto případě bude na následujících stránkách podrobněji pojednáno ve 3.kapitole a v souvislosti s hrou Výměna ve 4.kapitole.
2.2 Typy rozhodovacích situací Jedním z hlavních cílů teorie her, je nalezení optimální strategie v rozhodovací situaci. Není však jednoduché, spíše ani možné, z hlediska různorodosti rozhodovacích situací nalézt zaručený postup při volbě optimální strategie. Budeme proto vycházet z několika základních kritérií pro volbu typu konfliktní situace:
Počet účastníků konfliktu
Možnost tvorby koalic
Náhodný mechanismus
Informovanost účastníků konfliktu
Počet možných strategií
Závislost součtu výher a jejich dělení
7
Podle počtu účastníků konfliktu, rozlišíme hru s jedním, dvěma a s více hráči. Situace, kdy účastník konfliktu je pouze jeden (N=1) je případem, kdy hráč má plnou kontrolu nad výslednou hodnotou své výplatní funkce. Hru s právě dvěma účastníky konfliktní situace (N=2) a její teoretické výsledky lze použít pro zobecnění her, kde je počet účastníků konfliktní situace větší jak dva (N>2). Takovéto zjednodušení uplatníme ve hře Výměna. Možnost tvorby koalic, tedy seskupení n-hráčů z množiny N = {1, 2, ... , N}. Koalicí nazveme množinu S, pro níž platí S ⊂ N . Pokud koalici tvoří všichni účastníci konfliktu, vzniká velká koalice. Druhým krajním případem je jednoprvková koalice, která je tvořena pouze jedním hráčem. Členové koalice společně spolupracují při volbě strategií. Zpravidla k tvorbě koalic dochází při větším počtu hráčů, N>2. Náhodný mechanismus nebo také neinteligentní účastník. Je opakem inteligentního rozhodovatele. Náhodný mechanismus volí svou strategii podle rozložení pravděpodobností na prostoru svých strategií bez ohledu na výši výplatní funkce. Nesnaží se maximalizovat svou výhru. Typicky neinteligentním hráčem je například příroda, která je svým chováním nevyzpytatelná. V konfliktu o dvou hráčích, z čehož jeden je inteligentním a druhý je náhodným mechanismem, nelze hovořit jako o konfliktu zájmů. Zavádí se proto označení rozhodování při riziku (kdy inteligentní účastník zná rozložení pravděpodobností náhodného mechanismu) a rozhodování při neurčitosti (inteligentní účastník rozložení pravděpodobností náhodného mechanismu nezná). Ve hře Výměna se nevyskytuje náhodný mechanismus. Informovanost účastníků konfliktu, lze dělit na informovanost ne/úplnou a ne/dokonalou. Termín ne/úplná informovanost zavádíme, pokud se jedná o okolnosti vzniklé před zahájením hry. Informovanost ne/dokonalá vzniká okolnostmi vzniklými během hry. Hra Výměna, kterou budeme ve 4.kapitole analyzovat je hra s úplnou a dokonalou informací. Počet možných strategií, ve kterých hledáme optimální řešení může být konečný nebo nekonečný počet. V prvním případě, kdy je konečný počet strategií, se jedná o konečné hry. V druhém případě, kdy vybíráme z nekonečného počtu strategií, hovoříme o hře nekonečné. Výměna je hrou s konečným počtem strategií.
8
Závislost součtu výher a jejich dělení se uskutečňuje na konci hry, kdy je známa výplatní funkce, závislá na konečné zvolené strategii. Rozlišujeme dva typy her.
1. Hra s konstantním součtem, je speciálním případem hry v normálním tvaru. Jedná se o antagonistický konflikt (co jeden hráč získá, druhý ztrácí). Zájmy hráčů jsou v přímém protikladu. Nemá smysl uvažovat o spolupráci mezi hráči. Pro výplatní funkci N hráčů platí,
M1(x)+M2(x)+ … +MN(x) = K, kde M1(x), ... , MN(x) je součet výplatních funkcí N hráčů, x = 1, 2, ..., N a K je pevně daná konstanta (libovolné reálné číslo) nezávislá na volbě strategií. Analogicky je výplatní funkce pro dva hráče dána: M1(x1,x2) +M2(x1,x2) = K. V případě, že je K=0 lze hovořit o hře s nulovým součtem, pokud přičteme konstantu u všech hodnot výplatních funkcí, řešení se nemění. U hry o dvou hráčích pro výplatní funkce platí: M1(x1,x2) = (-M2(x1,x2)). 2. Hra s nekonstantním součtem, je typem neantagonistického konfliktu. Hráči svými rozhodnutími sledují své vlastní zájmy, které nejsou v přímém protikladu k ostatním hráčům. Výhra jednoho neznamená prohru druhého. V tomto případě rozlišujeme situace, kdy hráči kooperují nebo nekooperují. Zda hráči budou chtít a moci kooperovat bude záviset na hodnotě výplatní funkce, o kterou se na konci hry podělí. Hodnota výplatní funkce je ovlivněna volbou strategie jednotlivých hráčů. Hráči by měli volit takové strategie, které povedou k co největší hodnotě výplatní funkce, v případě kooperace. Pro výplatní funkci N hráčů platí,
M1(x)+M2(x)+ … +MN(x) = φ(x), kde M1(x), ... , MN(x) je součet výplatních funkcí N hráčů, x = 1, 2, ..., N a φ(x) je funkce, která je definovaná na množině x = x1* x2 * ... * xN. Pro výplatní funkci dvou hráčů platí: M1(x1,x2) +M2(x1,x2) = φ(x1,x2). U kooperace rozlišujeme dva základní typy dělení výher. Hry s nepřenosnou výhrou, kdy hráč získá výhru, která je určena hodnotou jeho výplatní funkce. 9
Vhodnou spoluprácí může hráč tuto hodnotu navýšit. Druhým typem je hra s přenosnou výhrou. V tomto případě hráči spolupracují tak, aby celková částka, o kterou se na konci hry rozdělí byla co nejvyšší a každému z nich přinesla výnos. To znamená v případě, že by hráč volil takovou strategii, při které si sám nepolepší, ale dá možnost jinému hráči svým rozhodnutím dosáhnout vyšší hodnoty výplatní funkce než on sám a poté se o jeho zisk (určen opět hodnotou výplatní funkce) společně a spravedlivě podělí.
2.3 Antagonistické hry Při popisování antagonistických her se zaměříme na popis hry v případě kdy N=2, hru hrají právě dva inteligentní hráči. Společně se dělí o konstantní výhru, jejíž výše není závislá na volbě strategií. Výhra je rozložena mezi oba dva hráče, její rozložení je určeno výplatními funkcemi hráčů. V antagonistické hře hráči sledují pouze svůj prospěch a jejich zájmy jsou protichůdné. To co jeden z hráčů ztratí, druhý získá. Vylučuje se zde jakákoliv spolupráce. Vycházíme z matematického modelu hry s konstantním součtem v normálním tvaru. Výplatní funkce pro dva hráče je dána,
M1(x,y) +M2(x,y) = K, kde prostor strategií prvního hráče označíme X, x ∈ X a prostor strategií druhého hráče Y, y ∈ Y . K je konstanta (libovolné reálné číslo), nezávislá na volbě zvolených strategií. Mi(x,y) je výplatní funkce i-tého hráče, i=1,2. _
_
Optimální strategie, jsou zapisovány x ∈ X a y ∈ Y . Jsou to takové strategie, při nichž je nalezeno rovnovážné řešení vyhovující obou hráčům. Pokud první hráč _
_
zvolí strategii x ∈ X , pak existuje optimální strategie druhého hráče y ∈ Y a pro výplatní funkce hráčů platí: _
_
_
_
_
_
M 1 ( x , y ) ≤ M 1 ( x , y ) a M 2 ( x, y ) ≤ M 2 ( x, y )
10
Abychom mohli hru vyjádřit v maticové podobě a určit rovnovážné řešení hry pomocí rovnovážného prvku v matici, uvažujeme případ, kdy konstanta K je rovna nule. U hry s nulovým součtem se výplatní matice obou hráčů liší pouze o znaménko:
M1(x,y) = -M2(x,y) = M(x,y) To znamená, že můžeme sledovat pouze jednu výplatní matici, například výhru pro prvního hráče. Výsledky, které pak z maticové podoby získáme, hovoří o výhře prvního hráče a o prohře druhého hráče. Zjednodušený zápis nerovností má tvar: _
_
_
_
M ( x, y ) ≤ M ( x, y ) ≤ M ( x, y )
„ Ten kdo se odchýlí od optimální strategie si nemůže polepšit“. [1]
Vycházíme-li z konečného počtu strategií pro oba hráče, pak prostor strategií prvního hráče je X = {1, 2, ... , m} a prostor strategií druhého hráče je Y ={1, 2, ... , n}. Výplatní funkce hráčů jsou definované na kartézském součinu X*Y, což je množina prvků, která má m*n prvků. Obecné vyjádření maticové hry vypadá následně:
a11 , a12 , K , a1n a 21 , a 22, K , a 2 n A= K K K K a , a , K ,a mn m1 m 2
Matice A je tvořena m řádky a n sloupci. Řádky jsou přiřazené strategiím prvního hráče a sloupce jsou přiřazeny strategiím druhého hráče. Hodnoty výplatní funkce M(x,y) = aij pro
x ∈ X a y ∈ Y . Nashovu rovnováhu (rovnovážné řešení) v ryzích strategií
nalezneme pomocí sedlového prvku matice, udávajícím cenu hry. Sedlový prvek je
číslo, kterým první hráč maximalizuje svou výhru a druhý hráč minimalizuje výhru prvního hráče. Hledaný prvek je minimální hodnota v řádku, ve kterém se nalézá (první hráč) a maximální hodnota ve sloupci, ve kterém se nalézá (druhý hráč). V případě, že je nalezen sedlový prvek aij , pak i-tá strategie prvního hráče a j-tá strategie druhého jsou rovnovážnými strategiemi. Je-li v matici sedlových prvků nalezeno více, pak jsou nalezená rovnovážná řešení vzájemnými alternativami, určující alternativní strategie.
11
Pokud není nalezen sedlový prvek matice, není nalezena Nashova rovnováha v ryzích strategiích. Základní věta maticových her nám však říká:
„ Každá maticová hra má Nashovo rovnovážné řešení ve smíšených strategií.“ [1]
Optimální řešení lze najít ve smíšeném rozšíření maticové hry, kdy jednotlivé prostory strategií volíme podle hodnot jejich vektorů pravděpodobností. Pro prostory strategií dvou hráčů ve hře s nulovým součtem, při konečném počtu strategií platí: m → → →T X 5 = x, x = [x1 , x 2 , K , x m ], ∑ xi = 1, x ≥ 0 i =1
n → → →T Y 5 = y, y = [ y1 , y 2 ,K , y m ], ∑ y j = 1, y ≥ 0 j =1
Výplatní funkce je dána tvarem: → →
m
→T
n
→
M 5 ( x , y ) = ∑∑ xi aij y j = x A y i =1 j =1
Při hrách s konstantním součtem sledujeme pouze výplatní funkci prvního hráče. Její hodnota nám udává střední očekávanou hodnotu výhry. Nutno podotknout, že ryzí strategie, z prostoru prvků strategií x ∈ X a y ∈ Y jsou zvláštní podmnožinou smíšených
strategií,
z prostoru
prvků
strategií
x∈ X 5
a
y ∈Y 5 .
Všechny
pravděpodobnosti jsou rovny nule a jedna z pravděpodobností je rovna jedné. Pro Nashovu rovnovážnou strategii v případě smíšeného rozšíření platí: _
_T
_
_T
x Ay ≤ x Ay ≤ x Ay T
Hráč si volbou jiné strategie nemůže polepšit. Může si pouze pohoršit, v lepším případě na tom zůstane stejně.
2.4 Neantagonistické hry V neantagonistických hrách vyjdeme z předpokladu N=2, v konfliktu se vyskytují dva hráči. Rozhodnutí učiněna dvěmi inteligentními hráči jsou zaměřena na jejich vlastní zájmy. Neplatí však, že rozhodnutí jednoho je vždy v přímém protikladu s rozhodnutím druhého.
12
Pokud je možná spolupráce mezi hráči, pak je její realizování vždy závislé na přínosu, který z ní pro oba dva hráče plyne. Zároveň musí být splněno, že je přínos ze spolupráce vyšší, než kdyby hrál každý sám za sebe. Matematickým modelem neantagonistického konfliktu je hra dvou hráčů s nekonstantním součtem. Jakým způsobem hledáme odpověď k otázce, zda kooperovat či nikoliv. Nejjednodušším postupem je vyřešit nejdříve maticovou hru, kdy dva hráči nekooperují a pak se zabývat vzájemnou kooperací.
2.4.1 Nekooperativní hra dvou hráčů
Máme konečnou neantagonistickou hru o dvou hráčích. Hráči nemají možnost nebo pro ně není výhodné uzavírat smlouvy ani závazné dohody. Matematickým modelem této hry je dvoumaticová hra, která je určena dvěmi maticemi.
a11 , a12 , K , a1n a 21 , a 22, K , a 2 n A= K K K K a , a , K ,a mn m1 m 2
b11 , b12 , K , b1n b21 , b22, K , b2 n B= K K K K b , b , K ,b mn m1 m 2
Matice A i B jsou tvořeny m-řádky a n-sloupci. Matice A charakterizuje výplatní funkce prvního hráče. Matice B charakterizuje výplatní funkce druhého hráče.
Pro zjednodušení používáme zápis pomocí jedné tabulky ve tvaru dvojmatice:
a11 , b11 , a12 , b12 , K , a1n , b1n a 21 , b21 , a 22 , b22 ,K , a 2 n , b2 n K K K K K KK a , b , a , b K ,a , b mn mn m1 m1 m 2 m 2
Řádky dvojmatice odpovídají strategiím prvního hráče, její sloupce pak strategiím druhého hráče. Pokud první hráč volí strategii i-tou a druhý hráč strategii j-tou, pak výhra prvního hráče je aij a výhra druhého hráče je bij.
13
V rámci nekooperativní teorie se užívá pojmu modifikované Nashovo
rovnovážné řešení, které se uplatní při hledání rovnovážného řešení v ryzích strategií. _
_
Nashovi rovnovážné strategie x a y jsou takové strategie, při nichž je nalezeno rovnovážné řešení vyhovující obou hráčům. Jsou definované stejně jako v případě antagonistického konfliktu. S platným předpokladem, že hráč volící jinou než rovnovážnou strategii si může jen pohoršit, v lepším případě na tom zůstat stejně. Rovnovážného řešení v ryzích strategiích docílíme tak, že v bimaticové hře první hráč volí maximální hodnotu v řádku matice A, ve všech existujících řádcích a druhý hráč volí maximální hodnotu ve sloupci matice B, ve všech existujících sloupcích. Rovnovážné řešení je nalezeno, pokud je jedním i druhým hráčem označena hodnota z téže dvojice prvků. V ryzích strategiích mohou nastat případy nalezení právě jednoho
řešení. Rovnovážných řešení je nalezeno více, ale není jisté, pro které se jeden nebo druhý hráč rozhodne. Jejich rozhodnutí záleží na preferencích k jednotlivým rovnovážným řešením a ne vždy se na volbě shodnou. Rovnovážných řešení je nalezeno více, jedno z nich je pro oba hráče nejvýhodnější a preferují (volí) ho oba dva hráči (dominuje nad ostatními). Posledním možným případem je nenalezení rovnovážného
řešení
v ryzích
strategiích.
případě
V tomto
použijeme
smíšené
rozšíření
dvoumaticových her. Za platnosti věty: „ Smíšené rozšíření každé dvoumaticové hry má alespoň jedno rovnovážné řešení“. [1]
Prostory strategií jsou dány matematickým zápisem: m → → →T X = x, x = [x1 , x 2 , K , x m ], ∑ xi = 1, x ≥ 0 i =1 n → → →T Y = y, y = [ y1 , y 2 , K, y m ], ∑ y j = 1, y ≥ 0 j =1
Výplatní funkce pro prvního a druhého hráče jsou dány tvarem: → →
m
n
→T
→
→T
→
M 1 ( x , y ) = ∑∑ xi aij y j = x A y i =1 j =1
→ →
m
n
M 2 ( x , y ) = ∑∑ xi bij y j = x B y i =1 j =1
14
Rovnovážné strategie v případě smíšeného rozšíření dvoumaticových her, hledáme jako optimální řešení úlohy nelineárního programování dané ve tvaru: z = p T ( A + B)q − e T p − f T → max za podmínek Aq ≤ e BT p ≤ f p≥0 q≥0 Kde z je účelová funkce, jejíž hodnotu maximalizujeme. A je výplatní matice prvního hráče, B je výplatní matice druhého hráče, obě matice jsou o rozměrech m*n. Vektor p je tvořen m-proměnnými a vektor q o n-proměnných. Vektor e je složen z m-jedniček a vektor f o n-jedničkách.
_
_
Smíšené rovnovážné strategie x a y a jejich řešení dostaneme po transformacích zajišťujících , že součet pravděpodobností je roven jedné, platí: _
_
_
_
_
_
x = p/(e T p ) a y = q/(e T q ) Pro hledání více jak jednoho optimálního řešení volíme nejčastěji řešením úlohy z různých hodnot proměnných a sledujeme zda se bude měnit optimální řešení.
2.4.2 Kooperativní hra dvou hráčů
V konečné neantagonistické hře dvou inteligentních hráčů, lze uzavírat smlouvy a závazné dohody. Tímto faktem se schéma rozhodovací situace zásadně mění. Hráči se před samotnou hrou dohodnou jak budou při hře společně postupovat. V dohodách bývá zakotveno jakým způsobem si budou přerozdělovat výhru. Kdy jeden z hráčů učiní takové rozhodnutí, kterým umožní druhému hráči dosáhnout na jinak nedosažitelný celkový zisk, na úkor svého vlastního obětovaného zisku. Předpokládáme, že hráčům se spolupráce vyplatí a přináší pro oba větší výhry než kdyby nespolupracovali. U kooperativního konfliktu je třeba zjistit výši výhry, za předpokladu, že hráči nekooperují. Výši výhry zjistíme nalezením Nashova optimálního řešení nekooperativní hry a označíme ji jako zaručenou výhru.
15
Pro prvního hráče je zaručená výhra dána hodnotou v(1), platí:
v(1) = max min M 1 ( x, y ) y∈Y
x∈X
Pro druhého hráče je zaručená výhra dána hodnotou v(2), platí:
v(1) = max min M 2 ( x, y ) y∈Y
x∈ X
Maximální celková výhra obou inteligentních hráčů při možnosti kooperovat je dána hodnotou v(1,2) a platí pro ni: v(1,2) = max[M 1 ( x, y ) + M 2 ( x, y )] x∈X y∈Y
Pro hráče je výhodné spolupracovat a uzavírat závazné dohody a smlouvy, pokud celková částka ze spolupráce v(1,2) je větší jak součet jednotlivých zaručených výher prvního v(1) a druhého v(2) hráče. Nastane pokud: v(1,2) > v(1) + v(2) . To co hráči dostanou navíc bude kladná hodnota, přebytek, kdy od celkové výhry v(1,2) odečtou své zaručené výhry v(1) a v(2), tj. v(1,2)-v(1)-v(2).
Další otázkou je jakým způsobem se o maximální celkovou výhru v(1,2) budou hráči dělit. Pro oba hráče bude přijatelná taková dvojice částek a1 a a2 , pro kterou platí:
a1 + a 2 = v(1,2) a1 ≥ v(1) a 2 ≥ v ( 2)
Kde a1 je částka, kterou z celkové výhry v(1,2) dostane první hráč a a2 je částka, kterou dostane druhý hráč. Dvojici částek a1 a a2 nazveme rozdělením. Hráči se rozdělí o celkovou společnou výhru. Oba hráči musí zároveň dostát minimálně takové výhry, kterou si jsou sami schopni zajistit bez kooperace. Množinu všech rozdělení (a1 , a2 ), která splňuje uvedené podmínky nezveme jádrem hry. Jádro hry je znázorňováno graficky v podobě úsečky, na které leží všechny kombinace možného rozložení celkové výhry plynoucí z kooperace. Otázkou je, jaký bod na úsečce zvolit. Každý hráč se snaží maximalizovat svou výhru.
16
3. Hra v explicitním tvaru 3.1 Základní charakteristiky hry v explicitním tvaru Rozhodovací situaci, která je založena na po sobě jdoucích tazích, popisujeme modelem hry v explicitním tvaru. Jiným označením tohoto modelu je hra v rozvinutém tvaru nebo tahová hra. Příkladem jsou různé salónní hry, karetní hry, dáma, šachy a také hra Výměna. Hráči své tahy uskutečňují střídavě. Je-li první hráč na tahu, pak volba jeho strategie ovlivní rozhodnutí druhého hráče, který bude na jeho tah nějakým způsobem reagovat. Otázkou je jakou zvolit posloupnost tahů, aby bylo dosaženo optimum. Odhadnout jak bude spoluhráč nebo soupeř na mé tahy reagovat. Tahové hry mají svá herní pravidla, která jasně určují počátek, průběh a konec hry. Hra v explicitním tvaru je znázorněna pomocí grafu. Graf je tvořen množinou uzlů a množinou hran. Strom je typ grafu, který se užívá k zobrazení tahových her. Strom je graf souvislý a acyklický. Souvislý, tzn. mezi každou dvojicí uzlů existuje hrana a není důležité zda orientovaná nebo neorientovaná. Acyklický, tzn. cesta grafu nezačíná a nekončí ve stejném uzlu. Strom má jeden počáteční uzel, kořen a ve většině případů několik koncových uzlů, ve kterých hra končí. Samotný průběh hry je zaznamenán v rozhodovacích uzlech. KOŘEN hráč 1 Rozhodovací uzel hráč 2 Koncový uzel
Koncový uzel
Koncový uzel
Obrázek 1
Kořen je v grafickém zobrazení brán vždy za nejvýše položený uzel, z něhož se strom rozrůstá směrem dolů. Hráči se ve hře v rozhodovacích uzlech střídají. Strom bývá v teorii her znázorňován kořenem vzhůru a zpravidla se jím myslí výchozí herní situace. Každý existující uzel je přiřazen k herní situaci, která může ve hře nastat. Začne-li hru první hráč, je hráčem zahajujícím hru. Hra je zahájena z kořene, z něhož vychází tolik hran, kolik má první hráč možných tahů. Hrany jsou orientované, tah prvního hráče začíná v jednom uzlu (kořen) a končí ve druhém uzlu (rozhodovací uzel), v němž začíná nová herní situace.
17
Z uzlu, ve kterém začala nová herní situace opět vede tolik hran, kolik má druhý hráč možných tahů. Druhý hráč na tahu vybere jednu z hran a projde jí do nového rozhodovacího uzlu, odpovídajícímu nové herní strategii. V tomto uzlu se hráči opět vystřídají a první hráč je na tahu. Hráči se v tazích střídají tak dlouho, až dojdou k jednomu z koncových uzlů. Z koncového uzlu již nevychází žádná hrana k novému uzlu a tím pádem nevzniká nová herní situace, hra končí. Končí celá partie hry, jímž se myslí průběh hry od kořene k jednomu z koncových uzlů. V koncovém uzlu je uveden výsledek hry. Předpokládáme-li, že hru hrají dva inteligentní hráči, pak výsledkem může být výhra prvního nebo druhého hráče.
Nastat může situace nerozhodného
výsledku, například v podobě remízy. Výsledek hry by měl být pro všechny koncové uzly jasný z pravidel hry. Hry v rozvinutém tvaru řešíme pomocí zpětné indukce, kdy je hra rozložena na podhry, které jsou taktéž sami o sobě hrami ve „hře“. Řešení a grafické znázornění her v explicitním tvaru bude popsáno na známých hrách Stonožka a Ruská ruleta. Spojením principů těchto dvou her v rozvinutém tvaru, můžeme teoreticky popsat hru Výměna.
3.2 Hra Stonožka Stonožka je modelovým příkladem hry v explicitním tvaru. Má jasně stanovená pravidla hry a je zachycena v podobě stromu.
Pravidla hry Stonožka:
1. Na začátku je výhra dána tak, že začínající hráč vyhrává více než dvojnásobek výhry druhého hráče, výhra v kořeni je (3,1) 2. Hráč na tahu může přijmout výhru a ukončit hru, nebo zvolit pokračování hry, přičemž výhry se zdvojnásobí, ale zároveň se vymění mezi hráči. 3. Je dán konečný počet tahů. [1]
18
V našem případě je strom tvořen kořenem, dvěmi rozhodovacími uzly a čtyřmi koncovými uzly.
Obrázek 2
K řešení hry stonožka dojdeme pomocí zpětné indukce, kdy celou hru rozložíme na jednotlivé podhry (hry ve hře). Začneme od posledního rozhodovacího uzlu č.5, kdy hráč 1 je na tahu a volí mezi přijmutím výhry nebo pokračováním ve hře. Jelikož výhra z ukončení hry je pro něj vyšší než kdyby pokračoval ve hře, volí strategii přijmout. Tučně zvýrazněná hrana, vedoucí z uzlu č.5 do uzlu č.6 je optimální strategií, kterou volí racionální hráč 1 na tahu. Cena podhry je (12;4). Takto analogicky postupujeme až ke kořeni hry, k uzlu č.1. Hráč 1 je na tahu a jeho racionální rozhodnutí vede tučně zvýrazněnou hranou do uzlu č.2, ve kterém hru ukončí. Cena podhry vedoucí z kořene do prvního koncového uzlu je (3;1). Hráč 1 vyhrává, aniž by se dostal hráč 2 na tah. Hra končí triviálním řešením. Tučně označené hrany jsou nazývány dokonalou
rovnováhou podhry, popisující optimální strategie ve všech herních situacích, ke kterým ve hře může dojít.
3.3 Hra Ruská ruleta Modelovým případem hry v explicitním tvaru je Ruská ruleta. Jednotlivé hrany vedoucí k rozhodovacím uzlům v sobě mohou nést pravděpodobnosti nastoupení nějakého předem známého jevu nebo stavu. V případě ruské rulety se rozhodujeme mezi dvěmi strategiemi. Volbou první strategie, odstoupení ze hry, hráč nic neriskuje.
19
Maximálně potupu, ale i ta pro něj může mít větší užitek než možná smrt. Volbou strategie střílet se do jeho rozhodnutí zapojila pravděpodobnost s jakou může zemřít a s jakou střelbu přežije. Jeho volba závisí na užitku, který mu zvolená strategie přinese. Pravidla hry Ruská ruleta:
1. Do šestiranného revolveru se náhodně vloží jeden ostrý náboj. 2. První hráč na tahu má dvě možné strategie, a to odstoupit (prohra) ze hry nebo
střílet (výhra, smrt). S pravděpodobností P(1) = 1/6 nepřežije a s P(1)=5/6 přežije. Bubínek revolveru se po přežití hráče na tahu znovu neprotáčí (platí i pro další kola). 3. První hráč přežil, na tahu je druhý hráč. Hráč odstoupí nebo střílí. Pokud střílí, pravděpodobnost smrti je P(2)=1/5 a přežití P(2)=4/5. 4. Druhý hráč přežil. První hráč je na tahu. Volí možnost odstoupit nebo střílet. Hráč střílí, s pravděpodobností P(1)=1/4 nepřežije a s P(1)=3/4 přežije. 5. První hráč přežil. Druhý hráč je na tahu. Volí možnost odstoupit nebo střílet. Hráč střílí, s pravděpodobností P(1)=1/3nepřežije a s P(1)=2/3 přežije. 6. Druhý hráč přežil. První hráč je na tahu. Volí možnost odstoupit nebo střílet. Hráč střílí, s pravděpodobností P(1)=1/2 nepřežije a s P(1)=1/2 přežije. 7. První hráč přežil. Druhý hráč je na tahu. Volí možnost odstoupit nebo střílet. Hráč střílí, s pravděpodobností P(1)=1 nepřežije a s P(1)=0 přežije.
Obrázek 3
To jaké rozhodnutí 1.hráč na tahu zvolí, záleží na ohodnocení jeho užitků z prohry, výhry a smrti. Pokud by například cenil smrt zápornou hodnotou, vítězství by pro něj bylo nejdůležitějším a prohra přinesla nulový užitek. Lze předpokládat, že takto uvažující hráč by volil střílet. Oproti tomu jeho protihráč může mít užitky nastaveny jinak. Zpětnou indukcí bychom mohli určit optimální strategii, stejným principem jako u hry Stonožka. Na grafu již není zachycen poslední krok, v němž pravděpodobnost smrti 2.hráče je jistá, tedy rovna jedné.
20
4. Hra Výměna 4.1. Charakteristika hry Výměna Z teorie, která byla popsána na předešlých stránkách definujeme Výměnu jako hru:
v explicitním (rozvinutém) tvaru o N hráčích (omezíme se na model, kdy ve hře budou právě dva hráči) inteligentních účastníků s úplnou informací a zároveň s dokonalou informací s možností kooperace s konečným počtem možných strategií s nekonstantním součtem Hra Výměna je hrou původní. Skládá se ze dvou částí. První část tvoří „jistá
kola“ a jejich princip lze popsat hrou Stonožka. Druhou částí jsou „nejistá kola“, která jsou založena na herním principu hry Ruská ruleta. Důležitým prvkem hry je banka, která v rámci jistých kol do hry vydává nové poukázky, které jsou obrazem inflačního tlaku banky. V rámci nejistých kol banka plní roli likvidátora zmařených poukázek, které jsou uvrženy do bankrotu. To jakým způsobem tak učiní (výdej a likvidaci poukázek) a jak samotná hra probíhá jasně vymezují pravidla hry. Herní pravidla budou popsána pro 2 hráče. Na tento počet se omezíme i v samotném rozkladu a analýze hry. Především pro zjednodušení a jasnější výklad hry. Analyzovaná hra bude obsahovat sedm kol. Z toho tři jistá kola a čtyři nejistá kola. V případě, že by hra byla hrána na více jak devět kol, bylo by třeba použít vyšších početních soustav nebo rozlišitelného cyklu, apod. Hru Výměna lze v praktických situací aplikovat na finanční trhy, které jsou zasaženy určitým typem krize a modelově popsat jakým způsobem se na trzích budou chovat subjekty aktivně zapojeni do takovéto situace. Kdy jistá kola mohou znamenat určitý klid v ekonomice (jistá situace), který je narušen hrozícím bankrotem nebo krizí (nejistá situace). Pokud bychom hovořili o konkrétnějším případě, pak lze hru Výměna uplatnit například při výběrovém řízení na nějaký post ve finanční instituci. Lze opět zkoumat a stanovit chování jedince. Jak se v případě nejistoty bude rozhodovat a jakým způsobem riskovat nebo naopak se držet v ústranní. Z výsledků hry, pak můžeme vybrat takového kandidáta, který nejlépe vyhovuje předem stanoveným podmínkám.
Než přistoupíme k analýze hry Výměna, předložíme pravidla a matematický model hry. 21
4.2.Pravidla hry Výměna 1. Příprava hry Počet hráčů: 2 Potřebujeme: papír, tužku, tři bílé kuličky, jednu černou kuličku, dvě hrací kostky Hráči se seznámí s pravidly hry.
2. Průběh hry
1) Jistá kola – První, Druhé a Třetí kolo Z papíru vyrobíme poukázky, které budou ohodnoceny číslem jedna.
Nulté kolo: Oba hráči si hodí kostkou. Hráč, kterému na kostce padne větší číslo, začíná s hrou a je mu přiděleno označení Červený hráč (dále jen červený). V případě shody se opakují hody tak dlouho, dokud jeden druhého nepřehodí. Hráč, který hodí menší číslo je označen jako Modrý hráč (dále jen modrý).
První kolo: Bankéř vyhlásí první kolo. Bankéř pobídne směnárníka, aby dal červenému právě jednu poukázku s číslem jedna. Kolo se uzavře.
Druhé kolo: Bankéř pobídne červeného, aby svou poukázku předal modrému. Červený má možnost bankéřovu pobídku ignorovat a poukázku si ponechat. Modrý, který obdržel poukázku od červeného jde do banky, kde se o něj postará směnárník. Hráč předloží směnárníkovi drženou poukázku s číslem jedna. Protože bylo vyhlášené druhé kolo, zhodnotí se poukázka číslem dva. Směnárník na přinesenou poukázku dopíše číslo dva. Modrý dostane od směnárníka navíc dvě nové poukázky s číslem dva. Kolo se uzavře.
Třetí kolo: Bankéř pobídne modrého, aby své poukázky předal červenému. Modrý má možnost bankéřovu pobídku ignorovat a poukázky si ponechat. Červený, který obdržel poukázky od modrého jde do banky, kde se o něj postará směnárník. Hráč předloží směnárníkovi držené poukázky obsahující číslici dvě. Protože bylo vyhlášené třetí kolo, zhodnotí se poukázky číslem tři. Směnárník na každou přinesenou poukázku, na které je uvedena hodnota dva, dopíše číslo tři. Červený dostane od směnárníka navíc tři nové poukázky s číslem tři. Kolo se uzavře.
22
2) Nejistá kola – Tři bílé a jedna černá kulička
První rizikové kolo, o kterém hráči dopředu ví, že bude vyhlášeno. Od rizikového kola bankéř losuje z pytlíku kuliček. Pytlík obsahuje tři bílé a jednu
černou kuličku. Bankéř proto pobídne červeného, aby své poukázky předal modrému. Červený má možnost bankéřovu pobídku ignorovat a poukázky si ponechat. Po zhodnocení poukázek se losuje jedna kulička.
Čtvrté kolo a.) Modrý, který obdržel poukázky od červeného jde do banky, kde se o něj postará směnárník. Hráč předloží směnárníkovi držené poukázky s číslem tři. Směnárník na každou přinesenou poukázku, na které je uvedena hodnota tři, dopíše číslo
čtyři. Modrý dostane od směnárníka navíc čtyři nové poukázky s číslem čtyři. V případě, že po zhodnocení bankéř vylosuje bílou kuličku, kolo je platné a probíhá stejně jako předešlá kola do jeho uzavření. Kolo se uzavře.
b.) V případě, že bankéř vylosuje černou kuličku, bankéř vyhlásí BANKROT. Poukázky v držení modrého a obsahující číslo čtyři, ztrácejí hodnotu. Bankéř použije dvě kostky,
které určí pomocí
náhody vypořádací hodnotu
zbankrotovaných poukázek. 1. V případě, že na dvou kostkách padne součet sedm, hodnota bankrotu bude nulová a vypořádají se všechny poukázky, které nezbankrotovaly. Tzn. všechny poukázky, kromě poukázek obsahující číslo čtyři, které jsou v držení modrého. Vypořádací hodnota je určena předem stanoveným koeficientem k. V našem případě je koeficient k = 1. 2. V případě, že na dvou kostkách padne součet jiný než sedm, poukázky s číslem čtyři, v držení modrého a uvržené do bankrotu, budou zhodnoceny. To, jakým koeficientem budou zhodnoceny, určí bankéř hodem jedné kostky. V našem případě je koeficient k = {0,055; 0,06; 0,065; 0,07; 0,075; 0,08}. Pokud padne na hrací kostce jednička, pak koeficient bude roven k = 0,055. Při hodu dvojky, pak k = 0,06 atd. zhodnoceny koeficientem k=1.
23
Konec hry: V případě, že je vylosovaná černá kulička. Po určení vypořádací hodnoty poukázek uvržených do bankrotu, bankéř pobídne hráče k odevzdání všech držených poukázek. Směnárník je pečlivě uloží a vyhodnotí. Cílem hry, je
maximalizovat užitek z držených poukázek. Předpokládáme tak z důvodu zjednodušení hry, kdy pro zřetelný mechanismus je uvedena hra pro dva hráče.
Páté kolo: Druhé rizikové kolo. Pytlík obsahuje dvě bílé a jednu černou kuličku. Po zhodnocení poukázek bankou se losuje jedna kulička. Bankéř vyhlásí páté kolo, pouze pokud ve čtvrtém kole vytáhl bílou kuličku. Probíhá na stejném principu jako čtvrté kolo. Nastat může případ vytažení bílé nebo černé kuličky.
Šesté kolo: Třetí rizikové kolo. Pytlík obsahuje jednu bílou a jednu černou kuličku. Po zhodnocení poukázek bankou se losuje jedna kulička. Bankéř vyhlásí šesté kolo, pouze pokud v pátém kole vytáhl bílou kuličku. Probíhá na stejném principu jako čtvrté kolo. Nastat může případ vytažení bílé nebo černé kuličky.
Sedmé kolo: Poslední rizikové kolo. Pytlík obsahuje černou kuličku. Bankéř vyhlásí sedmé kolo, pouze pokud v šestém kole vytáhl bílou kuličku. Probíhá na stejném principu jako čtvrté kolo. Nastat může pouze případ vytažení černé kuličky.
24
4.3. Matematické vyjádření hry Výměna pro jistá kola Nulté kolo 0) P(1) = 0,5 P(2) = 0,5 P(1) + P(2) = 1
První kolo: 1) k1 = N/2 = 1
Druhé kolo: 2) k1* ∈ {0;1} 3) a. k1* = 0 → KONEC HRY b. k1* = 1
Z 2 = (10 * k1* + 2)
k 22 = 2 2 * L
PK 2 = Z 2 + k 22 ,
Třetí kolo 4) k 2* ∈ {0;2; 2,2; 12;12,2; 12,2,2 = PK 2 } 5) a. k 2* = 0 → KONEC HRY b. k 2* ∈ {2; 2,2; 12;12,2; 12,2,2 = PK 2 }
Z 3 = (10 * k 2* [12] + 3) * a + (10 * k 2* [2] + 3) * b a = 0, 1 , pro k 2* = 12 ; b = 0, 1, 2 , pro k 2* = 2 a +b ≥1
k32 = 32 * L
PK 3 = Z 3 + k 32 → KONEC JISTÝCH KOL
25
Vysvětlivky:
k i - poukázky N - počet hráčů
, i = 1, 2, 3 - číslo aktuálního herního kola , N=1,2
k i* - množina strategií, která kromě nulové varianty (kdy hráč na tahu si ponechá všechny držené poukázky) obsahuje poukázky nesoucí v sobě číslo předešlého kola,
čekající na možné předání, v aktuálním herním kole jejich možného zhodnocení, i = 1,2,3
Z i - zhodnocení předaných poukázek z předešlého kola, i = 2,3 k in - nové poukázky , i = 1,2,3 i - číslo aktuálního herního kola ; n =2 n je konstanta a její hodnota je vždy rovna dvěma L – počet hráčů, kteří jdou zhodnotit své poukázky do banky , L = 1
PK i - celková hodnota držených poukázek hráče na tahu, po zhodnocení předaných a obdržení nových poukázek bankou
, i = 2,3
ad.0) Před samotných zahájením hry je hod kostkou. Pravděpodobnost, že se první hráč stane zahajujícím hráčem červené barvy je P(1)=0,5, stejně tak pro druhého hráče P(2)=0,5 , P(1)+P(2)=1. Hráč, který v hodu kostkou prohrál, nese po celou dobu hry označení modrý hráč. Pravděpodobnost prohry je stejná jako pravděpodobnost výhry, pro prvního hráče P(1) = 1 – P(1) = 0,5 a pro druhého hráče P(2) = 1 – P(2) = 0,5, 1 – P(1) + 1 – P(2) = 1.
ad.1) k1 je počet poukázek vydaných bankou v prvním kole zahajujícímu, červenému hráči. k1 = N/2 = 1 banka vydá červenému hráči právě jednu poukázku s číslem jedna.
ad.2) k1* ∈ {0;1} , k1* je označení pro množinu, obsahující varianty předání poukázky s číslem jedna z prvního kola, v kole druhém. Množina k1* nám říká, jaké má červený hráč možnosti předání poukázek modrému hráči. Množina obsahuje dvě varianty
k1* = 0 a k1* = 1 .Červený hráč zvolí jednu z možných variant, nastat mohou dva případy, kdy hra končí nebo pokračuje.
26
ad.a k1* = 0 , kdy červený si poukázku ponechá a hra končí triviálním řešením. Červený hráč svým tahem hru ukončuje a cena hry je (1,0), ve prospěch červeného. Tento případ však nemá smysl uvažovat. Z pravidel, cílem hry není vyhrát, ale maximalizovat společnou výhru, v následujícím textu podrobněji popíšeme.
ad.b k1* = 1 , červený drženou poukázku s číslem jedna předává modrému a hra pokračuje. Modrý hráč:
Zhodnotí obdrženou poukázku v bance, dle vztahu Z 2 = (10 * k1* + 2) , kde Z 2 je označení pro zhodnocení, které je učiněno bankou ve druhém kole (i = 2).
Obdrží nové poukázky k 22 = 2 2 . k 22 je označení výdeje nových poukázek bankou. Vydávají se dvě nové poukázky obsahující číslo druhého aktuálního kola. Modrý hráč dostává dvě nové poukázky s číslem dva.
Celkem bude mít po druhém jistém kole v držení poukázky s hodnotou PK 2 = Z 2 + k 22 , což je součet zhodnocených obdržených poukázek od
červeného hráče a nových poukázek, získaných od banky. ad.4) k 2* ∈ {0;2; 2,2; 12;12,2; 12,2,2 = PK 2 } , k 2* je označení pro množinu, obsahující varianty předání zhodnocených a nově obdržených poukázek z druhého kola, v kole třetím. Množina k 2* nám říká, jaké má modrý hráč možnosti předání poukázek
červenému hráči. Množina obsahuje šest variant k 2* = 0 ; k 2* = 2 ; k 2* = 2,2 ; k 2* = 12 ; k 2* = 12,2 a k 2* = 12,2,2 = PK 2 . Červený volí vždy jednu z možných variant, nastat mohou dva případy, hra skončí nebo hra pokračuje.
ad.a k 2* = 0 , kdy modrý si ponechá všechny poukázky v držení a hra končí. Modrý hráč svým tahem hru ukončuje a cena hry je stanovena na (0,16), ve prospěch modrého hráče.
ad.b
k 2* ∈ {2; 2,2; 12;12,2; 12,2,2 = PK 2 } , z množiny k 2* , která obsahuje pět
variant zajišťujících pokračovaní hry, modrý hráč vybere právě jednu variantu předání poukázek červenému hráči.
27
První možnost, kdy k 2* = 2 je minimum, které může červený hráč od modrého při předávání obdržet (dostane jednu poukázku obsahující pouze číslo dva). Poslední možnost, kdy k 2* = 12,2,2 = PK 2 je maximem, které může modrý hráč červenému hráči předat (resp. předá mu vše co má v držení a nenechá si žádnou jistotu) Červený hráč:
Zhodnotí obdrženou poukázku / poukázky v bance, dle vztahu: Z 3 = (10 * k 2* [12] + 3) * a + (10 * k 2* [2] + 3) * b , a = 0, 1 , pro k 2* = 12 ; b = 0, 1, 2 , pro k 2* = 2
a +b ≥1
kde Z 3 je označení pro zhodnocení , které je provedeno ve třetím kole (i = 3). Zavedeme zde konstanty a, b. Konstanta a je přiřazena k poukázkám s hodnotou k 2* = 12 a červený hráč na tahu jich může mít připravených ke zhodnocení jednu nebo žádnou. Konstanta b je přiřazena k poukázkám s hodnotou k 2* = 2 a červený hráč na tahu jich v držení může mít žádnou, jednu nebo dvě. Musí být splněna podmínka, že a + b ≥ 1 , touto podmínkou jsme vyloučili variantu, která by vedla ke konci hry, k 2* = 0 a zároveň Z 3 = 0 . Nebylo by co zhodnotit, protože by modrý hráč červenému hráči nic nepředal.
Obdrží nové poukázky k 32 = 3 2 , kde k 32 je označení výdeje nových poukázek bankou. Vydávají se tři nové poukázky obsahující číslo třetího aktuálního kola. Červený hráč dostává tři nové poukázky s číslem tři.
Celkem bude mít po třetím jistém kole v držení poukázky s hodnotou PK 3 = Z 3 + k 32 → zde končí jistá kola a výše popsaný matematický model.
28
4.4. Jistá kola hry Výměna a jejich grafické vyjádření Grafické vyjádření jistých kol (1.,2. a 3. herní kolo) je zachyceno na následujícím grafu v podobě stromu:
Obrázek 4
Strom tvoří kořen (také rozhodovací uzel). Jeden rozhodovací uzel, ohodnocený (0;16). Sedm koncových uzlů, z toho dva koncové v rámci jistých kol (zelené barvy) a pět koncových uzlů, které pokračují do prvního nejistého kola jako uzle rozhodovací. V prvním kole červený hráč obdrží poukázku nesoucí hodnotu jedna. Pokud
červený hráč na počátku druhého kola předá poukázku ohodnocenou číslem jedna modrému hráči, modrý hráč ji ve druhém kole zhodnotí a kolo se uzavře. Modrý hráč má na počátku třetího kola pět možností předání poukázek červenému hráči. Vybere právě jednu z těchto pěti možností. Červený si předané poukázky nechá zhodnotit v bance a k nim dostane tři nové s číslem tři. Kolo se uzavře a hra přejde do druhé části nejistých kol.
Jistá kola ve hře Výměna o dvou hráčích, jsou založena na stejném principu jako herní kola hry Stonožka. Pokud si v pravidlech hry za cíl stanovíme zvítězit, nikoliv maximalizovat celkovou společnou výhru, pak má hra má triviální řešení k němuž dojdeme pomocí zpětné indukce. Výsledkem je, že zahajující červený hráč volí optimální strategii, která vede k ukončení hry s cenou podhry (1;0). V pravidlech hry Výměna je uvedeno, že cílem hráčů je maximalizace celkové výhry. Čímž se vyvarujeme triviálního řešení. V tomto případě je optimální, aby
červený předal poukázku s číslem jedna, kterou má v držení, modrému hráči.
29
Modrý po zhodnocení poukázek bankou opět předá všechny poukázky červenému. Tento sled tahů maximalizuje společný zisk a v konečné fázi jistých kol je cena hry (178;0). Tato částka je pevně dána a v každém případě jí ve hře v jistých kolech hráči dosáhnou. Podstatné je, že je výhra přenosná a hráči mohou kooperovat a uzavírat takové smlouvy či závazné dohody, které pro oba hráče budou výhodné a přinesou jim větší výhru něž kdyby nespolupracovali. Což ve hře Výměna, díky rychle rostoucí hodnotě poukázek, platí vždy. To jakým způsobem si rozdělí výhru záleží na vyjednávacích schopnostech a zvolené taktice daného hráče při uzavírání závazných dohod. Důležitým faktorem je, že dohody se uzavírají vždy před zahájením hry, kdy hráči ještě neví, jakou barvu budou hájit. Jedna z možností jak se podělit o výhru je, že si superaditivní efekt, plynoucí ze spolupráce, rozdělí půl na půl.
30
4.5. Nejistá kola hry Výměna a jejich grafické vyjádření
Grafické vyjádření nejistých kol (4.,5.,6. a 7. herní kolo) je zachyceno v podobě následujícího stromu:
Obrázek 5
31
Strom je na počátku prvního nejistého kola (4.herní kolo) tvořen množinou strategií červeného hráče. Strom hry se od čtvrtého kola příliš rychle rozrůstá, je proto výhodnější jej zachytit ve zjednodušené formě. Červený hráč vybere právě jednu variantu z množiny strategií předání poukázek a předá poukázky modrému hráči. Pokud
červený modrému nic nepředá, pak hra končí v koncovém uzlu zelené barvy, jehož hodnota je závislá na předešlé volbě strategií (podrobněji popsaná v podkapitole 4.6.). Nastalo první rizikové. Hra postupuje do rozhodovacího uzlu, v němž si nechá modrý hráč zhodnotit své poukázky číslem čtyři, dostane čtyři nové s číslem čtyři a tah se uzavře. Bankéř losuje z pytlíku kuliček, jednu kuličku. Vytáhne-li bílou kuličku s P(B) = 3/4, pak hráči v tomto případě vstupují do pátého nejistého kola. Pokud bankéř vylosuje černou kuličku s P(Č) = 1/4 nastává BANKROT, který je ve stromu hry označen fialovou barvou. Bankrotem myslíme ukončení hry, kdy se rozhoduje o vypořádací hodnotě zbankrotovaných poukázek hodem dvěmi kostkami. V případě, kdy součet hodnot na hracích kostkách je S = 7, poukázky uvržené do bankrotu, tj. poukázky obsahující číslo čtyři v držení modrého hráče, ztrácejí hodnotu. Výsledek hry je stanoven výplatní funkcí (J;J), kde J jsou jistoty hráčů. Jistotou se myslí všechny poukázky, které nejsou v kole jejich možného zhodnocení přineseny hráčem na tahu do banky a zhodnoceny směnárníkem (platí hlavně v případě, kdy hráč na tahu neobdržel od svého soupeře všechny poukázky, které mohou být v daném kole zhodnoceny). V dalších kolech ztrácejí na významu. Na konci hry je každý hráč odevzdá směnárníkovi, který je předem daným koeficientem k=1 zhodnotí a zahrne do celkového výsledku hráče, který je směnárníkovi přinesl. Jedná se o jistý druh pojištění, kdy hráč ví, že o tyto poukázky nepřijde. V případě, kdy součet hodnot na dvou hracích kostkách je různý od sedmi S ≠ 7, pak se poukázky uvržené do bankrotu budou zhodnocovat dle koeficientu k = {0,055; 0,06; 0,065; 0,07; 0,075; 0,08}. V množině k je obsaženo šest možných hodnot vypořádacího koeficientu. Vždy pouze jednou z hodnot se zbankrotované poukázky násobí. To jakou hodnotu bude koeficient mít, určí bankéř hodem jedné kostky (viz.pravidla hry). Koeficient je nastaven tak, aby hodnota zbankrotovaných poukázek v žádném případě nepřevýšila hodnotu plynoucí z jistoty (z nepředání poukázek, které je možné zhodnotit). Hra má pak výsledek daný (J; J + HB), kde J je jistota v držení jak modrého tak červeného a HB je hodnota zbankrotovaných poukázek obsahujících číslo čtyři v držení modrého, která se přičte do výsledku modrého. Analogicky postupujeme v kole pátém a šestém, sedmé kolo v sobě nese jistotu bankrotu. 32
Nejistá kola hry Výměna jsou založena na stejných principech jako je založena hra Ruská ruleta. Od čtvrtého kola se do hry zapojuje pravděpodobnost s jakou kolo proběhne bez problému stejně jako předešlá jistá kola a pravděpodobnost předčasného ukončení, které bude mít za následek snížení výhry. První nejisté kolo zahajuje červený hráč, který má na výběr ze dvou strategií, odstoupit ze hry a neriskovat vytažení černé kuličky. Užitek plynoucí z odstoupení a ukončení hry je pro něj větší než pokračování ve hře, kdy může dojít k bankrotu a v každém případě ke snížení hodnoty výhry s pravděpodobností P(Č) = 1/4. Hráč naopak může mít větší užitek z vyšší výhry a bude chtít ve hře pokračovat, pak s pravděpodobností P(B) = 3/4 může počítat s tím, že bude vytažena bílá kulička a kolo proběhne stejně jako jiné jisté kolo. Jeho rozhodnutí je závislé na závazné dohodě, která by měla být před samotným zahájením hry mezi oběma hráči uzavřena. Pravděpodobnost vytažení černé kuličky roste stejně rychle, jako u Ruské rulety roste pravděpodobnost smrti, v důsledku volby strategie střílet. Pokud jsou ve hře hráči, kterým nečiní problém riskovat, ale naopak jde jim o co nejvyšší výsledek, pak jejich maximální výhra po šestém kole, kdy si od zahájení hry vyměňují všechny poukázky, je rovna hodnotě (0;182 820). Samozřejmě, musí mít štěstí a poslední kulička v pytlíku musí být černá. Hráči ať riskují nebo neriskují, se vždy po ukončení hry, ať dobrovolném nebo pravděpodobném, dělí o výhru.
4.6. Výdej, předání, zhodnocení poukázek a optimální řešení hry Výměna Na následujících obrázcích č.6 a č.7 je zaznamenám průběh hry Výměna do konce čtvrtého kola. Jsou zde zakresleny možnosti, kdy předpokládáme, že v prvním rizikovém kole byla vytažena bílá kulička. Při výdeji nových poukázek se uplatňuje aritmetická posloupnost. Směnárník vždy vydá takový počet nových poukázek, který se shoduje s číslem aktuálního herního kola. Již se nebudeme zabývat strategiemi, které vedou k ukončení hry. Pouze krátce okomentujeme smysl předávání, zhodnocování a výdeje nových poukázek. Upozorníme na velký nárůst možností předání, kterých kolo od kola neustále přibývá. Tento problém nastává u tahových her jako jsou například šachy. U hry Vabank v případě dvou hráčů je však nalezení optimální strategie snadnější.
33
Výdej a předání do čtvrtého kola
1
Obrázek 6 1
(1,0)
12,2,2 2
2,2
12
12,2
12,2,2
23,3,3,3
23,23,3,3,3
123,3,3,3
123,23,3,3,3
123,23,23,3,3,3
12,2,2 (0,16)
Banka
23,3,3,3 3
3,3
3,3,3
23
23,3
23,3,3
34,4,4,4,4
34,34, 4,4,4,4
34,34,34, 4,4,4,4
234, 4,4,4,4
234,34, 4,4,4,4
234,34,34, 4,4,4,4
23,3,3,3 (32,14) 234,34,34,34, 4,4,4,4
23,23,3,3,3
. 3
3,3
3,3,3
23
23,3
23,3,3
23,3,3,3
23,23
23,23,3
34,4,4,4,4
34,34, 4,4,4,4
34,34,34, 4,4,4,4
234, 4,4,4,4
234,34, 4,4,4,4
234,34,34, 4,4,4,4
234,34,34,34, 4,4,4,4
234,234, 4,4,4,4
234,234,34, 4,4,4,4
23,23, 3,3
23,23, 3,3,3
(55,12)
234,234,34,34, 234,234,34,34, 4,4,4,4 34,4,4,4,4
123,3,3,3
3
3,3
3,3,3
123
123,3
123,3,3
123,3,3,3
34,4,4,4,4
34,34, 4,4,4,4
34,34,34, 4,4,4,4
1234, 4,4,4,4
1234,34, 4,4,4,4
1234,34,34, 4,4,4,4
1234,34,34 24,4,4,4,4
(132,4)
123,23,3,3,3
3
3,3
3,3,3
23
23,3
23,3,3
23,3,3,3
123
123,3
123,3,3
123,3,3,3
123,23
123,23,3
123,23, 3,3
123,23, 3,3,3
34,4,4,4,4
34,34, 4,4,4,4
34,34,34, 4,4,4,4
234, 4,4,4,4
234,34, 4,4,4,4
234,34,34, 4,4,4,4
234,34,34,34, 4,4,4,4
1234, 4,4,4,4
1234,34, 4,4,4,4
1234,34,34, 4,4,4,4
1234,34,34 34,4,4,4,4
1234,234, 4,4,4,4
1234,234,34, 4,4,4,4
1234,234,34, 34,4,4,4,4
1234,234,34,34 34,4,4,4,4
(155,2)
123,23,23 3,3,3
3
3,3
3,3,3
23
23,3
23,3,3
23,3,3,3
23,23
23,23,3
23,23, 3,3
23,23, 3,3,3
123
123,3
123,3,3
123, 3,3,3
123,23
123,23,3
123,23, 3,3
123,23, 3,3,3
123,23,23
123,23, 23,3
123,23,23 3,3
123,23,23 3,3,3
34, 4,4,4,4
34,34, 4,4,4,4
34,34,34, 4,4,4,4
234, 4,4,4,4
234,34, 4,4,4,4
234,34,34, 4,4,4,4
234, 34,34,34, 4,4,4,4
234,234, 4,4,4,4
234,234, 34, 4,4,4,4
234,234, 34,34, 4,4,4,4
234,234, 34,34,34, 4,4,4,4
1234, 4,4,4,4
34
1234, 34,34, 4,4,4,4
1234, 34,34, 4,4,4,4
1234, 34,34,34, 4,4,4,4
1234, 234, 4,4,4,4
1234, 234,,3, 4,4,4,4
1234, 234,3434, 4,4,4,4
1234, 234, 34,34,34, 4,4,4,4
1234, 234,234, 4,4,4,4
1234 234,234, 34, 4,4,4,4
1234, 234,234, 34,34, 4,4,4,4
1234, 234,234, 34,34,34, 4,4,4,4
(178,0)
34
Zhodnocení do čtvrtého kola
1
Obrázek 7
(0,1)
(1,0)
(0,16)
Banka
(2,14)
(4,12)
(12,4)
(14,2)
(16,0)
(32,14)
(54,12)
(132,4)
(155,2)
(178,0)
(0,16)
(32,14) (29,17)
(26,20)
(23,23)
(9,37)
(6,40)
(3,43)
(0,46) (32,14)
(29,64) (26,98) (23,132 (9,264) (6,298) (3,332) (0,366) (55,12)
(52,15)
(49,18)
(46,21)
(32,35)
(29,38)
(26,41)
(23,44)
(9,58)
(6,61)
(3,64)
(0,67)
(52,62)
(49,96)
(46,130)
(32,262)
(29,296)
(36,330)
(23,364)
(9,496)
(6,530)
(3,564)
(0,598)
(55,12)
(132,4) (129,7)
(126,10)
(123,13)
(9,127)
(6,130)
(3,133)
(0,136)
(129,54)
(126,88)
(123,122)
(9,1254)
(6,1288)
(3,1322)
(0,1356)
(132,4)
(155,2)
(152,5)
(149,8)
(146,11)
(132,25)
(129,28)
(126,31)
(123,34)
(32,125)
(29,128)
(26,131)
(23,134)
(9,148)
(6,151)
(3,154)
(0,157)
(152,52)
(149,86)
(146,120)
(132,252)
(129,286)
(126,320)
(123,354)
(32,1252)
(29,1286)
(26,1320)
(23,1354 )
(9,1486)
(6,1520)
(3,1554)
(0,158)
(155,2)
(178,0)
(175,3)
(172,6)
(169,9)
(155,2)
(152,2)
(149,29)
(146,32)
(132,46)
(129,49)
(126,52)
(123,55)
(55,12)
(52,126)
(49,129)
(46,132)
(32,146)
(29,149)
(26,152)
(23,155)
(9,169)
(6,172)
((3,175)
(0,178)
(175,50)
(172,84)
(169,118)
(155,250)
(152,284)
(149,318)
(146,352)
(132,484)
(129,518)
(126,552)
(123,586)
(55,1250)
35
(52,1384)
(49,1318)
(46,1352)
(32,1484)
(29,1518)
(26,1552)
(23,1586)
(9,1718)
(6,1752)
(3,1786)
(0,1820)
(178,0)
35
1) Předávání a výdej poukázek
Začínající hráč je červený, dostane poukázku s číslem jedna. Druhým na tahu je modrý, dostane poukázku od červeného a jde jí zhodnotit. V držení má poukázku 12 a dvě nové s číslem dva. Modrý má pět možných variant jak nakombinovat předání poukázek. Vybere si jednu z pěti možností a předá poukázky červenému. Červený se nachází v jedné z pěti možností, do které ho poslal modrý hráč ve třetím kole. Nachází-li se v uzlu ohodnoceném (32;14), má celkem 7 možných variant jak předat držené poukázky.Nachází-li se v uzlu ohodnoceném (178;0), tedy v takovém, kdy mu modrý předal všechny poukázky v držení, pak má 22 možných variant jak předat držené poukázky. Předávání poukázek je dobrovolné. Banka vydává nové poukázky podle aritmetické řady. Vydá tolik nových poukázek, kolikáté je kolo. Zároveň tolikrát, kolik hráčů přijde zhodnocovat. V našem případě jsou hráči pouze dva a do banky přichází vždy ten hráč, který je na tahu. Při větším počtu hráčů to však vede k otázce, kolik předat, komu předat a za jakých podmínek předávat. Týká se především při utváření koalic (tato část výkladu již nespadá do této práce, proto ji pouze zmiňujeme). Pravidla hry mohou být nastavena tak, že banka vydává vždy tolik nových poukázek, kolik jich hráč na tahu přinese ke zhodnocení. Tímto se však hra komplikuje a její zachycení je o mnoho náročnější.
2) Zhodnocení poukázek
Princip zhodnocení byl popsán v pravidlech hry a v matematickém modelu pro jistá kola. Zhodnocení v rámci nejistých kol v případě vytažení bílé kuličky je založené na stejném principu jako v kolech jistých. Pokud je vytažena černá kulička, k žádnému zhodnocování poukázek již nedochází, stanoví se pouze vypořádací hodnota zbankrotovaných poukázek.
36
3) Optimální řešení
Obecně u každé hry existuje optimální řešení, jen s tím rozdílem, jak snadno a za jak dlouho jej lze nalézt. V případě tahové hry Výměna, kdy cílem je maximalizovat společnou výhru, je v rámci jistých kol jasné, že by si měli hráči předávat všechny poukázky, které mohou být v aktuálním herním kole zhodnoceny. V rámci nejistých kol je pak nutné znát užitky hráčů z výhry a prohry v případě odstoupení ze hry a bankrotu. Aby bylo dosaženo optimálního řešení, je třeba dodržet principy kooperace a zejména závazné dohody. Ať je dohoda uzavřena ústně nebo písemně.
37
5. Závěr Pomocí teoretických východisek a aparátu, který teorie her užívá pro konkretizaci rozhodovacích situací, v několika bodech shrnu postup své práce a naplnění cílů, které jsem si v samém úvodu stanovila. V samotném počátku své práce jsem popsala základní myšlenku teorie her a způsoby jakými k hrám přistupujeme a třídíme. Omezení na hry v explicitním tvaru mělo jediný důvod, předložit dostatek teoretického základu k analýze hry Výměna. Hra Výměna byla pro zjednodušení popsána pro situaci, kdy hru hrají dva hráči, kteří jsou inteligentními subjekty, mající dokonalou a úplnou informaci o hře. Je povolena kooperace a konečná výhra je přenosná. Jejich rozhodnutí jsou dobrovolná, mohou se však
řídit podle předem stanovených závazných dohod a smluv, v případě jejich uzavření. Při rozboru hry jsem dospěla k teoretickému závěru, že pokud je hlavním cílem hry maximalizace zisku, pak je dohody v každém případě výhodné uzavírat. Dohody lze rozdělit do dvou bodů. Pro případ jistých kol a nejistých kol. Dohoda by měla být uzavřena ještě předtím, než se rozhodne o tom, jakou barvu bude hráč hájit. Jak bude dohoda vypadat, v každém případě závisí na povaze hráčů a jejich užitků v rámci nejistých kol. Zajímavá by pak byla tvorba koalic ve hře o N>2 hráčích. Hru Výměna jsem matematicky vyjádřila pro jistá kola. Následně popsala hru pro jednotlivá kola a stanovila jejich průběh. Od výdeje první poukázky, přes následné předání, zhodnocení a uzavření kola. V grafickém znázornění nebyl pro první tři kola problém se zachycením jejich průběhu. Od čtvrtého kola nastává problém v zachycení všech možností, které může hráč na tahu zvolit, strom se velmi rychle rozrůstá. Proto jsem se u nejistých kol omezila na jednodušší grafický popis. Při stanovení optimálního řešení lze říci, že do posledního jistého kola by si měli hráči předávat vše co mají v držení. U nejistých kol není situace zcela průhledná, jelikož zde hlavní úlohu hrají užitky hráčů ze zvoleného rozhodnutí. K vyřešení by mohlo pomoci, kdyby hráči do smluv své užitky uváděli a podle nich se v rozhodování řídili. Jako poslední bod bych ráda uvedla možné a z mého pohledu pro naplnění této analýzy nutné rozšíření hry. Prvním rozšířením by byla praktická část analýzy, kde by se utvořili dvojice hráčů a experimentálně by se stanovil „optimální“ průběh hry. Pouze z praktických výsledků bych mohla uvažovat o hře zahrané s N>2 hráči. Druhým rozšířením by bylo matematické vyjádření nejistých kol a jejich podrobný popis.
38
6. Literatura Seznam použité literatury [1] Dlouhý M., Fiala P., Úvod do teorie her. Oeconomice, Praha 2007. [2] Maňas M., Teorie her a konflikty zájmů. Oeconomica, Praha 2002. [3] Maňas M., Teorie her a její ekonomická aplikace. VŠE, Praha 1998. [4] Maňas M., Teorie her a optimální rozhodování. SNTL, Praha 1974. [5] Valenčík R., Teorie her a redistribuční systémy. Eurpress, Praha 2008.
39
