1 Stručný úvod do Teorie her

1

Struˇ cn´ yu ´ vod do Teorie her

N´ asleduj´ıc´ı text pˇribliˇzuje z´ aklady Teorie her pro potˇreby kurzu Matematick´e modely v ekonomii“, ” kter´ y bude pˇredn´ aˇsen na podzim roku 2008 na Masarykovˇe univerzitˇe. Text nen´ı v ˇz´adn´em pˇr´ıpadˇe vyˇcerp´ avaj´ıc´ı a pro z´ısk´ an´ı ˇsirˇs´ıho a u ´plnˇejˇs´ıho pˇrehledu je potˇreba konzultovat dalˇs´ı literaturu, pˇrev´ aˇznˇe v anglick´em jazyce. Mezi vhodn´e zdroje, z nichˇz tento text ve vˇetˇs´ı ˇci menˇs´ı m´ıˇre ˇcerpal patˇr´ı napˇr´ıklad knihy Osborne and Rubinstein (1994) a Gibbons (1992) a zdroje v nich uveden´e. Mezi dalˇs´ı zaj´ımav´e knihy patˇr´ı text Binmore (2007). Nˇekter´e pˇr´ıklady jsou inspirov´any pˇr´ıklady z knih Shy (1996) a Vega-Redondo (2003). Teorie her se zab´ yv´ a situacemi, ve kter´ ych nˇekolik, vˇetˇsinou pomˇernˇe m´alo, hr´aˇc˚ u vol´ı nˇejakou akci a v´ ysledek (ˇci uˇzitek z v´ ysledku) z´ avis´ı nejen na jejich vlastn´ı akci, ale tak´e na akc´ıch ostatn´ıch hr´ aˇc˚ u. Vyuˇzit´ı teorie her tedy pˇredstavuje jist´ y protip´ol k teorii dokonal´e konkurence, kdy kaˇzd´ y hr´ aˇc je dostateˇcnˇe mal´ y na to, aby jeho chov´an´ı ovlivnilo ostatn´ı hr´aˇce. Teorie her je proto vhodn´a pro modelov´ an´ı situac´ı, ve kter´ ych je hr´aˇc˚ u velmi m´alo a navz´ajem se silnˇe ovlivˇ nuj´ı. Existuj´ı dva z´ akladn´ı typy her. Prvn´ım typem jsou hry v norm´aln´ı formˇe. Ty pˇredstavuj´ı zcela obecn´ y popis hry, tedy popis hr´ aˇc˚ u, jejich moˇzn´ ych akc´ı a v´ ysledk˚ u (a uˇzitku z v´ ysledk˚ u). Veˇsker´a struktura hry mus´ı b´ yt obsaˇzena v mnoˇzinˇe strategi´ı kaˇzd´eho hr´aˇce. Hry v norm´aln´ı formˇe jsou vhodn´e pro studium obecn´ ych her a koncept˚ u ˇreˇsen´ı. Druh´ y typ her, poziˇcn´ı hry naopak obsahuj´ı pevnou strukturu—definice poziˇcn´ı hry zahrnuje popis toho, kdo a kdy hraje, co m˚ uˇze dˇelat a jak´e jsou moˇzn´e v´ ysledky. Jejich v´ yhodou je snadnost ˇreˇsen´ı a struˇcnost z´apisu, jak d´ale uvid´ıme. C´ılem Teorie her nen´ı podat definitivn´ı n´avod, jak hru hr´at, ˇci kdo vyhraje. C´ılem je sp´ıˇse pochopit, jak lid´e hry hraj´ı a jak´ a volba strategi´ı lze oˇcek´avat od racion´aln´ıch hr´aˇc˚ u. Z´akladem anal´ yzy je pˇredpoklad, ˇze hr´ aˇci maj´ı jasnˇe definovan´ y c´ıl, o kter´ y usiluj´ı. Pro zjednoduˇsen´ı tento c´ıl naz´ yv´ ame uˇzitek“ a je br´ an jako dan´ y vnˇejˇs´ımi vlivy, kter´e se nestuduje. Je tak´e obvykle ” vyˇzadov´ ana racionalita hr´ aˇc˚ u.1 Tento pˇredpoklad je ˇcasto terˇcem kritiky, i kdyˇz leckdy neopr´avnˇenˇe. Pokud se soustˇred´ıme na hry, kter´e hr´aˇci dobˇre znaj´ı (tˇreba proto, ˇze je hr´ali v minulosti) a ve kter´ ych jde o hodnˇe penˇez, racionalitu lze pˇredpokl´adat. Je ale dobr´e vˇzdy m´ıt na pamˇeti, ˇze jde hry pˇredstavuj´ı sch´ematick´ y, zestruˇcnˇen´ y popis urˇcit´e situace a aplikovat je na re´aln´e probl´emy je potˇreba s rozmyslem. Kl´ıˇcov´ ym pojmem Teorie her je ˇreˇsen´ı hry. Za ˇreˇsen´ı budeme povaˇzovat metodu, kter´a n´am pro danou hru ˇrekne, jakou strategii od racion´aln´ıch hr´aˇc˚ u m´ame oˇcek´avat. Napˇr´ıklad slavn´a Nashova rovnov´ aha je takov´e ˇreˇsen´ı dan´e hry, ve kter´ ym ˇz´adn´ y z hr´aˇc˚ u nem˚ uˇze zv´ yˇsit sv˚ uj uˇzitek jednostrannou zmˇenou sv´e strategie. Kromˇe her v norm´ aln´ı formˇe a poziˇcn´ıch her, budeme tak´e mluvit o opakovan´ ych hr´ach. Ty slouˇz´ı k popisu situac´ı, kdy se hr´ aˇci potk´avaj´ı pravidelnˇe ve st´ale stejn´ ych situac´ıch. Jak uvid´ıme, mnoˇzina ˇreˇsen´ı nekoneˇcnˇe opakovan´ ych her se znaˇcnˇe liˇs´ı od ˇreˇsen´ı her hran´ ych jednor´azovˇe. Protoˇze n´ asleduj´ıc´ı text je velmi struˇcn´ y, je doplnˇen o ˇradu pˇr´ıklad˚ u, jejichˇz vyˇreˇsen´ı je uˇziteˇcn´e a nˇekdy i nezbytn´e pro pln´e pochopen´ı dan´e l´atky.

1.1

Hry v norm´ aln´ı formˇ e

Definice 1.1.1 Hrou v norm´ aln´ı formˇe naz´yv´ ame trojci {N, {Si }i∈N , {ui : S1 × · · · SN −→ R}i∈N }, kde N je koneˇcn´ a mnoˇzina hr´ aˇc˚ u, Si je mnoˇzina strategi´ı i-t´eho hr´ aˇce, a ui je v´yhern´ı (payoff ) funkce i-t´eho hr´ aˇce. Prvky mnoˇziny S = ×i∈N Si naz´yv´ ame profily strategi´ı. Nˇekteˇr´ı autoˇri oznaˇcuj´ı prvky mnoˇzin Si akce nam´ısto slova strategie, obˇcas se hra v norm´aln´ı formˇe naz´ yv´ a strategickou hrou. Hru lze rovnˇeˇz definovat pomoc´ı preferenˇc´ıho uspoˇr´ad´an´ı mnoˇziny v´ ysledk˚ u (tj. kompletn´ı, reflexivn´ı a transitivn´ı bin´arn´ı relace). Definice 1.1.2 Hrou v norm´ aln´ı formˇe naz´yv´ ame trojici {N, {Si }i∈N , {i }i∈N }, kde N je koneˇcn´ a mnoˇzina hr´ aˇc˚ u, Si je mnoˇzina strategi´ı i-t´eho hr´ aˇce, a i je preferenˇcn´ı uspoˇr´ ad´ an´ı na mnoˇzinˇe S pro i-t´eho hr´ aˇce. 1 To bude platit pro cel´ y tento text, i kdyˇ z Teorie her jiˇ z studuje i situace, kdy hr´ aˇ ci nejsou racion´ aln´ı, ˇ ci maj´ı jen omezenou kapacitu pro anal´ yzy.

1

Rozd´ıl mezi tˇemito definicemi nebude pro n´as podstatn´ y. Snadno lze uk´azat, ˇze v´ yhern´ı funkce definuje preferenˇcn´ı uspoˇr´ ad´ an´ı (Ovˇeˇrte!). Opaˇcn´ y smˇer je sloˇzitˇejˇs´ı—lze nal´ezt jistou analogii jako mezi definic´ı ordin´ aln´ı a kardin´ aln´ı uˇzitkov´e funkce. Oznaˇ cen´ı 1.1.3 Pro zjednoduˇsen´ı z´ apisu znaˇc´ıme (x−i , xi ) X−i

=

(x1 , . . . , xi−1 , xi , xi+1 , . . . , xN ),

= X1 × · · · Xi−1 × Xi+1 × · · · XN

Definice 1.1.4 Hru naz´yv´ ame koneˇcnou, pokud Si je koneˇcn´ a pro kaˇzd´e i ∈ N. Vˇsimnˇete si, ˇze kaˇzd´ y hr´ aˇc vol´ı svoji strategii nez´avisle na volbˇe ostatn´ıch. Tato definice proto nejl´epe popisuje hry, kdy rozhodnut´ı o strategi´ıch prob´ıhaj´ı souˇcasnˇe a nez´avisle—bez znalosti zvolen´ ych strategi´ı ostatn´ıch hr´ aˇc˚ u. Pro kompaktn´ı z´apis her v norm´aln´ı formˇe o dvou hr´aˇc´ıch ˇcasto vyuˇz´ıv´ ame tabulek, kde kaˇzd´ y ˇra´dek pˇr´ısluˇs´ı strategii prvn´ıho hr´aˇce, kaˇzd´ y sloupec strategii druh´eho hr´ aˇce a pol´ıˇcka v tabulce odpov´ıdaj´ı uˇzitku pro hr´aˇce v pˇr´ıpadˇe volby odpov´ıdaj´ıc´ıch strategi´ı. Je zˇrejm´e, ˇze takto obecnou hru nelze vyˇreˇsit. I kdyby to moˇzn´e bylo, samotn´e ˇreˇsen´ı by nebylo pˇr´ıliˇs uˇziteˇcn´e. Teorie her se tedy vyuˇz´ıv´a k ˇreˇsen´ı konkretn´ıch her. My zde uvedeme nˇekter´e z´ akladn´ı pˇr´ıklady. V dalˇs´ım textu pˇredstav´ıme metody ˇreˇsen´ı (solution concepts) na tˇechto pˇr´ıkladech. Pozdˇeji v kurzu budeme vyuˇz´ıvat zde pˇredstaven´e teorie k ˇreˇsen´ı sloˇzitˇejˇs´ıch her. Pˇ r´ıklad 1.1.5 (Vˇ ezˇ novo dilema) Dva podezˇrel´ı jsou zatˇcen´ı a um´ıstˇeni do odliˇsn´ych vazebn´ıch cel. Jsou obvinˇeni z vraˇzdy a v´ı, ˇze pokud se oba pˇriznaj´ı, tak budou odsouzeni na 10 let. Pokud se vˇsak pˇrizn´ a jen jeden z nich, bude mu trest zcela odpuˇstˇen, zat´ımco ten druh´y dostane 20 let. Protoˇze policie nem´ a dost d˚ ukaz˚ u k prok´ az´ an´ı vraˇzdy, pokud se ani jeden z nich nepˇrizn´ a, kaˇzd´y dostane 2 roky ve vˇezen´ı za m´enˇe podstatn´y trestn´y ˇcin (vloup´ an´ı).2 Zapiˇstˇe tuto hru do norm´ aln´ı formy a diskutuje strategii, kter´ a v´ am pˇrijde ”optim´ aln´ı”. ˇ sen´ı 1.1.6 Jdo o hru dvou hr´ Reˇ aˇc˚ u N = {1, 2}, z nich kaˇzd´y m´ a moˇznost pˇriznat se (”P”) nebo se nepˇriznat (”N”). V´yhern´ı funkci zobrazuje n´ asleduj´ıc´ı tabulka

