1. 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}} $$

V jakémsi smyslu zobecnění optimalizace, kdy máme více hráčů

Úvodní příklad (hra ultimátum)

Mějme $I = [0, 1]$ a 1. hráč si vybere $x \in I$ a 2. hráč říká ano/ne na vybrané $x$.

Hry v normální formě

Definice $\D{HNF}$ (Hra v normální formě)

Mějme $n \in \N$ a $N = \set{1, 2, \dots, n}$ je množina hráčů. A zaveďme

$X_i$ - množina strategií $i$-tého hráče
$u_i$ - výherní funkce $i$-tého hráče ($\prod$ je zde kartézský součin)
$$u_i : \prod_{i \in N} X_i \to \R$$

Navíc předpokládáme, že hráči hrají "rozumně" a "ví všechno" (tj. znají množiny strategií ostatních hráčů i jejich výherní funkce).

Řekneme, že strategie $x_i$ dominuje $y_i$, značíme $ X_i \succ Y_i$. Navíc značíme $x_{\other i} = (x_1, \dots, x_{i - 1}, x_{i+1}, \dots, x_n)$ a pak $$ u_i(x_i, x_{\other i}) \geq u_i(y_i, x_{\other i}) \quad \forall x_{\other i} \quad \and \quad \exists x_{\other i} \quad u_i(x_i, x_{\other i}) > u_i(y_i, x_{\other i}) $$

Strategie $x$ je nedominovaná, jestliže neexistuje $y \succ x$.

Pokračování úvodního příkladů

$$ X_1 = I \ X_2 = \set{0,1}^I, $$ kde $\set{0,1}^I$ je množina zobrazení z $I$ do $\set{0,1}$. Pak výherní funkce jsou $$ u_1(x, f) = \begin{cases} x, & \text{ pro } f(x) = 1 \ 0, & \text{ pro } f(x) = 0 \end{cases} $$ $$ u_2(x, f) = \begin{cases} 1 - x, & \text{ pro } f(x) = 1 \ 0, & \text{ pro } f(x) = 0 \end{cases} $$

Pro 1. hráče jistě $0 \prec x$ pro $x \neq 0$, protože $$ u_i(0, f_{\other i}) = 0 $$ ale $$ u_i(x, f_{\other i}) = \begin{cases} x, & \text{ pro } f(x) = 1 \ 0, & \text{ pro } f(x) = 0 \end{cases} \geq 0 $$ Pro 2. hráče $f \prec g$ nastane právě tehdy, když v $g$ souhlasíme ve více případech, tj. $$ \forall x : f(x) = 1 \implies g(x) = 1 \quad \and \quad \exists x : f(x) = 0 \land g(x) = 1 $$ Jinak zapsáno $f < g$.

Nyní předpokládejme $x \prec y, \; x,y > 0, x \neq y$, tj. hledáme $$ f : u_1(x, f_{\hat i}) > u_1(y, f_{\hat i}) $$ a pak stačí libovolná $f$, že $f(x) = 1, f(y) = 0$, z čehož dostaneme $1 > 0$.

Z pohledu řešení hry je rozumné neuvažovat libovolné dominované strategie. Tímto jsme ji ale vytrhli z kontextu. Tedy zde by si odmítnutím "budoval prestiž" na další hry. Zde by totiž 1. hráč si mohl vzít (skoro) celý interval (rohlík) a podle nedominované strategie by to 2. hráč přijal.

Definice $\D{SIT}$ (Situace)

Sitaucí nazveme $n$-tici $(x_1, \dots, x_n) \in \prod_{i \in N} X_i$.

Řekneme, že situace $\vv x = (x_1, \dots, x_n)$ dominuje podle Pareta sitauci $\vv y = (y_1, \dots, y_n)$, pokud $$ \forall i \in N : u_i (\vv x) \geq u_i (\vv y) \AND \exists i \in N : u_i (\vv x) > u_i (\vv y) $$

Pokračování úvodního příkladů

Například $x = \frac 2 3$ a $f(x) = \begin{cases} 1, & x \leq \frac 1 2 \ 0, & \text{jinak}\end{cases}$.

