Skip to main content

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 x\vv x pro přechodovou matici AA, tj. Ax=x A \vv x = \vv x

Mějme počáteční pravděpodobnostní vektor x0\vv x_0 x0=(p0q0p0(1q0)(1p0)q0(1p0)(1q0)) \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ě x1=Ax0,x2=Ax1=A2x0 \vv x_1 = A \vv x_0, \\ \xx_2 = A \xx_1 = A^2 \xx_0 Navíc w(x0+δAx0+δ2A2x0+)=w(E+δA+δ2A2+)x0=w(EδAB)1x0y, 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 y=B1x0By=x0y= \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 pip_i.

Evoluční algoritmy

A počítejme 131+232=53 \frac 1 3 1 + \frac 2 3 2 = \frac 5 3 130+231,5=1 \frac 1 3 0 + \frac 2 3 1,5 = 1

Úloha o dohodě

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

Dále nechť úloha (S,u,v)(S, u\str, v\str), kde SS je konvexní a kompaktní podmnožina v R2\R^2 a (u,v)S(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

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

Požadavky na φ\vf

  1. φ(S,u,v)(u,v)\vf(S, u\str, v\str) \geq (u\str, v\str) (bavíme se pouze o výhrách - tzn. cca Paretovská optimalita)
  2. φ(S,u,v,u)S\vf(S, u\str, v\str, u\str) \in S
  3. (u,v)S(u,v)φ(S,u,v)    (u,v)=φ(S,u,v)(u,v) \in S \land (u,v) \geq \vf(S, u\str, v\str) \implies (u,v) = \vf(S, u\str, v\str)
  4. φ(S,u,v)TS(u,v)T    φ(T,u,v)=φ(S,u,v)\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)
  5. Invariance vůči translaci a afinní transformaci s kladným koeficientem (φ\vf nemění polohu vůči SS)
  6. SS je symetrická vůči ose x=yx = y a u=vu\str = v\str     φ(S,u,v)\implies \vf(S, u\str, v\str) leží na x=yx = y
  7. (u,v)TS    φ(T,u,v)φ(S,u,v)(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 NASH\D{NASH}

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

Lemma L1\D{L1}

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

Důkaz

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

Můžeme předpokládat, že u>uu' > u'' a jistě i v<vv' < v''. Potom g(u+u2,v+v2)=(u+u)(v+v)4=uv+uv+uv+uv4>?g(u,v)=uv=uv 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á uv+uv>uv+uv    (uu)(vv)>0, 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 L2\D{L2}

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

Důkaz

Sporem, nechť h(u,v)>h(uˉ,vˉ)h(u,v) > h(\bar u, \bar v) pro nějaké (u,v)S(u,v) \in S. Nechť ε(0,1)\ve \in (0,1) a (u,v)=(uˉ,vˉ)+ε((u,v)(uˉ,vˉ)) (u', v') = (\bar u, \bar v) + \ve ((u,v) - (\bar u, \bar v)) Pak ale h(uuˉ,vvˉ)=h(u,v)h(uˉ,vˉ)>0 h(u- \bar u, v - \bar v) = h(u,v) - h(\bar u, \bar v) > 0 Nyní dosaďme g(u,v)=(uˉε(uuˉ)u)(vˉε(vvˉ)v)==(uˉu)(vˉv)ε((uuˉ)(vˉv)+(uˉu)(vvˉ))+ε2(uuˉ)(vvˉ) 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<α+βε+γε2β+2γε, 0 < \alpha + \beta \ve + \gamma \ve^2 \to \beta + 2 \gamma \ve, tedy s růstem ε\ve roste derivace na vhodném (0,ε0)(0, \ve_0). Tedy gg je rostoucí, což je spor s L1\tagDe{L1}.

Důkaz NASH\tagDe{NASH}

Nastane právě jedna z možností

  1. existuje (u,v)S(u,v) \in S takové, že u>u,v>vu > u\str, v > v\str

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

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

Mějme bimaticovou hru

  • student
    A=ucˇıˊneucˇıˊ(2110)daˊ    nedaˊ A = \begin{matrix}\text{učí} \\ \text{neučí}\end{matrix} \overbrace{\mtr{2 & - 1 \\ 1 & 0}}^{\text{dá} \;\; \text{nedá}}
  • učitel
    B=(0231) B = \mtr{0 & - 2 \\ - 3 & -1}

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

Zajímavější případ