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$$
Ř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}$.
Pareto optimální situace je taková, že není dominovaná podle Pareta
2. 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}} $$
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
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á
0 | $a$ | $b$ | 1 |
---|---|---|---|
0 | 1 | 1 | 1 |
0 | 0 | 0 | 1 |
0 | 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
$$ \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}} \xdef\xx{\vv x} \xdef\yy{\vv y} $$
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
7. 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}} \xdef\xx{\vv x} \xdef\yy{\vv y} $$
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 \cup T = \emptyset \implies v(S \cup T) \geq v(S) + v(T)$ superaditivita
-
Rozdělení $x \in \R^N$
- $x_1 + \dots + x_n = v(N)$
- $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$- $(\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$
- $(\forall i \in S): x_i < y_i \quad \land \quad \sum_{i \in S} y_i \leq v(S)$
-
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$
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
$$ \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}} \xdef\xx{\vv x} \xdef\yy{\vv y} $$
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
$$ \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}} \xdef\xx{\vv x} \xdef\yy{\vv y} $$
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)
$$ \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}} \xdef\xx{\vv x} \xdef\yy{\vv y} $$
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í
$$ \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}} \xdef\xx{\vv x} \xdef\yy{\vv y} $$
Znalost
Nechť $\Omega$ označuje množinu stavů. Mějme informační funkci $P$, přičemž $P(\omega) \subseteq \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}}$$
Příklad - Hádání barvy klobouku
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} } $$