1     Stručný úvod do Teorie her
Následující text přibližuje základy Teorie her pro potřeby kurzu „Matematické modely v ekonomii", který bude přednášen na podzim roku 2008 na Masarykově univerzitě. Text není v žádném případě vyčerpávající a pro získání širšího a úplnějšího přehledu je potřeba konzultovat další literaturu, převážně v anglickém jazyce. Mezi vhodné zdroje, z nichž tento text ve větší či menší míře čerpal patří například knihy Osborne and Rubinstein (1994) a Gibbons (1992) a zdroje v nich uvedené. Mezi další zajímavé knihy patří text Binmore (2007). Některé příklady jsou inspirovány příklady z knih Shy (1996) a Vega-Redondo (2003).
Teorie her se zabývá situacemi, ve kterých několik, většinou poměrně málo, hráčů volí nějakou akci a výsledek (či užitek z výsledku) závisí nejen na jejich vlastní akci, ale také na akcích ostatních hráčů. Využití teorie her tedy představuje jistý protipól k teorii dokonalé konkurence, kdy každý hráč je dostatečně malý na to, aby jeho chování ovlivnilo ostatní hráče. Teorie her je proto vhodná pro modelování situací, ve kterých je hráčů velmi málo a navzájem se silně ovlivňují.
Existují dva základní typy her. Prvním typem jsou hry v normální formě. Ty představují zcela obecný popis hry, tedy popis hráčů, jejich možných akcí a výsledků (a užitku z výsledků). Veškerá struktura hry musí být obsažena v množině strategií každého hráče. Hry v normální formě jsou vhodné pro studium obecných her a konceptů řešení. Druhý typ her, poziční hry naopak obsahují pevnou strukturu—definice poziční hry zahrnuje popis toho, kdo a kdy hraje, co může dělat a jaké jsou možné výsledky. Jejich výhodou je snadnost řešení a stručnost zápisu, jak dále uvidíme.
Cílem Teorie her není podat definitivní návod, jak hru hrát, či kdo vyhraje. Cílem je spíše pochopit, jak lidé hry hrají a jaká volba strategií lze očekávat od racionálních hráčů. Základem analýzy je předpoklad, že hráči mají jasně definovaný cíl, o který usilují. Pro zjednodušení tento cíl nazýváme „užitek" a je brán jako daný vnějšími vlivy, které se nestuduje. Je také obvykle vyžadována racionalita hráčů.1 Tento předpoklad je často terčem kritiky, i když leckdy neoprávněně. Pokud se soustředíme na hry, které hráči dobře znají (třeba proto, že je hráli v minulosti) a ve kterých jde o hodně peněz, racionalitu lze předpokládat. Je ale dobré vždy mít na paměti, že jde hry představují schématický, zestručněný popis určité situace a aplikovat je na reálné problémy je potřeba s rozmyslem.
Klíčovým pojmem Teorie her je řešení hry. Za řešení budeme považovat metodu, která nám pro danou hru řekne, jakou strategii od racionálních hráčů máme očekávat. Například slavná Nashova rovnováha je takové řešení dané hry, ve kterým žádný z hráčů nemůže zvýšit svůj užitek jednostrannou změnou své strategie.
Kromě her v normální formě a pozičních her, budeme také mluvit o opakovaných hrách. Ty slouží k popisu situací, kdy se hráči potkávají pravidelně ve stále stejných situacích. Jak uvidíme, množina řešení nekonečně opakovaných her se značně liší od řešení her hraných jednorázově.
Protože následující text je velmi stručný, je doplněn o řadu příkladů, jejichž vyřešení je užitečné a někdy i nezbytné pro plné pochopení dané látky.
1.1     Hry v normální formě
Definice 1.1.1  Hrou v normálni formě nazýváme trojči
{N, {Si}ieN, {uí : S\ x • • • SN —> R}ieAr},
kde N je konečná množina hráčů, Si je množina strategii i-tého hráče, a Ui je výherní (payoff) funkce i-tého hráče. Prvky množiny S = x^^Si nazýváme profily strategii.
Někteří autoři označují prvky množin Si akce namísto slova strategie, občas se hra v normální formě nazývá strategickou hrou. Hru lze rovněž definovat pomocí preferenčího uspořádání množiny výsledků (tj. kompletní, reflexivní a transitivní binární relace).
Definice 1.1.2 Hrou v normální formě nazýváme trojici
{N, {Si}ieN, {hi}iGN},
kde N je konečná množina hráčů, Si je množina strategií i-tého hráče, a ^ je preferenční uspořádání na množině S pro i-tého hráče.
írľo bude platit pro celý tento text, i když Teorie her již studuje i situace, kdy hráči nejsou racionální, či mají jen omezenou kapacitu pro analýzy.
1
Rozdíl mezi těmito definicemi nebude pro nás podstatný. Snadno lze ukázat, že výherní funkce definuje preferenční uspořádání (Ověřte!). Opačný směr je složitější—lze nalézt jistou analogii jako mezi definicí ordinální a kardinální užitkové funkce.
Označení 1.1.3 Pro zjednodušeni zápisu značíme
\X—i7 Xij             \^l: • • • , •£*—1, -Ei: ^ž+1, • • • , -EN)i
X-i    =   X i x • • • Xj_i x Xi+i x • • • Xn Definice 1.1.4 Hru nazýváme konečnou, pokud Si je konečná pro každé i G N.
Všimněte si, že každý hráč volí svoji strategii nezávisle na volbě ostatních. Tato definice proto nejlépe popisuje hry, kdy rozhodnutí o strategiích probíhají současně a nezávisle—bez znalosti zvolených strategií ostatních hráčů. Pro kompaktní zápis her v normální formě o dvou hráčích často využíváme tabulek, kde každý řádek přísluší strategii prvního hráče, každý sloupec strategii druhého hráče a políčka v tabulce odpovídají užitku pro hráče v případě volby odpovídajících strategií.
Je zřejmé, že takto obecnou hru nelze vyřešit. I kdyby to možné bylo, samotné řešení by nebylo příliš užitečné. Teorie her se tedy využívá k řešení konkrétních her. My zde uvedeme některé základní příklady. V dalším textu představíme metody řešení (solution concepts) na těchto příkladech. Později v kurzu budeme využívat zde představené teorie k řešení složitějších her.
Příklad 1.1.5 (Vězňovo dilema) Dva podezřelí jsou zatčeni a umístěni do odlišných vazebních cel. Jsou obviněni z vraždy a ví, že pokud se oba přiznají, tak budou odsouzeni na 10 let. Pokud se však přizná jen jeden z nich, bude mu trest zcela odpuštěn, zatímco ten druhý dostane 20 let. Protože policie nemá dost důkazů k prokázání vraždy, pokud se ani jeden z nich nepřizná, každý dostane 2 roky ve vězení za méně podstatný trestný čin (vloupání)? Zapište tuto hru do normální formy a diskutuje strategii, která vám přijde "optimální".
Řešení 1.1.6 Jdo o hru dvou hráčů N = {1, 2}, z nich každý má možnost přiznat se ("P") nebo se nepřiznat ("N").  Výherní funkci zobrazuje následující tabulka
Hráč 2
Hráč 1
	P	N
