Teorie her – úvod a motivace
Jiřina Novotná
Masarykova Univerzita, fakulta Pedagogická, katedra matematiky
e-mail: novotna@ped.muni.cz

Abstrakt

Teorie her se zabývá jakýmikoliv situacemi, v nichž se střetávají zájmy jednotlivců či skupin, přičemž jednání jedné strany ovlivňuje, ale plně neurčuje výsledek určité události, který závisí také na tom, jaká opatření podnikne druhá strana. Takovéto situace se vyskytují nejen ve společenských hrách, ale velmi často jde o konfliktní, problémové situace charakteru ekonomického, vojenského, sportovního, apod. V [1] je uvedeno, že teorie her proniká do stále většího počtu různých oblastí, jsou to  finance, telekomunikace, doprava, počítačové systémy, sociologie, psychologie, medicína, biologie, životní prostředí, zemědělství politologie, právo, etika, obrana. 

Teorie her je poměrně mladá disciplína. Její základy položil v roce 1928 americký matematik John von Neumann, který definoval základní pojmy a také dokázal větu o existenci řešení, která platí pro každou maticovou hru. Tato věta je v teorii her nazývána základní větou teorie her a mohly bychom ji formulovat takto: Každá maticová hra má řešení v ryzích nebo smíšených strategiích.
 
S jednoduchými hrami a jejich způsoby řešení by se mohli již seznámit žáci na konci základní školní docházky a v dalším průběhu studia by  mohl být tento atraktivní obor dále rozvíjen. Je škoda, že na většině učitelských fakult se studenti o teorii her nic nedozví.

Příklad 1. Výrobce uvádí na trh nový výrobek, na kterém má zisk 200 Kč. Uvědomuje si, že při běžné kontrole jakosti výrobků se dostane na trh určité množství vadných výrobků a odhaduje, že každá záruční oprava ho bude stát průměrně  50 Kč. Protože doposud neví, jaké procento vadných výrobků projde běžnou kontrolou, rozhoduje se mezi dvěma možnostmi:
I.	ponechat pouze běžnou kontrolu a opravy provádět v záruce,
II.	provést speciální kontrolu, která ho bude pro každý výrobek stát 5 Kč, a zjištěné závady odstranit, přičemž se předpokládá, že každá oprava přijde průměrně na 20 Kč.

Matice hry je:
		Náhoda			
		dobrý	vadný			
Výrobce A	I.	200	150	150		
	II.	195	175	175	maximin	
		200	175			
			minimax		Sedlový bod	

Příklad 2. Student Ambrož má nepříjemný pocit, že by mohl být zítra vyvolán ze zeměpisu i z chemie. Zbývá mu však čas připravit se pořádně pouze do jednoho předmětu, a proto by se měl rozhodnout pro chemii nebo pro zeměpis.  Při svém rozhodování hodnotí jednotlivé možnosti body tak, jak je to uvedeno v následující tabulce. V jakém poměru by měl optimálně rozdělit dobu na přípravu na oba předměty? 
Řešíme užitím smíšených strategií
	Matice hry  je

		učitel					
		vyvolává	nevyvolává		maximum	rozdíl	poměr	
Student se naučí	Z	3	0		0	3	2:3	
	CH	1	3		1	-2		
								
	minimax	3	3					
	rozdíl	2	3					
	poměr	3:2						

Pro studenta bude nejvýhodnější, jestliže 0,4 svého času věnuje zeměpisu a 0,6 chemii. 

Příklad 4. Vedoucí obchodu s potravinami z rekreační oblasti uvažuje, kolik má na sobotu a na neděli objednat litrů mléka. Má zkušenost, že při slunečném počasí se prodá 1000 litrů mléka, při chladném suchém počasí se prodá 700 litrů mléka a při deštivém počasí 500 l mléka. Jestliže objednávka převyšuje spotřebu ztrácí prodejna na každém přebytečném přebytečném litru mléka 1 Kč. Jestliže je objednávka menší než poptávka, ztrácí prodejna 0,50 Kč na každém chybějícím litru mléka, což je zisk, který mohla prodejna realizovat. Jakou strategii má volit vedoucí prodejny, aby její zisk byl maximální. 

Matice hry je: 

		Počasí

	
		 	 	 	
Vedoucí	1000l	500	50	-250	
	700l	200	350	50	
	500l	0	150	250	

Napíšeme si soustavu příslušnou k této hře pro relativní četnosti x1,  x2 ,  x3  použití ryzích strategií hráče A, v je cena hry

