Úvod do teorie her. podzim 2010 v.1.0

´ Uvod do teorie her

podzim 2010 v.1.0

1

Obsah 1 Matematick´ a teorie her 1.1 Matematick´ y model . . . . 1.2 Maticov´e hry . . . . . . . . 1.3 Bi–maticov´e hry . . . . . . 1.4 Sm´ıˇsen´e optim´ aln´ı strategie 1.5 Simplexov´a metoda . . . . 1.6 Kooperativn´ı hry . . . . . 1.7 Opakovan´e hry . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

3 3 6 13 14 19 22 29

2 Aplikace teorie her 36 2.1 Dopravn´ı hry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2

1 1.1

Matematick´ a teorie her Matematick´ y model

C´ılem teorie her je popsat situaci, kter´a n´ as zaj´ım´ a, jako hru. Proto, abychom mohli pouˇz´ıvat matematick´ y apar´ at, mus´ıme jasnˇe definovat, co znamenaj´ı pojmy, kter´e budeme pˇri popisov´an´ı pouˇz´ıvat. Rozhodov´ an´ı - v´ ybˇer jedn´e z v´ıce variant Rozhodovac´ı situace - situace, ve kter´e je potˇreba vykonat rozhodov´an´ı V´ ysledek - v´ ybˇer variant vede k urˇcit´ ym v´ ysledk˚ um, kter´e mohou b´ yt z hlediska z´ajmu rozhoduj´ıc´ıho se subjektu horˇs´ı nebo lepˇs´ı. Racion´ aln´ı u ´ˇ castn´ık - rozhoduj´ıc´ı se subjekt vych´ az´ı z pozorov´an´ı moˇzn´ ych v´ ysledk˚ u a usiluje o v´ ybˇer (v jist´em smyslu) nejlepˇs´ı varianty Indiferentn´ı (neracion´ aln´ı) u ´ˇ castn´ık - subjekt, kter´emu je v´ ysledek rozhodov´an´ı lhostejn´ y (poˇcas´ı,...) Pˇredpokl´ ad´ ame, ˇze rozhodovac´ı situace m´ a alespoˇ n jednoho racion´ aln´ıho u ´ˇcastn´ıka a hled´ ame ’ odpovˇed , jak´e rozhodov´ an´ı racion´ aln´ıho u ´ˇcastn´ıka m˚ uˇzeme pokl´ adat v dan´e rozhodovac´ı situaci za optim´ aln´ı. Dˇ elen´ı rozhodovac´ıch situac´ı: 1. (a) Rozhodovac´ı situace se skal´ arn´ım ohodnocen´ım (rozhodnut´ı je moˇzn´e hodnotit jednou charakteristikou) (b) Rozhodovac´ı situace s vektorov´ ym ohodnocen´ım (rozhodnut´ı je moˇzn´e hodnotit v´ıce charakteristikami) 2. (a) Rozhodovac´ı situace s jedn´ım (nutnˇe racion´ aln´ım) u ´ˇcastn´ıkem (b) Rozhodovac´ı situace s v´ıce (alespoˇ n jedn´ım racion´ aln´ım) u ´ˇcastn´ıky 3. (a) Nekonfliktn´ı rozhodovac´ı strategie (s jedn´ım u ´ˇcastn´ıkem a skal´arn´ım ohodnocen´ım (matematick´e programov´an´ı)) (b) Konfliktn´ı rozhodovac´ı strategie (s vˇetˇs´ım poˇctem racion´ aln´ıch u ´ˇcastn´ık˚ u pˇr´ıpadnˇe alespoˇ n jedn´ım indiferentn´ım, nebo s vektorov´ ym ohodnocen´ım (jejich kombinace)) Teorie her ˇreˇs´ı konfliktn´ı rozhodovac´ı situace s vˇetˇs´ım poˇctem racion´ aln´ıch u ´ˇcastn´ık˚ u a se skal´ arn´ım ohodnocen´ım Jako dalˇs´ı mus´ıme zav´est formalismus, kter´ y n´ am umoˇzn´ı zformulov´an´ı matematick´eho modelu. Uvaˇzujeme tedy n´ asleduj´ıc´ı objekty: P = {1, 2, . . . , n} – mnoˇzina racion´ aln´ıch u ´ˇcastn´ık˚ u. Q = {1, 2, . . . , m} – mnoˇzina indiferentn´ıch u ´ˇcastn´ık˚ u. kp 1 aln´ıho u ´ˇcastn´ıka p. Pro p ∈ P, Xp = (Xp , . . . , Xp ) – mnoˇzina alternativ rozhodov´an´ı racion´ 3

l

ych stav˚ u vznikl´ ych v d˚ usledku p˚ usoben´ı indiPro q ∈ Q, Yq = (Yq1 , . . . , Yq q ) – mnoˇzina moˇzn´ ferentn´ ıho u ´ ˇ c astn´ ıka q. Q Q V = ni=1 Xi × m ysledek rozhodovac´ı situace. j=1 Yj – v´ Pro (x, y) ∈ V,  1  Mp (x, y)   .. Mp (x, y) =  , . Mpn (x, y)

kde Mpi : V → R – platba p–t´eho u ´ˇcastn´ıka i– t´emu u ´ˇcastn´ıkovi. Definice 1. Matematick´ ym modelem rozhodovac´ı situace v norm´ aln´ım tvaru naz´ yv´ ame n´ asleduj´ıc´ı z´ apis:   P = {1, . . . , n} X1 , . . . , Xn M1 , . . . , Mn Q = {1, . . . , m} Y1 , . . . , Ym Definice 2. Racion´aln´ı u ´ˇcastn´ık p ∈ P se chov´ a tak, ˇze pokud Mps (x1 , y1 ) ≥ Mps (x2 , y2 ), ∀s = 1, . . . , n a alespoˇ n pro jedno s plat´ı: Mps (x1 , y1 ) > Mps (x2 , y2 ), pak upˇrednostˇ nuje alternativu (x1 , y1 ) pˇred (x2 , y2 ). Teorie her zkoum´ a konfliktn´ı rozhodovac´ı situace Nˇekter´e zp˚ usoby (rozhodnˇe ne vˇsechny), jak je moˇzn´e teorii her dˇelit, jsou n´ asleduj´ıc´ı: 1. (a) Hry dvou hr´ aˇc˚ u. (b) Hry n hr´ aˇc˚ u. 2. (a) Koneˇcn´ a hra - koneˇcn´e mnoˇziny strategi´ı. (b) Nekoneˇcn´ a hra - mnoˇzina strategi´ı alespoˇ n jednoho hr´ aˇce je nekoneˇcn´ a. P 3. (a) Hra s konstantn´ım souˇctem plateb – ∀(x, y) ∈ V, p∈P Mp (x, y) = c. P (b) Hra s nulov´ ym souˇctem plateb – ∀(x, y) ∈ V, p∈P Mp (x, y) = 0. 4. (a) Nekooperativn´ı hry – hry bez moˇznosti uzav´ırat koalice. (b) Koaliˇcn´ı hry – hry s moˇznosti uzav´ırat koalice. N´asleduj´ıc´ı pˇr´ıklad ukazuje, jak ze slovn´ıho zad´ an´ı vytvoˇrit pˇr´ısluˇsn´ y matematick´ y model: Pˇ r´ıklad 1 (Hra plukovn´ıka Blotta). Boj o pozice B-Brno a O-Olomouc. Arm´ ada A1 o s´ıle tˇr´ı pluk˚ u pozice dob´ yv´ a, arm´ ada A2 o s´ıle dvou pluk˚ u pozice br´ an´ı. V´ ysledek stˇretnut´ı kromˇe s´ıly odd´ıl˚ u ovlivˇ nuje i poˇcas´ı. Arm´ ady A2 a A1 rozm´ıst´ı sv´e pluky do pozic B, O, aniˇz by znaly rozm´ıstˇen´ı protivn´ıka. Pozici obsazuje arm´ ada s vˇetˇs´ım poˇctem um´ıstˇen´ ych pluk˚ u. Pokud je pluk˚ u stejn´ y poˇcet, vyhr´ av´ a v pˇr´ıpadˇe pˇekn´eho poˇcas´ı u ´toˇcn´ık, v pˇr´ıpadˇe ˇspatn´eho obr´ ance. Zisk je poˇcet zniˇcen´ ych jednotek +1. 4

Matematick´ y model: M´ ame dva racion´ aln´ı u ´ˇcastn´ıky, a to arm´ ady A1 a A2 a jednoho indiferentn´ıho, a to poˇcas´ı. Mnoˇzina racion´ aln´ıch u ´ˇcastn´ık˚ u je tedy P = {1, 2} a mnoˇzina indiferentn´ıch u ´ˇcastn´ık˚ u (poˇcas´ı) je Q = {1}. Mnoˇzina alternativ rozhodov´ an´ı racion´ aln´ıho u ´ˇcastn´ıka 1 je pak X1 = (X11 = an´ı racion´ aln´ıho (0, 3), X12 = (1, 2), X13 = (2, 1), X14 = (3, 0)) a mnoˇzina alternativ rozhodov´ u ´ˇcastn´ıka 2 je X2 = (X21 = (0, 2), X22 = (1, 1), X23 = (2, 0)). Mnoˇzina moˇzn´ ych stav˚ u vznikl´ ych v d˚ usledku p˚ usoben´ı indiferentn´ıho u ´ˇcastn´ıka 1 je koneˇcnˇe Y1 = (Y11 = hezky, Y12 = ˇskaredˇe). V´ ysledky rozhodovac´ı situace tvoˇr´ı mnoˇzinu V = X1 × X2 × Y1 . Platba prvn´ıho u ´ˇcastn´ıka je funkce M1 definovan´ a v´ yˇctem M1 (X11 , X21 , Y11 ) = 3

M1 (X11 , X22 , Y11 ) = 2

M1 (X11 , X23 , Y11 ) = 1

M1 (X12 , X21 , Y11 ) = 4

M1 (X12 , X22 , Y11 ) = 4

M1 (X12 , X23 , Y11 ) = 1

M1 (X13 , X21 , Y11 ) = 0

M1 (X13 , X22 , Y11 ) = 4

M1 (X13 , X23 , Y11 ) = 4

M1 (X14 , X21 , Y11 ) = 1

M1 (X14 , X22 , Y11 ) = 2

M1 (X14 , X23 , Y11 ) = 4

M1 (X11 , X21 , Y12 ) = 4

M1 (X11 , X22 , Y12 ) = 2

M1 (X11 , X23 , Y12 ) = 1

M1 (X12 , X21 , Y12 ) = −1

M1 (X12 , X22 , Y12 ) = 1

M1 (X12 , X23 , Y12 ) = 0

M1 (X13 , X21 , Y12 ) = 0

M1 (X13 , X22 , Y12 ) = 1

M1 (X13 , X23 , Y12 ) = −1

M1 (X14 , X21 , Y12 ) = 1

M1 (X14 , X22 , Y12 ) = 2

M1 (X14 , X23 , Y12 ) = 3

a platba druh´eho u ´ˇcastn´ıka je funkce M2 M2 (X11 , X21 , Y11 ) = −1

M2 (X11 , X22 , Y11 ) = 0

M2 (X11 , X23 , Y11 ) = 1

M2 (X12 , X21 , Y11 ) = −2

M2 (X12 , X22 , Y11 ) = −2

M2 (X12 , X23 , Y11 ) = 1

M2 (X13 , X21 , Y11 ) = 2

M2 (X13 , X22 , Y11 ) = −2

M2 (X13 , X23 , Y11 ) = −2

M2 (X14 , X21 , Y11 ) = 1

M2 (X14 , X22 , Y11 ) = 0

M2 (X14 , X23 , Y11 ) = −2

M2 (X11 , X21 , Y12 ) = −2

M2 (X11 , X22 , Y12 ) = 0

M2 (X11 , X23 , Y12 ) = 1

M2 (X12 , X21 , Y12 ) = 3

M2 (X12 , X22 , Y12 ) = 1

M2 (X12 , X23 , Y12 ) = 2

M2 (X13 , X21 , Y12 ) = 2

M2 (X13 , X22 , Y12 ) = 1

M2 (X13 , X23 , Y12 ) = 3

M2 (X14 , X21 , Y12 ) = 1

M2 (X14 , X22 , Y12 ) = 0

M2 (X14 , X23 , Y12 ) = −1

Matematick´ y model je pak   P = {1, 2} X1 , X2 M1 , M2 Q = {1} Y1 Pˇ r´ıklad 2 (Oper´ atoˇri). Dva oper´ atoˇri T–Mobile a O2 chtˇej´ı postavit vys´ılaˇc do jednoho ze ˇctyˇr mˇest A, B, C, D, kter´e jsou od sebe vzd´ aleny n´ asleduj´ıc´ım zp˚ usobem: B C D

A 0 —— 20 ——————— 60 ——————— 100

Kaˇzd´e dominantn´ı pokryt´ı odpov´ıd´ a proporcion´ alnˇe d´elce u ´seku. Pokud napˇr´ıklad T–Mobile postav´ı vys´ılaˇc v bodˇe B a O2 v bodˇe C, bude T–Mobile dominantn´ı na u ´seku AB a na p˚ ulce 5