P	(-10,-10)	(0, -20)
N	(-20,0)	(-2,-2)
Příklad 1.1.7 (Souboj pohlaví (Battle of the Sexes))  Manžel a manželka chtějí strávit společný večer. Muž má raději balet, manželka raději chodí na hokej, ale nejdůležitější pro ně je strávit večer spolu. Hru lze popsat takto
Muž
Zena
	H	B
H	(2,1)	(0,0)
B	(0,0)	(1,2)
Příklad 1.1.8 (Hlava nebo Orel (Matching Pennies))  Dva hráči si tajně vyberou jednu stranu mince ("Panna" nebo "Orel"). Pak si je současně ukáží. Pokud se strany shodují, první hráč hráč dostane 1Kč od druhé hráče, v opačném případě dá první hráč 1Kč druhému hráči. Připadá vám nějaká strategie optimální bez ohledu na to, co hraje druhý hráč?
Hráč 1
Hráč 2
	p	o
P	(-1,1)	(1,-1)
o	(1,-1)	(-1,1)
Příklad 1.1.9 (Kámen, nůžky, papír)  Zapište známou dětskou hru Kámen, nůžky, papír jako hru v normální formě.
2Implicitně předpokládáme, že hráči chtějí strávit ve vězení co možná nejkratší čas.
2
Cílem TH je dát předpověď, jakou strategii by zvolili racionální hráči, zejména pokud by šlo o větší částku a s hrou by již byli dobře obeznámeni. Za takových podmínek se zdá být přirozené vyžadovat, aby žádný z hráčů nezvolil " špatnou" strategii, tj. strategii, která za každých okolností (pro všechny možné strategie ostatních hráčů) vede k pro něj horšímu výsledku než nějaká jiná strategie. Tuto intuici lze snadno formalizovat
Definice 1.1.10 Nechi i G N a si; s[ G Si jsou dvě různé strategie i—tého hráče. Strategii Sj nazýváme striktně dominovanou strategií s^, pokud
Ui(s-i,Si) < Mj(s_i;s-), Vs_j G XjeN\{i}Sj
Někdy též říkáme, že s[ striktně dominuje Sj. Nahradíme-li striktní nerovnost nerovností neostrou (<), dostáváme definici slabě dominované strategie. Je obvyklé požadovat, aby existovala alespoň jedna kombinace strategií ostatních hráčů, kdy nerovnost platí striktně.
Pokud nám tedy připadá přirozené, že žádný z hráčů nikdy nebude hrát striktně dominovanou strategii, můžeme takovou strategii odstranit. Pokud tento proces opakujeme, je možné, že se postupně dostaneme do situace, kde množina strategií každého hráče je jednoprvková.
Řešení 1.1.11 Pokud opakovaným eliminováním striktně dominovaných strategií získáme hru, ve které \Si\ = 1 pro všechna i G N, říkáme, že hra je řešitelná pomocí iterované eliminace striktně dominovaných strategií.
Poznámka 1.1.12 Při eliminaci striktně dominovaných strategií nezáleží na pořadí, se kterým volíme striktně dominované strategie. Analogicky můžeme některé hry vyřešit pomocí eliminování slabě dominovaných strategií. V takovém případě ale výsledek není jednoznačný a záleží na pořadí (Najděte příklad!).
Příklad 1.1.13 Pokuste se vyřešit předešlé příklady pomocí eliminace striktně dominovaných strategií.
Je zřejmé, že požadavek, aby strategie byla horší (než jiná strategie daného hráče) pro všechny možné strategie ostatních hráčů je velmi silný. V mnoha případ "optimální" strategie závisí na tom, jak hrají ostatní hráči (viz "Souboj pohlaví").
Definice 1.1.14 (Strategie optimální odpovědi (Best response)) Nechi s* = (s*_i7s*) G S  je profil strategií. Strategii s* nazýváme optimální odpovědí na s*_^ pokud
ui{s*-i, s*) = max Mi(s"Li; Si). Množinu všech optimálních odpovědí na s*_i značíme B(s*_i), tj.
B{s*-i) = Wi e Si : Ui(s*_i, s'i) = max u^s*^, s i)}
Pojmu optimální odpovědi použijeme k definici Nashovy rovnováhy. V rovnováze, jak již název naznačuje, žádný z hráčů nemá důvod (motivaci) svoji strategii jednostranně měnit. To nastává v případě, že každý z hráčů volí optimální odpověď na strategie ostatních hráčů.3
Definice 1.1.15 (Nashova rovnováha v čistých strategiích) Profil strategií s* G S nazýváme Nashovou rovnováha v čistých strategiích (Nash Equilibrium in pure strategies), pokud
Si G B{s*_i), VíeJV
Nashovu rovnováhu (NR) lze interpretovat několika ekvivalentními způsoby. Například můžeme mluvit o NR v situaci, kdy žádný z hráčů nemůže vylepšit svoji situaci jednostrannou změnou strategie (no profitable deviation), pro dané strategie ostatních hráčů. Podobně jako řešení metodou opakované eliminace striktně dominovaných strategií, ani Nashova rovnováha nemusí vždy existovat.4
3Terminologie je možná trošku zavádějící z jazykového hlediska. Volba strategií probíhá vždy simultánně. Proto by bylo přesnější mluvit o volbě optimální strategie v situaci, kdy daný hráč očekává, že ostatní hráči volí s*_i. Je také dobré si uvědomit, že teorie neřeší, jak je této rovnováhy dosaženo.
4 Řešení vždy existuje, pokud je množina strategií každého hráče Si neprázdná, kompaktní a konvexní podmnožina Euklidovského prostoru, a za určitých podmínek na preference.
3
Příklad 1.1.16 Nalezněte Nashovy rovnováhy her 1.1.5 až 1.1.9. Kolik jich je?
Jak jsme viděli, existují hry které nemají Nashovu rovnováhu (v čistých strategiích). Pokud připustíme, aby hráči volili náhodně mezi vybranými strategiemi, nikoliv deterministicky jako dosud, situace se změní. Tomuto postupu se říká pravděpodobností rozšíření. Každý hráč volí pravděpodobnostní rozdělení na množině svých strategií. V případě konečných her, které nás budou nejvíce zajímat, jde jednoduše o volbu pravděpodobností, se kterými bude danou strategii hrát. Součet pravděpodobností přes všechny strategie daného hráče musí dát 1.
Definice 1.1.17 Pravděpodobností rozšíření hry v normální formě {N, {S'ijieAr, {uí}í^n} je hra {N, {ASi}ieN, {Ui}ieiy}, kde ASi je množina pravděpodobnostních rozdělení nad množinou Si a Ui : ASi x • • • ASn —> R přiřazuje každému prvku množiny a G AS*! x • • • ASn očekávanou (střední) hodnotu hry
Ui(s) = Yl     IT CTJ'(sj)     Wi(s)' ■seS \jeN            J
pro konečné množiny S.
Definice 1.1.18 Nashova rovnováha hry v normální formě ve smíšených strategiích (NE in mixed strategies) je Nashova rovnováha jejího pravděpodobnostního rozšíření.
Příklad 1.1.19 Nalezněte Nashovu rovnováhu ve smíšených strategiích u předešlých příkladů, kde neexistovala Nashova rovnováha v čistých strategiích.
Příklad 1.1.20 Zjistěte, zda u her, kde existuje Nashova rovnováha v čistých strategií, existují další smíšené NR.
Příklad 1.1.21 Spočtěte všechny Nashovy rovnováhu hry Souboj pohlaví a spočítejte očekávaný užitek prvního hráče. Je vyšší v případě smíšených strategií nebo v případě čistých?
Řešení 1.1.22 Lze snadno ukázat, že existují dvě rovnováhy v čistých strategiích. Zkusme najít Nashovu rovnováhu ve smíšených strategiích. Označme p pravděpodobnost, že žena zahraje „H", q pravděpodobnost že totéž zahraje můž. Abychom byli v rovnováze, tak musí platit, že volba hodnoty p maximalizuje očekávaný užitek ženy, tedy hráče který p volí.
maxp2pq + (1 — p)(í — q)
Aby hodnota p, která tento výraz maximalizuje, ležela vevnitř intervalu [0,1], musí platit, že 'Iq = 1 — q. Pokud by tomu tak nebylo, problém by neměl vnitřní řešení a dostali bychom se zpět do čistých strategií. Podobná úvaha pro muže nám dává podmínku na hodnotu p a to tuto: p = 2(1 — p). Řešení těchto rovnic dává rovnováhu ve smíšených strategiích (|, ^), kde první číslo udává pravděpodobnost, se kterou první hráč hraje první strategii a druhé číslo tutéž pravděpodobnost pro druhého hráče.
Očekávaná hodnota výhry prvního hráče je
2pq+(l-p)(l-q) = -.
Tento příklad ukazuje dva důležité poznatky. Zaprvé, hráč, který volí určité strategie ve smíšené rovnováze s pozitivní pravděpodobností, musí být indifferentní mezi všemi těmito strategiemi. Jinými slovy, všechny strategie zvolené s pozitivní pravděpodobností mu musejí přinášet stejný užitek, větší než ty strategie, které s kladnou pravděpodobností voleny nejsou. Tohoto poznatku lze častu využít pro rychlejší výpočet rovnováhy ve smíšených strategiích.
Druhý poznatek se týká očekávané výhry v rovnováze v čistých a ve smíšených strategiích. Nejmenší možná výhra v čistých strategiích je pro daného hráče 1, ale ve smíšených to je |, tedy méně. I když se může zdát překvapivé, že rozšířením množiny strategií poklesne očekávaný užitek hráčů v rovnováze, není to nic neobvyklého. Existuje samozřejmě i řada her, ve kterých očekávaná výhra v rovnováze ve smíšených strategií je větší než v některé rovnováze v čistých strategiích.
4
1.2     Poziční Hry
Hry v normální formě jsou vhodné pro popis situací, kdy se hráči rozhodují zároveň. Jak dále uvidíme, je možné i pomocí normálních her popsat situace, kdy se hráče rozhodují postupně, ale takový popis může být komplikovaný. Pro hry s explicitní strukturou postupné volby jednotlivých hráčů je vhodné využít tzv. poziční formy her. Neformálně, poziční forma hry popisuje, jak se hra postupuje (kdy se kdo rozhoduje), jaké má možnosti a co v danou situaci ví.
1.2.1     Poziční hry s kompletní informací
Pro začátek budeme definovat poziční hry s perfektní informací, tedy hry, ve kterých každý hráč ví, jak hráli všichni hráči před ním.
Definice 1.2.1 Poziční hrou s perfektní informací (extensive game with perfect information) nazýváme 5-tici
{N, H, Z, P: H\Z ^N,{Ui:Z^ R}ieN},
kde
•   N je konečná množina hráčů,
•   H je množina posloupnosti splňujících:
—  prázdná posloupnost je jejím prvkem: 0 G H.
—  pokud daná posloupnost náleží do H:(sk)jí=il...lK & H, K G N U {oo}7 pak i každá kratší posloupnost leží v H, tj. pro všechna L < K, (sfc)fc=i,...,L G H
•   Prvky množiny H nazýváme historie, prvky historií nazýváme akce.
•   Z C H je množina těch terminálních historií (sfc)fc=i,...K G H, tedy těch posloupností z H, které jsou buď nekonečné a nebo neexistuje (sk)jí=il...lK+i & H.
•   Funkce P přiřazuje každé neterminální historii hráče, který po dané historii hraje (volí akci).
•   Ui je užitková funkce přiřazující každé terminálni historii výhru daného hráče.5
Jak dále uvidíme, jedna ze vhodných forem zápisu pozičních her jsou stromy. Kořenem stromu je rozhodnutí prvního hráče. V druhé úrovni jsou rozhodnutí, která následují jako druhá v pořadí atd.
Definice 1.2.2 Pokud je množina H konečná, mluvíme o konečné hře. Pokud jsou všechny historie z H konečné, mluvíme o hře s konečným horizontem.
Příklad 1.2.3  Zkonstruujte hru, která není konečná, ale má konečný horizont.
I zde existují alternativní definice pomocí, například pomocí stromů, vrcholů a listů atd. Pro srovnání použijte například Wikipedii (http://en.wikipedia.org/wiki/Extensive_form_game).
Definice 1.2.4 Pro každou neterminální historii h označujeme {h, a) historii, ve které h je následována akcí a a je tedy o jednotku delší. Pro každou historii h hráč P(h) volí akci z množiny
A{h) = {a: (h,a) G __"}.
Příklad 1.2.5 Hra o vstupu na trh (Market Entry Game). Existující trh je pokryt jedinou firmou, která dosahuje zisku 2. Nová firma zvažuje vstup na tento trh. Pokud se rozhodne nevstoupit, žádné náklady ani výnosy mít nebude. Pokud vstoupí, tak se existující firma rozhodne, zda se tomuto vstupu přizpůsobí (obě firmy v takovém případě dosáhnou zisku 1), nebo bude s novou firmou bojovat o trh (například prostřednictvím snížených cen, nákladnou reklamní kampaní atd.), ale pak budou obě firmy ve ztrátě.
5 Podobně jako pro hry v normální formě lze i zde použít o něco obecnější přístup a definovat preferenční uspořádání na množině terminálních vrcholů.
5
Nová firma
(-1,-1)                           (i,i)
Příklad 1.2.6 (Dělení pokladu.)   Ve známé úloze jak se dva mohou spravedlivě rozdělit o hromádku předmětů se doporučuje nechat prvního z podílníků rozdělit předměty na dvě části a druhého nechat vyhrát si jednu z hromádek. Namodelujte tento postup jako hru dvou hráčů. Pro zjednodušení můžete uvažovat, že celá hromádka má hodnotu $1 a je dokonale dělitelná. Nebo je jednodušší, pokud poklad lze dělit jen po desetinách?
Nashovu rovnováhu v pozičních hrách je možné definovat velmi podobně jako ve hrách v normální formě, jen je potřeba pečlivě definovat, co je to strategie.
Definice 1.2.7 Strategie i-tého hráče v poziční hře s perfektní informací je funkce, která každé neterminální historii h G H\Z, po které hraje hráč i, tj. P(h) = i, přiřazuje akci z množiny A{h). Strategie obvykle značíme Sj, jejich množinu Si.
Na této definici může být poněkud překvapivé to, že strategie hráče musí určovat akci v každé historii, ve které daný hráč hraje, a to i v těch historiích, které nemohou napsat kvůli volbě daného hráče. Dále je potřeba rozlišit výsledek hry (outcome) od strategického profilu hry (sí)í^m-Výsledkem hry je terminálni historie, ke které vede hra podle onoho strategického profilu.
Pomocí strategií můžeme snadno definovat strategickou formu poziční hry. Hru v normální formě definuje množina hráčů, která zůstává beze změny, množina strategií každého hráče z předchozí definice a systém výherních funkcí, který vzniká přirozeně z výherních funkcích poziční hry.
Příklad 1.2.8 V následující hře patří mezi strategie prvního hráče i strategie L, R, přestože poté, co zahrál „L" není možné, aby dostal příležitost znovu hrát.
(-3,3)             (2,2)
Totéž platí pro druhého hráče.
Definice 1.2.9 Nashovou rovnováhou poziční hry s perfektní informací je strategický profil hry (st)ieN takový, že
uÁs*-i,s*) > uÁs*-i,si), Vsi € S», Vi G N
Příklad 1.2.10 Řešení hry o vstupu na trh. Tato hra má dvě Nashovy rovnováhy. V první z nich stávající firma volí strategii (Boj) pokud nová firma vstoupí. V takovém případě je pro novou firmu výhodnější nevstupovat. V druhé Nashově rovnováze se stávající firma po (potenciálním) vstupu přizpůsobí a pro firmu zvažující vstup je tedy optimální vstoupit.
6
Předchozí příklad naznačuje, že koncept Nashovy rovnováhy není pro poziční hry vhodný. Zatímco ve hrách v normální formě probíhá volba strategií současně, poziční hry jsou typicky sekvenční, tedy rozhodnutí některých hráčů následuje až po rozhodnutí jiných. Rozhodnutí o strategii druhý hráč tvoří teprve poté, co se dozví rozhodnutí prvního hráče. I když se druhý hráč může snažit přesvědčit prvního hráče o tom, jakou volbu provede v budoucnu, racionální hráči maximalizují vlastní užitek a první hráč toho může využít k odhadu toho, jakou strategii zvolí druhý hráč. Například v předešlém příkladu není racionální volba strategie (Boj), poté co první hráč vstoupil na trh. Druhý hráč takovou volbou ztrácí užitek a protože první hráč již vstoupil, nemůže tím ani ovlivnit prvního hráče. První z Nashových rovnovách tak nedává smysl pro racionální hráče.6 Tyto úvahy lze formalizovat do přístupu tzv. zpětné indukce. Při zpětné indukci se hra řeší od konce - postupuje se od nejnižších úrovní a každý neterminální uzel se nahrazuje terminálním s takovou hodnotou, jaká odpovídá řešení této úrovně. Nejlépe tento postup popisuje příklad následující po potřebných definicích. Začít musíme s definicí podhry.
Definice 1.2.11 Podhra poziční hry F = {N, H, Z, P : H\Z —> M, {«j : Z —> R}iejv} následující po historii h je poziční hra
T{h) = {N,H\h,Z\h,P\h : H\h\Z\h -+ N,{Ui\h : Z\h -+ R}ieN},
kde H\h je množina historií b! takových, že (h,h') G H, funkce P\^ je definována předpisem P\h(h!) = P(h, h1) pro všechna b! G H\h- Množina terminálních historií Z\h je definována jako v definici poziční hry a Ui\h jsou definována pomocí Ui takto: Ui\h(h!) = Ui(h, h1).
Řešení hry pomocí zpětné indukce vyžaduje, aby akce, kterou hráč volí, byla optimální pro dané strategie protihráčů po každé historii.7 Profil strategií, které tyto požadavky splňují, jsou někdy nazývány dokonalá rovnováha vzhledem k podhrám (subgame perfect equilibrium).
Definice 1.2.12 Dokonalou rovnováhou vzhledem k podhrám (DRVP) nazýváme takový profil strategií s* hry T = {N, H, Z, P : H\Z —> M, {«j : Z —> R}jejv}7 že pro každého hráče i G N a každou neterminální historii h G H\Z takovou, že P(h) = i platí
Ui\h{s*-i\h, S*\h)  > Ui\h{s*_i\h, Si)
pro všechny strategie s j podhry T (h).
Z definice vyplývá, že každá DRVP je také Nashovou rovnováhou. Opačným směrem to samozřejmě neplatí.8
Řešení 1.2.13 (Hra o vstupu na trh)  Pokud použijeme zpětnou indukci na hru O vstupu na trh, nejprve řešíme podhru, kdy se druhý hráč (Zaběhnutá firma) rozhoduje, zda bojovat či přizpůsobit se. Evidentně, jakmile hra dosáhla tohoto bodu, je výhodnější se přizpůsobit. První hráč bere toto řešení v úvahu a hra, kterou řeší je
Nová firma Nevstupuj  /        ^\    Vstup
(0,2)                           (1,1)
V takové situaci je pro novou firmu výhodnější na trh vstoupit. DRVP je tedy („vstup", „přizpůsob se").
Řešení 1.2.14 (Dělení pokladu) Druhý hráč si vybírá mezi dvěma hromádkami. Je v jeho zájmu vybrat si tu větší (hodnotnější). První hráč toto očekává a proto je pro něj nejvýhodnější hromádku rozdělit na dvě stejné části. (Co když to nejde?).
6 Formálně je nejen potřeba, že oba hráči jsou racionální, ale že tento fakt je všeobecně znám. Tedy první hráč ví, že druhý hráč je racionální. Také druhý hráč ví, že první hráč ví, že druhý hráč je racionální atd. Úplná formalizace toho problému je poměrně složitá a jde nad rámec tohoto textu.
7V pozičních hrách s neúplnou informací uvidíme, že ne každá historie definuje podhru. V tuto chvíli ale je situace jednodušší, neboť pro každou historii můžeme definovat podhru.
8Někdy mluvíme o tzv. refinements, tedy zpřesněných Nashovy rovnováhy, které nám umožňují vybrat tu „nejrozumnější" z Nashových rovnováh. V případě DRVP jsou odstraněny ty Nashovy rovnováhy, ve kterých některý z hráčů vyhrožuje pomocí nevěrohodné hrozby (non-credible threat).
7
Definice dokonalé rovnováhy vzhledem k podhrám vyžaduje porovnání potenciálního kandidáta na rovnováhu se všemy možnými strategiemi, pro všechny hráče. Dá se ukázat, že toto srovnání lze výrazně zjednodušit. K tomu, abychom ověřili zda o rovnováhu jde (či ne), stačí ověřit, že žádný hráč si nemůže polepšit změnou jediné akce v situaci, kdy se o ní rozhoduje.
Lemma 1.2.15 Lemma o jedné odchylce. Necht ľ = {N, H, Z, P : H\Z —> M, {«j : Z —> R}j£Ar} je hra s konečným horizontem. Profil strategii s* tvoří DRVP tehdy a jen tehdy když pro každého hráče i G N a každou historii h takovou, že P (h) = i piati
Ui\h{s*-i\h, S*\h)  > Ui\h{s*_i\h, Si)
pro každou strategii Si hráče i v podhře T (h) která se Uší od s*\h jen v akci po historii h.
Věta 1.2.16 Každá konečná poziční hra s dokonalou informací má DRVP, a tedy alespoň jednu Nashovu rovnováhu.
Důkaz 1.2.17 Indukcí vzhledem k délce nejdelší historie hry .
1.2.2     Poziční hry s neúplnou informací
Definici poziční hry lze snadno přizpůsobit situaci, kdy daný hráč při volbě své akce neví, jak se rozhodl hráč před ním. Je dokonce možné definici přizpůsobit i situaci, kdy nějaký hráč zapomene, jak hrál dříve.
Formálně je tato definice založena na tzv. informačních množinách. Například pokud druhý hráč neví, jakou akci zvolil první hráč, jsou pro něj ty historie, které se liší v tahu prvního hráče nerozlišitelné. Aby nebyl schopen odvodit, jakou akci první hráč zvolil, je nutné, aby množina jeho možných akcí byla pro dané historie stejná. Pokud by druhý hráč po jedné akci prvního hráče měl na výběr 3 akce, ale po druhé akci jen 2, mohl by si snadno odvodit, jak hrál první hráč. Tyto případy musí být vyloučeny.
Definice 1.2.18 Poziční hrou (extensive-form game ) nazýváme 7-tici
{N, H,Z,f0,P: H\Z ^NU {0},IieN, {m : Z -+ R}ieN, },
kde
•   N je konečná množina hráčů, 0 je hráč „náhoda",
•   H je množina posloupností splňujících:
—  prázdná posloupnost je jejím prvkem: 0 G H.
—  pokud daná posloupnost náleží do H:(sk)jí=il...lK & H, K G N U {oo}7 pak i každá kratší posloupnost leží v H, tj. pro všechna L < K, (sfc)fc=i,...,L G H
•   Prvky množiny H nazýváme historie, prvky historií nazýváme akce.
•   Z C H je množina těch terminálních historií (sk)k=i k € H, tedy těch posloupností z H, které jsou buď nekonečné a nebo neexistuje (sk)k=i     k+i € H.
•   Funkce f0 přiřazuje každé historii h takové, že P(h) = 0 pravděpodobnostní rozděleni? Í0(-\h) na množině A{h)
•   Funkce P přiřazuje každé neterminální historii hráče, který po dané historii hraje (volí akci).
•   Pro každého hráče i G N označuje Ij = {Ij}j=il... rozdělení10 množiny {h G H : P (h) = i} takové, že A{h) = A(h') pokud hah' náleží do téže množiny rozdělení. Značíme A(Ij) množinu A{h) a P {Ii) množinu P (h) pro libovolnou historii h G ij. Rozdělení li nazýváme informační rozdělení, jeho prvky informačními množinami i-tého hráče
9Obvykle budeme uvažovat hry, kde A(h) je konečná a tak f0(a\h) udává pravděpodobnost, že náhoda zvolí akci a po historii h.
10Rozdělení je množina podmnožin dané množiny, které jsou vzájemně disjunktní a jejich sjednocení pokrývá danou množinu.
8
• Ui je užitková funkce přiřazující každé loterii terminálni historie výhru daného hráče.
Tato definice zavádí kromě pojmu informační rozdělení a informační množina také nového hráče - náhodu. Je možné bez větších obtíží dodefinovat náhodu i ve hrách bez úplné informace.
Příklad 1.2.19 Formálně definujte následující hru
(1,2)                           (2,1)                           (-1,3)                           (3,-1)
ve které přerušovanou čarou spojené uzly patří do stejné informační množiny.
Příklad 1.2.20 Nalezněte hru v normální formě odpovídající předchozí poziční hře.
Příklad 1.2.21  Je možné každou poziční hru s dokonalou informací považovat za poziční hru?
Definice 1.2.22   Cistou strategií v pozičních hrách rozumíme předpis akce a pro každou informační množinu li pro daného hráče i.
Příklad 1.2.23  Je následujícím stromem popsána poziční hra?
Předchozí příklad naznačuje, jakým způsobem je možné modelovat hry, ve kterých jeden z hráčů zapomene vlastní předešlý tah. Formálně je možné definovat hry s dokonalou pamětí (perfect recall). Na ty se budeme zaměřovat v dalším textu, není-li zmíněno jinak.
Podobně jako v pozičních hrách s dokonalou informací lze i ve hrách s nedokonalou informací definovat podhry. Jedinou dodatečnou podmínkou je, aby podhra, která obsahuje část určité informační množiny, tuto množinu obsahovala celou.
Příklad 1.2.24   Vypište všechny podhry následující hry
D                                         E--------------------------------F                                         G
Díky této definici můžeme rozšířit definici dokonalé rovnováhy vzhledem k podhrám i na poziční hry bez kompletní informace. Opět požadujeme, aby strategie rovnováhy tvořily Nashovu rovnováhu v každé podhře.
11 Protože ve hře může hrát náhoda, hra nemá obvykle jedinou terminálni historii. Je potřeba uvážit loterii, kterou náhoda způsobuje. Pro naše účely postačí, když budeme uvažovat střední (očekávanou) hodnotu výhry vycházející z výher v jednotlivých terminálních historiích.
9
Příklad 1.2.25 Nalezněte všechny DRVP následující hry:
(2,1,2)                           (0,1,0)             (0,2,0)                           (2,2,2)
Řešení 1.2.26 Hra má dvě podrhy. Hru samotnou a podhru začínající tahem druhého hráče. Stačí nalézt všechny Nashovy rovnováhy druhé podhry a pak ověřit, zda existuje strategie prvního hráče tak, že jde stále o Nashovu rovnováhu. Nashova rovnováha vlastní podhry je jediná, a to (X, C). První hráč pak volí raději A, takže DRVP je (A, X, C).
Příklad 1.2.27 Jsou šachy poziční hrou ? Jsou hrou bez kompletní informace? A poker?
Podobně jako ve hrách v normální formě je i v pozičních hrách možné definovat strategie využívající pravděpodobnosti. Není ale zřejmé, zda hráči mají náhodně volit čistou strategii a nebo náhodně a nezávisle volit akci kdykoliv jsou na tahu. Tyto dvě možnosti vedou k následujícím dvěma definicím.
Definice 1.2.28 Smíšená strategie i-tého hráče je pravděpodobnostní rozdělení na množině čistých strategií. Behaviorální strategie je souhrn nezávislých pravděpodobnostní rozdělení (ßi(Ii)), kde ßi(Ii) Je pravděpodobnostní rozdělení nad množinou -A(ij).
Analogicky k předchozím definicím, pomocí konceptu smíšených a behaviorálních strategií můžeme definovat i zde Nashovu rovnováhu. Pro hry s dokonalou pamětí jsou tyto dva koncepty ekvivalentní vzhledem k výsledkům (outcome equivalent).12
Příklad 1.2.29 Pokuste se najít řešení následující hry, které by bylo analogické dokonalé rovnováze vzhledem k podhrám, tedy vyžadovalo, aby strategie každého hráče byla optimální v každé informační množině.
(3,1)                           (0,0)             (0,2)                           (1,1)
Řešení 1.2.30 Jakmile se druhý hráč ocitne na tahu, tedy ve své informační množině, je pro něj optimální volit „L", bez ohledu na to, zda se do této informační množiny dostal—tedy zda první hráč volil „M" či „R". První hráč pak optimálně volí „L".
Příklad 1.2.31 Pokuste se podobně vyřešit následující příklad
(3,1)                           (0,2)             (0,2)                           (1,1)
12 Smíšenou strategii daného hráče definujeme jako ekvivalentní vzhledem k výsledkům behaviorální strategii, pokud pro každou kombinaci čistých strategií ostatních hráčů tyto strategie vedou ke stejnému pravděpodobnostnímu rozdělení terminálních historií.
10
Řešení 1.2.32 V této situaci již není zřejmé, zda je lepší pro druhého hráče hrát „L" nebo „R". Toto rozhodnutí záleží na tom, jak hrál první hráč. Pokud druhý hráč považuje za pravděpodobnější, že první hráč volil „M", pak je pro něj lepší zvolit „R", v opačném případě „L". Strategie prvního hráče potom může odpovídat tomu, v co druhý hráč věří. V některých situací ale tato informace nemůže být odvozena ze strategií hráčů, neboí pravděpodobnost že se hra dostane do této informační množiny může být nula. Například pokud se první hráč rozhodne hrát „L", informační množiny druhého hráče není dosaženo.
První možný přístup k řešení pozičních her s neúplnou informací je založen na slabé Bayesově rovnováze ( Weak Perfect Bayesian Equilibrium, dále jen WPBE, využívajícím tzv. očekávání (beliefs), což je množina pravděpodobnostních rozdělení, každé z nich nad historiemi náležejícími do téže informační množiny. V případě, že informační množina obsahuje jediný prvek, je očekávání triviální—každý hráč ví, kde se nachází. V předchozím příkladu je tak podstatné jediné očekávání, tedy pravděpodobnost, se kterou hráč očekává, že se vyskytuje vlevo v informační množině (po „M") nebo vpravo (po „R"). WPBE požaduje, aby očekávání byla založena na Bayesově pravidle,13 kdekoliv to je možné. Bayesovo pravidlo nelze použít tam, kde dané informační množiny není vůbec dosaženo a použití pravidla by vyžadovalo dělení 0. Tam, kde dané informační množiny není dosaženo, mohou být očekávání jakákoliv.
Příklad 1.2.33 V předchozím příkladě první hráč hraje behaviorální strategii \i = (p, q, 1 — p — q). Jaké je očekávání druhého hráče podle Bay esová pravidla?
Řešení 1.2.34 Očekávání je pravděpodobnost, že se hráč nachází v daném místě informační množiny za podmínky, že bylo dané množiny dosaženo. Je tedy zřejmé, že součet pravděpodobností daného očekávání přes každou informační množinu musí dát součet 1. Označme tedy r pravděpodobnost, se kterou hráč 2 očekává, že se nachází v levé části dané informační množiny. Podle Bayseova pravidla platí r = j^- a podobně pro pravděpodobnost, že se nachází vpravo platí í — r = ~^q. Snadno lze ověřit, že součet dává 1. Pokud je ovšem p = 1, q = 0, Bayesovo pravidlo nelze použít a hráč 2 může mít jakékoliv očekávání.
Definice 1.2.35 Behaviorálníprofil strategií (ßi(Ii)) tvoří WPBE, pokud existuje profil očekávání H* takový, že strategie každého hráče maximalizuje jeho výhru pro dané strategie ostatních hráčů a daná očekávání, a takový, že očekávání jsou odvozena pomocí Bayesova vzorce ve všech informačních množinách, kterých je dosaženo.
To, že definice neupřesňuje očekávání v informačních množinách, kterých není nikdy dosaženo způsobuje, že mohou existovat WPBE, které netvoří dokonalou rovnováhu vzhledem k podhrám, jak ukazuje následující příklad.
Příklad 1.2.36 Nalezněte všechny WPBE příklady 1.2.25
Řešení 1.2.37 Prvním příkladem WPBE je právě DRVP, jak lze snadno ověřit. Existuje ale i další WPBE. Klíčem k jeho nalezení je právě možnost volby libovolných očekávání v situaci, kdy dané informační množiny není dosaženo. Představme si, že hráč 3 věří, že se nachází vlevo své informační množiny. Pak je pro něj optimální hrát D. Pro druhého hráče je i v takovém případě optimální hrát X. Pro prvního hráče je ale optimální hrát B, protože kdyby hrál A, tak by jeho zisk byl 0, namísto 1, které mu zaručuje strategie B. V podstatě nesmyslné14 očekávání hráče 3 tak není vyvráceno, protože hra se nedostane do jeho informační množiny.
Jedním ze způsobů, jak zaručit, aby všechna očekávání byla „rozumná", je uvažovat o tzv. „dokonale smíšených" strategiích. Díky tomu se v každé informační množině dá použít Bayesovo pravidlo. Jde ale o hodně silný požadavek—každý hráč by takto musel hrát strategie, které jsou pro něj nevýhodné. Místo toho budeme uvažovat jen strategie, ke kterým se lze limitně přiblížit pomocí takovýchto strategií.
Bayesovo pravidlo je
P(A\B) = P^A^A\
kde P(X) je pravděpodobnost jevu X, P(X\Y) je podmíněná pravděpodobnost jevu X za podmínky, že nastal jev Y.
14 Nesmyslné proto, že strategie X druhého hráče je dominantní.
11
Definice 1.2.38 Kompletně smíšená strategie je behaviorální strategie, která přiřazuje každé čisté akci v každé informační množině kladnou pravděpodobnost.
Definice 1.2.39 Dvojce behaviorálních strategií a očekávání (/?, /x) je konzistentní pokud existuje posloupnost ((/3n, /xn))^=1 která konverguje k (/?, /x) a jejíž prvky jsou dokonale smíšené strategie, a očekávání jsou odvozena pomocí Bay esová vzorce.1^
Abychom mohli definovat rovnováhu, musíme nejprve definovat jak hráči porovnávají a odhadují možné výsledky.
Definice 1.2.40 Definujme funkci pravděpodobnostního rozdělení výsledku O'(/?, fj,\I) podmíněném na dosažení informační množiny I, pro danou terminálni historii h* = (a1,...,aK) jakožto pravděpodobností distribuci na terminálních historiích za podmínky, že bylo dosaženo dané informační množiny a za daných očekávání a behaviorálních strategií:
0(/3,M|/)(/l*)=M(/)(/l)nf=-L1/3P(oli...i0fc)(a1,...,afc)(afc+1),
pokud existuje podhistorie h* ležící v I, a položíme ji rovnu 0 pokud taková podhistorie neexistuje.16
Nyní konečně můžeme přistoupit k definici sekvenční racionality.
Definice 1.2.41  Dvojce (/?, /x) tvoří sekvenčně racionální rovnováhu, pokud je konzistentní a
£ooMii)(fcKW > £o( (/?_,,#, H WKW
hez                                      hez
pro každou strategii ß[ a informační množinu li G I každého hráče i G N.
Poznámka 1.2.42 Lze ukázat, že každá konečná poziční hra má alespoň jednu sekvenčně racionální rovnováhu.
Příklad 1.2.43 Nalezněte sekvenčně racionální rovnováhy v příkladu 1.2.31.
y v násle ■(1,1,1)
Příklad 1.2.44 Nalezněte sekvenčně racionální rovnováhy v následujícím příkladu
1                                         C                                    2
(3,3,2)                           (0,0,0)             (4,4,0)                           (0,0,1)
Řešení 1.2.45 Pro srovnání nejprve nalezneme Nashovy rovnováhy. Hraje-li třetí hráč L a druhý hráč c s dostatečně vysokou pravděpodobností (alespoň ^), pak první hráč preferuje hrát D. Protože se druhý hráč nedostane na tah, jde o Nashovu rovnováhu.17. Druhá skupina Nashových rovnováh je ta, kdy třetí hráč hraje R s velkou pravděpodobností (alespoň ^) a druhý hráč pak optimálně hraje c a první C. V rovnováze třetí hráč nehraje—jeho strategie, tedy jak by hrál, kdyby se na tah dostal, je ale podstatná pro to, jak hrají ostatní dva hráči.
První sada Nashových rovnováh netvoří sekvenčně racionální rovnováhy, protože strategie druhého hráče není optimální. Za podmínky dosažení jeho informační množiny by pro něj bylo optimální
15Konvergenci je nutnou definovat v příslušném Euklidovském prostoru, ale formální definici nebudeme dále potřebovat, proto ji vynecháváme. Bayesovo pravidlo je
P(B\A)P(A)
P{A\B) =
P(B)
kde P(X) je pravděpodobnost jevu X, P(X\Y) je podmíněná pravděpodobnost jevu X za podmínky, že nastal jev Y.
16Pokud informační množina / obsahuje jen počáteční historii, tak 0(ß, ß\I) definujeme jako pravděpodobností rozdělení nad terminálními historiemi vzniklé tím, když každý hráč hraje svoji behaviorální strategii.
17Všimněte si, že uvažujeme behaviorální strategie, a tedy jich existuje celá řada—pro všechny hodnoty pravděpodobností hry akce c mezi 3 a 1.
12
hrát d, nikoliv c. Druhá skupina NR tvoří sekvenčně racionální rovnováhy, pokud očekávání třetího hráče jsou taková, že se nachází v levé části (odpovídající historii D) s pravděpodobností g. Ověřit konsistenci lze pomocí posloupnosti kompletně smíšených strategií—stačí přiřadit strategii D prvního hráče pravděpodobnost e, strategii d druhého hráče pravděpodobnost dvakrát větší. Strategie třetího hráče je smíšená až na případ, kdy hraje R s pravděpodobností 1, pak stačí uvážit dokonale smíšenou strategii s pravděpodobnostmi e, 1 — e). Všechny tyto strategie konvergují k požadované rovnováze, jsou dokonale smíšené a racionalitu očekávání třetího hráče lze snadno ověřit.
Příklad 1.2.46 Nalezněte sekvenčně racionální rovnováhy v příkladu 1.2.31.
1.3    Opakované hry
V situaci, kdy hráči opakovaně hrají tutéž hru, není předchozí teorie příliš praktická. Množina strategií či historií může být velmi snadno nekonečná (i nespočetná). Pokud jde ale o nekonečné opakování téže hry, problém lze poměrně značně zjednodušit.
Pro zjednodušení se nebudeme zabývat hrami, které se opakují konečněkrát. I když je zřejmé, že většina opakovaných her je nutně konečná, toto není nutně na překážku. Cílem teorie je popis her, kdy hráči hry vnímají jako nekonečné, tedy neuvažují o jejich konci a předpokládají, že budou hrát dále v dohledné budoucnosti.
Výsledky teorie závisejí na tom, jakým způsobem hráči uvažují o budoucnosti, tedy jak porovnávají hodnotu výhry zítra s výhrou dnes. V literatuře lze nalézt několik různých metod, které se navíc lehce liší ve svých důsledcích. My se budeme zabývat jen tou nejčastěji používanou a v podstatě nejjednodušší—(exponenciální) diskontovaní.
Při exponenciálním diskontovaní je příjem v následujícím období vážen diskontním faktorem 5 G (0,1). Pro posloupnost strategických profilů a = (a*) a okamžitou užitkovou funkci «j jednoho hráče můžeme definovat užitkovou funkci Ui pro posloupnost akčních profilů.18
oo
Ui(a) = Y,Ui{at)5t t=í
Budeme předpokládat, že tato suma vždy existuje a je konečná, což je triviální požadavek pokud m i je ohraničená.
Definice 1.3.1 Nechí G = {N, {S\}, {uí}} je hra v normální formě, S = XiS\. Hrou s nekonečným počtem opakování nazýváme poziční hru s dokonalou informací O' = {N, H, P, {Ui}}, kde
•   H = U™0St,S° = {0}
•   P(h) = N pro každou neterminální historii h G H
•   Ui jsou definovány pomocí exponenciální diskontovaní Historii nazýváme terminálni, tehdy a jen tehdy, je-li nekonečná.
Po každé neterminální historii volí každý hráč i G N akci z Si. Strategii hráče tedy tvoří předpis akce z Si pro každou konečnou posloupnost výsledků hry G.
Na rozdíl od konečných strategických her, kde Nashových rovnováh bylo relativně málo, nebo dokonce neexistovala žádná, problémem nekonečných her je velké množství rovnováh. Ukážeme, že každá posloupnost strategický profilů, která každému hráči zaručuje více než jistý minimální příjem (minimax payoff), je limitně blízký nějaké Nashově rovnováze opakované hry.
Je intuitivní očekávat, že v Nashově rovnováze nemůže žádný z hráčů dosáhnout menšího užitku, než k jakému ho mohou donutit ostatní hráči. Tuto hodnotu označujeme za minmax výhru a formálně ji definujeme takto:
Ví = mins_ies-i'maxSiesiUi{s-i,Si)
18Zatímco Ui je užitková funkce přiřazující reálné číslo jedinému strategickému profilu, funkce Ui přiřazuje reálné číslo nekonečné posloupnosti strategických profilů. Jinými slovi, v,i je okamžitý užitek v jednom opakování hry, Ui je užitek za všechna opakování.
13
Budeme značit p_j G S-i nebo též p-i(si) řešení tohoto minimalizačního problému. Pro každé s_i navíc značíme 5j(s_j) nejlepší odpověď na s_j.
Výherní profil w ve hře G" je vynutitelný (enforceable), pokud Wi > vi pro všechna i e N. Pokud Wi > Vi, mluvíme o striktní vynutitelnosti.19
Následující dvě věty ukazují, že každý striktně vynutitelný profil lze (přibližně) podpořit Na-shovou rovnováhou a že každá Nashova rovnováha definuje vynutitelný profil.
Věta 1.3.2 Pro libovolný diskontní faktor S G (0,1) a libovolnou hru s nekonečným počtem opakováni G1 = {N, H, P, {ty} platí, že každý výherní profil odpovídající libovolné Nashově rovnováze této nekonečné hry je vynutitelný.
Věta 1.3.3 Pro každý striktně vynutitelný výherní profil w hry O' a každé e > 0 existuje S G (0, 1) a výherní profil w' hry O' takový, že \w' — w\ < e a existuje Nashova rovnováha, pro níž je w' výherním profilem hry O' s nekonečným počtem opakování a diskontním faktorem ö.
Důkaz první věty je triviální a lze jej provést sporem. Pokud by totiž Nashova rovnováha vedla na nevynutitelný výherní profil, pak alespoň jeden hráč by vydělával méně než minmax výhru. Což ale znamená, že by pro něj existovalo jednostranné vylepšení a tedy by nemohlo jít o Nashovu rovnováhu.
Druhá věta využívá tzv. trigger strategií. To jsou strategie, ve kterých jakožto reakce na odchýlení od rovnováhy určitým hráčem je ostatními hráči zvolena strategie snižující výhru odchylujícího se hráče (jde o potrestání). Výše trestu závisí na vzdálenosti výhry v rovnovážné strategii a minmax výhře, ale také na diskontním faktoru. Čím vyšší je 6, tím větší váhu má budoucnost a tedy i možný trest a tím snáze se zabraňuje hráčům v odchýlení se od rovnovážné strategie.
Podobně jako u pozičních her, i zde tyto hrozby nemusejí být věrohodné, pokud by jejich realizováním ostatní hráči poškozovali sami sebe. Pokud bychom vyžadovali, aby strategie byly optimální i ve všech podhrách, získáme tím analogickou definici dokonalé rovnováhy vzhledem k podhrám (DRVP). Předchozí věta pak platí v následující podobě:
Věta 1.3.4 Nechi s* je striktně vynutitelný strategický profil, tedy takový profil strategií, kterému odpovídá striktně vynutitelný výherní profil w. Předpokládejme, že existuje N striktně vynutitelných strategických profilů (a(i))j£jv takových, že s* >~i a(i) a a(j) >~i a(i) pro všechna j G N {i}. Pak existuje dolní hranice na diskontní parametr S takový, že pro všechna S > ö existuje dokonalá rovnováha vzhledem k podhrám hry O' s nekonečným počtem opakování diskontované pomocí ö, která generuje výsledek (s*), takový, že s* = s*,Ví.
Příklad 1.3.5   Uvažte následující hru v normální formě
Země 2
	Válka	Mír
Válka	(1,1)	(3,0)
Mír	(0,3)	(2,2)
V této hře jde o dvě země, které spolu mohou válčit. Pokud obě válčí, každá získá užitek 1. Pokud jedna hraje agresivně (Válka) a druhá mírově (Mír), tak agresor získá ústupek a užitek 3, druhá strana získá 0. Pokud jsou obě země v míru, tak každá získá 2.
Ukažte, že (Mír,Mír) není Nashova rovnováha hry v normální formě. Nalezněte trigger strategii v hře s nekonečným opakováním, která umožňuje, aby se ((Mír,Mír)) stal Nashovou rovnováhou této opakované hry. Pro jaký diskontní faktor je to možné?
Řešení 1.3.6 V této hře (bez opakování) profil strategií (Mír,Mír) není Nashovou rovnováhou, neboí obě země mají možnost vylepšit svůj užitek tím, že jednostranně přejdou do Války. Uvažme následující strategii ve hře s nekonečným počtem opakování. Každý hráč hraje Mír, pokud ve všech předchozích kolech protihráč zahrál Mír. V opačném případě hraje Válka. V prvním kole hrají oba hráči Mír.
Je zřejmé, že pokud oba hráči hrají podle této strategie, tak výsledkem je neustále (Mír,Mír). Je tedy jen nutné ověřit, že žádný z hráčů si nemůže polepšit jednostrannou změnou strategie. Protože hra je symetrická, můžeme uvažovat jen Zemi 1. Dále je snadné si uvědomit, že pokud je někdy pro Zemi 1 výhodné se odchýlit od dané strategie, pak je to výhodné udělat hned v prvním kole.
19Proč tento název bude zřejmé za chvíli. Někdy se též používá označení inidividuálně racionální.
14
Pokud se tedy Země 1 odchýlí v prvním kole a zahraje Válka, pak druhý hráč hrající podle své strategie hraje Válka od druhého kola až do konce hry. Pak je tedy i pro prvního hráče optimální hrát Válka od druhého kola dále. Musíme nyní spočítat celkové užitky hráčů při hře podle původní a této strategie a zjistit, který je větší, v závislosti na diskontním faktoru 6.
Při původní strategii je užitek součtem následující nekonečné řadu
oo                            _.
U^ö)    =    ]T2<f = 2 —
-     S u '                   ^                 1-6       1-6
i=l
Porovnáním obou výrazů dostaneme, že uvedená trigger strategie je Nashovou rovnováhou, pokud
1          3-2(5
2—6>Y^6-A to nastává tehdy a jen tehdy, pokud 6 > ^.
Následující věta značně zjednodušuje hledání DRVP, protože místo porovnání se všemi možnými alternativními strategiemi stačí zkontrolovat, že neexistuje odchylka v jediné periodě, pro každého z hráčů.20
Věta 1.3.7 Profil strategií tvoří DRVP hry s nekonečným počtem opakování hry G tehdy a jen tehdy, kdy neexistuje odchylka v jediné periodě pro některého z hráčů.
Příklad 1.3.8   Ověřte, že strategie „Oko za oko"21 tvoří Nashovu rovnováhu pro stejné hodnoty 6.
Příklad 1.3.9  Spočítejte, pro jaké diskontní faktory je ve  Vězňově dilematu možné docílit spolupráce, tedy opakovaně (N,N).
Řešení 1.3.10 Podobně jako v předchozím řešeném příkladu stačí spočítat, zda jednorázová změna strategie vede k lepšímu výsledku
oo                                 1
U^ö)    =    -]T2(f; = -2—
1-6
i=0
OO                                               £
uí(s)    =    0-^10(f = -10
1-6 Porovnáním získáme podmínku pro Nashovu rovnováhu 6 > ^.
Reference
BlNMORE, K. (2007): Playing for real: a text on game theory. Oxford University Press.
Gibbons, R. (1992): A primer in Game Theory. Pearson Education Limited.
Osborne, M. J., and A. Rubinstein (1994): A course in Game Theory. MIT PRESS.
Shy, O. (1996): Industrial Organization. The MIT Press.
Vega-Redondo, F. (2003): Economics and the Theory of Games. Cambridge University Press.
20Dále lze například ukázat, že množina možných výher v DRVP je uzavřená.
21Strategie „Oko za oko" je definována takto. Daný hráč hraje v prvním kole Mír a pak hraje to, co v předchozím kole hrál druhý hráč.
15