Zobrazení zdroje stránky Hra s nulovým součtem

'''Hra s nulovým součtem''' je termín používaný v [[teorie her|teorii her]]. Patří do skupiny her popisující [[antagonistický konflikt|antagonistické konflikty]] – co jeden hráč získá, druhý ztrácí, takže spolupráce v těchto konfliktech nemá smysl. Jakoukoliv [[hra s konstantním součtem|hru s konstantním součtem]] lze transformovat na ekvivalentní hru s nulovým součtem, protože přičtením [[konstanta|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&nbsp;Kč, ten kdo prohraje −1&nbsp;Kč. '''1&nbsp;+&nbsp;(−1)&nbsp;=&nbsp;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:<ref name="manas">MAŇAS, Miroslav. ''Teorie her a její aplikace''. první vydání. Praha : SNTL, 1991. 280 s.</ref>
# '''Množinou hráčů''' v obecném případě očíslovaných [[přirozená čísla|přirozenými čísly]] {1, 2, …, N}
# '''Množinou prostorů strategií''' {X<sub>1</sub>, X<sub>2</sub>, …, X<sub>N</sub>}, které jsou přiřazeny jednotlivým hráčům
# '''Množinou výplatních funkcí''' {f1(x<sub>1</sub>, x<sub>2</sub>, …, x<sub>N</sub>),…, f<sub>N</sub>(x<sub>1</sub>,x<sub>2</sub>, …, x<sub>N</sub>)}, které jsou rovněž přiřazeny jednotlivým hráčům. Každá výplatní funkce je definována na [[kartézský součin|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. Dále že mají hráči dokonalé informace, tj. znají možnosti ([[Strategie (teorie her)|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<ref name="dlouhy">Dlouhý, Martin - Fiala, Petr ''Úvod do teorie her'' Oeconomica, 2007. {{ISBN|978-80-245-1273-0}}</ref>

<math>f_1(x,y)+f_2(x,y)=K,</math>

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''. 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:

<math>f_1(x,y)=-f_2(x,y)</math>

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'' . Pro výplatní funkce hráčů platí:

<math>f_1(x,y^o)\leq f_1(x^o,y^o)</math> a <math>f_2(x^o,y)\leq f_2(x^o,y^o)</math>

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 ''f<sub>1</sub>(x, y) = f(x, y)'' a výplatní funkci hráče 2 jako ''f<sub>2</sub>(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. Výše uvedené podmínky nerovnosti lze tedy uvést zjednodušeně ve tvaru:

<math>f(x,y^o)\leq f(x^o,y^o)\leq f(x^o,y)</math>

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. [[Nashova rovnováha|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 [[matice|maticí]] ''A = (a<sub>ij</sub>), i = 1, 2,..., m; j = 1, 2,..., 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 ''a<sub>ij</sub>'' odpovídá výplatě hráče 1. Výplata hráče 2 je pak definována jako opačná hodnota ''a<sub>ij</sub>'' tedy ''-a<sub>ij</sub>''. Tento model se nazývá [[maticová hra]] a matici '''A''' nazýváme '''výplatní maticí'''.

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

Řešení této hry respektive Nashovo rovnovážné řešení získáme nalezením [[sedlový bod|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á ''-a<sub>ij</sub>''; pokud vybereme minimum v řádku, pro hráče 2 je to maximum). Nalezneme-li sedlový bod s hodnotou ''a<sub>ij</sub>'', potom i-tá strategie hráče 1 a j-tá strategie hráče 2 jsou optimální rovnovážné strategie a tuto hodnotu ''a<sub>ij</sub>'' nazýváme '''cenou hry'''. Takto nalezené řešení nazýváme Nashovou rovnováhou (rovnovážným řešením) v [[ryzí strategie|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.
# 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. 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.

<math>
\begin{pmatrix}
5 & 6 & \left|(4)\right| & 5 \\
\left|-2\right| & 5 & 3 & (7) \\
(8) & (7) & \left|-2\right| & 6 
\end{pmatrix}
</math>
Matice má jeden sedlový prvek.

<math>
\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}
</math>
Matice má čtyři sedlové prvky.

<math>
\begin{pmatrix}
(2) & 1 & \left|0\right| \\
\left|0\right| & (2) & (3) 
\end{pmatrix}
</math>
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'''. 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. 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:
<math>
\begin{pmatrix}
0 & +1 & -1 \\
-1 & 0 & +1 \\ 
+1 & -1 & -0 
\end{pmatrix}
</math>

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). Tyto strategie nazýváme '''smíšenými (pravděpodobnostními) strategiemi'''. Ryzí strategie jsou tedy zvláštním případem ([[podmnožina|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.

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

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

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. konstantním) součtem stačí sledovat výplatní funkci prvního hráče.

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

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]]:

<math>
 x^TA\bar{y}^o \leq \bar{x}^{oT}Ay^o \leq \bar{x}^{oT}Ay
</math>

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. V obecném případě se dá řešení získat vypočítáním úlohy [[lineární programování|lineárního programování]] [[simplexová metoda|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'''''

<math>
p_1 + p_2 + ... + p_m
</math>

za podmínek

<math>
a_{11}p_1 + a_{21}p_2 + ... +a_{m1}p_m \geq 1;
</math>

<math>
...
</math>

<math>
...
</math>

<math>
...
</math>

<math>a_{1n}p_1 + a_{2n}p2 + ... +a_{mn}p_m \geq 1;</math>

<math>p_i \geq 0; i=1,2,...,m;</math>

nebo

'''''Maximalizovat'''''

<math>
q_1 + q_2 + ... + q_n
</math>

za podmínek

<math>
a_{11}q_1 + a_{12}q_2 + ... +a_{1n}q_n \leq 1;
</math>

<math>
...
</math>

<math>
...
</math>

<math>
...
</math>

<math>a_{m1}q_1 + a_{m2}q2 + ... +a_{mn}q_n \leq 1;</math>

<math>q_j \geq 0; j=1,2,...,n;</math>

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. Jelikož jsou všechny prvky ''a<sub>ij</sub>'' 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. 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í funkce|lineárních funkcí]] a nalezení maxima z těchto funkcí odvozené.

Uvažujme tedy hru s maticí typu (2,n)
<math>
A=\begin{pmatrix}
a_{11} & a_{12} & ... & a_{1n} \\
a_{21} & a_{22} & ... & a_{2n}
\end{pmatrix}
</math>

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∈ <0,1>. Tento parametr udává pravděpodobnost volby první strategie. 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í:

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

V grafickém znázornění jsou to přímky definované na intervalu <0,1>. Sestrojením grafu a nalezením maxima zjistíme hodnotu ''x'' i cenu hry. 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)<ref name="manas" />

==== Výpočet metodou fiktivní hry ====
G.W.Brown<ref name="brown-neumann">Brown, G.W. – Neumann, J. von: ''Solutions of games differentials equtations''. Ve: Contibutions to the theory of games Vol. 1 (M. W. Kuhn - A. W. Tucker (red.)). Princeton, Princeton University Press 1950, str. 73 – 79</ref> navrhl [[metoda|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<ref name="szep-forgo">Szep J. – Forgo, F.: ''Introduction to the theory of games''. Budapest, Akadémiái Kiado 1985</ref>) 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 (hra)|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. 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 [[interval (matematika) |interval]]ové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. Brown a [[John von Neumann|J. von Neumann]].<ref name="brown-neumann" /> Řešit maticovou hru soustavou [[diferenciální rovnice|diferenciálních rovnic]] je opět trochu zbytečné, když lze tyto úlohy řešit prostředky [[lineární algebra|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<ref name="brown-neumann" />

== Odkazy ==
=== Reference ===
<references/>

=== Související články ===
* [[Teorie her]]
* [[Simulace]]
* [[Kognitivní věda]]
* [[John Forbes Nash|John Nash]]
* [[Equilibrium (ekonomika)|Equilibrium]]
* [[Souboj pohlaví (teorie her)|Souboj pohlaví]]
* [[No-win situation]]

=== Externí odkazy ===

* {{Cs}} [http://psh.ntkcz.cz/skos/PSH11427/html/cs Rozcestník k nalezení materiálů o teorii her ]{{Nedostupný zdroj}}
* {{en}} [http://stanford.library.usyd.edu.au/entries/game-theory/ Podrobné informace o teorii her] {{Wayback|url=http://stanford.library.usyd.edu.au/entries/game-theory/ |date=20091206124423 }}
{{Autoritní data}}

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