5
ANTAGONISTICKE´ HRY
JJ x II 172
Antagonisticky´ konflikt je rozhodovacı´ situace, v nı´zˇ vystupujı´ dva inteligentnı´ rozhodovatele´, kterˇ´ı se po volbeˇ svy´ch rozhodnutı´ rozdeˇlı´ o pevnou cˇa´stku, jejı´zˇ vy´sˇe neza´visı´ na tom, jaka´ rozhodnutı´ zvolili. Matematicky´m modelem antagonisticke´ho konfliktu je hra v norma´lnı´m tvaru s konstantnı´m soucˇtem: {Q = {1, 2}; S, T ; u1 (s, t), u2 (s, t)} u1 (s, t) + u2 (s, t) = konst.
pro kazˇde´ (s, t) ∈ S × T
JJ x II 173
Definice 1. Strategie s∗ , t∗ se nazy´vajı´ rovnova´zˇne´ ve hrˇe (5), platı´-li pro kazˇde´ s ∈ S a kazˇde´ t ∈ T : u1 (s, t∗ ) ≤ u1 (s∗ , t∗ ) a za´rovenˇ
u2 (s∗ , t) ≤ u2 (s∗ , t∗ )
Je-li specia´lneˇ soucˇet ve hrˇe nulovy´, budeme pouzˇ´ıvat znacˇenı´ u1 (s, t) = u2 (s, t) = u(s, t); model tedy bude vypadat takto: {Q = {1, 2}; S, T ; u(s, t)}
(5.1)
Pro rovnova´zˇne´ strategie s∗ , t∗ ve hrˇe s nulovy´m soucˇtem musı´ platit:
u(s, t∗ ) ≤ u(s∗ , t∗ ) ≤ u(s∗ , t)
pro vsˇechna s ∈ S, t ∈ T. (5.2)
Hodnota u(s∗ , t∗ ) se nazy´va´ cena hry.
JJ x II 174
Lze doka´zat, zˇe ke kazˇde´ hrˇe tvaru (5) s konstantnı´m soucˇtem lze prˇirˇadit hru v norma´lnı´m tvaru s nulovy´m soucˇtem, ktera´ je s pu˚vodnı´ hrou strategicky ekvivalentnı´, tj. kazˇda´ dvojice strategiı´ s, t, ktere´ jsou rovnova´zˇne´ v pu˚vodnı´ hrˇe, prˇedstavuje dvojici rovnova´zˇny´ch strategiı´ i v prˇ´ıslusˇne´ hrˇe s nulovy´m soucˇtem a naopak. Prˇesneˇji: Veˇta 1. Necht’(5) je hra s konstantnı´m soucˇtem rovny´m K. Potom s∗ , t∗ jsou rovnova´zˇne´ strategie ve hrˇe (5) tehdy a jen tehdy, jsou-li s∗ , t∗ rovnova´zˇne´ strategie ve hrˇe s nulovy´m soucˇtem (5.1), kde u(s, t) = u1 (s, t) − u2 (s, t).
JJ x II 175
MATICOVE´ HRY Hru dvou hra´cˇu˚ s nulovy´m soucˇtem a konecˇny´mi prostory strategiı´ S = {s1 , s2 , . . . sm },
T = {t1 , t2 , . . . tn }
(5.3)
lze zadat pomocı´ matice A =
a11 a12 . . . a1n a21 a22 . . . a2n .................... am1 am2 . . . amn
=
u1 (s1 , t1 ) u1 (s1 , t2 ) . . . u1 (s1 , tl ) u1 (s2 , t1 ) u1 (s2 , t2 ) . . . u1 (s2 , tl ) ................................... u1 (sk , t1 ) u1 (sk , t2 ) . . . u1 (sk , tl )
jejı´zˇ prvky uda´vajı´ hodnoty vy´platnı´ funkce prvnı´ho hra´cˇe (vy´platnı´ funkce druhe´ho hra´cˇe ma´ vzˇdy opacˇnou hodnotu): prvek aij je roven hodnoteˇ vy´platnı´ funkce prvnı´ho hra´cˇe, zvolil-li strategii si a protivnı´k zvolil strategii tj . Pro takto zadane´ hry se pouzˇ´ıva´ oznacˇenı´ maticove´ hry.
JJ x II 176
Rovnova´zˇne´ strategie v maticove´ hrˇe Prvnı´ hra´cˇ pro kazˇdou svou strategii si , tj. pro kazˇdy´ rˇa´dek i ∈ {1, 2, . . . , m} matice, nalezne minima´lnı´ prvek, ktery´ pro danou strategii prˇedstavuje minima´lnı´ zarucˇenou vy´hru bez ohledu na volbu protivnı´ka. Pak vybere tu strategii, neboli ten rˇa´dek, kde je toto minimum nejvysˇsˇ´ı a tı´m i nejvysˇsˇ´ı zarucˇena´ vy´hra – „nejmensˇ´ı zlo“. Podobneˇ postupuje druhy´ hra´cˇ. Pro neˇj je nejhorsˇ´ı mozˇnostı´ ta nejvysˇsˇ´ı hodnota vy´hry prvnı´ho hra´cˇe; proto pro kazˇdou svou strategii ti , tj. pro kazˇdy´ sloupec j ∈ {1, 2, . . . , n} matice, nalezne maxima´lnı´ prvek, ktery´ pro danou strategii prˇedstavuje maxima´lnı´ zarucˇenou prohru bez ohledu na volbu protivnı´ka. Potom vybere tu strategii, neboli ten sloupec, kde je toto maximum nejmensˇ´ı, neboli kde je maxima´lnı´ prohra co nejnizˇsˇ´ı.
JJ x II 177
Hra´cˇ 2 t1 s1 Hra´cˇ 1 s2 .. . sk
t2
...
tl
u1 (s1 , t1 ) u1 (s1 , t2 ) . . . u1 (s1 , tl )
u1 (s2 , t1 ) u1 (s2 , t2 ) . . . u1 (s2 , tl ) .................................. u1 (sk , t1 ) u1 (sk , t2 ) . . . u1 (sk , tl )
Hra´cˇ 1: mintj u1 (si , tj ) Hra´cˇ 2: maxsi u1 (si , tj )
MAX MIN
Zrˇejmeˇ platı´: max min u1 (si , tj ) ≤ min max u1 (si , tj ) si
tj
tj
si
(5.4)
JJ x II 178
Platı´-li ve vztahu (5.4) rovnost, pak spolecˇna´ hodnota u(s∗ , t∗ ) = max min u1 (si , tj ) = min max u1 (si , tj ) si
tj
tj
si
(5.5)
prˇedstavuje cenu hry a dvojice strategiı´ (s∗ , t∗ ) je rovnova´zˇny´m bodem. Prvek u(s∗ , t∗ ) ma´ tu vlastnost, zˇe je soucˇasneˇ nejmensˇ´ı na rˇa´dku a nejveˇtsˇ´ı ve sloupci, proto se nazy´va´ sedlovy´ prvek matice.
JJ x II 179
☛ Prˇ´ıklad 1. Uvazˇujme hru s maticı´ Hra´cˇ 2
Hra´cˇ 1
t1 t2
t3 t4
s1
5
4
4
s2
−4
5
3
sk
max:
7
8 −1
7
8
4
5
4 9 −4
8
min
−1
9
max min u1 (si , tj ) = 4 = min max u1 (si , tj ) = u1 (s1 , t3 ) s
t
t
s
Dvojice strategiı´ (s1 , t3 ) je rovnova´zˇny´m bodem hry.
JJ x II 180
Bohuzˇel, ne vzˇdy sedlovy´ prvek existuje: ☛ Prˇ´ıklad 2. Hra´cˇ 2
Hra´cˇ 1
t1
t2
0
1 −1
s1
s2
−1
sk max:
t3
−1 1 −1
0
1 −1
0
1
1
1
min
−1
max min u1 (si , tj ) = −1 < min max u1 (si , tj ) = 1 s
t
t
s
JJ x II 181
Podobneˇ pro matice: A=
1 −1 −1 1
,
B=
0 −5/2 −2 −1 3 1
.
(5.6)
V teˇchto prˇ´ıpadech nezbyde nezˇ zave´st smı´sˇene´ strategie. Uvazˇujme novy´ model dane´ rozhodovacı´ situace, pu˚vodneˇ popsane´ maticovou hrou s maticı´ (5):
JJ x II 182
Definice 2. Meˇjme maticovou hru s prostory strategiı´ (5.8) a maticı´ hry (5). Hru dvou hra´cˇu˚ s nulovy´m soucˇtem s prostory strategiı´ S s = {p; p = (p1 , . . . pm ), p1 + · · · + pm = 1, p ≥ o} T s = {q; q = (q1 , . . . qn ), q1 + · · · + qn = 1, q ≥ o} (5.7) a s vy´platnı´ funkcı´ π(p, q) =
n m X X
pi aij qj = pAq T
(5.8)
i=1 j=1
nazveme smı´sˇeny´m rozsˇ´ırˇenı´m pu˚vodnı´ maticove´ hry. Prvky pu˚vodnı´ch prostoru˚ strategiı´ S, T se nazy´vajı´ ryzı´ strategie, prvky prostoru˚ S s , T s , ktere´ uda´vajı´ rozdeˇlenı´ pravdeˇpodobnostı´ na prostoru ryzı´ch strategiı´, se nazy´vajı´ smı´sˇene´ strategie. Veˇta 2. Za´kladnı´ veˇta maticovy´ch her. Smı´sˇene´ rozsˇ´ırˇenı´ kazˇde´ maticove´ hry ma´ rˇesˇenı´ v rovnova´zˇny´ch strategiı´ch. JJ x II 183
Tj. pro kazˇdou matici A existujı´ vektory p∗ ∈ S s , q ∗ ∈ T s : pAq ∗T ≤ p∗ Aq ∗T ≤ p∗ Aq T
pro vsˇechna p ∈ S s , q ∈ T s . (5.9)
Jesˇteˇ jinak: Veˇta. Vzˇdy existujı´ smı´sˇene´ strategie (p∗ , q ∗ ), pro ktere´ π(p∗ , q ∗ ) = max min π(si , tj ) = min max π(si , tj ) p
q
q
p
Veˇta 3. Rovnova´zˇne´ strategie smı´sˇene´ho rozsˇ´ırˇenı´ maticove´ hry se nemeˇnı´, prˇicˇteme-li ke kazˇde´mu prvku matice hry tote´zˇ kladne´ nebo za´porne´ cˇı´slo c. Cena hry s takto pozmeˇneˇnou maticı´ je v + c, kde v je cena pu˚vodnı´ hry.
JJ x II 184
ˇ ESˇENI´ MATICOVY´CH HER GRAFICKE´ R PRO MATICE TYPU (2, n) Strˇednı´ hodnoty vy´hry hra´cˇe 1 prˇi smı´sˇene´ strategii (p, 1 − p) a prˇi ryzı´ch strategiı´ch hra´cˇe 2: gj (p) = pa1j + (1 − p)a2j ,
j = 1, 2, . . . , n.
(5.10)
Hleda´me p∗ := arg max
min gj (p).
p∈h0,1i j=1,2,...,n
(5.11)
Nejprve budeme uvazˇovat funkci ϕ(p) :=
min gj (p).
j=1,2,...,n
(5.12)
Tato funkce je konka´vnı´, po cˇa´stech linea´rnı´, snadno nalezneme bod jejı´ho maxima. Hledana´ cena hry je potom rovna v = ϕ(p∗ ) := max ϕ(p) p∈h0,1i
(5.13)
a hledana´ smı´sˇena´ rovnova´zˇna´ strategie hra´cˇe 1 je (p∗ , 1 − p∗ ). Nasta´va´-li extre´m v bodeˇ p∗ , kde gj (p∗ ) = gk (p∗ ) = v pro jednoznacˇneˇ urcˇene´ strategie j, k pak slozˇky smı´sˇene´ rovnova´zˇne´ JJ x II 185
strategie hra´cˇe 2 s indexy ru˚zny´mi od j, k jsou rovny nule. Slozˇky, ktere´ mohou by´t nenulove´, zı´ska´me vyrˇesˇenı´m soustavy a1j qj + a1k qk = v,
qj + qk = 1,
qj ≥ 0,
qk ≥ 0,
qj + qk = 1,
qj ≥ 0,
qk ≥ 0.
nebo a2j qj + a2k qk = v,
JJ x II 186
☛ Prˇ´ıklad 3. Urcˇenı´ rovnova´zˇny´ch strategiı´ pro hru s maticı´ 5 5/2 3 . 4 8 6 g1 (p) = 5p + 4(1 − p) = p + 4 g2 (p) =
5 11 p + 8(1 − p) = − p + 8 2 2
g3 (p) = 3p + 6(1 − p) = −3p + 6 ϕ(p) naby´va´ maxima v bodeˇ p = 12 , hodnota tohoto maxima je v(M ) = 4.5. Vyrˇesˇenı´m soustavy rovnic 5q1 + 3q3 = 4.5,
q1 + q3 = 1,
q1 ≥ 0,
q3 ≥ 0,
zı´ska´me q1 = 0.75, q2 = 0.25. Rovnova´zˇny´ bod je tedy p∗ =
1 1 , 2 2
,
q∗ =
3 1 , 4 4
.
JJ x II 187
JJ x II 188
ˇ ES ˇ ENI´ MATICOVY´CH HER OBECNE´ R ´ RNI´ PROGRAMOVA ´ NI´ – LINEA Uvazˇujme maticovou hru s maticı´ a11 a12 . . . a1n a22 . . . a2n a A = 21 ................... am1 am2 . . . amn
(5.14)
a smı´sˇene´ strategie p = (p1 , . . . , pm ), p1 + · · · + pm = 1, pi ≥ 0 ∀i ∈ {1, . . . , m}, q = (q1 , . . . , qn ),
q1 + · · · + qn = 1, qj ≥ 0 ∀j ∈ {1, . . . , n}.
Prˇedpokla´dejme, zˇe vsˇechny prvky matice A jsou kladne´ (Pokud by nebyly, mohli bychom ke vsˇem prvku˚m matice prˇicˇı´st dostatecˇneˇ vysokou kladnou konstantu c, cˇı´mzˇ se podle veˇty 3 z hlediska strategiı´ nic nezmeˇnı´).
JJ x II 189
Postup je podobny´, jako v prˇ´ıpadeˇ hleda´nı´ ryzı´ch rovnova´zˇny´ch strategiı´. Prvnı´ hra´cˇ hleda´ pro libovolne´, ale v tuto chvı´li pevne´ p svou minima´lnı´ zarucˇenou vy´hru h. Uvazˇujme h = min{a1j p1 + a2j p2 + · · · + amj pm } . ∀j
(5.15)
Zrˇejmeˇ je h ≤ a1j p1 + a2j p2 + · · · + amj pm pro vsˇechna j ∈ {1, 2, . . . , n}.
q1 h ≤ q1 (a11 p1 + a21 p2 + · · · + am1 pm ) q2 h ≤ q2 (a12 p1 + a22 p2 + · · · + am2 pm ) ...................................... qn h ≤ qn (a1n p1 + a2n p2 + · · · + amn pm ) m X n X
(q + q2 + · · · + qn ) h ≤ pi aij qj = π(p, q) |1 {z } i=1 j=1 1 h ≤ π(p, q)
JJ x II 190
Hodnota h je proto minima´lnı´ zarucˇenou vy´hrou hra´cˇe 1, at’ jizˇ jeho protivnı´k zvolı´ jakoukoli ryzı´ cˇi smı´sˇenou strategii (vzhledem k (5.15) je h nejveˇtsˇ´ı cˇı´slo splnˇujı´cı´ poslednı´ nerovnost). Nerovnosti h ≤ a1j p1 + a2j p2 + · · · + amj pm pro vsˇechna j ∈ {1, 2, . . . , n}. vydeˇlme hodnotou h 1 ≤ a1j
p2 pm p1 + a2j + · · · + amj h h h
a oznacˇme yi =
pi ; h
zrˇejmeˇ platı´:
y1 + y2 + · · · + ym =
1 . h
Obdrzˇ´ıme nerovnost 1 ≤ a1j y1 + a2j y2 + · · · + amj ym .
(5.16)
JJ x II 191
Maximalizovat minima´lnı´ zarucˇenou vy´hru znamena´ maximalizovat h, tj. Minimalizovat 1 = y1 + y2 + · · · + ym h prˇi omezenı´ch 1 ≤ a1j y1 + a2j y2 + · · · + amj ym ,
j = 1, 2, . . . , n . (5.17)
To je prˇesneˇ dua´lnı´ u´loha linea´rnı´ho programova´nı´, ktera´ na´m jako vy´sledek poskytne prˇ´ıslusˇnou strategii p.
JJ x II 192
Pro druhe´ho hra´cˇe je postup analogicky´. Hleda´ h a q tak, aby h ≥ ai1 q1 + ai2 q2 + · · · + ain qn
pro vsˇechna i ∈ {1, 2, . . . , m},
prˇicˇemzˇ opeˇt q1 + q2 + · · · + qn = 1, qj ≥ 0 pro vsˇechna ∀j ∈ {1, 2, . . . , n}. Vydeˇlme nerovnost hodnotou h q1 q2 qn 1 ≥ ai1 + ai2 + · · · + ain h h h a oznacˇme 1 qj ; zrˇejmeˇ platı´: x1 + x2 + · · · + xn = . xj = h h Obdrzˇ´ıme nerovnost 1 ≥ ai1 x1 + ai2 x2 + · · · + ain xn .
(5.18)
Minimalizovat h tedy znamena´: maximalizovat 1 = x1 + x2 + · · · + xn h prˇi omezenı´ch 1 ≥ ai1 x1 + ai2 x2 + · · · + ain xn ,
i = 1, 2, . . . , m . (5.19) JJ x II 193
To je odpovı´dajı´cı´ prima´rnı´ u´loha linea´rnı´ho programova´nı´ (aby h byla cena hry, je trˇeba, aby to v obou prˇ´ıpadech bylo tote´zˇ cˇı´slo).
JJ x II 194
☛ Prˇ´ıklad 4 – Penalty Strˇelba penalt mu˚zˇe by´t povazˇova´na za antagonistickou hru s na´sledujı´cı´ maticı´, ktera´ uda´va´ pravdeˇpodobnost go´lu pro ru˚zne´ strategie strˇelce (1. hra´cˇ) a branka´rˇe (2. hra´cˇ). Budeme hledat rovnova´zˇny´ bod v ryzı´ch nebo smı´sˇeny´ch strategiı´ch. Strategie
skocˇ vlevo
skocˇ vpravo
cˇekej uprostrˇed
Strˇ´ılej vlevo
0, 6
0, 7
1
Strˇ´ılej vpravo
1
0, 8
0, 7
Rˇesˇenı´. g1 (p) = 0, 6 + 1 − p = 1 − 0, 4p g2 (p) = 0, 7p + 0, 8(1 − p) = 0, 8 − 0, 1p g3 (p) = p + 0, 7(1 − p) = 0, 7 + 0, 3p Nejvysˇsˇ´ı zarucˇena´ vy´hra pro strˇelce: g2 (p) = g3 (p) ⇐ p = Rovnova´zˇny´ bod:
1 3 , 4 4
1 4
, 0, 43 , 14 , cena hry: v = 0, 775 JJ x II 195
Spra´vnost rˇesˇenı´ maticovy´ch her si mu˚zˇete zkontrolovat pomocı´ appletu, ktery´ naleznete zde. Na´sledujı´cı´ prˇ´ıklad ilustruje prˇechod od sedlove´ho prvku k rovnova´zˇne´mu bodu. Pro hry s nulovy´m a konstantnı´m soucˇtem se oba pojmy shodujı´, pro hry s nekonstantnı´m soucˇtem uzˇ tomu tak by´t nemusı´:
(3, −3) (2, −2)
(0, 0)
(3, 3)
(1, −1)
(2, 4)
(3, 3) → (2, 4)
↑ ↓ (0, 2) → (4, 5)
(0, 6)
(1, 5)
(4, 5) . . . vza´jemneˇ nejlepsˇ´ı odpoveˇdi – rovnova´zˇny´ bod
JJ x II 196
