M7190 Teorie her

Úvodní informace
1. přednáška
2. přednáška
3. přednáška
4. přednáška
5. přednáška
6. přednáška
7. přednáška
8. přednáška
Teorie sociálního výběru
Hry v rozšířené formě (poziční hry)
Hry s neúplnou informací

Úvodní informace

Ukončení

písemná zkouška
- zpracování (nějaké) hry
- 2 hodiny (klidně i déle)
jsou k dispozici skripta ve studijních materiálech (je povolená na zkoušku - pouze tento text)
maximálně 3 neomluvené absence

Náplň

hra v normální formě
- hlavně tohle
- maticové, případně bimaticové, hry
opakované hry
- konečné i nekonečné
poziční hry
na závěr semestru koaliční hry a funkce sociálního rozhodování (volební systémy)

1. přednáška

$$ \xdef\scal#1#2{\langle #1, #2 \rangle} \xdef\norm#1{\left\lVert #1 \right\rVert} \xdef\dist{\rho} \xdef\and{\&}\xdef\AND{\quad \and \quad}\xdef\brackets#1{\left\{ #1 \right\}} \xdef\parc#1#2{\frac {\partial #1}{\partial #2}} \xdef\mtr#1{\begin{pmatrix}#1\end{pmatrix}} \xdef\bm#1{\boldsymbol{#1}} \xdef\mcal#1{\mathcal{#1}} \xdef\vv#1{\mathbf{#1}}\xdef\vvp#1{\pmb{#1}} \xdef\ve{\varepsilon} \xdef\l{\lambda} \xdef\th{\vartheta} \xdef\a{\alpha} \xdef\vf{\varphi} \xdef\Tagged#1{(\text{#1})} \xdef\tagged*#1{\text{#1}} \xdef\tagEqHere#1#2{\href{#2\#eq-#1}{(\text{#1})}} \xdef\tagDeHere#1#2{\href{#2\#de-#1}{\text{#1}}} \xdef\tagEq#1{\href{\#eq-#1}{(\text{#1})}} \xdef\tagDe#1{\href{\#de-#1}{\text{#1}}} \xdef\T#1{\htmlId{eq-#1}{#1}} \xdef\D#1{\htmlId{de-#1}{\vv{#1}}} \xdef\conv#1{\mathrm{conv}\, #1} \xdef\cone#1{\mathrm{cone}\, #1} \xdef\aff#1{\mathrm{aff}\, #1} \xdef\lin#1{\mathrm{Lin}\, #1} \xdef\span#1{\mathrm{span}\, #1} \xdef\O{\mathcal O} \xdef\ri#1{\mathrm{ri}\, #1} \xdef\rd#1{\mathrm{r}\partial\, #1} \xdef\interior#1{\mathrm{int}\, #1} \xdef\proj{\Pi} \xdef\epi#1{\mathrm{epi}\, #1} \xdef\grad#1{\mathrm{grad}\, #1} \xdef\gradT#1{\mathrm{grad}^T #1} \xdef\gradx#1{\mathrm{grad}_x #1} \xdef\hess#1{\nabla^2\, #1} \xdef\hessx#1{\nabla^2_x #1} \xdef\jacobx#1{D_x #1} \xdef\jacob#1{D #1} \xdef\subdif#1{\partial #1} \xdef\co#1{\mathrm{co}\, #1} \xdef\iter#1{^{[#1]}} \xdef\str{^*} \xdef\spv{\mcal V} \xdef\civ{\mcal U} \xdef\other#1{\hat{#1}} $$

V jakémsi smyslu zobecnění optimalizace, kdy máme více hráčů

Úvodní příklad (hra ultimátum)

Mějme $I = [0, 1]$ a 1. hráč si vybere $x \in I$ a 2. hráč říká ano/ne na vybrané $x$.

Hry v normální formě

Definice $\D{HNF}$ (Hra v normální formě)

Mějme $n \in \N$ a $N = \set{1, 2, \dots, n}$ je množina hráčů. A zaveďme

$X_i$ - množina strategií $i$-tého hráče
$u_i$ - výherní funkce $i$-tého hráče ($\prod$ je zde kartézský součin)
$$u_i : \prod_{i \in N} X_i \to \R$$

Navíc předpokládáme, že hráči hrají "rozumně" a "ví všechno" (tj. znají množiny strategií ostatních hráčů i jejich výherní funkce).

Řekneme, že strategie $x_i$ dominuje $y_i$, značíme $ x_i \succ y_i$. Navíc značíme $x_{\other i} = (x_1, \dots, x_{i - 1}, x_{i+1}, \dots, x_n)$ a pak $$ u_i(x_i, x_{\other i}) \geq u_i(y_i, x_{\other i}) \quad \forall x_{\other i} \quad \and \quad \exists x_{\other i} \quad u_i(x_i, x_{\other i}) > u_i(y_i, x_{\other i}) $$

Strategie $x$ je nedominovaná, jestliže neexistuje $y \succ x$.

Pokračování úvodního příkladů

$$ X_1 = I \ X_2 = \set{0,1}^I, $$ kde $\set{0,1}^I$ je množina zobrazení z $I$ do $\set{0,1}$. Pak výherní funkce jsou $$ u_1(x, f) = \begin{cases} x, & \text{ pro } f(x) = 1 \ 0, & \text{ pro } f(x) = 0 \end{cases} $$ $$ u_2(x, f) = \begin{cases} 1 - x, & \text{ pro } f(x) = 1 \ 0, & \text{ pro } f(x) = 0 \end{cases} $$

Pro 1. hráče jistě $0 \prec x$ pro $x \neq 0$, protože $$ u_i(0, f_{\other i}) = 0 $$ ale $$ u_i(x, f_{\other i}) = \begin{cases} x, & \text{ pro } f(x) = 1 \ 0, & \text{ pro } f(x) = 0 \end{cases} \geq 0 $$ Pro 2. hráče $f \prec g$ nastane právě tehdy, když v $g$ souhlasíme ve více případech, tj. $$ \forall x : f(x) = 1 \implies g(x) = 1 \quad \and \quad \exists x : f(x) = 0 \land g(x) = 1 $$ Jinak zapsáno $f < g$.

Nyní předpokládejme $x \prec y, \; x,y > 0, x \neq y$, tj. hledáme $$ f : u_1(x, f_{\hat i}) > u_1(y, f_{\hat i}) $$ a pak stačí libovolná $f$, že $f(x) = 1, f(y) = 0$, z čehož dostaneme $1 > 0$.

Z pohledu řešení hry je rozumné neuvažovat libovolné dominované strategie. Tímto jsme ji ale vytrhli z kontextu. Tedy zde by si odmítnutím "budoval prestiž" na další hry. Zde by totiž 1. hráč si mohl vzít (skoro) celý interval (rohlík) a podle nedominované strategie by to 2. hráč přijal.

Definice $\D{SIT}$ (Situace)

Sitaucí nazveme $n$-tici $(x_1, \dots, x_n) \in \prod_{i \in N} X_i$.

Řekneme, že situace $\vv x = (x_1, \dots, x_n)$ dominuje podle Pareta sitauci $\vv y = (y_1, \dots, y_n)$, pokud $$ \forall i \in N : u_i (\vv x) \geq u_i (\vv y) \AND \exists i \in N : u_i (\vv x) > u_i (\vv y) $$

Pokračování úvodního příkladů

Například $x = \frac 2 3$ a $f(x) = \begin{cases} 1, & x \leq \frac 1 2 \ 0, & \text{jinak}\end{cases}$.

V tomto případě pro $(x, f)$ mají $u_1(x, f) = u_2(x,f) = 0$.

Naopak $y = \frac 1 2$ a $g(x) = \begin{cases} 1, & x \leq \frac 2 3 \ 0, & \text{jinak}\end{cases}$.

V tomto případě pro $(x, f)$ mají $$ u_1(y, g) = u_2(y, g) = \frac 1 2 $$

A tedy $(x,f) \prec (y,g)$ .

Pokud se dohodnou v obou situacích, pak o jejich dominování nemůžeme mluvit - jeden dostane méně, druhý více.

Definice $\D{ZAR}$ (Zaručování)

Hráč $i$ si zaručuje $x$, pokud $$ \exists x_ i : \forall x_ {\other i} : u_ i(x_ i, x_ {\other i}) \geq x $$ Dolní hodnotou hry pro $i$-tého hráče je $$ h^-_ i = \sup _ {x_ i} \inf_ {x_ {\other i}} u_ i (x_i, x_{\other i}) $$

Horní hodnotou hry pro $i$-tého hráče je $$ h^+_ i = \inf_ {x_ i} \sup_ {x_ {\other i}} u_ i (x_i, x_{\other i}) $$

U dolní hodnoty "škodící" hráči dopředu ví, co zahraji (první volíme v infimu, potom až v supremu)

Pro úvodní příklad je $$ h_1^ - = h_2^ - = 0 $$ a $$ h_1^ + = h_2^ + = 0 $$

Definice $\D{ROV}$ (Rovnovážná situace)

Řekneme, že $\vv x$ je rovnovážná situace (Nashova rovnováha), pokud $$ \forall i \in N : \forall y_i \in X_i : u_i(x_i, x_{\other i}) \geq u_i (y_i, x_{\other i}) $$

Pro každého hráče samostatně je dobré hrát takto

Mějme $(x, f)$ pro $x > 0$, pak pro $f(y) = \begin{cases}1, & y \leq x \ 0, & y > x\end{cases}$. Změňme $x \to y$, pak pokud

$y < x$, pak $u_1(x,f) = x$ a $u_1(y,f) = y < x$
$y > x$, pak $u_1(x,f) = x$ a $u_1(y,f) = 0 < x$

Nyní změňme $f \to g$, pak pro $g(x) = 1$ je $u_2(x,f) = x = u_2(x,g)$. Naopak pro $g(x) = 0$ je $u_2(x,g) = 0 \leq u_2(x,f)$.

Hra 2 hráčů

Zde $n = 2$ a značme

$x_1$ jako $x$, $X_1$ jako $X$
$x_2$ jako $y$, $X_2$ jako $Y$
$u_1$ jako $u$
$u_2$ jako $v$

Antagonistická hra je taková, že pro situace $(x,y)$ a $(\bar x, \bar y)$, tak pokud $$ u(x,y) \geq u(\bar x, \bar y) \iff v(x,y) \leq v(\bar x, \bar y) $$

Paretovská dominance vylučuje antagonistickou hru

Hra s konstatním součtem nazýváme hru, kde $$ u(x,y) + v(x,y) = c $$ a speciální případ jsou hry s nulovým součtem, kde $$ u(x,y) + v(x,y) = 0 $$

Šachy jsou hra s konstantím součtem (výhra - 1, remíza - 0.5). Naopak fotbal není (výhra - 3, remíza - 1), ale je antagonistická.

U koopertivních her mají hráči nějakým způsobem možnost dosahovat paretovské dominance

Definice $\D{MAT}$ (Maticová hra)

Mějme hru 2 hráčů, kde množiny $X,Y$ jsou konečné. Pišme $$ X = \set{x_1, \dots, x_k} \AND Y = \set{y_1, \dots, y_l} $$ a pak situace uspořádáme do matice $X \times Y$ následovně

Matice $A,B$ jsou pak výherní matice 1. a 2. hráče a $u(x_i, y_j) = A_{i,j}$.

Je-li navíc $A = - B$, pak jde o maticovou hru, což je hra s nulovým součtem.

