Dynamic Games (Extensive Form Games)

THE: Dymické hry s úplnou informac´ı Dynamic Games (Extensive Form Games) Martin Hrubý Brno University of Technology Brno Czech Republic

November 1, 2013

Martin Hrub´ y

Dynamick´ e hry s u ´plnou informac´ı

Motivace ke zkoumán´ı her Zpátky na zaˇcátek. Je tˇreba se vyrovnat s tˇemito fakty: ◮ TH se snaˇ z´ı studovat motivace v jedn´ an´ı lid´ı, jejich preference a moˇzné akce. Predikce jejich chov´ an´ı je aˇz sekundárn´ı. ◮ NE je koncept chov´ an´ı, který je univerz´ alnˇe platný. TH z nˇeho vycház´ı v dalˇs´ıch zkoum´ an´ıch. Nekooperativn´ı hry s nenulovým souˇctem jsou z´ aklad strategických model˚ u (jsou dalˇs´ı aplikace). ◮ Existuj´ ı otázky nad smyslem MNE a jeho ˇreˇsen´ım. ◮ Existuj´ ı lidé, kteˇr´ı nad MNE definuj´ı své problémy. Jin´ı lidé se soustˇred´ı na výpoˇcet MNE. ◮ MNE je algoritmicky t´ emˇeˇr neˇreˇsitelný problém. Kamal Jain (Microsoft research): ”Kdyˇz tv˚ uj notebook nenajde ˇreˇsen´ı nˇejaké situace na trhu, nenajde ho ani trh”. Pokud trh funguje, mus´ı pro nˇej existovat i jeho simulaˇcn´ı model. Tuˇs´ıme, ˇze nˇekde mus´ı existovat ten algoritmus, ale st´ ale ho hledáme. Zat´ım prezentujeme dosaˇzené výsledky. Martin Hrub´ y


Demo: dopravn´ı model Jet do práce cestou a nebo b? Kdyˇz pojedou stejnou, cestovn´ı doba se protáhne. Petr/Jan a b

a -10,-10 -1,-5

b -5,-1 -20,-20

PNE = {(a, b), (b, a)}, MNE = (( 85 , 38 ), ( 58 , 38 )), π(MNE ) = −8.125 Jak interpretovat dvˇe moˇzn´ a PNE? Jak Petr pˇresvˇedˇc´ı Jana k (b, a)? Kooperace.

Martin Hrub´ y


Motivace ke zkoumán´ı her ◮

◮

Ukáˇzeme si dalˇs´ı koncepty NE, tzv. refinements (zpˇresnˇen´ı), ale i zobecnˇen´ı. Univerzáln´ı ˇreˇsen´ı výpoˇctu MNE neexistuje, ukazujeme principy. ◮

◮

◮ ◮

Metody a nástroje pro nalezen´ı ”vˇsech” ekvilibri´ı jsou podezˇrelé. Obvykle pracuj´ı ve vymezené skupinˇe her.

Program gambit. MNE je jednoznaˇcnˇe definovaný koncept. Hledáme jeho algoritmické ˇreˇsen´ı.

Reálné modely zaloˇzené na TH: ◮ ◮

◮

Obecnˇe je TH vn´ım´ ano jako ”vˇeda, do které málokdo vid´ı”. Reálných model˚ u je m´ alo. Ovˇsem nen´ı ˇspatné se nauˇcit takto modelovat. Rozbor jednoho re´ alného modelu bude pod´ an koncem semestru. Martin Hrub´ y


ˇ sen´ı reálných model˚ Reˇ u ◮

Máme reálnou situaci a chceme napsat jej´ı (napˇr. poˇc´ıtaˇcový) model. Napˇr´ıklad proto, ˇze ho nˇekdo chce.

◮

Stanov´ıme hráˇce, strategie, preference, uˇzitky a hledáme ˇreˇsen´ı.

◮

Jistˇe se v urˇcitém okamˇziku dostaneme do stavu, kdy nˇejakou formu ekvilibria mus´ıme vypoˇc´ıtat.

◮

Disponujeme obecnými hernˇe-teoretickými principy: dominance, best-response, ekvivalence her.

◮

Pokud je hra velk´ a, mus´ı existovat metody jej´ı redukce na menˇs´ı (ménˇe strategi´ı, ménˇe strategických hr´ aˇc˚ u).

◮

Pokud hledáme ˇreˇsen´ı, je v heuristik´ ach. Je to obecný postup v UI: generovat stavový prostor a v nˇem hledat ˇreˇsen´ı. V pˇr´ıliˇs velkém stavovém prostoru hled´ ame heuristiky, které nám prostor redukuj´ı. Martin Hrub´ y


