Martin Reiss
Dynamické a Bayesovské hry, zpětná indukce,
opakované hry
Dynamické hry
Hry, ve kterých se objevují situace , kdy jsou rozhodnutí činěna v
různých časech s tím, že alespň jedno z dřívějších rozhodnutí je
všeobecně známé v době učinění pozdějších rozhodnutí.
Dynamické hry jsou většinou reprezentovány v tzv. rozvětveném
(extenzivním) tvaru.
V extenzivním tvaru hry se zadává:
• seznam hráčů ve hře
• kdy je který hráč na tahu, jaké má hráč možnosti v každé situaci
kdy je na tahu a jaké má hráč informace v každé situaci kdy je na
tahu
• výplata každého hráče při všech možných kombinacích tahů které
mohli hráči zvolit
• Dynamické hry se obvykle znázorňují pomocí herního
stromu.
• Jedná se o graf, který má jediný začátek a neobsahuje
cykly.
• Strom se skládá se z větví a uzlů. Každému uzlu přímo
předchází pouze jeden uzel. Uzly rozdělujeme na
rozhodovací, koncové, předcházející, následující a jeden
počáteční (kořen stromu).
• Každý rozhodovací uzel představuje rozhodovací bod
jednoho z hráčů. Každý koncový uzel obsahuje výplaty
hráčů.
• Jsou zde zachyceny všechny situace, které ve hře mohou
nastat. Každé situaci odpovídá jeden uzel, z každého
uzlu vychází určitý počet hran odpovídajících možným
rozhodnutím daného hráče.
Příklad vezňova dilema v rozvětveném tvaru
Hry s opakováním
• Hráči hrají hru opakovaně.
• Má-li každý hráč přehled o tom, kdo a jak v
minulých kolech z jeho protihráčů hrál
mluvíme pak o hrách s dokonalou informací.
• Pokud jsou mezi hráči známy i strategie a
hodnoty užitkových funkcí protihráčů,
mluvíme o hrách s úplnou informací.
• Dva typy:
• Hra se opakuje s pevným počtem kol, tj.
existuje nějaký bod, do kterého hra dospěje a
ukončí se
• Hra se může opakovat do nekonečna, což
může být interpretováno tak, že hráči hrají
hru, ale neví kdy skončí.
• Základní metodou pro řešení her s pevným
počtem kol je zpětná indukce.
• Při řešení postupujeme od konce hry. Jestliže se
tam hra dostane, pak poslední hráč, který by
mohl být na tahu bude volit takový závěrečný
tah, který mu přinese maximální užitek.
• Hráč, jež je na tahu před ním se pochopitelně
také snaží maximalizovat užitek, ale je si vědom
toho, jak na každý jeho možný tah bude reagovat
hráč po něm, proto svůj tah zvolí s ohledem na
rozhodnutí následujícího hráče.
• Tímto způsobem postupujeme až ke kořenu hry
Příklad: Hlasování o platech
Vězňovo dilema
• Dva podezřelí jsou zatčeni a postaveni před následující
problém: pokud by oba statečně zapírali, putovali by do
vězení na tři roky. Pokud by se jeden z nich přiznal a
udal zároveň toho druhého, dostal by jeden rok,
zatímco druhý by byl odsouzen na 25 let. Pokud by se
doznali oba, byli by posláni do vězení na 10 let.
Opakované vězňovo dilema
• Uskuteční-li se hra jednou a není možné
dopředu uzavřít skutečně závaznou dohodu,
zvolí racionální hráč dominující strategii
„přiznat se“.
• Ocitá-li se však daná dvojice hráčů ve stejné
situaci opakovaně, v nekonečném či neurčitém
časovém horizontu, může být již strategií více.
Příklady strategií v opakovaném
vězňově dilematu
• vždy spolupracuje
• vždy zradí
• nevraživec – spolupracuje, dokud jej protihráč
nezradí, pak navždy zrazuje
• půjčka za oplátku – v prvním tahu
spolupracuje, v dalších opakuje tah protihráče
• naivní pokušitel – jako půjčka za oplátku, ale
občas zradí
= Hry s neúplnou informací
• Neúplná informace - informace, u které někteří hráči
neznají hodnoty výplatních funkcí některých dalších
hráčů.
• Většina reálných situací je s neúplnou informací
Bayesovské hry
Příklad 1.a:
• na trhu působí Firma1, která zvažuje otevření své další pobočky, a Firma2,
která zvažuje vstoupení či nevstoupení na trh
• své strategie zvažují obě firmy současně
• Firma2 si není jistá, jaké jsou náklady Firmy1 na postavení závodu.
Ví pouze, že budou buď vysoké, a to v hodnotě 3 milionů korun, nebo
nízké - pro jednoduchost uvažme nejprve nulové
• hodnota výplatní funkce Firmy2 nezávisí přímo na těchto nákladech, ale
na skutečnosti, zda Firma1 postaví nebo nepostaví nový závod
Pro vysoké náklady
Firma2
Strategie Vstoupit Nevstoupit
Otevřít (0, -1) (2, 0)
Firma1
Neotevřít (2, 1) (3, 0)
Pro nízké náklady
Firma2
Strategie Vstoupit Nevstoupit
Otevřít (3, -1) (5, 0)
Firma1
Neotevřít (2, 1) (3, 0)
 Firma1 má soukromé informace o nákladech na otevření