Řešení eliminační metodou:				   Po úpravách:
							
x1	x2	x3	s1	s2	s3	v	b	
 1	1	1	0	0	0	0	1	
500	200	0	-1	0	0	-1	0	
50	200	150	0	-1	0	-1	0	
-250	50	250	0	-1	-1	-1	0	
0	0	0	0,5	0	0,5	1	125	
1	0,4	0	-0	0	0	0	0,25	
0	0,6	1	0	0	-0	0	0,75	
0	-190	0	-0,4	1	0,4	0	0	

1. Úvod

Teorie her se zabývá jakýmikoliv situacemi, v nichž se střetávají zájmy jednotlivců či skupin, přičemž jednání jedné strany ovlivňuje, ale plně neurčuje výsledek určité události, který závisí také na tom, jaká opatření podnikne druhá strana. Takovéto situace se vyskytují nejen ve společenských hrách, ale velmi často jde o konfliktní, problémové situace charakteru ekonomického, vojenského, sportovního, apod. V [1] je uvedeno, že teorie her proniká do stále většího počtu různých oblastí, jsou to  finance, telekomunikace, doprava, počítačové systémy, sociologie, psychologie, medicína, biologie, životní prostředí, zemědělství politologie, právo, etika, obrana. 

K mohutné expanzi teorie her do oblasti evoluční biologie došlo po roce 1973, kdy J.M. Smith a G. R. Price publikovali svoji práci [4]. Ačkoli se to na první pohled zdá paradoxní, postupem času se ukázalo, že nejslibnější aplikace teorie her jsou právě v biologii. Teorie her se dokonce jeví fungovat tím lépe, čím méně je vyvinutá schopnost organismu přemýšlet. Zatímco ve společenských vědách je předpoklad racionálnosti „hráčů“ často značně ošidný, v evoluční biologii s jeho splněním nebývají potíže. 

Obyčejně se uvažuje následující model: hráči v strategické hře jsou geny, strategií je geny určené „předprogramované“ chování, tj. specifikace toho, co bude jedinec dělat v jakékoli situaci, v níž se může ocitnout, výplatní funkcí je reprodukční „zdatnost“ genů, tj.schopnost zachovat se a šířit se, a tím zvýšit svou frekvenci v genotypu populace. Ústředním pojmem při řešení evolučních modelů je evolučně stabilní strategie, která je obvykle definována takto: používají-li všichni členové populace tuto strategii, pak žádný  mutant (tj. jedinec používající jinou strategii) nemůže populaci napadnout ve smyslu přírodního výběru (je méně úspěšný v reprodukci).

Teorie her je poměrně mladá disciplína. Její základy položil v roce 1928 americký matematik John von Neumann, který definoval základní pojmy a také dokázal větu o existenci řešení, která platí pro každou maticovou hru. Tato věta je v teorii her nazývána základní větou teorie her a mohly bychom ji formulovat takto:
Každá maticová hra má řešení v ryzích nebo smíšených strategiích.

S jednoduchými hrami a jejich způsoby řešení by se mohli již seznámit žáci na konci základní školní docházky a v dalším průběhu studia by  mohl být tento atraktivní obor dále rozvíjen. Je škoda, že na většině učitelských fakult se studenti o teorii her nic nedozví.
	 
2. Hry se sedlovým bodem

Uvedeme několik jednoduchých her a strategií jejich řešení, přičemž strategií rozumíme předpis, který určuje, jaký tah má hráč zvolit v kterékoliv situaci, která může ve hře nastat. 

Příklad 1. Výrobce uvádí na trh nový výrobek, na kterém má zisk 200 Kč. Uvědomuje si, že při běžné kontrole jakosti výrobků se dostane na trh určité množství vadných výrobků a odhaduje, že každá záruční oprava ho bude stát průměrně  50 Kč. Protože doposud neví, jaké procento vadných výrobků projde běžnou kontrolou, rozhoduje se mezi dvěma možnostmi:

III.	ponechat pouze běžnou kontrolu a opravy provádět v záruce,
IV.	provést speciální kontrolu, která ho bude pro každý výrobek stát 5 Kč, a zjištěné závady odstranit, přičemž se předpokládá, že každá oprava přijde průměrně na 20 Kč.