Hr´ aˇc 1

P N

Hr´aˇc 2 P (−10, −10) (−20, 0)

N (0, −20) (−2, −2)

Pˇ r´ıklad 1.1.7 (Souboj pohlav´ı (Battle of the Sexes)) Manˇzel a manˇzelka chtˇej´ı str´ avit spoleˇcn´y veˇcer. Muˇz m´ a radˇeji balet, manˇzelka radˇeji chod´ı na hokej, ale nejd˚ uleˇzitˇejˇs´ı pro nˇe je str´ avit veˇcer spolu. Hru lze popsat takto

ˇ Zena

H B

Muˇz H (2, 1) (0, 0)

B . (0, 0) (1, 2)

Pˇ r´ıklad 1.1.8 (Hlava nebo Orel (Matching Pennies)) Dva hr´ aˇci si tajnˇe vyberou jednu stranu mince (”Panna” nebo ”Orel”). Pak si je souˇcasnˇe uk´ aˇz´ı. Pokud se strany shoduj´ı, prvn´ı hr´ aˇc hr´ aˇc dostane 1Kˇc od druh´e hr´ aˇce, v opaˇcn´em pˇr´ıpadˇe d´ a prvn´ı hr´ aˇc 1Kˇc druh´emu hr´ aˇci. Pˇripad´ a v´ am nˇejak´ a strategie optim´ aln´ı bez ohledu na to, co hraje druh´y hr´ aˇc?

Hr´ aˇc 1

P O

Hr´aˇc 2 P (−1, 1) (1, −1)

O (1, −1) (−1, 1)

Pˇ r´ıklad 1.1.9 (K´ amen, n˚ uˇ zky, pap´ır) Zapiˇste zn´ amou dˇetskou hru K´ amen, n˚ uˇzky, pap´ır jako hru v norm´ aln´ı formˇe. 2 Implicitnˇ e

pˇredpokl´ ad´ ame, ˇ ze hr´ aˇ ci chtˇ ej´ı str´ avit ve vˇ ezen´ı co moˇ zn´ a nejkratˇs´ı ˇ cas.

2

C´ılem TH je d´ at pˇredpovˇed’, jakou strategii by zvolili racion´aln´ı hr´aˇci, zejm´ena pokud by ˇslo o vˇetˇs´ı ˇca´stku a s hrou by jiˇz byli dobˇre obezn´ameni. Za takov´ ych podm´ınek se zd´a b´ yt pˇrirozen´e vyˇzadovat, aby ˇz´ adn´ y z hr´ aˇcu nezvolil ”ˇspatnou”strategii, tj. strategii, kter´a za kaˇzd´ ych okolnost´ı (pro vˇsechny moˇzn´e strategie ostatn´ıch hr´aˇc˚ u) vede k pro nˇej horˇs´ımu v´ ysledku neˇz nˇejak´a jin´a strategie. Tuto intuici lze snadno formalizovat Definice 1.1.10 Necht’ i ∈ N a si , s0i ∈ Si jsou dvˇe r˚ uzn´e strategie i−t´eho hr´ aˇce. Strategii si naz´yv´ ame striktnˇe dominovanou strategi´ı s0i , pokud ui (s−i , si ) < ui (s−i , s0i ), ∀s−i ∈ ×j∈N \{i} Sj Nˇekdy t´eˇz ˇr´ık´ ame, ˇze s0i striktnˇe dominuje si . Nahrad´ıme-li striktn´ı nerovnost nerovnost´ı neostrou (≤), dost´ av´ ame definici slabˇe dominovan´e strategie. Je obvykl´e poˇzadovat, aby existovala alespoˇ n jedna kombinace strategi´ı ostatn´ıch hr´ aˇc˚ u, kdy nerovnost plat´ı striktnˇe. Pokud n´ am tedy pˇripad´ a pˇrirozen´e, ˇze ˇz´adn´ y z hr´aˇc˚ u nikdy nebude hr´at striktnˇe dominovanou strategii, m˚ uˇzeme takovou strategii odstranit. Pokud tento proces opakujeme, je moˇzn´e, ˇze se postupnˇe dostaneme do situace, kde mnoˇzina strategi´ı kaˇzd´eho hr´aˇce je jednoprvkov´a. ˇ sen´ı 1.1.11 Pokud opakovan´ym eliminov´ Reˇ an´ım striktnˇe dominovan´ych strategi´ı z´ısk´ ame hru, ve kter´e |Si | = 1 pro vˇsechna i ∈ N , ˇr´ık´ ame, ˇze hra je ˇreˇsiteln´ a pomoc´ı iterovan´e eliminace striktnˇe dominovan´ych strategi´ı. Pozn´ amka 1.1.12 Pˇri eliminaci striktnˇe dominovan´ych strategi´ı nez´ aleˇz´ı na poˇrad´ı, se kter´ym vol´ıme striktnˇe dominovan´e strategie. Analogicky m˚ uˇzeme nˇekter´e hry vyˇreˇsit pomoc´ı eliminov´ an´ı slabˇe dominovan´ych strategi´ı. V takov´em pˇr´ıpadˇe ale v´ysledek nen´ı jednoznaˇcn´y a z´ aleˇz´ı na poˇrad´ı (Najdˇete pˇr´ıklad!). Pˇ r´ıklad 1.1.13 Pokuste se vyˇreˇsit pˇredeˇsl´e pˇr´ıklady pomoc´ı eliminace striktnˇe dominovan´ych strategi´ı. Je zˇrejm´e, ˇze poˇzadavek, aby strategie byla horˇs´ı (neˇz jin´a strategie dan´eho hr´aˇce) pro vˇsechny moˇzn´e strategie ostatn´ıch hr´ aˇc˚ u je velmi siln´ y. V mnoha pˇr´ıpad ”optim´aln´ı” strategie z´avis´ı na tom, jak hraj´ı ostatn´ı hr´ aˇci (viz ”Souboj pohlav´ı”). Definice 1.1.14 (Strategie optim´ aln´ı odpovˇ edi (Best response)) Necht’ s∗ = (s∗−i , s∗i ) ∈ ∗ ame optim´aln´ı odpovˇed´ı na s∗−i , pokud S je profil strategi´ı. Strategii si naz´yv´ ui (s∗−i , s∗i ) = max ui (s∗−i , si ). si ∈Si

Mnoˇzinu vˇsech optim´ aln´ıch odpovˇed´ı na s∗−i znaˇc´ıme B(s∗−i ) , tj. B(s∗−i ) = {s0i ∈ Si : ui (s∗−i , s0i ) = max ui (s∗−i , si )} si ∈Si

Pojmu optim´ aln´ı odpovˇedi pouˇzijeme k definici Nashovy rovnov´ahy. V rovnov´aze, jak jiˇz n´azev naznaˇcuje, ˇz´ adn´ y z hr´ aˇc˚ u nem´ a d˚ uvod (motivaci) svoji strategii jednostrannˇe mˇenit. To nast´av´a v pˇr´ıpadˇe, ˇze kaˇzd´ y z hr´ aˇc˚ u vol´ı optim´aln´ı odpovˇed’ na strategie ostatn´ıch hr´aˇc˚ u.3 Definice 1.1.15 (Nashova rovnov´ aha v ˇ cist´ ych strategi´ıch) Profil strategi´ı s∗ ∈ S naz´yv´ ame Nashovou rovnov´ aha v ˇcist´ych strategi´ıch (Nash Equilibrium in pure strategies), pokud si ∈ B(s∗−i ), ∀i ∈ N Nashovu rovnov´ ahu (NR) lze interpretovat nˇekolika ekvivalentn´ımi zp˚ usoby. Napˇr´ıklad m˚ uˇzeme mluvit o NR v situaci, kdy ˇz´ adn´ y z hr´aˇc˚ u nem˚ uˇze vylepˇsit svoji situaci jednostrannou zmˇenou strategie (no profitable deviation), pro dan´e strategie ostatn´ıch hr´aˇc˚ u. Podobnˇe jako ˇreˇsen´ı metodou opakovan´e eliminace striktnˇe dominovan´ ych strategi´ı, ani Nashova rovnov´aha nemus´ı vˇzdy existovat.4 3 Terminologie je moˇ zn´ a troˇsku zav´ adˇ ej´ıc´ı z jazykov´ eho hlediska. Volba strategi´ı prob´ıh´ a vˇ zdy simult´ annˇ e. Proto by bylo pˇresnˇ ejˇs´ı mluvit o volbˇ e optim´ aln´ı strategie v situaci, kdy dan´ y hr´ aˇ c oˇ cek´ av´ a, ˇ ze ostatn´ı hr´ aˇ ci vol´ı s∗−i . Je tak´ e dobr´ e si uvˇ edomit, ˇ ze teorie neˇreˇs´ı, jak je t´ eto rovnov´ ahy dosaˇ zeno. 4 Reˇ ˇ sen´ı vˇ zdy existuje, pokud je mnoˇ zina strategi´ı kaˇ zd´ eho hr´ aˇ ce Si nepr´ azdn´ a, kompaktn´ı a konvexn´ı podmnoˇ zina Euklidovsk´ eho prostoru, a za urˇ cit´ ych podm´ınek na preference.

3

Pˇ r´ıklad 1.1.16 Naleznˇete Nashovy rovnov´ ahy her 1.1.5 aˇz 1.1.9. Kolik jich je? Jak jsme vidˇeli, existuj´ı hry kter´e nemaj´ı Nashovu rovnov´ahu (v ˇcist´ ych strategi´ıch). Pokud pˇripust´ıme, aby hr´ aˇci volili n´ ahodnˇe mezi vybran´ ymi strategiemi, nikoliv deterministicky jako dosud, situace se zmˇen´ı. Tomuto postupu se ˇr´ık´a pravdˇepodobnost´ı rozˇs´ıˇren´ı. Kaˇzd´ y hr´aˇc vol´ı pravdˇepodobnostn´ı rozdˇelen´ı na mnoˇzinˇe sv´ ych strategi´ı. V pˇr´ıpadˇe koneˇcn´ ych her, kter´e n´as budou nejv´ıce zaj´ımat, jde jednoduˇse o volbu pravdˇepodobnost´ı, se kter´ ymi bude danou strategii hr´ at. Souˇcet pravdˇepodobnost´ı pˇres vˇsechny strategie dan´eho hr´aˇce mus´ı d´at 1. Definice 1.1.17 Pravdˇepodobnost´ı rozˇs´ıˇren´ı hry v norm´ aln´ı formˇe {N, {Si }i∈N , {ui }i∈N } je hra {N, {4Si }i∈N , {Ui }i∈N }, kde 4Si je mnoˇzina pravdˇepodobnostn´ıch rozdˇelen´ı nad mnoˇzinou Si a Ui : 4S1 × · · · 4SN → R pˇriˇrazuje kaˇzd´emu prvku mnoˇziny σ ∈ 4S1 × · · · 4SN oˇcek´ avanou (stˇredn´ı) hodnotu hry   X Y  Ui (s) = σj (sj ) ui (s), s∈S

j∈N

