Statické hry a Nashova rovnováh
Ivica Kopčoková
Teória hier
• Ekonomická vedná disciplína skúmajúca široké spektrum rozhodovacích situácií s viacerými účastníkmi pomocou modelov
• Nielen matematika, na hranici psychológie, biológie a ostatných disciplín
• A. Cournote (1838), model duopolu
• Neumann, Morgenstern, Theory of Games and Economic Behavior (1944)
Základné pojmy teórie hier	
hra	rozhodovacia situácia, konflikt
hráč	účastník konfliktu (firma, jedinec, politická strana, biologický druh)
stratégia	konkrétna alternatíva, ktorú môže hráč
optimálna stratégia	hráčom zvolená stratégia, ktorá je pre neho najvýhodnejšia
priestor stratégií	všetky možné alternatívy, ktoré sú hráčovi dostupné
výplatná funkcia	výsledok hry, tj. úžitok, výhra hráča v závislosti na stratégii
inteligentný hráč	má dokonalé informácie a maximalizuje výhru
Teória úžitku
• Úžitok = stupeň uspokojenia zo spotreby (udalosti) /subjektívny pojem/
• Kardinalistická x ordinalistická teória úžitku
• Úžitková funkcia u popisuje hráčovu sústavu preferencií u (a) > u(b) ak hráč preferuje a pred b
• Zachycuje individuálne preferencie, ktoré nieje možné medzi jednotlivcami porovnávať a sčítať
Racionálna voľba
• V každej danej situácii si hráč vyberie najlepšiu stratégiu z množiny stratégii podľa svojich preferencií
• Ak existuje možnosť viacerých rovnako preferovaných stratégií, hráč si vyberie stratégiu podľa preferencií minimálne tak dobrú ako ktorákoľvek iná stratégia
Strategická (normálna) hra
• množina hráčov {1,2,...N}
• pre každého hráča množina stratégií {SVS2,..SN}
• funkcie výplat u,: S1 xS2xxSN^R, i=(1,2,...N)
• pojem stratégie je zvyčajne interpretovaný ako "plán akcie"
• profilom stratégií s = (svs2,..sN) nazývame prvok z množiny
S = S1 x S2 xxSN. Predstavuje výber stratégií všetkých hráčov.
• výber stratégií všetkých hráčov okrem hráča i s.j = (svs2,.., Sj_vSj+1,.. sN)
čisté stratégie x zmiešané stratégie
Čas neexistuje, hráči sa rozhodujú simultánne, žiadny hráč nieje informovaný o voľbe druhého hráča v čase vlastného rozhodovania
Väzňovo dilema
• Dvaja podozrivý zo závažného zločinu sú držaní v cele. Polícia má dosť dôkazov na usvedčenie z menej závažného činu, ale pokiaľ ani jeden nebude svedčiť, nemá dostatok dôkazov na usvedčenie zo závažného zločinu.
• Ak obaja budú ticho, usvedčia ich z menšieho zločinu a dostanú 1 rok
• Bude svedčiť iba jeden z nich proti druhému, bude voľný, druhý dostane 10 rokov
• Ak obaja prehovoria, dostanú 5 rokov
HRACÍ: 2
MNOŽINA STRATÉGIÍ: {Ticho, Svedok} PREFERENCIE:
• P1: (Svedok, Ticho) 0 rokov; (Ticho, Ticho) 1 rok; (Svedok, Svedok) 5 rokov; (Ticho, Svedok) 10 rokov
• u/S,V >u1(T,T)> Ul(S,S) > Ul(T,S)
• P2: (Ticho, Svedok) 0 rokov; (Ticho, Ticho) 1 rok; (Svedok, Svedok) 5 rokov; (Svedok, Ticho) 10 rokov
• U2(T,S) > u2(T, T) > o/S,S; > u2(S, T)
• u,(S,7> 3 U1(T,T)= 2
uJT.S) = 0
• u2(T,S)= 3
u2(T,T)= 2
u2(S,S)= 1
u2(S, T)= 0
u/S, V= 3
U1(TJ)= 2
u/S,S;= 1
uJT.S) = O
u2(T,S)= u2(T, T)= u2(S,S)= u2(S, T) =
3 2 1 O
P2
		Ticho	Svedok