Uvedenou hru můžeme znázornit pomocí dvou modelů: stromu hry a matice hry. Strom hry sestavíme takto: Každé situaci odpovídá jeden uzel, z každého uzlu vychází určitý počet hran odpovídajících možným rozhodnutím, tzv. tahům daného hráče. Jestliže se hráč , který je na řadě rozhodne pro nějaký tah, navodí novou situaci, v níž se rozhoduje druhý hráč – této nové situaci odpovídá jistý uzel stromu spojený s předchozí hranou.  Při znázorňování se většinou postupuje  ve směru shora dolů a pravidelně se střídají uzly, v nichž se rozhoduje první hráč, a uzly, v nichž se rozhoduje druhý hráč. Výplatní matici hry sestavíme tak, že do záhlaví řádků napíšeme možné strategie hráče A, a do záhlaví sloupců možné strategie hráče B a do polí tabulky výhry hráče A při použití těch strategií, které jsou uvedeny v záhlaví řádku a sloupce, kterém se kříží v příslušném poli tabulky.

Strom hry je v tomto případě jednoduchý.              Matice hry je
		Náhoda	
		dobrý	vadný	
Výrobce A	I.	200	150	
	II.	195	175	

             

								

Obrázek 1. Strom hry

Maximální garantovanou výhru hráče A zjistíme tak, že v každém řádku matice hry určíme minimální prvek a z těchto minimálních prvků najdeme maximální prvek – tzv. maximinová strategie. V našem případě je tímto maximálním minimem číslo 175, které se nazývá maximin, nebo též dolní cena hry, neboť je to minimální výhra, kterou má hráč A zaručenou při použití strategie, která odpovídá řádku,  v němž leží maximin. Výplaty hráči B jsou opačná čísla k výplatám hráči A, takže maximalizace výplaty hráči B je totéž jako minimalizace výplaty hráči A. V každém sloupci matice hry určí tedy hráč B maximální prvek a mezi těmito prvky určí minimální – minimaxová strategie. Minimálním maximem je v našem případě číslo 175, tzv. minimax, nebo též horní cena hry, která udává nejlepší výsledek, který si může B zaručit bez ohledu na to , co hraje A. Jestliže maximin je roven minimaxu, je tento prvek výplatní matice minimálním prvkem ve svém řádku a maximálním ve svém sloupci a nazývá se sedlový bod a udává tzv. cenu hry.

Sedlový bod je 175, optimální strategie je ryzí strategií II., neboť zaručuje z každého výrobku minimální zisk 175 Kč, i kdyby byly všechny výrobky vadné. 

3. Hry bez sedlového bodu

Nemá-li výplatní matice sedlový bod, hledáme optimální řešení užitím smíšených strategií, jak ukážeme v následujícím příkladu. Využijeme následující pravidlo: Poměr ryzích strategií r1 : r2 v optimální smíšené strategii hráče A ve hře (2,2) bez sedlového bodu je roven převrácenému poměru absolutních hodnot rozdílu prvků v prvním a druhém řádku výplatní matice. Důkaz je uvedený [6] na str. 93, 94.

Příklad 2. Student Ambrož má nepříjemný pocit, že by mohl být zítra vyvolán ze zeměpisu i z chemie. Zbývá mu však čas připravit se pořádně pouze do jednoho předmětu, a proto by se měl rozhodnout pro chemii nebo pro zeměpis.  Při svém rozhodování hodnotí jednotlivé možnosti body tak, jak je to uvedeno v následující tabulce. V jakém poměru by měl optimálně rozdělit dobu na přípravu na oba předměty? 

	Matice hry  je

		učitel					
		vyvolává	nevyvolává		maximum	rozdíl	poměr	
Student se naučí	Z	3	0		0	3	2:3	
	CH	1	3		1	-2		
								
	minimax	3	3					
	rozdíl	2	3					
	poměr	3:2						

Pro studenta bude nejvýhodnější, jestliže 0,4 svého času věnuje zeměpisu a 0,6 chemii. 

V jinak formulovaných úlohách , které se řeší užitím smíšených strategií, je nutné, aby hráči prováděli volbu strategií v uvedeném poměru zcela nahodile, aby svěřili volbu svých strategií v daném poměru náhodě. Např. má-li hráč používat strategie v poměru 1 : 2, může postupovat takto: Dá si do kapsy dvě bílé kuličky a jednu černou. Když vytáhne z kapsy černou kuličku tak, aby ji soupeř neviděl, použije první strategii. To, že při větším počtu her budou oběma hráči dodržena optimální poměry ryzích strategií, je při této volbě strategií zaručeno zákony počtu pravděpodobnosti.

4. Hry s dominovanými strategiemi