Pareto optimální situace je taková, že není dominovaná podle Pareta

2. přednáška

Definice $\D{KON}$ (Konečná hra)

Mějme množinu hráčů $N = \set{1, 2, \dots, n}$. Pak hra $G = (M, X_i, u_i)$ je konečná, pokud jsou $X_i$ konečné.

Na konečných hrách můžeme zavést tzv. pravděpodobností rozšíření

Definice $\D{SYM}$ (Symetrická hra)

Hra $G$ 2 hráčů je symetrická právě tehdy, když $u(x,y) = v(y, x)$. V případě bimaticových her to je ekvivalentní s podmínkou $$ U^T = V $$

Příklad (kámen, nůžky, papír)

Mějme 2 hráče, tj. $N = \set {1, 2}$ a $X = Y = \set{ \mcal K, \mcal N, \mcal P }$. Jelikož je to bimaticová hra, tak výhra je dána jako $$ U = \mtr{ 0 & 1 & -1 \ -1 & 0 & 1 \ 1 & -1 & 0 \ } $$

Sloupce a řádky jsou indexovány $\mcal K, \mcal N, \mcal P$

Podívejme se na Nashovu rovnováhu, tj. $$ u(x,y) \geq u(\bar x, y) \quad \text{pro libovolné } \bar x \ v(x,y) \geq v(x, \bar y) \quad \text{pro libovolné } \bar y \ $$

Aneb si odbočením do jiného řádku si nepomůžeme

Aby nastala rovnováha, tak musí $u(x,y) = 1$, tj. $v(x,y) = 1$. Ale druhý hráč by mohl hrát $\bar y$ tak, že $v(x, \bar y) = 1$.

Zde si všimněme, že pokud půjdeme podle šipek, tak nikdy neskončíme

Dominance by zde znamenalo, že by jeden řádek, byl větší než nějaký jiný - aneb 2 řádky by musely být porovnatelné (jakožto vektory)

Dolní hodnota $$ h_ 1^- = \sup_ x \inf_ y u(x,y) $$

a horní hodnota

Definice $\D{PRA}$ (Pravděpodobnostní rozšíření)

Mějme konečnou hru $G = (M, X_i, u_i)$. Pak definujeme pravděpodobnostní rozšíření $$ G\str = (N, X_i\str, u_i\str), $$ kde $X_i\str = \set{a_i^1 x_i^1 + a_i^2 x_i^2 + \dots + a_i^{m_i} x_i^{m_i} \mid x_i^j \in X_i \; \land \; a_ i^1 + \dots + a_i^{m_ i} = 1 \; \land \; a_i^j > 0}$ je množina konvexních kombinací strategií a pro výhry platí $$ u_i\str(\vv x\str) = \sum_{(x_1^{j_1}, \dots, x_n^{j_n}) \in \prod X_i} a_1^{j_1} a_2^{j_2} \cdot \ldots \cdot a^{j_n}_n \cdot u_i(x^{j_1}_1, \dots, x^{j_1}_n) $$

Pokračování příkladu

Počítejme pravděpodobnostní rozšíření, tj. $$ u\str((p_1, p_2), (q_1, q_2)) = p_1 q_1 \overbrace{u(\mcal K, \mcal K)}^0 + p_1 q_2 \overbrace{u(\mcal K, \mcal N)}^1 + p_1 (1 - q_1 - q_2) u(\mcal K, \mcal P) + \dots $$ kde

$p_1$ je pravděpodobnost zahrání $\mcal K$ prvním hráčem
$p_2$ je pravděpodobnost zahrání $\mcal N$ prvním hráčem
$q_1$ je pravděpodobnost zahrání $\mcal K$ druhým hráčem
$q_2$ je pravděpodobnost zahrání $\mcal N$ druhým hráčem
$1 - p_1 - p_2$ je pravděpodobnost zahrání $\mcal P$ prvním hráčem

To ale můžeme napsat jako $$ u\str((p_1, p_2), (q_1, q_2)) = \mtr{p_1 & p_2 & (1 - p_1 - p_2)} U \mtr{q_1 \ q_2 \ 1 - q_1 - q_2} $$

Potom pro $$ \mtr {1/3 & 1/3 & 1/3} U = \mtr{0 & 0 & 0} \ \mtr{0 & 0 & 0} \mtr{q_1 \ q_2 \ 1 - q_1 - q_2} = 0 $$ Tedy strategie $(1/3, 1/3, 1/3)$ a $(1/3, 1/3, 1/3)$ tvoří rovnovážnou situaci a navíc $$ h_1^{* -} = h_1^{* +} = 0 $$

Prvky $x_1\str \in X_i\str$ nazýváme smíšené strategie a původní strategie do tohoto nového prostoru vnoříme volbou pravděpodobnostího rozdělení $(0, \dots, 0, 1, 0, \dots, 0)$. V tomto smyslu takovým strategiím říkáme čisté strategie

Věta $\D{NASH}$ (Nashova)

Pravděpodobnostní rozšíření každé konečné hry má rovnovážnou situaci.

Důkaz

Mějme rovnováhu $\vv x$, tj. $$ u_i\str(\vv x) \geq u_i\str(x_i\str, x_{\other i}\str) $$ Dále označme $B_i(x_{\other i}\str)$ nejlepší odpovědi na volbu protihráčů $x_{\other i}\str$. Tedy $\vv x$ je rovnováha právě tehdy, když $$ \forall i \in N: \quad x_i\str \in B_i(x_{\other i}\str) $$ Tedy $B_i : \prod_{j \neq i} X_j \str \to \mcal P (X_i\str)$ a pokud dáme $B_i$ dohromady jako $$ B = (B_ i)_ {i \in N}, \qquad B : \prod_ {i \in N} X_i\str \to \prod_{i \in N} \mcal P (X_i\str) $$

Pod $\mcal P$ zde myslíme "power set" (potenční množina) - pro jednu situaci může být více nejlepších strategií (odpovědí)

$B$ je tedy (množinová) funkce na prostoru situací. Podle Kakutanyho věty o pevném bodě existuje $x\str \in B(x\str)$, což je rovnovážná situace. $\blacksquare$

Mějme $$ u(\vv x) = (x) U (y) $$

V rovnovážně situaci nám budou vycházet stěny polyedru

Příklad - využití pro (bi)maticové hry

Mějme $$ U = \mtr{1 & 0 \ 0 & 2}, V = \mtr{0 & 1 \ 2 & 0} $$

Tedy celkem $$ u(p,q) = pq + 2(1-p)(1-q) \ v(p,q) = p(1 - q) + 2(1 - p)q $$

Rovnováha je tak, že druhý hráč nemá kam pohnout (je mu to jedno)

Indiferenční rovnice - chceme zařídit, aby $u$ nezáviselo na $p$ a $v$ na $q$

V našem případě $$ u(p,q) = p(\underbrace{q - 2 + 2q}_0) + 2(1-q) \implies 3q - 2 = 0 \implies q = {2 \over 3} \ v(p,q) = q(\underbrace{-p + 2 - 2p}_0) + p \implies 3p - 2 = 0 \implies p = \frac 2 3 $$

Tedy pravděpodobnostní rozdělení $((2/3, 1/3), (2/3, 1/3))$ tvoří rovnovážnou situaci a $$ u(\vv x\str) = \frac 2 3, \qquad v(\vv x\str) = \frac 2 3 $$

Věta $\D{ANT}$

U antagonistických her platí, že strategie je optimální právě tehdy, když je opatrná. Řekneme, že strategie $x_i$ je opatrná, pokud zaručuje $h_i^-$.

Strategii nazveme optimální, pokud tato strategie realizuje nějakou rovnovážnou situaci

Pokud počítáme $h_1^-$, tak "zjišťujeme, co mi může soupeř provést", tj. $$ \begin{align*} u(p,q) &= q(p - 2 + 2q) + 2(1-p) \ &= q(\underbrace{3p - 2}_0) + 2(1-p) \ &= \frac 2 3 \end{align*} $$

Při zvýšení $p$ dá soupeř $q = 0$ a já si pohorším, naopak s menším $p$ dává soupeř $q = 1$

Tedy $h_1^- = \frac 2 3$ a tato strategie je opatrná.

Pravděpodobnostní rozšíření na nekonečných prostorech se konstruuje přes míry a Riemann-Stiltjesův integrál

3. přednáška

$$ \xdef\scal#1#2{\langle #1, #2 \rangle} \xdef\norm#1{\left\lVert #1 \right\rVert} \xdef\dist{\rho} \xdef\and{\&}\xdef\AND{\quad \and \quad}\xdef\brackets#1{\left\{ #1 \right\}} \xdef\parc#1#2{\frac {\partial #1}{\partial #2}} \xdef\mtr#1{\begin{pmatrix}#1\end{pmatrix}} \xdef\nmtr#1{\begin{matrix}#1\end{matrix}} \xdef\bm#1{\boldsymbol{#1}} \xdef\mcal#1{\mathcal{#1}} \xdef\vv#1{\mathbf{#1}}\xdef\vvp#1{\pmb{#1}} \xdef\ve{\varepsilon} \xdef\l{\lambda} \xdef\th{\vartheta} \xdef\a{\alpha} \xdef\vf{\varphi} \xdef\Tagged#1{(\text{#1})} \xdef\tagged*#1{\text{#1}} \xdef\tagEqHere#1#2{\href{#2\#eq-#1}{(\text{#1})}} \xdef\tagDeHere#1#2{\href{#2\#de-#1}{\text{#1}}} \xdef\tagEq#1{\href{\#eq-#1}{(\text{#1})}} \xdef\tagDe#1{\href{\#de-#1}{\text{#1}}} \xdef\T#1{\htmlId{eq-#1}{#1}} \xdef\D#1{\htmlId{de-#1}{\vv{#1}}} \xdef\conv#1{\mathrm{conv}\, #1} \xdef\cone#1{\mathrm{cone}\, #1} \xdef\aff#1{\mathrm{aff}\, #1} \xdef\lin#1{\mathrm{Lin}\, #1} \xdef\span#1{\mathrm{span}\, #1} \xdef\O{\mathcal O} \xdef\ri#1{\mathrm{ri}\, #1} \xdef\rd#1{\mathrm{r}\partial\, #1} \xdef\interior#1{\mathrm{int}\, #1} \xdef\proj{\Pi} \xdef\epi#1{\mathrm{epi}\, #1} \xdef\grad#1{\mathrm{grad}\, #1} \xdef\gradT#1{\mathrm{grad}^T #1} \xdef\gradx#1{\mathrm{grad}_x #1} \xdef\hess#1{\nabla^2\, #1} \xdef\hessx#1{\nabla^2_x #1} \xdef\jacobx#1{D_x #1} \xdef\jacob#1{D #1} \xdef\subdif#1{\partial #1} \xdef\co#1{\mathrm{co}\, #1} \xdef\iter#1{^{[#1]}} \xdef\str{^*} \xdef\spv{\mcal V} \xdef\civ{\mcal U} \xdef\other#1{\hat{#1}} $$

Přehled her

Bimaticové hry 2x2

Mějme $$ A = \mtr{a & b \ c & d}, \quad B = \mtr{e & f \ g & h} $$

V případě dominování, např. $a > b \;\and\; c > d$ , je to jednoduché... Tedy předpokládejme, že žádný řádek nedominuje pro 1. hráče a žádný sloupec pro 2. hráče.

A tedy $$ u(p,q) = \mtr{p & 1-p} A \mtr{q \ 1-q}, \ v(p,q) = \mtr{p & 1-p} B \mtr{q \ 1-q} $$

