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ť U\mcal U je množina událostí, která je seřazená podle toho, jak jsou pro nás užitečné. Množinu U\mcal U rozšíříme o konvexní kombinace r1A1+⋯+rnAn, r_1 A_1 + \dots + r_n A_n, kde A1,…,An∈UA_1, \dots, A_n \in \mcal U a r1,…,rn≥0r_1, \dots, r_n \geq 0 s r1+⋯+rn=1r_1 + \dots + r_n = 1.

Relace A≺BA \prec B znamená, že BB upřednostňuji před AA. A∥BA \parallel B znamená, že žádnou událost neupřednostňuji.

Axiomy teorie užitečnosti AXT\D{AXT}
  • ∀A,B\forall A,B nastane právě jedna možnost A≻B,A≺B,A∥B(U1)A \succ B, A \prec B, A \parallel B \tag{\T{U1}}
  • (U2)(\T{U2}): ∥\parallel je relace ekvivalence
  • (U3)(\T{U3}): je tranzitivní
  • (U4)(\T{U4}): A≺B∥C  ⟹  A≺CA \prec B \parallel C \implies A \prec C a A∥B≺C  ⟹  A≺CA \parallel B \prec C \implies A \prec C
  • (U5)(\T{U5}): 1⋅A+0⋅B=A1 \cdot A + 0 \cdot B = A
  • (U6)(\T{U6}): r1A1+⋯+rnAn=rσ1Aσ1+⋯+rσnAσnr_1 A_1 + \dots + r_n A_n = r_{ \sigma_1} A_{ \sigma_1} + \dots + r_{ \sigma_n} A_{ \sigma_n} pro libovolnou permutaci σ∈S(n)\sigma \in S(n)
  • (U7)(\T{U7}): rA+(1−r)(sB+(1−s)C)=rA+(1−r)sB+(1−r)(1−s)CrA + (1-r)(sB + (1-s)C) = rA + (1-r)sB + (1-r)(1-s)C
  • (U8)(\T{U8}): rA+(1−r)A=ArA + (1-r)A = A
  • (U9)(\T{U9}): A∥CA \parallel C a vezmeme r∈[0,1],B∈U  ⟹  rA+(1−r)B∥rC+(1−r)Br \in [0,1], B \in \mcal U \implies rA + (1-r)B \parallel rC + (1-r)B
  • (U10)(\T{U10}): A≺C,r>0,B∈U  ⟹  rA+(1−r)B≺rC+(1−r)BA \prec C, r > 0, B \in \mcal U \implies rA + (1-r)B \prec rC + (1-r)B
  • (U11)(\T{U11}): A≺B≺C  ⟹  ∃r∈[0,1]:rA+(1−r)C∥BA \prec B \prec C \implies \exists r \in [0,1] : rA + (1-r)C \parallel B
Věta TEU\D{TEU}

Existuje u:U→Ru : \mcal U \to \R tak, že pro ∀A,B∈U,r∈[0,1]:u(A)<u(B)  ⟺  A≺B \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)u(rA + (1-r)B) = ru(A) + (1-r)u(B)
  • je-li vv jiná taková funkce, pak platí
    (∀A∈U):v(A)=αu(A)+β,(\forall A \in \mcal U): \quad v(A) = \alpha u(A) + \beta, kde α>0,β∈R\alpha > 0, \beta \in \R
Lemma TUL\D{TUL}

Pokud B≺AB \prec A a máme 0≤s≤r≤10 \leq s \leq r \leq 1, pak

  1. sA+(1−s)B⪯rA+(1−r)BsA + (1-s)B \preceq rA + (1-r) B
  2. B≺C≺A,r∈(0,1):rA+(1−r)B∥C,B \prec C \prec A, r \in (0,1) : \quad r A + (1-r) B \parallel C, pak rr je určeno jednoznačně
