Hra s nulovým součtem

Hra s nulovým součtem je termín používaný v teorii her. Patří do skupiny her popisující antagonistické konflikty - co jeden hráč získá, druhý ztrácí, takže spolupráce v těchto konfliktech nemá smysl. Jakoukoliv hru s konstantním součtem lze transformovat na ekvivalentní hru s nulovým součtem, protože přičtením konstanty ke všem hodnotám výplatní funkce nedojde ke změně jejího řešení.

Jednoduchým názorným příkladem zde může být například hra - kámen, nůžky, papír. Pokud bychom hráli o 1 Kč, tak ten kdo vyhraje, získá 1 Kč, ten kdo prohraje −1 Kč. +more 1 + (−1) = 0, proto hra s nulovým součtem.

Hra s nulovým součtem

Hra v normálním tvaru

Základním modelem hry s nulovým součtem a vůbec modelem celé teorie her je hra v normálním tvaru. Ta je charakterizována 3 množinami: # Množinou hráčů v obecném případě očíslovaných přirozenými čísly {1, 2, …, N} # Množinou prostorů strategií {X1, X2, …, XN}, které jsou přiřazeny jednotlivým hráčům # Množinou výplatních funkcí {f1(x1, x2, …, xN),…, fN(x1,x2, …, xN)}, které jsou rovněž přiřazeny jednotlivým hráčům. +more Každá výplatní funkce je definována na kartézském součinu prostoru strategií. (Výplatní funkce stanovuje výhru hráče pro všechny možné kombinace strategií).

Důležitým předpokladem v této hře je, že jsou hráči inteligentní (chovají se racionálně), tj. chtějí maximalizovat hodnotu své výplatní funkce. +more Dále že mají hráči dokonalé informace, tj. znají možnosti (strategie) a výplatní funkce ostatních hráčů.

Jakoukoliv hru s konstantním součtem můžeme transformovat na ekvivalentní hru s nulovým součtem. Pokud budeme pro zjednodušení uvažovat hru dvou hráčů, je hra s konstantním součtem ve svém normálním tvaru definována jako

f_1(x,y)+f_2(x,y)=K,

kde pro libovolné strategie x∈X, y∈Y a K je libovolné reálné číslo. Pro hru s nulovým součtem je K=0. +more Pro tuto hru platí, že přičteme-li určitou konstantu ke všem hodnotám výplatní funkce, řešení zůstává stejné. Výplatní funkce pro hru s nulovým součtem pak vypadá takto:.

f_1(x,y)=-f_2(x,y)

Cílem každé hry v teorii her je samozřejmě nalézt návod pro optimální chování jednotlivých hráčů. Pokud tedy i nadále budeme uvažovat hru dvou hráčů, označíme si optimální strategii hráče 1 jako x°∈X, ke které existuje optimální strategie hráče 2 y°∈Y . +more Pro výplatní funkce hráčů platí:.

f_1(x,y^o)\leq f_1(x^o,y^o) a f_2(x^o,y)\leq f_2(x^o,y^o)

Pro zjednodušení výpočtu se i u her s konstantním součtem můžeme omezit na hru s nulovým součtem, označíme si výplatní funkci hráče 1 jako f1(x, y) = f(x, y) a výplatní funkci hráče 2 jako f2(x, y) = -f(x, y). Z tohoto zjednodušení vyplývá, že pro popis řešení hry není potřeba brát v úvahu výplatní funkci druhého hráče, neboť ta obsahuje pouze opačné hodnoty výplatní funkce prvního hráče. +more Výše uvedené podmínky nerovnosti lze tedy uvést zjednodušeně ve tvaru:.

f(x,y^o)\leq f(x^o,y^o)\leq f(x^o,y)

Tyto nerovnosti vyjadřují fakt, že pokud se jeden z hráčů odchýlí od své optimální strategie, zatím co druhý hráč zůstane u své optimální strategie, hráč, který se odchýlil si nemůže v žádném případě polepšit. V nejlepším případě jeho výhra zůstane stejná.

Takto definované optimální strategie představují tzv. Nashovu rovnováhu (Nashovo rovnovážné řešení) a nazýváme je rovnovážnými strategiemi.

Pokud je prostor strategií konečný, můžeme hru s nulovým součtem vyjádřit maticí A = (aij), i = 1, 2,. , m; j = 1, 2,. +more, n. Řádky matice odpovídají strategiím hráče 1 a sloupce matice odpovídají strategiím hráče 2. Pokud hráč 1 zvolí i-tou strategii a hráč 2 j-tou strategii, hodnota aij odpovídá výplatě hráče 1. Výplata hráče 2 je pak definována jako opačná hodnota aij tedy -aij. Tento model se nazývá maticová hra a matici A nazýváme výplatní maticí.

