01LIP:Kapitola6
Z WikiSkripta FJFI ČVUT v Praze
Verze z 1. 8. 2010, 02:41, kterou vytvořil Admin (diskuse | příspěvky) (Založena nová stránka: %\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_...)
[ znovu generovat, | výstup z překladu ] | Kompletní WikiSkriptum včetně všech podkapitol. | |
PDF Této kapitoly | [ znovu generovat, | výstup z překladu ] | Přeložení pouze této kaptioly. |
ZIP | Kompletní zdrojový kód včetně obrázků. |
Součásti dokumentu 01LIP
součást | akce | popis | poslední editace | soubor | |||
---|---|---|---|---|---|---|---|
Hlavní dokument | editovat | Hlavní stránka dokumentu 01LIP | Admin | 1. 8. 2010 | 02:38 | ||
Řídící stránka | editovat | Definiční stránka dokumentu a vložených obrázků | Admin | 7. 9. 2015 | 14:46 | ||
Header | editovat | Hlavičkový soubor | Admin | 1. 8. 2010 | 02:39 | header.tex | |
Kapitola1 | editovat | Úvod | Admin | 1. 8. 2010 | 02:40 | kapitola1.tex | |
Kapitola2 | editovat | Dualita v LP | Pohanjur | 3. 7. 2011 | 21:33 | kapitola2.tex | |
Kapitola3 | editovat | Simplexová metoda | Karel.brinda | 13. 9. 2010 | 18:32 | kapitola3.tex | |
Kapitola4 | editovat | Princip dekompozice | Admin | 1. 8. 2010 | 02:40 | kapitola4.tex | |
Kapitola5 | editovat | Celočíselné programování | Admin | 1. 8. 2010 | 02:40 | kapitola5.tex | |
Kapitola6 | editovat | Aplikace lineárního programování v teorii her | Admin | 1. 8. 2010 | 02:41 | kapitola6.tex |
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}