u ´seku BC (to dˇel´ a 40% cel´eho u ´zem´ı), kdeˇzto O2 bude dominantn´ı na u ´seku CD a na p˚ ulce u ´seku BC (to dˇel´ a ale 60% u ´zem´ı). Vys´ılaˇc mus´ı b´ yt um´ıstˇen v jednom z bod˚ u A, B, C, D. Matematick´ y model: P = {1, 2} Q=∅ X1 = (X11 = A, X12 = B, X13 = C, X14 = D) X2 = (X21 = A, X22 = B, X23 = C, X24 = D) V = X1 × X2

1.2

M1 (X11 , X21 ) = 50 M1 (X11 , X21 ) = 90 M1 (X11 , X21 ) = 70 M1 (X11 , X21 ) = 50

M1 (X21 , X22 ) = 10 M1 (X21 , X22 ) = 50 M1 (X21 , X22 ) = 60 M1 (X21 , X22 ) = 40

M1 (X31 , X23 , ) = 30 M1 (X31 , X23 , ) = 40 M1 (X31 , X23 , ) = 50 M1 (X31 , X23 , ) = 20

M1 (X41 , X22 ) = 50 M1 (X41 , X22 ) = 60 M1 (X41 , X22 ) = 80 M1 (X41 , X22 ) = 50

M2 (X11 , X21 ) = 50 M2 (X11 , X21 ) = 10 M2 (X11 , X21 ) = 30 M2 (X11 , X21 ) = 50

M2 (X21 , X22 ) = 90 M2 (X21 , X22 ) = 50 M2 (X21 , X22 ) = 40 M2 (X21 , X22 ) = 60

M2 (X31 , X23 , ) = 70 M2 (X31 , X23 , ) = 60 M2 (X31 , X23 , ) = 50 M2 (X31 , X23 , ) = 80

M2 (X41 , X22 ) = 50 M2 (X41 , X22 ) = 40 M2 (X41 , X22 ) = 20 M2 (X41 , X22 ) = 50

Maticov´ e hry

Vˇsimnˇeme si, ˇze u pˇr´ıkladu telefonn´ıch oper´ ator˚ u m´ ame dva hr´ aˇce a zisk jednoho znamen´a automaticky ztr´ atu druh´eho. Takov´e hˇre se ˇr´ık´a antagonistick´a hra dvou hr´ aˇc˚ u a nen´ı tˇeˇzk´e si pˇredstavit, ˇze je moˇzn´e takovou hru reprezentovat matic´ı. Hr´am, kter´e lze reprezentovat matic´ı, se ˇr´ık´a maticov´e hry. Form´ alnˇe je maticov´a hra koneˇcn´ a hra dvou hr´ aˇc˚ u s konstantn´ım (nulov´ ym souˇctem). To, ˇze je hru dvou hr´ aˇc˚ u s konstantn´ım souˇctem moˇzn´e reprezentovat jen matic´ı plateb prvn´ıho hr´ aˇce M1 , plyne pˇr´ımo z n´ asledju´ıc´ıho faktu. Pokud je hra s konstantn´ım souˇctem, plat´ı M1 (x, y) + M2 (x, y) = c a je tedy moˇzn´e vyj´adˇrit matici plateb druh´eho hr´ aˇce pomoc´ı matice plateb prvn´ıho: M2 (x, y) = c − M1 (x, y). Definice 3. Hrou dvou hr´ aˇc˚ u v norm´aln´ı formˇ  e s konstantn´ım souˇctem (maticovou hru) naz´ yv´ ame hru P = {1, 2} X, Y M (x, y) c . Z definice je jasn´e, ˇze ned´ av´a smysl uvaˇzovat moˇznou spolupr´aci hr´ aˇc˚ u (ˇc´ım v´ıc jeden z´ısk´a t´ım v´ıc druh´ y ztrat´ı). Takov´e hry se naz´ yvaj´ı antagonistick´ e (nekooperativn´ı). Definice 4. Matic´ı plateb rozum´ıme matici  M (x1 , y1 ) · · ·  .. .. M = . . M (xm , y1 ) · · · 6

 M (x1 , yn )  .. . .

M (xm , yn )

Pˇ r´ıklad 3 (Hra s prsty). Kaˇzd´ y ze dvou hr´ aˇc˚ u uk´ aˇze jeden nebo dva prsty. Pokud je celkov´ y poˇcet uk´ azan´ ych prst˚ u sud´e ˇc´ıslo, pak zaplat´ı druh´ y hr´ aˇc prvn´ımu sumu rovnaj´ıc´ı se tomuto ˇc´ıslu. V opaˇcn´em pˇr´ıpadˇe inkasuje od prvn´ıho hr´ aˇce pˇr´ısluˇsnou sumu druh´ y hr´ aˇc. Strategie prvn´ıho hr´ aˇce jsou i=1

uk´ azat jeden prst

i=2

uk´ azat dva prsty

Strategie druh´eho hr´ aˇce jsou j=1

uk´ azat jeden prst

j=2

uk´ azat dva prsty

Jde tedy o maticovou hru s matic´ı plateb 

 2 −3 −3 4

a konstantou c = 0 Pˇ r´ıklad 4 (Hra plukovn´ıka Blotta (Pˇr. 1)). Pokud v Pˇr´ıkladˇe 1 vynech´ ame indiferentn´ıho u ´ˇcastn´ıka tak, ˇze pˇredpokl´ ad´ ame, ˇze bude ˇskaredˇe, dostaneme maticovou hru, kde: Strategie prvn´ıho hr´ aˇce jsou i=1

(3,0)

i=2

(2,1)

i=3

(1,2)

i=4

(0,3)

Strategie druh´eho hr´ aˇce jsou j=1

(2,0)

j=2

(1,1)

j=3

(0,2)

Jde tedy o maticovou hru s matic´ı plateb 

3 −1  0 1

 2 1 1 0  1 −1 2 3

a konstantou c = 2. 7

Pˇ r´ıklad 5 (Oper´ atoˇri (Pˇr. 2)). V pˇr´ıkladˇe s oper´ atory jde jednoznaˇcnˇe o maticovou hru s matic´ı plateb:   50 10 30 50 90 50 40 60   70 60 50 80 50 40 20 50 a konstantou v = 100. Maticov´a hra se tedy hraje tak, ˇze prvn´ı hr´ aˇc vyb´ır´ a ˇra´dek a druh´ y hr´ aˇc sloupec. Pˇr´ısluˇsn´e ˇc´ıslo v matici je pak platba prvn´ıho hr´ aˇce. Definice 5. Strategie i = 1, . . . , m a j = 1, . . . n naz´ yv´ ame ˇcist´e strategie prvn´ıho a druh´eho hr´ aˇce. Pokud prvn´ı hr´ aˇc vol´ı i–tou ˇcistou strategii, potom m˚ uˇze s urˇcitost´ı zabezpeˇcit, ˇze jeho platba bude alespoˇ n min aij . j

Vzhledem k tomu, ˇze chce ale zabezpeˇcit co moˇzn´ a nejvyˇsˇs´ı platbu uvaˇzuje pˇrinejmenˇs´ım o platbˇe max min aij . i

j

Druh´ y hr´ aˇc chce minimalizovat platbu prvn´ıho hr´ aˇce, ta vˇsak nebude vyˇsˇs´ı neˇz max aij i

a druh´ y hr´ aˇc tedy vol´ı strategii min max aij . j

i

Z toho tedy vypl´ yv´ a, ˇze volbou ˇcist´e strategie m˚ uˇze prvn´ı hr´ aˇc zabezpeˇcit, ˇze jeho platba nebude niˇzˇs´ı neˇz maxi minj aij , pˇriˇcemˇz druh´ y hr´ aˇc m˚ uˇze vhodnou volbou strategie zajistit, aby jeho platba nebyla vyˇsˇs´ı neˇz minj maxi aij Pokud by tyto u ´vahy obou hr´ aˇc˚ u nebyly ve sporu znamenalo by to, ˇze svou volbou zaruˇc´ı, ˇze pˇr´ıpadn´a zmˇena protihr´aˇcovy strategie, by pro nˇej nebyla v´ yhodn´ a. M˚ uˇzeme ˇr´ıct, ˇze kdo pak uhne, tak si nepolepˇs´ı. Toto d´ av´a smysl n´ asleduj´ıc´ım definic´ım: Definice 6. Sedlov´ ym bodem matice A = (aij ) naz´ yv´ ame takov´ y jej´ı prvek aij pro kter´ y plat´ı maxi minj aij = minj maxi aij . Definice 7. Takov´e strategie i0 , j0 , ˇze (i0 , j0 ) je sedlov´ y bod matice plateb A, naz´ yv´ ame ˇcist´ ymi ˇ ıslo v = ai j naz´ optim´ aln´ımi strategiemi prvn´ıho a druh´eho hr´ aˇce v maticov´e hˇre. C´ y v´ a me 0 0 hodnotou t´eto hry. Trojici (i0 , j0 , v) naz´ yv´ ame ˇreˇsen´ım maticov´e hry v ˇcist´ ych strategi´ıch. V n´ asleduj´ıc´ım dok´aˇzeme, ˇze tyto u ´vahy jsou obecnˇe platn´e. 8

Vˇ eta 1. Necht’ f (x, y) je re´ aln´ a funkce definovan´ a pro x ∈ X a y ∈ Y a pˇredpokl´ adejme ˇze existuj´ı veliˇciny max min f (x, y), min max f (x, y). x∈X y∈Y

y∈Y x∈X

Potom max min f (x, y) ≤ min max f (x, y). x∈X y∈Y

y∈Y x∈X

D˚ ukaz. Z definice minima a maxima v´ıme, ˇze pro libovoln´e zadan´e x ∈ X plat´ı min f (x, y) ≤ f (x, y) y∈Y

a pro libovoln´e zadan´e y ∈ Y plat´ı f (x, y) ≤ max f (x, y). x∈X

Proto pro vˇsechna x ∈ X a y ∈ Y plat´ı min f (x, y) ≤ max f (x, y). y∈Y

x∈X

Vzhledem k tomu, ˇze prav´a strana nerovnice nez´ avis´ı na x ∈ X tedy max min f (x, y) ≤ max f (x, y). x∈X y∈Y

x∈X

A vzhledem k tomu, ˇze lev´a strana nerovnice nez´ avis´ı na y ∈ Y , dostaneme celkem max min f (x, y) ≤ min max f (x, y). x∈X y∈Y

y∈Y x∈X

Definice 8. Necht’ f (x, y) je re´ aln´ a funkce definovan´ a pro x ∈ X a y ∈ Y . Sedlov´ ym bodem t´eto funkce vzhledem k mnoˇzinˇe X × Y naz´ yv´ ame takov´ y bod (x0 , y0 ) ∈ X × Y , ˇze pro vˇsechny x ∈ X a y ∈ Y plat´ı f (x, y0 ) ≤ f (x0 , y0 ) ≤ f (x0 , y). Vˇ eta 2 (Vˇ eta o sedlov´ em bodu). Necht’ f (x, y) je re´ aln´ a funkce definovan´ a pro x ∈ X a y ∈ Y a necht’ existuj´ı veliˇciny maxx∈X miny∈Y f (x, y) a miny∈Y maxx∈X f (x, y). Pak funkce f (x, y) m´ a sedlov´ y bod na mnoˇzinˇe X × Y pr´ avˇe tehdy, kdyˇz plat´ı max min f (x, y) = min max f (x, y). x∈X y∈Y

y∈Y x∈X

Nav´ıc pokud (x0 , y0 ) je sedlov´ y bod funkce f (x, y) na mnoˇzinˇe X × Y , pak max min f (x, y) = min max f (x, y) = f (x0 , y0 ). x∈X y∈Y

y∈Y x∈X

9

D˚ ukaz. 1. Necht’ (x0 , y0 ) ∈ X × Y je sedlov´ y bod funkce f (x, y). Pak podle Definice 8. pro vˇsechna x ∈ X a y ∈ Y plat´ı f (x, y0 ) ≤ f (x0 , y0 ) ≤ f (x0 , y). Z toho vypl´ yv´ a, ˇze maxx∈X f (x, y0 ) ≤ f (x0 , y0 ) ≤ miny∈Y f (x0 , y). Vzhledem k tomu, ˇze min max f (x, y) ≤ max f (x, y0 ) y∈Y x∈X

x∈X

a min f (x0 , y) ≤ max min f (x, y), y∈Y

x∈X y∈Y

plat´ı min max f (x, y) ≤ max min f (x, y) y∈Y x∈X

x∈X y∈Y

Avˇsak podle pˇredeˇsl´e vˇety plat´ı max min f (x, y) ≤ min max f (x, y). x∈X y∈Y

y∈Y x∈X

A tedy celkem max min f (x, y) = min max f (x, y). x∈X y∈Y

y∈Y x∈X

a z d˚ ukazu je zˇrejm´e, ˇze se v´ yraz tak´e mus´ı rovnat f (x0 , y0 ). 2. Necht’ je splnˇena rovnost ve znˇen´ı vˇety. Pˇredpokl´adejme, ˇze funkce miny∈Y f (x, y) nab´ yv´ a sv´eho maxima v bodˇe x0 ∈ X a funkce maxx∈X f (x, y) sv´eho minima v bodˇe y0 ∈ Y , tj. plat´ı min f (x0 , y) = max min f (x, y) y∈Y

