Západočeská univerzita v Plzni Fakulta aplikovaných věd Katedra matematiky. Časové struktury v teorii her

Za´padoˇceska´ univerzita v Plzni Fakulta aplikovanyćh vˇed Katedra matematiky

Bakal´ aˇ rsk´ a pr´ ace ˇ Casov´ e struktury v teorii her

Plzeˇ n 2013

ˇ Lucie Stejrov´ a

Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem bakaláˇrskou práci vypracovala samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u. V Plzni dne 28. kvˇetna 2013 ˇ Lucie Stejrov´ a

Abstrakt C´ılem této práce je sestavit srozumitelné shrnut´ı role ˇcasován´ı v teorii her. Hlavn´ı pozornost je upˇrena na hry, které ve své statické formˇe maj´ı v´ıce rovnováh. Konkrétnˇe se vˇenuje dvˇema scénáˇr˚ um Válka pohlav´ı a Jestˇra´bi a holubice. V práci je ukázáno, jak ˇcasován´ı mˇen´ı poˇcet a zejména jednoznaˇcnost rovnováh. Práce se vˇenuje ˇcasov´ ym strukturám v bˇeˇznˇe znám´ ych dynamick´ ych hrách, ale i ve speciáln´ıch typech dynamick´ ych her, kde je ˇcasován´ı náhodné. Kl´ıˇ cov´ a slova: Teorie her, Válka pohlav´ı, Jestˇrábi a holubice, statické hry, dynamické hry, dynamické hry s náhodn´ ym ˇcasován´ım tah˚ u

Abstract The aim of this work is to make clear summary of timing structures in the game theory. The main attention is given to situations, which have multiple Nash equilibria in the form of static game. Namely it is The Battle of Sexes scenario and The Game of Chicken scenario. In the work we show how timing can cause change of number of equilibria and especially uniqueness of equalibria. This work pursues commonly known dynamic games but also gives attention to special types of dynamic games with stochastic timing of moves. Key words: Game theory, Battle of Sexes, Game of Chicken, static games, dynamic games, dynamic games with stochastic timing of moves

Obsah ´ 1 Uvod 2 Z´ akladn´ı pojmy teorie her ´ 2.1 Uvod do teorie her . . . . . . . . . . . . 2.2 Hra, hráˇc, strategie, uˇzitek . . . . . . . . 2.2.1 Typy her . . . . . . . . . . . . . . 2.3 Statické hry . . . . . . . . . . . . . . . . 2.4 Scénáˇre s nejednoznaˇcn´ ymi rovnováhami 2.4.1 Válka pohlav´ı . . . . . . . . . . . 2.4.2 Jestˇrábi a holubice . . . . . . . . 2.4.3 Grafické znázornˇen´ı uˇzitk˚ u . . . .

1

. . . . . . . .

2 2 2 3 3 5 6 8 9

3 Dynamick´ e hry 3.1 Zobrazen´ı dynamické hry . . . . . . . . . . . . . . . . . . . . . ˇ sen´ı dynamické hry . . . . . . . . . . . . . . . . . . . . . . 3.2 Reˇ 3.3 V´ yhoda poˇrad´ı . . . . . . . . . . . . . . . . . . . . . . . . . .

12 12 13 14

4 Dynamick´ e hry s n´ ahodn´ ym ˇ casov´ an´ım tah˚ u 4.1 Popis hry . . . . . . . . . . . . . . . . . . . . ˇ 4.2 Casov´ an´ı reviz´ı . . . . . . . . . . . . . . . . . 4.3 V´ ybˇer optimáln´ı rovnováhy . . . . . . . . . . 4.3.1 Jin´ y zp˚ usob vyjádˇren´ı podm´ınky v´ yhry 4.3.2 V´ ymˇena poˇrad´ı hráˇc˚ u. . . . . . . . . .

16 16 16 18 22 23

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . .

5 Pˇ r´ıklady, z´ avislosti na parametrech a uˇ zitc´ıch 25 5.1 Ilustraˇcn´ı pˇr´ıklady . . . . . . . . . . . . . . . . . . . . . . . . 25 5.2 Závislost podm´ınek v´ yhry . . . . . . . . . . . . . . . . . . . . 29 5.2.1 Shrnut´ı . . . . . . . . . . . . . . . . . . . . . . . . . . 32 6 Z´ avˇ er

35

´ 1 Uvod C´ılem této práce je pˇredstavit roli ˇcasován´ı v teorii her s ohledem hlavnˇe na kooperaˇcn´ı hry a situace s násobn´ ymi rovnováhami, kde ˇcasován´ım m˚ uˇzeme dosáhnout zmˇeny poˇctu a jednoznaˇcnosti rovnováh. Zab´ yváme se klasick´ ymi dynamick´ ymi hrami, ale i situacemi, kde je ˇcasován´ı tah˚ u náhodné. Hlavn´ım námˇetem pro tuto práci byl ˇclánek Libich a Stehl´ık [3]. V zaˇca´tku práce ˇctenáˇre seznám´ıme se základn´ımi pojmy teorie her, které dále pouˇz´ıváme. Pˇredstav´ıme také základn´ı pˇredpoklady teorie her. Velká ˇcást této kapitoly je vˇenována statick´ ym hrám a dvˇema scénáˇr˚ um s násobn´ ymi rovnováhami: Válka pohlav´ı a Jestˇra´bi a holubice. V dalˇs´ı kapitole zkoumáme dynamické hry. Ukáˇzeme jak pˇreveden´ım statick´ ych her, s v´ yˇse uveden´ ymi scénáˇri, na dynamickou hru m˚ uˇzeme vyˇreˇsit problém nejednoznaˇcnosti rovnováhy. Následnˇe se vˇenujeme dynamick´ ym hrám se speciáln´ım ˇcasován´ım tah˚ u, které je náhodné, zadané nˇejak´ ym pravdˇepodobnostn´ım rozdˇelen´ım. Pop´ıˇseme tento typ hry a snaˇz´ıme se opˇet vyˇreˇsit nejednoznaˇcnost rovnováhy. Pro ilustraci nalezeného ˇreˇsen´ı uvedeme pˇr´ıklady. Nakonec zkoumáme závislost ˇreˇsen´ı na obsaˇzen´ ych parametrech.

1

2 Základn´ı pojmy teorie her Tato kapitola slouˇz´ı jako struˇcn´ yu ´vod do problematiky teorie her. Jsou zde vysvˇetlené základn´ı pojmy a myˇslenky této discipl´ıny. Vˇetˇsina definic a vˇet je pˇrejata z literatury Webb [1] a Fudenberg [2]. Dále zde pˇredstav´ıme a pop´ıˇseme statické hry a ukáˇzeme dva základn´ı scénáˇre.

2.1

´ Uvod do teorie her

Teorie her je matematická discipl´ına, která aplikuje matematické poznatky pˇri rozhodovac´ıch a konfliktn´ıch situac´ıch, které mohou bˇeˇznˇe nastat. Situace rozhodován´ı racionáln´ıch hráˇc˚ u jsou pˇrevádˇeny na matematické modely. Z tohoto modelu se potom pomoc´ı v´ ypoˇct˚ u snaˇz´ı nalézt nejlepˇs´ı strategii pro vˇsechny hráˇce. Zde se nacház´ı hlavn´ı rozd´ıl mezi teori´ı her a optimalizac´ı. Pˇri optimalizaci hledáme nejlepˇs´ı alternativu pro jednoho hráˇce, kter´ y zanedbává okol´ı, zat´ımco v teorii her hledáme nejlepˇs´ı strategii pro hráˇce za pˇredpokladu vlivu naprosto racionáln´ıho okol´ı (dalˇs´ıch hráˇc˚ u). Teorie her má mnoho aplikac´ı v sociáln´ıch, politick´ ych a poˇc´ıtaˇcov´ ych vˇedách, stejnˇe jako v biologii. Ze sociáln´ıch vˇed je to pˇredevˇs´ım ekonomie. Pro biologii jsou d˚ uleˇzité evoluˇcn´ı hry, které mohou modelovat chován´ı r˚ uzn´ ych ˇzivoˇciˇsn´ ych druh˚ u.

2.2

Hra, hr´ aˇ c, strategie, uˇ zitek

Jako hra je v teorii her oznaˇcována jakákoliv rozhodovac´ı situace, kde vystupuj´ı alespoˇ n dva hráˇci. Pro takové hry uvaˇzujeme obecné pˇredpoklady teorie her. Pˇ redpoklad 1. (i) Hráˇci jsou racionáln´ı. (ii) Vˇsichni u ´ˇcastn´ıci znaj´ı pravidla a ta se v pr˚ ubˇehu jedné hry nemˇen´ı. (iii) Hráˇci znaj´ı své vlastn´ı uˇzitky a zároveˇ n maj´ı pˇrehled o uˇzitc´ıch ostatn´ıch hráˇc˚ u. Jako hráˇce uvaˇzujeme jedince, kter´ y má moˇznost uˇcinit rozhodnut´ı, tj. vybrat jednu z mnoˇziny moˇzn´ ych strategi´ı. Jedno urˇcité rozhodnut´ı je tedy 2

Základn´ı pojmy teorie her

Statické hry

oznaˇcováno jako strategie. Kaˇzd´ y hráˇc má dané uˇzitky pro kombinaci sv´ ych strategi´ı postupnˇe se vˇsemi strategiemi protihráˇc˚ u.

2.2.1

Typy her

Hry m˚ uˇzeme dˇelit dle r˚ uzn´ ych kritéri´ı. Za základn´ı dˇelen´ı povaˇzujeme dva typy, a to hry statické (v normáln´ım tvaru) a hry dynamické (v explicitn´ım tvaru). Tˇemto typ˚ um her budou vˇenovány samostatné kapitoly v pr˚ ubˇehu této práce. Dalˇs´ı dˇelen´ı m˚ uˇzeme provádˇet dle poˇctu hráˇc˚ u, nejˇcastˇeji se vˇsak setkáme s typem her, kde se vyskytuj´ı pouze dva hráˇci. Nen´ı potom vylouˇcené, ˇze jeden hráˇc zastupuje celou skupinu jedinc˚ u se stejn´ ymi zájmy. Hry m˚ uˇzeme rozdˇelit i podle poˇctu strategi´ı na hry s koneˇcn´ ym poˇctem strategi´ı a hry s nekoneˇcn´ ym poˇctem strategi´ı. Nekoneˇcn´ y poˇcet strategi´ı m˚ uˇze nastat tehdy, pokud hráˇc vyb´ırá napˇr´ıklad reálné ˇc´ıslo ze spojitého intervalu.

2.3