pro koneˇcn´e mnoˇziny S. Definice 1.1.18 Nashova rovnov´ aha hry v norm´ aln´ı formˇe ve sm´ıˇsen´ych strategi´ıch (NE in mixed strategies) je Nashova rovnov´ aha jej´ıho pravdˇepodobnostn´ıho rozˇs´ıˇren´ı. Pˇ r´ıklad 1.1.19 Naleznˇete Nashovu rovnov´ ahu ve sm´ıˇsen´ych strategi´ıch u pˇredeˇsl´ych pˇr´ıklad˚ u, kde neexistovala Nashova rovnov´ aha v ˇcist´ych strategi´ıch. Pˇ r´ıklad 1.1.20 Zjistˇete, zda u her, kde existuje Nashova rovnov´ aha v ˇcist´ych strategi´ı, existuj´ı dalˇs´ı sm´ıˇsen´e NR. Pˇ r´ıklad 1.1.21 Spoˇctˇete vˇsechny Nashovy rovnov´ ahu hry Souboj pohlav´ı a spoˇc´ıtejte oˇcek´ avan´y uˇzitek prvn´ıho hr´ aˇce. Je vyˇsˇs´ı v pˇr´ıpadˇe sm´ıˇsen´ych strategi´ı nebo v pˇr´ıpadˇe ˇcist´ych? ˇ sen´ı 1.1.22 Lze snadno uk´ Reˇ azat, ˇze existuj´ı dvˇe rovnov´ ahy v ˇcist´ych strategi´ıch. Zkusme naj´ıt Nashovu rovnov´ ahu ve sm´ıˇsen´ych strategi´ıch. Oznaˇcme p pravdˇepodobnost, ˇze ˇzena zahraje H“, q ” pravdˇepodobnost ˇze tot´eˇz zahraje m˚ uˇz. Abychom byli v rovnov´ aze, tak mus´ı platit, ˇze volba hodnoty p maximalizuje oˇcek´ avan´y uˇzitek ˇzeny, tedy hr´ aˇce kter´y p vol´ı. maxp 2pq + (1 − p)(1 − q) Aby hodnota p, kter´ a tento v´yraz maximalizuje, leˇzela vevnitˇr intervalu [0, 1], mus´ı platit, ˇze 2q = 1 − q. Pokud by tomu tak nebylo, probl´em by nemˇel vnitˇrn´ı ˇreˇsen´ı a dostali bychom se zpˇet do ˇcist´ych strategi´ı. Podobn´ au ´vaha pro muˇze n´ am d´ av´ a podm´ınku na hodnotu p a to tuto: p = 2(1 − ˇ sen´ı tˇechto rovnic d´ av´ a p). Reˇ av´ a rovnov´ ahu ve sm´ıˇsen´ych strategi´ıch ( 23 , 13 ), kde prvn´ı ˇc´ıslo ud´ pravdˇepodobnost, se kterou prvn´ı hr´ aˇc hraje prvn´ı strategii a druh´e ˇc´ıslo tut´eˇz pravdˇepodobnost pro druh´eho hr´ aˇce. Oˇcek´ avan´ a hodnota v´yhry prvn´ıho hr´ aˇce je 2pq + (1 − p)(1 − q) =

5 . 9

Tento pˇr´ıklad ukazuje dva d˚ uleˇzit´e poznatky. Zaprv´e, hr´aˇc, kter´ y vol´ı urˇcit´e strategie ve sm´ıˇsen´e rovnov´ aze s pozitivn´ı pravdˇepodobnost´ı, mus´ı b´ yt indifferentn´ı mezi vˇsemi tˇemito strategiemi. Jin´ ymi slovy, vˇsechny strategie zvolen´e s pozitivn´ı pravdˇepodobnost´ı mu musej´ı pˇrin´aˇset stejn´ y uˇzitek, vˇetˇs´ı neˇz ty strategie, kter´e s kladnou pravdˇepodobnost´ı voleny nejsou. Tohoto poznatku lze ˇcastu vyuˇz´ıt pro rychlejˇs´ı v´ ypoˇcet rovnov´ahy ve sm´ıˇsen´ ych strategi´ıch. Druh´ y poznatek se t´ yk´ a oˇcek´ avan´e v´ yhry v rovnov´aze v ˇcist´ ych a ve sm´ıˇsen´ ych strategi´ıch. Nejmenˇs´ı moˇzn´ a v´ yhra v ˇcist´ ych strategi´ıch je pro dan´eho hr´aˇce 1, ale ve sm´ıˇsen´ ych to je 59 , tedy m´enˇe. I kdyˇz se m˚ uˇze zd´ at pˇrekvapiv´e, ˇze rozˇs´ıˇren´ım mnoˇziny strategi´ı poklesne oˇcek´avan´ y uˇzitek hr´ aˇc˚ u v rovnov´ aze, nen´ı to nic neobvykl´eho. Existuje samozˇrejmˇe i ˇrada her, ve kter´ ych oˇcek´avan´a v´ yhra v rovnov´ aze ve sm´ıˇsen´ ych strategi´ı je vˇetˇs´ı neˇz v nˇekter´e rovnov´aze v ˇcist´ ych strategi´ıch.

4

1.2

Poziˇ cn´ı Hry

Hry v norm´ aln´ı formˇe jsou vhodn´e pro popis situac´ı, kdy se hr´aˇci rozhoduj´ı z´aroveˇ n. Jak d´ale uvid´ıme, je moˇzn´e i pomoc´ı norm´ aln´ıch her popsat situace, kdy se hr´aˇce rozhoduj´ı postupnˇe, ale takov´ y popis m˚ uˇze b´ yt komplikovan´ y. Pro hry s explicitn´ı strukturou postupn´e volby jednotliv´ ych hr´ aˇc˚ u je vhodn´e vyuˇz´ıt tzv. poziˇcn´ı formy her. Neform´alnˇe, poziˇcn´ı forma hry popisuje, jak se hra postupuje (kdy se kdo rozhoduje), jak´e m´a moˇznosti a co v danou situaci v´ı. 1.2.1

Poziˇ cn´ı hry s kompletn´ı informac´ı