nové pobočky a je zřejmé, že závod postaví pouze v případě,
když budou náklady nízké.
 Označme:
p........pravděpodobnost, kterou Firma2 přiřadí situaci, kdy jsou náklady Firmy1
vysoké
1-p.....pravděpodobnost, kterou Firma2 přiřadí situaci, kdy jsou náklady Firmy1
nízké
Firma2 je postavena před loterii:
1) S pravděpodobností p jsou výplatní funkce dány první dvojmaticí a Firma2 na
trh nevstoupí.
2) S pravděpodobností 1-p jsou výplatní funkce dány druhou dvojmaticí a
Firma2 na trh vstoupí.
Jestliže Firma2 na trh vstoupí, pak s pravděpodobností p bude její výplatní
funkce 1 milion. S pravděpodobností 1-p to bude -1 milion.
Očekávaná výplatní hodnota pro Firmu2 je
1p+(-1)(1-p)=2p-1.
Firmě2 se vyplatí vstoupit na trh, pokud bude výplatní hodnota kladná, tj.
p>0,5. Pokud Firma2 na trh nevstoupí, pak bude její výplatní hodnota
v každém případě nulová.
Příklad 1.b:
Nyní předpokládejme, že nízké náklady nejsou nulové, ale 1,5
milionu. Pro tyto nízké náklady jsou potom hodnoty výplatních
funkcí následující:
Firma2
Strategie Vstoupit Nevstoupit
Otevřít (1.5, -1) (3.5, 0)
Firma1
Neotevřít (2, 1) (3, 0)
Optimální strategie Firmy1 nyní závisí na odhadu, co bude dělat Firma2.
Označme:
q........pravděpodobnost, kterou Firma1 přiřadí skutečnosti, že Firma2
vstoupí na trh
1-q......pravděpodobnost, kterou Firma1 přiřadí skutečnosti, že Firma2
nevstoupí na trh
Firmě1 se pak vyplatí otevřít pobočku, bude-li platit:
1,5q+3,5(1-q) > 2q+3(1-q)
tedy q<0,5
Firma1 se tedy musí pokusit odhadnout chování Firmy2, aby mohla vybrat svoji
vlastní strategii.
Firma2 nemůže odhadnout strategii Firmy1 jen z její znalosti výplatních funkcí.
Shrňme dosavadní výsledky:
Firma1:
 při vysokých nákladech nepostaví nový závod
 při nízkých nákladech
- postaví nový závod, jestliže q<0,5
- nepostaví nový závod, jestliže q>0,5
Firma2:
 q=1 (vstoupí na trh), pokud p>0,5
 q=0 (nevstoupí na trh), pokud p<0,5
 q náleží do (0,1), pokud p=0,5