x∈X y∈Y

max f (x, y0 ) = min max f (x, y). x∈X

y∈Y x∈X

Uk´ aˇzeme, ˇze dvojice (x0 , y0 ) ∈ X×Y je sedlov´ ym bodem funkce f (x, y). Na z´akladˇe pˇredpokladu o splnˇen´ı rovnosti m´ ame min f (x0 , y) = max f (x, y0 ). y∈Y

x∈X

Z definice minima vypl´ yv´ a min f (x0 , y) ≤ f (x0 , y0 ), y∈Y

a tedy max f (x, y0 ) ≤ f (x0 , y0 ). x∈X

Celkem f (x, y0 ) ≤ f (x0 , y0 ), pro vˇsechna x ∈ X. Analogicky f (x0 , y) ≥ f (x0 , y0 ), pro vˇsechna y ∈ Y, a tedy (x0 , y0 ) ∈ X × Y je z definice sedlov´ ym bodem. Vˇsimnˇeme si jeˇstˇe jedn´e d˚ uleˇzit´e vlastnosti maticov´ ych her. Pokud je nˇekter´ y ˇra´dek matice ve vˇsech sloupc´ıch vˇetˇs´ı neˇz jin´ y, nem´ a pro prvn´ıho hr´ aˇce smysl pˇr´ısluˇsnou strategii hr´ at. 10

ˇ Definice 9. Rekneme, ˇze vektor a = (a1 , · · · , an )T dominuje (ostˇre) vektoru b = (b1 , · · · , bn )T , pokud pro vˇsechna j = 1, · · · , n plat´ı aj ≥ bj (aj > bj ). Vˇ eta 3. Optim´ aln´ı strategie hr´ aˇc˚ u v maticov´e hˇre se nezmˇen´ı, pokud k matici plateb pˇripoˇcteme libovolnou konstantu ξ nebo pokud matici plateb vyn´ asob´ıme libovolnou kladnou konstantou β. Pˇ r´ıklad 6 (Prsty (Pˇr. 3.)). V tomto pˇr´ıkladˇe jde o maticovou hru s matic´ı plateb 

 2 −3 −3 4

M´ ame tedy min a1j = −3

min a2j = −3

j

j

max min aij = −3 i

max ai1 = 2

j

i

max ai2 = 4

min max aij = 2.

i

j

i

Plat´ı tedy maxi minj aij < minj maxi aij a ˇcist´ a optim´ aln´ı strategie neexistuje. Pˇ r´ıklad 7. Mˇejme maticovou hru urˇcenou matic´ı 

 3 2 . 4 −1

M´ ame tedy min a1j = 2 j

min a2j = −1

max min aij = 2

j

i

max ai1 = 4

j

max ai2 = 2

i

i

min max aij = 2 j

i

a tedy maxi minj aij = minj maxi aij a ˇcist´ a optim´ aln´ı strategie je (1, 2). Pˇ r´ıklad 8. Pokud v Pˇr´ıkladˇe 1 vynech´ ame indiferentn´ıho u ´ˇcastn´ıka, tj. poˇcas´ı dostaneme maticovou hru s matic´ı plateb   3 2 1 −1 1 0     0 1 −1 . 1 2 3 11

M´ ame tedy min a1j = 1 j

min a2j = −1

min a3j = 0

j

j

min a4j = 1

max min aij = 1

max ai1 = 3

max ai2 = 2

max ai3 = 3

min max aij = 2

j

i

i

j

i

i

j

i

a opˇet maxi minj aij < minj maxi aij a ˇcist´ a optim´ aln´ı strategie neexistuje. Pˇ r´ıklad 9 (Oper´ atoˇri (Pˇr. 2)). V pˇr´ıkladˇe s oper´ atory se jedn´ a o maticovou hru s matic´ı plateb:   50 10 30 50 90 50 40 60   70 60 50 80 . 50 40 20 50 M´ ame tedy: min a1j = 10 j

min a2j = 40

min a3j = 50

min a4j = 20

max min aij = 50

max ai1 = 90

max ai2 = 60

max ai3 = 50

max ai4 = 80

j

j

j

i

i

j

i

i

i

min max aij = 50 j

i

a tentokr´ at maxi minj aij = minj maxi aij , existuje tedy ˇcist´ a optim´ aln´ı strategie a jde o strategii, kdy si oba oper´ atoˇri postav´ı vys´ılaˇc na stejn´em m´ıstˇe, a to na m´ıstˇe C. Pˇ r´ıklad 10 (Vˇ ezˇ novo dilema). 

 zradit nezradit  zradit (−6, −6) (0, −9)  nezradit (−9, 0) (−1, −1)

Pˇ r´ıklad 11 (K´ amen, n˚ uˇ zky, pap´ır).   k´ amen n˚ uˇzky pap´ır k´   amen (0, 0) (1, −1) (−1, 1)  n˚ uˇzky (−1, 1) (0, 0) (1, −1) pap´ır (1, −1) (−1, 1) (0, 0) 12

Pˇ r´ıklad 12 (Hra pohlav´ı). 

 divadlo f otbal divadlo (3, 1) (1, 1)  f otbal (0, 0) (2, 3) Pˇ r´ıklad 13 (Semafory). Pˇri programov´ an´ı chov´ an´ı semafor˚ u na kˇriˇzovatk´ ach se zvaˇzuje nakolik se m´ a semafor pˇrizp˚ usobovat aktu´ aln´ımu provozu (napˇr´ıklad z ohledem na statistiku pr˚ ujezdnosti ve vˇsech smˇerech upravit pˇrep´ın´ an´ı mezi ˇcervenou a zelenou). Prvn´ı hr´ aˇc je poˇc´ıtaˇc ˇr´ıd´ıc´ı kˇriˇzovatku, druh´ y hr´ aˇc je u ´ˇcastn´ık dopravn´ıho provozu. Pro poˇc´ıtaˇc m´ ame dva stavy “pˇrizp˚ usobuje / nepˇrizp˚ usobuje“ a pro druh´eho hr´ aˇce m´ ame dva stavy “respektuje / nerespektuje (projede klidnˇe i na ˇcervenou)”. Pokud se poˇc´ıtaˇc pˇrizp˚ usobuje a u ´ˇcastn´ıci semafor respektuj´ı, vznikne mal´ a ˇcasov´ a prodleva ”d”bˇehem kter´e se ˇcek´ a na zelenou. Pokud hr´ aˇc semafor nerespektuje a semafor se tomu pˇrizp˚ usobuje zpoˇzdˇen´ı bude nula. Pokud hr´ aˇc semafor respektuje, ale semafor se nepˇrizp˚ usobuje mus´ı si nav´ıc poˇckat dalˇs´ı ˇcas ”D”. Pokud hr´ aˇc semafor nerespektuje, ale semafor se nepˇrizp˚ usobuje prodleva vˇsech je ”D”. Jedn´ a se o maticovou hru z matic´ı plateb:   d d+D . 0 D Vid´ıme, ˇze pro poˇc´ıtaˇc dokonce dominuje druh´ y sloupec tedy “nepˇrizp˚ usobuje“. Nejlepˇs´ı strategie pro semafor je nepˇrizp˚ usobovat se, takˇze je ˇcasto ˇcerven´ a i na pr´ azdn´e kˇriˇzovatce. Pˇrid´ ame z´ asadu, ˇze na kˇriˇzovatce bude dopravn´ı policie s pravdˇepodobnost´ı p zastavovat ˇridiˇce kteˇr´ı poruˇs´ı pˇredpisy a zdrˇzovat je o dalˇs´ı ˇcas f . Zavedeme pak funkci plateb c.   c(d, p, 0) c(d + D, p, 0) . c(0, p, f ) c(D, p, f ) Pokud bude funkce line´ arn´ı, tj. c(x, p, f ) = x + pf pak m´ ame matici plateb   d d+D . 0 + pf D + pf Zvol´ıme–li pf > d, tj. vhodnˇe zvol´ıme pravdˇepodobnost kontrol a m´ıru prostoj˚ u je optim´ aln´ı strategi´ı semaforu pˇrizp˚ usobit se.

1.3

Bi–maticov´ e hry

Pro koneˇcnou hru dvou hr´ aˇc˚ u, kter´a nem´ a konstantn´ı souˇcet, a tedy nemus´ı b´ yt ani antagonistick´a, se vˇzilo oznaˇcen´ı bimaticov´ a hra. Jedin´ y rozd´ıl od maticov´e hry tedy je, ˇze kaˇzd´ y hr´ aˇc m´ a svou vlastn´ı matici plateb. Definice 10. Necht’ X, Y jsou nepr´ azdn´e mnoˇziny. Bi–maticovou hrou dvou hr´ aˇc˚ u rozum´ıme hru v norm´ aln´ım tvaru: {Q = {1, 2}, X, Y, M1 (x, y), M2 (x, y)} s nekonstantn´ım souˇctem M1 (x, y) + M2 (x, y) = µ(x, y). 13

Mus´ıme proto modifikovat definici rovnov´aˇzn´eho bodu pro dva hr´ aˇce. Definice 11. Dvojice strategi´ı (x, y) se naz´ yv´ a rovnov´ aˇzn´ y bod, pr´ avˇe tehdy kdyˇz plat´ı: u1 (s, y) ≤ u1 (x, y), pro kaˇzd´e s ∈ S u2 (x, t) ≤ u1 (x, y), pro kaˇzd´e t ∈ T Pˇ r´ıklad 14. Hru urˇcen´ a dvojmatic´ı Strategie X1 X2 X3 Y1 (3,3) (2,2) (3,10) Y2 (-3,-2) (1,15) (1,8) Y3 (10,2) (0,0) (1,2) m´ a rovnov´ aˇzn´ y bod (X2 , Y1 )

X4 (6,9) (10,2) (1,2)

X5 (10,11) (-1,2) (0,2)

Pˇ r´ıklad 15. Hru urˇcen´ a dvojmatic´ı Strategie X1 X2 X3 X4 Y1 (3,3) (2,2) (3,10) (6,9) Y2 (3,-2) (7,15) (6,8) (10,2) Y3 (10,2) (0,0) (1,2) (1,2) nem´ a rovnov´ aˇzn´ y bod.

X5 (10,11) (3,2) (0,2)

Vˇsimnˇeme si, ˇze bi–maticov´a hra 

(4, 1) (−9, 8) (3, 4) (−4, 5)



m´ a dvˇe rovnov´aˇzn´e strategie (4, 1) a (−4, 5). Pokud prvn´ı hr´ aˇc vol´ı x = 1, tedy svou rovnov´aˇznou strategii a druh´ y hr´ aˇc vol´ı y = 2 tak´e svou rovnov´aˇznou strategii, je pak v´ ysledek nejhorˇs´ı moˇzn´ y. Existuje moˇznost v´ yhodnˇejˇs´ı volby strategie x = 2, y = 1, ale je potˇreba dohody o strategii. Definice 12. Necht’ (¯ x, y¯) je dvojice rovnov´ aˇzn´ ych strategi´ı s vlastnost´ı, ˇze M1 (x, y¯) ≥ M1 (¯ x, y¯) M2 (¯ x, y) ≥ M2 (¯ x, y¯), kde (x, y) je libovoln´ a jin´ a dvojice rovnov´ aˇzn´ ych strategi´ı hry. Potom dvojici (x, y) nazveme dominuj´ıc´ı dvojic´ı rovnov´ aˇzn´ ych strategi´ı hry.

1.4

Sm´ıˇ sen´ e optim´ aln´ı strategie

Pokud nem´ a maticov´a hra optim´ aln´ı strategii, plat´ı max min aij < min max aij . i

j

j

i

V tomto pˇr´ıpadˇe se pˇri opakov´an´ı hry, tj. pˇri jednotliv´ ych parti´ıch, bude prvn´ı i druh´ y hr´ aˇc snaˇzit opakovat ˇcist´e strategie s takovou pravdˇepodobnost´ı, aby v pr˚ umˇeru, prvn´ı hr´ aˇc z´ıskal v´ıce neˇz jen maxi minj aij a druh´ y hr´ aˇc se snaˇz´ı zajistit aby, prvn´ı z´ıskal m´enˇe neˇz minj maxi aij . Tady kaˇzd´ y hr´ aˇc pˇriˇrazuje kaˇzd´e sv´e ˇcist´e strategii urˇcitou pravdˇepodobnost, s jakou j´ı bude pouˇz´ıvat. 14

Definice 13. Sm´ıˇsenou strategi´ı prvn´ıho hr´ aˇce naz´ yv´ ame m–rozmˇern´ y vektor x (x1 , . . . , xm )T , pro kter´ y plat´ı m X xi = 1, xi ≥ 0.

=

i=1

Sm´ıˇsenou strategi´ı druh´eho hr´ aˇce naz´ yv´ ame n–rozmˇern´ y vektor y = (y1 , . . . , yn )T , pro kter´ y plat´ı n X yi = 1, yi ≥ 0 i=1

Mnoˇziny Sm = {x ∈ Em ,

m X

xi = 1, xi ≥ 0}

n X