Rovnováhy

Hráč 2 chce zabránit volit tomu prvnímu a tedy indiferenční rovnice je tvaru $$ u(0, q) = u(1,q) \ \mtr{c & d} \mtr{q \ 1-q} = \mtr{a & b} \mtr{q \ 1-q} \ (c - d)q + d = (a - b)q + b \ (a-b-c+d)q = d-b $$ $$ q = {d-b \over a - b - c + d} $$ a opačně $$ v(p,0) = v(p,1) \ \mtr{p & 1 - p} \mtr{f \ h} = \mtr{p & 1 - p} \mtr{e \ g} \ \mtr{p & 1 - p} \mtr{f-e \ h-g} = 0 \ p(f-e-h+g) - h-g = 0 $$ $$ p = {g-h \over f-e-g+h} $$

Pak tedy rovnovážná strategie ve smíšených strategiích je tvaru $(p,q)$

Dolní hodnota

Počítejme $h_1^-$ a tedy bychom chtěli zjistit, jak máme volit $p$, aby nám bylo jedno, jak hraje 2. hráč $$ u(p, 0) = u(p,1) \ \mtr{p & 1 - p} \mtr{b \ d} = \mtr{p & 1 - p} \mtr{a \ c} \ \vdots $$ $$ p = {d-c \over a-b-c+d} $$

Příklady her 2x2

Mějme $$ A = \mtr{1 & -2 \ -3 & 4} \to \mtr{4 &1 \ 0 & 7} \to \mtr{4/7 & 1/7 \ 0 & 1} $$

Normalizace hry: První posunume hru do kladných čísel, pak ji "zmenšíme" tak, že největší výhra 1 Tj.

$\min A = 0$
$\max A = 1$

Pozor, pořád jsou to ekvivalentní hry!!

Přehled základních her 2x2

Prozkoumejme čtveřici $(0, 1, 2, 3)$

mince $$ A = \mtr{1 & 0 \ 0 & 1}, \quad B = \mtr{0 & 1 \ 1 & 0} $$ tato hra není symetrická, ale je "spravedlivá" (kdyby si vyměnili role, tak jim to nepomůže). Zřejmě ani jeden z hráčů nemá dominovanou strategii. Počítejme rovnováhu $$ q = {1-0 \ 1 - 0 - 0 + 1}= \frac 1 2 = \dots = p $$ a rovnováha je $(p,q) = (\frac 1 2, \frac 1 2)$. Přičemž dolní hodnota $$ q = \frac {1-0} {1 -0 - 0 + 1} = \frac 1 2 $$ a proto $h_1^- = \frac 1 2$
na kočku a myš
Kočka má na výběr z vytápěné/nevytápěné místnosti (světice/komora) $$ A = \mtr{3 & 1 \ 0 & 2}, \quad B = \mtr{0 & 3 \ 2 & 1} $$
A tedy máme situace $$ (3, 0) \quad (1,3) \succ (0,2) \quad (1,2) $$ Tato hra není ani antagonistická, ani s nulovým součtem. Evidentně existuje rovnováha pouze v smíšených situacích
líný rodič
Rodiče chtějí, aby potomek přežil, ale chceme se flákat a nechat to na tom druhém. Je to jistě symetrická hra $$ \nmtr{\text{stará se} \ \text{nestará se}} \mtr{2 & 1 \ 3 & 0}, \qquad ()^T = \mtr{2 & 3 \ 1 & 0} $$ a potom máme situace $$ (0,0) \prec (2,2), \underbrace{(1,3), (3,1)}_ {\textbf{rovnováhy} \text{ v čistých}} $$ Rozhodně nejde o hru, která aby antagonistická nebo s nulovým součtem.
Ve smíšených strategiích $$ q = {d-b \over a - b - c + d} = \frac {-1} {-2} = \frac 1 2 = \text{symetrie} = p $$ a tedy $u(\frac 1 2, \frac 1 2) = \mtr{\frac 1 2 & \frac 1 2} \mtr{\frac 1 2 \ \frac 1 2} = \frac 3 2$. Tedy je lepší, aby se oba rodiče starali, než kdyby to nechali na náhodu
na kuře
Jedeme proti sobě autem a pokud uhnu dřív, než soupeř, tak jsem prohrál a jsem zbabělec $$ \nmtr{\text{uhnu} \ \text{zůstanu}} \mtr{0 & -1 \ 1 & -10} $$ Po normalizaci dostaneme hru tvaru líný rodič.
lov na jelena
Máme 2 lovce, kteří se nemohou domluvit. Pokud loví dohromady, tak mají šanci ulovit jelena, ale jeden sám ho neuloví. Navíc můžeme ulovit max 2 zajíce, kteří jsou v lese. $$ \nmtr{\text{jdu na jelena} \ \text{jdu na zajíce}} \mtr{3 & 0 \ 2 & 1} \; \and \; \mtr{3 & 2 \ 0 & 1} $$ Potom situace rovnováhy jsou $(1,1), (3,3)$, přičemž z ní "jednostraně" nemůžeme uhnout. Navíc $(3,3)$ je dominující strategií (je optimální). Jediná opatrná strategie je zde jít si pro zajíce.

Ilustruje, že příroda si může vybrat rovnováhu, která není nejlepší - přechod na nejlepší rovnováhu by vyžadoval domluvu.

vězňovo dilema
Máme 2 vězně, kde každý má na výběr buď mlčet (spolupracovat s spolupachatelem) nebo to zkusím hodit na spolupachatele (zradit). Jistě je to navíc symetrická hra $$ \nmtr{\text{spolupracovat} \ \text{zradit}} \mtr{-1 & -3 \ 0 & -2} \to \mtr{2 & 0 \ 3 & 1} $$ Po normalizaci si snažíme maximalizovat roky na svobodě (snažíme si ušetřit trest). Jistě navíc $$ \text{spolupracovat} \prec \text{zradit} $$ Přičemž $(2,2)$ je jediná rovnovážná situace i ve smíšených strategiích.

V případě opakované hry se rozhodujeme v závislosti na předchozích rozhodnutích. Můžeme řešit pomocí stavového automatu:
a celkem
Přičemž automaty jsou "strategie s omezenou pamětí"

4. přednáška

$$ \xdef\scal#1#2{\langle #1, #2 \rangle} \xdef\norm#1{\left\lVert #1 \right\rVert} \xdef\dist{\rho} \xdef\and{\&}\xdef\AND{\quad \and \quad}\xdef\brackets#1{\left\{ #1 \right\}} \xdef\parc#1#2{\frac {\partial #1}{\partial #2}} \xdef\mtr#1{\begin{pmatrix}#1\end{pmatrix}} \xdef\nmtr#1{\begin{matrix}#1\end{matrix}} \xdef\bm#1{\boldsymbol{#1}} \xdef\mcal#1{\mathcal{#1}} \xdef\vv#1{\mathbf{#1}}\xdef\vvp#1{\pmb{#1}} \xdef\ve{\varepsilon} \xdef\l{\lambda} \xdef\th{\vartheta} \xdef\a{\alpha} \xdef\vf{\varphi} \xdef\Tagged#1{(\text{#1})} \xdef\tagged*#1{\text{#1}} \xdef\tagEqHere#1#2{\href{#2\#eq-#1}{(\text{#1})}} \xdef\tagDeHere#1#2{\href{#2\#de-#1}{\text{#1}}} \xdef\tagEq#1{\href{\#eq-#1}{(\text{#1})}} \xdef\tagDe#1{\href{\#de-#1}{\text{#1}}} \xdef\T#1{\htmlId{eq-#1}{#1}} \xdef\D#1{\htmlId{de-#1}{\vv{#1}}} \xdef\conv#1{\mathrm{conv}\, #1} \xdef\cone#1{\mathrm{cone}\, #1} \xdef\aff#1{\mathrm{aff}\, #1} \xdef\lin#1{\mathrm{Lin}\, #1} \xdef\span#1{\mathrm{span}\, #1} \xdef\O{\mathcal O} \xdef\ri#1{\mathrm{ri}\, #1} \xdef\rd#1{\mathrm{r}\partial\, #1} \xdef\interior#1{\mathrm{int}\, #1} \xdef\proj{\Pi} \xdef\epi#1{\mathrm{epi}\, #1} \xdef\grad#1{\mathrm{grad}\, #1} \xdef\gradT#1{\mathrm{grad}^T #1} \xdef\gradx#1{\mathrm{grad}_x #1} \xdef\hess#1{\nabla^2\, #1} \xdef\hessx#1{\nabla^2_x #1} \xdef\jacobx#1{D_x #1} \xdef\jacob#1{D #1} \xdef\subdif#1{\partial #1} \xdef\co#1{\mathrm{co}\, #1} \xdef\iter#1{^{[#1]}} \xdef\str{^*} \xdef\spv{\mcal V} \xdef\civ{\mcal U} \xdef\other#1{\hat{#1}} $$

Opakované hry

Znovu definujme strategii, jako celkový vzorec chování (algoritmus, kterým vybíráme akci pro dané kolo). Akce je výběr pro dané kolo.

Rozdělme si je na

konečné opakování
nekonečné opakování

Konečné vězňovo dilema

Mějme matici hry $$ \begin{matrix} \text{spolupracovat} \ \text{zradit} \end{matrix} \mtr{ 2 & 0 \ 3 & 1 } $$

V 1 kolové hře bylo logické zradit

Nyní předpokládejme, že ji budeme hrát $2 \times$:

Jistě v 2. druhém kole bude výhodné zradit ($ZZ$)
Jelikož v 2. kole dávalo smysl pouze zradit, tak i v prvním kolem budeme zrazovat, protože 2. kolo stejně nijak neovlivníme

Obecně pro konečné opakování vězňova dilematu vede k výsledku $ZZ$ pro všechna kola

Nekonečné vězňovo dilema

Můžeme interpretovat, že nevíme, které kolo je poslední.

Celkovou výhru si definujme jako:

Mějme výhry prvního hráče v $i$-tém kole $$ u_1, u_2, \dots $$ Pak vezmeme částečný průměr, který pošleme do limity, jako výhru, tj. $$ u = \lim_{n \to \infty} \frac {u_1 + \dots + u_n} n $$ Avšak pro například řadu výher $$ 1, 0, \underbrace{1}_ {\frac 1 2}, 0, 0, \underbrace{1}_ {\frac 1 4}, 1, 1, 1, 1, 1, 1, 1, 1, \underbrace{1}_{\frac 3 4}, \dots $$

Tedy částečné průměry nefungují obecně
Pomocí disktování
Zaveďme $\delta \in (0,1)$ (diskontní faktor) a pak $$ \bar u_1 = \delta u_1 \ \bar u_2 = \delta^2 u_2 \ \vdots \ \bar u_n = \delta^n u_n $$

Tedy v tomto případě mají větší hodnotu "peníze" (výhra), která je teď. Navíc je degradace hry pořád stejná
Velké $\delta$ můžeme interpretovat jako "střadatele"... Pro malé $\delta$ "žije hráč okamžikem" $$ u = \delta u_1 + \delta^2 u_2 + \dots $$ Lze vždy sečíst
Overtaking
Pro 2 posloupnosti výher $$ u_1, u_2, \dots \ \bar u_1, \bar u_2, \dots $$ Pak řekneme, že $u_i \succ \bar u_i$ pokud $\liminf_{n \to \infty} (u_1 - \bar u_1) + \dots + (u_n - \bar u_n) > 0$