Pro zaˇc´ atek budeme definovat poziˇcn´ı hry s perfektn´ı informac´ı, tedy hry, ve kter´ ych kaˇzd´ y hr´aˇc v´ı, jak hr´ ali vˇsichni hr´ aˇci pˇred n´ım. Definice 1.2.1 Poziˇcn´ı hrou s perfektn´ı informac´ı (extensive game with perfect information) naz´yv´ ame 5-tici {N, H, Z, P : H\Z → N, {ui : Z → R}i∈N }, kde • N je koneˇcn´ a mnoˇzina hr´ aˇc˚ u, • H je mnoˇzina posloupnost´ı splˇ nuj´ıc´ıch: – pr´ azdn´ a posloupnost je jej´ım prvkem: ∅ ∈ H. – pokud dan´ a posloupnost n´ aleˇz´ı do H:(sk )k=1,...,K ∈ H, K ∈ N ∪ {∞}, pak i kaˇzd´ a kratˇs´ı posloupnost leˇz´ı v H, tj. pro vˇsechna L < K, (sk )k=1,...,L ∈ H • Prvky mnoˇziny H naz´yv´ ame historie, prvky histori´ı naz´yv´ ame akce. • Z ⊂ H je mnoˇzina tˇech termin´ aln´ıch histori´ı (sk )k=1,...K ∈ H, tedy tˇech posloupnost´ı z H, kter´e jsou bud’ nekoneˇcn´e a nebo neexistuje (sk )k=1,...,K+1 ∈ H. • Funkce P pˇriˇrazuje kaˇzd´e netermin´ aln´ı historii hr´ aˇce, kter´y po dan´e historii hraje (vol´ı akci). • ui je uˇzitkov´ a funkce pˇriˇrazuj´ıc´ı kaˇzd´e termin´ aln´ı historii v´yhru dan´eho hr´ aˇce.5 Jak d´ ale uvid´ıme, jedna ze vhodn´ ych forem z´apisu poziˇcn´ıch her jsou stromy. Koˇrenem stromu je rozhodnut´ı prvn´ıho hr´ aˇce. V druh´e u ´rovni jsou rozhodnut´ı, kter´a n´asleduj´ı jako druh´a v poˇrad´ı atd. Definice 1.2.2 Pokud je mnoˇzina H koneˇcn´ a, mluv´ıme o koneˇcn´e hˇre. Pokud jsou vˇsechny historie z H koneˇcn´e, mluv´ıme o hˇre s koneˇcn´ ym horizontem. Pˇ r´ıklad 1.2.3 Zkonstruujte hru, kter´ a nen´ı koneˇcn´ a, ale m´ a koneˇcn´y horizont. I zde existuj´ı alternativn´ı definice pomoc´ı, napˇr´ıklad pomoc´ı strom˚ u, vrchol˚ u a list˚ u atd. Pro srovn´ an´ı pouˇzijte napˇr´ıklad Wikipedii (http://en.wikipedia.org/wiki/Extensive form game). Definice 1.2.4 Pro kaˇzdou netermin´ aln´ı historii h oznaˇcujeme (h, a) historii, ve kter´e h je n´ asledov´ ana akc´ı a a je tedy o jednotku delˇs´ı. Pro kaˇzdou historii h hr´ aˇc P (h) vol´ı akci z mnoˇziny A(h) = {a : (h, a) ∈ H}. Pˇ r´ıklad 1.2.5 Hra o vstupu na trh (Market Entry Game). Existuj´ıc´ı trh je pokryt jedinou firmou, kter´ a dosahuje zisku 2. Nov´ a firma zvaˇzuje vstup na tento trh. Pokud se rozhodne nevstoupit, ˇz´ adn´e n´ aklady ani v´ynosy m´ıt nebude. Pokud vstoup´ı, tak se existuj´ıc´ı firma rozhodne, zda se tomuto vstupu pˇrizp˚ usob´ı (obˇe firmy v takov´em pˇr´ıpadˇe dos´ ahnou zisku 1), nebo bude s novou firmou bojovat o trh (napˇr´ıklad prostˇrednictv´ım sn´ıˇzen´ych cen, n´ akladnou reklamn´ı kampan´ı atd.), ale pak budou obˇe firmy ve ztr´ atˇe. 5 Podobnˇ e jako pro hry v norm´ aln´ı formˇ e lze i zde pouˇ z´ıt o nˇ eco obecnˇ ejˇs´ı pˇr´ıstup a definovat preferenˇ cn´ı uspoˇr´ ad´ an´ı na mnoˇ zinˇ e termin´ aln´ıch vrchol˚ u.

5

Nov´ a firma

• ss HHHH HVstup HH s ss HH s ys H# Zabˇehnut´a firma •B (0, 2) xx BB x BBPˇrizp˚ Bojuj xx usob se x BB xx B x {x (−1, −1) (1, 1) Nevstupujsss

Pˇ r´ıklad 1.2.6 (Dˇ elen´ı pokladu.) Ve zn´ am´e u ´loze jak se dva mohou spravedlivˇe rozdˇelit o hrom´ adku pˇredmˇet˚ u se doporuˇcuje nechat prvn´ıho z pod´ıln´ık˚ u rozdˇelit pˇredmˇety na dvˇe ˇc´ asti a druh´eho nechat vybrat si jednu z hrom´ adek. Namodelujte tento postup jako hru dvou hr´ aˇc˚ u. Pro zjednoduˇsen´ı m˚ uˇzete uvaˇzovat, ˇze cel´ a hrom´ adka m´ a hodnotu $1 a je dokonale dˇeliteln´ a. Nebo je jednoduˇsˇs´ı, pokud poklad lze dˇelit jen po desetin´ ach? Nashovu rovnov´ ahu v poziˇcn´ıch hr´ach je moˇzn´e definovat velmi podobnˇe jako ve hr´ach v norm´ aln´ı formˇe, jen je potˇreba peˇclivˇe definovat, co je to strategie. Definice 1.2.7 Strategie i-t´eho hr´ aˇce v poziˇcn´ı hˇre s perfektn´ı informac´ı je funkce, kter´ a kaˇzd´e netermin´ aln´ı historii h ∈ H\Z, po kter´e hraje hr´ aˇc i, tj. P (h) = i, pˇriˇrazuje akci z mnoˇziny A(h). Strategie obvykle znaˇc´ıme si , jejich mnoˇzinu Si . Na t´eto definici m˚ uˇze b´ yt ponˇekud pˇrekvapiv´e to, ˇze strategie hr´aˇce mus´ı urˇcovat akci v kaˇzd´e historii, ve kter´e dan´ y hr´ aˇc hraje, a to i v tˇech histori´ıch, kter´e nemohou napsat kv˚ uli volbˇe dan´eho hr´ aˇce. D´ ale je potˇreba rozliˇsit v´ysledek hry (outcome) od strategick´eho profilu hry ( si )i∈N . V´ ysledkem hry je termin´ aln´ı historie, ke kter´e vede hra podle onoho strategick´eho profilu. Pomoc´ı strategi´ı m˚ uˇzeme snadno definovat strategickou formu poziˇcn´ı hry. Hru v norm´aln´ı formˇe definuje mnoˇzina hr´ aˇc˚ u, kter´ a z˚ ust´av´a beze zmˇeny, mnoˇzina strategi´ı kaˇzd´eho hr´aˇce z pˇredchoz´ı definice a syst´em v´ yhern´ıch funkc´ı, kter´ y vznik´a pˇrirozenˇe z v´ yhern´ıch funkc´ıch poziˇcn´ı hry. Pˇ r´ıklad 1.2.8 V n´ asleduj´ıc´ı hˇre patˇr´ı mezi strategie prvn´ıho hr´ aˇce i strategie L, R, pˇrestoˇze pot´e, co zahr´ al L“ nen´ı moˇzn´e, aby dostal pˇr´ıleˇzitost znovu hr´ at. ” 1 •K tt KKKK t L ttt KKR KK tt KK t zt K% 2 (0, 0) t • JJJ tt JJ t U tt JJD t JJ t t JJ t zt J$ 1 • HH (1, −1) t HH tt t HHR L tt HH t HH tt t HH zt $ 2 (−2, 2) v • @@@ v v @@D U vv @@ vv v @@ zvv @ (−3, 3) (2, 2) Tot´eˇz plat´ı pro druh´eho hr´ aˇce. Definice 1.2.9 Nashovou rovnov´ ahou poziˇcn´ı hry s perfektn´ı informac´ı je strategick´y profil hry (s∗i )i∈N takov´y, ˇze ui (s∗−i , s∗i ) ≥ ui (s∗−i , si ), ∀si ∈ Si , ∀i ∈ N ˇ sen´ı hry o vstupu na trh. Tato hra m´ Pˇ r´ıklad 1.2.10 Reˇ a dvˇe Nashovy rovnov´ ahy. V prvn´ı z nich st´ avaj´ıc´ı firma vol´ı strategii (Boj) pokud nov´ a firma vstoup´ı. V takov´em pˇr´ıpadˇe je pro novou firmu v´yhodnˇejˇs´ı nevstupovat. V druh´e Nashovˇe rovnov´ aze se st´ avaj´ıc´ı firma po (potenci´ aln´ım) vstupu pˇrizp˚ usob´ı a pro firmu zvaˇzuj´ıc´ı vstup je tedy optim´ aln´ı vstoupit.

6

Pˇredchoz´ı pˇr´ıklad naznaˇcuje, ˇze koncept Nashovy rovnov´ahy nen´ı pro poziˇcn´ı hry vhodn´ y. Zat´ımco ve hr´ ach v norm´ aln´ı formˇe prob´ıh´a volba strategi´ı souˇcasnˇe, poziˇcn´ı hry jsou typicky sekvenˇcn´ı, tedy rozhodnut´ı nˇekter´ ych hr´aˇc˚ u n´asleduje aˇz po rozhodnut´ı jin´ ych. Rozhodnut´ı o strategii druh´ y hr´ aˇc tvoˇr´ı teprve pot´e, co se dozv´ı rozhodnut´ı prvn´ıho hr´aˇce. I kdyˇz se druh´ y hr´ aˇc m˚ uˇze snaˇzit pˇresvˇedˇcit prvn´ıho hr´aˇce o tom, jakou volbu provede v budoucnu, racion´aln´ı hr´ aˇci maximalizuj´ı vlastn´ı uˇzitek a prvn´ı hr´aˇc toho m˚ uˇze vyuˇz´ıt k odhadu toho, jakou strategii zvol´ı druh´ y hr´ aˇc. Napˇr´ıklad v pˇredeˇsl´em pˇr´ıkladu nen´ı racion´aln´ı volba strategie (Boj), pot´e co prvn´ı hr´ aˇc vstoupil na trh. Druh´ y hr´aˇc takovou volbou ztr´ac´ı uˇzitek a protoˇze prvn´ı hr´aˇc jiˇz vstoupil, nem˚ uˇze t´ım ani ovlivnit prvn´ıho hr´aˇce. Prvn´ı z Nashov´ ych rovnov´ach tak ned´av´a smysl pro racion´ aln´ı hr´ aˇce.6 Tyto u ´vahy lze formalizovat do pˇr´ıstupu tzv. zpˇetn´e indukce. Pˇri zpˇetn´e indukci se hra ˇreˇs´ı od konce - postupuje se od nejniˇzˇs´ıch u ´rovn´ı a kaˇzd´ y netermin´aln´ı uzel se nahrazuje termin´ aln´ım s takovou hodnotou, jak´a odpov´ıd´a ˇreˇsen´ı t´eto u ´rovnˇe. Nejl´epe tento postup popisuje pˇr´ıklad n´ asleduj´ıc´ı po potˇrebn´ ych definic´ıch. Zaˇc´ıt mus´ıme s definic´ı podhry. Definice 1.2.11 Podhra poziˇcn´ı hry Γ = {N, H, Z, P : H\Z → M, {ui : Z → R}i∈N } n´ asleduj´ıc´ı po historii h je poziˇcn´ı hra Γ(h) = {N, H|h , Z|h , P |h : H|h \Z|h → N, {ui |h : Z|h → R}i∈N }, kde H|h je mnoˇzina histori´ı h0 takov´ych, ˇze (h, h0 ) ∈ H , funkce P |h je definov´ ana pˇredpisem P |h (h0 ) = P (h, h0 ) pro vˇsechna h0 ∈ H|h . Mnoˇzina termin´ aln´ıch histori´ı Z|h je definov´ ana jako v definici poziˇcn´ı hry a ui |h jsou definov´ ana pomoc´ı ui takto: ui |h (h0 ) = ui (h, h0 ). ˇ sen´ı hry pomoc´ı zpˇetn´e indukce vyˇzaduje, aby akce, kterou hr´aˇc vol´ı, byla optim´aln´ı pro Reˇ dan´e strategie protihr´ aˇc˚ u po kaˇzd´e historii.7 Profil strategi´ı, kter´e tyto poˇzadavky splˇ nuj´ı, jsou nˇekdy naz´ yv´ any dokonal´ a rovnov´ aha vzhledem k podhr´ am (subgame perfect equilibrium). Definice 1.2.12 Dokonalou rovnov´ ahou vzhledem k podhr´am (DRVP) naz´yv´ ame takov´y profil strategi´ı s∗ hry Γ = {N, H, Z, P : H\Z → M, {ui : Z → R}i∈N }, ˇze pro kaˇzd´eho hr´ aˇce i ∈ N a kaˇzdou netermin´ aln´ı historii h ∈ H\Z takovou, ˇze P (h) = i plat´ı ui |h (s∗−i |h , s∗i |h ) ≥ ui |h (s∗−i |h , si ) pro vˇsechny strategie si podhry Γ(h). Z definice vypl´ yv´ a, ˇze kaˇzd´ a DRVP je tak´e Nashovou rovnov´ahou. Opaˇcn´ ym smˇerem to samozˇrejmˇe neplat´ı.8 ˇ sen´ı 1.2.13 (Hra o vstupu na trh) Pokud pouˇzijeme zpˇetnou indukci na hru O vstupu na Reˇ trh, nejprve ˇreˇs´ıme podhru, kdy se druh´y hr´ aˇc (Zabˇehnut´ a firma) rozhoduje, zda bojovat ˇci pˇrizp˚ usobit se. Evidentnˇe, jakmile hra dos´ ahla tohoto bodu, je v´yhodnˇejˇs´ı se pˇrizp˚ usobit. Prvn´ı hr´ aˇc bere toto ˇreˇsen´ı v u ´vahu a hra, kterou ˇreˇs´ı je Nov´ a firma

• z DDD DDVstup DD zz D! z }z (0, 2) (1, 1)

Nevstupuj zzz

V takov´e situaci je pro novou firmu v´yhodnˇejˇs´ı na trh vstoupit. DRVP je tedy ( vstup“, pˇrizp˚ usob ” ” se“). ˇ sen´ı 1.2.14 (Dˇ Reˇ elen´ı pokladu) Druh´y hr´ aˇc si vyb´ır´ a mezi dvˇema hrom´ adkami. Je v jeho z´ ajmu vybrat si tu vˇetˇs´ı (hodnotnˇejˇs´ı). Prvn´ı hr´ aˇc toto oˇcek´ av´ a a proto je pro nˇej nejv´yhodnˇejˇs´ı hrom´ adku rozdˇelit na dvˇe stejn´e ˇc´ asti. (Co kdyˇz to nejde?). 6 Form´ alnˇ e je nejen potˇreba, ˇ ze oba hr´ aˇ ci jsou racion´ aln´ı, ale ˇ ze tento fakt je vˇseobecnˇ e zn´ am. Tedy prvn´ı hr´ aˇ c v´ı, ´ ˇ ze druh´ y hr´ aˇ c je racion´ aln´ı. Tak´ e druh´ y hr´ aˇ c v´ı, ˇ ze prvn´ı hr´ aˇ c v´ı, ˇ ze druh´ y hr´ aˇ c je racion´ aln´ı atd. Uplna formalizace toho probl´ emu je pomˇ ernˇ e sloˇ zit´ a a jde nad r´ amec tohoto textu. 7 V poziˇ cn´ıch hr´ ach s ne´ uplnou informac´ı uvid´ıme, ˇ ze ne kaˇ zd´ a historie definuje podhru. V tuto chv´ıli ale je situace jednoduˇsˇs´ı, nebot’ pro kaˇ zdou historii m˚ uˇ zeme definovat podhru. 8 Nˇ ekdy mluv´ıme o tzv. refinements, tedy zpˇresnˇ en´ ych Nashovy rovnov´ ahy, kter´ e n´ am umoˇ zn ˇuj´ı vybrat tu nej” rozumnˇ ejˇs´ı“ z Nashov´ ych rovnov´ ah. V pˇr´ıpadˇ e DRVP jsou odstranˇ eny ty Nashovy rovnov´ ahy, ve kter´ ych nˇ ekter´ yz hr´ aˇ c˚ u vyhroˇ zuje pomoc´ı nevˇ erohodn´ e hrozby (non-credible threat).

7

Definice dokonal´e rovnov´ ahy vzhledem k podhr´am vyˇzaduje porovn´an´ı potenci´aln´ıho kandid´ata na rovnov´ ahu se vˇsemy moˇzn´ ymi strategiemi, pro vˇsechny hr´aˇce. D´a se uk´azat, ˇze toto srovn´an´ı lze v´ yraznˇe zjednoduˇsit. K tomu, abychom ovˇeˇrili zda o rovnov´ahu jde (ˇci ne), staˇc´ı ovˇeˇrit, ˇze ˇz´ adn´ y hr´ aˇc si nem˚ uˇze polepˇsit zmˇenou jedin´e akce v situaci, kdy se o n´ı rozhoduje. Lemma 1.2.15 Lemma o jedn´e odchylce. Necht’ Γ = {N, H, Z, P : H\Z → M, {ui : Z → R}i∈N } je hra s koneˇcn´ym horizontem. Profil strategi´ı s∗ tvoˇr´ı DRVP tehdy a jen tehdy kdyˇz pro kaˇzd´eho hr´ aˇce i ∈ N a kaˇzdou historii h takovou, ˇze P (h) = i plat´ı ui |h (s∗−i |h , s∗i |h ) ≥ ui |h (s∗−i |h , si ) pro kaˇzdou strategii si hr´ aˇce i v podhˇre Γ(h) kter´ a se liˇs´ı od s∗i |h jen v akci po historii h. Vˇ eta 1.2.16 Kaˇzd´ a koneˇcn´ a poziˇcn´ı hra s dokonalou informac´ı m´ a DRVP, a tedy alespoˇ n jednu Nashovu rovnov´ ahu. D˚ ukaz 1.2.17 Indukc´ı vzhledem k d´elce nejdelˇs´ı historie hry . 1.2.2