yi = 1, yi ≥ 0}

i=1

Sn = {y ∈ En ,

i=1

naz´ yv´ ame mnoˇzinou sm´ıˇsen´ ych strategi´ı prvn´ıho a druh´eho hr´ aˇce. Kaˇzd´ a ˇcist´ a strategie odpov´ıd´ a sm´ıˇsen´e x = (0, . . . , 0, 1, 0, . . . , 0)T . Definice 14. Funkci E(x, y) =

n m X X

aij xi yj = xT Ay

i=1 j=1

definovanou pro x ∈ Sm a y ∈ Sn naz´ yv´ ame funkc´ı stˇredn´ı hodnoty platby v maticov´e hˇre. Stejn´ ymi u ´vahami odvod´ıme, ˇze prvn´ı hr´ aˇc volbou sm´ıˇsen´e strategie m˚ uˇze doc´ılit toho, ˇze stˇredn´ı hodnota jeho platby bude niˇzˇs´ı neˇz max min E(x, y),

x∈Sn y∈Sm

pˇriˇcemˇz druh´ y hr´ aˇc m˚ uˇze zajistit, aby stˇredn´ı hodnota plateb prvn´ıho byla niˇzˇs´ı neˇz min max E(x, y).

y∈Sm x∈Sn

V´ıme, ˇze pro kaˇzdou funkci plat´ı max min E(x, y) ≤ min max E(x, y) y∈Sm x∈Sn

x∈Sn y∈Sm

a pokud plat´ı rovnost max min E(x, y) = min max E(x, y), y∈Sm x∈Sn

x∈Sn y∈Sm

existuje sedlov´ y bod. 15

Definice 15. Necht’ (¯ x, y¯) je sedlov´ y bod funkce E(¯ x, y¯) vzhledem k Sm ×Sn . Vektory x ¯ respektive y¯ naz´ yv´ ame optim´ aln´ımi sm´ıˇsen´ ymi strategiemi prvn´ıho respektive druh´eho hr´ aˇce v pˇr´ısluˇsn´e maticov´e hˇre a ˇc´ıslo v = E(¯ x, y¯) naz´ yv´ ame hodnotou t´eto hry. Trojici (¯ x, y¯, v) naz´ yv´ ame ˇreˇsen´ım maticov´e hry ve sm´ıˇsen´ ych strategi´ıch. Pˇ r´ıklad 16. Mˇejme maticovou hru s matic´ı plateb   2 −3 , −3 4 pˇriˇcemˇz uˇz v´ıme, ˇze ˇcist´ a optim´ aln´ı strategie neexistuje (ovˇeˇrte). Hra m´ a ˇreˇsen´ı ve sm´ıˇsen´ ych 7 5 T 7 5 T ’ strategi´ıch x ¯ = ( 12 , 12 ) a y¯ = ( 12 , 12 ) . Toto ˇreˇsen´ı ted jen ovˇeˇr´ıme:   7  1 7 5 2 −3 12 =− E(¯ x, y¯) = ( , ) 5 12 12 −3 4 12 12 

2 −3 E(x, y¯) = (x1 , x2 ) −3 4 −

 7  12 5 12

1 − 12 = (x1 , x2 ) 1 − 12





=

1 1 1 1 x1 − x2 = − (x1 + x2 ) = − 12 12 12 12

   1 7 5 2 −3 y1 =− E(¯ x, y) = ( , ) y2 12 12 −3 4 12 Vˇ eta 4 (J. von Neuman, J. Nash). Pro kaˇzdou maticovou hru plat´ı max min E(x, y) = min max E(x, y) y∈Sm x∈Sn

x∈Sn y∈Sm

a tedy existuje sedlov´ y bod funkce E(x, y) na mnoˇzinˇe Sm × Sn . Tedy kaˇzd´ a hra m´ a ˇreˇsen´ı ve sm´ıˇsen´ ych strategi´ıch. D˚ ukaz. D˚ ukaz, kter´ y zde struˇcnˇe nastiˇ nujeme, je zaloˇzen´ y na technik´ach line´ arn´ıho programov´an´ı. Line´arn´ı programov´an´ı ˇreˇs´ı u ´lohy, pˇri kter´ ych maximalizujeme nebo minimalizujeme line´ arn´ı funkci vzhledem k nˇejak´e mnoˇzinˇe rovnic a nerovnic. Zformulujeme si dvˇe takov´e u ´lohy: Maximalizovat ω za podm´ınek: m X aij xi + ω ≤ 0, ∀j − i=1

m X

xi = 1

i=1

xi ≥ 0

16

Minimalizovat u za podm´ınek: n X aij yj + u ≥ 0, ∀i − j=1

n X

yi = 1

i=1

yj ≥ 0

pro i = 1, · · · , m, j = 1, · · · , n. Tyto dvˇe u ´lohy jsou du´ aln´ı a to z hlediska line´ arn´ıho programov´an´ı znamen´a, ˇze maj´ı stejnou mnoˇzinu pˇr´ıpustn´ ych ˇreˇsen´ı (tj. ˇreˇsen´ı, kter´a splˇ nuj´ı dan´e nerovnosti) a souˇcasnˇe, pokud existuje optim´ aln´ı ˇreˇsen´ı jedn´e, existuje i optim´ aln´ı ˇreˇsen´ı druh´e a v´ ysledn´ a hodnota u ´ˇcelov´e funkce je stejn´a. Pokud zvol´ıme za pˇr´ısluˇsn´ a aij prvky matice hry A, dostaneme optim´ aln´ı ˇreˇsen´ı, kter´e bude rovno sedlov´emu bodu funkce E(x, y), a tedy optim´ aln´ı strategi´ı pˇr´ısluˇsn´e maticov´e hry. Poznamenejme nakonec, ˇze toto ˇreˇsen´ı nen´ı dan´e jednoznaˇcnˇe. Bez d˚ ukazu uv´ad´ıme n´ asleduj´ıc´ı dvˇe vˇety: Vˇ eta 5. 1. Pokud ve hˇre s matic´ı plateb A = (aij ) typu m × n plat´ı, ˇze pro nˇejak´e k (1 ≤ k ≤ m) existuj´ı ˇc´ısla αi (i 6= k) takov´ a, ˇze pro vˇsechna j = 1, . . . , n m´ ame X X αi aij ≥ akj , αi = 1, i6=k

i6=k

potom existuje optim´ aln´ı strategie prvn´ıho hr´ aˇce x ¯ ∈ Sm kter´e sloˇzka je x ¯0 = 0. 2. Pokud ve hˇre s matic´ı plateb A = (aij ) typu m × n plat´ı, ˇze pro nˇejak´e t (1 ≤ t ≤ n) existuj´ı ˇc´ısla βj (j 6= t) takov´ a, ˇze pro vˇsechna i = 1, . . . , m m´ ame X X βi aij ≤ ait , βj = 1, j6=t

j6=t

potom existuje optim´ aln´ı strategie druh´eho hr´ aˇce x ¯ ∈ Sn kter´e sloˇzka je y¯0 = 0. Pˇ r´ıklad 17. V maticov´e hˇre s matic´ı plateb   2 4 6 6 8 2 3 5 3 existuje k = 3, α1 = α2 = 12 takov´e, ˇze pro vˇsechna j = 1, 2, 3 plat´ı α1 a1j +α2 a2j ≥ a3j . Existuje tedy optim´ aln´ı strategie pro kterou je x3 = 0. 17

Z d˚ ukazu Nashovy vˇety v´ıme, ˇze optim´ aln´ı sm´ıˇsen´ a strategie maticov´e hry s matic´ı A je optim´ aln´ım ˇreˇsen´ım dvojice u ´loh line´ arn´ıho programov´an´ı. Potˇrebujeme ale tyto u ´lohy pˇrev´est na tvar, kter´ y um´ıme ˇreˇsit. Jako v´ ychoz´ı u ´lohu pouˇzijeme

Minimalizovat u za podm´ınek: n X aij yj + u ≥ 0, − j=1

n X

yi = 1

i=1

yj ≥ 0

pro i = 1, · · · , m, j = 1, · · · , n. Z pˇredeˇsl´ ych vˇet v´ıme, ˇze matici plateb m˚ uˇzeme pˇriˇcten´ım vhodn´e konstanty upravit tak aby aij ≥ 0, tedy i hodnota u ´ˇcelov´e funkce u je kladn´a a m˚ uˇzeme nerovnosti dˇelit beze zmˇeny smˇeru nerovnosti.

Minimalizovat u za podm´ınek: n X yj aij + 1 ≥ 0, − u j=1

n X yi i=1

zavedeme substituci pi =

yi u

1 = u u yi ≥0 u

a dostaneme

Minimalizovat u za podm´ınek: n X aij pj ≤ 1, j=1

n X

pi =

i=1

1 u

pi ≥ 0

18

Minimalizovat funkci u je to sam´e jako maximalizovat Maximalizovat

n X

Pn

i=1 pi

a dost´ av´ame v´ ysledn´ y tvar:

pi za podm´ınek:

i=1

n X

aij pj ≤ 1,

j=1

pi ≥ 0

tedy tvar, kter´ y um´ıme ˇreˇsit jak uvid´ıme v dalˇs´ı kapitole.

1.5

Simplexov´ a metoda

´ Ulohu line´ arn´ıho programov´an´ı m˚ uˇzeme ch´ apat jako nalezen´ı extr´emu (maxima nebo minima) line´ arn´ı funkce v´ıce promˇenn´ ych pˇri vedlejˇs´ıch podm´ınk´ach vyj´adˇren´ ych line´ arn´ımi rovnicemi, nebo nerovnicemi. Existuje nˇekolik formulac´ı z´akladn´ı u ´lohy line´ arn´ıho programov´an´ı, my budeme pracovat s n´ asleduj´ıc´ımi omezuj´ıc´ımi podm´ınkami: a11 x1 + a12 x2 + · · · + a1n xn ≤ b1 a21 x1 + a22 x2 + · · · + a2n xn ≤ b2 ··· am1 x1 + am2 x2 + · · · + amn xn ≤ bm kde m < n a xi ≥ 0. Jako prvn´ı krok dopln´ıme soustavu o pomocn´e promˇenn´e x ¯1 , · · · x ¯m tak, aby platila n´ asleduj´ıc´ı soustava rovnic: a11 x1 + a12 x2 + · · · + a1n xn + x ¯ 1 = b1 a21 x1 + a22 x2 + · · · + a2n xn + x ¯ 2 = b2 ··· am1 x1 + am2 x2 + · · · + amn xn + x ¯ m = bm kde m < n a bi ≥ 0. Vˇsimnˇeme si, ˇze soustava m´ a ˇreˇsen´ı: x1 = xn = 0, x ¯ 1 = b1 , · · · , x ¯ n = bm . Promˇenn´e x ¯1 , · · · , x ¯n jsou, ale pomocn´e a ˇreˇsen´ı v z´akladn´ıch promˇenn´ ych je x1 = xn = 0. Naˇsim c´ılem je maximalizovat funkci z = c1 x1 + · · · cn xn + d, pˇriˇcemˇz pro naˇse ˇreˇsen´ı x1 = · · · = xn = 0 je hodnota u ´ˇcelov´e funkce rovna d. 19

Pˇrid´ ame si jako dalˇs´ı ˇra´dek soustavy u ´ˇcelovou funkci z − c1 x1 − · · · − cn xn = d, t´ım ale pˇrid´ ame jeˇstˇe jednu promˇennou z (kterou chceme maximalizovat). Matice soustavy pak vypad´a n´ asledovnˇe: 

0 a11 a12 0 a21 a22   .. .. . .  0 am1 am2 1 −c1 −c2

··· ···

a1n a2n

··· ···

amn −cn

1 0 ··· 0 1 ··· .. .. . . ··· 0 0 ··· 0 0 ···

 |b1 |b2   ..  . .   1 |bm  0 |d

0 0 .. .

Zamysleme se ted’ nad t´ım, jak naj´ıt jin´e ˇreˇsen´ı. M´ame soustavu m rovnic o m + n nezn´ am´ ych takovou, ˇze m promˇenn´ ych je z´ akladn´ıch. Dalˇs´ı ˇreˇsen´ı m˚ uˇzeme z´ıskat tak, ˇze pomoc´ı ˇra´dkov´ ych element´arn´ı u ´prav vynulujeme nˇejak´ y dalˇs´ı sloupec. Abychom se rozhodli kter´ y, mus´ıme se pod´ıvat na posledn´ı ˇra´dek soustavy z − c1 x1 − c2 x2 − · · · − cn xn = d Protoˇze vˇsechna xi jsou kladn´ a m˚ uˇzeme zv´ yˇsit hodnotu u ´ˇcelov´e funkce z jen pokud vybereme takov´e ci , kter´e je z´ aporn´e. V naˇsem algoritmu pak vybereme to nejmenˇs´ı ˇc´ıslo (ˇc´ıslo s nejvˇetˇs´ı absolutn´ı hodnotou), protoˇze u nˇeho je pˇredpoklad, ˇze u ´ˇcelovou funkci zv´ yˇs´ıme nejv´ıce. Vybran´ y sloupec bychom pak chtˇeli pˇridat k jednotkov´e matici, ale jeˇstˇe nev´ıme, v˚ uˇci kter´emu ˇra´dku budeme sloupec nulovat. Pˇredstavme si tedy, jak budou vypadat pˇr´ısluˇsn´ a ˇreˇsen´ı pro xi = 0, i 6= k: x1 = b1 − a1k xk x2 = b2 − a2k xk .. . xm = bm − amk xk . S ohledem na podm´ınky nez´ apornosti mus´ı platit: xk ≤

bi . aik

To znamen´a, ˇze mus´ı platit: xk ≤ min

bs bi = . aik ask

pro i = 1, 2, . . . , m, tj. pˇredpokl´ad´ ame, ˇze nejmenˇs´ı pod´ıl je v s–t´e ˇra´dce soustavy. Promˇennou xk naz´ yv´ ame vstupuj´ıc´ı promˇennou a promˇennou xs vystupuj´ıc´ı promˇennou. 20

Pˇ r´ıklad 18. Maximalizujte z = 4x1 + 2x2 za podm´ınek −x1 − 3x2 ≤ 9 2x1 + 3x2 ≤ 18 2x1 − x2 ≤ 10. kde xi ≥ 0. Simplexov´ a matice m´ a tvar 

0 −1 3 1 0 2 3 0  0 2 −1 0 1 −4 −2 0

0 1 0 0

 0 |9 0 |18 . 1 |10 0 |0

Z´ aporn´e hodnoty v posledn´ım ˇr´ adku jsou dvˇe, -4 a -2, vybereme tu menˇs´ı, podˇel´ıme sloupec prav´ ych stran pˇr´ısluˇsn´ ymi koeficienty (pokud jsou kladn´e) a dostaneme: 

0 −1 3 1 0 2 3 0  0 2 −1 0 1 −4 −2 0

0 1 0 0

0 |9 0 |18 1 |10 0 |0

−



18  2  10  . 2

−

y sloupec vzhledem k podrˇzen´e dvojce v Vybereme ten nejmenˇs´ı pod´ıl, tedy 10 2 a nulujeme druh´ tˇret´ım ˇr´ adku   0 −1 3 1 0 0 |9 0 2 3 0 1 0 |18   0 2 −1 0 0 1 |10 . 1 −4 −2 0 0 0 |0 Po proveden´ı pˇr´ısluˇsn´ ych ˇr´ adkov´ ych element´ arn´ıch u ´prav tedy dostaneme. 

0 0  0 1

0 52 0 4 1 − 21 0 −4

 0 12 |14 1 −1 |8  . 0 12 |5  0 2 |20

1 0 0 0

Zlepˇsen´e ˇreˇsen´ı je x1 = 5, x2 = 0, x¯1 = 14, x¯2 = 8, x ¯3 = 0 a hodnota u ´ˇcelov´e funkce je z = 20. V posledn´ım ˇr´ adku je uˇz jen jedno z´ aporn´e ˇc´ıslo -4, a opˇet porovn´ ame pod´ıly.  0 0  0 1

0 52 0 4 1 − 21 0 −4

1 0 0 0

0 12 |14 1 −1 |8 0 12 |5 0 2 |20 21

28  5

2  − −

a vyberme druh´ y ˇr´ adek  0 0  0 1

0 0 1 0

0 1 0 0

1 − 85 0 41 0 81 0 1

9 8 − 14 3 8

1

 |9 |2  . |6  |28

V´ ysledn´e ˇreˇsen´ı je x1 = 6, x2 = 2, x ¯1 = 9, x¯2 = 0, x ¯3 = 0 a hodnota u ´ˇcelov´e funkce je z = 28. V´ ychoz´ı u ´loha pro maticovou hru s matic´ı plateb {aij } je Maximalizovat

n X

pi za podm´ınek:

i=1

n X

aij pj ≤ 1,

j=1

pi ≥ 0. Pokud p = (p1 , . . . , pn ) je libovoln´e optim´ aln´ı ˇreˇsen´ı, pak pi xi = Pm

i=1 pi

je optim´ aln´ı sm´ıˇsenou strategi´ı prvn´ıho hr´ aˇce a ˇc´ıslo 1 u = Pm

i=1 pi

je hodnotou v pˇr´ısluˇsn´e maticov´e hˇre.

1.6

Kooperativn´ı hry

Definice 16. Hrou n hr´ aˇc˚ u v norm´ aln´ım tvaru naz´ yv´ ame model  P = {1, 2, . . . , n} X1 , . . . Xn M1 , . . . Mn ,

kde P je mnoˇzina hr´ aˇc˚ u, X1 , X2 , . . . , Xn jsou mnoˇziny strategi´ı hr´ aˇc˚ u a M1 , M2 , . . . , Mn jsou funkce plateb hr´ aˇc˚ u definovan´e na mnoˇzinˇe v´ ysledk˚ u X=

n Y

Xp

p=1

Kaˇzd´e strategii xp ∈ Xp pˇriˇrad´ıme pˇrirozen´e ˇc´ıslo jp ∈ {1, . . . , mp }. M´ısto mnoˇziny strategi´ı pak zkoum´ ame mnoˇzinu index˚ u Jp = {1, . . . , jp , . . . mp } V t´eto notaci odpov´ıd´ a kaˇzd´e strategii ostatn´ıch hr´ aˇc˚ u (j1 , . . . , jp−1 , jp+1 , . . . , jn ) ∈ J1 × · · · × Jp−1 × Jp+1 × · · · × Jn 22

Toto je koneˇcn´ y poˇcet strategi´ı a my je uspoˇra´d´ ame pomoc´ı pˇrirozen´ ych ˇc´ısel kp = 1, 2, . . . , tp . M˚ uˇzeme pak kaˇzd´ y v´ ysledek hry ps´ at jako (jp , kp ). Platbu hodnot p–t´eho hr´ aˇce odpov´ıdaj´ıc´ı tomuto v´ ysledku m˚ uˇzeme napsat jako: Mp (j1 , . . . , jp , . . . , jn ) = Mp (jp , kp ) = apjk a vˇsechny hodnoty funkce plateb Mp m˚ uˇzeme pak zapsat ve tvaru Ap = (aijk ). Definice 17. Koneˇcnou hrou n hr´ aˇc˚ u v norm´aln´ım tvaru naz´ yv´ ame model   P = {1, 2, . . . , n} J1 , . . . Jn , K1 , . . . Kn A1 , . . . An kde P je mnoˇzina hr´ aˇc˚ u, Jp je uspoˇr´ adan´ a koneˇcn´ a mnoˇzina strategi´ı p–t´eho hr´ aˇce, Kp je uspoˇr´ adan´ a mnoˇzina soubor˚ u strategi´ı protivn´ık˚ u p–t´eho hr´ aˇce a Ap je matice plateb p–t´eho hr´ aˇce (p ∈ P ). Pˇ r´ıklad 19. Mˇejme n´ asleduj´ıc´ı hru. Hraj´ı ji tˇri hr´ aˇci a kaˇzd´ y m´ a dvˇe karty. Prvn´ı m´ a ˇcervenou pˇetku a ˇcernou pˇetku, druh´ y ˇcervenou trojku a ˇcernou pˇetku, tˇret´ı hr´ aˇc ˇcervenou pˇetku a ˇcernou trojku. Hr´ aˇci navz´ ajem svoje karty znaj´ı. Souˇcasnˇe vyloˇz´ı na st˚ ul karty. Pokud maj´ı vˇsechny stejnou barvu, nikdo nikomu nic neplat´ı, pokud ne, tak ten hr´ aˇc, jehoˇz barva je jedin´ a, ostatn´ım dvˇema souˇcet karet, kter´e vyloˇzili. Pˇr´ısluˇsn´ y matematick´ y model: 1. hr´ aˇc 2. hr´ aˇc 3. hr´ aˇc

j1 j1 j2 j2 j3 j3

=1 =2 =1 =2 =1 =2

volil ˇcervenou 5 volil ˇcernou 5 volil ˇcervenou 3 volil ˇcernou 5 volil ˇcervenou 5 volil ˇcernou 3

Uspoˇr´ adan´e mnoˇziny strategi´ı hr´ aˇc˚ u jsou: J1 = (1, 2) J2 = (1, 2) J3 = (1, 2) Uspoˇr´ adan´e mnoˇziny strategi´ı protihr´ aˇc˚ u jsou: K1 = (1, 2, 3, 4) = ((1, 1), (1, 2), (2, 1), (2, 2)) K2 = (1, 2, 3, 4) = ((1, 1), (1, 2), (2, 1), (2, 2)) K3 = (1, 2, 3, 4) = ((1, 1), (1, 2), (2, 1), (2, 2)) A matice plateb jednotliv´ ych hr´ aˇc˚ u jsou pak:   0 5 5 −8 1 A = −8 5 5 0 23



 0 3 3 −8 A = −10 5 5 0   0 5 5 −10 A3 = −8 3 3 0 2

Vˇsimnˇeme si, ˇze jde o hru s konstatn´ım (dokonce nulov´ ym) souˇctem. Definice 18. Necht’ Jp je mnoˇzina ˇcist´ ych strategi´ı p–t´eho hr´ aˇce v koneˇcn´e hˇre n hr´ aˇc˚ u v norm´ aln´ım tvaru. Sm´ıˇsenou strategi´ı p–t´eho hr´ aˇce naz´ yv´ ame mp –rozmˇern´ y vektor p ) y p = (y1p , y2p , . . . , ym p

takov´ y, ˇze X

yip = 1, yip ≥ 0,

i∈Jp

kde p ∈ P, j ∈ Jp . Definice 19. Necht’ P = {1, 2, . . . } je mnoˇzina hr´ aˇc˚ u. Koalic´ı ve hˇre nazveme kaˇzdou podmnoˇzinu S ⊂ P . Definice 20. Koaliˇcn´ı strukturou je soubor nepr´ azdn´ ych podmnoˇzin B = (B1 , B2 , . . . , Bn ) Sk mnoˇziny P , pro kter´e plat´ı j=1 Bj = P (kaˇzd´ y je ˇclenem nˇejak´e koalice)

¯ = {i ∈ P : i ∈ Protikoalici ke koalici K ⊂ P se rozum´ı mnoˇzina hr´ aˇc˚ uK / K}. Mnoˇzina vˇsech hr´ aˇc˚ u se naz´ yv´ a velk´a koalice, jej´ı protikoalice pak pr´ azdn´ a koalice. Pokud Bi ∪ Bj 6= ∅ ∀i, j pak hovoˇr´ıme o disjunktn´ı koaliˇcn´ı struktuˇre. Pozn´ amka 1. Existuje 2n − 1 koalic pro n–hr´ aˇc˚ ua   k n X 1X k k (−1) (k − j)n j k k=1

j=1

disjunktn´ıch koaliˇcn´ıch struktur. Definice 21. Zevˇseobecnˇenou hrou n–hr´ aˇc˚ u v norm´ aln´ım tvaru nazveme model:   P = {1, . . . , n} X1 , . . . , Xn , M1 , . . . , Mn K = (K1 , K2 , . . . , Km ) kde K = (K1 , K2 , . . . , Km ) je koaliˇcn´ı struktura. Definice 22. Mˇejme hru n–hr´ aˇc˚ u P = (1, 2, . . . , n). Charakteristickou funkc´ı naz´ yv´ ame funkci ν : K → R, pro kterou plat´ı: ν(∅) = 0, ν(K1 ∪ K2 ) ≥ ν(K1 ) + ν(K2 ). A dvojici (P, ν) pak kooperativn´ı hrou ve tvaru charakteristick´e funkce. Hra se naz´ yv´ a nepodstatn´ a, pokud ∀Ki , Kj ⊂ P, ν(K1 ∪ K2 ) = ν(K1 ) + ν(K2 ). Jinak se hra naz´ yv´ a podstatn´ a. 24

V dalˇs´ım se budeme zab´ yvat kooperativn´ımi hrami, kter´e umoˇzn ˇuj´ı pˇrerozdˇelen´ı zisku. Definice 23. Mˇejme hru (P, ν), n–tice a re´ aln´ ych ˇc´ısel naz´ yv´ ame imputace, jsou–li splnˇeny n´ asleduj´ıc´ı podm´ınky: • individu´ aln´ı racionalita: pro kaˇzd´eho hr´ aˇce i je ai ≥ ν({i}), • kolektivn´ı racionalita plat´ı

Pn

i=1 ai

= ν(P ).

Individu´aln´ı racionalita vede k potˇrebˇe vytv´aˇret koalice a kolektivn´ı racionalita p˚ usob´ı proti vytv´aˇren´ı velk´ ych koalic. Bez d˚ ukazu uvedeme n´ asleduj´ıc´ı vˇetu: Vˇ eta 6. Necht’ (P, ν) je hra ve tvaru charakteristick´e funkce. Je-li nepodstatn´ a, pak m´ a pr´ avˇe jednu imputaci, a to a = (ν(1), ν(2), . . . , ν(N )). Je-li v podstatn´ a, pak m´ a nekoneˇcnˇe mnoho imputac´ı. Definice 24. Necht’ (P, ν) je hra ve tvaru charakteristick´e funkce, K je koalice, a, b jsou impuˇ tace. Rekneme, ˇze a dominuje b pro koalici K, jestliˇze plat´ı: • ai > bi pro vˇsechna i ∈ K, •

P

i∈K

ai ≤ ν(K).

Dominanci budeme znaˇcit symbolem a ≻K b. Druh´ a podm´ınka ˇr´ık´a, ˇze imputace je dosaˇziteln´ a. Definice 25. Necht’ v je hra ve tvaru charakteristick´e funkce. J´ adro hry je tvoˇreno vˇsemi imputacemi, kter´e nejsou dominov´ any ˇza ´dnou jinou imputac´ı pro ˇza ´dnou jinou koalici. N´asleduj´ıc´ı vˇeta n´ am usnadˇ nuje nalezen´ı j´adra, opˇet si ji uvedeme bez d˚ ukazu Vˇ eta 7. Necht’ (P, ν) je hra ve tvaru charakteristick´e funkce s N hr´ aˇci a necht’ a je N –tice ˇc´ısel. Potom a je imputace v j´ adru pr´ avˇe, kdyˇz plat´ı: •

PN

•

P

i=1 ai

i∈K

= ν(P )

ai ≤ ν(K) pro kaˇzdou koalici K.

Je-li tedy imputace ξ v j´adru dan´e hry, nem´ a ˇz´adn´ a skupina hr´ aˇc˚ u d˚ uvod vytvoˇrit jinou koalici a nahradit ξ jinou imputaci. 25

Pˇ r´ıklad 20. Uvaˇzujme hru tˇr´ı hr´ aˇc˚ u s charakteristickou funkc´ı: ν({1}) = −

1 2

ν({2}) = 0 ν({3}) = −

1 2

1 4 ν({1, 3}) = 0 1 ν({2, 3}) = 2 ν({1, 2, 3}) = 1 ν({1, 2}) =

J´ adro je pak: a1 + a2 + a3 = 1 a1 ≥ −

1 2

a2 ≥ 0 a3 ≥ −

1 2

1 4 a1 + a3 ≥ 0 1 a2 + a3 ≥ 2

a1 + a2 ≥

Tato soustava m´ a nekoneˇcnˇe mnoho ˇreˇsen´ı, prvkem j´ adra je napˇr´ıklad trojice ( 31 , 13 , 13 ). N´asleduj´ıc´ım pˇr´ıklad popisuje postup pˇri hled´ an´ı j´adra pro hru v norm´aln´ım tvaru. Z´ akladem je nalezen´ı charakteristick´e funkce, kter´a bude pro kaˇzdou koalici odpov´ıdat pˇr´ısluˇsn´ ym platb´ am rovnov´aˇzn´ ych startoviˇstˇe bimaticov´e hry koalice vs. pˇr´ısluˇsn´ a protikoalice. Dostaneme tak hru ve tvaru charakteristick´e funkce a pˇr´ısluˇsn´e j´adro. Toto j´adro lze nal´ezt pro jakoukoli maticovou hru a kaˇzd´e takto nalezen´e j´adro nese informaci o p˚ uvodn´ı hˇre v norm´aln´ım tvaru. Pokud, ale chceme aby j´ adro odpov´ıdalo pˇresnˇe vˇsem moˇzn´ ym rozdˇelen´ım plateb v pˇr´ısluˇsn´ ych koalic´ıch mus´ıme zaruˇcit, ˇze vznikem koalice budou ostatn´ı hr´ aˇci pˇrinuceni vytvoˇrit protikoalici. Tedy, ˇze pˇr´ısluˇsn´ a hodnota charakteristick´e funkce opravdu maximalizuje platbu koalice t´ım, ˇze souˇcasnˇe minimalizuje platbu proti koalice. Pˇ r´ıklad 21. Mˇejme koneˇcnou hru tˇr´ı hr´ aˇc˚ u, kde kaˇzd´ y hr´ aˇc m´ a dvˇe strategie: 26

(j1 ,j2 ,j3 ) 1,1,1 1,1,2 1,2,1 1,2,2 2,1,1 2,1,2 2,2,1 2,2,2

M1 2 1 3 -1 0 3 1 2

M2 1 3 2 1 2 0 3 -2

M3 3 1 1 4 -1 2 -2 3

Pˇredokl´ ad´ ame, ˇze jde o kooperativn´ı hru, tj. jsou pˇr´ıpustn´e vˇsechny koalice. Matice plateb koalice {1} vypad´ a n´ asledovnˇe: 1 2

(11) 2 0

(12) 1 3

(21) 3 1

(22) 1 2

Optim´ aln´ı sm´ıˇsenou strategi´ı je vektor ( 27 , 57 ) a hodnotou hry je ˇc´ıslo pˇredstavuje hodnota 4 ν({1}) = . 7 Matice plateb koalice {2} vypad´ a n´ asledovnˇe: 1 2

(11) 1 2

(12) 3 1

(21) 2 3

4 7.

Hodnotu koalice tedy

(22) 0 -2

Optim´ aln´ı sm´ıˇsenou strategi´ı je vektor (1, 0) a hodnotou hry je ˇc´ıslo 0. Hodnotu koalice tedy pˇredstavuje hodnota ν({2}) = 0. Matice plateb koalice {3} vypad´ a n´ asledovnˇe: 1 2

(11) 3 1

(12) 1 4

(21) -1 2

(22) -2 3

Optim´ aln´ı sm´ıˇsenou strategi´ı je vektor ( 14 , 45 ) a hodnotou hry je ˇc´ıslo pˇredstavuje hodnota 7 ν({3}) = 5 Matice plateb koalice {1,2} vypad´ a n´ asledovnˇe: 1 3 5 2 4

(11) (12) (21) (22) 27

2 4 0 3 0

7 5.

Hodnotu koalice tedy

Optim´ aln´ı sm´ıˇsenou strategi´ı je vektor ( 23 , 31 , 0, 0) a hodnotou hry je ˇc´ıslo tedy pˇredstavuje hodnota 10 ν({1, 2}) = . 3 Matice plateb koalice {1,3} vypad´ a n´ asledovnˇe: (11) (12) (21) (22)

1 5 2 -1 5

10 3 .

Hodnotu koalice

10 3 .

Hodnotu koalice

2 4 3 -1 5

Optim´ aln´ı sm´ıˇsenou strategi´ı je vektor (0, 0, 0, 1) a hodnotou hry je ˇc´ıslo tedy pˇredstavuje hodnota ν({1, 3}) = 5 Matice plateb koalice {2,3} vypad´ a n´ asledovnˇe: 1 4 4 3 5

(11) (12) (21) (22)

2 1 2 1 1

Optim´ aln´ı sm´ıˇsenou strategi´ı je vektor (0, 1, 0, 0) a hodnotou hry je ˇc´ıslo koalice tedy pˇredstavuje hodnota ν({2, 3}) = 2.

10 3 .

Hodnotu prvn´ı

Hodnotu charakteristick´e funkce koalice vˇsech hr´ aˇc˚ u dostaneme jako maximum souˇctu plateb a to je 6 pro vektory (1, 1, 1) a (1, 2, 1). Tedy ν({1, 2, 3}) = 6. Charakteristick´ a funkce t´eto hry je tedy: ν(∅) = 0 4 ν({1}) = 7 ν({2}) = 0 7 ν({3}) = 5 10 ν({1, 2}) = 3 ν({1, 3}) = 5 ν({2, 3}) = 2 ν({1, 2, 3}) = 6

28

a jedn´ a se o podstatnou hru s nekonstantn´ım souˇctem. V j´ adru jsou pak imputace splˇ nuj´ıc´ı n´ asleduj´ıc´ı podm´ınky: a1 + a2 + a3 = 6 4 a1 ≥ 7 a2 ≥ 0 4 a3 ≥ 7 10 a1 + a2 ≥ 3 a1 + a3 ≥ 5 a2 + a3 ≥ 2 A to je napˇr´ıklad (3, 1, 2), ale i (4, 0, 2). Pˇ r´ıklad 22. Honza m´ a star´ y automobil, kter´ y nepouˇz´ıv´ a a je pro nˇej bezcenn´ y, pokud jej nebude moci prodat. O koupi se zaj´ımaj´ı dva lid´e, Marie a Frantiˇsek. Marie automobil cen´ı na 50 000 Kˇc Frantiˇsek na 70 000 Kˇc. Hra spoˇc´ıv´ a v tom, ˇze z´ ajemci navrhnou cenu Davidovi a ten bud’ pˇr´ıjme jednu z nab´ıdek, nebo obˇe odm´ıtne.

1.7

Opakovan´ e hry

Jako motivaci k t´eto kapitole si uvedeme opakovanou verzi vˇezˇ nova dilematu, pˇreformulovanou na probl´em placen´ı nebo neplacen´ı koncesion´aˇrsk´ ych poplatk˚ u. Pˇ r´ıklad 23 (Koncesion´aˇrovo dilema). Mˇejme maticovou hru zaloˇzenou na placen´ı/neplacen´ı koncesion´ aˇrsk´ ych poplatk˚ u. Koncesion´ aˇrsk´e poplatky jsou hlavn´ım pˇr´ıjmem veˇrejnopr´ avn´ı televize a pokud by vˇetˇsina div´ aku poplatky pˇrestala platit, vedlo by to k neodvratn´emu z´ aniku stanice. Pokud ale pˇrestane platit jeden, kvalita se nezmˇen´ı a m˚ uˇze si tak uˇz´ıvat vys´ıl´ an´ı zdarma. Realizujeme si tuto hru jako bimaticou hru dvou hr´ aˇc˚ u.

zaplat´ı nezaplat´ı

zaplat´ı (10,10) (5,20)

nezaplat´ı (20,5) (6,6)

Hra obsahuje rovnov´aˇznou strategii ve kter´e oba hr´ aˇci nezaplat´ı. Pokud by se ale dohodli a oba zaplatili z´ıskaj´ı pˇri opakovan´ı t´eto hry mnohem v´ıce. Pˇredstavme si tedy, ˇze se hra opakuje, pˇriˇcemˇz v kaˇzd´em kole je pravdˇepodobnost, ˇze se uskuteˇcn´ı jeˇstˇe i kolo n´ asleduj´ıc´ı, rovna 32 . Budou–li hr´ aˇci spolupracovat, pak oˇcek´avan´ a hodnota v´ yhry je pro oba rovna πn = 10 + 10 ·

2 2 2 2 + 10 · ( )2 + 10 · ( )3 + · · · 10 · ( )n + · · · 3 3 3 3

Protoˇze strategi´ı v opakovan´e hˇre je pl´ an jak se chovat v pr˚ ubˇehu cel´e hry, m˚ uˇzeme uvaˇzovat napˇr´ıklad strategie : 29

nevraˇ zivec: Spolupracuj, dokud tˇe druh´ y nepodraz´ı. Je jasn´e, ˇze potkaj´ı-li se dva nevraˇzivci, budou do konce hry spolupracovat a z´ıskaj´ı tak oba hodnotu πn . Dalˇs´ı strategi´ı m˚ uˇze b´ yt padouch: Spolupracuje a pak zrad´ı. Pˇredpokl´adejme, ˇze k odchylce doˇslo v kole n + 1 a padouch i nevraˇzivec od tohoto kola zr´ az´ı. πp = 10 + 10 ·

2 2 2 2 2 2 + 10 · ( )2 + 10 · ( )3 + · · · 10 · ( )n−1 + 20 · ( )n + 6 · ( )n+1 + · · · 3 3 3 3 3 3

Protoˇze, ale πn > πd z˚ ust´ av´a strategie nevraˇzivec/nevraˇzivec rovnov´aˇzn´ a. Dalˇs´ı strategi´ı pak m˚ uˇze b´ yt: p˚ ujˇ cka na opl´ atku: Prvn´ım tahem spolupracuje a pak opakuje protivn´ık˚ uv tah. Strategie p˚ ujˇcka na opl´ atku/p˚ ujˇcka na opl´ atku tak´e pˇredstavuje rovnov´aˇzn´ y bod. Nˇejak´e dalˇs´ı strategie mohou b´ yt: Pavlov: Spolupracuje pr´ avˇe tehdy, kdyˇz v pˇredchoz´ım kole zvolili oba hr´ aˇci stejnou strategii jinak zrad´ı. Hard Joss (Joss – ˇ c´ınsk´ a modla): Hraje jako p˚ ujˇcka za opl´ atku, ale spolupracuje jen s pravdˇepodobnost´ı 0,9 Abychom mohli opakovan´e hry zkoumat, potˇrebujeme opˇet matematickou formalizaci probl´emu: Pravidla hry – pˇredpis, kter´ y stanovuje, jak´ ym zp˚ usobem urˇcuj´ı hr´ aˇci v´ ybˇer sv´ ych alternativ. Tah – volba element´ arn´ı alternativy Osobn´ı tah – tah uskuteˇcnˇen´ y hr´ aˇci N´ ahodn´ y tah – tah uskuteˇcnˇen´ı n´ ahodn´ ymi mechanismy. Partie – posloupnost tah˚ u Libovoln´e koneˇcn´e mnoˇzinˇe n hr´ aˇc˚ u m˚ uˇzeme pˇriˇradit nˇejak´ y strom S(T ). Vrcholy stromu pak naz´ yv´ ame pozicemi. Mnoˇzinu vˇsech tah˚ u i–t´eho hr´ aˇce oznaˇcujeme Ti a mnoˇzinu vˇsech koncov´ ych pozic jako T ⋆ . Tedy kaˇzd´emu mysliteln´emu pr˚ ubˇehu hry odpov´ıd´ a jedna cesta stromu S(T ) od poˇc´atku do nˇekter´e z koncov´ ych pozic v T ⋆ . Pˇ r´ıklad 24. Mˇejme hru pˇri kter´e je jedna partie posloupnost´ı ˇctyˇr tah˚ u 1. tah prvn´ı hr´ aˇc vol´ı ˇc´ıslo α1 ∈ {1, 2} 2. tah druh´ y hr´ aˇc vol´ı ˇc´ıslo β ∈ {1, 2} 3. tah tˇret´ı hr´ aˇc vol´ı ˇc´ıslo δ ∈ {1, 2} 4. tah prvn´ı hr´ aˇc vol´ı ˇc´ıslo α2 ∈ {1, 2} Druh´ y hr´ aˇc nezn´ a v´ ysledky prvn´ıho tahu, tˇret´ı hr´ aˇc uˇz je zn´ a, ale nezn´ a v´ ysledky druh´eho tahu. Posledn´ı tah provede prvn´ı hr´ aˇc tak´e se znalost´ı prvn´ıho tahu. V´ ysledn´e platby Mp pak obsahuje n´ asleduj´ıc´ı tabulka: 30

(α1 , β, δ, α2 ) (1, 1, 1, 1) (1, 1, 1, 2) (1, 1, 2, 1) (1, 2, 1, 1) (2, 1, 1, 1) (1, 1, 2, 2) (1, 2, 2, 1) (2, 2, 1, 1) (2, 1, 2, 1) (1, 2, 1, 2) (2, 1, 1, 2) (1, 2, 2, 2) (2, 2, 2, 1) (2, 1, 2, 2) (2, 2, 1, 2) (2, 2, 2, 2)

F1 -1 3 4 1 6 -3 -1 0 2 -1 4 0 -2 -2 -1 3

F1 -1 -4 2 0 -2 1 2 2 -4 3 -4 -3 2 -2 -1 0

F1 2 1 -6 -1 4 2 -1 -2 2 -2 0 3 0 4 2 -3

Celkem m´ ame 16 moˇzn´ ych pr˚ ubˇeh˚ u partie hry, tedy strom bude m´ıt 16 cest z koˇrene na jeden z list˚ u. Tabulka je tabulkou hry v pˇr´ıpadˇe, ˇze se ˇz´adn´ a informace nepˇren´ aˇs´ı, tedy zejm´ena by prvn´ı hr´ aˇc pˇri sv´em druh´em tahu neznal sv˚ uj prvn´ı coˇz je nepravdˇepodobn´e. Pˇr´ısluˇsn´ y strom je naznaˇcen´ y v n´ asleduj´ıc´ım obr´ azku:

 1 @2 @  R @

III. hr´ aˇc



  PP PP 1 2  PP   PP  PP    )  q P II. hr´ aˇc q3 q2     H 1  HHH 2 1 2 HH    HH  H      j   j H