´ Dneˇsn´ı téma: sekvenˇcn´ı hry. Uvod ˇ ano z: Cerp´ ◮

Myerson, R. B.: Game theory: Analysis of Conflict, Harvard University Press, 2004

◮

Osborne, M., Rubinstein, A.: A Course in Game Theory, MIT Press

◮

Rasmunsen, E.: Games and Information: An Introduction to Game Theory, Blackwell Publishing, 2007

◮

McCarthy, N., Mierowitz, A.: Political Game Theory, Cambridge University Press, 2007

◮

Basar, T., Olsder, G.J.: Dynamic Noncooperative Game Theory , Society For Industrial And Applied Mathematics, 1999

◮

Magdaléna Hykˇsov´ a: Pˇredn´ aˇsky z teorie her, Fakulta dopravn´ı ˇ CVUT Martin Hrub´ y


Pˇripomenut´ı statických her Hry v normáln´ı formˇe (statické hry). ◮

Hráˇc strategicky promýˇsl´ı moˇzné tahy svoje a protivn´ıka.

◮

Asi by mu hodnˇe usnadnilo pˇremýˇslen´ı, kdyby vˇedˇel, co protivn´ık bude táhnout.

◮

Kdyby se mu podaˇrilo (tajnˇe) vyzvˇedˇet (v ˇcase libovolnˇe bl´ızkém uzávˇerce rozhodov´ an´ı), co protihr´ aˇc odevzdal za rozhodnut´ı tomu pomyslenému nez´ avislému arbitrovi, tak táhne velmi efektivnˇe.

◮

Ve statických hrách toto nepˇripouˇst´ıme.

V sekvenˇcn´ıch hrách pˇredpokl´ ad´ ame, ˇze se hr´ aˇci stˇr´ıdaj´ı v taz´ıch a tuto skuteˇcnost si uvˇedomuj´ı. Pˇresnˇejˇs´ı n´ azev je ovˇsem hry v rozˇs´ıˇrené formˇe – rozˇs´ıˇren´ı nen´ı pouze v sekvenˇcnosti.

Martin Hrub´ y


Stackelberg˚ uv model duopolu/oligopolu Heinrich Freiherr von Stackelberg: Market Structure and Equilibrium (Marktform und Gleichgewicht) in 1934 ◮

◮

◮

◮

◮

◮

Bertrand˚ uv a Cournot˚ uv model pˇredpokl´ ad´ a normáln´ı pˇr´ıstup ke hˇre. Hráˇci jsou (pˇribliˇznˇe) stejnˇe siln´ı. Tento pˇredpoklad neodpov´ıd´ a mnohým re´ alným situac´ım s jedn´ım extrémnˇe silným hr´ aˇcem (v˚ udcem, leader) a skupinou slabˇs´ıch hráˇc˚ u (následovn´ık˚ u, followers). Stále doufáme, ˇze vˇsichni hr´ aˇci jsou svým rozhodnut´ım schopni ovlivnit cenu produktu (tzn. nen´ı to monopol). Vznikaj´ı ovˇsem dvˇe role a dvˇe podoby (odliˇsného) chován´ı: v˚ udce a následovn´ıci. V˚ udce: je si vˇedom svého postaven´ı. V´ı, ˇze následovn´ıci se budou inspirovat jeho rozhodnut´ım. Následovn´ıci: ˇcekaj´ı na rozhodnut´ı v˚ udce, pak se pˇrizp˚ usob´ı.

Z principu tohoto rozloˇzen´ı sil neprobˇehne hra v jednom tahu, ale ve dvou. Martin Hrub´ y


Stackelberg˚ uv model oligopolu Pˇr´ıklady ze ˇzivota: ◮

◮

◮

Pˇredpoklad: pohybujeme se v systému s nedokonalou konkurenc´ı. ˇ CEZ ˇ Výroba silové elektˇriny v CR: – v˚ udce, IPP (Independent Power Producers) – n´ asledovn´ıci. ˇ IPP ˇcekaj´ı na cenové rozhodnut´ı CEZu, pak nastav´ı cenu za MWh o tˇri CZK niˇzˇs´ı.

◮

IPP tud´ıˇz svou produkci vˇzdy prodaj´ı (o 3 CZK/MWh levnˇeji).

◮

V˚ udce si tuto skuteˇcnost uvˇedomuje a zahrnuje ji do svého rozhodován´ı.

R˚ uzné pˇr´ıstupy v situac´ıch, kdy je n´ asledovn´ık˚ u v´ıce (v´ıcehráˇcovo Stackelbergovo ekvilibrium, ...).

Martin Hrub´ y


