Skip to main content

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

  1. $$sA + (1-s)B \preceq rA + (1-r) B$$
  2. $$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}$
  1. $$ 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 $$
  2. 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

  1. $v(\emptyset) = 0$ personálnost
  2. $S,T \subseteq N, S \cup T = \emptyset \implies v(S \cup T) \geq v(S) + v(T)$ superaditivita
  3. 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)$
  4. Podstata $\sum_{i \in N} v(\set{i}) < v(N)$
  5. 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$
  6. 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

  1. $v(\set{i}) = 0$
  2. $v(\set{1,2}) = 1$
  3. $v(\set{1,2,3}) = 1$
  4. $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) $$

Back to top