I. hr´ aˇc

q4

q1

 1 @2 @  R @

q5

 1 @2 @  R @

q6

 1 @2 @  R @

q7

        1
A 2
A2 1
A 2 1 1
A 2 1
A 2 1
A 2 1
A 2 1
A 2 AU U A U A AU AU AU AU AU        

 















aˇc q9 q8 I. hr´

q10

q11

q12

q13

q14

q15

               

Pˇriˇcemˇz pˇr´ısluˇsn´e mnoˇziny tah˚ u hr´ aˇc˚ u jsou n´ asleduj´ıc´ı:

T1 = {q1, q8, q9, q10, q11, q12, q13, q14} T2 = {q2, q3, } T3 = {q4, q5, q6, q7} 31

Abychom mohli pˇri v´ ypoˇctu zohlednit informaci, kterou m´ a kaˇzd´ y hr´ aˇc k dipozici, zavedeme n´ asleduj´ıc´ı pojem informaˇcn´ı mnoˇziny: Definice 26. Informaˇcn´ı mnoˇzinou i–t´eho hr´ aˇce v koneˇcn´e hˇre n–hr´ aˇc˚ u v rozvinut´em tvaru rozum´ıme nˇejakou podmnoˇzinu Tis mnoˇziny vˇsech jeho pozic Ti , kde s = si , i = 1, 2, . . . , k pro kterou plat´ı: S 1. i Tis = Ti 2. Tis ∩ Tir = ∅ pro libovoln´e s, r takov´e, ˇze s 6= r