Princip zpˇetné indukce, zat´ım neformálnˇe Backward induction. ◮

◮

V˚ udce tedy nem˚ uˇze nechat vyp˚ usobit n´ asledovn´ıky a pak se rozhodnout (oni pr´ avˇe ˇcekaj´ı na jeho tah). V˚ udce experimentuje s moˇznou reakc´ı n´ asledovn´ık˚ u a hledá strategii, která mu pˇrinese maxim´ aln´ı zisk ◮ ◮ ◮

◮

Ta strategická ´ uvaha je na v˚ udci. Následovn´ıci pouze zareaguj´ı na tah v˚ udce. Pˇredpokládáme (i v˚ udce pˇredpokládá), ˇze následovn´ıci potáhnou BR.

Zpˇetná indukce vede k NE, je to ovˇsem podmnoˇzina moˇzných PNE, kde nejsou zahrnuty iracion´ aln´ı varianty (hrozby).

Pozn.: M˚ uˇzeme zavést komplikovanˇejˇs´ı chov´ an´ı, jako napˇr´ıklad systém v˚ udce versus oligopolistické chov´ an´ı n´ asledovn´ık˚ u. Pozn.: Taková perliˇcka - Unexpected hanging paradox. Martin Hrub´ y


Stackelberg˚ uv model oligopolu: design modelu Model je v mnoˇzstevn´ıch strategi´ıch. Firma 1 zvol´ı mnoˇzstv´ı q1 ≥ 0, Firma 2 to sleduje, zhodnot´ı a vol´ı q2 ≥ 0. Výplata firmy i je pak urˇcena ui (qi , qj ) = qi [P(q) − c] kde P(q) = M − q, q = q1 + q2 . c jsou výrobn´ı náklady; P(q) je cena na trhu pˇri dodaném mnoˇzstv´ı q. R1 , R2 budou rozhodnut´ı firem o mnoˇzstevn´ı strategii.

Martin Hrub´ y


Zopakujme ui (qi , qj ) = qi [P(q) − c]. Backwards-induction: R2 (q1 ) : max u2 (q1 , q2 ) = max q2 [M − q1 − q2 − c] q2 ≥0

q2 ≥0

Hledáme tedy maximum funkce s promˇennou q2 . Matematická analýza: vyˇsetˇrován´ı extrém˚ u funkc´ı. Hledáme extrém: ∂f∂q(q22 ) ; f (q2 ) = q2 M − q2 q1 − q22 − cq2 Bod extrému: M − q1 − 2q2 − c = 0 M − q1 − c ; q1 < M − c 2 R2 (q1 ) je analyticky vyj´ adˇrené mnoˇzstevn´ı rozhodnut´ı následovn´ıka vztaˇzené k rozhodnut´ı v˚ udce. V˚ udce v´ı, ˇze takto se rozhodne následovn´ık a s t´ımto vˇedom´ım vol´ı jeho optim´ aln´ı strategii. q2 = R2 (q1 ) =

Martin Hrub´ y


[q1 ≥ 0] max u1 (q1 , R2 (q1 )) =

max q1 [M − q1 − R2 (q1 ) − c] max q1 (M − q1 − c)/2 1 1 1 f (q1 ) = q1 M − q12 − q1 c 2 2 2 1 1 1 M − 2 q1 − c = 0 2 2 2 M − 2q1 − c = 0

M −c M −c ; q2∗ = R2 (q1∗ ) = 2 4 M−c M−c ∗ ∗ ∗ . Ekvilibrium je q = (q1 , q2 ) = 2 , 4 q1∗ =

Pokud tedy v˚ udce dod´ a na trh jiné (napˇr. vˇetˇs´ı) mnoˇzstv´ı neˇz M−c 2 , rozhodnˇe jeho zisk bude niˇzˇs´ı. Jako dom´ ac´ı cviˇcen´ı toto provˇeˇrte. To samé plat´ı pro následovn´ıka. N´ asledovn´ık ovˇsem má vˇzdy moˇznost volit BR a tuto volbu t´ ahnout. Martin Hrub´ y


Modely oligopolu Známe jiˇz tˇri pohledy na vˇec: ◮

Cournot – oligopol v mnoˇzstevn´ıch strategi´ıch, statická hra.

◮

Bertrand – oligopol v cenových strategi´ıch, statická hra.

◮

Stackelberg – oligopol v mnoˇzstevn´ıch strategi´ıch, sekvenˇcn´ı hra.

Tyto modely jsou common knowledge pro kaˇzdého hern´ıho teoretika. Dnes v´ıme, ˇze se hráˇci nenechaj´ı strhnout k cenové hˇre, která m˚ uˇze vést k cenové válce. Po cenové v´ alce je totiˇz rozloˇzen´ı vlivu na trhu pˇribliˇznˇe podobné, jako na zaˇc´ atku, pouze hráˇci ménˇe trˇz´ı.