Důkaz TUL\tagDe{TUL}
  1. sA+(1−s)(r−s1−sA+1−r1−sB)=(U7)A(r−s)A+(1−r)B=(U7)r(srA+r−srA)+(1−r)B=(U8)rA+(1−r)B 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 (U8)\tagEq{U8} platí
    B=r−s1−sB+1−r1sB≺(U10)r−s1−sA+1−r1−s 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 (U10)\tagEq{U10} dostáváme
    rA+(1−r)B≻sA+(1−s)B rA + (1-r) B \succ sA + (1-s) B
  2. Mějme r,sr,s a rA+(1−r)B∥sA+(1−s)B, rA + (1-r)B \parallel sA + (1-s)B, což je spor s TUL\tagDe{TUL}/1 a navíc
    • r=0  ⟹  B∥Cr = 0 \implies B \parallel C spor
    • r=1  ⟹  A∥Cr = 1 \implies A \parallel C spor
Důkaz TEU\tagDe{TEU}

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

  • F≺AF \prec A
  • F∥AF \parallel A
  • E≺A≺FE \prec A \prec F
  • E∥AE \parallel A
  • A≺EA \prec E

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

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

  • (1−s)E+sF∥A(1-s) E + sF \parallel A
  • rA+(1−r)E∥FrA + (1-r)E \parallel F
  • tA+(1−t)F∥EtA + (1-t)F \parallel E

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

Pak (1−s1)E+s1F∥A(1−s2)E+s2F∥B (1-s_1) E + s_1 F \parallel A \\ (1-s_2) E + s_2 F \parallel B a tedy u(A)=s1u(A) = s_1 a u(B)=s2u(B) = s_2. Předpokládejme s1=s2, s_1 = s_2, pak podle vztahu výše a (U2)\tagEq{U2}, tj. A∥BA \parallel B.
Nyní předp. s1<s2s_1 < s_2, pak z TUL\tagDe{TUL} dostáváme A≺BA \prec B.
Naopak z s1>s2s_1 > s_2 plyne A≻BA \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:2N→R, v: 2^N \to \R, kde N={ 1,…,n }N = \set{1, \dots, n} je množina všech hráčů a 2N2^N je množina všech koalic (P(N)\mcal P(N)) a tedy pro S⊆N,  v(S)∈RS \subseteq N, \; v(S) \in \R

Požadujme

  1. v(∅)=0v(\emptyset) = 0 personálnost
  2. S,T⊆N,S∪T=∅  ⟹  v(S∪T)≥v(S)+v(T)S,T \subseteq N, S \cup T = \emptyset \implies v(S \cup T) \geq v(S) + v(T) superaditivita
  3. Rozdělení x∈RNx \in \R^N
    1. x1+⋯+xn=v(N)x_1 + \dots + x_n = v(N)
    2. xi≥v({ i })x_i \geq v(\set{i})
      Množinu všech rozdělení hry vv označme E(v)E(v)
  4. Podstata ∑i∈Nv({ i })<v(N)\sum_{i \in N} v(\set{i}) < v(N)
  5. Značme
    x≺Sy,x \prec_S y, což čteme jako: rozdělení xx je dominované rozdělenením yy pro koalici SS
    1. (∀i∈S):xi<yi∧∑i∈Syi≤v(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≺yx \prec y, pokud existuje koalice SS tak, že x≺Syx \prec_S y
  6. jádro - Množina všech nedominovaných rozdělení, značíme C(v)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∈C(v)  ⟺  (∀S⊆N):∑i∈Sxi≥v(S) x \in C(v) \iff (\forall S \subseteq N): \quad \sum_{i \in S} x_i \geq v(S)

Příklad

Mějme N={ 1,2,…,2k=n }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)v(S) koalice SS je pak počet funkčních párů bot, co jsou schopni dát dohromady

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

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

Navíc i pro čtveřice musí platit x1+x4=1x2+x3=1 x_1 + x_4 = 1 \\ x_2 + x_3 = 1

Celkem tedy mám soustavu x1+x2x1+x4=1x2+x3=1x3+x4=1  ⟹  x1=x3∧x2=x4 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∈C(v)  ⟺  x=(a,1−a,a,1−a,… ) x \in C(v) \iff x = (a, 1-a, a, 1-a, \dots)

Back to top