UNIVERZITA PALACKÉHO V OLOMOUCI PŘÍRODOVĚDECKÁ FAKULTA KATEDRA MATEMATICKÉ ANALÝZY A APLIKACÍ MATEMATIKY
DIPLOMOVÁ PRÁCE Teorie nekonečných her
Vedoucí diplomové práce: doc. Mgr. Karel Pastor, Ph.D Rok odevzdání: 2012
Vypracoval: Petr Sušovský AME, II. ročník
Prohlášení Prohlašuji, že jsem vytvořil tuto diplomovou práci samostatně pod vedením doc. Mgr. Karla Pastora, Ph.D. a že jsem v seznamu použité literatury uvedl všechny zdroje použité při zpracování práce.
V Olomouci dne 29. 3. 2012
Poděkování Rád bych na tomto místě poděkoval svému vedoucímu diplomové práce doc. Mgr. Karlu Pastorovi, Ph.D. za obětavou spolupráci i za čas, který mi věnoval při konzultacích. Také bych rád poděkoval své rodině a přátelům za podporu během studia.
Obsah 1 Úvod
4
2 Konečné hry
5
3 Nekonečné hry 3.1 Úvodní pojmy . . . . . . . . . . . . . . . . . . . . . . 3.2 Optimální strategie . . . . . . . . . . . . . . . . . . . 3.3 Skupiny nekonečných her . . . . . . . . . . . . . . . . 3.3.1 Nekonečné hry definované na jednotce čtverce 4 Hry načasování 4.1 Hry načasování jedné akce pro 4.1.1 Hlučný souboj . . . . . 4.1.2 Tichý souboj . . . . . 4.1.3 Tichý-hlučný souboj . 4.1.4 Souboj 4 . . . . . . . .
každého hráče . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . .
. . . . .
. . . .
. . . . .
. . . .
. . . . .
. . . .
. . . . .
. . . .
. . . . .
. . . .
. . . . .
. . . .
13 13 14 16 16
. . . . .
22 24 25 29 36 46
5 Nekonečné hry, jejíchž prostory strategií jsou známé prostory funkcí 50 6 Závěr
52
1
Úvod Teorie nekonečných her je přibližně 70 let stará. Základem těchto her byla
studie von Neumanna a Morgensterna, kteří roku 1944 vydali knihu, ve které se zabývali jak hrami konečnými, tak nekonečnými. Samotná studie taktických soubojů začala v roce 1939, kdy ve světě probíhala II. světová válka. O tuto studii se nejvíce zasloužila korporace RAND, která se v té době snažila najít tým matematiků, statistiků, ekonomů a sociálních vědců, aby analyzovali význam a strukturu tzv. „nejistoty válkyÿ. Měli za úkol vytvořit optimální plán pro budoucí fungování ekonomiky své země při útoku a obraně. Právě při této příležitosti vznikla teorie her načasování jako vedlejší produkt studie taktických soubojů. Název „hry načasováníÿ, jakožto třída taktických soubojů, vznikl roku 1950, kdy skupina matematiků rozpoznala široký rozsah jejich možných aplikací. Předložená diplomová nabízí čtenářům stručný náhled do teorie nekonečných her a her načasování a zároveň uvádí i jejich využití na konkrétních příkladech. První kapitola je úvodem do tématu. Druhá kapitola obsahuje úvodní pojmy, které se týkají teorie konečných her. Vysvětlil jsem zde jednotlivé termíny, které byly pro tuto problematiku nezbytné uvést, jako například hra v normálním tvaru, maticová hra, hra s konstantním součtem, optimální strategie a v neposlední řadě jsem také nadefinoval smíšené rozšíření maticových her. Pro lepší pochopení jsem uváděl konkrétní příklady. Kapitola třetí sloužila jako takový přechod konečných her do nekonečných. Jednotlivé pojmy, které byly nadefinované v kapitole první, jsem se snažil rozšířit pro hry nekonečné. Dále jsou uvedeny pojmy, které se týkají pouze nekonečných her. Na závěr této kapitoly jsou stručně uvedeny některé typy těchto her. Čtvrtá kapitola je stěžejním bodem této práce. Zde se zabývám právě hrami načasování. Uvedl jsem zde základní typy těchto her jako je hlučný souboj, tichý souboj a tichý-hlučný souboj. Pro lepší názornost a pochopení je každý souboj doplněn konkrétním okomentovaným příkladem. Doufám, že tato práce pomůže čtenáři orientovat se v oblasti teorie her.
4
2
Konečné hry Všichni se každý den ocitáme v situacích, kdy musíme zvolit vhodný postup,
abychom dospěli k co nejlepšímu výsledku. Jestliže tento výsledek závisí jenom na nás nebo na více dalších vlivech, které můžeme předvídat s určitou pravděpodobností, ale které nejsou vzájemně závislé na rozhodnutí kohokoli jiného, pak je situace poměrné jasná. Když se však do rozhodování vloží ještě nějaká další osoba, můžeme se obrátit k tzv. teorii her. Teorie her vytváří a analyzuje modely situací, ve kterých dochází k interakci alespoň dvou racionálních entit, často s protichůdnými zájmy. Této interakci se pak říká hra a jejími hráči jsou ony entity. Hrou v tomto smyslu může být třeba partie pokeru, studená válka, veřejná aukce nebo jednání nad podmínkami smlouvy. V obecných případech her se uvažuje užitková (výplatní) funkce, která každému možnému výsledku hry přiřadí n-tici reálných čísel vyjadřující užitek pro jednotlivé hráče. Tradičně se kladným číslem vyjadřuje zisk, záporným ztráta. Nyní si úvodní pojmy nadefinujeme na konečném prostoru strategií jednotlivých hráčů. Jednotlivé definice a tvrzení s důkazy uvedené v této kapitole byly převzaty z literatury [5, 6, 7, 8] a jsou ilustrovány vlastními příklady. Definice 2.1. Nechť je dána konečná neprázdná n-prvková množina Q = {1, 2, ..., n}, dále n neprázdných množin S1 , S2 , ..., Sn a n reálných funkcí K1 , K2 , ..., Kn definovaných na kartézském součinu S1 × S2 × ... × Sn . Hrou n hráčů v normálním tvaru budeme rozumět uspořádanou (2n+1)-tici {Q; S1 , S2 , ..., Sn ; K1 (s1 , s2 , ..., sn ), K2 (s1 , s2 , ..., sn ), ..., Kn (s1 , s2 , ..., sn )}.
(1)
Množinu Q nazveme množinou hráčů, množinu Si nazveme prostorem strategií hráče i, prvek si ∈ Si nazveme strategií hráče i a funkci Ki (s1 , s2 , ..., sn ) nazveme výplatní funkcí hráče i. Klíčovým pojmem při analýze her je optimální bod hry. Tento bod je definován jako takový soubor strategií jednotlivých hráčů, že žádný hráč nemůže získat změnou své strategie, pokud ji změní jen on sám. 5
Definice 2.2. n-tice strategií s = (s1 , s2 , ...sn ) se nazývá optimálním bodem hry, jestliže pro každé i ∈ {1, 2, ..., n} a všechna si ∈ Si platí: Ki (s1 , ..., si−1 , si , si+1 , sn ) ≤ Ki (s1 , ..., si−1 , si , si+1 , sn ).
(2)
Strategie si se nazývá optimální strategie hráče i. Optimální strategie jsou strategie, kterými se budou řídit racionální hráči (hráči, kteří chtějí dosáhnout co největšího zisku). Definice 2.3. Hra v normálním tvaru, v níž pro všechna si ∈ Si , i = 1, 2, ..., n, platí n X
Ki (s1 , ..., sn ) = A,
(3)
i=1
kde A je konstanta nezávislá na volbě strategií s1 , ..., sn se nazývá hra s konstantním součtem. Poznámka 2.1. Je-li A=0, jedná se o hru s nulovým součtem - hra s nulovým součtem je taková hra, při které je součet užitků všech n hráčů nulový pro každý možný výsledek hry. To např. u hry dvou hráčů znamená, že co jeden hráč získá, druhý tratí (např. u pokeru). Jestliže součet výplatních funkcí závisí na zvolených strategiích, jedná se o hru s nekonstantním součtem. V definici 2.2. jsme si definovali, jak vypočítat optimální bod hry pro n hráčů. V další části této práce se budeme zabývat hrami se dvěma hráči. Proto si tuto definici uvedeme pro množinu Q = {1, 2} a uvedeme si ji rovněž pro hru s konstantním součtem (resp. nulovým součtem). Definice 2.4. Konečná hra s nulovým součtem dvou hráčů je definována jako {Q = {1, 2}; X = {1, 2, ..., m}; Y = {1, 2, ..., n}; K(i, j) = aij ; i ∈ X, j ∈ Y }, (4) kde
a11 a21 A= ... am1
a12 a22 ... am2 6
... ... ... ...
a1n a2n ... amn
je matice hry. Jak už bylo zmíněno v předchozím textu, cílem takové hry je najít optimální strategie, díky kterým oba dva hráči se snaží maximalizovat svou výhru, resp. minimalizovat svou ztrátu, ve smyslu následující definice. Poznámka 2.2. Pro hru s nulovým součtem platí, že K1 (x, y) = −K2 (x, y) pro všechna x ∈ X, y ∈ Y . Často píšeme, že K1 (x, y) = K(x, y). Definice 2.5. Nechť {Q = {1, 2}; X; Y ; K1 (x, y); K2 (x, y)}
(5)
je hra s konstantním součtem. Optimální strategie hráče 1 je taková strategie x ∈ X, pro kterou existuje strategie y ∈ Y tak, že platí K1 (x, y) ≤ K1 (x, y) ∧ K2 (x, y) ≤ K2 (x, y)
(6)
pro všechna x ∈ X, y ∈ Y . Strategie y ∈ Y se ekvivalentně nazývá optimální strategie hráče 2. Tato definice vychází z definice 2.2. Je-li navíc {Q = {1, 2}; X; Y ; K1 (x, y); K2 (x, y)} hra s nulovým součtem, sloučí se nám nerovnosti do následujícího tvaru: K(x, y) ≤ K(x, y) ≤ K(x, y).
(7)
Věta 2.1. Nechť (5) je hra s konstantním součtem, A 6= 0. Potom x¯, y¯ jsou optimální strategie ve hře (5) tehdy a jen tehdy, jsou-li x¯, y¯ optimální strategie ve hře s nulovým součtem, kde K(x, y) = K1 (x, y) − K2 (x, y). Důkaz:
Nechť x¯, y¯ jsou optimálními strategiemi ve (5). Z první nerovnosti (6)
dostaneme K1 (x, y¯) − K2 (x, y¯) ≤ K1 (¯ x, y¯) − K2 (x, y¯).
7
Protože K − K1 (x, y¯) = K2 (x, y¯) ≥ K2 (¯ x, y¯) = K − K1 (¯ x, y¯) dostáváme z předchozí nerovnosti K1 (x, y¯) − K2 (x, y¯) ≤ K1 (¯ x, y¯) − K2 (¯ x, y¯). což je levá nerovnost v (7) pro K(x, y) = K1 (x, y) − K2 (x, y). Pravou nerovnost v (7) dostaneme zcela obdobně. Nechť obráceně pro x¯, y¯ platí předchozí nerovnost. Tento vztah můžeme přepsat jako K1 (x, y¯) − [K − K1 (x, y¯)] ≤ K1 (¯ x, y¯) − [K − K1 (¯ x, y¯)], odkud dostaneme první nerovnost z (6). Obdobně dostaneme i druhou nerovnost z (6). Tímto je věta dokázána. Nyní si uvedeme konkrétní příklad, jak vypadá hra s nulovým součtem dvou hráčů. Příklad 2.1. Máme hru dvou hráčů (A a B), jejíž výplatní funkce vypadají následovně
4 −6 A −1 5 5 6
−1 9 B 4 −2 −2 −3
Jedná se o hru s konstantním součtem, protože pokud budeme sčítat příslušné výhry z obou matic hráčů při stejných strategiích, budeme dostávat jedno a to samé číslo. V tomto případě získáme vždy 3. Našim úkolem bude najít optimální strategie. Abychom tyto strategie našli, musíme k jejím zjištěním využít vztah (7). Jelikož se jedná o hru s konstantním součtem, převedeme si tuto hru na hru s nulovým součtem tím, že nahradíme jednotlivé matice jednou maticí (buď hráče A nebo B) dle věty 2.1. V našem případě maticí hráče A. Získáme tímto matici
5 −15 −5 7 7 9 8
Nyní využijeme vztah (7) a najdeme optimální strategie. Hledáme číslo, které bude nejmenší v řádku (hráči A zaručí minimální výhru) a zároveň největší v daném sloupci (maximalizuje svou minimální výhru). Je jasné, že tyto dvě podmínky splňuje dvojice strategií (x3 , y1 ). Výhra hráče A bude tudíž 5, kdežto „výhraÿ hráče B bude -2. ♣
Jak už jsme se zmínili dříve, teorie her se snaží nalézt v každé hře optimální bod (ve smyslu definice 2.5), v němž hráči volí takové strategie, že žádný z nich nemá důvod svou strategii změnit za předpokladu, že druhý hráč svou strategii nezmění. Ne vždy ale optimální bod ve smyslu definice 2.5 existuje. Z tohoto důvodu byly zavedeny tzv. smíšené strategie, které udávají, s jakou pravděpodobností mají hráči volit jednotlivé strategie, aby dosáhli co největšího zisku. Na konkrétním příkladě si ukážeme, kdy bude optimální bod dán smíšenými strategiemi. Příklad 2.2. Budeme uvažovat antagonistický konflikt dvou hráčů, kde výplatní funkce obou hráčů budou obsaženy v následující matici
31 13
Abychom našli optimální bod v tzv. ryzích strategiích (řešení hry), musí zde existovat prvek dle definice 2.5, který je nejmenší v řádku a zároveň největší v tom daném sloupci. Z uvedené matice vidíme, že žádný prvek tyto dvě podmínky nesplňuje. Proto budeme řešení hledat ve smíšených strategiích. Tento příklad budeme řešit pomocí tzv. simplexové metody. Poznámka 2.3. Simplexovou metodou se řeší úlohy lineárního programování a je to metoda, která slouží mimo jiné i pro ruční výpočty, protože její algoritmus je jednoduchý a neustále se opakuje. Výpočty se provádějí přes jednotlivé iterace. V jednotlivých krocích se vypočte nové řešení, které je z hlediska maximalizace 9
účelové funkce lepší nebo alespoň stejné než řešení v předchozím kroku. Samotný výpočet se skládá ze dvou části: 1. Nalezení výchozího základního řešení 2. Iterační postup vedoucí k optimalizaci účelové funkce Poznámka 2.4. Podrobnější algoritmus výpočtu simplexové metody je uveden v literatuře [4]. Nyní se vrátíme k řešení předchozího příkladu. Nejdříve si tuto matici přepíšeme do následující tabulky y1 3 1
x1 x2
y2 1 3
Z pohledu 2. hráče nám vznikne tato soustava nerovnice a rovnic 3y1 + y2 ≤ u y1 + 3y2 ≤ u y1 + y2 = 1,
y1 ≥ 0, y2 ≥ 0.
Analogicky z pohledu 1. hráče nám zase vznikne tato soustava rovnic a nerovnic 3x1 + x2 ≥ v x1 + 3x2 ≥ v x1 + x2 = 1,
x1 ≥ 0, x2 ≥ 0.
V dalších krocích je jedno, zda budeme v našem výpočtu používat soustavu 1. nebo 2. hráče. Zvolme si například soustavu 2. hráče. Zavedeme si nové proměnné q1 a q2 , které lze získat takto q1 =
y1 y2 , q2 = . u u
10
Pak platí tato soustava 3q1 + q2 ≤ 1 q1 + 3q2 ≤ 1 1 u q1 + q2 → max q1 + q 2 =
Musíme dostat soustavu rovnic. K tomu dojdeme tak, že do každé nerovnice dodáme další proměnnou. V našem případě tj. e1 a e2 . Další kroky se řeší přes simplexovou metodu a jednotlivé iterace jsou uvedeny v následujících tabulkách 1. Iterace
e1 e2
q1 3 1 -1
q2 1 3 -1*
e1 1 0 0
e2 0 1 0
q1
q2 0 1 0
e1 1 0 0
e2 − 13
1 1 0
2. Iterace
e1 q2
8 3 1 3 − 23 ∗
1 3 1 3
2 3 1 3 1 3
3. Iterace
q1 q2
q1 1 0 0
q2 0 1 0
e1 3 8
− 18 1 4
e2 − 81 3 8 1 4
1 4 1 4 1 2
Vyšel nám vektor (q1 , q2 , e1 , e2 ) = ( 41 , 14 , 0, 0). Tzn., že (y1 , y2 ) = ( 12 , 12 ). 2. hráč bude tudíž hrát první strategii s pravděpodobností
1 2
a druhou strategií s prav-
děpodobností také 12 . Analogicky by se vypočítaly i jednotlivé pravděpodobnosti 1. hráče. ♣ 11
Definice 2.6. Nechť je dána maticová hra (4). Hru dvou hráčů s nulovým součtem jejíž prostory strategií jsou T
(X) = {x = (x1 , ..., xm );
m X
xi = 1; xi ≥ 0},
(8)
yi = 1; yi ≥ 0}
(9)
i=1
T
(Y ) = {y = (y1 , ..., yn );
n X i=1
a výplatní funkce K(x, y) =
m X n X
xi aij yj = xT Ay,
(10)
i=1 j=1
nazveme smíšeným rozšířením maticové hry (4). Věta 2.2. Smíšené rozšíření každé maticové hry má řešení. Důkaz:
Důkaz této věty se provádí přes tzv. simplexovou metodu a je uveden
v literatuře [5]. Poznámka 2.5. Větě 2.2 se taky říká základní věta teorie maticových her. Až doposud jsme se bavili o teorie her s konečným prostorem strategií. Nyní se budeme zabývat prostorem strategií, který bude nekonečný.
12
3
Nekonečné hry
3.1
Úvodní pojmy
V předchozí kapitole jsme si vysvětlili základní pojmy teorie her, kdy prostor strategií obou hráčů byl konečný. Model, který nám zobrazoval daný konflikt, byla maticová hra. V příkladě na simplexovou metodu jsme si ukázali, že i když jsme měli hráče, u kterých byl prostor strategií konečný, museli jsme použít právě simplexovou metodu a tím jsme jako kdyby popisovali nekonečnou hru. Ve světě však neexistují pouze konečné antagonistické konflikty, ale existují i antagonistické konflikty, kde prostor strategií obou hráčů může být nekonečný. Součástí této kapitoly bude zobecnit si tyto pojmy na nekonečném prostoru strategií, kdy budeme brát v úvahu dva hráče, a opět si tyto pojmy aplikujeme na hru s konstantním součtem. Opět jednotlivé definice a tvrzení byla převzata z [3, 5]. Nejdříve se budeme zabývat hrami v normálním tvaru, které stojí na rozhraní mezi hrami maticovými a hrami nekonečnými. Jedná se o hry, kde prostor strategií obou hráčů X a Y jsou nekonečné spočetné množiny. Cílem bude opět najít optimální strategie obou dvou hráčů, aby oba dva maximalizovali svůj zisk (resp. minimalizovali ztrátu). Bude platit, že X = Y = 1, 2, ... . Dále zde bude platit, že optimální strategie budeme hledat spíše ve smíšených strategiích než v ryzích strategiích. Proto si nadefinujeme smíšené rozšíření hry pro tyto množiny. Definice 3.1. Množina všech rozložení pravděpodobností (X) na X je množina všech nekonečných posloupností x = (x1 , x2,... ), pro které platí: ∞ X
xi = 1, xi ≥ 0, i = 1, 2, ... .
(11)
i=1
Analogicky množina všech rozložení pravděpodobností (Y ) na Y je množina všech nekonečných posloupností y = (y1 , y2,... ), pro které platí: ∞ X
yj = 1, yj ≥ 0, j = 1, 2, ... .
j=1
13
(12)
Potom výplatní funkce vypadá: K(x, y) =
∞ X ∞ X
xi aij yj ,
(13)
i=1 j=1
kde aij jsou prvky z matice A, kde ovšem indexy i a i jdou do nekonečna. Poznámka 3.1. Smíšené rozšíření nekonečného antagonistického konfliktu nemusí mít vždy řešení pro hry, kde prostor strategií je nekonečná spočetná množina. Důkaz pro toto tvrzení je uveden v [5]. Že smíšené rozšíření nekonečného antagonistického konfliktu nemusí mít vždy řešení, je patrné z toho, že střední hodnota (13) nebude definována pro všechna x ∈ (X) a y ∈ (Y ). Podrobnější problematika je uvedena v [5].
3.2
Optimální strategie
Na začátek si uvedeme větu, která nám určuje takové postačující podmínky, aby existovaly optimální strategie v nekonečné hře s nulovým součtem. Jenom pro připomenutí, symbolem R budeme značit množinu reálných čísel a symbolem Rk budeme značit k-rozměrný vektorový prostor reálných čísel, kde k = 1, ..., n. Věta 3.1. Budiž {Q = 1, 2; (X), (Y ); K(x, y)} hra v normálním tvaru s nulovým součtem. Nechť (X) ⊆ Rm a (Y ) ⊆ Rn jsou kompaktní konvexní množiny a nechť K(x, y) je spojitá funkce na (X) × (Y ), která je konkávní v x (pro každé y ∈ (Y )) a konvexní v y (pro každé x ∈ (X)). Potom tato hra v normálním tvaru má řešení. Důkaz:
Důkaz této věty je uveden v [5].
Poznámka 3.2. Ze zjištěných poznatků plyne, že věta 2.2 je speciálním případem předchozí věty. Postup pro hledání optimálních strategií je následující: Hráč 1 se snaží nalézt svou minimální výhru přes množinu strategií druhého hráče: min K(x, y), y∈Y
14
(14)
a tuto svou minimální výhru se snaží maximalizovat: max min K(x, y). x∈X y∈Y
(15)
Druhý hráč se chová opačně. Snaží se najít maximální výhru prvního hráče: max K(x, y), x∈X
(16)
a tuto maximální výhru se snaží minimalizovat: min max K(x, y). y∈Y x∈X
(17)
Musíme si však dokázat, že dvojice x, y z věty 2.1. je ta samá, která splňuje vztahy (15) a (17). Proto si nyní uvedeme větu, která nám tuto myšlenku potvrdí. Věta 3.2. Budiž {Q={1,2};X,Y;K(x,y)} hra s nulovým součtem. Nechť existují hodnoty (15) a (17). Potom rovnost min max K(x, y) = max min K(x, y) y∈Y x∈X
x∈X y∈Y
(18)
platí jenom tehdy, jestliže existují optimální strategie x, y vyhovující definičnímu vztahu K(x, y) ≤ K(x, y) ≤ K(x, y),
(19)
pro všechna x ∈ X, y ∈ Y . Společná hodnota (19) je potom rovna ceně hry K(x, y). Důkaz:
Důkaz věty je uveden v [5].
Poznámka 3.3. Postup při řešení nekonečných her je značně složitý, většinou se řeší přes tzv. diferenciální a integrální rovnice. V různých typech těchto her existuje postup, jak stanovit optimální strategie. Tento postup není formální jak u řešení konečných her. Jestliže to je nutné, výpočty mohou být řešeny přes numerické metody. V další podkapitole si uvedeme příklady nekonečných her a nastíníme si postup, jak budou řešeny. 15
3.3
Skupiny nekonečných her
Rozeznáváme několik typů nekonečných her. Prvním typem her, jsou tzv. hry definované na jednotce čtverce (kde se budeme hlavně podrobněji zabývat hrami načasování). V závěru si pak uvedeme další typy. 3.3.1
Nekonečné hry definované na jednotce čtverce
Tento typ her je jeden z nejjednodušších verzí nekonečných her a užívá se zde obdobná definice hry, jako jsme si uváděli v úvodních kapitolách této práce. Definice 3.2. Hra je definována jako trojice {X, Y, K}, kde X a Y jsou prostory strategií hráče 1 a hráče 2, K(ξ, η) je výplatní funkce, která se skládá ze dvou proměnných ξ a η, jejíž hodnoty nabývají hodnot na intervalu < 0, 1 >. Prostory strategií X, Y se skládají z distribučních funkcí x(ξ) a y(η). Výplatní funkce při volbě x hráče 1 a volbě y hráče 2 vypadá takto: Z
1
1
Z
K(x, y) =
K(ξ, η)dx(ξ)dy(η). 0
(20)
0
Více o distribučních funkcí se dozvíme dále v textu. Definice 3.3. Ryzí strategie jsou speciální strategie následujícího tvaru xξ0 (ξ) =
0 ξ < ξ0 , 1 ξ ≥ ξ0 .
(21)
Obecně strategie x(ξ) v X jsou pravděpodobnostním smíšením ryzích strategií. K(x, y) představuje očekávaný výnos hráče 1 pro ryzí strategie ξ a η. Poznámka 3.4. Pro zjednodušení budeme v našem textu používat tento zápis: K(x, η) pro K(x, yη ); K(ξ, y) pro K(xξ , y) a K(ξ, η) pro K(xξ , yη ). Slovní interpretace například pro K(x, η) zní následovně: „K(x, η) je očekávaný výnos hráče 1, jestliže volí strategii x a jestliže hráč 2 volí ryzí strategii yη .ÿ 16
Vztah (19) nám ukazuje, jak máme vypočítat optimální strategie u nekonečných her. Pokud ale hru na jednotkovém čtverci považujeme za speciální případ nekonečné hry, lze u ní také dokázat, že pokud K(x, y) je spojitá, tak k určení optimálních strategií můžeme opět využít vztah (19). Abychom mohli stanovit optimální strategie těchto her, musíme si nejdříve nadefinovat určité pojmy. Definice 3.4. Množina všech bodů, které patří (náleží) nějakému členu posloupnosti {Sn } je sjednocení a množina všech bodů, které náleží všem členům posloupnosti se nazývá průnik. Tyto dvě množiny značíme ∞ [
Sn a
n=1
∞ \
Sn
(22)
n=1
respektivě. Poznámka 3.5. Množina bodů patřících do množiny S1 a zároveň nepatřící do množiny S2 se nazývá rozdíl a značí se S1 − S2 . Definice 3.5. Každá třída S, která je podmnožinou Rk , se nazývá aditivní podmnožina, jestliže splňuje následující podmínky: 1) Rk ∈ S, 2) P okud S1 , ..., Sn ∈ S, potom
∞ [
Sn ∈ S,
n=1
3) P okud S1 , ..., Sn ∈ S, potom S1 − S2 ∈ S. Definice 3.6. Nejmenší třída množin, která obsahuje „obdélníkyÿ v Rk se nazývá třída borelovských množin. Definice 3.7. Nezáporná množinová funkce P je funkce, která je definována na třídě borelovských množin S a splňuje následující podmínky 1) P (S) ≥ 0 ∀S ∈ S, 2) P (
∞ [ n=1
Sn ) =
∞ X
P (Sn ), pokud Sn ∩ Sm = φ, pro n 6= m,
n=1
3) P (S) < ∞, je − li soubor S omezen. 17
Třída všech nezáporných funkcí definovaných na třídě borelovských množin reálných čísel je ekvivalentní s třídou všech rostoucích funkcí (opět definovaných na množině reálných čísel), které jsou spojité zprava. Tato ekvivalence je jednoznačná, pokud ztotožníme dvě rostoucí funkce, které se všude od sebe liší o fixní konstantu. Ekvivalence je zkonstruována následovně. Vezmeme P a libovolnou reálnou hodnotu α tak, že:
F (x, α) =
P {ξ | α < ξ ≤ x} x > α, 0 x = α, − P {ξ | x < ξ ≤ α} x < α.
F (x, α) je rostoucí funkce pro každé α a spojitá zprava. Dále platí, že jestliže α1 < α2 , potom F (x, α1 ) − F (x, α2 ) = P {ξ | α1 < ξ ≤ α2 }. To znamená, že F (x, α1 ) a F (x, α2 ) se liší o konstantu, nezávisle na x. Na druhou stranu můžeme říct, že pokud F (x) bude nějaká rostoucí funkce, která bude spojitá zprava, můžeme definovat P {ξ | a < ξ ≤ b} = F (b) − F (a). Definice 3.8. Jestliže P {ξ | −∞ < ξ ≤ ∞} = 1, pak se množinová funkce nazývá pravděpodobností mírou. Definice 3.9. Pokud platí, že F (−∞) = 0 a F (∞) = 1, nazývá se funkce F distribuční. Definice 3.10. Ryzí strategii ξ se říká základní, jestliže existuje optimální strategie x, v jejímž spektru leží ξ. Definice 3.11. Pro jakoukoliv distribuční funkci f na reálné ose je spektrum (nosič) definován jako doplněk největší otevřené množiny, ve které se funkce f nevyskytuje.
18
Definice 3.12. Strategie x je strategie konečného typu, jestliže x je konečnou konvexní kombinací ryzích strategií, tzn. že spektrum x se skládá z konečného počtu bodů a x se reprezentuje jako x=
n X
λi xξi ,
λi > 0,
i=1
n X
λi = 1.
(23)
i=1
Ryzím strategiím ξ1 , ξ2 , ..., ξn , které jsou obsažené v x, se říká základní s váhami λ1 , λ2 , ..., λn . Poznámka 3.6. Z předchozí definice je patrné, že konečné strategie jsou ovlivněny jednak volbou jediné hodnoty j z 1 do n dle svých pravděpodobností λj (j = 1, ..., m) a jednak volbou ryzí strategie ξj . Věta 3.3. Nechť x0 a y0 jsou optimální strategie a η0 je obsaženo v nosiči y0 , potom K(x0 , η0 ) = v, kde v je cena hry. Důkaz:
Víme, že v = K(x0 , y0 ) je cena hry a že funkce K(ξ, η) je spojitá.
Protože x0 je optimální, tak platí, že K(x0 , η) ≥ v pro 0 ≤ η ≤ 1. Budeme předpokládat, že K(x0 , η0 ) je ostře větší než v, tudíž nerovnost bude platit pro interval okolo η0 . Dále platí, že η0 je obsažena v nosiči y0 , což znamená, že i příslušný interval bude kladný pro y0 míru. Proto pokud budeme integrovat funkci K(x0 , η) vzhledem k dy0 , dostaneme že K(x0 , y0 ) > v, což je ve sporu s tím, že y0 je optimální. Definice 3.13. Strategie x˜ se nazývá ekvalizér, jestliže K(˜ x, η) = c, pro 0 ≤ η ≤ 1 a pro nějakou konstantu c. Důsledek 3.1. Jestliže x0 je zcela smíšená optimální strategie, potom každá optimální strategie pro hráče 2 je ekvalizér strategie. Důsledek 3.2. Jestliže každé ξ v jednotkovém intervalu je základní pro hráče 1, potom každá optimální strategie pro hráče 2 je ekvalizér. Poznámka 3.7. Hra s výplatní funkcí K(ξ, η) je symetrická, jestliže K(η, ξ) = −K(ξ, η). 19
Definice 3.14. Dvojice ryzích strategií {ξ 0 , η 0 } je sedlový bod pro hru, jestliže K(ξ 0 , η) ≥ K(ξ 0 , η 0 ) ≥ K(ξ, η 0 ),
pro
0 ≤ ξ, η ≤ 1.
(24)
Nyní si ukážeme konkrétní příklady nekonečných definovaných na jednotce čtverce. Zvonovité hry Představme si válku, kde se ponorka S snaží uniknout ponorným bombám, které jsou zhazovány z letadla A. Ponorka se nachází v moři, jejíž polohu lze najít v intervalu −a ≤ η ≤ a, kde a je fixní konstanta. Letadlo A si je vědomo různých poloh, kde by se daná ponorka mohla nacházet. Jestliže poloha ponorky bude (η) a letadlo shodí bombu v poloze (ξ), můžeme předpokládat, že škody, které 2
jsou napáchané, jsou proporční tzv. chybové (škodové) funkce: e−b(ξ−η) . Platí, že výplatní funkce je tvaru: 2
K(ξ, η) = e−λ(ξ−η) , kde λ je parametr závislý na konstantách a, b. Jedná se o tzv. zvonovité hry, jestliže jádro K(ξ, η) = φ(ξ − η), kde φ má následující vlastnosti:
1. φ(u) je analytická funkce definovaná pro všechna reálná u, 2. pro každé n a pro každý soubor hodnot ξi a ηj , takové že: ξ1 ≤ ξ2 ≤ ... ≤ ξn a η1 ≤, η2 ≤ ... ≤ ηn je determinant matice kφ(ξi − ηj )k kladný, 3.
+∞ R
φ(u)du < ∞.
−∞
Pokud jsou splněny následující podmínky, existují optimální strategie . V tomto 2
případě φ(u) = e−λu mohou být tyto optimální strategie počítány rekursivně s proměnnou λ. Další postup řešení je uveden v literatuře [3]. Více informací o nekonečných hrách se lze dočíst v literatuře [1, 3, 5]. Dalším typem nekonečných her definovaných na jednotce čtverce jsou hry načasování. 20
Protože tato problematika bude tvořit podstatnou část diplomové práce, rozhodl jsem se ji uvést samostatně do 4. kapitoly. Jednotlivé modely, definice a tvrzení následující kapitoly jsou převzaty z literatury [3] a jsou doplněny vlastními ilustrativními příklady. Dále je ještě nutné podotknout, že podstatnou část následující kapitoly tvoří různá odvozování. Výsledky těchto odvozování jsou uvedeny v literatuře [3], samotný postup odvození ale ne.
21
4
Hry načasování Hry načasování jsou hry, ve kterých výběr ryzích strategií reprezentují volby
doby k provedení určité akce. Předpokládejme, že máme dvě velké zásilkové společnosti obchodující se zbožím. Obě dvě hodlají vydat své roční katalogy, kde zveřejní nabídku nového zboží. Než daný katalog zveřejní, musí si tyto společnosti dobře uvědomit, kdy nastane ta nejvhodnější doba pro jejich vydání. Ta společnost, která katalog uvede dříve, může mít oproti konkurentovi velkou výhodu, neboť si potencionální zákazník nejdříve přečte její nabídku nového zboží a na základě toho se může rozhodnout o koupi zboží právě z její nabídky. Na druhou stranu může nastat situace, že konkurent bude schválně vyčkávat, až první společnost vydá svůj katalog, aby mohl později využít jeho slabin. Jako druhý příklad se může vyskytnou v oblasti politiky, kdy budeme mít dvě politické strany s různými názory a cíly, a to těsně před volbami. Každá politická strana se snaží získat co nejvíce příznivců, kteří ji budou volit. Aby veřejnost přesvědčily o svých záměrech a cílech, budou muset v rámci kampaně posílat letáky se svým politickým programem. Opět zde vzniká otázka, kdy zahájit danou kampaň. Na některé lidi jejich letáková kampaň nemusí zapůsobit z toho důvodu, protože jsou již dávno přesvědčeni o tom koho volit. Ale ostatní, což může být většina, se rozhodnou právě až na základě zveřejněného politického programu. V takovém případě může opět rozhodovat doba začátku letákové kampaně. Jako poslední příklad her načasování si uvedeme ze světa cestování. Představme si dvě cestovní agentury, které připravují zájezd pro vysoce postavené osoby ve společnosti (např. se může jednat o majitele několika významných firem v zemi). Ta agentura, která poskytne zájezd dané osobě, si zajistí finanční odměnu, jeho přízeň a možnost doporučení jeho obchodních partnerů. Majitel firem se může rozhodnout na základě kvality daného zájezdu, ale rovněž může záležet na době, kdy mu rychlejší cestovní společnost daný zájezd nabídne. Pokud první agentura bude ihned zareaguje a druhá bude vyčkávat, může se stát, že se majitel firem rozhodne podle nabídky první společnosti. Na druhou stranu, příliš rychlá 22
nabídka, může vypadat uspěchaně a nekvalitně. Z matematického hlediska jsou hry načasování popsány jako hry definované na jednotkovém čtverci a jejich výplatní funkce splňuje tři požadavky a to: 1. L(ξ, η) pro ξ < η, pro ξ = η, K(ξ, η) = φ(ξ) M (ξ, η) pro ξ > η.
(25)
2. Dále platí, že každá z funkcí L(ξ, η) a M (ξ, η) jsou spojité v proměnných ξ a η. 3. L(ξ, η) je neklesající funkce v ξ pro každé η, M (ξ, η) je neklesající funkce v ξ pro každé η, L(ξ, η) je nerostoucí funkce v η pro každé ξ, M (ξ, η) je nerostoucí funkce v η pro každé ξ.
Proměnné ξ a η označují dobu obou soupeřů, kdy propukne akce - například, kdy proběhne volební kampaň. Monotónnost funkcí L(ξ, η) a M (ξ, η) a nespojitost výplatní funkce, když ξ = η, se může vysvětlit takto: Jestliže hráč 2 provede akci v pevném (fixním) čase η, hráč 1 si zvyšuje svou šanci na úspěch tím, že čeká tak dlouho, jak to jde, za předpokladu, že hráč 1 jedná před tím než hráč 2. Pokud hráč 1 jedná až poté, co začne jednat hráč 2, může ztratit, pokud hráč 2 bude úspěšný; odsud vyplývá nespojitost v ξ = η. Jakmile hráč 2 jednal, tak potom postupem času se šance na úspěch hráče 1 zvyšují; to je vyjádřeno monotónní funkci M (ξ, η) jako funkci ξ. Obdobné prohlášení platí i pro hráče 2, protože výhody 1. hráče způsobují nevýhody 2. hráče. Existují 2 skupiny her načasování: 1. První skupinou se nazývají hry s kompletními informacemi, kdy funkce L(ξ, η) je funkci pouze ξ a M (ξ, η) je funkci pouze η. Myšlenku kompletních informací je třeba chápat v tom smyslu, že když hráč 1 začne, jeho 23
akce a následky jsou soupeři známy. Jedná se například o konkurenci dvou cestovních kanceláří, která byla popsána v úvodu (vědělo se, že mohou přijít o odměnu). 2. Druhá skupina se skládá ze všech her načasování mimo třídu 1. Jedná se o hry, ve kterých L(ξ, η) nebo M (ξ, η) nebo obě explicitně závisí na obou proměnných ξ a η. V těchto hrách platí pravidlo, že oba soupeři navzájem neznají dobu akce a její následky. Optimální strategie zde zahrnují skutečnou náhodnost ryzích strategií. V dalších kapitolách narazíme na hry jak s kompletními informacemi, tak i hry s nekompletními informacemi.
4.1
Hry načasování jedné akce pro každého hráče
Hry načasování jedné akce pro každého hráče, jak už bylo zmíněno v předchozí kapitole, jsou důležitou třídou her, které jsou definovány na jednotkovém čtverci. Už ze samotného názvu poznáme, že se bude jednat o duely, při kterých oba hráči budou mít pouze jednu možnost pro provedení své akce. Hodnoty 0 ≤ ξ ≤ 1 pro hráče 1 a 0 ≤ η ≤ 1 pro hráče 2 představují možné časy, během kterých mohou být provedeny určité akce (doba výstřelu, podpis smlouvy, atd.). Pro lehké nastínění této problematiky si můžeme představit následující ideální model. Máme dvě nepřátelské osoby, které budou mít k dispozici jednu jednotku palebné síly. To znamená, že každý hráč má jednu možnost zasáhnout svého protihráče, s vědomím, že jeho přesnost - tzn. jeho šance na úspěšnou střelbu se zvyšuje s časem. Ve hře tohoto typu záleží úspěch hlavně na pořadí, ve kterém hráči hrají a na jejich příslušném stupni úspěchu. Každý hráč si zjevně přeje odložit akci na tak dlouho jak je to možné, aby zvýšil svou možnost úspěchu, ale zároveň si nepřeje opozdit se na tak dlouho, že ho jeho soupeř může předejít s efektivností. Optimální strategie zde vyjadřují správnou rovnováhu mezi touhou po zpoždění a nebezpečím prodlevy. Četné verze válečných her načasování mohou být vyjádřeny z hlediska toho, jaké informace má hráč o činnosti svého protihráče. V úvodu jsme zmínili, že se 24
jedná o hru definovanou na jednotkovém čtverci, proto i tato hra bude spojena s výplatní funkcí K(ξ, η), která musí opět splňovat nám už známé tři vlastnosti, které jsou uvedeny v souvislosti se vztahem (25). Nyní si ukážeme několik typů her načasování, které mohou nastat. 4.1.1
Hlučný souboj
Tento souboj je charakterizován tím, že oběma dvěma protihráčům je dovoleno vystřelit pouze jednou (nutná podmínka), a navíc budeme předpokládat, že mají tzv. hlučné zbraně. Jinými slovy to znamená, že oba dva soupeři ví, jestli už protihráč vystřelil nebo ne. Termín „hlučnýÿ bude obecně používán k označení stavu kompletní informace, tzn. situace, kdy každý hráč ví, kdy ostatní hrají. Předpokládá se, že funkce přesnosti P1 (ξ) (pravděpodobnost úspěchu) pro hráče 1 je spojitá a neklesající v ξ, s P1 (0) = 0 a P1 (1) = 1. Přesnost hráče 2 je popsána podobně, jedná se zde opět o spojitou neklesající funkci P2 (η), s hodnotami P2 (0) = 0 a P2 (1) = 1. Jestliže hráč 1 zasáhne hráče 2, předpokládá se, že hodnota výhry pro hráče 1 bude +1, jestli tomu bude naopak, bude jeho hodnota opačná (-1). Výplatní funkce K(ξ, η) bude očekávaná hodnota pro hráče 1, když oba dva hráči použijí ryzí strategie ξ a η. Jestliže ξ < η, pravděpodobnost hráče 1 že zasáhne hráče 2 je P1 (ξ) a hodnota bude 1 ∗ P1 (ξ). Naopak když mine, bude to znamenat pravděpodobnost s hodnotou 1 − P1 (ξ). Skutečnost, že obě dvě zbraně jsou hlučné, nám ovlivní strukturu výplatní funkce. Můžou zde nastat některé situace, které mohou šance na úspěch ještě zvýšit. Například, když hráč 2 ještě nevystřelí, ale ví, že hráč 1 už nemůže vystřelit znovu, může zvýšit své šance na úspěch čekáním. Dokud η = 1. Proto, jestliže hráč 1 mine v ξ, je si jistý tím, že bude zasažen hráčem 2, pokud ξ < η. Tyto základní poznatky si můžeme shrnout do následujícího vztahu: L(ξ, η) = P1 (ξ) + (−1)[1 − P1 (ξ)]
(ξ < η).
Obdobně platí M (ξ, η) = P2 (η)(−1) + [1 − P2 (η)](1) 25
(ξ > η)
a φ(ξ) = P1 (ξ)[1 − P2 (ξ)](1) + P2 (ξ)[1 − P1 (ξ)](−1)
(ξ = η).
V posledním vzorci se předpokládá, že oba protihráči vypálí zároveň úspěšně nebo neúspěšně, popř. jeden z nich se trefí a druhý ne. Hodnota je tudíž 0. Předchozí vztahy si můžeme zjednodušit a vyjádříme si je jako: pro ξ < η, 2P1 (ξ) − 1 K(ξ, η) = P1 (ξ) − P2 (ξ) pro ξ = η, 1 − 2P2 (η) pro ξ > η.
(26)
Výplatní funkce K(ξ, η) nám určuje hru načasování třídy 1 (hlučný souboj). Z (26) lze usoudit, že hodnota u η = ξ je průměr hodnot dosažených funkcemi L a M. Nyní si tuto problematiku ukážeme na konkrétním příkladě. Příklad 4.1. Máme obchodníka s nemovitostmi, který nyní prodává luxusní vilu. Tuto vilu chce nutně prodat, poněvadž nemá peníze a na jeho zbylý majetek mu hrozí exekuce. O tuto vilu projevili zájem dva zahraniční magnáti. Obchodník si oba dva magnáty pozve do této vily a poskytne jim určitý čas na prohlídku budovy. Oba magnáti (dále hráči) mohou během této doby učinit nabídku ke koupi tohoto objektu. Pokud nastane situace, že některý z hráčů vysloví nabídku ke koupi vily, ale samotný prodej se nevydaří, nemá již daný hráč nárok svou nabídku opakovat. V tomto případě se o neúspěchu prvního hráče dozví hráč druhý, který z logického hlediska se svou nabídkou počká až uplyne určená doba na prohlídku objektu. Vzniká zde otázka, v jakém časovém okamžiku bude nejlepší vyslovit nabídku na tuto koupi. Samotné řešení příkladů spočívá v některých předpokladech. Zájem o prodej jednotlivým hráčům bude zde popsán pro každého hráče neklesajícími funkcemi. Pro hráče 1 to bude funkce P1 (ξ) a pro hráče 2 to bude funkce P2 (η). Obě dvě tyto funkce popisují pravděpodobnost prodeje vily určitému hráči v určitém čase - pro hráče 1 je okamžik prodeje popsán proměnnou ξ, pro hráče 2 η. Dále ze zadání vyplývá, že funkce P1 (ξ) a P2 (η) jsou definovány na intervalu h0, 1i a to z 26
takového důvodu, že v čase 0 začíná prohlídka vily a v čase 1 končí prohlídka. Z toho důvodu zde platí P1 (0) = P2 (0) = 0 a P1 (1) = P2 (1) = 1. Už ze samotného zadání je patrné, že se jedná o tzv. „hlučný soubojÿ. Jelikož se pohybujeme časově na intervalu h0, 1i, jsou prostory strategií jednotlivých hráčů definovány jako množiny G = {ξ; ξ ∈ h0, 1i}, H = {η; η ∈ h0, 1i}.
(27)
Mohou zde nastat 3 případy situací: 1. Pro časový okamžik ξ < η to znamená, že hráč 1 uskutečnil nabídku dříve než hráč 2. 2. Pro časový okamžik ξ = η to znamená, že oba dva hráči uskuteční nabídku ve stejný čas. 3. Pro časový okamžik ξ > η to znamená, že hráč 2 uskutečnil nabídku dříve než hráč 1. Víme, že výplatní funkce má chování náhodné veličiny, tudíž bude střední hodnota závislá na proměnných ξ a η. Jedná se o hru s prostory strategií (27) a s výplatními funkcemi (26). Pro tuto hru platí, že má řešení v ryzích strategií a navíc pro optimální strategie platí: ξ0 = η0 = z.
(28)
Hodnotu z jsme schopni vypočítat z rovnice: P1 (z) + P2 (z) = 1.
(29)
Jinými slovy platí, že optimální by bylo, kdyby oba dva magnáti vyslovili svou nabídku ke koupi současně. Hodnota z v tomto případě reprezentuje „určitý čas prohlídky budovyÿ a cena hry má tudíž tvar P1 (z) − P2 (z). Abychom mohli říci, že vztahy (28) a (29) splňují podmínku optimálních strategií, čili musíme dokázat, že platí: K(ξ, z) ≤ P1 (z) − P2 (z) ≤ K(z, η). 27
(30)
Tento vztah musí platit pro všechna ξ a η, kde ξ ∈ h0, 1i a η ∈ h0, 1i. V této práci si ověříme pravou nerovnost, protože obě dvě nerovnosti se dokazují analogicky a navíc, důkaz na levou nerovnost je uveden v literatuře [5]. Abychom správně ověřili pravou nerovnost, musíme nejdříve rozlišit tři případy, které mohou nastat pro proměnnou z 1. Pro z < η platí, že K(z, η) = 2P1 (z)−1. Po využití vztahu (26) lze následně upravovat: P1 (z) − P2 (z) ≤ 2P1 (z) − 1 P1 (z) − P2 (z) ≤ −P1 (z) − P2 (z) + 2P1 (z) P1 (z) − P2 (z) ≤ P1 (z) − P2 (z). Zde jsme si dokázali, že pravá nerovnost (30) platí jako rovnost. 2. Když z = ξ, pak je zřejmé, že i v tomto případě nerovnost platí jako rovnost: P1 (z) − P2 (z) ≤ P1 (z) − P2 (z). 3. Pro z > η platí, že K(z, η) = 1 − 2P2 (η). Opět využijeme vztah (26) a dostaneme: P1 (z) − P2 (z) ≤ 1 − 2P2 (η) P1 (z) − P2 (z) ≤ P1 (z) + P2 (z) − 2P2 (η) −2P2 (z) ≤ −2P2 (η) P2 (z) ≥ P2 (η). I pro tento případ nerovnost platí, protože v zadání jsme si uváděli několik předpokladů a mezi ně patřilo např. to, že funkce P2 (η) je neklesající. Zkusíme si vypočítat řešení pro konkrétní funkce P1 (ξ) a P2 (η). Nechť P1 (ξ) = ξ 2
pro ξ ∈ h0, 1i,
P2 (η) = η 2
pro η ∈ h0, 1i. 28
Pokud tyto funkce dosadíme do (29), vyjde nám, že z =
q
1 2
. = 0, 71. Znamená to,
že nejoptimálnější bude pro oba dva magnáty, aby svou nabídku řekli současně. A to v době, jakmile uplyne 0, 71 času od zahájení prohlídky. Myslí se to tak, že pokud budou mít na prohlídku vily jednu hodinu, měli by se ozvat, jakmile uplyne 43 minut (0, 71 ∗ 60). ♣ 4.1.2
Tichý souboj
U tohoto souboje je opět hráčům dovoleno vystřelit pouze jednou. Je zde ovšem změna a to taková, že obě dvě zbraně jsou vybaveny tlumiči. Čili žádný soupeř nemůže určit, zda jeho protihráč vypálil nebo ne. Předpokládejme situaci, že přesnost (pravděpodobnost úspěchu) je dána P1 (ξ) = P2 (ξ) = ξ, tudíž výplatní funkce je popsána následovně: ξ − (1 − ξ)η K(ξ, η) = 0 ξ(1 − η) − η
pro ξ < η, pro ξ = η, pro ξ > η.
(31)
Odvozování této výplatní funkce je podobné jako u předchozího hlučného souboje. Nejdříve budeme brát situaci, že hráč 1 vystřelil dříve než hráč 2 (ξ < η). Pokud hráč 1 zasáhne hráče 2, hodnota jeho výhry bude 1. Výplatní funkce K(ξ, η) bude očekávaná hodnota výhry hráče 1 a opět bude mít charakter náhodné veličiny. Střední hodnota tudíž bude ξ − (1 − ξ)η. Opačná situace nastane, pokud hráč 1 vystřelí později než hráč 2 (η < ξ). Pokud hráč 2 zasáhne hráče 1, hodnota jeho výhry bude 1. Výplatní funkce K(ξ, η) bude mít opět charakter náhodné veličiny a střední hodnota bude ξ(1 − η) − η. Pokud se stane, že oba dva hráči vystřelí najednou (ξ = η), mohou nastat 4 situace. Buď se oba dva trefí nebo minou, nebo jeden z nich se trefí a druhý mine. V tomto případě očekávaná hodnota výhry bude vždy 0. Výplatní funkce tohoto tichého souboje má jednu důležitou vlastnost a to takovou, že zde platí: K(ξ, η) = −K(η, ξ). Jinými slovy to znamená, že tichý 29
souboj (když P1 (ξ) = P2 (ξ) = ξ) je hra symetrická. Hodnota hry je proto 0 a jakákoliv strategie, která je optimální pro jednoho hráče, tak je optimální i pro hráče druhého. Tichý souboj patří mezi hry načasování druhé třídy (funkce L(ξ, η) a M (ξ, η) závisí na obou proměnných ξ a η). Její forma je stejná jako v případě (25), kde L(ξ, η) = ξ − η + ξη,
M (ξ, η) = ξ − η − ξη,
dále pro jednotlivá ξ a η platí Lξ (ξ, η) Lη (ξ, η) 0 ≤ ξ, η < 1 = M ξ (ξ, η) Mη (ξ, η)
= = = =
1 + η > 0, −1 + ξ < 0, 1 − η > 0, −1 − ξ < 0.
Funkce Lξ a Mξ označují parciální derivaci podle ξ; Lη a Mη mají podobný význam. Z toho důvodu jsou funkce L(ξ, η), M (ξ, η) rostoucí v ξ a klesající v η na jednotce intervalu h0, 1i. Protože oba dva hráči neví, kdy soupeř provede danou akci, může každý z nich čekat na úspěch plný časový interval. A proto, rozumný první odhad má optimální strategii tvořenou hustotou na intervalu ha; 1i (případně v bodě 1).
Ukážeme si následující možný příklad z praxe a uvedeme jeho řešení. Příklad 4.2. V České republice se na dvoudenním veletrhu objevil nový typ mobilního telefonu, o který projevili zájem dva zákazníci (1) a (2). Česká firma, která tento telefon vyrobila, se bude snažit tento produkt během těchto dvou dnů prodat. Firma není nijak zaujatá vůči zahraničí, proto je jí jedno, zda prodá tento telefon právě tam nebo do tuzemska. O jednotlivých zákaznících víme, že zákazník (1) je z tuzemska a zákazník (2) je ze zahraničí. Oba dva zákazníci mají dva dny na to, aby učinili nabídku. Opět zde může nastat situace, při které když daný zákazník učiní nabídku a ta se z nějakého důvodu nevydaří, ztrácí tímto nárok na opětovné učinění další nabídky. Protože daný telefon vyrobila firma, které je 30
jedno, kdo bude kupcem, nebude mít žádný zákazník výhodu. Aby jednotlivé nabídky probíhaly v anonymitě, rozhodla se tato firma, že pokud nějaký zákazník vysloví nabídku dříve, druhá strana se nic nedozví. Vzniká zde otázka, kdy oba dva zákazníci mají učinit nabídku, aby jejich šance na koupi tohoto telefonu byla co největší. Nyní si ukážeme postup, jak lze najít optimální strategie tohoto souboje:
Budeme hledat optimální strategie, které jsou v následujících tvarech: Z
0
ξ
Z
0
f (t)dt, y (η) =
x (ξ) = a
η
g(t)dt. a
Požadavek konstantního výnosu v může být splněn pouze v intervalu ha; 1i. Věta 3.2. nám udává podmínku pro optimalitu a tudíž podle této věty platí Z
1
Z
0
K(ξ, η)dx (ξ) =
K(ξ, η)f (ξ)dξ = v = 0
(32)
a
pro všechna η ∈ ha; 1i. Z důvodu symetričnosti, je konstantní výnos roven 0.
Pokud si funkci K(ξ, η) vyjádříme v explicitním tvaru (využijeme vztah (31)), bude předcházející rovnice vypadat následovně Z
η
1
Z (ξ − η + ξη)f (ξ)dξ +
(ξ − η − ξη)f (ξ)dξ ≡ 0.
a
(33)
η
Platí vztah Z
1
f (ξ)dξ = 1.
(34)
a
Při využití předchozího vztahu, můžeme vztah (33) přepsat následovně Z
1
Z
Z ξf (ξ)dξ − η
ξf (ξ)dξ + η a
η
a
Z ξf (ξ)dξ − η
η
31
1
1
f (ξ)dξ ≡ 0 a
Z
1
η
Z ξf (ξ)dξ − η + η
Z
1
ξf (ξ)dξ − η
a
ξf (ξ)dξ ≡ 0.
a
(35)
η
Abychom mohli dále upravit danou integrální rovnici na diferenciální rovnici, bylo by dobré si uvést 2 věty, dle kterých budeme postupovat. Jedná se o věty, které nám říkají, jak derivovat integrál jako funkci horní meze. Věta 4.1. Nechť a < b, existuje
Rb a
f (t)dt a nechť c je libovolné číslo z intervalu
ha; bi. Potom platí tato tvrzení: Rx 1) Funkce c f (t)dt je spojitá v intervalu ha, bi. 2) Je-li a < x < b a je-li funkce f (t) spojitá v bodě x, existuje v tomto bodě derivace d dx Důkaz:
x
Z
f (t)dt = f (x).
(36)
c
Důkaz této věty je uveden v [2].
Věta 4.2. Nechť a < b, existuje
Rb a
f (t)dt a nechť c je libovolné číslo z intervalu
ha; bi. Potom platí tato tvrzení: Rc 1) Funkce x f (t)dt je spojitá v intervalu ha, bi. 2) Je-li a < x < b a je-li funkce f (t) spojitá v bodě x, existuje v tomto bodě derivace d dx Důkaz:
Z
c
f (t)dt = −f (x).
(37)
x
Důkaz této věty je uveden v [2].
V dalším kroku využijeme předchozí věty a převedeme si integrální rovnici (35) na diferenciální rovnici. Pro zjednodušení použijeme substituci r(ξ) = ξf (ξ). Výpočet je následující: d : dη
η
Z −1+
1
Z r(ξ)dξ + ηr(η) −
a
Z −1 +
r(ξ)dξ + ηr(η) = 0 η
η
Z r(ξ)dξ + 2ηr(η) −
a
r(ξ)dξ = 0. η
32
1
V dalším kroku opět využijeme předchozí věty a budeme derivovat podruhé d : r(η) + 2r(η) + 2ηr0 (η) + r(η) = 0. dη Získáme tak tuto lineární diferenciální rovnici 2ηr0 (η) + 4r(η) = 0.
(38)
Postup výpočtu této rovnice si opět ukážeme 2ηr0 (η) + 4r(η) = 0
/ : 2η
2 r0 (η) + r(η) = 0 η ln|r(η)| = −2ln|η| + ln|k| r(η) = eln|η
−2 |
k
r(η) = kη −2 .
(39)
Získali jsme tudíž obecné řešení. Po dosazení zpět do substituce dostaneme, že f (ξ) = kξ −3 . Pokud dosadíme f (ξ) = kξ −3 do (35), získáme následující rovnici
1 −k 1 − a
1 1 − − η − kη + kη 1 − η a k η −1 + + k + k −3 + a
Tato identita platí pouze tehdy, jestliže a =
1 3
1 η
1 a
≡0 ≡ 0, a ≤ η ≤ 1.
(40)
a k = 14 . Dále musíme ověřit, že
hodnoty a a k splňují omezení (34).
Z
1
f (ξ)dξ = 1 a
k
1 1 − 2 2a 2 33
= 1.
(41)
A po dosazení konkrétních hodnot vidíme, že tato rovnice (popř. toto omezení) platí. Můžeme pak napsat, že hustota optimální strategie x0 vypadá takto f (ξ) =
0 1 −3 ξ 4
0 ≤ ξ < 13 , 1 ≤ ξ ≤ 1, 3
(42)
pokud se prokáže, že 1
Z
K(ξ, η)f (ξ)dξ > 0 a
pro všechna η < a. Tato skutečnost vyplývá ovšem jako důsledek monotónních vlastností výplatní funkce. Skutečně, pro η < a, d dη
Z
1
Z
1
Mη f (ξ)dξ ≤ 0,
K(ξ, η)f (ξ)dξ = a
a
přičemž Z
1
K(ξ, η)f (ξ)dξ a
je spojitý pro všechny η a je nulový v η = a. Proto tvrdíme, že integrál R1 K(ξ, η)f (ξ)dξ je kladný. Jak už bylo zmíněno v úvodu, jedná se o hru symeta rickou, tudíž stejná strategie je optimální i pro hráče 2. ♣ Důležitým ukazatelem hustoty optimální strategie je spektrum. Toto spektrum nám udává, kdy nejdříve propukne daná akce, například, kdy daný hráč vystřelí. Interval spektra se mění v závislosti na pravděpodobnostní funkci úspěchu. Doposud jsme se bavili o situaci, kdy P1 (ξ) = P2 (ξ) = ξ. Nyní si ukážeme ještě dva typy těchto funkcí a zjistíme hodnotu spektra. Protože se jedná o různé typy pravděpodobnostních funkcí úspěchu, bude se každý případ řešit pomocí příslušného modelu, na jehož základě se vytvoří příslušné integrální rovnice Vezmeme případ, kdy P1 (ξ) = P2 (ξ) =
34
ξ . 2−ξ
Příslušné integrální rovnice vy-
padají Z
1
K(ξ, η)f (ξ)dξ ≡ v
(a ≤ η ≤ 1),
K(ξ, η)g(η)dη ≡ v
(a ≤ ξ ≤ 1).
a
Z
1
a
V druhém případě bude platit, že P1 (ξ) = P2 (ξ) = ξ 2 . Příslušné integrální rovnice budou vypadat 1
Z
K(ξ, η)f (ξ)dξ + αK(1, η) ≡ v
(a ≤ η ≤ 1),
K(ξ, η)g(η)dη + βK(ξ, 1) ≡ v
(a ≤ ξ ≤ 1).
a
Z
1
a
Hodnota α resp. β představuje váhu (neboli pravděpodobnost), že hráč 1 resp. hráč 2 bude čekat se svým výstřelem až do konce. Jelikož jsou pravděpodobnostní funkce úspěchu složitější, bude jejich postup řešení daleko obtížnější než doposud, uvedeme si zde jenom výsledky řešení. Danou tabulku jsem použil z [3]. P (ξ) ξ
a
ξ 2−ξ 2
0,414 0,481
ξ
1 3
Nejdříve se musíme přesvědčit, zda dané funkce splňují podmínku a to takovou, že P (0) = 0 a P (1) = 1, což lze jednoduše ověřit, že platí. Dále lze zjistit, že ξ >
ξ 2−ξ
dá říct, že
> ξ 2 pro ∀ξ ∈ (0; 1). Na druhou stranu o jednotlivých spektrech se 1 3
< 0, 414 < 0, 481. Tento fakt si můžeme okomentovat následovně.
Čím je hodnota pravděpodobnostní funkce úspěchu vyšší v určitém časovém okamžiku, tím začíná interval spektra optimální strategie dříve. Znamená to tedy, že čím vyšší pravděpodobnost zásahu v danou dobu u hráče existuje, tím dřívější výstřel můžeme od něho čekat.
35
4.1.3
Tichý-hlučný souboj
Tato situace je kombinace obou dvou předchozích soubojů. Budeme předpokládat, že hráč 1 má tichou zbraň a hráč 2 má zbraň hlučnou. Jinými slovy to znamená, že první hráč ví, kdy druhý hráč vystřelil, ale ne naopak. Tudíž hráč 1 bude ve výhodě. Opět si tuto situaci znázorníme v případě, kdy funkce přesnosti budou P1 (ξ) = P2 (ξ) = ξ. Jak už bylo zmíněno na začátku, že se jedná o kombinaci tichého a hlučného souboje, tak také výplatní funkce bude touto kombinací ovlivněna. Výplatní funkce L(ξ, η) bude reprezentovat tichý souboj a výplatní funkce M (ξ, η) hlučný souboj. Dále zde opět platí ta situace, že pokud oba dva hráči vystřelí najednou, je hodnota výplatní funkce 0. A to v případě zásahu či minutí. Dohromady bude výplatní funkce vypadat následovně ξ − η + ξη K(ξ, η) = 0 1 − 2η
pro ξ < η, pro ξ = η, pro ξ > η.
(43)
Když jsme hledali optimální strategie u tichého souboje, ukázali jsme si určitý postup. Tento postup budeme také aplikovat na hledání optimálních strategií u tohoto souboje. Budeme hledat strategie x0 (ξ), která se skládá z části hustoty f (ξ) na intervalu ha; 1i s váhou α v ξ = 1, a y 0 (η) skládající se z části hustoty g(η) na tom samém intervalu s váhou β v η = 1. Nyní se opět vrátíme k příkladu 4.2 , u kterého pozměníme zadání a tímto ho převedeme do ticho-hlučného souboje. Na závěr si zjištěné informace okomentujeme. Příklad 4.3. V České republice se na dvoudenním veletrhu objevil nový typ mobilního telefonu, o který projevili zájem dva zákazníci (1) a (2). Česká firma, která tento telefon vyrobila, se bude snažit tento produkt během následujících dvou dnů prodat. O jednotlivých zákaznících víme, že zákazník (1) je z tuzemska, kdežto zákazník (2) je ze zahraničí. Oba dva zákazníci mají dva dny na to, aby učinili nabídku. Opět zde může nastat situace, při které když daný zákazník učiní nabídku a ta se z nějakého důvodu nevydaří, ztrácí tímto nárok na opětovné učinění 36
další nabídky. Zákazník z tuzemska má u zahraničního zákazníka špióna. Kvůli němu bude mít zahraniční zákazník vůči tuzemskému handicap spočívající v podstatné věci. Pokud nabídku učiní zákazník z tuzemska, zahraniční zákazník se o ní nedozví, ale pokud nastane opačná situace a to, že nabídku učiní zahraniční zákazník, tuzemský odběratel se tuto informaci vždy od svého špióna dozví. Vzniká zde otázka, v jakou dobu mají oba dva zákazníci učinit nabídku, aby jejich šance na koupi tohoto telefonu byla co největší. Při nalezení optimálních strategií budeme postupovat stejně jako to bylo u tichého souboje.
Postup Nejdříve si opět napíšeme, jak budou vypadat příslušné integrální rovnice. 1
Z
K(ξ, η)f (ξ)dξ + αK(1, η) ≡ v
(a ≤ η ≤ 1),
(44)
K(ξ, η)g(η)dη + βK(ξ, 1) ≡ v
(a ≤ ξ ≤ 1).
(45)
a
Z
1
a
Pokud za K(ξ, η) dosadíme konkrétní výplatní funkce, dostaneme
t
Z
Z
(1 − 2t)f (ξ)dξ + α(1 − 2t) ≡ v
(a ≤ t < 1), (46)
(t − η + tη)g(η)dη + β(2t − 1) ≡ v
(a ≤ t < 1). (47)
(ξ − t + ξt)f (ξ)dξ + a
t
t
Z
1
Z (1 − 2η)g(η)dη +
a
1
t
S využitím vět (4.1) a (4.2) převedeme tyto integrální rovnice na diferenciální rovnice. Protože se jedná o složitější převod než v případě tichého souboje, ukážeme si ještě jednu větu, která nám tento převod usnadní. Věta 4.3. Předpokládejme, že funkce f : P −→ R je spojitá a má spojité parciální derivace
∂f ∂y
na obdélníku P = {(x, y) ∈ R2 ; a ≤ x ≤ b ∧ c ≤ y ≤ d}. Dále
37
předpokládejme, že α(y) a β(y) mají spojitě diferencovatelné funkce na hc, di, jejichž hodnoty leží v ha, bi pro každé y ∈ hc, di, potom integrál Z
β(y)
f (x, y)dx
F (y) = α(y)
je definován pro každé y ∈ hc, di a funkce F (y) je spojitě diferencovatelnou funkcí, přičemž platí 0
0
0
Z
β(y)
F (y) = f (β(y), y)β (y) − f (α(y), y)α (y) + α(y)
Důkaz:
∂f (x, y)dx. ∂y
(48)
Důkaz této věty je uveden v [9].
Nyní převedeme rovnice (46) a (47) pomocí věty 4.3 na rovnice diferenciální. Jednotlivé převody těchto rovnic jsou analogické, proto si zde uvedeme postup pro první rovnici. Rovnici (46) si nachystáme, abychom pak mohli použít větu 4.3. Platí, že
Z
t
Z
1
(ξ − t + ξt)f (ξ)dξ +
F (t) = a
(1 − 2t)f (ξ)dξ + α(1 − 2t) ≡ v. t
Využitím vztahu (48) dostaneme
Z
0
F (t) = [(ξ − t + ξt)f (ξ)]ξ=t +
t
Z (−1 + ξ)f (ξ)dξ − [(1 − 2t)f (ξ)]ξ=t +
a
1
−2f (ξ)dξ t
−2α ≡ 0,
použijeme druhou derivaci dle t a získáme
d : dt
2tf (t) + t2 f 0 (t) + (−1 + t)f (t) − [−2f (t) + (1 − 2t)f 0 (t)] + 2f (t) ≡ 0.
38
Po vytknutí a navrácení se zpět k proměnné ξ dostaneme 3(1 + ξ)f (ξ) + (ξ 2 + 2ξ − 1)f 0 (ξ) = 0.
(49)
Po totožných úpravách vztahu (47) obdržíme (1 − 2η − η 2 )g 0 (η) − 3(1 + η)g(η) = 0.
(50)
Dalším krokem bude opět stanovit obecné řešení těchto diferenciálních rovnic, které nám budou charakterizovat hustoty funkcí pro optimální strategie. Jelikož mají podobnou strukturu, ukážeme postup výpočtu (49). Rovnice je lineární a homogenní.
f 0 (ξ) = −
ξ2
3ξ + 3 f (ξ) + 2ξ − 1
1 3ξ + 3 df (ξ) = − 2 dξ f (ξ) ξ + 2ξ − 1 Z Z 1 3ξ + 3 df (ξ) = − 2 dξ f (ξ) ξ + 2ξ − 1 f (ξ) =
(ξ 2
k1 + 2ξ − 1)3/2
(51)
Vztah (50) se počítá analogicky, a proto si uvedeme pouze výsledek
g(η) =
(η 2
k2 + 2η − 1)3/2
(52)
Abychom mohli zjistit úplné (konečné) řešení, musíme vypočítat neznámé konstanty a, v, α, β, k1 a k2 . Rovnice (46) a (47) nám reprezentují rovnosti pro ξ a η. Nyní si uvedeme 2 integrály, které využijeme v dalším odvozováním.
Z (ξ 2
ξ+1 dξ + 2ξ − 1)3/2 39
Tento integrál řešíme pomocí tzv. substituce ξ 2 + 2ξ − 1 = t2 (2ξ + 2)dξ = 2tdt p t = ξ 2 + 2ξ − 1. Po využití této substituce dostaneme integrál Z 1 dt. t2 Pak po zintegrování a navrácení se k původní proměnné dostaneme, že
Z
1 ξ+1 p dξ = − + c. (ξ 2 + 2ξ − 1)3/2 ξ 2 + 2ξ − 1
(53)
Druhý integrál je o trochu složitější a řeší se přes tři substituce. Opět si ukážeme stručný postup Z
dξ = 2 (ξ + 2ξ − 1)3/2
Z
dξ ((ξ + 1)2 − 2)3/2
Nejdříve si zavedeme první substituci x = ξ+1 dx = dξ, získáme Z (x2
dξ − 2)3/2
a zavedeme si druhou substituci x=
1 t
1 dx = − 2 dt, t 40
přičemž získáme Z
− t12 dt =− (( 1t )2 − 2)3/2
Z
tdt . (1 − 2t2 )3/2
Nakonec si zavedeme třetí substituci 1 − 2t2 = u −4tdt = du −tdt =
1 du. 4
Obdržíme integrál, ve kterém už nemusíme zavádět substituci, a dosazením za 2. a 3. substituci se dopracujeme k výsledku
1 4
Z
du 1 1 1 x √ = − + c = − + c. u3/2 2 (1 − 2t2 )1/2 2 x2 − 2
Po dosazení za první substituci dostaneme, že
Z (ξ 2
dξ 1 ξ+1 =− p . 3/2 2 + 2ξ − 1) 2 ξ + 2ξ − 1
(54)
Jestliže nahradíme hodnoty f (ξ) a g(η) vztahy (51) a (52) a dosadíme je do (46) a (47) získáme dvě rovnice. V jednotlivých postupech využijeme právě pomocné integrály, které jsme odvodili. Opět v obou dvou rovnicích se objevuje analogický postup, proto si podrobněji odvodíme jen rovnici vycházející ze vztahu √ (46). Pro zjednodušení jsme si zavedli substituci, ve které P (a) = a2 + 2a − 1. Postup odvození je následující: Po dosazení získáme výraz Z a
t
1 (ξ−t+ξt)k1 2 dξ+ (ξ + 2ξ − 1)3/2
Z
1
(1−2t)k1 t
41
1 dξ+α(1−2t) ≡ v. (ξ 2 + 2ξ − 1)3/2
Nejdříve se budeme zabývat prvním integrálem. Máme t
Z t 1 1 (1 + t)ξk1 2 dξ − tk1 dξ = 3/2 2 3/2 (ξ + 2ξ − 1) a a (ξ + 2ξ − 1) Z t Z t ξ+1 1 = k1 (1 + t) dξ − k1 (1 + t) dξ 2 3/2 2 3/2 a (ξ + 2ξ − 1) a (ξ + 2ξ − 1) Z t 1 dξ. −k1 t 2 3/2 a (ξ + 2ξ − 1) Z
Po dosazení pomocných integrálů a samotném integrování, získáváme vztah 1 1 1 √ −k1 (1 + t) + k1 (1 + t)(1 + t) + tk1 (1 + t) + 2 2 t2 + 2t − 1 1 1 k1 (1 + t) + k1 (1 + t)(a + 1) + tk1 (a + 1) , P (a) 2 Nyní se budeme zabývat druhým integrálem. Získáme Z t
1
1 (1 − 2t)k1 2 dξ = (1 − 2t)k1 (ξ + 2ξ − 1)3/2
"
1 − 2
ξ+1 p ξ 2 + 2ξ − 1
#1 . t
Výsledek druhého integrálu bude pak (1 − 2t)k1
1 − 2
2 t+1 √ −√ t2 + 2t − 1 2
.
Když potom použiji dohromady výsledek prvního integrálu, výsledek druhého integrálu a lineární člen, získáme po jednoduchých úpravách k1 (1 + t)
1 a+1 1 a+1 1 1 − k1 (1 + t) − tk1 − (1 − 2t)k1 √ + α(1 − 2t) ≡ v P (a) 2 P (a) 2 P (a) 2 a 2α 2 1−a α 1 k1 −t + −√ + + −√ ≡ v. P (a) k1 2P (a) k1 2 2
Po dosazení zpět k proměnné, kdy t = η, dostaneme konečný výsledek k1 −η
2α 2 a + −√ P (a) k1 2
α 1 1−a + + −√ 2P (a) k1 2
42
≡ v.
(55)
Jak už bylo zmíněno na začátku, postup odvozování (47) je analogický, tudíž výsledek je k2
ξ 3a − 1 β − √ + (2ξ − 1) ≡ v. 2P (a) 2 k2
(56)
Požadujeme, aby koeficient u ξ byl roven 0 z toho důvodu, že cena je konstantní. Zařídíme to tak, že položíme k2 β= √ . 2 2 Dále naopak chceme, aby v první rovnici byl koeficient u η také roven 0 (ze stejného důvodu jako v případě ξ). To opět zařídíme tak, že položíme α = 0, potom a 2 =√ . P (a) 2 V dalším kroku si vypočítáme hodnoty a a P (a). Víme, že tyto hodnoty jsou v poměru
√2 . 2
A z tohoto vztahu taky budeme vycházet. a 2 = √ P (a) 2 2 a √ = √ a2 + 2a − 1 2 a2 + 4a − 2 = 0.
√ 6 ± 2. Víme však, že √ a může nabývat maximálně hodnoty 1. Tudíž jediné řešení je a = 6 − 2. Dále √ √ po dosazení získáme, že P (a) = 3 − 2. Řešením této kvadratické rovnice získáme dvě řešení a to:
Jak u tichého souboje, tak i zde platí normalizační rovnice. V případě tichohlučného souboje mají ovšem trochu jinou strukturu díky parametrům α a β. Díky těmto rovnicím můžeme zjistit hodnoty konstant k1 a k2 . Tyto rovnice mají tento tvar Z
1
Z f (ξ)dξ = 1 − α,
1
g(η)dη = 1 − β.
a
a
43
Opět si zde ukážeme odvození jednotlivých konstant. Ukážeme si nejdříve odvození konstanty k1 . Pokud do první normalizační rovnice dosadíme vše, co už známe z předchozích výpočtů a odvozování, získáme
Z
1
k1 dξ = 1 + 2ξ − 1)3/2 a k1 2 a+1 √ − − =1 2 P (a) 2 √ 2 1 √ = k1 2 6−4 (ξ 2
2 √ k1 = √ 3+ 2
(57)
Odvození konstanty k2 bude obdobné s jedinou výjimkou a to takovou, že hodnota parametru β nebude 0, nýbrž 1
Z a
(η 2
k√2 . 2 2
k2 k2 dη = 1 − √ 3/2 + 2η − 1) 2 2 1 a+1 1 = − √ k2 2P (a) 2 2 √ √ 1 2 12 − 2 3 √ = k2 4 6−8 4 √ k2 = √ 3 2+2 3
(58)
Na závěr, abychom zdůvodnili výběr α = 0, musíme dokázat, že rovnice (55) a (56) jsou v souladu s uvedenými hodnotami α, β, a, k1 a k2 a že stanovené strategie jsou skutečně optimální. To, že jsou rovnice v souladu s uvedenými parametry, √ jde jednoduše zkontrolovat a vede k hodnotě v = 5 − 2 6. Nyní prověřím obě dvě rovnice ((55), (56)), že to opravdu platí. Pokud dosadíme všechny známé hodnoty do první rovnice, získáme vztah
2 √ √ 3+ 2
! √ 3− 6 1 √ √ −√ = 2 3−2 2 2 44
√ √ √ 5 2−4 3 √ √ = 5 − 2 6. 3 2−2 2
Dále prověříme druhou rovnici. Opět po dosazení získáme 4 √ √ 3 2+2 3
(
) √ √ √ √ 3 6−7 10 3 − 12 2 1 √ √ − √ √ = = 5 − 2 6. 2 3−2 2 2 2 2 3
Zjistili jsme, že obě dvě rovnice jsou v souladu s uvedenými parametry. Monotónní vlastnosti K(ξ, η) nám zaručují, že Z
K(ξ, η)dx0 (ξ) > v,
pro 0 ≤ η ≤ a.
proto x0 je optimální tak jak je uvedeno výše. Podobný důvod platí i pro y 0 . Na závěr je nutné zkontrolovat výnos pro strategie x0 a y 0 v η = 1 a ξ = 1. Toto lze jednoduše zkontrolovat pro η, neboť α = 0, a také pro ξ, kdy K(1, 1) = 0 < (2ξ − 1)|ξ=1 . Pokud porovnáme výsledky ticho-hlučného souboje a plně tichého souboje, můžeme si nejdříve všimnout, že spektrum u tichého souboje začíná v a = 13 , zatímco √ v ticho-hlučném souboji spektrum začíná v a = 6−2 > 13 . Z těchto dvou hodnot je patrné, že když má jeden z hráčů výhodu schopnosti slyšet výstřel (dozvědět se čas učinění nabídky) jeho soupeře, jeho optimální strategii je vystřelit (učinit nabídku) později než za běžných podmínek tichého souboje. Druhý a důležitější rozdíl u ticho-hlučného souboje je takový, že hráč 2 (s hlučnou zbraní) musí udržovat hrozbu střelby (dobu učinění nabídky) až do samého konce. Tento fakt se odráží ve skoku y 0 , kdy η = 1. ♣ Doposud jsme se zabývali jednotlivými souboji, které byly definovány na jednotce čtverce. Nyní si vybereme souboj, který bude definován ne na jednotce čtverce, ale na čtverci, kdy b ≤ ξ ≤ 1, b ≤ η ≤ 1. Přitom platí, že b > 0. Pro zajímavost si tento typ příkladu ukážeme pro tichý souboj a porovnáme ho s tichým soubojem definovaném na jednotce čtverce. Pro značení ho budeme chápat jako souboj 4. 45
4.1.4
Souboj 4
Abychom tento souboj mohli přesně porovnat s tichým soubojem, budeme uvažovat stejné funkce přesnosti jako to bylo doposud a to P1 (ξ) = P2 (ξ) = ξ. To, že jednotlivé proměnné jsou zespodu ohraničené hodnotou b a ne 0, nám ukazuje verzi tichého souboje, ve kterém má každý hráč počáteční přesnost. Výplatní funkce budou stejné jako v případě tichého souboje a to ξ − η + ξη K(ξ, η) = 0 ξ − η − ξη
pro ξ < η, pro ξ = η, pro ξ > η,
(b ≤ ξ, η ≤ 1).
Opět se jedná o hru symetrickou, kde hodnota hry je 0. Tudíž platí, že každá optimální strategie pro jednoho hráče je zároveň optimální pro hráče druhého. Jestliže b ≤ 31 , je řešení tohoto souboje stejné jako u tichého. V našem případě se budeme snažit najít optimální strategie pro libovolnou hodnotu b. Platí zde opět pravidlo, že jednotliví hráči nemají žádnou znalost vzájemných akcí. Čili, optimální strategii bude i v tomto případě charakterizovat jednak hustota části f na intervalu ha; 1i a diskrétní hodnota v bodě b. Výnos hráče 1, když hráč 2 používá η (a ≤ η ≤ 1), je velmi podobný výnosu u tichého souboje, akorát zde musíme zohlednit diskrétní hodnotu v bodě b.
Z
η
Z
a
1
(ξ − η − ξη)f (ξ)dξ + α(b − η + bη) ≡ 0 (a ≤ η ≤ 1).
(ξ − η + ξη)f (ξ)dξ + η
Hodnota α nám opět určuje váhu, že hráč 1 vystřelí v čase b. Když se podíváme na tuto integrální rovnici a na rovnici (33), zjistíme, že se od sebe liší pouze lineárním členem, který nebude mít vliv na převod této rovnice na diferenciální. Opět řešení této diferenciální rovnice bude f (ξ) = kξ −3 . Postup derivací jsme zde záměrně neuváděli, protože je analogický jako v případě tichého souboje. Ovšem co se nám bude lišit od tichého souboje, tak budou rovnice (40) a (41). Budou se počítat analogicky jako u právě zmíněných rovnic:
46
Z
η
1
Z (ξ − η + ξη)f (ξ)dξ +
(ξ − η − ξη)f (ξ)dξ + α(b − η + bη) ≡ 0
a
η
k k k kη k kη k kη − + + − 2 −k+ −k+ + − + kη − k + α(b − η + bη) = 0 η a 2η 2a a η 2 2η 1 1 1 3 kη − 2 + + +k − 3 + α(b − η + bη) = 0 2a a 2 a
(59)
a normalizační podmínka nám udává, že Z
1
f (ξ)dξ = 1 − α a
k
1 1 − 2 2a 2
Řešením soustav (59) a (60), pro b >
a=
b , 2 − 3b
α=
= 1 − α. 1 3
(60)
je
3b − 1 , 2b2
1 k= . 4
Jelikož řešení soustav není hned ze zadání patrné, opět si zde ukážeme postup výpočtu. Nejdříve si upravíme rovnici (59) tím, že vytkneme hodnotu η, k k 3k 1 η − 2+ + − α + αb + k − 3 + αb = 0. 2a a 2 a Aby nám zde platila tato rovnost, musí se lineární i konstantní člen v této rovnici rovnat nule. Tudíž musí platit −
k k 3k + + − α + αb = 0, 2 2a a 2
(61)
k − 3k + αb = 0. a
(62)
47
Nyní si upravíme rovnici (60) k k − = 1 − α, 2 2a 2 −
k k − α = −1. + 2a2 2
(63)
Úpravou (61) získáme −
k k k + − α + + k + αb = 0. 2 2a 2 a
Abychom mohli na předchozí vztah aplikovat vztahy (62) a (63) a přitom zachovali rovnost, musíme ho upravit následujícím způsobem: k k k − 2 + − α + ( − 3k + αb) +4k = 0. } |a {z } | 2a {z 2 −1
0
Jediná možnost, aby předchozí rovnost platila, musí se nutně k = 14 . Dalším důležitým krokem je vypočtení hodnot a a α. Nejdříve si stanovíme hodnotu α v závislosti na a. Pokud dosadíme k = −
1 4
do (63), získáme
1 1 + − α = −1 2 8a 8 9 1 α = − 2. 8 8a
(64)
Pokud dosadíme (64) do (62) dostaneme parametrickou rovnici s parametrem b 3 1 − + 4a 4
9 1 − 2 8 8a
b=0
a2 (9b − 6) + 2a − b = 0, kde a1,2
p −2 ± (6b − 2)2 = . 2(9b − 6) 48
Řešením pak získáme dvě hodnoty
a1 =
1 a2 = − . 3
b , 2 − 3b
Je jasné, že hodnota a musí být kladná, a proto a =
b . 2−3b
Pak už je velmi
jednoduché dopočítat hodnotu α, když hodnotu a dosadíme do (64). Dostaneme
α=
9 − 8
1
=
8b2 (2−3b)2
3b − 1 . 2b2
Tímto postup řešení končí. Pokud shrneme jednotlivé výsledky, mohou nastat celkem 3 případy Případ 1. Pokud hodnota b ≤
1 , 3
optimální strategie jsou stejné jako v případě tichého
souboje. Případ 2. Musíme brát v úvahu, že α nám představuje váhu a tudíž její hodnota se nutně pohybuje na intervalu h0; 1i. Aby byl splněn tenhle předpoklad, musí platit, že b ≤ 21 . Pokud by se stalo, že b > 12 , pak optimální strategie nebudou v předepsané formě. Jinými slovy, pokud b ∈ ( 13 ; 12 i, optimální strategie budou mít formu: ∗
Z
x = αxb (ξ) +
ξ
f (t)dt,
a=
a
b , 2 − 3b
α=
3b − 1 . 2b2
a dále platí, že f (ξ) =
0 1 −3 ξ 4
0 ≤ ξ < a, a ≤ ξ ≤ 1,
Případ 3. Tento případ nastává právě, když b >
1 . 2
Pak optimální strategie má formu:
xb (ξ), z důvodu, že hodnota a bude záporná. Jinými slovy, nejlepší možností bude vystřelit hned na začátku intervalu. Na samotný závěr si ve stručnosti ukážeme ještě jeden typ her. 49
5
Nekonečné hry, jejíchž prostory strategií jsou známé prostory funkcí Do této kapitoly patří hry, kde prostory strategií jsou podmnožiny prostorů
funkcí, které jsou rozeznatelné. Nepovažují se však za utkání na jednotce čtverce. Do těchto her vstupuje další proměnná a to intenzita střel. Což je rozdíl oproti hrám načasováním jedné akce. Typickým příkladem těchto her je tzv. „Souboj stíhačekÿ.
Souboj stíhaček
Tento typ nekonečné hry je ze světa války. Máme dvě stíhačky, které po sobě střílí. V jedné letí střelec F, který je vybaven municí na jedno kolo a snaží se zničit (sestřelit) bombardér B druhé stíhačky. Vzhledem k tomu, že střelec může střílet pouze jedno kolo (do vyčerpání zásobníku), budeme uvažovat, že jeho strategie bude věc volby, kdy má trefit bombardér. Označíme si a(t) přesnost střelce - pravděpodobnost, že bude B zničen. Proměnná t je hodnota z intervalu h0; 1i. Smíšené strategie hráče F je pravděpodobnostní distribuční funkce přes h0; 1i. Dále budeme předpokládat, že tento model funguje tak, že jakmile F vystřílí svou munici (trefí nebo netrefí), stíhačky odletí a hra skončila. Bombardér B je vybaven kulometem a snaží se při obraně zničit F. Strategie B je popsána funkcí p(t), která označuje intenzitu střel, se kterou kulomet střílí za čas t. Celkové množství munice bombardéru se vypálí do doby δ ≤ 1. Proto nenáhodné strategie p(t) pro B se skládají ze všech funkcí, které splňují Z 0 ≤ p(t) ≤ 1 a
1
p(t) = δ.
(65)
0
V tomto modelu nám ještě bude vystupovat další důležitá funkce, která navíc bude monotónní, a to r(t), která udává přesnost bombardéru s hodnotami r(0) = 0, r(1) = 1. Je to přesnost, v tom smyslu, jestliže B střílí s intenzitou p(t) přes malý časový interval [t;t+h], potom pravděpodobnost, že F bude zničen 50
je p(t)r(t)h + o(h). Hodnota h je velmi malá hodnota. Pravděpodobností φ(t, p) označíme situaci, kdy F přežije až do doby t, když B zvolí intenzitu střel p(t). φ(t + h, p) = φ(t, p)[1 − p(t)r(t)h] + o(h) pro malá kladná h platí φ(t + h, p) − φ(t, p) = −φ(t, p)p(t)r(t) + o(1), h limitně (na hranici) zjistíme, že φ(t, p) splňuje diferenciální rovnici φ0 (t, p) = −φ(t, p)r(t)p(t), s počáteční podmínkou φ(0, p) = 1, jehož řešení je Z φ(t, p) = exp[−
t
p(u)r(u)du].
(66)
0
Výplatní funkce pro tuto hru má tvar K(ξ, p). Když F použije ryzí strategii ξ (doba střelby z munice) a B použije strategii p, je výplatní funkce ohodnocená takto: Označme výplatní funkci na F jako α (jestliže F střelí B) a −β (jestliže B střelí F) a 0 když se nikdo netrefí. Pak se jádro bude uvádět jako očekávaná výplatní funkce k hráči 1 (F) a to tak, že K(ξ, p) = αa(ξ)φ(ξ, p) − β[1 − φ(ξ, p)].
(67)
Výplatní funkce pro smíšené strategie x pro hráče 1 a volba p pro hráče 2 se získá jako průměr (23) vzhledem k dx(ξ) 1
Z K(x, p) =
K(ξ, p)dx(ξ). 0
Další kroky řešení jsou uvedeny v literatuře [3].
51
(68)
6
Závěr Jednotlivé typy soubojů, jako byly hlučné, tiché a ticho-hlučné, popsali dva
významní matematici D. Blackwell and M. A. Girshick. Oba byli rovněž nápomocni při přípravě a řešení několika verzí taktických soubojů. Domnívali se, že ve většině typu nekonečných her se objevují názory vojenských taktických manévrů, které následně zkoumali. Takto vznikly příklady, podle kterých se řeší některé hry načasování. Při samotném psaní této práce jsem si uvědomil, že řešit tuto problematiku her je velmi složité. A skutečně, opravdu zde záleží na zvolených funkcích přesností. Na druhou stranu jsem si připomněl a zopakoval integrální počet, diferenciální rovnice a naučil jsem se převádět integrální rovnice na diferenciální. V podstatě jsem si zopakoval matematickou analýzu spojenou s úpravami jednotlivých vztahů. Ve své práci jsem se zabýval nejenom klasickými modely jednotlivých soubojů, ale ukázal jsem na konkrétních příkladech, kde by se dané souboje mohly objevit. Jednalo se o situace přímo z válečného prostředí nebo situace ekonomické. Dále jsem u tichého souboje uvedl ještě jeden typ souboje, tzv. „souboj 4ÿ, ve kterém jsem se snažil ukázat rozdíl mezi hráči, kteří mají na začátku souboje nějakou přesnost a hráči, kteří začínají na nule. Ze zjištěných poznatků bylo patrné, že jsou tyto dva souboje (tichý a souboj 4) do určité míry stejné. Na závěr bych chtěl říci, že jsem si také uvědomil, že hry načasování se objevují v běžném každodenním životě, aniž by si je člověk sám jakkoliv uvědomoval. Díky této práci jsem si připomněl znalosti konečných her, které jsem mohl rozšířit do her nekonečných. Jelikož jsem hlavně čerpal ze zahraniční (anglické) literatury, procvičil jsem si tímto i světový jazyk a naučil jsem se pracovat s odbornými texty. Psaním této práce jsem si rovněž zlepšil svou slohovou dovednost. Naučil se přesně vyjadřovat a definovat pojmy.
52
Literatura [1] Daňková, K., Teorie her a její aplikace, Bakalářská práce, Univerzita Palackého v Olomouci, Olomouc, 2008 [2] Jarník, V., Integrální počet (I), 3. vydání, Praha: Academia, 1984 [3] Karlin, S., Mathematical Methods and Theory in Games, Programming, and Economics, 2. vydání, London: Pergamon, 1959 [4] Korda, B. a kol., Matematické metody v ekonomii, 1. vydání, Praha: SNTL - Nakladatelství technické, 1967 [5] Maňas, M., Teorie her a optimální rozhodování, 1. vydání, Praha: Státní nakladatelství technické literatury, 1974 [6] Mendelson, E., Introducing game theory and its applications, Boca Raton; London; New York: Chapman and Hall/CRC, 2004 [7] Rubinstein, A., Osborne J. M., A course in game theory, MALondon: MIT Press, 1994 [8] Sušovský, P., Vězňovo dilema, Bakalářská práce, Univerzita Palackého v Olomouci, Olomouc, 2010 [9] Zorich, V. A., Mathematical Analysis II, Berlin: Springer, 2004
53