Martin Hrub´ y


Princip zpˇetné indukce Pedro/Juana Opera Fotbal

Opera 3,2 0,0

Fotbal 0,0 2,3

Pedro táhne prvn´ı. V´ı, ˇze Juana zvol´ı BR. Proto se pod´ıvá, co by byly ty BR (Oo, Ff). Z moˇznost´ı (Oo,Ff) vol´ı Oo. ˇ ım to, ˇze je tu naprosto jasné unik´ C´ atn´ı PNE? Martin Hrub´ y


Poˇrad´ı tah˚ u Je výhodné táhnout prvn´ı? Pˇr´ıklad s poslanci: Poslanci chtˇej´ı odhlasovat z´ akon o zvýˇsen´ı svých plat˚ u. Zvýˇsen´ı pˇrinese kaˇzdému poslanci individu´ aln´ı uˇzitek b ≥ 0, ovˇsem poslanec hlasuj´ıc´ı ”pro” sn´ıˇz´ı u vˇeˇrejnosti svou popularitu, coˇz odpov´ıdá ztrátˇe c ≥ 0 (naˇstˇest´ı b > c). Poslanci jsou tˇri, k odhlasován´ı zákona potˇrebujeme dva hlasy pro. K hlasován´ı pˇristupuj´ı sekvenˇcnˇe a hlasov´ an´ı je veˇrejné. Kdo p˚ ujde prvn´ı? ◮

ˇ ek bez znalosti THE by se moˇzn´ Clovˇ a ostýchal jako prvn´ı hlasovat o tak choulostivé vˇeci veˇrejnˇe.

◮

Je evidentn´ı, ˇze z´ akon projde.

◮

Pokud budu m´ıt to ˇstˇest´ı, ˇze budu moci j´ıt hlasovat prvn´ı, radostnˇe budu hlasovat ”proti” s pˇrid´ an´ım nˇejaké zásadn´ı ˇreˇci o nestoudných mzdových poˇzadavc´ıch nˇekterých poslanc˚ u. Martin Hrub´ y


Poˇrad´ı tah˚ u

Martin Hrub´ y


Studie v diskrétn´ıch strategi´ıch Mˇejme kolonii K a imperialistu I . Kolonie m´ a na svém u ´zem´ı ropný vrt, který nese 4 jednotky zisku. Nav´ıc kolonie plat´ı 2 jednotky dan´ı imperialistovi. ◮

Kolonie má strategie SK = {R, C }, revoltovat (R) nebo pokraˇcovat v poddanstv´ı (C).

◮

V pˇr´ıpadˇe, ˇze kolonie bude revoltovat, imperialista m˚ uˇze povolit kolonii nez´ avislost (G) nebo revoluci potlaˇcit (S) – zp˚ usobil by válku.

◮

V pˇr´ıpadˇe, ˇze kolonie bude posluˇsnˇe pokraˇcovat, imperialista m˚ uˇze vyb´ırat danˇe (T) nebo zruˇsit danˇe (E). p ∈ h0, 1i nechˇt je pravdˇepodobnost, ˇze by kolonie vyhrála válku za nezávislost.

◮

Martin Hrub´ y


Studie: kolonie versus imperialista

Uˇzitek ve hˇre: ◮

Ropa nese zisk 4 jednotky (tzn. 0 tomu druhému).

◮

Revoluce stoj´ı 1, pokud imperialista nezakroˇc´ı, jinak obˇe strany stoj´ı 6 (válka).

◮

Danˇe nesou 2 jednotky imperialistovi (tzn. -2 kolonii).

Studujme zat´ım situaci formou statické hry. Imperialista m´ a dvˇe sub-rozhodnut´ı, které v r´ amci strategie ve statické hˇre mus´ıme slouˇcit: {G , S} × {T , E } = {GT , GE , ST , SE }.

Martin Hrub´ y


Studie: kolonie versus imperialista K/I R

GT 3, 0

GE 3, 0

C

−2, 6

0, 4

ST −6 + 4p − 2(1 − p), −6 + 6(1 − p) −2, 6

SE −6 + 4p, −6 + 4(1 − p) 0, 4

Strategický rozbor situace, pro r˚ uzn´ a p: K/I p = 0 R C K/I p = 1 R C

GT 3, 0 −2, 6 GT 3, 0 −2, 6

GE 3, 0 0, 4 GE 3, 0 0, 4

ST −8, 0 −2, 6 ST −2, −6 −2, 6