Z pohledu psycholgie je pro nás důležitější výsledek "ve většině případů"

Jsou-li strategie hráčů dány konečnými automaty, pak lze výhry sečíst částečným průměrováním.

Vybrané strategie pro vězňovo dilema

Spoušť (Trigger)

Hodí se pro existenční důkazy

Oko za oko (TFT - Tit For Tat)

Hrdlička a Jestřáb (Always Cooperate (AllC) / Always Defect (AllD))

Pavlov (pes) (Win Stay Lose Switch - WSLS)

Často zavádíme šum $\ve > 0$ a předpokládáme, že hráč dodrží svou strategii (plán své strategie) s pravděpodobností $1 - \ve$, tj. s pravděpodobností $\ve$ dojde k zahrání opačné akce.

Podívejme se nyní na

TFT vs. TFT

Možné stavy

Počítejme výhru prvního částečným průměrováním $$ u = \frac 1 4 \cdot 2 + \frac 1 2 \frac {0 + 3} 2 + \frac 1 4 \cdot 1 = \frac 3 2 $$

Oko za oko je trochu moc přísné

WSLS vs. WSLS

Přičemž $$ u \approx 2 - \ve x $$

TFT vs. WSLS

Turnaj


X	S	O	H	J	P	$\sum$
S	$\approx 1$	$\approx 1$	$\approx 5/2$	$\approx 1$	$\approx 1$	$\approx \frac {13} 2$
O
H
J					$2$
P				$\frac 1 2$

Pokud je hodně "pes" strategií v Turnaji, tak vyhraje, protože spolu dobře spolupracuje

V "evoluční/populační" variantě, tj. necháváme potomky dobrých strategií v turnaji, často vyhraje pes, protože hraje dobře sám se sebou

Naopak je vidět, že Jestřáb umí vytěžit psa

Strategie se stochastickými přestupy

Šlechetné oko

nebo můžeme udělat novou parametrizaci

$p_0$ - pravděpodobnost spoluprací na začátku
- $1 - p_0$ - začnu zradou
$p_1$ - pst. přechodu od SS ke spolupráci
$p_2$ - pst. přechodu od SZ ke spolupráci
$p_3$ - pst. přechodu od ZS ke spolupráci
$p_4$ - pst. přechodu od ZZ ke spolupráci

	$\to$ S	SS $\to$ S	SZ $\to$ S	ZS $\to$ S	ZZ $\to$ S
X	$p_0$	$p_1$	$p_2$	$p_3$	$p_4$	šum
J	0	0	0	0	0	$(\ve, \ve, \ve, \ve, \ve)$
H	1	1	1	1	1	$(1 - \ve, \dots)$
S	1	1	0	0	0
O	1	1	0	1	0
P	1	1	0	0	1
ŠO	1	1	$\frac 1 2$	1	$\frac 1 2$

Všechny zmíněme byly tzv. jednopaměťové strategie, tzn. akce vychází pouze z předchozího kola

V Axelrodově turnaji byly i strategie s delší pamětí, ale nebyly moc dobré

V této parametrizaci v evolučním vývoji nastalo

Je to svým způsobem analogie pravděpodobnostního rozšíření, kdy strategie definujeme jako pětice parametrů

Jak dopadne $(p_0, \dots, p_4)$ proti $(q_0, \dots, q_4)$?

5. přednáška

$$ \xdef\scal#1#2{\langle #1, #2 \rangle} \xdef\norm#1{\left\lVert #1 \right\rVert} \xdef\dist{\rho} \xdef\and{\&}\xdef\AND{\quad \and \quad}\xdef\brackets#1{\left\{ #1 \right\}} \xdef\parc#1#2{\frac {\partial #1}{\partial #2}} \xdef\mtr#1{\begin{pmatrix}#1\end{pmatrix}} \xdef\nmtr#1{\begin{matrix}#1\end{matrix}} \xdef\bm#1{\boldsymbol{#1}} \xdef\mcal#1{\mathcal{#1}} \xdef\vv#1{\mathbf{#1}}\xdef\vvp#1{\pmb{#1}} \xdef\ve{\varepsilon} \xdef\l{\lambda} \xdef\th{\vartheta} \xdef\a{\alpha} \xdef\vf{\varphi} \xdef\Tagged#1{(\text{#1})} \xdef\tagged*#1{\text{#1}} \xdef\tagEqHere#1#2{\href{#2\#eq-#1}{(\text{#1})}} \xdef\tagDeHere#1#2{\href{#2\#de-#1}{\text{#1}}} \xdef\tagEq#1{\href{\#eq-#1}{(\text{#1})}} \xdef\tagDe#1{\href{\#de-#1}{\text{#1}}} \xdef\T#1{\htmlId{eq-#1}{#1}} \xdef\D#1{\htmlId{de-#1}{\vv{#1}}} \xdef\conv#1{\mathrm{conv}\, #1} \xdef\cone#1{\mathrm{cone}\, #1} \xdef\aff#1{\mathrm{aff}\, #1} \xdef\lin#1{\mathrm{Lin}\, #1} \xdef\span#1{\mathrm{span}\, #1} \xdef\O{\mathcal O} \xdef\ri#1{\mathrm{ri}\, #1} \xdef\rd#1{\mathrm{r}\partial\, #1} \xdef\interior#1{\mathrm{int}\, #1} \xdef\proj{\Pi} \xdef\epi#1{\mathrm{epi}\, #1} \xdef\grad#1{\mathrm{grad}\, #1} \xdef\gradT#1{\mathrm{grad}^T #1} \xdef\gradx#1{\mathrm{grad}_x #1} \xdef\hess#1{\nabla^2\, #1} \xdef\hessx#1{\nabla^2_x #1} \xdef\jacobx#1{D_x #1} \xdef\jacob#1{D #1} \xdef\subdif#1{\partial #1} \xdef\co#1{\mathrm{co}\, #1} \xdef\iter#1{^{[#1]}} \xdef\str{^*} \xdef\spv{\mcal V} \xdef\civ{\mcal U} \xdef\other#1{\hat{#1}} $$

Klasifikace 2x2 her

Předpokládejme, že máme hru $$ \mtr{ 0 & a \ b & 1 }, $$ kde $0 \leq a \leq b \leq 1$, což v extrémech odpovídá

$a$	$b$	1
1	1	1
0	0	1
0	1	1

Tady změna krychle odpovídá změně jedné nerovnosti

Opakované hry

Mějme strategii v 1-paměťovém prostředí $(p_0, p_1, p_2, p_3, p_4)$, kde

$p_0$ - pravděpodobnost spolupráce $S$ na začátku (v 1. kole)
$p_1$ - pravděpodobnost spolupráce $S$ po $SS$
$p_2$ - pravděpodobnost spolupráce $S$ po $SZ$
$p_3$ - pravděpodobnost spolupráce $S$ po $ZS$
$p_4$ - pravděpodobnost spolupráce $S$ po $ZZ$

$1 - p_i$ je pravděpodobnost zrady $Z$ po $\dots$

A nechť soupeř má strategii $(q_0, q_1, q_2, q_3, q_4)$, přičemž si uvědomme, že ZS pro nás je SZ pro něj apod.

Napišme si výherní matici do řádku do výherního vektoru $$ w = \underbrace{(w_1, w_2, w_3, w_4)}_{(SS, SZ, ZS, ZZ)} $$

A pak výhru v $n$-tém kolem dostaneme jako $$ (u(p,q))_n = w \cdot \mtr{P_1 \ \vdots \ P_4}, $$ kde $P_i$ je pravděpodobnost, že hra dospěla do stavu $SS, SZ, ZS, ZZ$

Vektor $\mtr{P_1 \ \vdots \ P_4}$ určíme pomocí teorie markovských řetězců. Spočítejme si přechodovou matici $A$ - ta bude mít tvar $$ A = \begin{matrix} SS \ SZ \ ZS \ ZZ \end{matrix}\underbrace{\mtr{ p_1 q_1 & p_2 q_3 & p_3 q_2 & p_4 q_4\ p_1 (1 - q_1) & p_2 (1 - q_3) & p_3 (1 - q_2) & p_4 (1 - q_4) \ (1-p_1)q_1 & (1 - p_2)q_3 & (1 - p_3) q_2 & (1 - p_4) q_4 \ (1 - p_1)(1 - q_1) & (1- p_2) (1 - q_3) & (1 - p_3) (1 - q_2) & (1 - p_4) (1 - q_4) }}_{SS, SZ, ZS, ZZ} $$

A pak jistě platí $$ P = A^n \mtr{ p_0 q_0 \ p_0 (1 - q_0) \ \vdots } $$

Za předpokladu stability se neprojeví počáteční vektor $\mtr{ p_0 q_0 \ p_0 (1 - q_0) \ \vdots }$, ale hra dospěje do vektoru $\vv x$ takového, že $A \vv x = \vv x$

Matice $A$ musí být pravděpodobností, tj. suma v každém sloupci musí být 1.

Tento problém řešíme jako $$ A \vv x = x \ (A - I)\vv x = 0, $$ kde $\vv x$ říkáme stacionární vektor (z lingebry dostaneme, že řešení musí jediné až na násobek), který také musí být pravděpodobnostní, tj. $\sum \vv x = 1$.

Rozepišme si $$ A- E = \mtr{ p_1 q_1 - 1 & p_2 q_3 & p_3 q_2 & p_4 q_4\ p_1 (1 - q_1) & p_2 (1 - q_3) - 1 & p_3 (1 - q_2) & p_4 (1 - q_4) \ (1-p_1)q_1 & (1 - p_2)q_3 & (1 - p_3) q_2 - 1 & (1 - p_4) q_4 \ (1 - p_1)(1 - q_1) & (1- p_2) (1 - q_3) & (1 - p_3) (1 - q_2) & (1 - p_4) (1 - q_4) - 1 }, $$ což řešme pomocí Cramerova pravidla

a tedy $$ \vv x_1 = \frac {|B_1|} {|B|} $$

kde $B_1$ je matice, kde jsme 1. sloupec vyměnili za sloupec pravých stran

V tuto chvíli, pokud budeme pouze sčítat řádky, tak se nám nemění determinant. Tedy přičtěme 1. řádek z $B$ k tomu 2. a 3., tj.

A proveďme Laplaceův rozvoj podle 1. řádků pro $B_1$

Obdobně bychom postupovali i pro $B_2$

Celkem naše výhra $$ u = w_1 \vv x_1 + w_2 \vv x_2 + \dots \ u = w_1 \frac {|B_1|} {|B|} + w_2 \frac {|B_2|} {|B|} + \dots \ u = \frac{w_1 |B_1| + w_2 |B_2| + \dots} {|B|}, $$ přičemž jmenovatel můžeme vnímat jako Laplaceův rozvoj pro $B$, kde místo vektoru $1$ jsme dali vektor $w$, tj.

Celkem výhru dostaneme jako $$ u = \frac {|C|} {|B|} $$

Uvědomme si, že každá proměnná je lineárné v každém z determinantů (vyskytuje se vždy pouze v jednom sloupci), tj. $$ u = \frac{\alpha p_i + \beta} {\gamma p_i + \delta} $$

Počítejme optimální vektor $(p_1, \dots, p_4)$, tedy $$ \parc u {p_i} = \frac{\alpha(\gamma p_i + \delta) - (\alpha p_i + \beta) \gamma}{(\gamma p_i + \delta)^2} \ \parc u {p_i} = \frac{\alpha \delta - \beta \gamma}{\underbrace{(\gamma p_i + \delta)^2}_{> 0}} $$