Situace s neúplnou informací zvyšuje nutnost
uvažování názoru hráče na preference ostatních hráčů,
jeho názory, jeho názory na názory ostatních o jeho
preferencích, jeho názory o jeho názorech o jeho
názorech o jeho preferencích, atd. A takto se spustí
cyklický systém názorů. Tento postup se zdá být
neschůdný.
J. Harsanyi vyvinul metodu, jak transformovat hry s neúplnými informacemi
(bayesiánské hry) na hry s úplnými informacemi, které pak mohou být
analyzovány s pomocí standardních nástrojů.
John Harsanyi tvrdí, že i ty hry, kde účastníkům chybějí znalosti o strategii
soupeřů, mohou být analyzovány takřka stejně jako hry normální. Výhody
samozřejmě získává ten hráč, který na rozdíl od svých rivalů disponuje
potřebnými informacemi.
Způsob, jak modelovat a pochopit tuto situaci bez
nekonečného cyklického systému názorů vyvinul v 60.
letech 20. století držitel Nobelovy ceny za ekonomii
profesor John C. Harsanyi (1920-2000).
Odstranil hlavní nedostatek konceptu Nashovy
rovnováhy, spočívající v předpokladu, že jednotliví
účastníci hry mají úplné informace o preferencích
ostatních hráčů.
Navrhl zavést tah fiktivního hráče nazvaného Příroda, který
určuje tzv. typ každého hráče. V našem příkladě to byly
náklady na postavení závodu (vysoké, nízké). Každý hráč zná
svůj typ a všechny možné typy ostatních hráčů (spolu
s příslušnými pravděpodobnostmi), což znamená, že hra je
nyní hrou s úplnou, ale nejistou, informací. Všichni hráči znají
všechny možné výplatní hodnoty všech typů všech hráčů, ale
ne všichni zjistí tah fiktivního hráče nazvaného Příroda.
Standardním předpokladem je skutečnost, kdy všichni hráči
mají stejné názory na pravděpodobnostní rozdělení tahu
Přírody. Dostáváme tedy Hru s úplnou, ale nejistou informací,
na kterou může být použita koncepce Nashovy rovnováhy.
Definice:
Bayesovská hra H je určena:
1. Množinou hráčů: {1,2,...,N}
2. Množinou prostorů strategií: {X1, X2..., XN}
Zde Xi označuje prostor strategií i-tého hráče. Konkrétní strategie
budeme dále značit x1, x2, ..., xN.
3. Množinami prostorů typů hráčů: {T1, T2..., TN}.
Typ ti náležící do Ti odpovídá určité výplatní funkci, kterou může mít hráč i.
Hráč i zná svůj typ, ale nezná typy ostatních hráčů.
4. Množinou názorů hráčů: {p1, p2..., pN}.
pi představuje názor hráče i, který má o typech dalších hráčů
5. Množinou výplatních funkcí všech hráčů:
{f1(x1,...,xN, t1,...,tN),...fN(x1,...,xN, t1,...,tN)}.
Abychom mohli použít Harsanyiovu koncepci,
budeme reformulovat hru s neúplnou informací
následovně:
 budeme považovat každý typ každého hráče za samotného hráče
 budeme předpokládat, že Příroda náhodně vybere ty hráče, kteří
budou hru skutečně hrát
 každý typ každého hráče musí vybrat svoji strategii dříve než
