Počítali jsme stacionární vektor x pro přechodovou matici A, tj.
Ax=x
Mějme počáteční pravděpodobnostní vektor x0x0=p0q0p0(1−q0)(1−p0)q0(1−p0)(1−q0)
A jistě
x1=Ax0,x2=Ax1=A2x0
Navíc
w(x0+δAx0+δ2A2x0+…)=w(E+δA+δ2A2+…)x0=wy(E−δAB)−1x0,
což je tedy
y=B−1x0By=x0y=∣⋅∣∣⋅∣
A tím pádem dostaneme opět lineární závislost výhry na parametru pi.
Evoluční algoritmy
A počítejme
311+322=35310+321,5=1
Úloha o dohodě
Nechť D je množina všech úloh o dohodě (pouze hry 2 hračů) s funkci φ:D→R2.
Dále nechť úloha(S,u∗,v∗), kde S je konvexní a kompaktní podmnožina v R2 a (u∗,v∗)∈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 φ
φ(S,u∗,v∗)≥(u∗,v∗) (bavíme se pouze o výhrách - tzn. cca Paretovská optimalita)
φ(S,u∗,v∗,u∗)∈S
(u,v)∈S∧(u,v)≥φ(S,u∗,v∗)⟹(u,v)=φ(S,u∗,v∗)
φ(S,u∗,v∗)∈T⊆S∧(u∗,v∗)∈T⟹φ(T,u∗,v∗)=φ(S,u∗,v∗)
Invariance vůči translaci a afinní transformaci s kladným koeficientem (φ nemění polohu vůči S)
S je symetrická vůči ose x=y a u∗=v∗⟹φ(S,u∗,v∗) leží na x=y
(u∗,v∗)∈T⊆S⟹φ(T,u∗,v∗)≤φ(S,u∗,v∗)
Lze ukázat, že taková funkce φ splňující 1.-7. neexistuje
Podmínka 7. je velmi silná a pokazí nám to
VětaNASH
Existuje právě jedno φ splňující 1.-6..
LemmaL1
Nechť (∃u,v∈S)u>u∗,v>v∗,
pak existuje jediné maximum funkce g(u,v)=(u−u∗)(v−v∗) na množině S+={(u,v)∈S∣u≥u∗,v≥v∗}.
Důkaz
Jistě g je spojitá, S+ je kompaktní. Lze předpokládat, že (u∗,v∗)=(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(2u′+u′′,2v′+v′′)=4(u′+u′′)(v′+v′′)=4u′v′+u′′v′+u′v′′+u′′v′′>?g(u′,v′)=u′v′=u′′v′′
Nerovnost odpovídá
u′v′′+u′′v′>u′v′+u′′v′′⟺(u′−u′′)(v′′−v′)>0,
což ale jistě platí. Tedy jsme našli nové maximum, což je spor. ■
LemmaL2
Za předpokladů L1 nechť
h(u,v)=(vˉ−v∗)u+(uˉ−u∗)v,
kde (uˉ,vˉ) je bod, ve kterém se realizuje maximum g z L1.
Pak pro libovolné (u,v)∈S platí h(u,v)≤h(uˉ,vˉ).
Důkaz
Sporem, nechť h(u,v)>h(uˉ,vˉ) pro nějaké (u,v)∈S.
Nechť ε∈(0,1) a
(u′,v′)=(uˉ,vˉ)+ε((u,v)−(uˉ,vˉ))
Pak ale
h(u−uˉ,v−vˉ)=h(u,v)−h(uˉ,vˉ)>0
Nyní dosaďme
g(u′,v′)=(uˉ−ε(u−uˉ)−u∗)(vˉ−ε(v−vˉ)−v∗)==(uˉ−u∗)(vˉ−v∗)−ε((u−uˉ)(vˉ−v′)+(uˉ−u∗)(v−vˉ))+ε2(u−uˉ)(v−vˉ)
A derivací podle ε0<α+βε+γε2→β+2γε,
tedy s růstem ε roste derivace na vhodném (0,ε0). Tedy g je rostoucí, což je spor s L1.