V tomto případě pro $(x, f)$ mají $u_1(x, f) = u_2(x,f) = 0$.

Naopak $y = \frac 1 2$ a $g(x) = \begin{cases} 1, & x \leq \frac 2 3 \ 0, & \text{jinak}\end{cases}$.

V tomto případě pro $(x, f)$ mají $$ u_1(y, g) = u_2(y, g) = \frac 1 2 $$

A tedy $(x,f) \prec (y,g)$ .

Pokud se dohodnou v obou situacích, pak o jejich dominování nemůžeme mluvit - jeden dostane méně, druhý více.

Definice $\D{ZAR}$ (Zaručování)

Hráč $i$ si zaručuje $x$, pokud $$ \exists x_ i : \forall x_ {\other i} : u_ i(x_ i, x_ {\other i}) \geq x $$ Dolní hodnotou hry pro $i$-tého hráče je $$ h^-_ i = \sup _ {x_ i} \inf_ {x_ {\other i}} = u_ i (x_i, x_{\other i}) $$

Horní hodnotou hry pro $i$-tého hráče je $$ h^+_ i = \inf_ {x_ i} \sup_ {x_ {\other i}} = u_ i (x_i, x_{\other i}) $$

U dolní hodnoty "škodící" hráči dopředu ví, co zahraji (první volíme v infimu, potom až v supremu)

Pro úvodní příklad je $$ h_1^ - = h_2^ - = 0 $$ a $$ h_1^ + = h_2^ + = 0 $$

Definice $\D{ROV}$ (Rovnovážná situace)

Řekneme, že $\vv x$ je rovnovážná situace (Nashova rovnováha), pokud $$ \forall i \in N : \forall y_i \in X_i : u_i(x_i, x_{\other i}) \geq u_i (y_i, x_{\other i}) $$

Pro každého hráče samostatně je dobré hrát takto

Mějme $(x, f)$ pro $x > 0$, pak pro $f(y) = \begin{cases}1, & y \leq x \ 0, & y > x\end{cases}$. Změňme $x \to y$, pak pokud

$y < x$, pak $u_1(x,f) = x$ a $u_1(y,f) = y < x$
$y > x$, pak $u_1(x,f) = x$ a $u_1(y,f) = 0 < x$

Nyní změňme $f \to g$, pak pro $g(x) = 1$ je $u_2(x,f) = x = u_2(x,g)$. Naopak pro $g(x) = 0$ je $u_2(x,g) = 0 \leq u_2(x,f)$.

Hra 2 hráčů

Zde $n = 2$ a značme

$x_1$ jako $x$, $X_1$ jako $X$
$x_2$ jako $y$, $X_2$ jako $Y$
$u_1$ jako $u$
$u_2$ jako $v$

Antagonistická hra je taková, že pro situace $(x,y)$ a $(\bar x, \bar y)$, tak pokud $$ u(x,y) \geq u(\bar x, \bar y) \iff v(x,y) \leq v(\bar x, \bar y) $$

Paretovská dominance vylučuje antagonistickou hru

Hra s konstatním součtem nazýváme hru, kde $$ u(x,y) + v(x,y) = c $$ a speciální případ jsou hry s nulovým součtem, kde $$ u(x,y) + v(x,y) = 0 $$

Šachy jsou hra s konstantím součtem (výhra - 1, remíza - 0.5). Naopak fotbal není (výhra - 3, remíza - 1), ale je antagonistická.

U koopertivních her mají hráči nějakým způsobem možnost dosahovat paretovské dominance

Definice $\D{MAT}$ (Maticová hra)

Mějme hru 2 hráčů, kde množiny $X,Y$ jsou konečné. Pišme $$ X = \set{x_1, \dots, x_k} \AND Y = \set{y_1, \dots, y_l} $$ a pak situace uspořádáme do matice $X \times Y$ následovně

Matice $A,B$ jsou pak výherní matice 1. a 2. hráče a $u(x_i, y_j) = A_{i,j}$.

Je-li navíc $A = - B$, pak jde o maticovou hru, což je hra s nulovým součtem.

Pareto optimální strategie je taková, že není není dominovaná podle Pareta