Tedy to znamená, že řešíme znaménko pouze u $\alpha \delta - \beta \gamma$

Tedy se výhra řídí ryze rostoucí, či ryze klesající, funkcí v každém parametru

Celkem nejlepší protihra (odpověď) se realizuje nějakou "rohovou" strategií, tj. volbou $p_i \in \set{0,1}$ (nebo s šumem $\set{\ve, 1 - \ve}$)

Případě, že nám vyjde parciální derivace nulová, tak dostaneme "nerohové strategie", což odpovídá celé jedné stěně hyperkrychle $[0,1]^4$.

Spočítejme si nyní onu parciální derivaci "pořádně":

Z tohoto dostáváme podle Dasnanotovy-Jacobiho formule

ve smyslu jejího značení $$ |A| = \left|\begin{matrix} p_2 q_3 & \dots \ p_2 - 1 & \dots \ q_3 & \dots \end{matrix}\right| $$

V této formě to na zkoušce nebude

Speciální strategie v IPD

ekvalizátor - soupeř si volí $\vv q$ tak, aby $u$ byla konstatní
- realizuje se lineární závislostí $\mtr{q_1 & q_3 & q_2 - 1 & q_4}, \mtr{1 & 1 & 1 & 1}$ a $\mtr{w_1 & w_2 & w_3 & w_4}$
- některé determinanty jsou zde nulové
0-determinant (ZD-strategie)
- rozdíl mezi $u$ a $v$ je prohození $w_2$ a $w_2$ (je to symetrická hra)
- $v$ se liší od $v$ vektorem výher $\bar w = \mtr{w_1 & w_3 & w_2 & w_4}$
- $$ u = \frac {|w|} {|1|}, \qquad v = \frac {|\bar w|} {|1|} $$ a $$ \left|\begin{matrix} q_1 & \dots & q_4 \ 1 & \dots & 4 \ w_1 & \dots & w_4 \ w_1 & \searrow \hspace{-10pt}\swarrow & w_4 \end{matrix}\right| $$
- jsou tzv. vyděračské strategie

6. přednáška

Pokračování

Počítali jsme stacionární vektor $\vv x$ pro přechodovou matici $A$, tj. $$ A \vv x = \vv x $$

Mějme počáteční pravděpodobnostní vektor $\vv x_0$ $$ \vv x_0 = \mtr{ p_0 q_0 \ p_0(1 - q_0) \ (1 - p_0) q_0 \ (1 - p_0)(1 - q_0) } $$ A jistě $$ \vv x_1 = A \vv x_0, \ \xx_2 = A \xx_1 = A^2 \xx_0 $$ Navíc $$ w(\xx_0 + \delta A\xx_0 + \delta^2 A^2 \xx_0 + \dots) = \ w(E + \delta A + \delta^2 A^2 + \dots) \xx_0 = \ w \underbrace{(\overbrace{E - \delta A}^B)^{-1} \xx_0}_{\yy}, $$ což je tedy $$ \yy = B^{-1} \xx_0 \ B \yy = \xx_0 \ \yy = \frac{|\cdot|}{|\cdot|} $$

A tím pádem dostaneme opět lineární závislost výhry na parametru $p_i$.

Evoluční algoritmy

A počítejme $$ \frac 1 3 1 + \frac 2 3 2 = \frac 5 3 $$ $$ \frac 1 3 0 + \frac 2 3 1,5 = 1 $$

Úloha o dohodě

Nechť $\mcal D$ je množina všech úloh o dohodě (pouze hry 2 hračů) s funkci $\vf : \mcal D \to \R^2$.

Dále nechť úloha $(S, u\str, v\str)$, kde $S$ je konvexní a kompaktní podmnožina v $\R^2$ a $(u\str, v\str) \in S$ je výchozí dvojice výher, která je dána tím, co si hráči zaručí - přičemž hledá optimální situaci

$S$ je podmnožina, na které se mohou hráči "hýbat"

Požadavky na $\vf$

$\vf(S, u\str, v\str) \geq (u\str, v\str)$ (bavíme se pouze o výhrách - tzn. cca Paretovská optimalita)
$\vf(S, u\str, v\str, u\str) \in S$
$(u,v) \in S \land (u,v) \geq \vf(S, u\str, v\str) \implies (u,v) = \vf(S, u\str, v\str)$
$\vf(S, u\str ,v\str) \in T \subseteq S \land (u\str, v\str) \in T \implies \vf(T, u\str, v\str) = \vf(S, u\str, v\str)$
Invariance vůči translaci a afinní transformaci s kladným koeficientem ($\vf$ nemění polohu vůči $S$)
$S$ je symetrická vůči ose $x = y$ a $u\str = v\str$ $\implies \vf(S, u\str, v\str)$ leží na $x = y$
$(u\str, v\str) \in T \subseteq S \implies \vf(T, u\str, v\str) \leq \vf(S, u\str, v\str)$

Lze ukázat, že taková funkce $\vf$ splňující 1.-7. neexistuje

Podmínka 7. je velmi silná a pokazí nám to

Věta $\D{NASH}$

Existuje právě jedno $\vf$ splňující 1.-6..

Lemma $\D{L1}$

Nechť $(\exists u,v \in S) \quad u > u\str, v > v\str$, pak existuje jediné maximum funkce $g(u,v) = (u - u\str)(v - v\str)$ na množině $S_+ = \set{(u,v) \in S \mid u \geq u\str, v \geq v\str}$.

Důkaz

Jistě $g$ je spojitá, $S_+$ je kompaktní. Lze předpokládat, že $(u\str, v\str) = (0,0)$ (posunutím do počátku). Mějme $(u', v'), (u'', v'')$ maxima $g$.

Můžeme předpokládat, že $u' > u''$ a jistě i $v' < v''$. Potom $$ g\left( \frac {u' + u''} 2, \frac {v' + v''} 2 \right) = \frac {(u' + u'')(v' + v'')} 4 = \ \frac{u'v' + u''v' + u' v'' + u'' v''} 4 >^? g(u', v') = u'v' = u'' v'' $$ Nerovnost odpovídá $$ u'v'' + u'' v' > u'v' + u'' v'' \iff (u' - u'')(v'' - v') > 0, $$ což ale jistě platí. Tedy jsme našli nové maximum, což je spor. $\blacksquare$

Lemma $\D{L2}$

Za předpokladů $\tagDe{L1}$ nechť $$ h(u,v) = (\bar v - v\str)u + (\bar u - u\str)v, $$ kde $(\bar u, \bar v)$ je bod, ve kterém se realizuje maximum $g$ z $\tagDe{L1}$. Pak pro libovolné $(u,v) \in S$ platí $h(u,v) \leq h(\bar u, \bar v)$.

Důkaz