Statick´ e hry

Statická hra je jednotahová hra dvou nebo v´ıce hráˇc˚ u se dvˇema nebo v´ıce strategiemi. Tento typ hry se nˇekdy naz´ yvá simultánn´ı hra, protoˇze hráˇci uskuteˇcn ˇuj´ı své rozhodnut´ı ve stejn´ y okamˇzik a neznaj´ı pˇredem volbu ostatn´ıch. Matematické vyjádˇren´ı této hry je popsáno následuj´ıc´ı definic´ı. Definice 1. Statická hra je matematická struktura skládaj´ıc´ı se ze tˇr´ı mnoˇzin: 1. Mnoˇzina hráˇc˚ u i ∈ {1, 2, ..., N }, 2. mnoˇzina jejich strategi´ı Si , 3. uˇzitky πi (s1 , s2 , ..., sN ) pro kaˇzdou moˇznou kombinaci ˇcist´ ych strategi´ı vˇsech hráˇc˚ u, kde s1 ∈ S1 , s2 ∈ S2 , ..., sn ∈ Sn . Dále, pro u ´ˇcely této práce, budeme uvaˇzovat pouze hru dvou hráˇc˚ u se dvˇema strategiemi. Statickou hru zapisujeme v normáln´ım tvaru, kde se vy3


Statické hry

skytuj´ı data ze vˇsech tˇr´ı nadefinovan´ ych mnoˇzin. Hra m˚ uˇze vypadat následovnˇe: H2 C A a,w H1 B c,y

D b,x d,z

Zápis hry pomoc´ı tabulky se naz´ yvá normáln´ı tvar statické hry. Máme tedy mnoˇzinu dvou hráˇc˚ u {H1, H2}. Jejich strategie jsou S1 = {A, B} a S2 = {C, D}. Uˇzitky prvn´ıho hráˇce jsou {a, b, c, d}, kde napˇr´ıklad uˇzitek a m˚ uˇzeme zapsat jako π1 (A, C). Uˇzitky druhého hráˇce jsou {w, x, y, z}. Strategie {A, B} a {C, D} uvedené v tabulce jsou ˇcisté strategie, jejich kombinac´ı z´ıskáme sm´ıˇsené strategie. Definice 2. Sm´ıˇsená strategie i-tého hráˇce je vektor pravdˇepodobnostn´ıho rozdˇelen´ı σi = (pi1 , pi2 , ..., piN ) ˇcist´ ych strategi´ı, kde kaˇzdá sloˇzka pij udává pravdˇepodobnost s jakou bude i-t´ y hráˇc hrát strategii sj . Mnoˇziny vˇsech moˇzn´ ych sm´ıˇsen´ ych strategi´ı oznaˇc´ıme Σi . ˇ sen´ım hry je dvojice strategi´ı, které by racionáln´ı hráˇci pouˇzili. Tuto Reˇ dvojici budeme naz´ yvat rovnováha nebo rovnováˇzný stav hry a budeme ji zapisovat ve tvaru (s1 , s2 ). Speciáln´ı typ rovnováhy je Nashova rovnováha, kde ani jeden z hráˇc˚ u nem˚ uˇze z´ıskat lepˇs´ı uˇzitek pouˇzit´ım jiné strategie. Definice 3. Nashova rovnováha (pro dva hráˇce) je dvojice strategi´ı (σ1∗ ; σ2∗ ) takov´ ych, ˇze plat´ı π1 (σ1∗ ; σ2∗ ) ≥ π1 (σ1 ; σ2∗ )

∀σ1 ∈ Σ1 ,

(2.1)

π2 (σ1∗ ; σ2∗ ) ≥ π2 (σ1∗ ; σ2 )

∀σ2 ∈ Σ2 .

(2.2)

Poznámka 1. V pˇr´ıpadˇe, ˇze strategie σ1∗ a σ2∗ jsou ˇcisté strategie, dostaneme ˇcistou Nashovu rovnováhu. Jinak budeme uvaˇzovat sm´ıˇsenou Nashovu rovnováhu. Poznámka 2. V pˇr´ıpadˇe, ˇze se v rovnici (2.1) nebo (2.2) vyskytne neostrá nerovnost, kaˇzdá malá zmˇena v hodnotách uˇzitk˚ u vytvoˇr´ı nové rovnováhy nebo vyruˇs´ı stávaj´ıc´ı rovnováhy. Takové hˇre budeme ˇr´ıkat negenrická hra.

4


Scénáˇre s nejednoznaˇcnými rovnováhami

Nen´ı vylouˇcené, naopak je sp´ıˇs bˇeˇzné, ˇze hra má vˇetˇs´ı poˇcet rovnováh. Pro nalezen´ı ˇcist´ ych Nashov´ ych rovnováh m˚ uˇzeme vyuˇz´ıt ˇreˇsen´ı pomoc´ı dominovan´ ych strategi´ı, které je uvedeno napˇr´ıklad ve Webb [1] a pro nalezen´ı vˇsech Nashov´ ych rovnováh (ˇcisté i sm´ıˇsené) je opˇet ve Webb [1] popsán koncept nejlepˇs´ı odpovˇedi. Problém existence Nashovy rovnováhy ve statick´ ych hrách ˇreˇs´ı následuj´ıc´ı vˇeta, jej´ıˇz d˚ ukaz m˚ uˇze ˇctenáˇr naj´ıt ve Fudenberg [2]. Vˇ eta 1 (Nashova vˇeta). Kaˇzdá statická hra s koneˇcným poˇctem hráˇc˚ u a koneˇcným poˇctem strategi´ı má alespoˇ n jednu Nashovu rovnováhu. Dalˇs´ı problém je jednoznaˇcnost rovnováhy. Pro tuto otázku neexituje jednoduchá odpovˇed’. Jsou pouze urˇcité postaˇcuj´ıc´ı podm´ınky, které obsáhnou jen malou mnoˇzinu her. Ale velká tˇr´ıda her má v´ıce neˇz jednu rovnováhu a zde nastává právˇe problém v´ ybˇeru optimáln´ı rovnováhy. M˚ uˇzeme pouˇz´ıt v´ıce zp˚ usob˚ u pro v´ ybˇer rovnováhy. Nejjednoduˇsˇs´ı je v´ ybˇer dle tradice nebo spoleˇcensk´ ych konvenc´ı (Na silnici mohou jezdit vozidla obou smˇer˚ u vlevo nebo vpravo. Pokud budou jezdit oba vlevo, je to rovnováha, ale pokud budou jezdit oba vpravo, je to také rovnováha. Potom záleˇz´ı napˇr´ıklad na zemi, ve které se vozidla nacház´ı, protoˇze ve Velké Británii by byla optimáln´ı rovˇ e Republice). Dalˇs´ı moˇznost´ı je pouˇzit´ı evoluˇcn´ı dynováha jiná neˇz v Cesk´ namiky, kde hráˇci pˇredstavuj´ı populace jedinc˚ u (v´ıce napˇr. ve Webb [1]). Posledn´ım ˇreˇsen´ım je vyuˇzit´ı ˇcasován´ı tah˚ u, ˇc´ımˇz se budeme zab´ yvat ve zbytku práce.

2.4

Sc´ en´ aˇ re s nejednoznaˇ cn´ ymi rovnov´ ahami

Uvaˇzujeme hru dvou hráˇc˚ u M a F. Kaˇzd´ y z hráˇc˚ u má na v´ ybˇer ze dvou strategi´ı, pro hráˇce M je to R a S a pro hráˇce F je to r a s. Uˇzitky jsou následuj´ıc´ı:

F r R a,w M S c,y

5

s b,x d,z



Podle hodnot uˇzitk˚ u m˚ uˇzeme odliˇsit r˚ uzné scénáˇre hry. Pro tuto práci budou d˚ uleˇzité scénáˇre, které maj´ı v´ıce Nashov´ ych rovnováh a nastává v nich konflikt. To znamená, ˇze kaˇzy ´ hráˇc preferuje jinou rovnováhu.

2.4.1

V´ alka pohlav´ı

Prvn´ım takov´ ym scénáˇrem je Válka pohlav´ı. Uˇzitky splˇ nuj´ı nerovnice a>d>b≥c pro hráˇce M a z>w>x≥y pro hráˇce F. Existuj´ı v nˇem dvˇe ˇcisté Nashovy rovnováhy (R, r) a (S, s). Hráˇci se tedy chtˇej´ı zkoordinovat, ale kaˇzd´ y z nich preferuje jinou rovnováhu. Hráˇc M preferuje (R, r), zat´ımco hráˇc F dává pˇrednost rovnováze (S, s). V tomto scénáˇri pozorujeme oba problémy, jak koordinaˇcn´ı, tak konfliktn´ı. Pro pˇredstavu uvedeme základn´ı pˇr´ıklad hry s t´ımto scénáˇrem. Pˇr´ıklad 1. Hˇra´ˇc M je muˇz, hráˇc F je ˇzena. Plánuj´ı strávit spoleˇcn´ y veˇcer a rozhoduj´ı se, kam p˚ ujdou. Oba maj´ı na v´ ybˇer stejné strategie: {Hokej, Opera}. Muˇz preferuje Hokej, ˇzena Operu. Uˇzitky mohou b´ yt napˇr´ıklad následuj´ıc´ı: ˇ Zena Hokej Opera Hokej 2,1 0,0 Muˇz Opera 0,0 1,2

Z uˇzitk˚ u vypl´ yvá, ˇze je d˚ uleˇzité, aby ˇsli spoleˇcnˇe (koordinaˇcn´ı problém). Hru vyˇreˇs´ıme pomoc´ı reakˇcn´ı funkce (podrobnˇeji ve Webb [1]). Reakˇcn´ı funkci sestroj´ıme tak, ˇze budeme pˇredpokládat sm´ıˇsené strategie σ1 = (p, 1 − p) hráˇce M a σ2 = (q, 1 − q) hráˇce F. Tento zápis m˚ uˇzeme interpretovat tak, ˇze hráˇc M bude hrát strategii Hokej s pravdˇepodobnost´ı p a strategii Opera s pravdˇepodobnost´ı (1 − p), obdobnˇe to plat´ı pro soupeˇre. Nyn´ı spoˇcteme 6



uˇzitek prvn´ıho hráˇce z tˇechto sm´ıˇsen´ ych strategi´ı v závislosti na hodnotách p a q.

π1 (σ1 , σ2 ) = 2pq + (1 − p)(1 − q) = 2pq + pq − p − q + 1 = 3pq − p − q + 1 = p(3q − 1) − q + 1

(2.3)