udělá svůj první tah Příroda
Definice:
Rozšířená Bayesovská hra H* je určena:
1. Množinou hráčů: {1, 2, ..., M}
kde M = ∑ ‫׀‬Ti‫׀‬
hráč j=(i,ti)
2. Množinou prostorů strategií: {Y1, Y2..., YM}
3. Množinou výplatních funkcí všech hráčů:
{g1(y1, . . . , yM), . . . gM(y1, . . . , yM)}
Definice: (Bayesova-Nashova rovnováha)
Bayesova-Nashova rovnováha ve hře s neúplnou
informací H je Nashova rovnováha ve hře
s nejistou informací H*, která je reprezentací
původní hry H.
Věta:
Každá konečná hra s neúplnou informací má
alespoň jedno Bayesovo-Nashovo rovnovážné
řešení.
Pokračování příkladu 1.b:
Označme:
VN............vysoké náklady
NN............nízké náklady
OT............otevřít novou pobočku
NEOT........neotevřít novou pobočku
VST...........vstoupit na trh
NEVST.......nevstoupit na trh
Z...............zvažovat vstup
H: H*:
Hráči a typy:
{1, 2}, T1={VN, NN}, T2={Z} {1, 2, 3}={(1, VN), (1, NN), (2, Z)}
Strategie:
X1={OT, NEOT}, X2={VST, NEVST} Y1=Y2=X1={OT, NEOT},
Y3=X2={VST, NEVST}
Názory a výplatní funkce:
p(VN)=p, p(NN)=1-p g1(y1,y2,y3) = f1(x1,x2,VN)
fi(x1,x2,VN), fi(x1,x2,NN) g2(y1,y2,y3) = f1(x1,x2,NN)
g3(y1,y2,y3) = pf2(x1,x2,VN)+(1−p)f2(x1,x2,NN)
Označme:
pot.......pravděpodobnost, že hráč (1, NN) otevře novou pobočku
1-pot....pravděpodobnost, že hráč (1, NN) neotevře novou pobočku
q........pravděpodobnost, že hráč (2, Z) vstoupí na trh
1-q......pravděpodobnost, že hráč (2, Z) nevstoupí na trh
Přistupme nyní k samotnému hledání Nashovy rovnováhy této
hry s nejistou informací:
(1, VN):
(2, Z)
Strategie VST (q) NEVST (1 - q)
OT (pot) (0 , -1) (2, 0)
(1, VN)
NEOT (1 - pot) (2, 1) (3, 0)
Je jasně vidět, že hráč (1, VN) má dominantní strategii NEOT, tedy
Firma1 nebude při vysokých nákladech pobočku otvírat.
(1, NN):
(2, Z)
Strategie VST (q) NEVST (1 - q)
OT (pot) (1.5 , -1) (3.5, 0)
(1, NN)
NEOT (1 - pot) (2, 1) (3, 0)
pot = 1...... očekávaná výhra: 1.5q+3.5(1-q) = 3.5-2q
pot = 0...... očekávaná výhra: 2q+3(1-q) = 3-q
3.5-2q = 3-q
q = 0.5
Tedy nejlepší odezva pro hráče (1, NN) je:
1 pro q < 0.5
pot = 0 pro q > 0.5
(0,1) pro q = 0.5
(2, Z):
(2, Z)
Strategie VST (q) NEVST (1 - q)
POST (pot) (1.5 , -1) (3.5, 0)
(1, NN)
NEPOST (1 - pot) (2, 1) (3, 0)
očekávaná výhra pro VST:
1.p + (1−p) [pot(−1)+1(1− pot)] = 1−2pot(1−p)
očekávaná výhra pro NEVST:
0.p + (1−p) [pot0+(1−pot)0] = 0
1−2pot(1−p) = 0
pot = 1 / [2(1-p)]
Tedy nejlepší odezva pro hráče (2, Z) je:
1 pro pot < 1 / [2(1-p)]
q = 0 pro pot > 1 / [2(1-p)]
(0,1) pro pot = 1 / [2(1-p)]
Rovnovážné strategie:
Rovnovážné strategie zapíšeme ve tvaru vektoru:
(Strategie pro Firmu1 s VN, Strategie pro Firmu1 s NN, Strategie pro Firmu 2)
1) Pro p < ½ dostáváme:
(NEOT, NEOT, VST);
(NEOT, OT, NEVST);
(NEOT, OT s pot = 1 / [2(1-p)], VST s q = ½)
2) Pro p > ½ dostáváme:
(NEOT, NEOT, VST)
Děkuji za pozornost