2. Trojuholníková nerovnosť vzorové riešenie

2

3
1
1 1

3
1
-1 1

0.000000000 0.000000000 1.000000000
0.500000000 0.500000000 0.000000000

Pri pohľade na túto úlohu každému padne do oka jej netradičné bodovanie. Aj keď ste nenašli najlepšiu stratégiu pre Miša, mohli ste získať za úlohu body. Neznamená to ale, že je ťažké nájsť najlepšiu stratégiu – ide ju spočítať exaktne, a netreba sa uchýliť k heuristickým metódam, magickým konštantám, a podobným.

Ako hrá Žaba?

Máme maticu \(A\) rozmerov \(n \times n\), v ktorej sú hodnoty \(0\), \(\frac{1}{2}\) alebo \(1\) podľa zadaného grafu, pričom hodnotu \(\frac{1}{2}\) máme iba na diagonále. V každom kole si Mišo tajne vyberie riadok \(r\) a Žaba si tajne vyberie \(s\). Následne sa ich voľby odkryjú, a podľa hodnoty v riadku \(r\) a stĺpci \(s\) sa pridelia body. Mišo získa toľko bodov, koľko je tá hodnota. Žaba vždy získa taký počet bodov, aby celkový počet udelených bodov bol \(1\).

Mišo si zvolil pravdepodobnosti \(p_1, \ldots, p_n\) – \(p_i\) reprezentuje pravdepodobnosť, s akou si zvolí \(i\)-ty riadok. Súčet pravdepodobností je \(1\). Predstavme si, že si Žaba zvolil stĺpec \(s\). Potom s pravdepodobnosťou \(p_1\) zvolil Mišo riadok \(1\), a v tom prípade by získal \(A_{1, s}\) bodov. S pravdepodobnosťou \(p_2\) zvolil riadok \(2\), a získal by vtedy \(A_{2, s}\) bodov. Podobne pre ostatné prípady. V priemere by tak získal toľkoto bodov:

\[p_1 \cdot A_{1, s} + p_2 \cdot A_{2, s} + \ldots + p_n \cdot A_{n, s} = (p_1, p_2, \ldots, p_n) \cdot (A_{1, s}, A_{2, s}, \ldots, A_{n, s})\]

Samozrejme, Žaba zvolí \(s\) tak, aby v priemere získal Mišo čo najmenej bodov. Môžeme sa na to pozerať tak, že Mišo priradil riadkom pravdepodobnosti, a následne každý riadok matice prenásobil pravdepodobnosťou, ktorú riadku priradil. Následne príde Žaba, a vyberie si stĺpec s najmenším súčtom. Tento súčet reprezentuje očakávaný počet bodov, ktoré získa Mišo.

(Napríklad Mišo si zvolil pravdepodobnosti \(0.3, 0.2, 0.4, 0.1\). Potom vie Žaba hrať tak, že Mišo získa v priemere \(0.25\) bodov – vždy zvolí sivý stĺpec.)

Nash equilibrium

Pod stratégiou hrania tejto hry budeme rozumieť pravdepodobnosti, s akými si zvolíme vrcholy grafu. Zoberme si dvoch hráčov, prvý nech má stratégiu \(P = (p_1, p_2, \ldots, p_n)\). Druhý nech má stratégiu \(Q = (q_1, q_2, \ldots, q_n)\).

Hovoríme, že \((P, Q)\) sú v Nashovom equilibriu, ak žiaden z hráčov nevie zlepšiť svoju stratégiu proti tomu druhému za predpokladu, že ten druhý svoju stratégiu nezmení. Inak povedané, žiadnemu z hráčov sa neoplatí meniť svoju stratégiu – nezlepší si tým priemerný počet získaných bodov.