SE −6, −2 0, 4 SE −2, −6 0, 4

Se zvyˇsuj´ıc´ım se p se evidentnˇe zvˇetˇsuje nutk´ an´ı (incentive) kolonie k rebelii (a souˇcasnˇe imperialista racionalnˇe vol´ı podporu nezávislosti). Martin Hrub´ y


Kolonie versus imperialista: Dynamický pˇr´ıstup Statický pˇr´ıstup nen´ı pˇrirozený (navrhuje ekvilibria, která jsou sekvenˇcnˇe iracionáln´ı). Hru velmi dobˇre rozhodne sekvenˇcn´ı pˇr´ıstup. K R-revolta C-pokracuje I

I

G-nezavis. S-potlaceni 3,0

4p-6-2(1-p),6(1-p)-6

Martin Hrub´ y

T-dane -2,6

E-zrusit-dane 0,4


Kolonie versus imperialista: Dynamický pˇr´ıstup p=0

p=

K R

G 3,0

1 2

K C

R

I

I

S

T

-8,0

-2,6

E

I

I

S

T

-5,-3

-2,6

G 0,4

3,0

C

E

K R

G

p=1

3,0

Martin Hrub´ y

C

I

I

S

T

-2,-6

-2,6

E 0,4


0,4

D˚ uveryhodná/ned˚ uveryhodná hrozba Credible/Incredible threat. Uvaˇzujme situaci, kdy hr´ aˇc A pˇrijde k hr´ aˇci B s t´ım, ˇze má bombu a pokud mu B nedá jistý obnos (nem´ a smysl zkoumat jeho výˇsi), tak bombu odpál´ı (zp˚ usob´ı smrt A i B). Hráˇc B oˇcekává u A racionalitu a zkoum´ a, zda-li je hrozba ”odpálit” d˚ uvˇeryhodná. Oˇcek´ av´ a, ˇze A je racion´ aln´ı (dá pˇrednost ˇzivotu). Pak nemá smysl hr´ at strategii ”Odevzdat”. Paradoxnˇe, vˇetˇsina lid´ı vˇsak pen´ıze zaplat´ı. Hráˇc zkoumá, zda-li m´ a racion´ alnˇe zahrnout hrozbu protivn´ıka do svého rozhodován´ı (stále pˇredpokl´ ad´ a racionalitu protivn´ıka). Ned˚ uvˇeryhodnou hrozbu hr´ aˇc ohlaˇsuje (signalizuje), pokud doufá, ˇze ji nebude muset naplnit. Aby se hrozba stala d˚ uvˇeryhodnout, hráˇc mnohdy sobˇe zp˚ usob´ı ˇskodu (p´ alen´ı lod´ı). Martin Hrub´ y


D˚ uveryhodná/ned˚ uveryhodná hrozba

A/B top bottom

left 2,1 1,2

right 0,0 1,2

◮

PNE: (top,left), (bottom, right)

◮

Ikdyˇz je right slabˇe dominovan´ a strategi´ı left, pˇresto nen´ı iracionáln´ı. Tvoˇr´ı hrozbu.

◮

Mus´ı se vˇsak A ob´ avat right?

◮

Ve statické hˇre sloupcový vol´ı left.

◮

Sekvenˇcn´ı chován´ı m˚ uˇze potlaˇcit vliv hrozby.

Martin Hrub´ y


Informace ve hˇre ◮

◮

◮ ◮

Hry s u ´plnou/ne´ uplnou informac´ı (complete/incomplete) – hráˇc˚ um je známa/nezn´ ama struktura hry (hr´ aˇci, strategie, zisky). Hry s dokonalou/nedokonalou informac´ı (perfect/imperfect) – hráˇc˚ um je známa historie hry. Nás budou zaj´ımat hry s u ´plnou informac´ı. Dále budeme zkoumat perfektnost/imperfektnost informace.

Hry proti pˇr´ırodˇe – prvn´ı tah m´ a pˇr´ıroda (zdroj nedokonalosti v informaci). Historie znamená informaci o aktu´ aln´ım uzlu ve stromu hry. Pokud je znalost uzlu jistá (informaˇcn´ı mnoˇzina je jednoprvková – singleton), pak je perfektn´ı informace. Nejistotu modelujeme v´ıceprvkovou informaˇcn´ı mnoˇzinou. Perfect recall – hráˇc je schopen si pamatovat vlastn´ı tahy. Martin Hrub´ y


Informace ve hˇre - hra s nedokonalou informac´ı Prázdné koleˇcko uprostˇred, prvn´ı t´ ahne pˇr´ıroda a vol´ı typ hráˇce 1.

Martin Hrub´ y