Hry o velkém počtu strategií můžeme zjednodušit tak, že vynecháme dominované (ryzí nebo smíšené) strategie, přičemž říkáme, že strategie s1 dominuje nad strategií s2, jestliže strategie s2 nepřinese hráči A při žádné strategii hráče B větší výhru než strategie s1. Na eliminování dominovaných strategií se s výhodou užívá grafického řešení, pomocí něhož se snáze určí optimální strategie z příslušné subhry (2,2), (matice subhry je podmaticí matice hry). Grafické řešení si ilustrujeme na následujícím příkladě.

Příklad 3. Hráč A napíše na papír některé z čísel 1, -2, 3, -4, 5. Hráč B hádá, jestli napsané číslo je kladné nebo záporné. Když uhodne, vyhrává absolutní hodnotu napsaného čísla v Kč, když neuhodne, prohrává absolutní hodnotu napsaného čísla v Kč.

Matice hry je

                                                                    B
                                                    kladné            záporné
-1	1	
2	-2	
-3	3	
4	-4	
-5	5	
		 	1	        		        
		          -	2                                       	    
		A        	3	        		         
		          -	4	                                       
			5	                                    

  

Poměr užití ryzích strategií hráče B v jeho optimální smíšené strategii označíme a : b, po sehrání  a + b her platí následující vztahy

-a   +   b   ≥   v . (a + b)
2a  -  2b   ≥   v . (a + b)
	-3a  + 3b   ≥   v . (a + b)			
4a  -  4b   ≥   v . (a + b)
-5a  + 5b   ≥   v . (a + b),				(1)

kde v je cena hry. Znaménko ≥ je v uvedených vztazích proto, že proti dominovaným strategiím hráče A může hráč B dosáhnout větší výhry než je cena hry.
Po úpravě a substituci
   			x1  =	                         x2   =       ,

mají podmínky (1) tvar:
                                             v   ≤   -2x1  +    1
                                             v   ≤   -2
                                             v   ≤   -6x1  +   3
	                                             v   ≤   -4
	                                             v   ≤   -10x1   +   5  					(2)      

který znázorníme graficky (viz. obr. 1), přičemž s1: v=-2x1+1, s2: v=-2, s3: v=-6x1+3, s4: v=-4, s5: v=-10x1+5.

Obrázek 2. Grafické znázornění podmínek (2)

Z obrázku číslo jedna vidíme, že strategie s1, s2, s3 neovlivňují řešení, jsou dominovány strategiemi s4 a s5. Optimální strategie hráče B můžeme nyní určit řešením subhry, jejíž matice je :

		B				
		r1	r2	maximin	rozdíl	poměr	
A	s4	4	-4	-4	8	10:8=5:4	
	s5	-5	5	-5	-10		
minimax		4	5				
rozdíl		9	-9				
poměr		9:9=1:1				

Optimální smíšená strategie je pro hráče A s4:s5=5:4 a pro hráče B r1:r2=1:1.
Při grafickém řešení transformujeme vlastně algebraický model problémové situace na model analytické geometrie, ten potom na kartézské grafy. 

5.Řešení her typu (m, n)

Hry typu (m, n), kde m ≥ 2, n ≥ 2, se řeší kromě dosud popsaných metod, které jsou výhodné jen pro hry (2, n), užitím determinantů matic, eliminačními metodami lineárních rovnic, přibližně užitím jednoduchého algoritmu, pomocí grafu – stromů hry. Následující hru „proti přírodě“ vyřešíme dvěma výše uvedenými metodami. 

Příklad 4. Vedoucí obchodu s potravinami z rekreační oblasti uvažuje, kolik má na sobotu a na neděli objednat litrů mléka. Má zkušenost, že při slunečném počasí se prodá 1000 litrů mléka, při chladném suchém počasí se prodá 700 litrů mléka a při deštivém počasí 500 l mléka. Jestliže objednávka převyšuje spotřebu ztrácí prodejna na každém přebytečném přebytečném litru mléka 1 Kč. Jestliže je objednávka menší než poptávka, ztrácí prodejna 0,50 Kč na každém chybějícím litru mléka, což je zisk, který mohla prodejna realizovat. Jakou strategii má volit vedoucí prodejny, aby její zisk byl maximální. 

Matice hry je: 

		Počasí

	
		 	 	 	
Vedoucí	1000l	500	50	-250	
	700l	200	350	50	
	500l	0	150	250	

Poměr strategií vedoucí koupit 1000l, 700l nebo 500l mléka je: 

s1 : s2 : s3 = p1 : p2 : p3,