Sporem, nechť $h(u,v) > h(\bar u, \bar v)$ pro nějaké $(u,v) \in S$. Nechť $\ve \in (0,1)$ a $$ (u', v') = (\bar u, \bar v) + \ve ((u,v) - (\bar u, \bar v)) $$ Pak ale $$ h(u- \bar u, v - \bar v) = h(u,v) - h(\bar u, \bar v) > 0 $$ Nyní dosaďme $$ g(u', v') = (\bar u - \ve(u - \bar u) - u\str)(\bar v - \ve(v - \bar v) - v\str) = \ = (\bar u - u\str)(\bar v - v\str) - \ve( (u -\bar u)(\bar v - v') + (\bar u - u\str)(v - \bar v)) + \ve^2(u - \bar u )(v - \bar v) $$ A derivací podle $\ve$ $$ 0 < \alpha + \beta \ve + \gamma \ve^2 \to \beta + 2 \gamma \ve, $$ tedy s růstem $\ve$ roste derivace na vhodném $(0, \ve_0)$. Tedy $g$ je rostoucí, což je spor s $\tagDe{L1}$.

Důkaz $\tagDe{NASH}$

Nastane právě jedna z možností

existuje $(u,v) \in S$ takové, že $u > u\str, v > v\str$

Potom vezmeme $(\bar u, \bar v)$ z $\tagDe{L1}$.
Neplatí 1., ale existuje $(u,v) \in S$ takové, že $u > u\str$ (a $v = v\str$)

V tomto případě vezmeme $\bar v = v\str$ a s $\bar u$ jdeme na maximum $(u \quad S)$
Neplatí 1., ale existuje $(u, v) \in S$ takové, že $v > v\str$ (a $u = u\str$)
$\hspace{3cm}$ANALOGICKY
Neplatí nic, z 1. - 3., tzn. $\bar u = u\str$ a $\bar v = v\str$. $\blacksquare$

Příklad

Mějme bimaticovou hru

student
$$ A = \begin{matrix}\text{učí} \ \text{neučí}\end{matrix} \overbrace{\mtr{2 & - 1 \ 1 & 0}}^{\text{dá} \;\; \text{nedá}} $$
učitel
$$ B = \mtr{0 & - 2 \ - 3 & -1} $$

U bimaticových her je $S$ konvexní obal všech situací a bodů z dolních hodnot

Zajímavější případ

7. přednáška

Teorie užitečnosti

Nechť $\mcal U$ je množina událostí, která je seřazená podle toho, jak jsou pro nás užitečné. Množinu $\mcal U$ rozšíříme o konvexní kombinace $$ r_1 A_1 + \dots + r_n A_n, $$ kde $A_1, \dots, A_n \in \mcal U$ a $r_1, \dots, r_n \geq 0$ s $r_1 + \dots + r_n = 1$.

Relace $A \prec B$ znamená, že $B$ upřednostňuji před $A$. $A \parallel B$ znamená, že žádnou událost neupřednostňuji.

Axiomy teorie užitečnosti $\D{AXT}$

$\forall A,B$ nastane právě jedna možnost $$A \succ B, A \prec B, A \parallel B \tag{\T{U1}}$$
$(\T{U2})$: $\parallel$ je relace ekvivalence
$(\T{U3})$: je tranzitivní
$(\T{U4})$: $A \prec B \parallel C \implies A \prec C$ a $A \parallel B \prec C \implies A \prec C$
$(\T{U5})$: $1 \cdot A + 0 \cdot B = A$
$(\T{U6})$: $r_1 A_1 + \dots + r_n A_n = r_{ \sigma_1} A_{ \sigma_1} + \dots + r_{ \sigma_n} A_{ \sigma_n}$ pro libovolnou permutaci $\sigma \in S(n)$
$(\T{U7})$: $rA + (1-r)(sB + (1-s)C) = rA + (1-r)sB + (1-r)(1-s)C$
$(\T{U8})$: $rA + (1-r)A = A$
$(\T{U9})$: $A \parallel C$ a vezmeme $r \in [0,1], B \in \mcal U \implies rA + (1-r)B \parallel rC + (1-r)B$
$(\T{U10})$: $A \prec C, r > 0, B \in \mcal U \implies rA + (1-r)B \prec rC + (1-r)B$
$(\T{U11})$: $A \prec B \prec C \implies \exists r \in [0,1] : rA + (1-r)C \parallel B$

Věta $\D{TEU}$

Existuje $u : \mcal U \to \R$ tak, že pro $$ \forall A,B \in \mcal U, r \in [0,1]: \quad u(A) < u(B) \iff A \prec B $$ a navíc platí

$u(rA + (1-r)B) = ru(A) + (1-r)u(B)$
je-li $v$ jiná taková funkce, pak platí
$$(\forall A \in \mcal U): \quad v(A) = \alpha u(A) + \beta,$$ kde $\alpha > 0, \beta \in \R$

Lemma $\D{TUL}$

Pokud $B \prec A$ a máme $0 \leq s \leq r \leq 1$, pak

$$sA + (1-s)B \preceq rA + (1-r) B$$
$$B \prec C \prec A, r \in (0,1) : \quad r A + (1-r) B \parallel C,$$ pak $r$ je určeno jednoznačně

Důkaz $\tagDe{TUL}$

$$ sA + (1-s)\left(\frac {r-s} {1-s} A + \frac {1-r}{1-s} B\right) =^{\tagEq{U7}} \ A (r-s)A + (1-r) B =^{\tagEq{U7}} \ r\left(\frac s r A + \frac {r-s} r A\right) + (1-r) B =^{\tagEq{U8}} rA + (1-r) B $$ a podle $\tagEq{U8}$ platí
$$ B = \frac {r-s} {1-s} B + \frac {1-r} {1_s} B \prec^{\tagEq{U10}} \frac {r-s} {1-s} A + \frac {1-r} {1 - s} $$ a celkem podle $\tagEq{U10}$ dostáváme
$$ rA + (1-r) B \succ sA + (1-s) B $$
Mějme $r,s$ a $$ rA + (1-r)B \parallel sA + (1-s)B, $$ což je spor s $\tagDe{TUL}$/1 a navíc
- $r = 0 \implies B \parallel C$ spor
- $r = 1 \implies A \parallel C$ spor

Důkaz $\tagDe{TEU}$

Vezměme události $E,F \in \mcal U, E \prec F$. Uvážíme $A \in \mcal U$, pak nastane některá z možností

$F \prec A$
$F \parallel A$
$E \prec A \prec F$
$E \parallel A$
$A \prec E$

Kdyby takové $E,F$ neexistovalo, pak $E \parallel F$ a pro libovolná $E,F$ a mohli bychom volit $u \equiv 0$

Klademe respektive podle možností výše $$ u(A) = \frac 1 r, 1, s, 0, \frac {t-1} t, $$ kde

$(1-s) E + sF \parallel A$
$rA + (1-r)E \parallel F$
$tA + (1-t)F \parallel E$

Nyní zvolíme $B \in \mcal U$ a vyšetříme 25 možností pozice $A,B$ vůči $E,F$, např. $E \prec A, B \prec F$

Pak $$ (1-s_1) E + s_1 F \parallel A \ (1-s_2) E + s_2 F \parallel B $$ a tedy $u(A) = s_1$ a $u(B) = s_2$. Předpokládejme $$ s_1 = s_2, $$ pak podle vztahu výše a $\tagEq{U2}$, tj. $A \parallel B$.
Nyní předp. $s_1 < s_2$, pak z $\tagDe{TUL}$ dostáváme $A \prec B$.
Naopak z $s_1 > s_2$ plyne $A \succ B$.

Hry ve tvaru charakteristické funkce

Hráči jsou poslanci a mají vytvořit vládní koalici - Snaha hráče je vždy dostat se koalice, která má šanci vyhrát

Mějme výherní funkci $$ v: 2^N \to \R, $$ kde $N = \set{1, \dots, n}$ je množina všech hráčů a $2^N$ je množina všech koalic ($\mcal P(N)$) a tedy pro $S \subseteq N, \; v(S) \in \R$

Požadujme

$v(\emptyset) = 0$ personálnost
$S,T \subseteq N, S \cap T = \emptyset \implies v(S \cup T) \geq v(S) + v(T)$ superaditivita
Rozdělení $x \in \R^N$
1. $x_1 + \dots + x_n = v(N)$
2. $x_i \geq v(\set{i})$
  Množinu všech rozdělení hry $v$ označme $E(v)$
Podstata $\sum_{i \in N} v(\set{i}) < v(N)$
Značme
$x \prec_S y,$ což čteme jako: rozdělení $x$ je dominované rozdělenením $y$ pro koalici $S$
1. $(\forall i \in S): x_i < y_i \quad \land \quad \sum_{i \in S} y_i \leq v(S)$
  Navíc píšeme $x \prec y$, pokud existuje koalice $S$ tak, že $x \prec_S y$
jádro - Množina všech nedominovaných rozdělení, značíme $C(v)$.
Lze ukázat, že jádro je složeno z rozdělení, kde každá koalice dostane alespoň tolik, kolik si sama zaručí, tj. $$ x \in C(v) \iff (\forall S \subseteq N): \quad \sum_{i \in S} x_i \geq v(S) $$

Příklad

Mějme $N = \set{1, 2, \dots, 2k = n}$, přičemž lichý hráč má levou botu a pravý hráč má pravou botu - výhra $v(S)$ koalice $S$ je pak počet funkčních párů bot, co jsou schopni dát dohromady

$v(\set{i}) = 0$
$v(\set{1,2}) = 1$
$v(\set{1,2,3}) = 1$
$v(\set{1,3}) = 0$

Jelikož $v(\set{2m-1, 2m}) = 1$, pak $$ v(N) = \sum_{m = 1}^k v(\set{2m-1, 2m}), $$ tedy jistě pro libovolné $x$ musí platit $x_{2m-1} + x_{2m} = 1$

Navíc i pro čtveřice musí platit $$ x_1 + x_4 = 1 \ x_2 + x_3 = 1 $$

Celkem tedy mám soustavu $$ x_1 + x_2 \ x_1 + x_4 = 1 \ x_2 + x_3 = 1 \ x_3 + x_4 = 1 \implies x_1 = x_3 \land x_2 = x_4 $$

A proto $$ x \in C(v) \iff x = (a, 1-a, a, 1-a, \dots) $$

8. přednáška

Pokračování her ve tvaru charaketeristické funkce

Věta $\D{KER}$

Pro libovolnou hru $v$ platí $$ C(v) = \set{ x \in \R^n \mid (\forall S \subseteq N) \sum_{i \in S} x_i \geq v(S), \sum_{i \in N} x_i = v(N)}, $$ kde $C(v)$ je jádro.

Definice ($\D{NM}$-řešení)

Označme $V \subseteq E(v)$ s vlastnostmi

$x,y \in V \implies x \not \prec y$
$x \in E(v) \setminus V \implies \exists y \in V : x \prec y$

Pak $V$ nazveme NM-řešením. Pod $E(v)$ myslíme množinu rozdělení.

Je to jistým způsobem alternativa k jádru

Hru nazveme symetrickou, pokud $v(S)$ je funkcí $|S|$.

Příklad

Mějme 3 hráče, 2 se domluví a 3. hráč jim musí zaplatit korunu každému. Jistě $v(\emptyset) = 0$ a $$ v(\set{1}) = v(\set{2}) = v(\set{3}) = -2 $$ Také $$ v(\set{1,2}) = \dots = 2 $$ a jako poslední $$ v(\set{1,2,3}) = 0 $$

Počítejme pro $C(v):$ $$ x_1 + x_2 \geq 2 \ x_1 + x_3 \geq 2 \ x_2 + x_3 \geq 2 $$ celkem $$ 2(x_1 + x_2 + x_3) \geq 6 \ x_1 + x_2 + x_3 \geq 3, $$ ale $x_1 + x_2 + x_3 = 0$, což je spor, tedy je jádro prázdné.

Naopak NM-řešeními jsou $$ \set{(1, 1, -2), (1, -2, 1), (-2, 1, 1)} $$ Zkontroluje ne-dominování mezi situacemi, např. $$ (1, 1, -2) \prec^? (1, -2, 1) $$

Zde při dominování si musí polepšit všichni hráči

Toto můžeme splnit koalicí $S$, ale ta podle pidgeon-hole principle nemůže být 2 ani 3 prvková, stejně přijdeme na to, že si 1 prvková koalice nic nezaručuje, tedy ani ona nebude fungovat. Tedy se tyto strategie nedominují.

Ověřme nyní druhou podmínku $$ (x,y,z) \not \in V, $$ BÚNO předpokládejme $x \leq y \leq z$, přičemž jistě $x = 2 - y - z$. Pak pro

$y > 1$, pak ale $y + z > 2$, tedy $x < -2$, ale potom $(x,y,z) \not \in E(v)$ (stejná situace nastane pro $y = 1$ a $z > y$)
$y = z = 1 \implies x = -2 \implies (x,y,z) \in V$
$y < 1, z < 1$, pak ale $(x,y,z) \prec (-2, 1, 1)$
$y < 1, z \geq 1$, pak tuto situaci dominuje $(1,1, -2)$

Shapleyho vektor

Vezměme $V$ - všechny hry ve tvaru charakteristické funkce (s $n$ hráči) - a chceme funkci $$ \vf : V \to \R^n $$

Máme několik požadavků na takovou funkci (na Shapleyho vektor)

$$\vf_i (\pi v) = \vf_{\pi^{-1} (i)} (v), \tag{\T{S1}}$$ kde $\pi v$ je hra vzniklá permutací $\pi$ na množině hráčů
$$\vf_i (u + v) = \vf_i(u) + \vf_i(v), \tag{\T{SS}}$$ kde platí $(u + v)(S) = u(S) + v(S)$
$$\alpha > 0 : \vf_i(\alpha v) = \alpha \vf_i (v), \tag{\T{S3}}$$ kde $(\alpha v)(S) = \alpha v(S)$
Pokud $S \subseteq N$ obsahuje všechny podstatné hráče, pak $v(S) = \sum_{i \in S} \vf_i (v)$, kde $i$ nazveme podstatným hráčem, pokud $$\exists S \subseteq N, i \not \in S : v(S, \set{i}) > v(S) + v(\set{i}) \tag{\T{S4}}$$

$$ \sum_{i \in N} \vf_i (v) = v(N) $$ Je-li $i$-tý hráč nepodstatný, pak $$ \vf_i(v) = v(\set{i}) $$

Věta $\D{Shapleyho}$

Existuje jediná funkce $\vf : V \to R^n$ splňující axiomy $\tagEq{S1}$ - $\tagEq{S4}$ uvedené výše a to $$ \vf_i(v) = \sum_{i \in T \subseteq N} \frac {(|T| - 1)! (n - |T|)!} {n!} \Big(v(T) - v(T - \set{i})\Big) $$

Lemma $\D{LS1}$

Nechť $w_S$ je hra $$ w_S (T) = \begin{cases} 1, & S \subseteq T \ 0, & \text{jinak}, \end{cases} $$ pak platí $$ \vf_i(w_S)) = \begin{cases} \frac 1 {|S|}, & i \in S \ 0, & i \not \in S \end{cases} $$

Důkaz $\tagDe{LS1}$

Hráč je podstatný $\iff$ $\in S$. Proto $$ \implies \sum_{i \in S} \vf_i(w_s) = 1 $$ Připusťme $\vf_i(w_s) \neq \vf_j(w_s), i, j \in S$. Zvolíme $\pi = (i,j)$, což ale dává spor s $\tagEq{S1}$.

Lemma $\D{LS2}$

Nechť $v \in V$ a $\emptyset \neq S \subseteq N$ a definujeme $$ c_S = \sum_{\emptyset \neq T \subseteq S} (-1)^{s-t} v(T), $$ kde $s = |S|, t = |T|.$ Potom $$ v = \sum_{\emptyset \neq S \subseteq N} c_s w_s $$

Důkaz $\tagDe{LS2}$

Zvolme koalici $\emptyset \neq U \subseteq N$ a $$ \sum_{\emptyset \neq S \subseteq N} c_s w_s(U) = \sum_{\emptyset \neq S \subseteq N} \sum_{\emptyset \neq T \subseteq S} (-1)^{s-t} v(T) w_S(U) $$

Jelikož $w_S(U) = 1 \iff S \subseteq U$, pak $$ = \sum_{\emptyset \neq T \subseteq U} \sum_{T \subseteq S \subseteq U} (-1)^{s-t} v(T) = \sum_{\emptyset \neq T \subseteq U} \left( \sum_{s = t}^{u} (-1)^{s-t} \binom{u-t}{s-t} \right) v(T) = \ = \sum_{\emptyset \neq T \subseteq U} \underbrace{\left( \sum_{i = 0}^{u-t} (-1)^i \binom{u -t}{i} \right)}_{(1 - 1)^{u-t} = 0 \text{ pro } t \leq u, 1 \text{ jinak}} v(T) \blacksquare $$

Lemma $\tagDe{LS2}$ dává jednoznačnost z $\tagDe{Shapleyho}$ věty.

Důkaz $\tagDe{Shapleyho}$ věty

Počítejme $$ \vf_i(v)=^{\tagDe{LS2}} = \sum_{\emptyset \neq S \subseteq N} c_S \vf_i(w_S) =^{\tagEq{S1}} \sum_{\emptyset \neq S \subseteq N} c_S \frac 1 s = \ = \sum_{\emptyset \neq S \subseteq N} \frac 1 s \sum_{\emptyset \neq T \subseteq S} (-1)^{s-t} v(T) = \sum_{\emptyset \neq T \subseteq N} \sum_{T \subseteq S \subseteq N} \frac {(-1)^{s-t}} s v(T) = \ = \sum_{i \in T \subseteq N} \gamma_i(T) (v(T) - v(T \setminus \set{i})), $$ kde $$ \gamma_i(T) = \sum_{T \cup \set{i} \subseteq S \subseteq N} \frac {(-1)^{s-t}} s $$

Počítejme $$ \gamma_i (T) = \sum_{s = t}^n \frac{(-1)^{s-t}} s \binom{n - t} {s-t} = \sum_{s = t}^n (-1)^{s-t} \binom {n-t}{s-t} \int_0^1 x^{s-1} dx = $$ $$ = \int_0^1 x^{t-1} \underbrace{\left( \sum_{s = t}^n (-1)^{s-t} \binom{n-t}{s-t} x^{s-t} \right)}_ {\sum_{j = 0}^{n-t} (-1)^j \binom{n-t} {j} x^j = (1-x)^{n-t} } dx = \ = \int_0^1 x^{t-1} (1-x)^{n-t} dx =^\text{per partes} \dots = \frac{(t-1)! (n-t)!} {n!} $$

$$ \int_0^1 x^{t-1} (1-x)^{n-t} dx = \frac 1 t x^T (1-x)^{n-t} - \int_0^1 \frac 1 t x^t (-1) (1-x)^{n-t-1} dx = \ = \frac 1 t \left( x^T (1-x)^{n-t} + \int_0^1 x^t (1 -x)^{n-t-1} \right) $$

Shapleyho vektor se nemusí nacházet v jádře

Pokračování příkladu s NM-řešením

$$ \vf_1(v) = \sum_{1 \in T \subseteq N} \frac {(t-1)!(n-t)!} {n!} (v(T) - v(T \setminus \set{1})) = \ = \frac {0! 2!}{3!}(-2) + 2 \cdot \frac{1! 1!}{3!} (2 - (-2)) + \frac {2! 0!}{3!} (0 - 2) = \ = \frac 1 {3!} \left( -4 + 8 -4 \right) = 0 $$

Teorie sociálního výběru

Teorie sociálního výběru - teorie her o volebních systémech

Příklad

Máme 15 zaměstnanců - ti si chtějí zvolit nového šéfa - a 3 kandidáty $$ A,B,C $$ Potom prefereční uspořádání jsou

7 zaměstnanců: $A > B > C$
7 zaměstnanců: $B > A > C$
1 zaměstnanec: $C > A > B$

Přehled bodů:

# people	A	B	C
7	2	1	0
7	1	2	0
1	1	0	2

Celkem má $A$ 22 bodů, $21$ bodů pro $B$ a $2$ pro C

Pokud by ale těch 7 zaměstnanců s 1. $B$ chtělo uškodit $A$, mohou si změnit preference na $$ B > C > A $$

To stejné mohou udělat i ti s 1. $A$. Potom prefereční uspořádání jsou

7 zaměstnanců: $A > C > B$
7 zaměstnanců: $B > C > A$
1 zaměstnanec: $C > A > B$

Přehled bodů:

# people	A	B	C
7	2	0	1
7	0	2	1
1	1	0	2

Celkem má $A$ 15 bodů, $14$ bodů pro $B$ a $16$ pro C

Označme

$N$ voliče
$i$-tici uspořádání $(<_i)_{i \in N}$ nazývanou preferenční uspořádání na množině $A$
$A$ množinu variant

Preferenční schéma $$ p : N \to S_m, \quad |A| = m, $$ kde $S_m$ je permutace množiny $A$

Dále označme $P$ množinu všech preferenčních schémat (pro pevné $N,A$).

Náš cíl je najít pevné $d : P \to S_m$, kde $d$ nazýváme funkcí sociálního rozhodování $$ d((<_i)_{i \in N}) = < $$ a požadujeme

$$(\forall (<_i)_{i \in N} \in P) (\forall a,b \in A) (\forall i \in N) \quad a <_i b \implies a < b \tag{\T{FSR-1}}$$

$$(\forall (<_i)_{i \in N}, (\prec_i)_{i \in N} \in P)(\forall a,b \in A) \quad \set{i | a <_i b} = \set{i | a_i \prec_i b} \implies (a < b \iff a \prec b) \tag{\T{FSR-2}}$$

Definice $\D{Dikt}$

Dále $j \in N$ nazveme diktátorem, pokud $$ d((<_i)_{i \in N}) = <_j $$

Věta $\D{Arrow}$

Nechť $n \geq 2, n \geq 3$. Pak libovolná funkce soc. rozhodování má diktátora.

Příklad

$m = 2, n \geq 2$, např. většinové pravidlo
$$I \subseteq N (\forall i \in I) \quad a <_i b \ (\forall j \in N \setminus I) \quad b <_j a$$
Je-li $|I| > \frac n 2 \implies a < b$ (a opačně). Při $n$ sudém dáme na "čestného předsedu"
$m = 2, n = 2$, možnosti
$$a <_1 b, a <_2 b \quad \implies a < b\ a <_1 b, b <_2 a\quad \implies a < b,\overbrace{b < a}^{\text{2. diktátor}}, \overbrace{a < b}^{\text{1. diktátor}}, b < a\ b <_1 a, a <_2 b\quad \implies a < b, \underbrace{a < b}_{\text{2. diktátor}}, \underbrace{b < a}_{\text{1. diktátor}}, b < a \ b <_1 a, b <_2 a \quad \implies b < a $$

Definice $\D{Filtr}$

Řekneme, že $\mcal F$ je filtr na množině $N$, pokud

$\emptyset \notin \mcal F$
$F, G \in \mcal F \implies F \cap G \in \mcal F$
$F \in \mcal F, F \subseteq G \implies G \in \mcal F$

Dále definujme hlavní filtr $$ \uparrow_A = \set{F \subseteq N | a \in F} $$ a ultrafiltr - maximální filtr, tj. $$ \mcal F \subseteq \mcal G \subseteq P(N) \implies \mcal G = \mcal F $$

Lemma $\D{L1}$

Filtr $\mcal F$ na $N$ je ultrafiltr $\iff$ $$ \forall F \subseteq N \text{ je } F \in \mcal F \text{ nebo } N \setminus F \in \mcal F $$

Důkaz $\tagDe{L1}$

Pokud by $F \notin \mcal F$ a ani $N \setminus F \in \mcal F$, pak generujme $\mcal G = \mcal F \cup \uparrow_F$

Nyní je třeba ukázat, že $\emptyset \notin \mcal G$. Kdyby ano, pak by muselo platit $\emptyset = F \cap G$ pro $G \in \mcal F$, pak $G \subseteq N \setminus F$, což je spor s $N - F \notin \mcal G$.

Lemma $\D{L2}$

Pro libovolnou konečnou množinu $N$ je každý ultrafiltr hlavní.

Podmnožina $F\subseteq N$ přehrává $F'$, typicky $F' = N \setminus F$, ve dvojici $a,b \in A$, platí-li $$ a <_F b, a <_{F'} b \implies a < b, $$ kde pod $a <_F b$ myslíme $(\forall i \in F) \quad a <_i b$

Lemma $\D{L3}$

Pokud $F$ přehrává $F' = N \setminus F$ pro $d$ v $a,b$ a $x,y$ jsou libovolné $x,y \in A \implies$ $F$ přehrává $F'$ i v $x,y$

Tedy pokud umí vynutit $a < b$ pro nějakou dvojici, umí to pro všechny dvojice

Důkaz $\tagDe{L3}$

Uvažujme $c <_F a <_F b$ a také $b <_{F'} c <_{F'} a$ (preferenční schéma musí být připravené pro všechny situace).
Pak ale podle $\tagEq{FSR-1}$ musí být $c < a$, ale také $a < b$ podle předpokladů. Celkem máme, že $c < a < b$.

Nyní vezměme libovolná $<_F, <_{F'}$ splňující $c <_F b, b <_F c$, pak dostaneme $c < b$, protože výsledek $d$ nezávisí na $a$ podle $\tagEq{FSR-2}$. Jinak řečeno $F$ přehrává $F'$ i v $c,b$.

Duálně nahradíme $b$ nějakým $e$ a stejně se dostaneme k $x,y$

Zde $F$ nazveme rozhodující (vládnoucí) rodina pro $d$

Lemma $\D{L4}$

Pro $n \geq 2, m \geq 3$ je množina všech vládnoucích rodin ultrafiltr na $N$

Důkaz $\tagDe{L4}$

Nechť $F$ je vládnoucí rodina a platí $F \subseteq G \subseteq N \implies G$ je vládnoucí rodina.
Mějme $a,b,c \in A$ s $F \subset G \subset N$ a požadujme

$a <_{N-G} c <_{N-G} b$
$a <_{G-F} b <_{G-F} c$
$b <_F a <_F c$

Z $\tagEq{FSR-1}$ víme, že $a<c$. Navíc $G$ přehrává $G'$ v $b,c$ a také $F$ je vládnoucí rodina a 3. víme, že $b < a < c$.

Celkem tedy $G$ přehrává $G'$ v $b,c$ a tedy $G$ je vládnoucí.

Dokažme, že $F$ je ultrafiltr a tedy $$ \emptyset \neq F \subset N \implies F \text{ nebo } F' \text{ je vl. rodina}, $$ tj. $b <_{F'} a, a <_F b$, pak

$a<b \implies F$ je vl.
$b < a \implies F'$ je vl.

Ukažme nyní uzavřenost na průniky. Nechť $$ \emptyset \neq F,G \subset N $$ a $F,G$ vládnoucí $\implies F \cap G$ vládnoucí. Vezměme nyní $$ b <_{N \setminus (F \cup G)} c <_{N \setminus (F \cup G)} a \ g <_{F \setminus G} a <_{F \setminus G} c \ c <_{G \setminus F} b <_{G \setminus F} a \ q <_{F \cap G} c <_{F \cap G} b, $$ z čehož dohromady víme z

$F = (F \cap G) \cup (F \setminus G)$, že $a < c$
$G = (F \cap G) \cup (G \setminus F)$, že $c < b$

Celkem $a < c < b \implies a < b$, tedy $F \cap G$ je vládnoucí pro $a,b$

Důkaz $\tagDe{Arrow}$

Jelikož $\mcal F = \uparrow_j \implies \set{j}$ je vládnoucí a tedy $j$ je diktátor.

Hry v rozšířené formě (poziční hry)

Také lze nazývat tahové hry

Definice $\D{HvRF}$

Nechť $N$ je množina hračů, $H$ množina historií

prázdná posloupnost $\ve \in H$
$(a^k)_ {k = 1}^K, K \in \N \cup \set{\infty}$ je historie $\implies (a^k)_ {k = 1}^L, L < K$ je historie
máme-li $(a^k)_ {k = 1}^\infty$ a víme, že $\forall L < \infty : (a_k)_ {k = 1}^L$ je historie, pak i $(a^k)_ {k = 1}^\infty$ je historie

Dále nechť $P$ je tahová funkce, $P : H' \to N$ (nebo také $P : H' \to \mcal P(N)$), kde $H' = H - Z$, $Z$ jsou terminální historie, což jsou maximální posloupnosti v $H$ (ty, které neumíme dále rozšířit).

Pak výherní funkce má tvar $u_i : Z \to \R$ nebo může být zadáno pouze preferenční uspořádání $\prec_i$ na $Z$

Příklad

Zde $N = \set{1,2}, P(\ve) = 1$ a $$ P((0,2)) = P((1,1)) = P((2,0)) = 2 $$ a také $u_1((1,1), y) = 1$. Množina historí má tvar $$ H = \set{\ve, (2,0), (1,1), (0,2), ((2,0), y), ((2,0), n), \dots} $$

Strategie pro prvního hráče $$ X =\set{(2,0), (1,1), (0,2)} $$ a pro druhého hráče $$ Y = \set{(2,0), y), (2,0), n), \dots} $$