Definice sekvenˇcn´ı hry (Extensive Form Game) Definition Koneˇcná sekvenˇcn´ı hra s perfektn´ı informac´ı ΓE je ˇctveˇrice (Q, H, p, U), kde: ◮ ◮

◮

◮

Q je mnoˇzina hráˇc˚ u, H je mnoˇzina histori´ı (kontext˚ u, uzl˚ u). H T oznaˇcuje mnoˇzinu 0 termináln´ıch histori´ı. H = ∅ oznaˇcuje poˇc´ ateˇcn´ı uzel. p(h) : H \ H T → Q pˇriˇrazuje kaˇzdé netermin´ aln´ı historii h hráˇce, který je aktu´ alnˇe na tahu. U je vektor uˇzitkových funkc´ı Ui (h) : H T → R1 pro vˇsechny i ∈ Q.

Pozn.: Mininum pro definici hry s perfektn´ı informac´ı je (Q, H, p). Pozn.: Zavedeme: A(h) je mnoˇzina akc´ı pro kaˇzdé h ∈ H \ H T , tzn. mnoˇzina proveditelných akc´ı po dosaˇzen´ı historie h. Martin Hrub´ y


Co je ta historie? Budeme cht´ıt vyjádˇrit, ˇze hr´ aˇc nev´ı, v jakém stavu (uzlu) stromu je. ◮

Historie h ∈ H je sekvence akc´ı (ak )k=1,... , kde kaˇzdá akce aj pˇredstavuje tah hr´ aˇce

◮

Prázdná sekvence je H 0 , poˇc´ atek hry.

◮

Je-li (ak )k=1,...,K ∈ H (K ∈ N) a L < K , pak (ak )k=1,...,L ∈ H.

◮

Kaˇzdý prvek h ∈ H se nazýv´ a historie, kaˇzd´ a sloˇzka h se nazývá akce.

Mnoˇzina H dává pˇredstavu o zp˚ usobu hran´ı hry, je to mnoˇzina vˇsech cest od poˇcátku k libovolnému uzlu stromu hry. Pˇredpokládáme tedy, ˇze v h = (ak )k=1,...,K , j ∈ {1, ..., K } táhl v j-tém okamˇziku hráˇc p(h′ ) akci aj , kde h′ = (ak )k=1,...,j−1 .

Martin Hrub´ y


Co je ta historie?

◮

Je-li H koneˇcná mnoˇzina, je i pˇr´ısluˇsn´ a hra koneˇcná.

◮

Je-li nejdelˇs´ı prvek h ∈ H koneˇcnˇe dlouhý, m´ a hra koneˇcný horizont.

◮

Je-li h histori´ı délky k, pak (h, a) je histori´ı délky k + 1. Skládá se pak z h n´ asledovaného a.

◮

Z toho plyne definice A(h) = {a|(h, a) ∈ H}.

Zpˇetná indukce m˚ uˇze být pouˇzita pouze na koneˇcné hry.

Martin Hrub´ y


Informaˇcn´ı mnoˇziny typu I ⊆ H \ H T

Martin Hrub´ y


Informaˇcn´ı mnoˇziny typu I ⊆ H \ H T Mˇejme rozklad (relace, kter´ a je reflexivn´ı, symetrická a tranzitivn´ı) na mnoˇzinˇe H \ H T , tzn. mnoˇzinu mnoˇzin, které dohromay tvoˇr´ı H \ HT . ◮

Jednu informaˇcn´ı mnoˇzinu budeme oznaˇcovat I .

◮

Z principu relace ”rozklad na mnoˇzinˇe” plyne, ˇze kaˇzdá h ∈ H je právˇe v jedné mnoˇzinˇe rozkladu.

◮

je-li h ∈ I , pak je hr´ aˇc p(h) nejistý, zda-li je v uzlu h nebo v jiném h′ ∈ I .

◮

∀h, h′ ∈ I : p(h) = p(h′ ).

◮

jsou-li vˇsechny I jednoprvkové, pak je hra s dokonalou informac´ı (perfect information), jinak nedokonalou (imperfect)

Martin Hrub´ y


H, I

H = {(), (O), (F )} ∪ H T H T = {(O, o), (O, f ), (F , o), (F , f )} p(()) = 1, p((O)) = p((F )) = 2, A(()) = {O, F } Is = {{∅}, {O}, {F }}

Martin Hrub´ y


H, I

Is = {{∅}, {O, F }} Pozn.: Hráˇc 2 ve svém okamˇziku tahu nev´ı, co hr´ al protivn´ık (v jakém je on uzlu). Fakticky to odpov´ıd´ a situaci hry v normáln´ı formˇe.