Poziˇ cn´ı hry s ne´ uplnou informac´ı

Definici poziˇcn´ı hry lze snadno pˇrizp˚ usobit situaci, kdy dan´ y hr´aˇc pˇri volbˇe sv´e akce nev´ı, jak se rozhodl hr´ aˇc pˇred n´ım. Je dokonce moˇzn´e definici pˇrizp˚ usobit i situaci, kdy nˇejak´ y hr´aˇc zapomene, jak hr´ al dˇr´ıve. Form´ alnˇe je tato definice zaloˇzena na tzv. informaˇcn´ıch mnoˇzin´ach. Napˇr´ıklad pokud druh´ y hr´ aˇc nev´ı, jakou akci zvolil prvn´ı hr´ aˇc, jsou pro nˇej ty historie, kter´e se liˇs´ı v tahu prvn´ıho hr´aˇce nerozliˇsiteln´e. Aby nebyl schopen odvodit, jakou akci prvn´ı hr´aˇc zvolil, je nutn´e, aby mnoˇzina jeho moˇzn´ ych akc´ı byla pro dan´e historie stejn´a. Pokud by druh´ y hr´aˇc po jedn´e akci prvn´ıho hr´aˇce mˇel na v´ ybˇer 3 akce, ale po druh´e akci jen 2, mohl by si snadno odvodit, jak hr´al prvn´ı hr´aˇc. Tyto pˇr´ıpady mus´ı b´ yt vylouˇceny. Definice 1.2.18 Poziˇcn´ı hrou (extensive-form game ) naz´yv´ ame 7-tici {N, H, Z, fØ , P : H\Z → N ∪ {Ø}, Ii∈N , {ui : Z → R}i∈N , }, kde • N je koneˇcn´ a mnoˇzina hr´ aˇc˚ u, Ø je hr´ aˇc n´ ahoda“, ” • H je mnoˇzina posloupnost´ı splˇ nuj´ıc´ıch: – pr´ azdn´ a posloupnost je jej´ım prvkem: ∅ ∈ H. – pokud dan´ a posloupnost n´ aleˇz´ı do H:(sk )k=1,...,K ∈ H, K ∈ N ∪ {∞}, pak i kaˇzd´ a kratˇs´ı posloupnost leˇz´ı v H, tj. pro vˇsechna L < K, (sk )k=1,...,L ∈ H • Prvky mnoˇziny H naz´yv´ ame historie, prvky histori´ı naz´yv´ ame akce. • Z ⊂ H je mnoˇzina tˇech termin´ aln´ıch histori´ı (sk )k=1,...K ∈ H, tedy tˇech posloupnost´ı z H, kter´e jsou bud’ nekoneˇcn´e a nebo neexistuje (sk )k=1,...,K+1 ∈ H. • Funkce fØ pˇriˇrazuje kaˇzd´e historii h takov´e, ˇze P (h) = Ø pravdˇepodobnostn´ı rozdˇelen´ı9 fØ (·|h) na mnoˇzinˇe A(h) • Funkce P pˇriˇrazuje kaˇzd´e netermin´ aln´ı historii hr´ aˇce, kter´y po dan´e historii hraje (vol´ı akci). • Pro kaˇzd´eho hr´ aˇce i ∈ N oznaˇcuje Ii = {Ij }j=1,... rozdˇelen´ı10 mnoˇziny {h ∈ H : P (h) = i} takov´e, ˇze A(h) = A(h0 ) pokud h a h0 n´ aleˇz´ı do t´eˇze mnoˇziny rozdˇelen´ı. Znaˇc´ıme A(Ii ) ame mnoˇzinu A(h) a P (Ii ) mnoˇzinu P (h) pro libovolnou historii h ∈ Ii . Rozdˇelen´ı Ii naz´yv´ informaˇcn´ı rozdˇelen´ı, jeho prvky informaˇcn´ımi mnoˇzinami i-t´eho hr´ aˇce 9 Obvykle budeme uvaˇ zovat hry, kde A(h) je koneˇ cn´ a a tak fØ (a|h) ud´ av´ a pravdˇ epodobnost, ˇ ze n´ ahoda zvol´ı akci a po historii h. 10 Rozdˇ elen´ı je mnoˇ zina podmnoˇ zin dan´ e mnoˇ ziny, kter´ e jsou vz´ ajemnˇ e disjunktn´ı a jejich sjednocen´ı pokr´ yv´ a danou mnoˇ zinu.

8

• ui je uˇzitkov´ a funkce pˇriˇrazuj´ıc´ı kaˇzd´e loterii termin´ aln´ı historie v´yhru dan´eho hr´ aˇce.11 Tato definice zav´ ad´ı kromˇe pojmu informaˇcn´ı rozdˇelen´ı a informaˇcn´ı mnoˇzina tak´e nov´eho hr´aˇce - n´ ahodu. Je moˇzn´e bez vˇetˇs´ıch obt´ıˇz´ı dodefinovat n´ahodu i ve hr´ach bez u ´pln´e informace. Pˇ r´ıklad 1.2.19 Form´ alnˇe definujte n´ asleduj´ıc´ı hru 1

l • SSSSS lll SSS D U llll SSS ll SSS l l l SSS l l l S 2 2 ul • D_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _) • FF x D z FF x DD R z FFR L zz L xxx DD z FF x DD z x F" |xx ! }zz (1, 2) (2, 1) (−1, 3) (3, −1) ve kter´e pˇreruˇsovanou ˇcarou spojen´e uzly patˇr´ı do stejn´e informaˇcn´ı mnoˇziny. Pˇ r´ıklad 1.2.20 Naleznˇete hru v norm´ aln´ı formˇe odpov´ıdaj´ıc´ı pˇredchoz´ı poziˇcn´ı hˇre. Pˇ r´ıklad 1.2.21 Je moˇzn´e kaˇzdou poziˇcn´ı hru s dokonalou informac´ı povaˇzovat za poziˇcn´ı hru? ˇ Definice 1.2.22 Cistou strategi´ı v poziˇcn´ıch hr´ ach rozum´ıme pˇredpis akce a pro kaˇzdou informaˇcn´ı mnoˇzinu Ii pro dan´eho hr´ aˇce i. Pˇ r´ıklad 1.2.23 Je n´ asleduj´ıc´ım stromem pops´ ana poziˇcn´ı hra? 1

a



•?  ???  ??  ?  1  c •> >> >> >> > b

Pˇredchoz´ı pˇr´ıklad naznaˇcuje, jak´ ym zp˚ usobem je moˇzn´e modelovat hry, ve kter´ ych jeden z hr´ aˇc˚ u zapomene vlastn´ı pˇredeˇsl´ y tah. Form´alnˇe je moˇzn´e definovat hry s dokonalou pamˇet´ı (perfect recall ). Na ty se budeme zamˇeˇrovat v dalˇs´ım textu, nen´ı-li zm´ınˇeno jinak. Podobnˇe jako v poziˇcn´ıch hr´ ach s dokonalou informac´ı lze i ve hr´ach s nedokonalou informac´ı definovat podhry. Jedinou dodateˇcnou podm´ınkou je, aby podhra, kter´a obsahuje ˇc´ast urˇcit´e informaˇcn´ı mnoˇziny, tuto mnoˇzinu obsahovala celou. Pˇ r´ıklad 1.2.24 Vypiˇste vˇsechny podhry n´ asleduj´ıc´ı hry jj A OOOO jjjj OOO j j j OOO jj j j j OOO jj j j O' j tjj C OOO B o @ @@ OOO ~ oo o ~ o OOO @@ ~ oo ~ o OOO o @ ~ oo @ ~ OO' o ~  o wo E @_ _ _ _ _ _ _ _ _ _ F A G@ D@ AA @@ @@ @@ }} }} ~~ ~~ A } @@ @ @ } ~ ~ A } @ @ } ~ ~ A } @@ @@ @@ } ~ ~ AA } ~~   ~~ ~}} ~}} • • • • • • • • D´ıky t´eto definici m˚ uˇzeme rozˇs´ıˇrit definici dokonal´e rovnov´ahy vzhledem k podhr´am i na poziˇcn´ı hry bez kompletn´ı informace. Opˇet poˇzadujeme, aby strategie rovnov´ahy tvoˇrily Nashovu rovnov´ ahu v kaˇzd´e podhˇre. 11 Protoˇ ze ve hˇre m˚ uˇ ze hr´ at n´ ahoda, hra nem´ a obvykle jedinou termin´ aln´ı historii. Je potˇreba uv´ aˇ zit loterii, kterou n´ ahoda zp˚ usobuje. Pro naˇse u ´ˇ cely postaˇ c´ı, kdyˇ z budeme uvaˇ zovat stˇredn´ı (oˇ cek´ avanou) hodnotu v´ yhry vych´ azej´ıc´ı z v´ yher v jednotliv´ ych termin´ aln´ıch histori´ıch.

9

Pˇ r´ıklad 1.2.25 Naleznˇete vˇsechny DRVP n´ asleduj´ıc´ı hry: 1