Obecně zapsáno strategie pro $i$-tého hráče je množina $$ X_i = \set{f : \bar H \to H \mid \bar H = \set{\bar h \in H \mid P(\bar h) = i}, \bar h \text{ je podposloupnost } f(\bar h) \text{ bez posledního členu}} $$

Nashova rovnováha:
Máme výherní funkci $$ u_i(\bar f _i, f _{\hat i}) \geq u_i(f _i, f _{\hat i}), $$ tj. $i$ volí nejlepší odpověď na $f_{\hat i}$. Pak $$ (\bar f_i)_{i \in N} $$ je rovnováha.

Dále definujme podhru hry $(N, H, P, (X _i) _{i \in N}, (u _i) _{i \in N})$ jako $$ (N, H \mid_h, P\mid_h, (X _i \mid_h) _{i \in N}, (u _i\mid_h) _{i \in N}), $$ kde $h \in H$ pevná historie a $h' \in H \mid_h \iff (h, h') \in H$. Dále

$P\mid_h (h') = P(h, h')$
$f' \in X_i \mid_h \iff (\exists f \in X_i) (\forall \bar h \in \bar H \mid_h) \quad (h, f'(\bar h)) = f(h, \bar h)$
$u_i \mid_h (h') = u_i (h, h')$

Situace $(f_i)_{i \in N}$ je perfektní podherní rovnováha (PPR), je-li takto zvolené $(f_i \mid_h)_{i \in N}$ (Nashovou) rovnováhou pro každou historii $h$.

