Modely konfliktů 1 Bimaticové hry Definice 1. Konečná hra dvou hráčů v normálním tvaru (bimaticová hra) je uspřádaná čtveřice G = (X, Y, u, v), kde X, Y jsou konečné množiny a u, v jsou funkce X × Y R. Množina X, resp. Y , je množina strategií prvního, resp. druhého, hráče. Funkce u, resp. v, je výplatní funkce prvního, resp. druhého, hráče. Poněvadž množiny X, Y jsou konečné, lze položit X = {1, 2, . . ., n} a Y = {1, 2, . . ., m}. Označme aij = u(i, j), bij = v(i, j), A = a11 a12 . . . a1m a21 a22 . . . a2m ... ... ... ... an1 an2 . . . anm , B = b11 b12 . . . b1m b21 b22 . . . b2m ... ... ... ... bm1 bm2 . . . bnm a dále ei vektor, jehož všechny složky jsou nulové s výjimkou i-té, která je rovna 1; jedná se tedy o i-tý prvek standardní báze vektorového prostoru Rk , jehož dimenze k bude dána kontextem. Při tomto označení je u(i, j) = eT i Aej, v(i, j) = eT i Bej = eT j BT ei. (1) Bimaticová hra je tedy jednoznačně určena maticemi A a B. Můžeme ji zapisovat ve tvaru hráč 2 1 2 . . . m 1 a11 b11 a12 b12 . . . a1m b1m hráč1 2 a21 b21 a22 b22 . . . a2m b2m ... ... ... ... ... n an1 bn1 an2 bn2 . . . anm bnm Označme Sk = (x1, x2, . . . , xT k Rk : x1 0, x2 0, . . . , xk 0, k i=1 xk = 1 k-rozměrný simplex. Definice 2. Pravděpodobnostní rozšíření bimaticové hry G = (X, Y, u, v) je uspořádaná čtveřice G = (X , Y , u , v ), kde X = Sn, Y = Sm a u , v jsou funkce X × Y R definované předpisem u (x, y) = xT Ay, v (x, y) = yT BT x, (2) kde A = u(i, j) , B = v(i, j) . Zobrazení f : X X a g : Y Y definovaná předpisy f(i) = ei, g(j) = ej jsou prostá. Proto lze množinu X (resp. Y ) považovat za podmnožinu množiny X , resp. Y . Porovnáním formulí (1) a (2) vidíme, že funkci u, resp. v lze považovat za zúžení zobrazení u , resp. v , na množinu X, resp. Y . Strategiím z množin X, Y budeme říkat ryzí, prvkům z množin X , Y budeme říkat smíšené strategie. 1 Definice 3. Buď G = (X, X, u, v) bimaticová hra s týmiž množinami strategií pro oba hráče. Smíšená strategie x X se nazývá rovnovážná (podle Nashe), jestliže pro každou smíšenou strategii x X platí nerovnosti u (x, x) u (x, x) , v (x, x) v (x, x) . Označení: Pro x = (x1, . . . , xn) T klademe C(x) = {k {1, 2, . . ., n} : xk > 0} ; množinu C(x) nazýváme nosič strategie x. Podobně zavádíme nosič strategie y Y . Kroneckerův symbol je definován jako ij = 1, i = 1 0, i = j. 2 Vyjádření konfliktu pomocí systému obyčejných diferenciálních rovnic Představme si dva účastníky konfliktní situace popsané bimaticovou hrou G = (X, Y, u, v), X = {1, 2, . . ., n}, Y = {1, 2, . . ., m}, u(i, j) = aij, v(i, j) = bij. Budou se chovat podle následujícího scénáře: Během časového intervalu délky t sehrají mnoho kol této hry tak, že budou používat pevně zvolené smíšené strategie x = x(t) = (x1(t), . . . , xn(t)) T , y = y(t) = (y1(t), . . . , ym(t)) T , tj. první hráč použije ryzí strategii i s relativní četností xi atd. Tímto způsobem první hráč empiricky zjistí střední hodnotu výhry xT Ay a také střední hodnotu výhry při používání ryzí strategie i, tj. eT i Ay = m j=1 aijyj (za první hodnotu může vzít celkovou výhru dělenou počtem sehraných kol, za druhou součet výher v kolech hraných se strategií i dělený jejich počtem). Po uplynutí času t změní první hráč svou smíšenou strategii tak, aby relativní změna frekvence používání strategie i byla úměrná odchylce výhry při používání strategie i a délce časového intervalu t, tj. xi xi = xi(t + t) - xi(t) xi(t) = c m j=1 aijyj(t) - x(t)T Ay(t) t. (3) Odtud plyne xi(t + t) = xi(t) 1 + c m j=1 aijyj(t) - x(t)T Ay(t) t . 2 Poněvadž x1(t), . . . , xn(t) T X , platí n i=1 xi(t) = 1 a tedy také n i=1 xi(t + t) = n i=1 xi(t) + c m j=1 xi(t)aijyj(t) - x(t)T Ay(t)xi(t) t = = 1 + c n i=1 m j=1 xi(t)aijyj(t) - x(t)T Ay(t) t = 1 + c 0 t = 1 pro libovolnou konstantu c. Za koeficient úměrnosti můžeme tedy volit c = 1. Rovnici (3) nyní přepíšeme na tvar xi t = xi eT i Ay - xT Ay = xi (ei - x) T Ay. Analogickou úvahou odvodíme pro druhého hráče rovnici yj t = yj (ej - y)T BT x. Limitním přechodem t 0 dostaneme autonomní systém n + m obyčejných diferenciálních rovnic x i = xi (ei - x)T Ay, i = 1, 2, . . ., n y j = yj (ej - y) T BT x, j = 1, 2, . . ., m. (4) Spolu s tímto systémem uvažujme počáteční podmínky xi(0) = xi,0 0, i = 1, 2, . . ., n, yj(0) = yj,0 0, j = 1, 2, . . . , m, (5) n i=1 xi,0 = 1, m j=1 yj,0 = 1. (6) Věta 1. Systém rovnic (4) s počáteční podmínkou (5) splňující rovnosti (6) má jediné řešení definované na intervalu [0, ). Množiny Sn × Sm, int(Sn × Sm) a (Sn × Sm) jsou invariantními množinami systému (4). Důkaz. Jsou-li x = x(t) = x1(t), . . . , xn(t) T , y = y(t) = x1(t), . . . , ym(t) T řešení systému (4), pak platí d dt n i=1 xi(t) - 1 = n i=1 x i(t) = n i=1 xi(t) n j=1 aijyj(t) - xT (t)Ay(t) = = xT (t)Ay(t) 1 - n i=1 xi(t) . To znamená, že funkce z = z(t) = n i=1 xi(t) - 1 splňuje lineární homogenní diferenciální rovnici z = xT (t)Ay(t)z, takže z(t) = n i=1 xi(t) - 1 = n i=1 xi(0) - 1 exp 0 t xT (s)Ay(s)ds . 3 Z první rovnosti (6) nyní plyne identita n i=1 xi(t) = 1 pro všechna t 0. (7) Analogicky odvodíme platnost rovnosti m j=1 yj(t) = 1 pro všechna t 0. (8) Pokud má tedy úloha (4), (5) řešení, pak řešení s počáteční podmínkou v množině Sn × Sm v této množině zůstává pro všechna t > 0, tedy Sn × Sm je invariantní množinou systému (4). Dále pro všechna i, k {1, 2, . . ., n}, j, l {1, 2, . . ., m} platí xk xi(ei - x)T Ay = ik(ei - x)T - xieT k Ay, yl xi(ei - x)T Ay = xi(ei - x)T Ael, xk yj(ej - y)T BT x = yj (ej - y) T BT ek, yl yj(ej - y)T BT x = jl(ej - yT ) - yjeT l BT x; parciální derivace pravých stran systému (4) podle všech proměnných jsou na množině Sn × Sm ohraničené. Odtud a z Picardovy-Lindelöfovy věty plyne, že systém (4) je globálně jednoznačně řešitelný na množině Sn × Sm. Je-li xi,0 = 0, resp. xi,0 > 0 pro nějaké i {1, 2, . . . , n}, pak z jednoznačnosti řešení systému (4) plyne, že xi(t) = 0, resp. xi(t) > 0, pro všechna t 0. Analogickou úvahu můžeme provést pro počáteční hodnotu yj,0 pro nějaké j {1, 2, . . ., m}. Odtud plyne, že množiny (Sn × Sm) a int(Sn × Sm) jsou invariantní. 3 Redukce dimenze systému (4) Z invariance množiny Sn × Sm vzhledem k systému (4), tj. z rovností (7) a (8) plyne xn = 1 - n-1 i=1 xj, ym = 1 - m-1 j=1 yj Odtud dále dostaneme m j=1 aijyj - xT Ay = m j=1 aijyj - n l=1 n j=1 xlaljyj = = m-1 j=1 aijyj + aim 1 - m-1 j=1 yj - n l=1 xl m-1 j=1 aljyj + alm 1 - m-1 j=1 yj = = m-1 j=1 (aij - aim)yj + aim - n l=1 xl m-1 j=1 (alj - alm)yj + alm = 4 = m-1 j=1 (aij - aim)yj + aim - n-1 l=1 xl m-1 j=1 (alj - alm)yj + alm - 1 - n-1 l=1 xl m-1 j=1 (anj - anm)yj + anm = = m-1 j=1 (aij - aim)yj + aim - m-1 j=1 (anj - anm)yj - anm- - n-1 l=1 xl m-1 j=1 (alj - alm - anj + anm)yj + alm - anm = = m-1 j=1 (aij - aim - anj + anm)yj + aim - anm- - n-1 l=1 xl m-1 j=1 (alj - alm - anj + anm)yj + alm - anm = = n-1 l=1 m-1 j=1 il [(alj - alm - anj + anm)yj + alm - anm] - - n-1 l=1 m-1 j=1 xl [(alj - alm - anj + anm)yj + alm - anm] = = n-1 l=1 m-1 j=1 (il - xl) [(alj - alm - anj + anm)yj + alm - anm] . Označme nyní ~aij = aij - aim - anj + anm, ^ai = anm - aim pro i = 1, 2, . . . , n - 1, j = 1, 2, . . ., m - 1 a dále ~A = ~a11 ~a12 . . . ~a1(m-1) ~a21 ~a22 . . . ~a2(m-1) ... ... ... ... ~a(n-1)1 ~a(n-1)2 . . . ~a(n-1)(m-1) , ^a = ^a1 ^a2 ... ^an-1 . Analogickým výpočtem lze ukázat, že n i=1 bjixi - yT BT x = m-1 j=1 n-1 l=1 (lj - yj) [(blj - blm - bnj + bnm)xl + bnj - bnm] a potom označit ~bij = bij - bim - bnj + bnm, ^bj = bnm - bnj pro i = 1, 2, . . . , n - 1, j = 1, 2, . . ., m - 1 a dále ~B = ~b11 ~b12 . . . ~b1(m-1) ~b21 ~b22 . . . ~b2(m-1) ... ... ... ... ~b(n-1)1 ~b(n-1)2 . . . ~b(n-1)(m-1) , ^b = ^b1 ^b2 ... ^bm-1 . 5 Provedená úvaha a výpočet ukazují, že (n + m)-rozměrný systém (4) lze zredukovat na systém (n + m - 2)-rozměrný x i = xi(ei - x)T ~Ay - ^a , i = 1, 2, . . ., n - 1, y j = yj(ej - y)T ~BT x - ^b , j = 1, 2, . . . , m - 1. (9) Nyní označujeme x = (x1, x2, . . . , xn-1) T , y = (y1, y2, . . . , ym-1) T . 4 Konflikty se dvěma strategiemi Nechť n = m = 2, A = a11 a12 a21 a22 , B = b11 b12 b21 b22 . Pak systém rovnic (9) je tvaru x = x(1 - x)(1y - 2), y = y(1 - y)(1x - 2), kde 1 = a11 - a12 - a21 + a22, 2 = a22 - a12, 1 = b11 - b12 - b21 + b22, 2 = b22 - b21. Fázovým prostorem je množina [0, 1] × [0, 1]. Systém má stacionární řešení (0, 0), (0, 1), (1, 0), (1, 1) odpovídající ryzím strategiím. V případě, že 1 = 0, 0 < 2 1 < 1, 1 = 0, 0 < 2 1 < 1, má také vnitřní stacionární řešení 2 1 , 2 1 odpovídající smíšeným strategiím. Variační matice systému je J(x, y) = (1 - 2x)(1y - 2) 1x(1 - x) 1y(1 - y) (1 - 2y)(1x - 2) , takže J(0, 0) = -2 0 0 -2 , J(0, 1) = 1 - 2 0 0 2 , J(1, 0) = 2 0 0 1 - 2 , J(1, 1) = 2 - 1 0 0 2 - 1 , J 2 1 , 2 1 = 0 12(1 - 2) 2 1 21(1 - 2) 2 1 0 . Odtud je vidět, že stacionární řešení odpovídající ryzím strategiím jsou sedla nebo uzly, stacionární řešení odpovídající smíšeným strategiím je sedlo nebo nestabilní ohnisko. 5 Symetrické konflikty Definice 4. Řekneme, že konečná hra dvou hráčů G = (X, Y, u, v) je symetrická, pokud X = Y a u(i, j) = v(j, i) pro každé dvě ryzí strategie i, j X. Pro symetrickou hru platí aij = u(i, j) = v(j, i) = bji, tedy A = BT . To znamená, že symetrická hra je jednoznačně určena maticí A. 6 Poznámka 1. Nechť matice A určuje výplatní funkce v symetrické konečné hře. Smíšená strategie x X je rovnovážnou strategií (podle Nashe) právě tehdy, když xT Ax xAx pro všechny smíšené strategie x X , tj. xT Ax = max xT Ax : x X . Důkaz. Nechť x X je rovnovážná strategie. Pak pro libovolnou smíšenou strategii x X platí xT Ax = u (x, x) u (x, x) = xT Ax. Nechť naopak platí xT Ax = max xT Ax : x X . Pak pro libovolnou smíšenou strategii x X platí u (x, x) = xT Ax xT Ax = u (x, x), v (x, x) = xT Ax xT Ax = v (x, x). Věta 2. Nechť G je symetrická konečná hra určená maticí A. Smíšená strategie x = (x1, x2, . . . , xn)T = n i=1 xiei X je rovnvážná právě tehdy, když eT i Ax xT Ax pro všechna i C(x) (10) a eT i Ax = xT Ax pro všechna i C(x). (11) Důkaz. Nechť x je rovnovážná strategie. Podle předchozí poznámky platí eT i Ax xT Ax pro všechna i {1, 2, . . ., n}. Připusťme, že existuje k C(x) tak, že eT k Ax < xT Ax. Pak xT Ax = n i=1 xieT i Ax = iC(x) xieT i Ax = xkeT k Ax + iC(x) {k} xieT i Ax < < xk xT Ax + iC(x) {k} xi xT Ax = n i=1 xi xT Ax = xT Ax, což je spor, který dokazuje nutnost podmínek. Nechť platí podmínky (10) a (11). Pak pro všechna i {1, 2, . . ., n} platí eT i Ax xT Ax. Je-li nyní x = (x1, x2, . . . , xn)T X libovolná smíšená strategie, pak xT Ax = n i=1 xieT i Ax n i=1 xi xT Ax = xT i Ax, takže podle předchozí poznámky je x rovnovážnou strategií. Podmínky jsou tedy i dostatečné. Poznámka 2. Ryzí strategie ei X je rovnovážnou strategií symetrické konečné hry s výplatními funkcemi určenými maticí A právě tehdy, když aji aii pro všechna j {1, 2, . . ., n}. Důkaz. V tomto případě je C(ei) = {i}, eT j Aei = aji, eT i Aei = aii. 7 Buď G konečná hra určená kladnou maticí A, tj. aij > 0 pro všechna i, j {1, 2, . . ., n}. Podmínka kladnosti čísel aij není újmou na obecnosti; její splnění lze pro libovolnou matici dosáhnout přičtením vhodné konstanty ke všem jejím prvkům. Budeme hledat rovnovážnou strategii x X takovou, že její používání dává ze všech rovnovážných strategií největší výhru, tj. v = ~xT A~x = max xT Ax : x X je rovnovážná strategie . Předpokládejme, že ~x = (~x1, ~x2, . . . , ~xn) T je strategie požadované vlastnosti. Pak platí v = n i=1 n j=1 ~xiaij ~xj > 0. Položme i = ~xi v . Pro libovolné i {1, 2, . . ., n} podle věty 2 platí v n j=1 aijj = n j=1 aij ~xj = eT i A~x ~xT i A~x = v, takže n j=1 aijj 1. Dále n j=1 j = 1 v n j=1 ~xj = 1 v . Má-li být kladné číslo v maximální, musí být jeho převrácená hodnota minimální; má-li být hod- nota n j=1 i minimální, musí být opačná hodnota maximální. Hledání rovnovážné strategie dávající největší výhru je tedy ekvivalentní hledání maxima lineárního výrazu - n j=1 i za podmínek n j=1 aijj 1, i 0 pro i = 1, 2, . . . , n, což je úloha lineárního programování. V symetrické hře je m = n, strategie obou hráčů jsou stejné, tj. y = x a BT = A. To znamená, že systém diferenciálních rovnic (4) se skládá ze dvou shodných subsystémů. Jinak řečeno, symetrickou hru můžeme vyjádřit systémem n obyčejných diferenciálních rovnic x i = xi (ei - x)T Ax, i = 1, 2, . . ., n. (12) Z věty 1 plyne, že systém (12) je jednoznačně řešitelný na n-rozměrném simplexu Sn a že množiny Sn, int Sn a Sn jsou vzhledem k němu invariantní. Věta 3. Je-li x rovnovážnou strategií symetrické konečné hry určené maticí A, pak x je stacionárním bodem autonomního systému (12). 8 Důkaz. Plyne bezprostředně z věty 2 a z toho, že podmínky (10) a (11) lze přepsat na tvar (ei - x) T Ax 0 pro všechna i C(x), (ei - x) T Ax = 0 pro všechna i C(x). Obrácené tvrzení neplatí; každá ryzí strategie ei je stacionárním bodem systému (12), ale ryzí strategie obecně není rovnovážná. Věta 4. Je-li ^x = (^x1, ^x2, . . . , ^xn)T X stabilním stacionárním bodem systému (12), pak ^x je rovnovážnou strategií symetrické konečné hry určené maticí A. Důkaz. Označme Fi(x) = xi (ei - x) T Ax = xi n k=1 aikxk - n l=1 n k=1 alkxlxk . Pak Fi xj (x) = ij n k=1 aikxk - n l=1 n k=1 alkxlxk + xi aij - n k=1 ajkxk - n l=1 aljxl = = ij eT i Ax - xT Ax + xi aij - eT j Ax - xT Aej . Prvky variační matice systému (12) v bodě ^x tedy jsou Fi xj (^x) = ^xi aij - eT j A^x - ^xT Aej , ^xi = 0, ij eT i A^x - ^xT A^x , ^xi = 0. Vlastní čísla variační matice splňují rovnici det Fi xj (^x) - ij = 0. Buď i takové, že ^xi = 0. Determinant rozvineme podle i-tého řádku: eT i A^x - ^xT A^x - (příslušný algebraický doplněk). Odtud plyne, že pro každé i takové, že ^xi = 0, je číslo eT i A^x - ^xT A^x vlastní hodnotou variační matice. Ze stability stacionárního řešení ^x plyne eT i A^x - ^xT A^x 0 pro každé i takové, že ^xi = 0. Současně platí eT i A^x - ^xT A^x = 0 pro každé i takové, že ^xi = 0, neboť ^x je stacionární řešení systému (12). Celkem tedy eT i A^x - ^xT A^x 0 pro všechna i {1, 2, . . ., n}. Je-li nyní x = n i=1 xiei X libovolná smíšená strategie, pak platí xT A^x = n i=1 xieT i A^x n i=1 xi ^xT A^x = ^xT A^x n i=1 xi = ^xT A^x, což znamená, že ^x je rovnovážnou strategií. 9 Obrácené tvrzení opět neplatí. Uvažme například konečnou symetrickou hru s maticí A = 1 0 0 0 . Pak strategie x = (0, 1)T je rovnovážná, neboť (x, 1 - x) 1 0 0 0 0 1 = 0 = (0, 1) 1 0 0 0 0 1 pro libovolné x [0, 1]. Příslušný systém diferenciálních rovnic je x = x (1, 0) 1 0 0 0 x y - (x, y) 1 0 0 0 x y = x(x - x2 ) = x2 (1 - x), y = y (0, 1) 1 0 0 0 x y - (x, y) 1 0 0 0 x y = y(-x2 ) = -x2 y. Stacionární body tedy jsou (0, y), (1, 0) pro libovolné y [0, 1]. Variační matice ve stacionárním bodě (x, y) je tvaru J(x, y) = 2x - 3x2 0 -2xy -x2 . Zejména tedy J(0, 1) = 0 0 0 0 . Charakteristický polynom této matice má dvojnásobný kořen = 0, což znamená, že stacionární řešení (0, 1) není stabilní. Věta 5. Pro i, j {1, 2, . . . , n - 1} položme bi,j = anj - aij, ri = ain - ann a B = b1,1 b1,2 . . . b1,n-1 b2,1 b2,2 . . . b2,n-1 ... ... ... ... bn-1,1 bn-1,2 . . . bn-1,n-1 , r = r1 r2 ... rn-1 . Pak systém (12) na množině int Sn a Lotkův-Volterrův systém y j = yj rj - eT j By , j = 1, 2, . . ., n - 1 (13) na množině int Rn-1 + = (y1, yj, . . . , yn-1)T Rn-1 : y1 > 0, y2 > 0, . . . , yn-1 > 0 jsou topologicky ekvivalentní, tj. existuje difeomorfismus F : int Sn int Rn-1 + , který zobrazí trajektorie systému (12) na trajektorie systému (13). Důkaz. Pro x = (x1, x2, . . . , xn)T int Sn a pro j {1, 2, . . ., n - 1} položme yi = xi xn . Pak n-1 j=1 yj = 1 xn n-1 j=1 xi = 1 xn (1 - xn) = 1 xn - 1. Odtud dostaneme xn = 1 1 + n-1 j=1 yj a xi = yi 1 + n-1 j=1 yj pro i = 1, 2, . . ., n - 1. 10 To znamená, že zobrazení F : int Sn int Rn-1 + dané předpisem F(x) = F (x1, x2, . . . , xn)T = x1 xn , x2 xn , . . . , xn-1 xn T je bijekce. Toto zobrazení je zřejmě spojité. Nechť nyní x = x(t) je řešení systému (12) takové, že xn(0) > 0, tedy xn(t) > 0 pro všechna t > 0. Položme = t 0 xn(s)ds. Pak je rostoucí funkcí proměnné t, d dt = xn a dále dyj d = d xj xn dt dt d = x jxn - xjx n x2 n 1 xn = 1 x2 n x j - xj x n xn = = 1 x2 n xj(eT j Ax - xT Ax) - xj(eT nAx - xT Ax) = xj x2 n eT j Ax - eT nAx = = xj x2 n n k=1 ajkxk - n k=1 ankxk = xj x2 n n k=1 (ajk - ank)xk = = xj x2 n n-1 k=1 (ajk - ank)xk + (ajn - ann)xn = xj xn ajn - ann - n-1 k=1 (ank - ajk) xk xn = = yj rj - n-1 k=1 bj,kyk = yj rj - eT j By . 11