A=\begin{pmatrix} a_{11} & a_{12} & ... & a_{1n} \\ a_{21} & a_{22} & ... & a_{2n} \\ .&&&\\ .&&&\\ .&&&\\ a_{m1} & a_{m2} & ... & a_{mn} \end{pmatrix}

Řešení této hry respektive Nashovo rovnovážné řešení získáme nalezením sedlového bodu matice A (výplatní matice hráče 1). Sedlový bod odpovídá největší hodnotě ve sloupci a zároveň nejmenší hodnotě ve svém řádku (oba hráči chtějí maximalizovat svůj zisk, je třeba si uvědomit, že výplata hráče 2 odpovídá -aij; pokud vybereme minimum v řádku, pro hráče 2 je to maximum). +more Nalezneme-li sedlový bod s hodnotou aij, potom i-tá strategie hráče 1 a j-tá strategie hráče 2 jsou optimální rovnovážné strategie a tuto hodnotu aij nazýváme cenou hry. Takto nalezené řešení nazýváme Nashovou rovnováhou (rovnovážným řešením) v ryzích strategiích.

Při hledání sedlového bodu matice (Nashovy rovnováhy) mohou nastat tyto tři případy: # Matice má jeden sedlový prvek (prvek je Nashovým rovnovážným řešením). # Matice má více sedlových prvků, jejichž hodnoty jsou si rovny, potom tyto sedlové prvky určují alternativní optimální (rovnovážné) strategie. +more # Matice nemá žádný sedlový prvek, optimální strategie se nám daným postupem nepodařilo najít (neexistuje rovnovážné řešení v ryzích strategiích).

Výše uvedené možnosti ukazují následující příklady. Postupuje se tak, že napřed se vyberou maxima ve sloupcích a ty se označí kulatými závorkami. +more Poté se vyberou minima v řádcích a označí se hranatými závorkami. Prvek, který bude ohraničen jak kulatými, tak hranatými závorkami je sedlový bod matice.

\begin{pmatrix} 5 & 6 & \left|(4)\right| & 5 \\ \left|-2\right| & 5 & 3 & (7) \\ (8) & (7) & \left|-2\right| & 6 \end{pmatrix}

Matice má jeden sedlový prvek.

\begin{pmatrix} \left|(0)\right| & 1 & 3 & \left|(0)\right| \\ \left|(0)\right| & 2 & (4) & \left|(0)\right| \\ \left|-4\right| & (5) & 0 & -2 \end{pmatrix}

Matice má čtyři sedlové prvky.

\begin{pmatrix} (2) & 1 & \left|0\right| \\ \left|0\right| & (2) & (3) \end{pmatrix}

Matice nemá žádný sedlový prvek.

Občas je možné si hledání optimálního řešení značně zjednodušit. S výplatní maticí lze zacházet jako s kteroukoliv jinou maticí, můžeme tedy využít dominovanosti. +more Racionální hráč nebude volit strategii, v níž jsou všechny hodnoty prvků menší než všechny prvky z jiné dostupné strategie. V konkrétním případě hry dvou hráčů, hráč 1 nikdy nebude volit řádek matice se všemi prvky menšími, než jsou v jiném řádku a analogicky hráč 2 nebude volit sloupec, kde jsou všechny prvky větší než v jiném sloupci.

Smíšené strategie

Když nelze ve výplatní matici nalézt sedlový bod, neznamená to, že pro danou hru neexistuje Nashovo rovnovážné řešení. Znamená to pouze to, že dosavadní výklad nebyl dostatečný pro nalezení rovnovážných strategií ve všech rozhodovacích situacích. +more Obecné řešení maticových her si lze dobře ukázat na známe hře kámen, nůžky, papír. Jedná se opět o hru 2 hráčů, kde každý z nich má na výběr ze tří strategií. Buď zvolí kámen, nůžky nebo papír. Pokud oba zvolí stejnou strategii, dojde k remíze a hra by se opakovala do té doby, než by došlo k výhře (prohře) jednoho z hráčů. V následujícím příkladě však budeme uvažovat pouze 1 kolo hry a pokud dojde k remíze, hra skončí remízou.

Výplatní matice hráče 1 vypadá takto:

\begin{pmatrix} 0 & +1 & -1 \\ -1 & 0 & +1 \\ +1 & -1 & -0 \end{pmatrix}