Martin Hrub´ y


Definice sekvenˇcn´ı hry: co je strategie?

V sekvenˇcn´ıch hrách je strategi´ı kompletn´ı pl´ an hry od poˇcáteˇcn´ı historie (poˇcátku) aˇz po termin´ aln´ı historii. Tedy, je to celá cesta stromem aˇz po listový uzel. Tady je zˇrejm´ a pˇrevoditelnost se statickými hrami.

Definition Mˇejme hru ΓE . Nechˇt Hi = {h ∈ H|p(h) = i }. Mnoˇzina strategi´ı hráˇce i ∈ Q je dána Si = ×h∈Hi A(h) Pozn.: A(h) jsou mnoˇziny!

Martin Hrub´ y


Strategický profil, pˇrevod na statickou hru

Strategický profil definujeme obvyklým zp˚ usobem jako s ∈ S, S = ×i ∈Q Si . Pro kaˇzdou sekvenˇcn´ı hru ΓE = (Q, H, p, U) m˚ uˇzeme definovat S s s s statickou hru Γ = (Q ; (Si ); (Ui )) tak, ˇze ◮

Qs = Q

◮

Sis = Si , ∀i ∈ Q

◮

Uis (s) = Ui (h), s ∈ S s a h je historie odpov´ıdaj´ıc´ı postupnému proveden´ı sekvenˇcn´ı hry se strategiemi hr´ aˇc˚ u (si )i ∈Q .

Martin Hrub´ y


Nashovo ekvilibrium

Bez vˇetˇs´ıho pˇrekvapen´ı definujeme Nashovo ekvilibrium v sekvenˇcn´ı hˇre:

Definition Mˇejme sekvenˇcn´ı hru s dokonalou informac´ı ΓE . Strategický profil s ∗ nazveme Nashovo ekvilibrium, pokud plat´ı pro vˇsechny hráˇce i ∈ Q: ∗ ∗ Ui (si∗ , s−i ) ≥ Ui (si , s−i ) ∀si ∈ Si

Bylo uˇz ˇreˇceno, ˇze NE v sekvenˇcn´ıch hr´ ach ned´ av´ a dobré výsledky.

Martin Hrub´ y


Zermel˚ uv teorém

Theorem Kaˇzdá koneˇcná hra dokonalé informace m´ a PNE, které je dosaˇzitelné zpˇetnou indukc´ı. Pokud ˇzádný hráˇc nem´ a v ˇz´ adných dvou termin´ aln´ıch histori´ıch stejné uˇzitky, je ve hˇre pouze jedno PNE.

Garance existence PNE!

Martin Hrub´ y


Podhra, subgame Chceme vyˇsetˇrovat podstromy sekvenˇcn´ı hry. Za jistých okolnost´ı se lze koncentrovat na podhru a vyˇreˇsit tuto ˇc´ ast oddˇelenˇe od zbytku hry (je to základ backward induction).

Definition Podhra zadané sekvenˇcn´ı hry s dokonalou informac´ı ΓE ve stavu h je sekvenˇcn´ı hra s dokonalou informac´ı ΓE (h) = (Q, H|h , p|h , U|h ), kde ◮

H|h = {h′ |(h, h′ ) ∈ H}

◮

p|h (h′ ) = p(h, h′ ) pro kaˇzdou h′ ∈ H|h .

◮

U|h (h′ ) = U(h, h′ ) pro kaˇzdou h′ ∈ (H T ∩ H|h ).

Ze stromu hry vyextrahuju podstrom zaˇc´ınaj´ıc´ı histori´ı h. Ve hrách s nedokonalou informac´ı bude definice podhry sloˇzitˇejˇs´ı. Martin Hrub´ y


Subgame Perfect Nash Equilibrium (SPNE) Reinhard Selten, 1975, IJGT (International Journal on Game Theory)

Definition Mˇejme sekvenˇcn´ı hru s dokonalou informac´ı ΓE . Strategický profil s ∗ nazveme u ´plný rovnov´ aˇzný bod (SPNE), pokud pro kaˇzdého hráˇce i ∈ Q a kaˇzdou historii h ∈ H \ H T , kde p(h) = i plat´ı ∗ ∗ Ui |h (si∗ |h , s−i |h ) ≥ Ui |h (si |h , s−i |h )

pro vˇsechny strategie si |h hr´ aˇc˚ u i v podhˇre ΓE (h). Jinak ˇreˇceno, profil s ∗ je SPNE, pokud zv´ıtˇez´ı jako NE v kaˇzdé podhˇre hry. SPNE je refinement (zpˇresnˇen´ı) NE. Martin Hrub´ y