Provedeme diskusi posledn´ıho ˇra´dku rovnice (2.3). Kdyˇz bude q < 13 , nejlepˇs´ı reakc´ı bude hrát p = 0. V pˇr´ıpadˇe, ˇze q > 13 , nejlepˇs´ı odezvou je zahrát p = 1. Pokud bude q = 31 , na hodnotˇe p nezáleˇz´ı, protoˇze v´ yraz (3q − 1) bude nulov´ y. Tuto funkci nám znázorˇ nuje modrá kˇrivka na Obrázku 2.1. Stejn´ ym postupem spoˇcteme uˇzitek hráˇce F ze sm´ıˇsen´ ych strategi´ı (rovnice 2.4) a po proveden´ı diskuse z´ıskáme ˇcervenou kˇrivku vyobrazenou na Obrázku 2.1.

π2 (σ1 , σ2 ) = pq + 2(1 − p)(1 − q) = pq + 2pq − 2p − 2q + 2 = 3pq − 2q − 2p + 2 = q(3p − 2) − 2p + 2

(2.4)

V m´ıstˇe protnut´ı obou kˇrivek se nacház´ı Nashova rovnováha. V tomto pˇr´ıkladu existuj´ı tˇri Nashovy rovnováhy: (0, 0), (1, 1) a ( 23 , 13 ). Prvn´ı dvˇe rovnováhy jsou ˇcisté, protoˇze hráˇc vyb´ırá pouze jednu strategii s pravdˇepodobnost´ı 1 a v tomto pˇr´ıkladu reprezentuj´ı (Hokej, Hokej) a (Opera, Opera). Posledn´ı rovnováha je sm´ıˇsená, kde prvn´ı hráˇc bude hrát strategii Hokej s pravdˇepodobnost´ı p = 32 a strategii Opera s pravdˇepodobnost´ı (1 − p) = 13 . Pro druhého hráˇce plat´ı analogicky. Dále se budeme zab´ yvat pouze ˇcist´ ymi Nashov´ ymi rovnováhami. T´ım máme vyˇreˇsen´ y koordinaˇcn´ı problém. Nastává problém v´ ybˇeru optimáln´ı rovnováhy (konflikt), kter´ y m˚ uˇzeme vyˇreˇsit právˇe ˇcasován´ım, jak bude uvedeno v dalˇs´ıch kapitolách.

7



q 1

2 3

1 3

1 3

2 3

1

p

Obrázek 2.1: Reakˇcn´ı funkce pro Válku pohlav´ı

2.4.2

Jestˇ r´ abi a holubice

Druh´ y vyhovuj´ıc´ı scénáˇr jsou Jestˇra´bi a holubice. Uˇzitky pro tento scénáˇr mus´ı splˇ novat nerovnice b>c>d≥a pro hráˇce M a y>x>z≥w pro hráˇce F. V této hˇre opˇet existuj´ı dvˇe ˇcisté Nashovy rovnováhy (R, s) a (S, r). Z rovnováh je zˇrejmé, ˇze hráˇci chtˇej´ı m´ıt rozd´ılné strategie a opˇet kaˇzd´ y preferuje jinou rovnováhu. Pro hráˇce M je uˇzitkovˇe v´ yhodnˇejˇs´ı rovnováha (R, s), zat´ımco pro hráˇce F je to rovnováha (S, r). Tento scénáˇr obsahuje antikoordinaˇcn´ı problém i konflikt. Pˇr´ıklad 2. Oba hráˇci pˇredstavuj´ı ˇridiˇce, kteˇr´ı jedou proti sobˇe na silnici. Maj´ı na v´ ybˇer strategie {N evyhnout, V yhnout}. Hráˇc, kter´ y se vyhne je oznaˇcen jako ”chicken”(anglick´ y název hry je Game of Chicken), tedy zbabˇelec. Nejlepˇs´ı uˇzitek dostane hráˇc v situaci, kdy se nevyhne, ale jeho soupeˇr ano. Nejhorˇs´ı uˇzitek maj´ı oba hráˇci, pokud se ani jeden nevyhne (auta do sebe nabouraj´ı). Hra m˚ uˇze vypadat napˇr´ıklad takto:

8



ˇ c2 Ridiˇ Nevyhnout Vyhnout Nevyhnout -10,-10 10,1 ˇ c1 Ridiˇ 1,10 0,0 Vyhnout

Pro nalezen´ı vˇsech rovnováh hry pouˇzijeme stejn´ y postup jako v pˇredchoz´ım pˇr´ıkladu. Budeme uvaˇzovat sm´ıˇsené strategie σ1 = (p, 1 − p) a σ2 = (q, 1 − q). Nalezneme uˇzitky hráˇce M pro tyto sm´ıˇsené strategie a sestroj´ıme reakˇcn´ı funkci, která je znázornˇená modrou kˇrivkou na Obrázku 2.2.

π1 (σ1 , σ2 ) = −10pq + 10p(1 − q) + (1 − p)q = −10pq + 10p − 10pq + q − pq = −21pq + 10p + q = p(−21q + 10) + q ˇ Dále vypoˇcteme uˇzitky hráˇce F pro sm´ıˇsené strategie σ1 a σ2 . Cervenou kˇrivkou je vyznaˇcena reakˇcn´ı funkce hráˇce F.