3. ze vˇsech pozic q ∈ Tis t´e stejn´e informaˇcn´ı mnoˇziny vych´ az´ı stejn´ y poˇcet hran stromu S(T ) 4. Pokud plat´ı q1 , q2 ∈ Tis potom nem˚ uˇze platit q1 < q2 ani q2 < q1 Poˇcet alternativ, kter´e m´ a i–t´ y hr´ aˇc v kaˇzd´e pozici sv´e informaˇcn´ı mnoˇziny Tis , oznaˇc´ıme jako Vis . Hrany vych´ azej´ıc´ı z kaˇzd´e pozice q ∈ Tis uspoˇr´ ad´ ame pomoc´ı indexu vis = 1, 2, . . . Vis . Prvn´ı a druh´a podm´ınka v definici ˇr´ık´a, ˇze pˇr´ısluˇsn´e informaˇcn´ı mnoˇziny kaˇzd´eho hr´ aˇce tvoˇr´ı ˇ rozklad na mnoˇzinˇe jeho tah˚ u. Ctvrt´ a podm´ınka ˇr´ık´a, ˇze informaˇcn´ı mnoˇziny nemohou obsahovat prvky z r˚ uzn´ ych pater stromu. Nepˇripouˇst´ıme tedy informaˇcn´ı mnoˇzinu, kter´a obsahuje tahy z r˚ uzn´ ych kol a nen´ı tedy moˇzn´e, aby hr´ aˇc nemˇel informaci o sv´ ych vlastn´ıch pˇredeˇsl´ ych taz´ıch. Tˇret´ı podm´ınka nav´ıc urˇcuje, ˇze v dan´e informaˇcn´ı mnoˇzinˇe m´ a kaˇzd´ y tah stejn´ y poˇcet strategi´ı. V pˇredch´ azej´ıc´ım pˇr´ıkladˇe m´ a prvn´ı hr´ aˇc tˇri informaˇcn´ı mnoˇziny T11 = {q0} T12 = {q7, q8, q9, q10} T11 = {q11, q12, q13, q14} '

  PP PP 1 2 & % PP   P PP    PP )  q II. hr´ aˇc q3 q2     H 1  HHH 2 1 2 HH    HH  H      j   j H