Známa veta pána Nasha hovorí, že naša hra má Nashovo equilibrium – existujú teda dve stratégie \(P, Q\) také, že sa žiadnemu hráčovi neoplatí meniť stratégiu. Potom musia mať obaja hráči ale očakávaný počet získaných bodov \(0.5\) – každý z hráčov sa totižto môže rozhodnúť skopírovať súperovu stratégiu, a tým by dosiahol zisk presne \(0.5\). My ale vieme, že si týmto nemohol polepšiť (lebo to je Nashovo equilibrium) – takže už predtým musel mať zisk aspoň \(0.5\). Celkový zisk je ale \(1\) – musí to byť preto presne \(0.5\).

To ale znamená, že Mišo vie priradiť riadkom také pravdepodobnosti, aby mal zisk v najhoršom prípade \(0.5\).

Ako nájsť equilibrium?

Niektorí ste sa možno dopátrali ku komplikovaným algoritmom ako Simplex Algorithm alebo Lemke-Howson Algorithm. S našimi obmedzeniami (\(n \leq 9\)) vieme problém vyriešiť aj jednoduchšie.

Predpokladajme, že Mišova stratégia \(P\) je najlepšia – teda má v najhoršom prípade zisk \(0.5\). Potom musí tvoriť dvojica \((P, P)\) Nash equilibrium. Zafixujme stratégiu prvého hráča, a pozrime sa na to, ako by mohol druhý hráč zlepšiť svoj zisk odklonom od stratégie \(P\). Povedzme, že by si v kole vybral stĺpec \(s\). Potom očakávaný zisk je

\[(p_1, p_2, \ldots, p_n) \cdot (A_{1, s}, A_{2, s}, \ldots, A_{n, s})\]

a je nanajvýš \(0.5\), lebo \(P\) je najlepšia stratégia. Ak to nie je \(0.5\), musí to byť menej ako \(0.5\). Potom ale \(P\) nikdy nemôže hrať tento vrchol \(s\) – ak by ho hral, tak by mal celkový zisk menší ako \(0.5\). A to nemôže, lebo keď máme proti sebe dve identické stratégie, tak zisk oboch hráčov musí byť \(0.5\).

Dostávame tak kľúčové pozorovanie – pre každé \(s \in \lbrace 1, 2, \ldots, n \rbrace\) platí, že buď \(p_s = 0\), alebo

\[(p_1, p_2, \ldots, p_n) \cdot (A_{1, s}, A_{2, s}, \ldots, A_{n, s}) = 0.5\]

Môžeme preto postupovať takto: pre každý vrchol si tipneme, ktorá z týchto možností nastala. Dostaneme tak dve množiny vrcholov – prvá množina obsahuje vrcholy, ktorým priradíme pravdepodobnosť výberu \(0\). Druhá množina obsahuje tie vrcholy \(s\), ktoré spĺňajú

\[(p_1, p_2, \ldots, p_n) \cdot (A_{1, s}, A_{2, s}, \ldots, A_{n, s}) = 0.5\]

Týchto rovníc máme \(k\), kde \(k\) je počet vrcholov v druhej množine. Máme teda \(k\) rovníc o \(k\) neznámych (lebo pre \(n - k\) vrcholov z prvej množiny platí \(p_i = 0\)) – na vyriešenie použijeme Gaussovu elimináciu. Takto ale iba získame kandidáta, nemusí to byť ešte hľadaná najlepšia stratégia (vieme ale, že niektorá z nich bude najlepšia). Preto na záver musíme ešte overiť

1. Či sú vypočítané hodnoty naozaj pravdepodobnosti, teda či sú aspoň \(0\) a najviac \(1\). (Môže sa nám totiž stať, že nám vyjdu hodnoty niektorých premenných záporné alebo väčšie ako \(1\).)

2. Či to je naozaj najlepšia stratégia. To znamená, že nech si protivník zvolí ľubovoľný z vrcholov \(1, 2, \ldots, n\), v každom prípade máme zisk zisk aspoň \(0.5\).

Časová zložitosť je \(O(2^n \cdot n^3)\) – máme \(2^n\) tipov, a v každom robíme Gaussovu elimináciu na matici s \(k \leq n\) rovnicami a \(k\) neznámymi.