Pˇr´ıklad SPNE Uvaˇzujme hru, kde druhý hr´ aˇc signalizuje hrozbu, ˇze pokud prvn´ı zahraje R, tak on zahraje U. Souˇcasnˇe vid´ıme dvˇe PNE ((L, UU), (R, UK )) a zjemnˇen´ı na SPNE.

Martin Hrub´ y


Existence SPNE

Theorem Kaˇzdá koneˇcná sekvenˇcn´ı hra m´ a SPNE. Nav´ıc, pokud ˇza´dný hráˇc nen´ı indiferentn´ı mezi libovolnými dvˇema termin´ aln´ımi historiemi, pak je SPNE unikátn´ı.

Martin Hrub´ y


Solution Concepts

Martin Hrub´ y


SPNE ve hrách s kompletn´ı, ale nedokonalou informac´ı

◮

Uvaˇzujme, ˇze hra m´ a nedokonalou informaci, tzn. existuje informaˇcn´ı mnoˇzina, kter´ a je v´ıceprvkov´ a (obsahuje v´ıc histori´ı) tak, ˇze daný hr´ aˇc nev´ı, v jakém konkrétn´ım uzlu se nacház´ı.

◮

Neplat´ı to nejsp´ıˇs pro vˇsechny uzly a historie, takˇze máme informaˇcn´ı hybrid – v nˇekterých uzlech m´ a hráˇc jistotu, v nˇekterých ne.

◮

Pokud hráˇc ˇcel´ı nejistotˇe ve vˇsech uzlech (okamˇzic´ıch tahu), pak je hra ekvivaletn´ı se statickou hrou.

◮

Koncept SPNE je uplatnitelný, mus´ıme vˇsak modifikovat definici podhry pro situaci hry s kompletn´ı, ale nedokonalou informac´ı.

Martin Hrub´ y


Podhra ve hˇre s kompletn´ı, ale nedokonalou informac´ı

Podhra je opˇet hra v rozˇs´ıˇrené formˇe ΓE (h). Mus´ı platit: ◮

Mus´ı zaˇc´ınat v uzlu (historii), kter´ a je v jednoprvkové informaˇcn´ı mnoˇzinˇe.

◮

Obsahuje vˇsechny uzly n´ asleduj´ıc´ı tento poˇc´ ateˇcn´ı uzel a ˇzádné jiné.

◮

Nenaruˇsuje ˇzádnou informaˇcn´ı mnoˇzinu. Pokud jsou dvˇe historie h a h′ v jedné informaˇcn´ı mnoˇzinˇe, pak jsou spolu i v podhˇre.

Martin Hrub´ y


Podhra ve hˇre s kompletn´ı, ale nedokonalou informac´ı Tˇri hráˇci, kaˇzdý má strategie {L, M, R}. Hr´ aˇc 1 má jednu informaˇcn´ı mnoˇzinu, hr´ aˇc 2 m´ a dvˇe – {{(L)}, {(M), (R)}}, hráˇc 3 má ˇctyˇri informaˇcn´ı mnoˇziny.

Hra má tedy tˇri podhry: 1) origin´ aln´ı hra, 2) podhra tvoˇrená histori´ı (L), 3) podhra tvoˇren´ a histori´ı (L, R)

Martin Hrub´ y


Opakované hry

◮

Opakovaná hra je pˇr´ıpad hry v rozˇs´ıˇrené formˇe (sekvenˇcn´ı hry), která sestáv´ a z koneˇcného/nekoneˇcného opakován´ı tzv. základn´ı hry (stage game).

◮

V opakovaných hr´ ach (specificky v tˇech nekoneˇcnˇe opakovaných) je racion´ aln´ı hr´ at spoleˇcensky optimáln´ı profil, který se m˚ uˇze znaˇcnˇe liˇsit od NE.

◮

V opakovaných hr´ ach s koneˇcným (a pˇredem známým) poˇctem opakován´ı je racion´ aln´ı hr´ at v posledn´ı hˇre NE a v pr˚ ubˇehu ten koncept (NE, soci´ alnˇe optim´ aln´ı profil), který je výhodnˇejˇs´ı s vˇedom´ım budouc´ıho opakov´ an´ı hry. (pˇr. chain-store paradox)

◮

Koneˇcnˇe-opakované hry lze ˇreˇsit zpˇetnou indukc´ı.

Martin Hrub´ y


Pˇr´ıˇstˇe

◮

Kooperativn´ı hry a vyjedn´ av´ an´ı.

◮

Opakované hry a Korelované ekvilibrium.

◮

Mechanism design.

Martin Hrub´ y


Dynamic Games (Extensive Form Games)

Recommend Documents