I. hr´ aˇc

 @2 '1 @  R @

III. hr´ aˇc

T11 $



q4

q1

  T12' 1 @2 1 @2 $ @ @   R @ R @

q6

q5

 1 @2 T13 $ @   R @

q7

       
A2 1
A 2 1
A 2 % 1
A 2 1
A 2 1
A 2 1
A 2 % 1
A 2 1 & & U A AU AU AU AU AU AU U A         













 



aˇc q9 q8 I. hr´

q10

q12

q11

q13

q14

q15

               

32

pˇriˇcemˇz v11 = 1, 2 v12 = 1, 2 v11 = 1, 2

druh´ y hr´ aˇc m´ a jednu informaˇcn´ı mnoˇzinu T21 = {q1, q2} '

T11 $



  PP PP 1 2 & % PP  ' $  PP   PP T21   )  q P

I. hr´ aˇc

  H 1 2  HH &  HH    j

II. hr´ aˇc

q4

  H 1 2%  HH  HH    j

q2

 @2 '1 @  R @

III. hr´ aˇc

q1

q3

  1 @2 1 @2 T12' $ @ @   R @ R @

q6

q5

 1 @2 T13 $ @  R @

q7

        1
A 2 1
A 2 1 1
A 2 1
A 2 % 1
A 2 1
A 2
A2 1
A 2 % & & AU U A U A AU AU AU AU AU        
   
 

 
 




 

aˇc q9 q8 I. hr´

q10

q11

q12

q13

q14

q15

               

pˇriˇcemˇz

v21 = 1, 2

a tˇret´ı hr´ aˇc m´ a dvˇe informaˇcn´ı mnoˇziny T31 = {q3, q4} T32 = {q5, q6} 33

'

T11 $



  PP 1 PP 2 & %  PP  $ '  P PP  T21   P ) q P II. hr´ aˇc q3 q2      H 1  HHH 2%  1 2 HH  &      HH  H      j   j H T31 T32

I. hr´ aˇc

 1 @2 ' @  R @

III. hr´ aˇc

q4

q1

   T12' 1 @2 1 @ 2 $ @ @   R @ R @

q6

q5

 T13 1 @ 2$ @  R @

q7

       
A2 1
A 2 1
A 2 % 1
A 2 1
A 2 1
A 2 % 1
A 2 1
A 2 1 & & U A AU AU AU AU AU AU U A         













 



aˇc q9 q8 I. hr´

q10

q12

q11

q13

q14

q15

               

pˇriˇcemˇz

v31 = 1, 2 v32 = 1, 2 Naˇsim c´ılem je vytvoˇrit norm´aln´ı tvar hry n–hr´ aˇc˚ u tak, aby v´ ysledn´ a hra jiˇz obsahovala pˇr´ısluˇsnou informaci. ˇ Cistou strategi´ı p–t´eho hr´ aˇce ve hˇre s rozvinut´ ym tvaru nazveme diskr´etn´ı funkci gp (Tps ) = vps kde s = sp = 1, 2, . . . Sp definovanou na mnoˇzinˇe informaˇcn´ıch mnoˇzin Tp1 , . . . , Tps , . . . , Tpsp potom jeho ˇcistou strategii m˚ uˇzeme napsat jako soubor pˇrirozen´ ych ˇc´ısel. (vp1 , . . . , vps , . . . , vpsp ) pro p–t´eho hr´ aˇce existuje mp = Vp1 × · · · × Vps × · · · × Vpsp takov´ ych ˇcist´ ych strategi´ı. Pokud uspoˇra´d´ ame strategie, tj. kaˇzd´e funkci gp pˇriˇrad´ıme pˇrirozen´e ˇc´ıslo jp = 1, 2, . . . mp dostaneme mnoˇzinu Jp strategi´ı p–t´eho hr´ aˇce. Funkce plateb je Mp (j1 , j2 , . . . , jn ) = Fp (q) Prvn´ı hr´ aˇc z pˇredeˇsl´eho pˇr´ıkladu m´ a tˇri informaˇcn´ı mnoˇziny T11 , T12 , T13 pˇriˇcemˇz 34

v11 = 1, 2 v12 = 1, 2 v13 = 1, 2 Prvn´ı hr´ aˇc m´ a tedy 2 × 2 × 2 = 8 ˇcist´ ych strategi´ı, kter´ y m˚ uˇzeme uspoˇra´dat takto: j1 = 1, 2, 3, 4, 5, 6, 7, 8 Pˇ r´ıklad 25. Podnik m˚ uˇze vyr´ abˇet dva v´ yrobky {1, 2} v mnoˇzstv´ı bud’ z1 kus˚ u 1. v´ yrobku, nebo z2 kus˚ u druh´eho v´ yrobku, pˇriˇcemˇz na v´ yrobu obou dvou v´ yrobk˚ u pouˇz´ıv´ a

35

2

Aplikace teorie her

2.1

Dopravn´ı hry

Pˇ r´ıklad 26 (Pigou 1920). Mˇejme n´ asleduj´ıc´ı diagram:  

c(x)=1

 

c(x)=1

x . . . jednotka dopravy. Pokud m´ a n hr´ aˇcu dohromady jednu jednotku dopravy a chtˇej´ı minimalizovat platbu c je doln´ı cesta rovnov´ aˇznou strategi´ P ı a hodnota t´eto strategie je ni=1 1 = n.

Optim´ aln´ı startegie je strategie, kter´ a minimalizuje spoleˇcnou platbu tedy strategie P 12 1 P1 kdy p˚ ulka jede spodem a p˚ ulka horem n=1 2 + n= 1 12 = 43 . 2

U her, kde se optim´ aln´ı strategie liˇs´ı od rovnov´aˇzn´e hraje roli jejich pomˇer a definujeme: Nejhorˇs´ı rovnov´aˇzn´ a strategie . Optim´aln´ı strategie Nejlepˇs´ı rovnov´aˇzn´ a strategie M´ıra stability = . Optim´aln´ı strategie

M´ıra anarchie =

