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 \leq 2 \ x_1 + x_3 \leq 2 \ x_2 + x_3 \leq 2 $$ celkem $$ 2(x_1 + x_2 + x_3) \leq 6 \ x_1 + x_2 + x_3 \leq 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 $$