Zdrojový kód
%\wikiskriptum{01LIP}
\section{Aplikace lineárního programování v teorii her}
\begin{define}
Nechť $n\in\N$, $X_1,X_2,\dots,X_n\not=\emptyset$,
$M_1,M_2,\dots,M_n:X_1\times X_2\times\dots\times
X_n\mapsto\R$. Množinu $\{\hat n,X_1,\dots,X_n,M_1,\dots,M_n\}$
nazýváme {\bf hrou $n$ hráčů} (v~normálním tvaru).
\begin{itemize}
\item $\hat n$ je {\bf množina hráčů} $1,2,\dots,n$,
\item $X_i$ je {\bf prostor strategií $i$-tého hráče},
\item $x\in X_i$ je {\bf strategie $i$-tého hráče},
\item $M_i$ je {\bf výplatní funkce $i$-tého hráče},
\item $M_i(x_1,\dots,x_n)$ je {\bf výhra resp. prohra $i$-tého hráče}.
\end{itemize}
\end{define}
\begin{example}
Hra dvou hráčů: $n=2$, $X_1=X_2=\la 0,1\ra$, $M_1(x_1,x_2)=x_1+x_2$,
$M_2(x_1,x_2)=-(x_1+x_2)$.
\end{example}
\begin{define}
Nechť je dána hra $N$ hráčů $\{\hat n,X_1,\dots,X_n,M_1,\dots,M_n\}$.
\begin{enumerate}
\item Nazýváme ji {\bf konečnou}, jsou-li prostory strategií všech
hráčů konečné množiny, jinak ji nazýváme {\bf nekonečnou}.
\item Existuje-li $K\in\R$ takové, že pro každou $n$-tici
$(x_1,\dots,x_n)\in X_1\times\dots\times X_n$ je
\[\sum_{i=1}^n M_i(x_1,\dots,x_n)=K,\]
nazýváme tuto hru {\bf hrou s~konstantním součtem $K$}, jinak {\bf
hrou s~nekonstantním součtem}.
\end{enumerate}
\end{define}
\subsection{Nekonfliktní rozhodovací situace}
Hra $\{1,X,M\}$. Optimální strategie je takové $\x\in X$, že
$M(\x)=\max\{M(x)|x\in X\}$. Optimální strategie nemusí existovat (např. $M(x)=x,\ X=(0,1)$).
\subsection{Antagonistický konflikt}
Budeme se zabývat pouze {\bf hrou dvou hráčů} s~konstantním
součtem. Označme $X_1=X$, $X_2=Y$, $M_1(x,y)+M_2(x,y)=K$. Je-li $K=0$,
označíme $M=M_1=-M_2$.
\begin{define}
Nechť je dána hra s~konstantním součtem $K$: $\{\hat 2,X,Y,M_1,M_2\}$. {\bf Optimální strategií 1. hráče} nazveme prvek
$\x\in X$ takový, k~němuž existuje $\y\in Y$ s~touto vlastností:
$(\forall x\in X)(\forall y\in Y)
(M_1(x,\y)\le M_1(\x,\y)\wedge M_2(\x,y)\le M_2(\x,\y))$.
Prvek $\y$ je {\bf optimální strategie 2. hráče}.
\end{define}
\begin{remark}
Je-li $K=0$, pak $M(x,\y)\le M(\x,\y)\le M(\x,y)$. Dvojici $(\x,\y)$
nazýváme {\bf řešení hry}, $M(\x,\y)$ je {\bf cena hry}. Cena hry je
jednoznačná: Nechť $(\tilde x,\tilde y)$ také řeší hru. Potom pro
každé $x,y$ platí
$M(x,\tilde y)\le M(\tilde x,\tilde y)\le M(\tilde x,y)$.
Po dosazení $x=\x$ a $y=\y$ máme
$M(\tilde x,\tilde y)\le M(\tilde x,\y)\le M(\x,\y)
\le M(\x,\tilde y)\le M(\tilde x,\tilde y)$.
\end{remark}
\begin{example}
Pro výše uvedenou hru je $\x=1$, $\y=0$, neboť $x\le 1\le 1+y$.
\end{example}
\begin{theorem}
Nechť je dána hra s~konstantním součtem $K$: $\{\hat
2,X,Y,M_1,M_2\}$. Potom $\x$ resp. $\y$ jsou optimální strategie v
této hře, právě když $\x$ a $\y$ jsou optimální strategie ve hře s
nulovým součtem $\{\hat 2,X,Y,M\}$, kde $M=M_1-M_2$.
\begin{proof}
\begin{enumerate}
\item $(\Rightarrow)$ Podle definice pro každé $x,y$ platí
\[M_1(x,\y)\le M_1(\x,\y)\le M_1(\x,y),\]
po dosazení $M_1(x,y)=K-M_2(x,y)$ máme
\[K-M_2(x,\y)\le K-M_2(\x,\y)\le K-M_2(\x,y),\]
po sečtení
\[(M_1-M_2)(x,\y)\le (M_1-M_2)(\x,\y)\le (M_1-M_2)(\x,y).\]
\item $(\Leftarrow)$ Nechť platí $(M_1-M_2)(x,\y)\le
(M_1-M_2)(\x,\y)\le (M_1-M_2)(\x,y)$. Dosadíme $M_2=K-M_1$.
\[M_1(x,\y)-(K-M_1(x,\y))\le M_1(\x,\y)-(K-M_1(\x,\y)),\]
tedy $2M_1(x,\y)\le 2M_1(\x,\y)$. Analogicky pro druhou nerovnost.\qed
\end{enumerate}
\noqed
\end{proof}
\end{theorem}
\subsection{Konečný antagonistický konflikt}
$X=\hat m$, $Y=\hat n$, $K=0$, $M(i,j)=a_{ij}$.
\begin{define}
Nechť $\A=(a_{ij})\in\R^{m,n}$. Hru s~nulovým součtem
$\{\hat 2,\hat m,\hat n,M\}$, kde $M(i,j)=a_{ij}$ nazýváme {\bf
maticovou hrou}. $\A$ je {\bf matice hry}.
\end{define}
Pro optimální strategii platí
$a_{i\overline j}\le a_{\overline i\overline j}\le a_{\overline ij}$.
Prvek $a_{\overline i\overline j}$, který splňuje tyto nerovnosti (a je tedy nejmenší v řádku a největší ve sloupci), se nazývá sedlový prvek.
\begin{example}
Matice
\[
\A=\begin{pmatrix}
5 & 4 & \mathbf 4 & 5\\
-3 & 5 & 3 & 7\\
7 & 8 & -1 & 6
\end{pmatrix}
\]
má sedlový prvek $\overline i=1$, $\overline j=3$. Matice
\[
\B=\begin{pmatrix}
1 & -\frac32 & -1\\
0 & 4 & 2
\end{pmatrix}
\]
nemá sedlový prvek.
\end{example}
\begin{define}
Nechť je dána maticová hra s~maticí $\A\in\R^{m,n}$. Hru
$\{\hat 2,(X),(Y),M\}$, kde
\[(X)=\left\{(x_1,\dots,x_m)\in\R^m\left|
\sum_{i=1}^m x_i=1\wedge x_i\ge 0\text{ pro $i\in\hat m$}\right.\right\},\]
\[(Y)=\left\{(y_1,\dots,y_n)\in\R^n\left|
\sum_{j=1}^n y_j=1\wedge y_j\ge 0\text{ pro $j\in\hat n$}\right.\right\},\]
\[M(x,y)=\sum_{i=1}^m\sum_{j=1}^n x_i a_{ij} y_j=x\A y^T,\]
nazýváme {\bf smíšeným rozšířením} původní maticové hry.
Vektory typu $(1,0,\dots,0),(0,1,0,\dots,0),\dots,(0,\dots,0,1)$
nazýváme {\bf ryzí strategie}, ostatní jsou {\bf smíšené strategie}.
\end{define}
\begin{theorem}
Smíšené rozšíření každé maticové hry má řešení.
\begin{proof}
\begin{enumerate}
\item Dokážeme, že smíšené rozšíření má řešení, pokud jsou všechny
prvky matice $\A$ kladné, tj.
$(\forall i\in\hat m)(\forall j\in\hat n)(a_{ij}>0)$. Chceme dokázat,
že
\[(\exists\x\in(X))(\exists\y\in(Y))(\forall x\in(X))(\forall y\in(Y))
(x\A\y^T\le\x\A\y^T\le\x\A y^T).\]
Buď $\tilde x\in(X)$. Definujeme $f_{\tilde x}(y)=\tilde x\A y^T$ pro
$y\in(Y)$. Označme
\[\min_{y\in(Y)}f_{\tilde x}(y)=c_{\tilde x},\]
existenci minima zaručuje kompaktnost $(Y)$ a spojitost $f_{\tilde
x}$. Pro každé $y\in(Y)$ je tedy $c_{\tilde x}\le\tilde x\A y^T$.
Analogicky pro $\tilde y\in(Y)$ definujeme $g_{\tilde y}(x)=x\A\tilde
y^T$,
\[\max_{x\in(X)}g_{\tilde y}(x)=v_{\tilde y}\]
a platí, že $v_{\tilde y}\ge x\A\tilde y^T$ pro každé $x\in(X)$.
Pokud bychom našli $v_{\tilde y}\le c_{\tilde x}$, byly by $\tilde
x,\tilde y$ optimální strategie, neboť
\[0<x\A\tilde y^T\le v_{\tilde y}\le c_{\tilde x}\le\tilde x\A y^T,\]
což musí platit i pro $x=\tilde x$, $y=\tilde y$, proto
$c_{\tilde x}=v_{\tilde y}=\tilde x\A\tilde y^T$. Označme společnou
hodnotu $c_{\tilde x}=v_{\tilde y}=V>0$. Budeme dokazovat, že
\[(\exists V>0)(\exists\x\in(X))(\exists\y\in(Y))
(\forall x\in(X))(\forall y\in(Y))(x\A\y^T\le V\le\x\A y^T).\]
Označme $\x=(\x_1,\dots,\x_m)$, $\y=(\y_1,\dots,\y_n)$. Uvažujme
nejprve ryzí strategie $x$ a $y$. Potom musí platit
\begin{align*}
\x_1 a_{11}+\x_2 a_{21}+\dots+\x_m a_{m1}&\ge V&
\y_1 a_{11}+\y_2 a_{12}+\dots+\y_n a_{1n}&\le V\\
&\xvdots & &\xvdots\\
\x_1 a_{12}+\x_2 a_{22}+\dots+\x_m a_{m2}&\ge V&
\y_1 a_{21}+\y_2 a_{22}+\dots+\y_n a_{2n}&\le V\\
\x_1 a_{1n}+\x_2 a_{2n}+\dots+\x_m a_{mn}&\ge V&
\y_1 a_{m1}+\y_2 a_{m2}+\dots+\y_n a_{mn}&\le V.
\end{align*}
Budou-li platit tyto nerovnosti, pak $x\A\y^T\le V\le\x\A y^T$ pro
každé $x,y$. Stačí nerovnice vynásobit $y_1,\dots,y_n$
(resp. $x_1,\dots,x_n$) a sečíst. Na pravé straně pak dostaneme opět
$V$.
Protože $V$ musí být kladné, každou nerovnici vydělíme $V$ a
zavedeme
\[\xi_i=\frac{\x_i}{V},\quad\eta_i=\frac{\y_i}{V}.\]
Potom nerovnice přejdou na
\begin{align*}
\xi_1 a_{11}+\dots+\xi_m a_{m1}&\ge 1&
\eta_1 a_{11}+\dots+\eta_m a_{1n}&\le 1\\
&\xvdots& &\xvdots\\
\xi_1 a_{1n}+\dots+\xi_m a_{mn}&\ge 1&
\eta_1 a_{m1}+\dots+\eta_m a_{mn}&\le 1.
\end{align*}
Dále platí
\[\sum_{i=1}^m\x_i=1,\ \x_i\ge 0\iff
\sum_{i=1}^m\xi_i=\frac1V,\ \xi_i\ge 0\]
\[\sum_{j=1}^n\y_j=1,\ \y_j\ge 0\iff
\sum_{j=1}^n\eta_j=\frac1V,\ \eta_j\ge 0.\]
Budeme tedy hledat
\[\min z=\sum_{i=1}^m\xi_i,\quad\max w=\sum_{j=1}^n\eta_j.\]
Pokud budou $z_{min}=w_{max}$, tj. bude existovat optimální řešení, bude
\[V=\frac{1}{\sum_{i=1}^m\xi_i}=\frac{1}{z_{min}}.\]
Stačí dokázat, že primární i duální úloha mají přípustné řešení. U
duální je to jasné (vyhovuje $\eta=0$). Primární úloha má přípustné
řešení díky kladnosti prvků $a_{ij}$. Stačí zvolit např. $\xi_1$
dostatečně velké a zbytek $\xi_i=0$. Proto mají obě úlohy optimální
řešení.
Protože $0$ není přípustné řešení primární úlohy, bude
$z_{min}=w_{max}>0$. Pro řešení hry pak platí
\[\x_i=V\xi_i,\quad \y_j=V\eta_j.\]
\item Obecný případ:
\begin{lemma}
Optimální strategie smíšeného rozšíření maticové hry se nezmění,
přičteme-li ke každému prvku matice $\A$ totéž číslo $c$. Cena nové
hry se o~$c$ zvětší.
\begin{proof}
Buďte $\x,\y$ řešení hry s~maticí $\A$. Potom pro každé $x,y$ platí
$x\A\y^T\le\x\A\y^T\le\x\A y^T$. Buď dále $\mathbf I\in\R^{m,n}$,
$\mathbf I_{ij}=1$. Potom $x\mathbf I y^T=1$ pro
$x\in(X),y\in(Y)$. Proto $c x\mathbf I y^T=c$ a platí
\[x\A\y^T+c\le\x\A\y^T+c\le\x\A y^T+c,\]
\[x\A\y^T+c x\mathbf I\y^T\le\x\A\y^T+c\x\mathbf I\y^T\le
\x\A y^T+c\x\mathbf I~y^T,\]
\[x(\A+c\mathbf I)\y^T\le\x(\A+c\mathbf I)\y^T\le
\x(\A+c\mathbf I) y^T.\qed\]
\noqed
\end{proof}
\end{lemma}
K~matici $A$ tak stačí pouze přičíst dostatečně velké číslo, abychom
dostali všechny prvky kladné. Nakonec odečteme $c$ od $V$.\qed
\end{enumerate}
\noqed
\end{proof}
\end{theorem}
\begin{example}
Nechť matice hry je
\[
\A=
\begin{pmatrix}
1 & -3/2 & -1\\
0 & 4 & 2
\end{pmatrix}
\]
K~matici přičteme $c=2$:
\[
\tilde\A=
\begin{pmatrix}
3 & 1/2 & 1\\
2 & 6 & 4
\end{pmatrix}
\]
Budeme řešit duální úlohu
\begin{align*}
\max w&=\eta_1+\eta_2+\eta_3\\
3\eta_1+\frac12\eta_2+\eta_3&\le 1\\
2\eta_1+6\eta_2+4\eta_2&\le 1
\end{align*}
\end{example}
\begin{align*}
\left(
\begin{array}{c|ccccc}
0 & -1 & -1 & -1 & 0 & 0\\
\hline
1 & \mathbf 3 & 1/2 & 1 & 1 & 0\\
1 & 2 & 6 & 4 & 0 & 1
\end{array}
\right)&\sim
\left(
\begin{array}{c|ccccc}
1/3 & 0 & -5/6 & -2/3 & 1/3 & 0\\
\hline
1/3 & 1 & 1/6 & 1/3 & 1/3 & 0\\
1/3 & 0 & 17/3 & \mathbf{10/3} & -2/3 & 1
\end{array}
\right)\sim\\
&\sim
\left(
\begin{array}{c|ccccc}
2/5 & 0 & & 0 & & \\
\hline
3/10 & 1 & & 0 & & \\
1/10 & 0 & 17/10 & 1 & -1/5 & 3/10
\end{array}
\right)
\end{align*}
Je tedy
\[\eta_1=\frac3{10},\quad\eta_2=0,\quad\eta_3=\frac1{10},\quad
w_{max}=\frac25\]
Protože $3\xi_1+2\xi_2=1$ a $\xi_1+4\xi_2=1$, je $\xi_1=\frac15$,
$\xi_2=\frac15$. Dále je $V=\frac52$, takže $\x_1=\frac12$,
$\x_2=\frac12$, $\y_1=\frac34$, $\y_2=0$, $\y_3=\frac14$.
Cena původní hry je $V'=\frac52-2=\frac12$.
\begin{example}[dominance sloupce a řádku]
Mějme matici
\[
\A=
\begin{pmatrix}
2 & 3 & 1/2 & 4 & 1\\
5 & 2 & 6 & 3 & 4\\
1 & 2 & -1 & 3 & 0
\end{pmatrix}
\]
Třetí řádek je dominován druhým, první sloupec je dominován pátým,
třetí sloupec je dominován druhým. Stačí řešit matici
\[
\A'=
\begin{pmatrix}
3 & 1/2 & 1\\
2 & 6 & 4
\end{pmatrix}
\]
\end{example}
\subsection{Symetrické hry}
\begin{define}
Nechť je dána hra s~nulovým součtem $\{\hat 2,X,Y,M\}$. Řekneme, že je
{\bf symetrická}, právě když
\begin{enumerate}
\item $X=Y$,
\item $M(x,y)=-M(y,x)$ pro každé $x\in X$, $y\in Y$.
\end{enumerate}
\end{define}
\begin{theorem}
Má-li symetrická hra řešení, pak je-li $(\x,\y)$ řešení této hry, je i
$(\y,\x)$ řešení této hry. Cena řešitelné symetrické hry je $0$.
\begin{proof}
Pro řešení hry platí
\[M(x,\y)\le M(\x,\y)\le M(\x,y).\]
Z~definice symetrické hry vyplývá, že
\[-M(\y,x)\le -M(\y,\x)\le -M(y,\x).\]
Vynásobením $-1$ máme
\[M(y,\x)\le M(\y,\x)\le M(\y,x),\]
tedy $(\y,\x)$ je řešení. Protože $M(\x,\y)=-M(\y,\x)=M(\y,\x)$
díky jednoznačnosti ceny hry, je $M(\x,\y)=0$.
\end{proof}
\end{theorem}