Pokračování příkladu

Rovnováha $$ \left((1,1), \begin{matrix} (2,0) \mapsto ((2,0), n) \ (1,1) \mapsto ((1,1), y) \ (0,2) \mapsto ((0,2), n) \end{matrix} \right), $$ což ale není perfektní podherní rovhována, neboť se zde $(0,2) \mapsto ((0,2), n$ rozhodl špatně, jinak řečeno $$ H \mid_h \qquad u_2((0,2), n) < u_2((0,2), y) $$

Tedy perfektní podherní rovnováha je v tomto případě $$ \left((1,1), \begin{matrix} (2,0) \mapsto ((2,0), n) \ (1,1) \mapsto ((1,1), y) \ (0,2) \mapsto ((0,2), y) \end{matrix} \right), $$ ale také $$ \left((1,1), \begin{matrix} (2,0) \mapsto ((2,0), y) \ (1,1) \mapsto ((1,1), y) \ (0,2) \mapsto ((0,2), y) \end{matrix} \right) $$

Lemma $\D{L1}$

Nechť $G = (N, H, P, \mcal X, \mcal U)$ je hra v rozšířené formě s konečným horizontem (všechny historie jsou konečné). Pak situace $(f_i)_{i \in N}$ je PPR $$ \iff \forall i \in N, \; \forall h \in H, \; P(h) = i \implies u_i((f_i \mid_h)_{i \in N}) \geq u_i(\tilde f_i, (f_j \mid_h)_{j \in \hat i}), $$ kde $\tilde f_i \in H \mid_h$ se liší od $f_i \mid_h$ pouze akcemi po $h$

Věta $\D{V1}$

Je-li $G = (N, H, P, \mcal X, \mcal U)$ konečná hra v rozšířené formě (tj. má konečný horizont a v každém vrcholu se rozhodujeme z konečně mnoha variant, tj. $H$ je konečná), pak existuje PPR*.

Dále tuto tématiku rozšiřují tzv. folkové věty.

Příklad: Stonožka

Máme 2 hráče $N = \set{1,2}$

A $$ f_1 = \begin{pmatrix} \ve \mapsto (z) \ (p,p) \mapsto (p,p,z) \ (p,p,p,p) \mapsto (p,p,p,p,z) \end{pmatrix} $$ a $f_2 = (\dots)$ analogicky.

Příklad: Dražba s placením

Tedy $$ \overbrace{ \mtr{ (-\infty, -\infty) & (4,0) \ (0,5) & (0,5) } }^{(p,\dots, p), \quad (z, \dots, z)}, $$ kde $(4,0)$ je rovnováha a $(0,5)$

Hry s neúplnou informací

Znalost

Nechť $\Omega$ označuje množinu stavů. Mějme informační funkci $P$, přičemž $P(\omega) \subseteq \Omega$

a máme 2 axiomy $$ \forall \omega \in \Omega \quad \omega \in P(\omega) \tag{\T{P1}} $$ a $$ \omega' \in P(\omega) \implies P(\omega') = P(\omega) \tag{\T{P2}}, $$ přičemž z $\tagEq{P1},\tagEq{P2}$ plyne, že $P$ vytváří rozklad na $\Omega$.

Dále definujme $K$ znalostní funkci a $E \subseteq \Omega$ událost a platí $$ K(E) = \set{\omega \in \Omega \mid P(\omega) \subseteq E}, $$ splňující

$$K(\Omega) = \Omega \tag{\T{K1}}$$
$$E \subseteq F \implies K(E) \subseteq K(F) \tag{\T{K2}}$$
$$K(E) \cap K(F) = K(E \cap F) \tag{\T{K3}}$$

$$K(E) \subseteq E \tag{\T{K4}}$$
$$K(K(E)) = K(E) \tag{\T{K5}}$$
(axiom moudrosti)
$$\Omega \setminus K(E) = K(\Omega \setminus K(E)) \tag{\T{K6}}$$

Pro začátek uvažujme 3 hráče, každý dostane černý nebo bílý klobouk, přičemž jeho barvu nezná. Hráči ví, že minimálně jeden klobouk je bílý. Hráči kteří odhadnou, jakou barvu má jejich klobouk, zvednou ruku a hraje dokud to všichni neví.

Možné situace

BČČ $\implies$ $\uparrow$?? $\implies$ (pokud by 1. nevěděl, že má jediný bílý, nezvedal by ruku) KONEC
BBČ $\implies$ ??? $\implies$ (bílý si řekne, druhý bílý nezvedl ruku, tedy já musím být taky bílý) $\uparrow$$\uparrow$? $\implies$ (černý nic neví, ale ostatní to už věděli, takže musí mít černý) KONEC
BBB $\implies$ ??? $\implies$ ??? $\implies$ (nikdo nic neví, tedy musí mít někdo bílý klobouk) KONEC

Jistě $$ \Omega = \set{c \in \set{\text{B}, \text{Č}}^n \mid \exists i \in N : c(i) = B} $$ a označme $P^i_j$ informační funkci $i$-tého hráče v $j$-tém kole ($j = 1,2,\dots$)

V případě BČČ je $P_1^1 (\text{BČČ}) = \set{\text{BČČ}}$, ale v $P_1^1(\text{BBČ}) = \set{\text{BBČ}, \text{ČBČ}}$

Dále označme $E_i$ jako událost, ve které $i$-tý hráč dozvěděl svoji barvu a tedy $|E_i| = 1$. Nyní nechť $$ F^k = \set{c ; \; |\set{c(i) = B}| = k} $$

Potom $P_i^2(c) = P_i^1(c) - F^1$. V našem případě $$ F^1 = \set{\text{BČČ}, \text{ČBČ}, \text{ČČB}}, F^2 = \set{\text{BBČ}, \text{BČB}, \text{ČBB}}, $$ proto $$ P_1^1(\text{BBČ}) = \set{\text{BBČ}, \text{ČBČ}} \implies \ P_1^2 = P_1^1(\text{BBČ}), \qquad P^3_1(\text{BBČ}) = \set{\underbrace{\text{ČBČ}}_{\in E_1}} $$

Označme $K_1, K_2$ - znalostní funkce 1. a 2. hráče. Dále $E$ je společnou znalostí ve stavu $\omega$, pokud $$K_1(E), K_2(E), K_1(K_2(E)), K_ 2(K_ 1(E)), K_2(K_1(K_2(E))), K_1(K_2(K_1(E))), \dots$$ obsahuje $\omega$.

Např. $$ P_1 = \set{ \set{\omega_1, \omega_2}, \set{\omega_3, \omega_4, \omega_5}, \set{\omega_6} }, \ P_2 = \set{ \set{\omega_1}, \set{\omega_2, \dots, \omega_5}, \set{\omega_5}, \set{\omega_6} }, \ E = \set{\omega_1, \dots, \omega_4}, $$ pak jistě

$K_1(E) = \set{\omega_1, \omega_2}$
$K_2(E) = \set{\omega_1, \dots, \omega_4}$
$K_1(K_2(E)) = \set{\omega_1, \omega_2}$ a $K_2(K_1(E)) = \set{\omega_1} = K_2(K_1(K_2(E)))$
$K_1(K_2(K_1(E)))) = \emptyset$

Událost $F \subseteq \Omega$ je samozřejmá mezi 1. a 2. hráčem, jestliže $\forall \omega \in F : P_i(\omega) \subseteq F$ pro $i = 1, 2$

$E$ je společnou znalostí v $\omega$, polid existuje $F$, $\omega \in F$, samozřejmá pro $i = 1,2$. Např. $$ F = \set{\omega_1, \dots, \omega_5} $$

V příkladu s klobouky

$$ P_1^1 = \set{ \set{BČČ}, \set{BBČ, ČBČ}, \set{BČB, ČČB}, \set{BBB, ČBB} } \ P_2^1 = \set{ \set{ČBČ}, \set{BBČ, BČČ}, \set{ČBB, ČCB}, \set{BBB, BČB} } $$