kde p1, p2, p3 jsou determinanty podmatic typu (2, 2) matice typu (3, 2), která vznikne z matice hry tak, že od prvního sloupce matice hry odečteme její druhý sloupec, výsledek je první sloupec matice typu (3, 2), jejíž druhý sloupec obdržíme odečtením třetího sloupce matice hry od jejího druhého sloupce. 

V našem případě je matice typu (3, 2) následující: 

450	300	
-150	300	
-130	-100	

, , 

s1:s2:s3 = 1:0:3

Vedoucí by měla po každé nakupovat:  mléka, a tím má zaručeno, že zisk neklesne pod 125Kč.

Řešení eliminační metodou:

Napíšeme si soustavu příslušnou k této hře pro relativní četnosti x1,  x2 ,  x3  použití ryzích strategií hráče A, v je cena hry. 

x1	x2	x3	s1	s2	s3	v	b	
1	1	1	0	0	0	0	1	
500	200	0	-1	0	0	-1	0	
50	200	150	0	-1	0	-1	0	
-250	50	250	0	-1	-1	-1	0	

Po úpravách:

0	0	0	0,5	0	0,5	1	125	
1	0,4	0	-0,001	0	0,001	0	0,25	
0	0,6	1	0,001	0	-0,001	0	0,75	
0	-190	0	-0,4	1	0,4	0	0	

Relativní četnost užití ryzích strategií vedoucí prodejny jsou: 

x1 = 0,25, x2 = 0, x3 = 0,75

optimální smíšená strategie vedoucí prodejny je: 

s1 : s2 : s3 = 1 : 0 : 3,
přičemž cena hry je 125.

Eliminační metody jsou pro dosti veliká m a n pracné, jsou vhodné pro počítač, pro rychlé rozřešení přibližné řešení maticových her, které umožňují najít pro oba hráče strategie, které nejsou sice optimální, ale budou již zaručovat výhru jen málo se lišící od cena hry. Pro tato řešení byl vytvořen předpis algoritmického typu, (jeho blokové schéma viz [5] str.111).

S  rychlým rozvojem výpočetních technologií se postupně přestalo využívat postupů , jimiž dostáváme postupné řešení. 

6. Závěr

Nyní uvedeme několik klasifikací jednotlivých typů her:

I.
1.	Hry s úplnou informací – oba hráči jsou informováni o všech předchozích tazích svých i protihráčových 

2.	Hry s neúplnou informací – hráči nejsou informováni o všech tazích.

Hry s neúplnou informací se dají normalizovat na hry s úplnou informací.

II.
1.	Hry s jedním tahem

2.	Hry s více tahy – dají se určitým způsobem transformovat na hry s jedním tahem.

III.
1.	Hra s nulovým součtem výplat – součet výplat všech hráčů je roven nule.

2.	Hry s nenulovým součtem výplat – na výhry hráčů připadá jen část vsazené sumy

IV.
1.	Hry se sedlovým bodem 

2.	Hry bez sedlového bodu

V.
1.	Hry neantagonistické - protihráč nepoužívá záměrně žádnou strategii aby vyhrál, jsou to takzvané hry proti přírodě. 

2.	Antagonistické hry – protivník používá záměrně takové strategie aby minimalizoval svoji prohru a zároveň maximalizoval svoji výhru.

Literatura:

[1]	Hykšová, M: Teorie her – prezentace a motivace in Prezentace matematiky. Sborník příspěvků z mezinárodní konference, Liberec 2003, ISBN 80-7083-739-X.
[2]	Maňas, M: Teorie her a optimální rozhodování. Praha, SNTL, 1974.
[3]	Maňas, M: Teorie her a její aplikace. Praha, SNTL, 1991.
[4]	Maynard Smith, J. – Price, G. R.: The Logic of Snímal Conflict. Nature 246 (1973), 15-18
[5]	Říha, O: Základy teorie her, Jednota čs. Matematiku a fyziků, Praha, 1973.
[6]	Vlach, M: Teorie her, Statní pedagogické nakladatelství Praha, 1988. 

[7]	Von Neumann, J.: Zur Theorie der Gesellschaftsspiele, Mathematische Annalen 100 (1928), 295-320 [anglický překlad: On the Theory of Games Strategy, In: Contributions to the Theory of Games, Volume IV, Tucker, A.W. – Luce, R.D.,ed.,Princeton, Princeton University Press, 1959]
[8]	Von Neumann, J. – Morgenstern, O.: Tudory of Games and Economic Behavior. Princeton, Princeton University Press, 1944.