r • SSSSSS rr SSS A B rrr SSS SSS rr r SSS r y S) 2 •T (1, 0, 3) x TTTTTT x TTTTX x Y xx TTTT xx TTTT x x TT 3 3 {x • F_F _ _ _ _ _ _ _ _ _ _ _ _ _ _* • FF x F FF x xx FF C FFC D xxx D xxx FF FF x x FF x x F# {xx {xx # (2, 1, 2) (0, 1, 0) (0, 2, 0) (2, 2, 2) ˇ sen´ı 1.2.26 Hra m´ Reˇ a dvˇe podrhy. Hru samotnou a podhru zaˇc´ınaj´ıc´ı tahem druh´eho hr´ aˇce. Staˇc´ı nal´ezt vˇsechny Nashovy rovnov´ ahy druh´e podhry a pak ovˇeˇrit, zda existuje strategie prvn´ıho hr´ aˇce tak, ˇze jde st´ ale o Nashovu rovnov´ ahu. Nashova rovnov´ aha vlastn´ı podhry je jedin´ a, a to (X, C). Prvn´ı hr´ aˇc pak vol´ı radˇeji A, takˇze DRVP je (A, X, C). Pˇ r´ıklad 1.2.27 Jsou ˇsachy poziˇcn´ı hrou ? Jsou hrou bez kompletn´ı informace? A poker? Podobnˇe jako ve hr´ ach v norm´ aln´ı formˇe je i v poziˇcn´ıch hr´ach moˇzn´e definovat strategie vyuˇz´ıvaj´ıc´ı pravdˇepodobnosti. Nen´ı ale zˇrejm´e, zda hr´aˇci maj´ı n´ahodnˇe volit ˇcistou strategii a nebo n´ ahodnˇe a nez´ avisle volit akci kdykoliv jsou na tahu. Tyto dvˇe moˇznosti vedou k n´asleduj´ıc´ım dvˇema definic´ım. Definice 1.2.28 Sm´ıˇsen´ a strategie i-t´eho hr´ aˇce je pravdˇepodobnostn´ı rozdˇelen´ı na mnoˇzinˇe ˇcist´ych strategi´ı. Behavior´ aln´ı strategie je souhrn nez´ avisl´ych pravdˇepodobnostn´ı rozdˇelen´ı (βi (Ii )), kde βi (Ii ) je pravdˇepodobnostn´ı rozdˇelen´ı nad mnoˇzinou A(Ii ). Analogicky k pˇredchoz´ım definic´ım, pomoc´ı konceptu sm´ıˇsen´ ych a behavior´aln´ıch strategi´ı m˚ uˇzeme definovat i zde Nashovu rovnov´ahu. Pro hry s dokonalou pamˇet´ı jsou tyto dva koncepty ekvivalentn´ı vzhledem k v´ ysledk˚ um (outcome equivalent).12 Pˇ r´ıklad 1.2.29 Pokuste se naj´ıt ˇreˇsen´ı n´ asleduj´ıc´ı hry, kter´e by bylo analogick´e dokonal´e rovnov´ aze vzhledem k podhr´ am, tedy vyˇzadovalo, aby strategie kaˇzd´eho hr´ aˇce byla optim´ aln´ı v kaˇzd´e informaˇcn´ı mnoˇzinˇe. 1 • VVVVV kkk VVVV k k k VVVV R k L kk VVVV k M k k VVVV k k VVVV k k uk  V 2 • B_ _ _ _ _ _ _ _ _ _ _ _ _V+ • B (2, 2) | B | || BBB BB L || L || BB BB | | | | R BB R BB | | ~| ~| (3, 1) (0, 0) (0, 2) (1, 1) ˇ sen´ı 1.2.30 Jakmile se druh´y hr´ Reˇ aˇc ocitne na tahu, tedy ve sv´e informaˇcn´ı mnoˇzinˇe, je pro nˇej optim´ aln´ı volit L“, bez ohledu na to, zda se do t´eto informaˇcn´ı mnoˇziny dostal—tedy zda prvn´ı ” hr´ aˇc volil M“ ˇci R“. Prvn´ı hr´ aˇc pak optim´ alnˇe vol´ı L“. ” ” ” Pˇ r´ıklad 1.2.31 Pokuste se podobnˇe vyˇreˇsit n´ asleduj´ıc´ı pˇr´ıklad 1 • VVVVV kkk VVVV k k VVVV R L kkkk VVVV k M kk VVVV k k VVVV ukkk  V 2 • B_ _ _ _ _ _ _ _ _ _ _ _ _V+ • B (2, 2) | B | || BBB BB L || L || BB BB | | | | R BB R BB | | ~| ~| (3, 1) (0, 2) (0, 2) (1, 1) 12 Sm´ ıˇsenou strategii dan´ eho hr´ aˇ ce definujeme jako ekvivalentn´ı vzhledem k v´ ysledk˚ um behavior´ aln´ı strategii, pokud pro kaˇ zdou kombinaci ˇ cist´ ych strategi´ı ostatn´ıch hr´ aˇ c˚ u tyto strategie vedou ke stejn´ emu pravdˇ epodobnostn´ımu rozdˇ elen´ı termin´ aln´ıch histori´ı.

10

ˇ sen´ı 1.2.32 V t´eto situaci jiˇz nen´ı zˇrejm´e, zda je lepˇs´ı pro druh´eho hr´ Reˇ aˇce hr´ at L“ nebo R“. ” ” Toto rozhodnut´ı z´ aleˇz´ı na tom, jak hr´ al prvn´ı hr´ aˇc. Pokud druh´y hr´ aˇc povaˇzuje za pravdˇepodobnˇejˇs´ı, ˇze prvn´ı hr´ aˇc volil M“, pak je pro nˇej lepˇs´ı zvolit R“, v opaˇcn´em pˇr´ıpadˇe L“. Strategie prvn´ıho ” ” ” hr´ aˇce potom m˚ uˇze odpov´ıdat tomu, v co druh´y hr´ aˇc vˇeˇr´ı. V nˇekter´ych situac´ı ale tato informace nem˚ uˇze b´yt odvozena ze strategi´ı hr´ aˇc˚ u, nebot’ pravdˇepodobnost ˇze se hra dostane do t´eto informaˇcn´ı mnoˇziny m˚ uˇze b´yt nula. Napˇr´ıklad pokud se prvn´ı hr´ aˇc rozhodne hr´ at L“, informaˇcn´ı mnoˇziny ” druh´eho hr´ aˇce nen´ı dosaˇzeno. Prvn´ı moˇzn´ y pˇr´ıstup k ˇreˇsen´ı poziˇcn´ıch her s ne´ uplnou informac´ı je zaloˇzen na slab´e Bayesovˇe rovnov´ aze (Weak Perfect Bayesian Equilibrium, d´ale jen WPBE, vyuˇz´ıvaj´ıc´ım tzv. oˇcek´av´an´ı (beliefs), coˇz je mnoˇzina pravdˇepodobnostn´ıch rozdˇelen´ı, kaˇzd´e z nich nad historiemi n´aleˇzej´ıc´ımi do t´eˇze informaˇcn´ı mnoˇziny. V pˇr´ıpadˇe, ˇze informaˇcn´ı mnoˇzina obsahuje jedin´ y prvek, je oˇcek´av´an´ı trivi´ aln´ı—kaˇzd´ y hr´ aˇc v´ı, kde se nach´ az´ı. V pˇredchoz´ım pˇr´ıkladu je tak podstatn´e jedin´e oˇcek´av´an´ı, tedy pravdˇepodobnost, se kterou hr´ aˇc oˇcek´av´a, ˇze se vyskytuje vlevo v informaˇcn´ı mnoˇzinˇe (po M“) nebo vpravo (po R“). WPBE poˇzaduje, aby oˇcek´av´an´ı byla zaloˇzena na Bayesovˇe pravi” 13 ” dle, kdekoliv to je moˇzn´e. Bayesovo pravidlo nelze pouˇz´ıt tam, kde dan´e informaˇcn´ı mnoˇziny nen´ı v˚ ubec dosaˇzeno a pouˇzit´ı pravidla by vyˇzadovalo dˇelen´ı 0. Tam, kde dan´e informaˇcn´ı mnoˇziny nen´ı dosaˇzeno, mohou b´ yt oˇcek´ av´ an´ı jak´akoliv. Pˇ r´ıklad 1.2.33 V pˇredchoz´ım pˇr´ıkladˇe prvn´ı hr´ aˇc hraje behavior´ aln´ı strategii µ = (p, q, 1 − p − q). Jak´e je oˇcek´ av´ an´ı druh´eho hr´ aˇce podle Bayesova pravidla? ˇ sen´ı 1.2.34 Oˇcek´ Reˇ av´ an´ı je pravdˇepodobnost, ˇze se hr´ aˇc nach´ az´ı v dan´em m´ıstˇe informaˇcn´ı mnoˇziny za podm´ınky, ˇze bylo dan´e mnoˇziny dosaˇzeno. Je tedy zˇrejm´e, ˇze souˇcet pravdˇepodobnost´ı dan´eho oˇcek´ av´ an´ı pˇres kaˇzdou informaˇcn´ı mnoˇzinu mus´ı d´ at souˇcet 1. Oznaˇcme tedy r pravdˇepodobnost, se kterou hr´ aˇc 2 oˇcek´ av´ a, ˇze se nach´ az´ı v lev´e ˇc´ asti dan´e informaˇcn´ı mnoˇziny. Podle Bayseova q pravidla plat´ı r = 1−p a podobnˇe pro pravdˇepodobnost, ˇze se nach´ az´ı vpravo plat´ı 1 − r = 1−p−q 1−p . Snadno lze ovˇeˇrit, ˇze souˇcet d´ av´ a 1. Pokud je ovˇsem p = 1, q = 0, Bayesovo pravidlo nelze pouˇz´ıt a hr´ aˇc 2 m˚ uˇze m´ıt jak´ekoliv oˇcek´ av´ an´ı. Definice 1.2.35 Behavior´ aln´ı profil strategi´ı (βi (Ii )) tvoˇr´ı WPBE, pokud existuje profil oˇcek´ av´ an´ı µ∗ takov´y, ˇze strategie kaˇzd´eho hr´ aˇce maximalizuje jeho v´yhru pro dan´e strategie ostatn´ıch hr´ aˇc˚ u a dan´ a oˇcek´ av´ an´ı, a takov´y, ˇze oˇcek´ av´ an´ı jsou odvozena pomoc´ı Bayesova vzorce ve vˇsech informaˇcn´ıch mnoˇzin´ ach, kter´ych je dosaˇzeno. To, ˇze definice neupˇresˇ nuje oˇcek´ av´ an´ı v informaˇcn´ıch mnoˇzin´ach, kter´ ych nen´ı nikdy dosaˇzeno zp˚ usobuje, ˇze mohou existovat WPBE, kter´e netvoˇr´ı dokonalou rovnov´ahu vzhledem k podhr´am, jak ukazuje n´ asleduj´ıc´ı pˇr´ıklad. Pˇ r´ıklad 1.2.36 Naleznˇete vˇsechny WPBE pˇr´ıklady 1.2.25 ˇ sen´ı 1.2.37 Prvn´ım pˇr´ıkladem WPBE je pr´ Reˇ avˇe DRVP, jak lze snadno ovˇeˇrit. Existuje ale i dalˇs´ı WPBE. Kl´ıˇcem k jeho nalezen´ı je pr´ avˇe moˇznost volby libovoln´ych oˇcek´ av´ an´ı v situaci, kdy dan´e informaˇcn´ı mnoˇziny nen´ı dosaˇzeno. Pˇredstavme si, ˇze hr´ aˇc 3 vˇeˇr´ı, ˇze se nach´ az´ı vlevo sv´e informaˇcn´ı mnoˇziny. Pak je pro nˇej optim´ aln´ı hr´ at D. Pro druh´eho hr´ aˇce je i v takov´em pˇr´ıpadˇe optim´ aln´ı hr´ at X. Pro prvn´ıho hr´ aˇce je ale optim´ aln´ı hr´ at B, protoˇze kdyby hr´ al A, tak by jeho zisk byl 0, nam´ısto 1, kter´e mu zaruˇcuje strategie B. V podstatˇe nesmysln´e14 oˇcek´ av´ an´ı hr´ aˇce 3 tak nen´ı vyvr´ aceno, protoˇze hra se nedostane do jeho informaˇcn´ı mnoˇziny. Jedn´ım ze zp˚ usob˚ u, jak zaruˇcit, aby vˇsechna oˇcek´av´an´ı byla rozumn´a“, je uvaˇzovat o tzv. ” dokonale sm´ıˇsen´ ych“ strategi´ıch. D´ıky tomu se v kaˇzd´e informaˇcn´ı mnoˇzinˇe d´a pouˇz´ıt Bayesovo ” pravidlo. Jde ale o hodnˇe siln´ y poˇzadavek—kaˇzd´ y hr´aˇc by takto musel hr´at strategie, kter´e jsou pro nˇej nev´ yhodn´e. M´ısto toho budeme uvaˇzovat jen strategie, ke kter´ ym se lze limitnˇe pˇribl´ıˇzit pomoc´ı takov´ ychto strategi´ı. 13 Bayesovo

pravidlo je

P (B|A)P (A) , P (B) kde P (X) je pravdˇ epodobnost jevu X, P (X|Y ) je podm´ınˇ en´ a pravdˇ epodobnost jevu X za podm´ınky, ˇ ze nastal jev Y. 14 Nesmysln´ e proto, ˇ ze strategie X druh´ eho hr´ aˇ ce je dominantn´ı. P (A|B) =

11

Definice 1.2.38 Kompletnˇe sm´ıˇsen´ a strategie je behavior´ aln´ı strategie, kter´ a pˇriˇrazuje kaˇzd´e ˇcist´e akci v kaˇzd´e informaˇcn´ı mnoˇzinˇe kladnou pravdˇepodobnost. Definice 1.2.39 Dvojce behavior´ aln´ıch strategi´ı a oˇcek´ av´ an´ı (β, µ) je konzistentn´ı pokud existuje posloupnost ((β n , µn ))∞ kter´ a konverguje k (β, µ) a jej´ ıˇ z prvky jsou dokonale sm´ıˇsen´e strategie, n=1 a oˇcek´ av´ an´ı jsou odvozena pomoc´ı Bayesova vzorce.15 Abychom mohli definovat rovnov´ ahu, mus´ıme nejprve definovat jak hr´aˇci porovn´avaj´ı a odhaduj´ı moˇzn´e v´ ysledky. Definice 1.2.40 Definujme funkci pravdˇepodobnostn´ıho rozdˇelen´ı v´ysledku O(β, µ|I) podm´ınˇen´em na dosaˇzen´ı informaˇcn´ı mnoˇziny I, pro danou termin´ aln´ı historii h∗ = (a1 , . . . , aK ) jakoˇzto pravdˇepodobnost´ı distribuci na termin´ aln´ıch histori´ıch za podm´ınky, ˇze bylo dosaˇzeno dan´e informaˇcn´ı mnoˇziny a za dan´ych oˇcek´ av´ an´ı a behavior´ aln´ıch strategi´ı: 1 k k+1 O(β, µ|I)(h∗ ) = µ(I)(h)ΠK−1 ), k=L βP (a1 ,...,ak ) (a , . . . , a )(a

pokud existuje podhistorie h∗ leˇz´ıc´ı v I, a poloˇz´ıme ji rovnu 0 pokud takov´ a podhistorie neexistuje.16 Nyn´ı koneˇcnˇe m˚ uˇzeme pˇristoupit k definici sekvenˇcn´ı racionality. Definice 1.2.41 Dvojce (β, µ) tvoˇr´ı sekvenˇcnˇe racion´ aln´ı rovnov´ ahu, pokud je konzistentn´ı a X X O(β, µ|Ii )(h)ui (h) ≥ O((β−i , βi0 , µ|Ii )(h)ui (h) h∈Z

h∈Z

pro kaˇzdou strategii βi0 a informaˇcn´ı mnoˇzinu Ii ∈ I kaˇzd´eho hr´ aˇce i ∈ N . Pozn´ amka 1.2.42 Lze uk´ azat, ˇze kaˇzd´ a koneˇcn´ a poziˇcn´ı hra m´ a alespoˇ n jednu sekvenˇcnˇe racion´ aln´ı rovnov´ ahu. Pˇ r´ıklad 1.2.43 Naleznˇete sekvenˇcnˇe racion´ aln´ı rovnov´ ahy v pˇr´ıkladu 1.2.31. Pˇ r´ıklad 1.2.44 Naleznˇete sekvenˇcnˇe racion´ aln´ı rovnov´ ahy v n´ asleduj´ıc´ım pˇr´ıkladu 1 C 2/ / • • (1, 1, 1) c

D

d

3  _ _ _ _ _ _ _ _ _ _ _ _ _ _ _3  • FF •F x FF x xx FFF FFR FFR L xxx L xxx FF FF xx xx F F# x x { # {x x (3, 3, 2) (0, 0, 0) (4, 4, 0) (0, 0, 1)

ˇ sen´ı 1.2.45 Pro srovn´ Reˇ an´ı nejprve nalezneme Nashovy rovnov´ ahy. Hraje-li tˇret´ı hr´ aˇc L a druh´y aˇc preferuje hr´ at D. Protoˇze hr´ aˇc c s dostateˇcnˇe vysokou pravdˇepodobnost´ı (alespoˇ n 13 ), pak prvn´ı hr´ se druh´y hr´ aˇc nedostane na tah, jde o Nashovu rovnov´ ahu.17 . Druh´ a skupina Nashov´ych rovnov´ ah je ta, kdy tˇret´ı hr´ aˇc hraje R s velkou pravdˇepodobnost´ı (alespoˇ n 43 ) a druh´y hr´ aˇc pak optim´ alnˇe hraje c a prvn´ı C. V rovnov´ aze tˇret´ı hr´ aˇc nehraje—jeho strategie, tedy jak by hr´ al, kdyby se na tah dostal, je ale podstatn´ a pro to, jak hraj´ı ostatn´ı dva hr´ aˇci. Prvn´ı sada Nashov´ych rovnov´ ah netvoˇr´ı sekvenˇcnˇe racion´ aln´ı rovnov´ ahy, protoˇze strategie druh´eho hr´ aˇce nen´ı optim´ aln´ı. Za podm´ınky dosaˇzen´ı jeho informaˇcn´ı mnoˇziny by pro nˇej bylo optim´ aln´ı 15 Konvergenci je nutnou definovat v pˇ r´ısluˇsn´ em Euklidovsk´ em prostoru, ale form´ aln´ı definici nebudeme d´ ale potˇrebovat, proto ji vynech´ av´ ame. Bayesovo pravidlo je

P (A|B) =

P (B|A)P (A) , P (B)

kde P (X) je pravdˇ epodobnost jevu X, P (X|Y ) je podm´ınˇ en´ a pravdˇ epodobnost jevu X za podm´ınky, ˇ ze nastal jev Y. 16 Pokud informaˇ cn´ı mnoˇ zina I obsahuje jen poˇ c´ ateˇ cn´ı historii, tak O(β, µ|I) definujeme jako pravdˇ epodobnost´ı rozdˇ elen´ı nad termin´ aln´ımi historiemi vznikl´ e t´ım, kdyˇ z kaˇ zd´ y hr´ aˇ c hraje svoji behavior´ aln´ı strategii. 17 Vˇ simnˇ ete si, ˇ ze uvaˇ zujeme behavior´ aln´ı strategie, a tedy jich existuje cel´ a ˇrada—pro vˇsechny hodnoty pravdˇ epodobnost´ı hry akce c mezi 31 a 1.

12

hr´ at d, nikoliv c. Druh´ a skupina NR tvoˇr´ı sekvenˇcnˇe racion´ aln´ı rovnov´ ahy, pokud oˇcek´ av´ an´ı tˇret´ıho hr´ aˇce jsou takov´ a, ˇze se nach´ az´ı v lev´e ˇc´ asti (odpov´ıdaj´ıc´ı historii D) s pravdˇepodobnost´ı 13 . Ovˇeˇrit konsistenci lze pomoc´ı posloupnosti kompletnˇe sm´ıˇsen´ych strategi´ı—staˇc´ı pˇriˇradit strategii D prvn´ıho hr´ aˇce pravdˇepodobnost ε, strategii d druh´eho hr´ aˇce pravdˇepodobnost dvakr´ at vˇetˇs´ı. Strategie tˇret´ıho hr´ aˇce je sm´ıˇsen´ a aˇz na pˇr´ıpad, kdy hraje R s pravdˇepodobnost´ı 1, pak staˇc´ı uv´ aˇzit dokonale sm´ıˇsenou strategii s pravdˇepodobnostmi ε, 1 − ε). Vˇsechny tyto strategie konverguj´ı k poˇzadovan´e rovnov´ aze, jsou dokonale sm´ıˇsen´e a racionalitu oˇcek´ av´ an´ı tˇret´ıho hr´ aˇce lze snadno ovˇeˇrit. Pˇ r´ıklad 1.2.46 Naleznˇete sekvenˇcnˇe racion´ aln´ı rovnov´ ahy v pˇr´ıkladu 1.2.31.

1.3

Opakovan´ e hry

V situaci, kdy hr´ aˇci opakovanˇe hraj´ı tut´eˇz hru, nen´ı pˇredchoz´ı teorie pˇr´ıliˇs praktick´a. Mnoˇzina strategi´ı ˇci histori´ı m˚ uˇze b´ yt velmi snadno nekoneˇcn´a (i nespoˇcetn´a). Pokud jde ale o nekoneˇcn´e opakov´ an´ı t´eˇze hry, probl´em lze pomˇernˇe znaˇcnˇe zjednoduˇsit. Pro zjednoduˇsen´ı se nebudeme zab´ yvat hrami, kter´e se opakuj´ı koneˇcnˇekr´at. I kdyˇz je zˇrejm´e, ˇze vˇetˇsina opakovan´ ych her je nutnˇe koneˇcn´a, toto nen´ı nutnˇe na pˇrek´aˇzku. C´ılem teorie je popis her, kdy hr´ aˇci hry vn´ımaj´ı jako nekoneˇcn´e, tedy neuvaˇzuj´ı o jejich konci a pˇredpokl´adaj´ı, ˇze budou hr´ at d´ ale v dohledn´e budoucnosti. V´ ysledky teorie z´ avisej´ı na tom, jak´ ym zp˚ usobem hr´aˇci uvaˇzuj´ı o budoucnosti, tedy jak porovn´ avaj´ı hodnotu v´ yhry z´ıtra s v´ yhrou dnes. V literatuˇre lze nal´ezt nˇekolik r˚ uzn´ ych metod, kter´e se nav´ıc lehce liˇs´ı ve sv´ ych d˚ usledc´ıch. My se budeme zab´ yvat jen tou nejˇcastˇeji pouˇz´ıvanou a v podstatˇe nejjednoduˇsˇs´ı—(exponenci´ aln´ı) diskontov´an´ı. Pˇri exponenci´ aln´ım diskontov´ an´ı je pˇr´ıjem v n´asleduj´ıc´ım obdob´ı v´aˇzen diskontn´ım faktorem δ ∈ (0, 1). Pro posloupnost strategick´ ych profil˚ u a = (at ) a okamˇzitou uˇzitkovou funkci ui jednoho u.18 hr´ aˇce m˚ uˇzeme definovat uˇzitkovou funkci Ui pro posloupnost akˇcn´ıch profil˚ Ui (a) =

∞ X

ui (at )δ t

t=1

Budeme pˇredpokl´ adat, ˇze tato suma vˇzdy existuje a je koneˇcn´a, coˇz je trivi´aln´ı poˇzadavek pokud ui je ohraniˇcen´ a. Definice 1.3.1 Necht’ G = {N, {Si }, {ui }} je hra v norm´ aln´ı formˇe, S = ×i Si . Hrou s nekoneˇcn´ ym poˇctem opakov´ an´ı naz´yv´ ame poziˇcn´ı hru s dokonalou informac´ı G0 = {N, H, P, {Ui }}, kde t 0 • H = ∪∞ t=0 S , S = {∅}

• P (h) = N pro kaˇzdou netermin´ aln´ı historii h ∈ H • Ui jsou definov´ any pomoc´ı exponenci´ aln´ı diskontov´ an´ı. Historii naz´yv´ ame termin´ aln´ı, tehdy a jen tehdy, je-li nekoneˇcn´ a. Po kaˇzd´e netermin´ aln´ı historii vol´ı kaˇzd´ y hr´aˇc i ∈ N akci z Si . Strategii hr´aˇce tedy tvoˇr´ı pˇredpis akce z Si pro kaˇzdou koneˇcnou posloupnost v´ ysledk˚ u hry G. Na rozd´ıl od koneˇcn´ ych strategick´ ych her, kde Nashov´ ych rovnov´ah bylo relativnˇe m´alo, nebo dokonce neexistovala ˇz´ adn´ a, probl´emem nekoneˇcn´ ych her je velk´e mnoˇzstv´ı rovnov´ah. Uk´aˇzeme, ˇze kaˇzd´ a posloupnost strategick´ y profil˚ u, kter´a kaˇzd´emu hr´aˇci zaruˇcuje v´ıce neˇz jist´ y minim´aln´ı pˇr´ıjem (minimax payoff), je limitnˇe bl´ızk´ y nˇejak´e Nashovˇe rovnov´aze opakovan´e hry. Je intuitivn´ı oˇcek´ avat, ˇze v Nashovˇe rovnov´aze nem˚ uˇze ˇz´adn´ y z hr´aˇc˚ u dos´ahnout menˇs´ıho uˇzitku, neˇz k jak´emu ho mohou donutit ostatn´ı hr´aˇci. Tuto hodnotu oznaˇcujeme za minmax v´ yhru a form´ alnˇe ji definujeme takto: vi = mins−i ∈S−i maxsi ∈Si Ui (s−i , si ) 18 Zat´ ımco ui je uˇ zitkov´ a funkce pˇriˇrazuj´ıc´ı re´ aln´ eˇ c´ıslo jedin´ emu strategick´ emu profilu, funkce Ui pˇriˇrazuje re´ aln´ e ˇ c´ıslo nekoneˇ cn´ e posloupnosti strategick´ ych profil˚ u. Jin´ ymi slovi, ui je okamˇ zit´ y uˇ zitek v jednom opakov´ an´ı hry, Ui je uˇ zitek za vˇsechna opakov´ an´ı.

13

Budeme znaˇcit p−i ∈ S−i nebo t´eˇz p−i (si ) ˇreˇsen´ı tohoto minimalizaˇcn´ıho probl´emu. Pro kaˇzd´e s−i nav´ıc znaˇc´ıme bi (s−i ) nejlepˇs´ı odpovˇed’ na s−i . V´ yhern´ı profil w ve hˇre G0 je vynutiteln´y (enforceable), pokud wi ≥ vi pro vˇsechna i ∈ N . Pokud wi > vi , mluv´ıme o striktn´ı vynutitelnosti.19 N´ asleduj´ıc´ı dvˇe vˇety ukazuj´ı, ˇze kaˇzd´ y striktnˇe vynutiteln´ y profil lze (pˇribliˇznˇe) podpoˇrit Nashovou rovnov´ ahou a ˇze kaˇzd´ a Nashova rovnov´aha definuje vynutiteln´ y profil. Vˇ eta 1.3.2 Pro libovoln´y diskontn´ı faktor δ ∈ (0, 1) a libovolnou hru s nekoneˇcn´ym poˇctem opakov´ an´ı G0 = {N, H, P, {Ui }} plat´ı, ˇze kaˇzd´y v´yhern´ı profil odpov´ıdaj´ıc´ı libovoln´e Nashovˇe rovnov´ aze t´eto nekoneˇcn´e hry je vynutiteln´y. Vˇ eta 1.3.3 Pro kaˇzd´y striktnˇe vynutiteln´y v´yhern´ı profil w hry G0 a kaˇzd´e ε > 0 existuje δ ∈ (0, 1) a v´yhern´ı profil w0 hry G0 takov´y, ˇze |w0 − w| < ε a existuje Nashova rovnov´ aha, pro n´ıˇz je w0 0 v´yhern´ım profilem hry G s nekoneˇcn´ym poˇctem opakov´ an´ı a diskontn´ım faktorem δ. D˚ ukaz prvn´ı vˇety je trivi´ aln´ı a lze jej prov´est sporem. Pokud by totiˇz Nashova rovnov´aha vedla na nevynutiteln´ y v´ yhern´ı profil, pak alespoˇ n jeden hr´aˇc by vydˇel´aval m´enˇe neˇz minmax v´ yhru. Coˇz ale znamen´ a, ˇze by pro nˇej existovalo jednostrann´e vylepˇsen´ı a tedy by nemohlo j´ıt o Nashovu rovnov´ ahu. Druh´ a vˇeta vyuˇz´ıv´ a tzv. trigger strategi´ı. To jsou strategie, ve kter´ ych jakoˇzto reakce na odch´ ylen´ı od rovnov´ ahy urˇcit´ ym hr´ aˇcem je ostatn´ımi hr´aˇci zvolena strategie sniˇzuj´ıc´ı v´ yhru odchyluj´ıc´ıho se hr´ aˇce (jde o potrest´ an´ı). V´ yˇse trestu z´avis´ı na vzd´alenosti v´ yhry v rovnov´aˇzn´e strategii ˇ ım vyˇsˇs´ı je δ, t´ım vˇetˇs´ı v´ahu m´a budoucnost a a minmax v´ yhˇre, ale tak´e na diskontn´ım faktoru. C´ tedy i moˇzn´ y trest a t´ım sn´ aze se zabraˇ nuje hr´aˇc˚ um v odch´ ylen´ı se od rovnov´aˇzn´e strategie. Podobnˇe jako u poziˇcn´ıch her, i zde tyto hrozby nemusej´ı b´ yt vˇerohodn´e, pokud by jejich realizov´ an´ım ostatn´ı hr´ aˇci poˇskozovali sami sebe. Pokud bychom vyˇzadovali, aby strategie byly optim´ aln´ı i ve vˇsech podhr´ ach, z´ısk´ ame t´ım analogickou definici dokonal´e rovnov´ahy vzhledem k podhr´ am (DRVP). Pˇredchoz´ı vˇeta pak plat´ı v n´asleduj´ıc´ı podobˇe: Vˇ eta 1.3.4 Necht’ s∗ je striktnˇe vynutiteln´y strategick´y profil, tedy takov´y profil strategi´ı, kter´emu odpov´ıd´ a striktnˇe vynutiteln´y v´yhern´ı profil w. Pˇredpokl´ adejme, ˇze existuje N striktnˇe vynutiteln´ych strategick´ych profil˚ u (a(i))i∈N takov´ych, ˇze s∗ i a(i) a a(j) i a(i) pro vˇsechna j ∈ N {i}. Pak a existuje doln´ı hranice na diskontn´ı parametr δ takov´y, ˇze pro vˇsechna δ > δ existuje dokonal´ rovnov´ aha vzhledem k podhr´ am hry G0 s nekoneˇcn´ym poˇctem opakov´ an´ı diskontovan´e pomoc´ı δ, kter´ a generuje v´ysledek (st ), takov´y, ˇze st = s∗ , ∀t. Pˇ r´ıklad 1.3.5 Uvaˇzte n´ asleduj´ıc´ı hru v norm´ aln´ı formˇe

Zemˇe 1

V´ alka M´ır

Zemˇe 2 V´ alka (1, 1) (0, 3)

M´ır (3, 0) (2, 2)

V t´eto hˇre jde o dvˇe zemˇe, kter´e spolu mohou v´ alˇcit. Pokud obˇe v´ alˇc´ı, kaˇzd´ a z´ısk´ a uˇzitek 1. Pokud jedna hraje agresivnˇe (V´ alka) a druh´ a m´ırovˇe (M´ır), tak agresor z´ısk´ au ´stupek a uˇzitek 3, druh´ a strana z´ısk´ a 0. Pokud jsou obˇe zemˇe v m´ıru, tak kaˇzd´ a z´ısk´ a 2. Ukaˇzte, ˇze (M´ır,M´ır) nen´ı Nashova rovnov´ aha hry v norm´ aln´ı formˇe. Naleznˇete trigger strategii v hˇre s nekoneˇcn´ym opakov´ an´ım, kter´ a umoˇzn ˇuje, aby se ((M´ır,M´ır)) stal Nashovou rovnov´ ahou t´eto opakovan´e hry. Pro jak´y diskontn´ı faktor je to moˇzn´e? ˇ sen´ı 1.3.6 V t´eto hˇre (bez opakov´ Reˇ an´ı) profil strategi´ı (M´ır,M´ır) nen´ı Nashovou rovnov´ ahou, nebot’ obˇe zemˇe maj´ı moˇznost vylepˇsit sv˚ uj uˇzitek t´ım, ˇze jednostrannˇe pˇrejdou do V´ alky. Uvaˇzme n´ asleduj´ıc´ı strategii ve hˇre s nekoneˇcn´ym poˇctem opakov´ an´ı. Kaˇzd´y hr´ aˇc hraje M´ır, pokud ve vˇsech pˇredchoz´ıch kolech protihr´ aˇc zahr´ al M´ır. V opaˇcn´em pˇr´ıpadˇe hraje V´ alka. V prvn´ım kole hraj´ı oba hr´ aˇci M´ır. Je zˇrejm´e, ˇze pokud oba hr´ aˇci hraj´ı podle t´eto strategie, tak v´ysledkem je neust´ ale (M´ır,M´ır). Je tedy jen nutn´e ovˇeˇrit, ˇze ˇz´ adn´y z hr´ aˇc˚ u si nem˚ uˇze polepˇsit jednostrannou zmˇenou strategie. Protoˇze hra je symetrick´ a, m˚ uˇzeme uvaˇzovat jen Zemi 1. D´ ale je snadn´e si uvˇedomit, ˇze pokud je nˇekdy pro Zemi 1 v´yhodn´e se odch´ylit od dan´e strategie, pak je to v´yhodn´e udˇelat hned v prvn´ım kole. 19 Proˇ c

tento n´ azev bude zˇrejm´ e za chv´ıli. Nˇ ekdy se t´ eˇ z pouˇ z´ıv´ a oznaˇ cen´ı inidividu´ alnˇ e racion´ aln´ı.

14

Pokud se tedy Zemˇe 1 odch´yl´ı v prvn´ım kole a zahraje V´ alka, pak druh´y hr´ aˇc hraj´ıc´ı podle sv´e strategie hraje V´ alka od druh´eho kola aˇz do konce hry. Pak je tedy i pro prvn´ıho hr´ aˇce optim´ aln´ı hr´ at V´ alka od druh´eho kola d´ ale. Mus´ıme nyn´ı spoˇc´ıtat celkov´e uˇzitky hr´ aˇc˚ u pˇri hˇre podle p˚ uvodn´ı a t´eto strategie a zjistit, kter´y je vˇetˇs´ı, v z´ avislosti na diskontn´ım faktoru δ. Pˇri p˚ uvodn´ı strategii je uˇzitek souˇctem n´ asleduj´ıc´ı nekoneˇcn´e ˇradu

U1 (δ)

=

∞ X

2δ i = 2

i=0

U10 (δ)

=

3+

∞ X

1 1−δ

δi = 3 +

i=1

3 − 2δ δ = 1−δ 1−δ

Porovn´ an´ım obou v´yraz˚ u dostaneme, ˇze uveden´ a trigger strategie je Nashovou rovnov´ ahou, pokud 2

1 3 − 2δ > 1−δ 1−δ

A to nast´ av´ a tehdy a jen tehdy, pokud δ > 12 . N´ asleduj´ıc´ı vˇeta znaˇcnˇe zjednoduˇsuje hled´an´ı DRVP, protoˇze m´ısto porovn´an´ı se vˇsemi moˇzn´ ymi alternativn´ımi strategiemi staˇc´ı zkontrolovat, ˇze neexistuje odchylka v jedin´e periodˇe, pro kaˇzd´eho z hr´ aˇc˚ u.20 Vˇ eta 1.3.7 Profil strategi´ı tvoˇr´ı DRVP hry s nekoneˇcn´ym poˇctem opakov´ an´ı hry G tehdy a jen tehdy, kdy neexistuje odchylka v jedin´e periodˇe pro nˇekter´eho z hr´ aˇc˚ u. Pˇ r´ıklad 1.3.8 Ovˇeˇrte, ˇze strategie Oko za oko“ 21 tvoˇr´ı Nashovu rovnov´ ahu pro stejn´e hodnoty ” δ. Pˇ r´ıklad 1.3.9 Spoˇc´ıtejte, pro jak´e diskontn´ı faktory je ve Vˇezˇ novˇe dilematu moˇzn´e doc´ılit spolupr´ ace, tedy opakovanˇe (N,N). ˇ sen´ı 1.3.10 Podobnˇe jako v pˇredchoz´ım ˇreˇsen´em pˇr´ıkladu staˇc´ı spoˇc´ıtat, zda jednor´ Reˇ azov´ a zmˇena strategie vede k lepˇs´ımu v´ysledku

U1 (δ) U10 (δ)

= − =

∞ X

2δ i = −2

i=0 ∞ X

0−

1 1−δ

10δ i = −10

i=1

δ 1−δ

Porovn´ an´ım z´ısk´ ame podm´ınku pro Nashovu rovnov´ ahu δ > 15 .

Reference Binmore, 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. 20 D´ ale

lze napˇr´ıklad uk´ azat, ˇ ze mnoˇ zina moˇ zn´ ych v´ yher v DRVP je uzavˇren´ a. Oko za oko“ je definov´ ana takto. Dan´ y hr´ aˇ c hraje v prvn´ım kole M´ır a pak hraje to, co v pˇredchoz´ım ” kole hr´ al druh´ y hr´ aˇ c. 21 Strategie

15