Opakované hry
Rostislav Staněk May 13, 2013
Nashova rovnováha: Zobecnění
SPE: Zobecnění
Aplikace
SPE a one-deviation
Profil strategií v nekonečně opakované hřeje SPE, pokud splňuje tzv. one-deviation vlastnost. Tj. pokud žádný hráč nemůže zvýšit svou výplatu, pokud se odchýlí na začátku jakékoliv podhry, ve které je první hráčem na tahu, při daných strategiích ostatních hráčů a zbytku své strategie.
Pro nekonečné hry platí, jen pokud je ô < 1.
Rostislav Staněk
Opakované hry
Nashova rovnováha: Zobecnění
SPE: Zobecnění
Aplikace
SPE
Grim-trigger strategie (definovaná výše) tvoří SPE, pokud ô ^ |
• Podhra po historii (C,C). Grimm-trigger je optimální, pokud 3(1-<$) + <$ ^2
• Podhra po jiné historii. Odchýlení není výhodné, protože ui(C, D) < ui(D, D) a volba C neovlivní další kola.
Rostislav Staněk
Opakované hry
Nashova rovnováha: Zobecnění
SPE: Zobecnění
Aplikace
Folk teorém
• Pro jakýkoli diskontní faktor je průměrná diskontovaná výplata každého hráče v SPE alespoň u/(D, D).
• (xi)*2) Je dosažitelný pár výplat v G, pro který platí
x; > Uj(D, D). Vždy existuje ô < 1 takový, že pokud ô > ô, pak existuje v G SPE ve které průměrná diskontovaná výplata hráče / je x,-.
Rostislav Staněk
Opakované hry
Nashova rovnováha: Zobecnění
SPE: Zobecnění
Aplikace
Minmax výplata
Ve vězňově dilematu nemohla průměrná diskontovaná výplata v rovnováze klesnout pod Uj(D,D).
Obecně nemůže průměrná diskontovaná výplata v rovnováze klesnout pod minmaxovou výplatu, definovanou následovně:
min   max u/(a,-, a_;)
Rostislav Staněk
Opakované hry
Nashova rovnováha: Zobecnění SPE: Zobecnění
Minmax výplata
Najděte minmaxovou výplatu v následující hře.
	A	B	C
A	4,4	3,0	1,0
B	0,3	2,2	1,0
C	0,1	0,1	0,0
Rostislav Staněk
Opakované hry
Nashova rovnováha: Zobecnění
SPE: Zobecnění
Aplikace
Folk teorém pro Nashovu rovnováhu
• Pro jakýkoliv diskontní faktor je průměrná diskontovaná výplata každého hráče v Nashově rovnováze alespoň jeho minmax výplata.
• x je dosažitelný profil výplat v G, pro který platí, že x; je větší než minmax výplata hráče /. Pak vždy existuje ô < 1, taková že pro každé ô > ó má nekonečně opakovaná hra Nashovu rovnováhu ve které průměrná diskontovaná výplata hráče / je
X/.
Rostislav Staněk
Opakované hry
Nashova rovnováha: Zobecnění
SPE: Zobecnění
Aplikace
Folk teorém pro Nashovu rovnováhu
S/(0) = bi
bi        pokud (a1,...a*-1) = {b,...,b)
(p-j)i    pokud (a1, ...af_1) ^ (b,/>)hráč _/ se sám odchýlil
kde (p-j)i označuje takovou strategii hráče /, která přináší hráči j minmax výplatu.
Profil těchto strategií tvoří Nashovu rovnováhu, pokud jsou hráči dostatečně trpělivý.
Rostislav Staněk
Opakované hry
Nashova rovnováha: Zobecnění
SPE: Zobecnění
Aplikace
SPE
Výše uvedená strategie nemusí být kredibilní. Netvoří proto SPE. Uvažujme následující příklad
	A	B	C
A	4,4	1,5	1,0
B	5,1	3,3	1,0
C	0,1	0,1	0,0
Rostislav Staněk
Opakované hry
Nashova rovnováha: Zobecnění
SPE: Zobecnění
Aplikace
SPE strategie
;V:flr
HZ
■ Pr-Pi —
J net p
I not f>
Figure: SPE strategie
Rostislav Staněk
Opakované hry
Nashova rovnováha: Zobecnění
SPE: Zobecnění
Aplikace
Důkaz SPE
Označme 77/ maximální výplata ve hře, u,(p) výplata při profilu akcí {pi-,pi), u-,{a) výplata při dodržení strategie
• Podhra vedoucí do stavu N.
u;(a)(l + ô + ... + ók) ^ 77/ + Ui{p){S + ... + 5k)
• Podhra vedoucí do některého ze stavů P/.
u;{p){l+ô+...+ôk-')+u;{a){ôk-l+1...+ôk) > mi+ui(p)(l+S...+Sk)
Pokud je tato podmínka splněna, pro 1 = 1, pak je jistě splněna také pro / > 1. ôk(uj(a) — u/(p)) = m-, — u-,{p)
Rostislav Staněk
Opakované hry
Nashova rovnováha: Zobecnění
SPE: Zobecnění
Aplikace
Důkaz SPE
Lze najít 5 a funkci k takové, že pro 5 > 5 a k = k(5) jsou výše uvedené podmínky splněny.
Rostislav Staněk
Opakované hry
Nashova rovnováha: Zobecnění
SPE: Zobecnění
Aplikace
Vyjednávání
Rubinstein, Ariel (1982). Perfect Equilibrium in a Bargaining Model
Hráči: 1 a 2
• Konečné historie: jakákoliv skevence typu
(x1, N, x2, N, ...,xf, V), kde xr je dvojice čísel, jejichž součet je jedna
• Hráčská funkce: P(0) = 1,
P((x\/V,x2,/V,...,xf
N)
• Preference: Výplata hráče pri konečné histórii je (x1, N, x2, N, ...,xt, Y) je S^1xf. Výplata pri nekonečné histórii je (x1, N, x2, N,...) je 0.
Rostislav Staněk
Opakované hry