π2 (σ1 , σ2 ) = −10pq + p(1 − q) + 10(1 − p)q = −10pq + p − pq + 10q − 10pq = −21pq + p + 10q = q(−21p + 10) + p Nashovy rovnováhy jsou opˇet pr˚ useˇc´ıky obou kˇrivek. Dvˇe ˇcisté Nashovy rovnováhy (1, 0) a (0, 1) znamenaj´ı (N evyhnout, V yhnout), 10 10 , 21 ). Opˇet (V yhnout, N evyhnout). Sm´ıˇsená Nashova rovnováha je v bodˇe ( 21 zde nastává konflikt, kter´ y m˚ uˇzeme vyˇreˇsit ˇcasován´ım.

2.4.3

Grafick´ e zn´ azornˇ en´ı uˇ zitk˚ u

Pro pˇredstavu m˚ uˇzeme hodnoty uˇzitk˚ u obou hráˇc˚ u ve v´ yˇse zm´ınˇen´ ych scénáˇr´ıch vyjádˇrit graficky. Hráˇc má ˇctyˇri uˇzitky, kaˇzd´ y jako v´ ysledek kombinace dvou strategi´ı. Dvˇema uˇzitk˚ um pˇriˇrad´ıme fixn´ı hodnotu a budeme zkoumat 9



q 1

10 21

10 21

1

p

Obrázek 2.2: Reakˇcn´ı funkce pro Jestˇra´by a holubice

d 4

2

-4

-2

JH

VP

2

4

a

-2

-4

Obrázek 2.3: Grafické znázornˇen´ı uˇzitk˚ u a a d hráˇce M pro oba scénáˇre pˇri volbˇe b = 1 a c = 0

10


Scénáˇre s nejednoznaˇcnými rovnováhami x 4

2

JH

y -4

-2

VP

2

4

-2

-4

Obrázek 2.4: Grafické znázornˇen´ı uˇzitk˚ u x a y hráˇce F pro oba scénáˇre pˇri volbˇe z = 1 a w = 0

pˇr´ıpustné oblasti pro zbylé hodnoty uˇzitk˚ u. Grafy jsme rozdˇelili podle hráˇc˚ u na graf uˇzitk˚ u hráˇce M a graf uˇzitk˚ u hráˇce F. Na Obrázku 2.3 jsou vyznaˇcené dvˇe oblasti. Oblast VP vymezuje moˇznou volbu uˇzitk˚ u a a d pro scénáˇr Válka pohlav´ı, za pˇredpokladu, ˇze zb´ yvaj´ıc´ı uˇzitky maj´ı zafixované hodnoty, a to b = 1 a c = 0. Oblast JH znázornˇ nuje také moˇznou volbu uˇzitk˚ u a a d pˇri stejnˇe zafixovan´ ych uˇzitc´ıch b a c, ale pro scénáˇr Jestˇra´bi a holubice. Na dalˇs´ım Obrázku 2.4 jsou vyznaˇcené moˇzné volby uˇzitk˚ u x a y, pokud w = 0 a z = 1. Oblast VP opˇet znaˇc´ı moˇznosti pro scénáˇr Válka pohlav´ı a JH pro scénáˇr Jestˇrábi a holubice.

11

3 Dynamické hry V této kapitole pˇredstav´ıme tˇr´ıdu dynamick´ ych her. V tomto typu her nenastávaj´ı tahy hráˇc˚ u souˇcasnˇe, ale postupnˇe. Hry jsou tedy minimálnˇe dvoutahové (v prvn´ı tahu hraje jeden hráˇc, ve druhém tahu hraje druh´ y hráˇc). Pokud by byla dynamická hra jednotahová, jednalo by se pouze o optimalizaci. Hlavn´ı odliˇsnost od statick´ ych her je fakt, ˇze hráˇc zná v´ ysledek pˇredchoz´ıho tahu a má moˇznost na nˇej reagovat.

3.1

Zobrazen´ı dynamick´ e hry

Dynamické hry se zobrazuj´ı v explicitn´ım tvaru pomoc´ı strom˚ u. Na Obrázku 3.1 je znázornˇena hra Válka pohlav´ı jako dynamická hra. V prvn´ım pˇr´ıpadˇe má moˇznost prvn´ıho tahu hráˇc M a vyb´ırá opˇet ze dvou strategi´ı {R, S}. Aˇz po ukonˇcen´ı tahu prvn´ıho hráˇce zaˇc´ıná tah druhého hráˇce, kter´ y uˇz zná v´ ysledek pˇredchoz´ıho tahu. Hráˇc F má na v´ ybˇer strategie {r,s}, ale nem˚ uˇze uˇz nijak ovlivnit tah prvn´ıho hráˇce. V druhém pˇr´ıpadˇe prob´ıhá hra stejn´ ym zp˚ usobem, pouze je vymˇenˇené poˇrad´ı hráˇc˚ u.

Obrázek 3.1: Dynamická hra - Válka pohlav´ı

12

ˇ sen´ı dynamické hry Reˇ

Dynamické hry

3.2

ˇ sen´ı dynamick´ Reˇ e hry

Pro nalezen´ı rovnováhy dynamické hry pouˇz´ıváme zpˇetnou indukci. Procház´ıme hru od konce a vyuˇz´ıváme znalost´ı o pˇredchoz´ıch taz´ıch. Pokud tuto metodu pouˇzijeme na hru z Obrázku 3.1 (moˇznost, kde hráˇc M hraje jako prvn´ı), budeme postupovat následovnˇe: Hráˇc F má v kaˇzdé vˇetvi dvˇe moˇznosti, a to r nebo s. Pokud by hráˇc M zahrál R, hráˇc F vybere také r, protoˇze z této strategie má lepˇs´ı uˇzitek, ve druhé vˇetvi dopadne v´ ybˇer analogicky. Nyn´ı se pˇresuneme na tah hráˇce M. Hráˇc M uˇz v´ı, ˇze pokud zahraje R, F zahraje taky r a pokud zahraje S, hráˇc F zahraje taky s. Staˇc´ı pouze vybrat strategii, ze které má lepˇc´ı uˇzitek, tedy R. T´ımto postupem dostaneme rovnováhu (R, r). Pro dynamické hry m˚ uˇzeme také definovat Nashovu rovnováhu, která vycház´ı z konstrukce zpˇetné indukce. Nejprve ale potˇrebujeme zavést pojem dynamická podhra. Definice 4. Dynamická podhra je podstrom, kter´ y mus´ı splˇ novat následuj´ıc´ı podm´ınky: 1. Zaˇcátek se nacház´ı v libovolném uzlu stromu (vyjma koneˇcn´ ych uzl˚ u s uˇzitky). 2. Hráˇc zná vˇsechna rozhodnut´ı provedená do tohoto ˇcasu (ve kterém se nacház´ı poˇca´teˇcn´ı uzel). 3. Podhra obsahuje vˇsechny uzly, které následuj´ı poˇca´teˇcn´ı uzel. Definice 5. Nashova rovnováha vzhledem k podhrám je rovnováha dynamické hry, která je Nashovou rovnováhou v kaˇzdé podhˇre této dynamické hry. Problém existence takové rovnováhy je vyˇreˇsen následuj´ıc´ı vˇetou, jej´ıˇz d˚ ukaz je uveden ve Webb [1]. Vˇ eta 2. Kaˇzdá koneˇcná dynamická hra má alespoˇ n jednu Nashovu rovnováhu vzhledem k podhrám. Otázka jednoznaˇcnosti rovnováhy je u dynmaick´ ych her snaˇzˇs´ı neˇz u statick´ ych her. 13

Dynamické hry

Výhoda poˇrad´ı

Vˇ eta 3. Pokud je hra generická, tj. nenastává rovnost uˇzitk˚ u, pak existuje právˇe jedna Nashova rovnováha vzhledem k podhrám. D˚ ukaz. Vypl´ yvá z konstrukce zpˇetné indukce.

3.3

V´ yhoda poˇ rad´ı

Z Vˇety 3 vypl´ yvá, ˇze dynamická verze hry Válka pohlav´ı má právˇe jednu Nashovu rovnováhu vzhledem k podhrám, stejnˇe jako dynamická verze hry Jestˇrábi a holubice. Pro nalezen´ı jednoznaˇcné rovnováhy tˇechto statick´ ych her je staˇc´ı pouze pˇrevést na dynamickou hru. Je zˇrejmé (kv˚ uli jednoznaˇcnosti rovnováhy), ˇze v´ ysledná rovnováha je v´ yhodnˇejˇs´ı pouze pro jednoho hráˇce. Zavedeme pojem v´ yhra hráˇce. Definice 6. Budeme ˇr´ıkat, ˇze hráˇc, jehoˇz preferovaná rovnováha je Nashova rovnáha vzhledem k podhrám, vyhrál. Následuj´ıc´ı vˇety uvádˇej´ı podm´ınky v´ yhry hráˇc˚ u. Lemma 1. Uvaˇzujeme scénáˇr Válka pohlav´ı. Hru vyhraje hráˇc, který má moˇznost prvn´ıho tahu. D˚ ukaz. D˚ ukaz provedeme tak, ˇze vyˇreˇs´ıme hru zpˇetnou indukc´ı pro obˇe dvˇe varianty zaˇc´ınaj´ıc´ıho hráˇce. T´ım bude vˇeta dokázaná pro oba dva hráˇce, protoˇze ukáˇzeme, ˇze hráˇc M vyhraje, kdyˇz bude zaˇc´ınat a zároveˇ n nevyhraje, kdyˇz bude zaˇc´ınat hráˇc F. Varianta hry, kde zaˇc´ıná hráˇc M je uˇz vyˇreˇsená v kapitole 3.2. Nashova rovnováha je v tomto pˇr´ıpadˇe (R, r), coˇz je v´ ysledek preferovan´ y hráˇcem M. Pokud zaˇc´ıná hru hráˇc F, zpˇetná indukce bude vypadat takto: Hráˇc M vyb´ırá lepˇs´ı strategii v obou vˇetv´ıch. Ve vˇetvi stromu, kde v´ı, ˇze F zahrál strategii r vybere strategii R, ve druhé vˇetvi vybere S. Hráˇc F v´ı, jaké strategie bude hrát M v závislosti na jeho volbˇe, vybere tedy v´ yhodnˇejˇs´ı strategii, kterou je S. Nashova rovnováha he tedy (s, S), v´ ysledek preferovan´ y hráˇcem F. (V rovnováze u dynamick´ ych her p´ıˇseme nejprve strategii zaˇc´ınaj´ıc´ıho hráˇce, z toho d˚ uvodu jsou strategie v opaˇcném poˇrad´ı.) Lemma 2. Uvaˇzujeme scénáˇr Jestˇrábi a holubice. Hru vyhraje hráˇc, který má moˇznost prvn´ıho tahu.

14

Dynamické hry

Výhoda poˇrad´ı

D˚ ukaz. D˚ ukaz provedeme stejnˇe jako u pˇredchoz´ı vˇety. Zpˇetná indukce pro pˇr´ıpad, kdy zaˇc´ıná hráˇc M: Hráˇc F vyb´ırá lepˇs´ı strategii v obou vˇetv´ıch stromu. Ve vˇetvi, kde v´ı, ˇze hráˇc M zahrál strategii R, zahraje strategii s, ve druhé vˇetvi vybere strategii r. Hráˇc M zná strategie, které bude hrát hráˇc F v závislosti na jeho volbˇe v prvn´ım kole. Vybere tedy v´ yhodnˇejˇs´ı strategii R a vznikne Nashova rovnováha (R, s). Zpˇetná indukce pro hru, kdyˇz zaˇc´ıná hráˇc F: Hráˇc M opˇet vybere nejv´ yhodnˇejˇs´ı strategii v obou vˇetv´ıch. Ve vˇetvi, kde hráˇc F vybral r, vybere S, ve druhé vˇetvi zvol´ı R. Hráˇc F zná reakce hráˇce M, vybere tedy v´ yhodnˇejˇs´ı strategii r a vznikne Nashova rovnováha (r, S). Kaˇzdá rovnováha je opˇet preferovan´ y v´ ysledek zaˇc´ınaj´ıc´ıho hráˇce. Hráˇc, kter´ y má v´ yhodu prvn´ıho tahu se naz´ yvá Stackelberg˚ uv leader. Problém nejednoznaˇcnosti rovnováhy ve statické hˇre je moˇzné vyˇreˇsit pˇreveden´ım na dynamickou hru. Preferovanou rovnováhu potom z´ıská hráˇc, kter´ y má moˇznost prvn´ıho tahu, tedy Stackelberg˚ uv leader.

15

4 Dynamické hry s náhodným ˇ casov´ an´ım tah˚ u Tato kapitola popisuje také dynamické hry, ale se speciáln´ım ˇcasován´ım tah˚ u. Budeme uvaˇzovat ˇcasován´ı náhodné, zadané nˇejak´ ym pravdˇepodobnostn´ım rozdˇelen´ım. Tato myˇslenka má své koˇreny pˇredevˇs´ım v ˇclánc´ıch Libich a Stehl´ık [3], Cho a Matsui [4], Lagunoff a Matsui [5] a Kamada a Kandori [6]. Ve ˇclánku Libich a Stehl´ık [3] autoˇri uvaˇzovali náhodné ˇcasován´ı tah˚ u pouze pro jednoho hráˇce. Druh´ y hráˇc mˇel moˇznost pouze simultánn´ıho tahu. V této kapitole se budeme zab´ yvat situac´ı, kde se náhodné ˇcasován´ı tah˚ u t´ yká obou hráˇc˚ u, ale pravdˇepodobnostn´ı rozdˇelen´ı tohoto ˇcasován´ı tah˚ u jednotliv´ ych hráˇc˚ u se navzájem nepˇrekr´ yvá.

4.1

Popis hry

Hra prob´ıhá v ˇcasovém intervalu od 0 do 1. V ˇcase 0 zahraj´ı oba hráˇci simultánn´ı tah, tedy ani jeden nev´ı, jakou strategii zahrál soupeˇr. Dále pˇredpokládáme, ˇze hráˇc M má moˇznost opakován´ı tah˚ u v ˇcasovém intervalu [0, K], kde 0 < K < 1. Hráˇc F má moˇznost opakován´ı tah˚ u v ˇcasovém intervalu [L, 1], kde K ≤ L < 1. Definice 7. Tahy, které následuj´ı po simultánn´ım tahu, budeme naz´ yvat revize. Prvn´ı provedenou revizi kaˇzdého hráˇce oznaˇc´ıme jako Revize (s velk´ ym p´ısmenem). Pro oba hráˇce je d˚ uleˇzitá pouze prvn´ı Revize. T´ımto tahem mohou poprvé reagovat na simultánn´ı tah (v pˇr´ıpadˇe prvn´ıho hráˇce) nebo reagovat na Revizi prvn´ıho hráˇce (v pˇr´ıpadˇe druhého hráˇce). Vˇsechny ostatn´ı revize jsou zanedbatelné, protoˇze jsou provádˇeny za stejn´ ych podm´ınek jako Revize a nemaj´ı uˇz ˇza´dn´ y vliv na pr˚ ubˇeh hry.

4.2

ˇ Casov´ an´ı reviz´ı

Hráˇci maj´ı moˇznost reviz´ı omezenou na urˇcit´ y podinterval ([0, K] pro hráˇce M a [L, 1] pro hráˇce F) celkového hern´ıho ˇcasu [0,1] a zároveˇ n je ˇcasován´ı reviz´ı 16

ˇ Casov´ an´ı reviz´ı

Dynamické hry s náhodným ˇcasován´ım tah˚ u CDF 1 0.3

1

à H1-MHtLLdt

à H1-FHtLLdt

0

0.6

MHtL

0.1

FHtL

0.3

à MHtLdt

à FHtLdt

0

0.6

0.2

1

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

t

Obrázek 4.1: Revizn´ı funkce

urˇceno pravdˇepodobnostn´ım rozdˇelen´ım na tomto podintervalu. Definice 8. Pravdˇepodobnostn´ı rozdˇelen´ı náhodného ˇcasován´ı reviz´ı je popsáno pravdˇepodobnostn´ı funkc´ı nebo funkc´ı hustoty daného pravdˇepodobnostn´ıho rozdˇelen´ı. Pro hráˇce M oznaˇc´ıme funkci m(t), pro hráˇce F ji oznaˇc´ıme f(t). Pro u ´ˇcely naˇs´ı práce bude d˚ uleˇzitˇejˇs´ı distribuˇcn´ı funkce tohoto pravdˇepodobnostn´ıho rozdˇelen´ı. Definice 9. Distribuˇcn´ı funkce pravdˇepodobnostn´ıho rozdˇelen´ı M (t) : [0, 1] → [0, 1], M (0) = 0, M (K) = 1, F (t) : [0, 1] → [0, 1], F (L) = 0, F (1) = 1, nazveme Revizn´ı funkce. Pˇr´ıklady Revizn´ıch funkc´ı máme na Obrázku 4.1. Rozdˇelen´ı náhodn´ ych tah˚ u je pro jednoduchost rovnomˇerné a hodnoty parametr˚ u jsouR K = 0, 3 K a L = 0, 6. Plochy pod funkcemi M (t) a F (t) jsou urˇceny integrály 0 M (t)dt 17

Dynamické hry s náhodným ˇcasován´ım tah˚ u

Výbˇer optimáln´ı rovnováhy

R1 a L F (t)dt. Tyto plochy udávaj´ı rychlost reakc´ı hráˇc˚ u, zat´ımco integrály RK R1 (1 − M (t))dt a L (1 − F (t))dt, tedy plochy nad funkcemi M (t) a F (t), 0 udávaj´ı rigiditu hráˇc˚ u (vˇernost p˚ uvodn´ımu rozhodnut´ı). Z Obrázku 4.1 je zˇrejmé, ˇze pro hráˇce M bude platit Z

K

K

Z (1 − M (t))dt +

K= 0

M (t)dt 0

a pro hráˇce F bude platit Z

1

Z

L

4.3

1

(1 − F (t))dt +

1−L=

F (t)dt. L

V´ ybˇ er optim´ aln´ı rovnov´ ahy

Zkoumáme takov´ yto typ hry pro dva uvedené scénáˇre: Válka pohlav´ı a Jestˇra´bi a holubice. V tˇechto hrách ve statické formˇe existuj´ı dvˇe ˇcisté Nashovy rovnováhy, ale docház´ı ke stˇretu zájm˚ u hráˇc˚ u. Kaˇzd´ y hráˇc preferuje jinou rovnováhu. Stejnˇe jako klasickou dynamickou hrou, m˚ uˇzeme i t´ımto zp˚ usobem vyˇreˇsit problém v´ ybˇeru optimáln´ı rovnováhy. Nejprve definujeme pojem v´ yhra. Definice 10. Pokud hráˇcova preferovaná rovnováha bude Nashovou rovnováhou v celém pr˚ ubˇehu hry, potom ˇrekneme, ˇze hráˇc vyhrává hru. Následuj´ıc´ı vˇety udávaj´ı podm´ınky v´ yhry hráˇce M pro oba zm´ınˇené scénáˇre. Postup nalezen´ı tˇechto podm´ınek bude demonstrován v d˚ ukazu. Vˇ eta 4. Uvaˇzujeme scénáˇr Válka pohlav´ı. Hráˇc M vyhraje hru (tj. rovnováha (R, r) bude Nashova rovnováha v celém pr˚ ubˇehu hry), pokud budou splnˇené podm´ınky RK R1 M (t)dt + L (1 − F (t))dt + (L − K) a−d 0 < , (4.1) R1 d−b F (t)dt L

RK 0

R1 M (t)dt + L (1 − F (t))dt + (L − K) z−y . > RK w−x (1 − M (t))dt 0 18

(4.2)



1 Poznámka 3. Levou stranu nerovnice (4.1) oznaˇc´ıme UM , pravou stranu VV1P . 2 Levá strana nerovnice (4.2) bude m´ıt oznaˇcen´ı UM a pravá strana VV2P .

D˚ ukaz. Pˇri d˚ ukazu Vˇety 4 budeme postupovat od konce hry, tzv. zpˇetnou indukc´ı. Pro v´ yhru hráˇce M, je nutné, aby oba hráˇci ve vˇsech sv´ ych taz´ıch volili strategie R (v pˇr´ıpadˇe hráˇce M) a r (v pˇr´ıpadˇe hráˇce F). Zaˇcneme tedy Reviz´ı hráˇce F. Tento tah je hráˇc˚ uv posledn´ı, coˇz znamená, ˇze mus´ı volit strategii, ze které mu plyne nejvˇetˇs´ı uˇzitek. Tento uˇ Rz1itek pak pro nˇej pˇretrvává pouze do konce hry, tedy ˇcas dan´ y v´ yrazem L F (t)dt. Mohou nastat dvˇe situace v závislosti na strategii, kterou zvol´ı hráˇc M ve své Revizi: (I) Hráˇc M zvol´ı v Revizi strategii R. (II) Hráˇc M zvol´ı v Revizi strategii S. V prvn´ım pˇr´ıpadˇe (I) je pro hráˇce F nejlepˇs´ı reakce strategie r a v druhém pˇr´ıpadˇe (II) strategie s. Z obou tˇechto voleb má nejvˇetˇs´ı moˇzn´ y uˇzitek. V´ıme tedy, ˇze hráˇc F se svoj´ı Reviz´ı pˇrizp˚ usob´ı Revizi hráˇce M. Nyn´ı nalezneme podm´ınku pro Revizi hráˇce M. Potˇrebujeme, aby hráˇc M volil ve své Revizi strategii R. Opˇet m˚ uˇzeme rozdˇelit na dva pˇr´ıpady v závislosti na simultánn´ım tahu hráˇce F: (I) Hráˇc F zvol´ı v simultánn´ım tahu strategii r. (II) Hráˇc F zvol´ı v simultánn´ım tahu strategii s. Pokud nastane situace (I), nejlepˇs´ı reakce hráˇce M je zahrát strategii R a to z toho d˚ uvodu, ˇze F v Revizi zahraje také r. T´ım je zajiˇstˇeno, ˇze hráˇc M bude m´ıt aˇz do konce hry uˇzitek a, kter´ y je podle nerovnice (2.4.1) z kapitoly 2.4.1 vˇzdy vˇetˇs´ı neˇz jak´ ykoliv jin´ y. V pˇr´ıpadˇe ˇze nastane situace (II), mus´ı b´ yt splnˇena následuj´ıc´ı nerovnice, aby se hráˇci M vyplatilo zahrát strategii R, tj. celkov´ y souˇcet uˇzitk˚ u, které hráˇc má ze strategie R, násoben´ ych ˇcasem, ve kterém pˇretrvávaj´ı, mus´ı b´ yt vˇetˇs´ı, neˇz celkov´ y souˇcet uˇzitk˚ u násoben´ ych ˇcasem, ve kterém pˇretrvávaj´ı, jeˇz hráˇci plynou ze strategie S.

K

Z

1

Z M (t)dt + b(L − K) + b

b 0

Z

(1 − F (t))dt + a L

K

Z

0

F (t)dt > L

1

M (t)dt + d(L − K) + d

d

1

Z Z (1 − F (t))dt + d

L

F (t)dt L

19

(4.3)

1



Jednotlivé ˇcleny nerovnice (4.3) znamenaj´ı vˇzdy nˇejak´ y ˇcasov´ yu ´sek hry. InRK tegrál 0 M (t)dt udává ˇcas po Revizi hráˇce M, L − K je doba od ˇcasu K do R1 ˇcasu L, L (1 − F (t))dt je doba od ˇcasu L do ˇcasu, kdy hráˇc F provede Revizi. R1 Nakonec intergrál L F (t)dt udává ˇcas po Revizi hráˇce F. V tˇechto ˇcasech potom pˇretrvávaj´ı uˇzitky ze zvolen´ ych strategi´ı obou hráˇc˚ u. Napˇr´ıklad v ˇcase RK M (t)dt pˇretrvává pro hráˇce M uˇzitek b, kter´ y odpov´ıdá tomu, ˇze hráˇc F 0 zvolil v simultánn´ım tahu strategii s a hráˇc M zahrál v Revizi strategii R. Nerovnici (4.3) m˚ uˇzeme dále upravit.

Z (b − d)

K

Z

1

M (t)dt + (L − K) + 0

(1 − F (t))dt

Z

1

> (d − a)

L

F (t)dt L

(4.4) R1 Vydˇel´ıme nerovnici (4.4) ˇcleny L F (t)dt a (b−d). Protoˇze (b−d) je záporn´ y, mus´ıme zároveˇ n zamˇenit znaménko nerovnosti. RK 0

M (t)dt +

R1

(1 − F (t))dt + (L − K) d−a < R1 b−d F (t)dt L

L

(4.5)

Pokud uˇz jen rozˇs´ıˇr´ıme zlomek na pravé stranˇe nerovice (4.5) hodnotou −1, dostáváme tvar (4.1) uveden´ y v dokazované vˇetˇe, kter´ y je názornˇejˇs´ı, protoˇze na jedné stranˇe obsahuje pouze hodnoty závislé na parametrech K a L a na stranˇe druhé zase jen hodnoty uˇzitk˚ u a, b a d. Nakonec mus´ıme zajistit, aby oba hráˇci volili v simultánn´ım tahu strategii R, popˇr´ıpadˇe r. Nejprve vyˇsetˇr´ıme simultánn´ı tah hráˇce F. Znovu se nám tato situace rozpadne na dvˇe ˇca´sti: (I) Hráˇc M zvol´ı v simultánn´ım tahu strategii R. (II) Hráˇc M zvol´ı v simultánn´ım tahu strategii S. V prvn´ım pˇr´ıpadˇe (I) je pro hráˇce F vˇzdy nejlepˇs´ı zvolit strategii r, nebot’ z´ıská po celou dobu do své Revize uˇzitek w, kter´ y je dle nerovnic (2.4.1) vˇetˇs´ı neˇz x. Pokud nastane situace (II), mus´ı b´ yt splnˇena následuj´ıc´ı nerovnice, aby hráˇc F zahrál strategii r. 20


Z

K

Z

K


Z

M (t)dt + w(L − K) + w 0 0 Z K Z Z K (1 − M (t))dt + x M (t)dt + x(L − K) + x z

1

(1 − M (t))dt + w

y

0

0

(1 − F (t))dt > L 1

(1 − F (t))dt

L

(4.6) R1 ˇ po Revizi hráˇce F dan´ Cas y integrálem L F (t)dt uˇz neuvaˇzujeme, protoˇze ˇclen obsahuj´ıc´ı tento integrál by byl na obou stranách nerovnice (4.6) stejn´ y. Tuto nerovnici (4.6) m˚ uˇzeme stejn´ ymi algebraick´ ymi u ´pravami dostat do poˇzadovaného tvaru (4.2), kter´ y je uveden´ y v dokazované vˇetˇe. Stejn´ ym zp˚ usobem zjist´ıme podm´ınku pro to, aby hráˇc M volil v simultánn´ım tahu strategii R. TentokráRt nás bude ale zaj´ımat jen ˇcas do Revize hráˇce M, K kter´ y je dan´ y integrálem 0 (1 − M ((t))dt. Pokud budeme pˇredpokládat, ˇze hráˇc F v simultánn´ım tahu zahraje strategii r, staˇc´ı pouze porovnat jak´ y bude m´ıt ve zm´ınˇeném ˇcase hráˇc M uˇzitek ze zvolen´ı strategie R, coˇz je uˇzitek a, a ze zvolen´ı strategie S, coˇz je uˇzitek c. Dle nerovnic (2.4.1) je zˇrejmé, ˇze a > c, hráˇc M tedy bude volit strategii R v simultánn´ım tahu pokud bude splnˇená podm´ınka pro simultánn´ı tah hráˇce F oznaˇcená (4.2).

Vˇ eta 5. Uvaˇzujeme scénáˇr Jestˇrábi a holubice. Hráˇc M vyhraje hru (tj. rovnováha (R, s) bude Nashova rovnováha v celém pr˚ ubˇehu hry), pokud budou splnˇené podm´ınky RK R1 M (t)dt + (1 − F (t))dt + (L − K) b−c 0 L < , (4.7) R1 c−a F (t)dt L

RK 0

R1 M (t)dt + L (1 − F (t))dt + (L − K) y−z > . RK x−w (1 − M (t))dt 0

(4.8)

1 1 Poznámka 4. Levou stranu nerovnice (4.7) oznaˇc´ıme UM , pravou stranu VJH . 2 2 Levá strana nerovnice (4.8) bude m´ıt oznaˇcen´ı UM a pravá strana VJH .

D˚ ukaz. D˚ ukaz bude proveden´ y stejn´ ym zp˚ usobem jako pro Vˇetu 4.

21


4.3.1


Jin´ y zp˚ usob vyj´ adˇ ren´ı podm´ınky v´ yhry

V nˇekter´ ych pˇr´ıpadech mohou b´ yt Revizn´ı funkce sloˇzité, tˇeˇzko integrovatelné nebo je neznáme pˇresnˇe. Z toho d˚ uvodu jsme naˇsli jin´ y ekvivalentn´ı tvar podm´ınky v´ yhry hráˇce M, kter´ y vyuˇz´ıvá pouze znalosti parametr˚ u K a L a stˇredn´ıch hodnot pravdˇepodobnostn´ıch rozdˇelen´ı náhodného ˇcasován´ı tah˚ u. Následuj´ıc´ı lemma je bˇeˇznˇe znám´ y statistick´ y v´ ysledek, vysvˇetlen´ y napˇr´ıklad v Kallenberg [7], z toho d˚ uvodu je zde uvádˇena bez d˚ ukazu. Lemma 3. Uvaˇzujeme funkci M (t) z Definice 9. Potom plat´ı Z

K

(1 − M (t))dt = µM .

(4.9)

0

Stejnˇe tak uvaˇzujeme funkci F (t) z Definice 9. Potom plat´ı Z 1 (1 − F (t))dt = µF − L.

(4.10)

L

Vˇ eta 6. Pˇredpokládejme, ˇze µM a µF jsou stˇredn´ı hodnoty pravdˇepodobnostn´ıch rozdˇelen´ı náhodného ˇcasován´ı tah˚ u hráˇc˚ u M a F. Potom budou podm´ınky výhry hráˇce M ve tvaru µF − µM < Vi1 1 − µF

i = {V P, JH},

(4.11)

µF − µM > Vi2 µM

i = {V P, JH}.

(4.12)

1 2 D˚ ukaz. Abychom mohli aplikovat pˇredchoz´ı Lemma 3 na v´ yraz UM a UM , je RK R1 nutné upravit integrály 0 M (t)dt a L F (t)dt pouˇzit´ım vzorc˚ u pro linearitu a aditivitu urˇcit´ ych integrál˚ u.

Z

K

K

Z

(M (t) + 1 − 1)dt =

M (t)dt = 0

1

1

Z

L

Z

1

1dt − L

22

0

1

(F (t) + 1 − 1)dt =

F (t)dt = L

(1 − M (t))dt,

0

Z

K

Z 1dt −

0

Z

K

Z

(1 − F (t))dt. L



Uˇzit´ım Lemmatu 3 dostáváme Z K M (t)dt = K − µM , 0

Z

1

F (t)dt = 1 − µF . L

Po dosazen´ı za integrály do podm´ınek v´ yhry hráˇce M máme

K − µM + µF − L + L − K µF − µM = < Vi1 1 − µF 1 − µF

i = {V P, JH},

µF − µM K − µM + µF − L + l − K = > Vi2 µM µM

i = {V P, JH},

coˇz jsou pˇresnˇe dokazované nerovnice (4.11) a (4.12).

4.3.2

V´ ymˇ ena poˇ rad´ı hr´ aˇ c˚ u

Doposud jsme pˇredpokládali, ˇze hráˇc M má moˇznost opakovat tah dˇr´ıve neˇz hráˇc F. Nyn´ı budeme pˇredpokládat opaˇcné poˇrad´ı hráˇc˚ u. Poznámka 5. M˚ uˇzeme také uvaˇzovat, ˇze hráˇc F bude m´ıt moˇznost provést Revizi jako prvn´ı. Revizn´ı funkce jsou v tomto pˇr´ıpadˇe F (t) : [0, 1] → [0, 1], F (0) = 0, F (K) = 1, M (t) : [0, 1] → [0, 1], M (L) = 0, M (1) = 1. Podm´ınky v´ yhry hráˇce F jsou ve stejném tvaru, pouze jsou pouˇzity pˇr´ısluˇsné Revizn´ı funkce a uˇzitky. Hráˇc F vyhraje, tj. jeho preferovaná rovnováha bude Nashovou rovnováhou v celém pr˚ ubˇehu hry, pokud bude splnˇeno, ˇze

RK 0

R1 F (t)dt + (L − K) + L (1 − M (t))dt < Wi1 R1 M (t)dt L 23

i = {V P, JH}, (4.13)


RK 0

R1 F (t)dt + (L − K) + L (1 − M (t))dt > Wi2 RK (1 − F (t))dt 0


i = {V P, JH}. (4.14)

Levou stranu nerovnice (4.13) oznaˇc´ıme jako UF1 a levou stranu nerovnice (4.14) jako UF2 . Podm´ınku v´ yhry m˚ uˇzeme vyjádˇrit i ve tvaru s vyuˇzit´ım stˇredn´ıch hodnot pravdˇepodobnostn´ıch rozdˇelen´ı náhodného ˇcasován´ı tah˚ u. µM − µF < Wi1 1 − µM µM − µF > Wi2 µF

i = {V P, JH}, i = {V P, JH}.

Pro scénáˇr Válka pohlav´ı je WV1 P =

z−w , w−x

WV2 P =

a−c . d−b

2 WJH =

b−d . c−a

Pro scénáˇr Jestˇra´bi a holubice je

1 WJH =

y−x , x−w

24

5 Pˇr´ıklady, závislosti na parametrech a uˇ zitc´ıch V této kapitole uvedeme pˇr´ıklady pro ilustraci v´ yˇse uveden´ ych Vˇet 4 a 6, které udávaj´ı podm´ınku v´ yhry hráˇce M ve scénáˇr´ıch Válka pohlav´ı a Jestˇrábi a holubice. Dále prozkoumáme, jak jsou tyto podm´ınky v´ yher závislé na zmˇenách parametr˚ u (K, L) a uˇzitk˚ u (a, b, c, d, w, x, y, z).

5.1

Ilustraˇ cn´ı pˇ r´ıklady

Uvedeme zde dva pˇr´ıklady. V prvn´ım pˇr´ıkladu vyuˇzijeme pro v´ ypoˇcet Vˇetu 4, ve druhém pouˇzijeme zjednoduˇsˇsené tvary tˇechto podm´ınek z Vˇety 6. Pˇr´ıklad 3. Uvaˇzujeme scénáˇr Válka pohlav´ı a uˇzitky zvol´ıme následovnˇe: F a A 2,1 M B 0,0

b 0,0 1,2

Parametry K a L zvol´ıme tak, ˇze K = L = 0, 5. Revizn´ı funkce jsou distribuˇcn´ı funkce rovnomˇerného rozdˇelen´ı znázornˇené na Obrázku 5.1:   0 kdyˇz t ≤ 0 2t kdyˇz t ∈ (0; 0, 5) , M (t) =  1 kdyˇz t ≥ 0, 5  kdyˇz t ≤ 0, 5  0 2t − 1 kdyˇz t ∈ (0, 5; 1) . F (t) =  1 kdyˇz t ≥ 1 Aby hráˇc M vyhrál, mus´ı b´ yt splnˇené obˇe dvˇe podm´ınky, (4.1) i (4.2), které 1 2 udává Vˇeta 4. Vypoˇcteme tedy hodnoty v´ yraz˚ u UM , UM , VV1P a VV2P a porovnáme. 25

Pˇr´ıklady, závislosti na parametrech a uˇzitc´ıch

Ilustraˇcn´ı pˇr´ıklady

CDF 1 0.5

1

à H1-MHtLLdt

à H1-FHtLLdt

0

0.5

MHtL

0.1

FHtL

0.5

à MHtLdt

à FHtLdt

0

0.5

0.2

0.3

1

0.4

0.5

0.6

0.7

0.8

0.9

1

t

Obrázek 5.1: Revizn´ı funkce pouˇzité v pˇr´ıkladu 3

RK 1 UM

=

0

M (t)dt +

R1

(1 − F (t))dt + (L − K) 0, 25 + 0, 25 + 0 = =2 R1 0, 25 F (t)dt L

L

VV P =

2−1 a−d = =1 d−b 1−0

1 V tomto pˇr´ıpadˇe je UM > VV1P , tud´ıˇz nen´ı splnˇená uˇz prvn´ı podm´ınka v´ yhry (4.1) z Vˇety 4, která zajiˇst’uje, aby hráˇc M ve své Revizi zvolil strategii R. Hráˇc M nevyhrává tuto hru.

Obdobn´ y pˇr´ıklad m˚ uˇzeme ukázat také pro druh´ y zpracovávan´ y scénáˇr. Pˇr´ıklad 4. Uvaˇzujeme scénáˇr Jestˇrábi a holubice a uˇzitky zvol´ıme následovnˇe: F a A 0,0 M B 1,5

26

b 5,1 0,0



Zvol´ıme K = 0, 4 a L = 0, 6. Revizn´ı funkce v tomto pˇr´ıpadˇe neznáme. Známe pouze stˇredn´ı hodnoty pravdˇepodobnostn´ıch rozdˇelen´ı Reviz´ı, a to µM = 0, 1 a µF = 0, 7. 1 1 Vypoˇcteme zjednoduˇsˇsené UM a VJH a zjist´ıme, zda je splnˇená podm´ınka (4.11), kterou udává Vˇeta 6.

1 UM =

0, 7 − 0, 1 µF − µM = =2 1 − µF 1 − 0, 7

1 VJH =

5−1 b−c = =4 c−a 1−0

1 1 Máme UM < VJH , podm´ınka pro revizi hráˇce M je splnˇená. Nyn´ı zjist´ıme, zda je splnˇená i druhá podm´ınka (4.8) z Vˇety 6.

2 UM =

µF − µM 0, 7 − 0, 1 = =6 µM 0, 1

2 VJH =

y−z 5−0 = =5 x−w 1−0

Druhá podm´ınka v´ yhry je v tomto pˇr´ıkladˇe také splnˇená, m˚ uˇzeme ˇr´ıct, ˇre hráˇc vyhrává hru. Jeho preferovaná rovnováha (R, s) bude Nashovou rovnováhou v celém pr˚ ubˇehu hry. V Tabulce 4 je udˇelan´ y mal´ y pˇrehled závislosti stˇredn´ı hodnoty µF na stˇredn´ı hodnotˇe µM pˇri nˇekter´ ych hodnotách prav´ ych stran podm´ınek v´ yhry 1 2 VJH a VJH . Vyznaˇcená oblast obsahuje hodnoty µM a µF , pˇri kter´ ych budou podm´ınky v´ yhry hráˇce, které jsou zavedené ve Vˇetˇe 6. Obrázek v ˇra´dce 1 2 VJH = 4 a sloupci VJH = 5 se vztahuje pˇr´ımo k Pˇr´ıkladu 4. V Pˇr´ıkladu 3 nen´ı splnˇená prvn´ı podm´ınka v´ yhry (4.1) z Vˇety 4. Tento fakt m˚ uˇzeme ovlivnit zmˇenou jednotliv´ ych parametr˚ u a uˇzitk˚ u, coˇz je náplˇ n dalˇs´ı podkapitoly.

27



2 VJH =2

2 VJH =5

mi_F

mi_F

1.0

1.0

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

1 VJH =2

mi_M 0.1

0.2

0.3

0.1

0.2

0.3

0.4

0.1

0.2

0.3

0.4

0.1

0.2

0.3

0.4

0.1

0.2

0.3

0.4

mi_F

1.0

1.0

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

1 VJH =4

mi_M 0.1

0.2

0.3

mi_M

0.4

mi_F

mi_F

1.0

1.0

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

1 VJH =7

mi_M 0.1

0.2

0.3

mi_M

0.4

mi_F

1 VJH = 10

mi_M

0.4

mi_F

mi_F

1.0

1.0

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

mi_M 0.1

0.2

0.3

0.4

mi_M

Tabulka 5.1: Oblast v´ ybˇeru µM a µF , aby z˚ ustaly splnˇené obˇe podm´ınky 1 2 v´ yhry za dan´ ych hodnot prav´ ych stran VJH a VJH 28


5.2

Závislost podm´ınek výhry

Z´ avislost podm´ınek v´ yhry

V podm´ınkách v´ yhry hráˇce figuruje v´ıce uˇzitk˚ u (a, b, c, d, w, x, y, z) a parametr˚ u (K, L), jejichˇz zvˇetˇsován´ım nebo zmenˇsován´ım m˚ uˇzeme ovlivˇ novat v´ ysledek hry. V této ˇca´sti práce pop´ıˇseme jak m˚ uˇzeme ˇsanci hráˇce na v´ yhru zv´ yˇsit zmˇenou hodnoty vˇzdy pouze jednoho uˇzitku nebo parametru. Nejprve vyˇreˇs´ıme prvn´ı podm´ınku, tj. podm´ınka pro Revizi prvn´ıho hráˇce 1 (4.1), (4.8) a (4.13). Levé strany tˇechto nerovnic oznaˇcené UM a UF1 jsou vˇzdy pro oba scénáˇre stejné. Rozd´ıl pro hráˇce je pouze ve v´ ymˇenˇe pˇr´ısluˇsn´ ych Revizn´ıch funkc´ı. 1 Lemma 4. Výraz UM , popˇr´ıpadˇe UF1 , se zmenˇsuje s klesaj´ıc´ım L. 1 . D˚ ukaz pro UF1 by byl proD˚ ukaz. Provedeme d˚ ukaz pouze pro v´ yraz UM vádˇen´ y stejn´ ym zp˚ usobem, pouze se zamˇenˇen´ ymi Revizn´ımi funkcemi. V´ y1 raz UM mus´ıme zderivovat podle parametru L.

d dL

RK 0

M (t)dt +

R1

(1 − F (t))dt + (L − K) L R1 F (t)dt L

! =

1 − L + F (L) R1 F (t)dt L

A protoˇze z Definice 9 v´ıme, ˇze F (L) = 0, m˚ uˇzeme derivaci v´ yrazu UM dále upravit na

d dL

RK 0

M (t)dt +

R1

(1 − F (t))dt + (L − K) L R1 F (t)dt L

!

1−L = R1 . F (t)dt L

1 Derivace UM podle L je vˇzdy kladná, protoˇze máme zavedeno, ˇze L < 1. 1 V´ yraz UM se tedy zmenˇsuje s klesaj´ıc´ım L. 1 Poznámka 6. O tom, jak se v´ yrazy UM a UF1 chovaj´ı v závislosti na K nem˚ uˇzeme obecnˇe rozhodnout. Derivace obou v´ yraz˚ u podle K se rovná 0.

Pravé strany nerovnic (4.1), (4.7), (4.13), jsou postupnˇe oznaˇceny VV1P , 1 1 VJH , WV1 P a WJH . Pˇri snaze o zv´ yˇsen´ı ˇsance na v´ yhru je nutné tyto zlomky zvˇetˇsit. Následuj´ıc´ı lemma demonstruje, jak´ y vliv maj´ı uˇzitky vystupuj´ıc´ı v jednotliv´ ych zlomc´ıch na prvn´ı podm´ınku v´ yhry. 29



Lemma 5. (a) VV1P je rostouc´ı v a, b, klesaj´ıc´ı v d. 1 (b) VJH je rostouc´ı v b, a, klesaj´ıc´ı v c.

(c) WV1 P je rostouc´ı v z, x, klesaj´ıc´ı v w. 1 (d) WJH je rostouc´ı v y, w, klesaj´ıc´ı v x.

D˚ ukaz. D˚ ukaz provedeme pouze pro ˇca´st (a), pro ostatn´ı ˇca´sti staˇc´ı v d˚ ukazu pouze zamˇenit odpov´ıdaj´ıc´ı si uˇzitky. Abychom dokázali monotónnost v´ yrazu VV1P je nutné tento v´ yraz zderivovat postupnˇe podle vˇsech obsaˇzen´ ych uˇzitk˚ u. d da

a−d d−b

=

1 d−b

yraz VV1P je Derivace VV1P podle promˇenné a je vˇzdy kladná (d > b), tud´ıˇz v´ rostouc´ı v a. d db

a−d d−b

=

a−d (d − b)2

Derivace v´ yrazu podle b je také vˇzdy kladná (a > d > b), VV1P je rostouc´ı v b. d dd

a−d d−b

=−

a−b (d − b)2

Derivace v´ yrazu VV1P podle promˇenné d je vˇzdy záporná (a > d > b), proto je VV1P klesaj´ıc´ı v d. Nyn´ı se dostáváme ke druhé podm´ınce v´ yhry, tj. podm´ınka pro simultánn´ı tah hráˇce F. Rozbor provedeme stejn´ ym zp˚ usobem jako pro prvn´ı podm´ınku. Jedin´ y rozd´ıl je v tom, ˇze nyn´ı chceme, aby levé strany nerovnic (4.2), (4.8) 2 a (4.14) oznaˇcené UM a UF2 byly co nejvˇetˇs´ı a naopak pravé strany tˇechto 2 2 nerovnic VV2P , VJH , WV2 P a WJH zase co nejmenˇs´ı. 2 Lemma 6. Výraz UM , popˇr´ıpadˇe UF2 , se zvˇetˇsuje s rostouc´ım K i L.

30



2 D˚ ukaz. D˚ ukaz opˇet provedem jen pro UM , pro d˚ ukaz druhého v´ yrazu staˇc´ı zamˇenit Revizn´ı funkce.

d dK

! R1 RK M (t)dt + (1 − F (t))dt + (L − K) (M (K) − 1) (1 − M (t))dt 0 0 + = RK R KL 2 ( (1 − M (t))dt) (1 − M (t))dt 0 0 RK R1 −( 0 M (t)dt + L (1 − F (t))dt + (L − K))(K − M (K)) + RK ( 0 (1 − M (t))dt)2

RK

Pokud dosad´ıme za M (K) = 1 (Definice 9), m˚ uˇzeme derivaci jeˇstˇe zjednoduˇsˇsit.

! RK R1 M (t)dt + L (1 − F (t))dt + (L − K) d 0 = RK dK (1 − M (t))dt 0 RK R1 −( 0 M (t)dt + L (1 − F (t))dt + (L − K))(K − 1) RK ( 0 (1 − M (t))dt)2 2 podle K je Máme zavedené, ˇze K < 1 a L ≥ K, takˇze derivace v´ yrazu UM 2 vˇzdy kladná. UM je rostouc´ı v K.

d dL

RK 0

! R1 M (t)dt + L (1 − F (t))dt + (L − K) 1 − L + F (L) = RK RK (1 − M (t))dt (1 − M (t))dt 0 0

2 Za F (L) dosad´ıme 0 dle Definice 9 a v´ıme, ˇze L < 1, potom je derivace UM podle L vˇzdy kladná a tento v´ yraz je rostouc´ı v L.

Lemma 7. (a) VV2P je rostouc´ı v z, x, klesaj´ıc´ı v y, w. 2 (b) VJH je rostouc´ı v y, w, klesaj´ıc´ı v z, x.

(c) WV2 P je rostouc´ı v a, b, klesaj´ıc´ı v c, d. 2 (d) WJH je rostouc´ı v b, a, klesaj´ıc´ı v d, c.

31



D˚ ukaz. Provedeme d˚ ukaz pouze pro ˇca´st (a), pro ostatn´ı ˇca´sti by byl analogick´ y. Abychom zjistili, jak se bude mˇenit v´ yraz VV2P v závislosti na zmˇenách uˇzitk˚ u, mus´ıme ho postupnˇe zderivovat podle vˇsech uˇzitk˚ u, které se v nˇem nacházej´ı. d dz d dx

d dy d dw

z−y w−x

z−y w−x

=

=

z−y w−x

z−y w−x

1 w−x

z−y (w − x)2

=

=−

−1 w−x z−y (w − x)2

Z nerovnic pro uˇzitky (2.4.1) vypl´ yvá, ˇze derivace podle z i podle x je vˇzdy 2 kladná. V´ yraz VV P je rostouc´ı v z a x. Zat´ımco derivace podle y a w je vˇzdy záporná, proto je vV2 P klesaj´ıc´ı v y a w.

5.2.1

Shrnut´ı

Následnˇe ve dvou tabulkách pˇrehlednˇe shrneme v´ ysledky z Lemma 4, 5, 6 a 7. ˇ Cásti tabulek pro prvn´ı podm´ınku ˇr´ıkaj´ı, co je tˇreba udˇelat, abychom zmenˇsili 1 rozd´ıl UM −Vi1 v pˇr´ıpadˇe, kdy Revizi provád´ı prvn´ı hráˇc M. Pro opaˇcn´ y pˇr´ıpad 1 1 zmenˇsujeme rozd´ıl UF − Wi . Rozd´ıly v uveden´ ych tvarech vycház´ı z prvn´ı 1 1 podm´ınky v´ yhry, která je ve tvaru UM < Vi , respektive UF1 < Wi1 , kde ˇ asti tabulek pro druhou podm´ınku zase dávaj´ı návod, jak i = {V P, JH}. C´ 2 zvˇetˇsit rozd´ıl Ui − Vi2 (v pˇr´ıpadˇe, ˇze prvn´ı provád´ı Revizi hráˇc M), respektive UF2 − Wi2 (v pˇr´ıpadˇe, ˇze prvn´ı provád´ı Revizi hráˇc F). Rozd´ıly opˇet vycház´ı 2 z podm´ınky v´ yhry, druhá podm´ınka je ve tvaru UM > Vi2 , pˇr´ıpadnˇe UF2 > Wi2 , kde opˇet i = {V P, JH}.

32



Scénáˇr Válka pohlav´ı Jestˇrábi a holubice Podm´ınka 1. podm´ınka 2. podm´ınka 1. podm´ınka 2. podm´ınka a ↑ × ↑ × b ↑ × ↑ × c nemá vliv × ↓ × a ↓ × nemá vliv × w × ↑ × ↓ x × ↓ × ↑ y × ↑ × ↓ z × ↓ × ↑ K nelze ob. urˇcit ↑ nelze ob. urˇcit ↑ L ↓ ↑ ↓ ↑ Tabulka 5.2: Závislost podm´ınek v´ yhry hráˇce M na uˇzitc´ıch a parametrech

Scénáˇr Válka pohlav´ı Jestˇrábi a holubice Podm´ınka 1. podm´ınka 2. podm´ınka 1. podm´ınka 2. podm´ınka a × ↓ × ↓ b × ↑ × ↓ c × ↑ × ↑ d × ↑ × ↑ w ↓ × ↑ × x ↑ × ↓ × y nemá vliv × ↑ × z ↑ × nemá vliv × K nelze ob. urˇcit ↑ nelze ob. urˇcit ↑ L ↓ ↑ ↓ ↑ Tabulka 5.3: Závislost podm´ınek v´ yhry hráˇce F na uˇzitc´ıch a parametrech

33



Vysvˇetlivky pro Tabulky 5.2 a 5.3: ↑ - je tˇreba zv´ yˇsit hodnotu parametru nebo uˇzitku, ↓ - je tˇreba sn´ıˇzit hodnotu parametru nebo uˇzitku, × - parametr nebo uˇzitek se v podm´ınce nevyskytuje.

34

6 Závˇer V poˇca´tku práce jsme vytvoˇrili teoretické zázem´ı a zavedli vˇsechny d˚ uleˇzité pojmy jako jsou statická hra, uˇzitek, rovnováha a Nashova rovnováha. Uvedli jsme základn´ı pˇredpoklady teorie her a zm´ınili jsme Nashovu vˇetu, která nám zaruˇcuje existenci rovnováhy. Zamˇeˇrili jsme se v´ yhradnˇe na scénáˇre Válka pohlav´ı a Jestˇra´bi a holubice, protoˇze v obou scénáˇr´ıch nalézáme problém v´ ybˇeru jednoznaˇcné rovnováhy. Oba tyto scénáˇre jsme d˚ ukladnˇe popsali a ukázali jejich konkrétn´ı pˇr´ıklady. Uvedli jsme teoretick´ y základ ke klasick´ ym dynamick´ ym hrám, definovali jsme zde Nashovu rovnováhu vzhledem k podhrám a zm´ınili jsme vˇety existence a jednoznaˇcnosti Nashov´ ych rovnováh. Definovali jsem v´ yhru hráˇce v dynamické hˇre tak, ˇze preferovaná rovnováha hráˇce mus´ı b´ yt Nashovou rovnováhou vzhledem k podhrám. Následnˇe jsme ukázali, ˇze zde plat´ı v´ yhoda poˇrad´ı. Zaˇc´ınaj´ıc´ı hráˇc vˇzdy z´ıskává preferovanou rovnováhu. T´ımto jsme z´ıskali pouze jedinou Nashovu rovnováhu jako ˇreˇsen´ı hry, která je optimáln´ı pro zaˇc´ınaj´ıc´ıho hráˇce. V dalˇs´ı ˇca´sti práce jsme se vˇenovali dynamick´ ym hrám s náhodn´ ym ˇcasován´ım tah˚ u, které je zadané pravdˇepodobnostn´ım rozdˇelen´ım. Uvaˇzovali jsme pouze pˇr´ıpad, kdy se pravdˇepodobnostn´ı rozdˇelen´ı pro jednotlivé hráˇce nepˇrekr´ yvá. Prvn´ı opakován´ı tahu jsme oznaˇcili jako Revizi. Distribuˇcn´ı funkce pravdˇepodobnostn´ıch rozdˇelen´ı náhodného ˇcasován´ı Reviz´ı jsme definovali jako Revizn´ı funkce. Opˇet jsme hledali podm´ınku v´ yhry hráˇce za pˇredpokladu, ˇze hráˇc vyhrává, pokud je jeho preferovaná rovnováha Nashovou rovnováhou v celém pr˚ ubˇehu hry. Tyto podm´ınky jsme naˇsli vyuˇzit´ım metody zpˇetné indukce a urˇcili jsme je pro oba scénáˇre, ale i pro obˇe moˇznosti zaˇc´ınaj´ıc´ıho hráˇce z pohledu Reviz´ı (jako prvn´ı provád´ı Revizi hráˇc M nebo naopak F). Podm´ınky v´ yhry v základn´ım tvaru obsahuj´ı urˇcité integrály z Revizn´ıch funkc´ı, a proto jsme naˇsli jednoduˇsˇs´ı zápis podm´ınek, kde se vyskytuj´ı pouze stˇredn´ı hodnoty pravdˇepodobnostn´ıch rozdˇelen´ı Reviz´ı. Pro ilustraci uveden´ ych podm´ınek v´ yhry jsme uvedli pˇr´ıklady, kde jeden demonstruje p˚ uvodn´ı podm´ınky v´ yhry a druh´ y ty upravené. V posledn´ı ˇradˇe jsme prozkoumali závislost podm´ınek v´ yhry na jednotliv´ ych parametrech hry (K, L) a uˇzitˇ c´ıch (a, b, c, d, w, x, y, z). Reˇsili jsme tyto závislosti za pˇredpokladu, ˇze se mˇen´ı vˇzdy pouze jeden parametr nebo uˇzitek a ostatn´ı z˚ ustávaj´ı stejné. Nakonec je uvedeno shrnut´ı tˇechto závislost´ı v tabulkách pro oba scénáˇre. V práci jsme tedy nast´ınili roli ˇcasován´ı v teorii her, kdy pˇreveden´ım sta35

Závˇer

tické hry, která má v´ıce rovnováh, na dynamickou hru dosáhneme jednoznaˇcnosti rovnováhy. Dále jsme naˇsli podm´ınky v´ yher jednotliv´ ych hráˇc˚ u v obou zkouman´ ych scénáˇr´ıch ve dvou typech dynamick´ ych her, klasické dynamické hˇre a dynamické hˇre s náhodn´ ym ˇcasován´ım tah˚ u. Tato práce by mohla b´ yt rozˇs´ıˇrena o dalˇs´ı typy dynamick´ ych her s náhodn´ ym ˇcasován´ım tah˚ u, napˇr´ıklad v´ıcekolové hry (probˇehne v´ıce kol reviz´ı) nebo hry s pˇrekrávaj´ıc´ım se pravdˇepodobnostn´ım rozdˇelen´ım reviz´ı.

36

Literatura [1] J. N. Webb, Game Theory: Decisions, Interaction and Evolution, Springer, 2007. [2] D. Fudenberg, J, Tirole, Game Theory, The MIT Press, 1991. [3] J. Libich, P. Stehl´ık, Monetary Policy Facing Fiscal Indiscipline under Generalized Timing of Actions, Journal of Institutional and Theoretical Economics, 168(3), 393-431, 2012. [4] I. Cho, A. Matsui, Time Consistency in Alternating Move Policy Games, The Japanese Economic Review, 56(3), 273-294, 2005. [5] R. Lagunoff, A. Matsui, Asynchronous Choice in Repeated Coordination Games, Econometrica, 65, 1467-1477, 1977. [6] Y. Kamada, M. Kandori, Revision Games, Harvard University, 2008. [7] O. Kallenberg, Foundations of Modern Probability Series: Probability and Its Applications, Springer, New York, 2002.

37

Západočeská univerzita v Plzni Fakulta aplikovaných věd Katedra matematiky. Časové struktury v teorii her

Recommend Documents