Jak je vidět ve výplatní matici není žádný sedlový bod, přesto tuto hru hrajeme a známe své odpovídající rovnovážné strategie, které náhodně vybíráme, každou s pravděpodobností 1/3. Pro oba hráče je tak rovnovážnou strategií vektor (1/3, 1/3, 1/3). +more Tyto strategie nazýváme smíšenými (pravděpodobnostními) strategiemi. Ryzí strategie jsou tedy zvláštním případem (podmnožinou) smíšených strategií, kdy jedna z pravděpodobností je rovná jedné a ostatní pravděpodobnosti jsou rovny nule. I pro smíšené strategie platí, že odchýlí-li se hráč od své optimální strategie, nemůže si polepšit. Nejlépe skončí se stejným výsledkem. Pokud tedy nějaká hra nemá řešení v ryzích strategiích, použije se tzv. smíšeného rozšíření maticové hry. Ve smíšeném rozšíření budou nyní prostory strategií odpovídat vektoru pravděpodobností, s kterým hráč zvolí určitou strategii.

X=\left\{x;x^T=\left|x_1,x_2,...,x_m \right|,\sum_{i=1}^m x_i=1,x \geq 0 \right\}

Y=\left\{y;y^T=\left|y_1,y_2,...,y_n \right|,\sum_{j=1}^n y_i=1,y \geq 0 \right\}

Hodnota výplatní funkce pak udává očekávanou střední hodnotu výhry. Opět zde platí, že v případě hry s nulovým (resp. +more konstantním) součtem stačí sledovat výplatní funkci prvního hráče.

f(x,y)= \sum_{i=1}^m \sum_{j=1}^n x_i a_{ij} y_j = x^TAy

Pro maticové hry platí tzv. základní věta maticových her:

Každá maticová hra má Nashovo rovnovážné řešení ve smíšených strategiích.

Ta tvrdí, že pro každou matici A existují vektory x° a y° (° = rovnovážné strategie), pro které platí tato nerovnice:

x^TA\bar{y}^o \leq \bar{x}^{oT}Ay^o \leq \bar{x}^{oT}Ay

Tato nerovnice je upravená definice Nashovy rovnováhy ve smíšených strategiích. Dá-li se hra vyjádřit maticovou hrou o rozměru m×2 nebo n×2, lze k nalezení rovnováhy použít grafickou metodu. +more V obecném případě se dá řešení získat vypočítáním úlohy lineárního programování simplexovou metodou. Tento postup si lze rozdělit do dvou částí. V prvním kroku je nutné ověřit, zdali výplatní matice neobsahuje záporné prvky. Pokud ano, je nutné ji převést na strategicky ekvivalentní matici s pouze kladnými prvky. Toho lze docílit přičtením konstanty C ke všem prvkům matice. Cena hry je potom rovna v + c. V druhém kroku je již možné přistoupit k řešení úlohy lineárního programování. Na výběr jsou samozřejmě 2 možnosti výpočtu - minimalizovat nebo maximalizovat. (Obecně se z výpočetního hlediska doporučuje spíše maximalizace. ).

Minimalizovat

p_1 + p_2 + ... + p_m

za podmínek

a_{11}p_1 + a_{21}p_2 + ... +a_{m1}p_m \geq 1;

...

...

...

a_{1n}p_1 + a_{2n}p2 + ... +a_{mn}p_m \geq 1;

p_i \geq 0; i=1,2,...,m;

nebo

Maximalizovat

q_1 + q_2 + ... + q_n

za podmínek

a_{11}q_1 + a_{12}q_2 + ... +a_{1n}q_n \leq 1;

...

...

...

a_{m1}q_1 + a_{m2}q2 + ... +a_{mn}q_n \leq 1;

q_j \geq 0; j=1,2,...,n;

Ať už je tedy úloha řešena minimalizací nebo maximalizací, v simplexové tabulce se nachází řešení obou úloh, tj. určí se rovnovážné strategie x° a y° a z hodnoty účelové funkce cena hry v. +more Jelikož jsou všechny prvky aij kladné, obě úlohy mají přípustné řešení a tedy i řešení optimální.

Další metody hledání rovnovážných strategií

Pro důkaz základní věty maticových her, byla v předchozí kapitole použita metoda hledání rovnovážných strategií pomocí řešení úlohy lineárního programování. Co se týče výpočetní efektivnosti, nemá tato metoda konkurenci. +more Je to dáno i tím, že v dnešní době existuje pro řešení těchto úloh mnoho počítačových aplikací, které prošly dlouholetým vývojem až k relativní dokonalosti. V předchozí kapitole byla pro nalezení řešení vyzdvihnuta především simplexová metoda, řešení je ovšem možné nalézt pomocí jakékoli metody lineárního programování. V literatuře o maticových hrách se dají nalézt ještě další metody, které nejsou závislé na postupech lineárního programování a pomocí nichž lze rovnovážné strategie také nalézt.

Grafické určení

Tuto metodu lze použít pouze v případě, že hráč 1 má pouze 2 ryzí strategie a je možné ji řešit pomocí grafického znázornění soustavy lineárních funkcí a nalezení maxima z těchto funkcí odvozené.

Uvažujme tedy hru s maticí typu (2,n)