V naˇsem pˇr´ıkladˇe se m´ıra stability a m´ıra anarchie rovnaj´ı ˇc´ıslu (existuje jen jedna rovnov´aˇzn´ a strategie, kter´a je souˇcasnˇe nejlepˇs´ı i nejhorˇs´ı) 4 1 = 3/4 3 Shapleyho model s´ıt’ov´ e hry: Necht’ G je orientovan´ y graf (V, E) spolu s funkc´ı E → R+ a necht’ ˇc´ıslo ce je hodnotou funkce c na hranˇe e ∈ E. Mˇejme k hr´ aˇc˚ u, kde kaˇzd´ y hr´ aˇc i ∈ {1, . . . , k} m´ a pˇriˇrazenou dvojici start-c´ıl ’ na kter´e se hra odehr´av´a je (si , ci ) a jeho strategie jsou cesty z s do c tvoˇ r ´ ıc´ ı mnoˇ z inu P . S´ ıt i i i P tedy P = e∈∪i Pi ce . Kaˇzd´ y hr´ aˇc pˇri uˇzit´ı hrany e plat´ı fcee , kde fe je poˇcet hr´ aˇc˚ u, kteˇr´ı danou hranu vyuˇz´ıvaj´ı. Pˇ r´ıklad 27. Mˇejme n´ asleduj´ıc´ı diagram: c(x)=k x . . . jednotka dopravy   ǫ ∈ R+ je dostateˇcnˇe mal´e si ci doln´ ı cesta je rovnov´ aˇznou i optim´ aln´ı strateg´ı   horn´ı cesta je rovnov´ aˇznoustrateg´ı c(x)=1+ǫ Cena optim´ aln´ı strategie, je 1 + ǫ a to je i cena lepˇs´ı ze dvou rovnov´ aˇzn´ ych strategi´ı, cena hroˇs´ı rovnov´ aˇzn´e strategie je k. M´ıra stability je 1 a m´ıra anarchie se bl´ıˇz´ı ke ”k” spolu s t´ım jak se ǫ bl´ıˇz´ı k nule. 36

Pˇ r´ıklad 28. Mˇejme pro nˇejak´e ǫ ∈ R+ dostateˇcnˇe mal´e n´ asleduj´ıc´ı diagram:

'$

t

I o S S &% 
 J

S 6]


S J


S J


S J 1 1 12
31 S k1 J k−1


S J


 S J        

 J A

0 0 0 J 0A 0

 J A

 J A

 J A

 J  A ?   J AU

v ^ J  /  

s1

s2

s3

...

sk−1

sk

1+ǫ

Optim´ aln´ı strategi´ı je v tomto pˇr´ıkladˇe ta kdy si kaˇzd´ y z hr´ aˇc˚ u vybere delˇs´ı cestu si → v → ci a hodnota hry je pak 1 + ǫ, ale to nen´ı rovnov´ aˇzn´ a strategie. Rovnov´ aˇznou strategi´ pro Pı kje naopak 1 vˇsechny hr´ aˇce volba kratˇs´ı cesty si → ci v tomto pˇr´ıpadˇe je, ale hodnota hry i=1 i ≈ ln(k). M´ıra stability a m´ıra anarchie pak konverguj´ı k ln(k) pro k → ∞ a ǫ → 0

Tyto dva pˇr´ıklady mˇely za c´ıl demonstrovat nˇejak´e klasick´e pˇr´ıklady teorie her v dopravˇe, pˇrejdˇeme ale k systematiˇctˇejˇs´ımu pˇr´ıstupu. Neatomick´ e hry. S´ıt’ pro n´ as bude orientovan´ y graf G = (V, E), spolu s mnoˇzinou uspoˇra´dan´ ych dvojic (komodit) (si , ci ) pro i ∈ {1, . . . , k}, Kaˇzd´ y hr´ aˇc se identifikuje s jednou komoditou a mnoˇzina moˇzn´ ych cest z si do ci oznaˇcovan´ a jako Pi je mnoˇzinou jeho strategi´ı. Pˇredpokl´ad´ ame, ˇze Pi 6= ∅ tedy, ˇze pro kaˇzdou komoditu existuje cesta, kterou j´ı m˚ uˇzeme pˇrepravit. Nakonec oznaˇc´ıme mnoˇzinu vˇsech cest k X Pi P = i=1

V´ ybˇer cest pro jednotliv´e komodity reprezentujeme tokem v s´ıti, kter´ y charakterizujeme nez´ aporn´ ym vektorem indexovan´ ym mnoˇzinou P . Tedy hodnota p–t´e souˇradnice vektoru, tj. fp je obˇem komodity i, kter´ y je pˇrepravovan´ y cestou p ∈ Pi . V naˇsem modelu, je doprava ”neelastick´a”a tedy je nutn´e pˇrepravit pˇredepsan´e mnoˇzstv´ı komodity i oznaˇcovan´e jako ri . Tok je uskuteˇcniteln´ y pro vektor r pokud pro kaˇzd´e i ∈ {1, 2, . . . , k} 37

P plat´ı p∈Pi = ri . Kaˇzd´ a hrana e je nav´ıc vybavena cenovou funkc´ı ce : R+ → R+ takovou, ˇze c je nez´ aporn´ a, spojit´a a neklesaj´ıc´ı. Pˇr´ıkladem m˚ uˇze b´ yt tˇreba zpoˇzdˇen´ı. Neatomick´ a dopravn´ı hra je tedy s´ıt’ (G, r, c), strategie jsou v´ ybˇery pˇr´ısluˇsn´ ych cest a hodnota cesty vzhledem k toku f je pak cp (f ) =

X

ce (fe ), kde fe =

e∈p

X

fp

p∈P :e∈p

Hodnota fe urˇcuje objem libovoln´e komodity pˇrepraven´e pˇres hranu e a hodnota cp (f ) urˇcuje platbu za pˇrepraven´ı komodity i cestou p ∈ Pi . Definice 27. Rovnov´aˇzn´ y tok je pˇr´ıpustn´ y tok v neatomick´e dopravn´ı hˇre (G, r, c) je takov´ y tok, ˇze pro kaˇzdou komoditu i ∈ {1, 2, . . . , k} a kaˇzdou dvojici p, p¯ ∈ Pi takovou, ˇze fp¯ ≥ 0 plat´ı, ˇze cp (f ) ≤ cp¯(f ) Pˇredeˇsl´ a definice vlastnˇe ˇr´ık´a, ˇze hodnotu pod´ıv´ame li se na kaˇzdou komoditu a na libovoln´e dvˇe cesty kudy j´ı lze pˇrepravit tak jsou obˇe platby stejn´e, nebo je jedna nulov´a. Hodnota toku je pak X X ce (fe )fe cp (f )fp = C(f ) := e

p∈P

a ˇr´ık´ame, ˇze tok je optim´ aln´ı pokud minimalizuje hodnotu pˇres vˇsechny pˇr´ıpustn´e toky. Pˇ r´ıklad 29 (Neline´arn´ı – Pigou). Mˇejme n´ asleduj´ıc´ı diagram: c(x)=x 







p je dostateˇcnˇe velk´e hr´ aˇci maj´ı dohromady jednu jednotku dopravy

c(x) = xp Existuje jedin´ a rovnov´ aˇzn´ a, vˇsichni jedou spodem a hodnota je jedna. Optim´ aln´ı v´ ysledek je −1 p strategie kdy mal´e mnoˇzstv´ı ǫ = 1 − (p + 1) jede horem a hra m´ a hodnotu ǫ + (1 − ǫ)p = −1

1 − (p + 1) p + (p + 1)−1 = 1 − (p + 1) → 0 a m´ıra anarchie → ∞

−1 p

+ (p + 1)−1 , pro p → ∞ hodnota optim´ aln´ıho toku

Uvedeme si ted’ jeden ze z´ akladn´ıch pˇr´ıklad˚ u teorie her v dopravˇe. Pˇ r´ıklad 30 (Braess˚ uv paradox). Mˇejme sch´ema: 38



  S

S

S c(x) = x

S

S

S

c(x) = 1 S

S 

 w S

v

 J J J J c(x) = 1J

s

   

hr´ aˇci maj´ı dohromady jednu jednotku dopravy jedin´ a rovnov´ aˇzn´ a strategie je kdyˇz p˚ ulka hr´ aˇc˚ u t ulka spodem, cena toku je pak 32  jede vrchem a p˚ 7  a je to i optim´ aln´ı strategi´ı.  c(x) = x 

J J  J ^ J  

w

Paradox je to proto, ˇze pokud vybudujeme rychlostn´ı komunikaci mezi body v a w cena rovnov´ aˇzn´eho toku se paradoxnˇe zv´ yˇs´ı: 



S

 S

S c(x) = x

S

S

S

c(x) = 1 S

S 

 w S 0

v

 J J J J c(x) = 1J J

s

   

hr´ aˇci maj´ı dohromady jednu jednotku dopravy rovnov´ aˇzn´ a strategie je pro vˇsechny hr´ aˇce s → v → w → c t to nen´ ı optim´ a ln´ ı strategi´ ı ,  7  protoˇze cena tohoto toku je 2.  c(x) = x 

J J ? ^ J  

w

M´ıra anarchie t´eto hry se tedy zv´ yˇsila na

4 3

Atomick´ e hry Mˇejme • orientovan´ y graf G = (V, E) 39

• k dvojic komodit (si , ci ) pro i ∈ {1, . . . , k}, • kladnou hodnotu ri urˇcuj´ıc´ı mnoˇzstv´ı komodit, kter´e mus´ıme pˇrepravit, • nez´ apornou, spojitou, neklesaj´ıc´ı funkci ce : R → R pro kaˇzdou hranu e ∈ E. Mˇejme k hr´ aˇc˚ u, kde kaˇzd´ y je spojen s jednou komoditou a jeho strategie jsou jsou pak mnoˇziny cest Pi . Poznamenejme, ˇze zat´ım co v neatomick´ ych hr´ ach reprezentuj´ı komodity velk´e mnoˇzstv´ı individualit kontroluj´ıc´ıch zanedbatelnou ˇc´ast dopravy, v atomick´ ych hr´ ach kaˇzdou komoditu reprezentuje jeden hr´ aˇc, kter´ y mus´ı pˇrepravit urˇcit´e mnoˇzstv´ı jednou cestou. (i) Tok f je nyn´ı nez´ aporn´ y vektor indexovan´ y hr´ aˇci a cestami fp oznaˇcuje objem dopravy hr´ aˇce i, po cestˇe p. Tok je pˇr´ıpustn´ y pokud ∀i : fp(i) = ri pro pr´ avˇe jednu cestu = 0 pro ostatn´ı cesty Definice 28 (Atomick´a rovnov´aˇzn´ a strategie). Necht’ f je pˇr´ıpustn´ y tok pro atomick´ y model (G, r, c) pak tok je rovnov´ aˇzn´ y pokud pro kaˇzd´eho hr´ aˇce i ∈ {1, . . . , k} a kaˇzdou dvojici p, p¯ ∈ Pi (i) (fp > 0) plat´ı cp (f ) ≤ cp¯(f¯), (i) kde f¯ je stejn´ y jako f aˇz na f¯Pi = 0, f¯p¯ = ri

Pˇ r´ıklad 31 (AAE–model). Mˇejme n´ asleduj´ıc´ı diagram: 

t2 , t3 , s 4

Kaˇzd´ y ze ˇctyˇr hr´ aˇc˚ u m´ a k dispozici jednu jednotku a dvˇe strategie: i) pˇres jednu hranu grafu,

 J ii) pˇres dvˇe hrany grafu. ]J J  J



xJ J x

Optim´ aln´ı strategie je, ˇze vˇsichni jedou pˇres jednu hranu a hodnota 0 x J J toku je 4, toto je tak´e rovnov´ aˇzn´ a, druh´ a rovnov´ aˇzn´ a je,

J J ˇze vˇsichni jedou pˇres dvˇe hrany, hodnota toku je pak 10. ^ J 

x   -J M´ıra anarchie je tu 2.5 v u    0 t1 , s 3 , t4 s1 , s2 w

Vˇ eta 8. Necht’ (G, r, c) je neatomick´ y model 1. Model pˇripouˇst´ı minim´ alnˇe jednu rovnov´ aˇzn´ y tok 2. Pokud f f¯ jsou rovnov´ aˇzn´e toky pak ce (fe ) = ce (f¯e ) pro kaˇzd´e e. Vˇ eta 9. Necht’ (G, r, c) je atomick´ y model ve kter´em plat´ı alespoˇ n jedna z sleduj´ıc´ıch vlastnost´ı: 1. kaˇzd´ y objem dopravy je roven stejn´emu ˇc´ıslu, tj. ri = r ∈ R+ 2. c je line´ arn´ı funkce pak (G, r, c) pˇripouˇst´ı alespoˇ n jeden rovnov´ aˇzn´ y tok. 40

Reference [CHK] Michal Chobot, Akku´l Turnovcov´a, Metody rozhodovania v konfliktn´ ych situ´ aci´ ach a za neurˇcitosti, Alfa, Bratislava, 1980 [K] J. McKinsey, Introduction to the Theory of Games, The Rand series, Stanford university, 1952 [H] Magdalena Hykˇsov´a, Teorie her a optim´ aln´ı (http://euler.fd.cvut.cz/predmety/teorie her/)

rozhodov´an´ı,

online

texty

[GGF] Julio Gonz´ alez-D´ıaz, Ignacio Garc´ıa-Jurado, M. Gloria Fiestras-Janeiro, An Introductory Course on Mathematical Game Theory, AMS Graduate Studies in Mathematics, vol. 114 (2010) [ERTV] Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani, Algorithmic Game Theory, pp. 776 pages, Cambridge University Press (2007)

41