P1	Ticho	2,2	0,3
	Svedok	3,0	1,1
Bach alebo Stravinsky
známa aj ako Súboj pohlaví
• Dvaja ľudia idú na koncert. Jeden preferuje Bacha, druhý Stravinskeho. Nemá pre nich význam ísť na rozdielne koncerty.
HRÁČI: 2
MNOŽINA STRATÉGIÍ: {Bach, Stravinsky} PREFERENCIE:
• u,(B,B)=     2 . u2(S,S)= 2
u/S,S;=     1 u2(B,B)= 1
u,fß,S;=     0 u2(S,B)= 0
u/S,ßj=    0 u2(B,S)= 0
Bach Stravinsky
Bach Stravinsky
2,1	0,0
0,0	1,2
Mince
• Dvaja hráči naraz hádžu mincou. Ak padne rovnaká strana, H2 dá H1 korunu, ak rozdielne strany potom H1 dá H2 korunu. Každému ide len o vyhranú sumu.
• Antagonistický konflikt: H1 chce rovnakú stranu ako H2, H2 chce presný opak
HRÁČI: 2
MNOŽINA STRATÉGIÍ: {Hlava, Znak} PREFERENCIE:
. Ul(H,H)= 1
U1(Z,Z)= 1
u,(H,Z)= -1
u1(Z,H)= -1
. U2(H,H)= -1
u2(Z,Z)= -1
u2(H,Z)= 1
u2(ZH) = 1
Hlava
Znak
Hlava Znak
1,-1	-1,1
-1,1	1,-1
Dominancia
• Predpoklad: racionalita hráčov, maximalizácia zisku
• Presvedčenie možno definovať ako pravděpodobnostně rozdelenie nad stratégiami ostatných hráčov. V prípade, že hráč nemá žiadne špeciálne presvedčenie o tom, čo budú jeho súperi hrať, rozdelenie bude rovnomerné.
• V prípade existencie dvoch stratégií, z ktorých jedna je horšia ako druhá bez ohľadu na to, čo bude hrať protihráč si túto stratégiu hráč nikdy nevyberie. V takomto prípade hovoríme o dominovanej stratégii.
Definícia 1.1.3 ([3])
Hovoríme, že stratégia Si € 5, hráča i je ostro dominovaná, ak existuje taká stratégia s'i 6 Si hráča i, že
Ui(4t8rri)  > Ui(Si,S_i)
pre každé s_i € SĽj.
ak nahradíme striktnú nerovnosť neostrou (<) a existuje aspoň jedna kombinácia stratégií ostatných hráčov, kedy platí striktná nerovnosť, dostaneme definíciu slabo dominovanej stratégie
každý hráč je presvedčený o tom, že žiadny z jeho súperov si nezvolí dominovánu stratégiu
dominované stratégie z hry odstránime
po odstránení niektorej resp. niektorých stratégií sa môže stať, že v novovzniknutej hre budú niektoré stratégie dominované, aj keď predtým neboli
vznikla ďalšia dominovaná stratégia, ktorú na základe predpokladu racionality z hry odstránime. Tento proces sa nazýva iterovaná dominancia
V prípade, že je možné postupným odstraňovaním dominovaných stratégií dôjsť až k jedinému profilu, možno tento považovať za riešenie hry, pretože racionalita hráčov implikuje, že práve tento profil stratégií budú hráči hrať
Nashova rovnováha
• optimálnu stratégiu hráčov v konfliktnej situácii nájdeme pomocou Nashovej rovnováhy. NR je riešenie, v ktorom platí, že pokiaľ sa niektorý z hráčov nebude držať optimálnej stratégie a jeho súper áno, jeho výplata sa zníži
• „kto sa odchýli od optimálnej stratégie, nemôže si polepšiť"
Definícia 1.1.6 ([3])
Profil stratégií s* je Nashovým ekvilibriom hry G v čistých stratégiách, ak pre každého hráča i a pre všetky Sj € S platí:
UiislslJ^Utisi.slJ (1.4)
Definícia 1.1.7 ([3])
Nashovo ekvilibrium s* v čistých stratégiách je ostré, ak pre každého hráča i a pre všetky Si € S také, že Si ^ s* platí:
iii(s*, šíj > Uí(sí, s*i) (1.5)
Nashove ekvilibrium nemusí byť Pareto-optimiálne. Toto riešenie môže viesť k výsledku, ktorý aspoň pre jedného z hráčov prinesie nižší úžitok ako niektorý iný výsledok hry
Nashove ekvilibrium nemusí byť v hre jedinečné. Ak je v hre viac ekvilibrií, tak hráči nie sú bez dodatočných informácií schopní určiť jedno z nich, podľa ktorého by sa mali správať
NE: Väzňovo dilema
P2
Ticho Svedok 2,2 0,3 3,0 1*,1*
• (Ticho, Ticho) nespĺňa NE, ak si P2 vyberie Ticho, výplata P1 pri Svedok predčí výplatu pri Ticho. Jeden z hráčov sa môže odchýliť prilepšiť si
• (Svedok, Ticho) nespĺňa NE, ak si P1 vyberie Svedok, výplata P2 pri Svedok predčí tú pri Ticho
• (Ticho, Svedok) nespĺňa NE, ak si P2 vyberie Svedok, výplata P1 pri Svedok predčí tú pri Ticho
P1 Ticho Svedok
NE: Bach vs Stravinsky
Bach Stravinsky
Bach Stravinsky
2*,1*	0,0
0,0	r,2*
(Bach, Bach) a (Stravinsky, Stravinsky) odchýlenie sa hociktorého hráča znamená pre neho stratu
(B,S) a (S,B) jeden z hráčov si odchýlením od súčasnej stratégie prilepší
NE: Bach vs Stravinsky
zmena: obaja preferujú Bacha pred Stravinskym
Bach Stravinsky
Bach Stravinsky
2*,2*	0,0
0,0	1*,1*
opäť dve NE
(B, B) je viac preferované NE, ale ak dospejú do NE (S, S) ani jeden z hráčov nemá dôvod odkloniť sa od stratégie
Stratégia optimálnej odpovede (BR)
Definice 1.1.14 (Strategie optimální odpovědi (Best response)) Nechť s* — ( S je profil strategii. Strategii s* nazýváme optimální odpovědí na .s-V, pokud
w*(äLí,ä*) = max uí(s*_í,Sí). Množinu všech optimálních odpovedi na .sli značíme £(sli), tj.
pojem optimálna odpoveď použijeme k definícii NE
V rovnováhe žiadny z hráčov nemá dôvod (motiváciu) svoji stratégiu jednostranne meniť. To nastáva v prípade, že každý z hráčov volí optimálnu odpoveď na stratégie ostatných hráčov
BR nieje nič iné ako "zlúčenie" najlepších odpovedí každého hráča do jediného zobrazenia prislúchajúceho všetkým hráčom
Nájdite NE pomocou BR
	L	C	R
T	Í 1.2	2,1	1,0
M	Í 2,1	. 0,1	0,0
B	! 0,1	0,0	1,2
Nájdite NE pomocou BR
	L	C	R
T	1 1.2	I 2,1	1,0
M	i 2*,1	i 0,1	0,0
B	i 0,1	0,0	1,2
Nájdite NE pomocou BR
	L	c	R
T	Í 1.2	! 2*,1	1,0
M	I 2*,1	[ 0,1	0,0
B	! 0,1	0,0	1,2
Nájdite NE pomocou BR
	L	c	R
T	Í 1.2	! 2*,1	í 1*,0
M	I 2*,1	[ 0,1	0,0
B	! 0,1	0,0	! 1*,2
Nájdite NE pomocou BR
	L	c	R
T	! 1,2*	2*,1	í 1*,0
M	! 2*,1	. 0,1	0,0
B	! 0,1	0,0	! 1*,2
Nájdite NE pomocou BR
	L	c	R
T	! 1.2* !	2*,1	1*,0
M	!   2*,1* I	0,1*	0,0
B	! 0,1 I	0,0	1*,2
Nájdite NE pomocou BR
	L	c	R
T	! 1.2* !	2*,1	i i*,o j
M	j   2*,1* j	0,1*	|    0,0 |
B	! 0,1 I	0,0	!   1*,2* j
Nájdite NE pomocou BR
L C R
1,2*	2*,1	1*,0
2*,1*	0,1*	0,0
0,1	0,0