A=\begin{pmatrix} a_{11} & a_{12} & ... & a_{1n} \\ a_{21} & a_{22} & ... & a_{2n} \end{pmatrix}

Protože má hráč na výběr pouze ze 2 strategií, může být smíšená strategie popsána jediným parametrem x∈ . Tento parametr udává pravděpodobnost volby první strategie. +more Pravděpodobnost volby druhé strategie pak odpovídá 1-x. Střední hodnoty výhry hráče 1 jsou při ryzích strategiích hráče 2 následující:.

g_j(x)=xa_{1j} + (1-x)a_{2j}, \quad j=1,2,...,n

V grafickém znázornění jsou to přímky definované na intervalu . Sestrojením grafu a nalezením maxima zjistíme hodnotu x i cenu hry. +more Rovnovážné strategie hráče 1 jsou pak [x, 1-x]. Pro nalezení rovnovážných strategií hráče 2 se využije věty o komplementaritě z teorie duality v lineárním programování. Při hledání hodnoty x z grafu mohou nastat některé komplikace. Především maximu se může nacházet v bodě x=0 nebo x=1. Pak má hráč 1 ryzí rovnovážné strategie a hráč 2 rovněž. Nebo se může stát, že hodnota x není určena jednoznačně, to znamená že existují alternativní rovnovážné strategie.

Popsaná grafická metoda lze upravit i pro matice typu (m, 2) a za cenu jistých komplikací i pro matice typu (3, n) a (m, 3)

Výpočet metodou fiktivní hry

G. W. +moreBrown navrhl metodu pro vyhledávání rovnovážných strategiích v maticových hrách, která vychází z přirozeného principu postupného učení z konfliktních situací. Tuto metodu nazval metodou fiktivní hry. Používat tuto metodu při hledání rovnovážného řešení v běžné maticové hře nemá žádný význam, protože existují mnohem efektivnější metody, s kterými je nalezení řešení podstatně jednodušší. Princip této metody je však možné uplatnit i v modelech jiných rozhodovacích situací, pro které nejsou žádné metody k nalezení optimálního řešení k dispozici. Díky této metodě lze nalézt alespoň přibližné odhady optimálních strategií. Důkaz konvergence metody fiktivní hry (uveden v knize) k rovnovážným strategiím maticových her je jeden z nejsložitějších, který se v teorii maticových her vůbec vyskytuje.

Pro jednoduché objasnění principu fiktivní hry si lze představit maticovou hru, kde 2 hráči hrají opakovaně partie matice A, přičemž si své rovnovážné strategie neumějí vypočítat. Aby se hráč správně rozhodl, bude sledovat volbu strategie hráče 2 a přitom bude svoji strategii přizpůsobovat tak, aby maximalizoval svoji výhru. +more Vedou-li si oba hráči záznam o tom, které strategie kolikrát použili, mohou získat odhad svých smíšených rovnovážných strategií tak, že vydělí počty použitých strategií počtem odehraných fiktivních partií. Stupeň přiblížení ke správným hodnotám je možné odhadnout z intervalového odhadu ceny hry, který lze získat při realizaci výpočetního schématu.

Řešení pomocí diferenciálních rovnic

Jedná se o metodu, kterou navrhli G. W. +more Brown a J. von Neumann. Řešit maticovou hru soustavou diferenciálních rovnic je opět trochu zbytečné, když lze tyto úlohy řešit prostředky lineární algebry. Tato metoda má však pozoruhodné rysy, proto stojí za zmínku. Jedná se o matematickou formulaci intuitivního postupu jak najít optimální strategie postupným zlepšováním libovolné výchozí strategie.

Princip této metody se opírá o následující větu:

Ke každé maticové hře s obecnou maticí B existuje hra s maticí A, která je asymetrická, přičemž obě hry jsou ekvivalentní v tom smyslu, že rovnovážné smíšené strategie jedné hry lze získat z rovnovážných strategií druhé hry provedením několika elementárních aplikací.

Při skutečném použití této metody pro výpočet rovnovážných strategií je nutné soustavu diferenciálních rovnic řešit numerickými metodami a výsledný algoritmus je velmi podobný metodě fiktivní hry. Více o této metodě viz

Odkazy

Reference

Související články

Teorie her * Simulace * Kognitivní věda * John Nash * Equilibrium * Souboj pohlaví * No-win situation

Externí odkazy

[url=http://psh. ntkcz. +morecz/skos/PSH11427/html/cs]Rozcestník k nalezení materiálů o teorii her [/url] * [url=http://stanford. library. usyd. edu. au/entries/game-theory/]Podrobné informace o teorii her[/url].

Kategorie:Teorie her Kategorie:Diskrétní matematika Kategorie:Umělá inteligence Kategorie:Hry Her Kategorie:Aplikovaná matematika Kategorie:Počítače a šachy