(Non-cooperative Normal-Form Games)

THE: Nekooperativn´ı hry v normáln´ı formˇe (Non-cooperative Normal-Form Games) Martin Hrubý Brno University of Technology Brno Czech Republic

October 1, 2014

Martin Hrub´ y

THE: Nekooperativn´ı hry v norm´ aln´ı formˇ e

´ Uvod ˇ ano z: Cerp´ ◮ ◮

◮

◮

Fudenberg, D., Tirole, J.: Game Theory, The MIT Press, 1991 Osborne, M., Rubinstein, A.: A Course in Game Theory, The MIT Press, 1994 McCarthy, N., Mierowitz, A.: Political Game Theory: An Introduction, Cambridge University Press, 2007 Magdaléna Hykˇsov´ a: Pˇredn´ aˇsky z teorie her, Fakulta dopravn´ı ˇ CVUT

´ Uvod: ◮

◮ ◮

Hry v normáln´ı formˇe (tzv. strategické hry) jsou nejobecnˇejˇs´ım pojet´ım strategické interakce. V rámci nich zkoum´ ame kooperativn´ı a nekooperativn´ı hry. Provedeme klasifikaci her. Dneˇsn´ı pˇredn´ aˇska bude o nekooperativn´ıch strategických hr´ ach s nenulovým souˇctem. Martin Hrub´ y


Dˇelen´ı strategických her Podle zp˚ usobu hran´ı hry: ◮

Hry jednotahové – hry v norm´ aln´ı formˇe (normal-form games).

◮

Hry dynamické (sekvenˇcn´ı hry, hry v rozˇs´ıˇrené formˇe) – hr´ aˇci se stˇr´ıdaj´ı v taz´ıch (angl. dynamic games, extensive-form games). ˇ asteˇcná pˇrevoditelnost. C´

◮

Podle moˇznost´ı komunikace mezi hr´ aˇci pˇred volbou strategie: ◮

Nekooperativn´ı – z´ akladn´ı forma strategické interakce.

◮

Kooperativn´ı – fundament´ alnˇe odliˇsné. Zkoumáme sp´ıˇse pˇredpoklady pro kooperativnost v jedn´ an´ı.

Podle m´ıry konkurence/soutˇeˇzivosti: ◮

S nenulovým souˇctem.

◮

S konstantn´ım/nulovým souˇctem – striktnˇe kompetitivn´ı hry.

Pozn.: Dalˇs´ı dˇelen´ı je podle m´ıry informace hr´ aˇc˚ u. Martin Hrub´ y


Dalˇs´ı pokraˇcován´ı studia her Ve strategických hrách: ◮

Sm´ıˇsené strategie.

◮

Opakován´ı ve hrách.

◮

Korelované ekvilibrium.

◮

Evoluˇcnˇe stabiln´ı strategie.

V mechanism designu: ◮

Návrh mechanism˚ u.

◮

Teorie veˇrejné volby.

◮

Teorie aukc´ı.

Martin Hrub´ y


´ Uvodn´ ı krátké demo strategické hry s nenulovým souˇctem A/B top bottom

left 1,2 5,6

right 3,4 7,8

Jak se hraje nekooperativn´ı hra v norm´ aln´ı formˇe (ilustrativn´ı pˇredstava): ◮ ◮ ◮

◮ ◮

◮

Hráˇci si vˇsichni uvˇedomuj´ı, ˇze jsou u ´ˇcastn´ıky ve hˇre. Hráˇci spolu nekomunikuj´ı. Hráˇci se rozhodnou, jakou strategii budou hr´ at, nap´ıˇs´ı ji na l´ıstek, ten vloˇz´ı do ob´ alky a ob´ alku odevzdaj´ı nezávislému arbitrovi. Vˇsichni hráˇci odevzdaj´ı svou ob´ alku ve stejný okamˇzik. Arbitr najednou otevˇre vˇsechny ob´ alky a zveˇrejn´ı hrané strategie hráˇc˚ u. Hráˇc˚ um je pˇridˇelen zisk daný modelem situace a podle hraných strategi´ı. Martin Hrub´ y


Demo, proveden´ı tahu A/B top bottom

left 1,2 5,6

right 3,4 7,8

1. Hráˇci oba (vˇsichni) zvol´ı tajnˇe svou strategii. V naˇsem pˇr´ıkladˇe ˇrádkový (A) zvol´ı ”top”, sloupcový (B) zvol´ı ”right”. 2. Nezávislý arbitr zjist´ı volbu strategi´ı a pˇridˇel´ı hráˇc˚ um jejich zisky: ◮ ◮

ˇ adkový dostane zisk 3 R´ Sloupcový dostane 4

3. Pokud se výsledek hr´ aˇc˚ um nel´ıb´ı, maj´ı sm˚ ulu: dalˇs´ı kolo hry uˇz nebude. Mˇeli uvaˇzovat lépe. V poznán´ı jedno-tahovosti mnoha her spoˇc´ıv´ a znaˇcné rozˇcarován´ı v mnoha lidských situac´ıch. Lidé se mnohdy nechovaj´ı racionálnˇe (správnˇe) proto, ˇze maj´ı dojem ˇze se to pˇrece vˇzdycky dá napravit, nééé...?! – Experiment´ aln´ı teorie her. Martin Hrub´ y


Co je to ta hra...? ◮

Hra je strategická interakce mezi dvˇema a v´ıce hráˇci, kteˇr´ı svou ˇcinnost´ı chtˇej´ı dos´ ahnout optim´ aln´ıho výsledku ve hˇre.

◮

Hra je matematický model rozhodovac´ı situace – je to tedy zjednoduˇsen´ı problému na jeho podstatné prvky.

◮

Hlavn´ım zjednoduˇsuj´ıc´ım pˇredpokladem je pˇredpoklad racionality hráˇc˚ u.

Pod toto oznaˇcen´ı spad´ a velmi mnoho vˇec´ı, cokoli od rulety po ˇsachy, od bakaratu po bridˇz. A nakonec kaˇzd´ a ud´ alost – jsou-li dány vnˇejˇs´ı podm´ınky a u ´ˇcastn´ıci situace (a ti se chovaj´ı dle svobodné v˚ ule) – m˚ uˇze být povaˇzov´ ana za spoleˇcenskou hru, jestliˇze sledujeme u ´ˇcinek, jaký m´ a na u ´ˇcastn´ıky [John von Neumann, 1928]. Juli Zeh: Hráˇcský instinkt, Odeon, 2006 Martin Hrub´ y


Hry s nulovým a nenulovým souˇctem

◮

Historicky dˇr´ıve byly zavedeny hry s nulovým souˇctem. Vˇeta o minimaxu, John von Neumann.

◮

Aˇz pozdˇeji (1950-1) byl definov´ an koncept ekvilibria ve hrách s nenulovým souˇctem (J. Nash).

◮

V THE probereme nejdˇr´ıve hry s nenulovým souˇctem (jsou pˇrirozenˇejˇs´ı). Hry s nulovým souˇctem jsou speciáln´ım pˇr´ıpadem her s nenulovým souˇctem (matematicky).

Martin Hrub´ y


Sociologický/psychologický aspekt her s nulovým souˇctem (doc. Franˇek, UHK) Nulový souˇcet: ◮ Situace, jeˇ z má skonˇcit nulovým souˇctem, je situac´ı soutˇeˇzen´ı. ◮ B´ yt hráˇcem s nulovými souˇcty znamen´ a vˇeˇrit, ˇze ve vˇsech ˇzivotn´ıch situac´ıch jsou jen dvˇe moˇznosti: z´ıskat nebo ztratit. ◮ Z psychologick´ eho (i etického) hlediska je poj´ımán´ı mezilidských kontakt˚ u jako ”her s nulovým souˇctem” poruchové, v ˇradˇe pˇr´ıpad˚ u sociopatické. Nenulový souˇcet: ◮ Oba mohou ”zv´ ıtˇezit”. ◮ Je nadˇ eje na kooperativn´ı chov´ an´ı vedouc´ı k efektivnˇejˇs´ımu výsledku hry. Pedro/Juana Rozdˇelit spravedlivˇe Rozdˇelit vychytrale Martin Hrub´ y

Spolupracovat 10,10 100,1

Trestat 0,0 0,0


Common knowledge Aumann, R: Agreeing to Disagree, The Annals of Statistics, Vol. 4, No. 6. (Nov., 1976), pp. 1236-1239. (v knihovnˇ e: Aumann: Collected Papers, vol. 1) Zat´ım pouze zkrácenˇe definujme spoleˇcnou znalost. ◮ ◮

Mˇejme dva hráˇce A a B Událost E je pro hr´ aˇce {A, B} common knowledge, pokud: ◮ ◮ ◮ ◮ ◮ ◮

... hráˇci {A, B} oba v´ı o události E ... hráˇc A v´ı, ˇze B v´ı o události E ... hráˇc B v´ı, ˇze A v´ı o události E ... hráˇc A v´ı, ˇze B v´ı, ˇze A v´ı o události E ... hráˇc B v´ı, ˇze A v´ı, ˇze B v´ı o události E takto aˇz do nekoneˇcného zanoˇren´ı

Pˇr´ıklad: dva vojev˚ udci se informuj´ı o m´ıstˇe a ˇcasu bitvy. Vojev˚ udce A vyˇsle k B posla, ... Martin Hrub´ y


Common knowledge – pˇr´ıklad s modrookými na ostrovˇe Mˇejme ostrov, kde ˇzij´ı lidé s modrýma (M) a zelenýma (Z) oˇcima. Poˇcet M je k ≥ 1. Na ostrovˇe nejsou zrcadla a lidi se o barvˇe oˇc´ı nebav´ı (maj´ı moˇznost pouze pozorovat). Pˇredpokládáme, ˇze jsou vˇsichni naprosto logicky uvaˇzuj´ıc´ı. ◮

Pokud se ˇclovˇek o sobˇe dozv´ı, ˇze je M, pak mus´ı následuj´ıc´ı den za sv´ıtán´ı ostrov opustit.

◮

Jednoho dne pˇrijde cizinec a vˇsem veˇrejnˇe oznám´ı: ”je tu alespoˇ n jeden M”.

◮

Pˇred pˇr´ıchodem cizince nebyl tento stav common knowledge.

Co se stane? ◮

k = 1, pˇr´ıˇst´ı den M odejde

◮

k = 2, pˇr´ıˇst´ı den nic, 2. sv´ıt´ an´ı odejdou oba. Kaˇzdý M v´ı, ˇze existuje M, ale kaˇzdý M nev´ı, ˇze jiný M m´ a tu stejnou znalost.

◮

k > 2, k−té sv´ıtán´ı odejdou vˇsichni M Martin Hrub´ y


Struktura hry

◮

Pravidla – zp˚ usob hran´ı hry, pˇredpoklady, ...

◮

Hráˇci – nezávislé inteligentn´ı entity sleduj´ıc´ı sv˚ uj zámˇer (jednou z definic racionality je ”snaha definovat své c´ıle a ty se snaˇzit naplnit”).

◮

Hráˇci hraj´ı hru t´ım, ˇze vol´ı své tahy – strategie, akce, volby.

◮

Volba akce vede k nˇejakému n´ asledku – uˇzitku ve hˇre.

◮

Hráˇci maj´ı jistou informaci o hˇre – znaj´ı protihráˇce, jejich akce a formu (a velikost) uˇzitku.

◮

Hráˇci se na základˇe znalost´ı o hˇre rozhoduj´ı.

Martin Hrub´ y


Definice strategické hry N hráˇc˚ u, N ≥ 2 Definition Strategická hra N hráˇc˚ u je (2N + 1)-tice Γ = (Q; S1 , S2 , ..., SN ; U1 , U2 , ..., UN ) ◮

Q = {1, 2, ..., N} je koneˇcn´ a mnoˇzina hr´ aˇc˚ u ve hˇre.

◮

Si , i ∈ Q jsou (koneˇcné) mnoˇziny ryz´ıch strategi´ı hráˇc˚ u i ∈ Q.

◮

Ui : S1 × S2 × ... × SN → U jsou funkce uˇzitku hráˇc˚ u.

Poznámky: ˇ ◮ U je univerzum vˇ sech moˇzných uˇzitk˚ u. Casto klademe U = R. ◮ S = S1 × S2 × ... × SN je mnoˇ zina strategických profil˚ u ve hˇre. s ∈ S je strategický profil. ◮ Prostor S n´ am ud´ av´ a rozmˇer problému, který mus´ıme algoritmicky ˇreˇsit. ◮ Ryz´ ı (angl. pure) a sm´ıˇsené (angl. mixed) strategie. Martin Hrub´ y


Pˇr´ıklad hry

A/B top bottom

left 1,2 5,6

right 3,4 7,8

◮

Q = {A, B}.

◮

SA = {top, bottom}, SB = {left, right}.

◮

S = SA × SB = {(top, left), (top, right), (bottom, left), (bottom, right)}

◮

UA (top, left) = 1, UA (top, right) = 3, ..., UB (bottom, right) = 8

Uˇzitky zapisujeme pˇrehlednˇe do matice – maticové hry.

Martin Hrub´ y


Informace o hˇre Aby hráˇci mohli provést rozhodnut´ı, mus´ı m´ıt nˇejaké informace o hˇre. Zat´ım pˇredpoklád´ ame (pro jednoduchost), ˇze jim ˇza´dná informace o hˇre nechyb´ı (jinak by si museli udˇelat o stavu nˇekterých vˇec´ı stochastický model). Proto zavedeme pojem kompletn´ı informace ve hˇre (angl. complete information):

Definition Mˇejme hru Γ = (Q; {Si }i ∈Q ; {Ui }i ∈Q ). Pokud jsou pro vˇsechny z´ uˇcastnˇené hráˇce Q následuj´ıc´ı informace common knowledge: ◮

struktura hry Γ,

◮

výplatn´ı (uˇzitkové) funkce Ui ; i ∈ Q,

◮

zp˚ usob hran´ı hry a forma hern´ıho ekvilibria,

a souˇcasnˇe tento fakt samotný je common knowledge, pak maj´ı hráˇci kompletn´ı informaci o hˇre. Martin Hrub´ y


Rozsah informac´ı ve hˇre

◮

Common knowledge.

◮

Kompletn´ı informace (complete information). Nekompletn´ı informace (incomplete information, Bayesian games)

◮

Dokonalá informace (perfect information). Nedokonalá informace (imperfect information).

Martin Hrub´ y


Nulový versus Nenulový souˇcet formálnˇe

Definition

ˇ Mˇejme hru Γ. Rekneme, ˇze Γ je hra s konstantn´ım souˇctem k ∈ R, pokud plat´ı X ∀s ∈ S : Ui (s) = k i ∈Q

Pokud je k = 0, pak je Γ hra s nulovým souˇctem. U her s nenulovým souˇctem nelze naj´ıt k ∈ R takové, ˇze by platila pˇredchoz´ı podm´ınka.

Martin Hrub´ y


Co je c´ılem? Solution concept... Strategická hra N hráˇc˚ u s nenulovým souˇctem je matematický model konfliktn´ı situace. ◮

Tento model obdrˇz´ıme nebo vytvoˇr´ıme (vˇeˇr´ıme, ˇze vˇsichni hráˇci model odvod´ı stejnˇe).

◮

Vˇeˇr´ıme, ˇze existuje nˇejaké racion´ aln´ı chov´ an´ı hráˇc˚ u, které je formalizovatelné. Hled´ ame ˇreˇsen´ı hry.

◮

Pokud existuje model chov´ an´ı ve formˇe algoritmu nad modelem hry, pak matematickým ˇreˇsen´ım hry z´ıskám predikci chován´ı hráˇc˚ u ve skuteˇcnosti.

◮

Formalizace chov´ an´ı – solution concept.

Snahou je predikovat chov´ an´ı hr´ aˇc˚ u nebo alespon rozumˇet jejich chován´ı.

Martin Hrub´ y


Model chován´ı hráˇc˚ u Hráˇci ˇcel´ı situaci a mus´ı zvolit sv˚ uj tah. Prov´ ad´ı urˇcitou u ´vahu. ◮

Budeme zkoumat postup hr´ aˇcova uvaˇzov´ an´ı.

◮

Teoreticky se nemus´ıme uˇcit, jak se rozhodnout. Model rozhodován´ı pouze algoritmizuje pˇrirozenou inteligenci a racionáln´ı pˇr´ıstup k ˇreˇsen´ı rozhodov´ an´ı.

Výsledkem rozhodován´ı kaˇzdého hr´ aˇce i ∈ Q je volba nˇejaké ryz´ı strategie si∗ ∈ Si , u které hr´ aˇc vˇeˇr´ı, ˇze mu pˇrinese maximáln´ı uˇzitek (outcome). Výsledek volby vˇsech hr´ aˇc˚ u je pak strategický profil s ∗ ∈ S, s ∗ = (s1∗ , s2∗ , ..., sN∗ ) Pokud profil s ∗ splˇ nuje urˇcité vlastnosti, je nazýv´ an ekvilibrium ve hˇre (ˇcesky rovnováha). Martin Hrub´ y


´ Uvod do analýzy her A/B top bottom

left 1,2 5,6

right 3,4 7,8

◮

Jakou strategii zvol´ı hr´ aˇc A, pokud by hr´ aˇc B mˇel hrát left? Hráˇc maximalizuje sv˚ uj uˇzitek.

◮

Hráˇc si rozmýˇsl´ı svoje moˇzné nejlepˇs´ı odpovˇedi na moˇzné tahy protihráˇce.

◮

Pozor, hra je jednotahov´ a, tzn. veˇskeré promýˇslen´ı se odehrává v mysl´ıch hr´ aˇc˚ u. Hr´ aˇci mus´ı hru kompletnˇe strategicky rozebrat.

◮

Hráˇci maj´ı pouze jednu moˇznost t´ ahnout!

Martin Hrub´ y


Charakteristika Best-response (BR), nejlepˇs´ı odpovˇedˇ Hra Γ = (Q; S; U). ◮

◮

Nechˇt hráˇc i ∈ Q pˇremýˇsl´ı, co bude hr´ at, kdyˇz jeho protivn´ıci Q−i = Q \ {i } budou hr´ at konkrétn´ı strategie sj , j ∈ Q−i . Q Pˇripomeˇ nme mnoˇzinu S = i ∈Q Si . Zavedeme mnoˇzinu: Y S−i = Sj j∈Q−i

◮ ◮

Prvek s−i ∈ S−i je jakýsi kontext rozhodov´ an´ı (sub-profil). Notace: (si , s−i ) je sloˇzen´ı do celého profilu, (si , s−i ) ∈ S V kontextu s−i ∈ S−i hr´ aˇ c i vol´ı si ∈ Si tak, ˇ ze aln´ı. Ui (si , s−i ) je na {(si , s−i )|si ∈ Si } maxim´ Mi (Si , s−i , ≥) = {si∗ ∈ Si |Ui (si∗ , s−i ) ≥ Ui (si , s−i ); ∀si ∈ Si } Martin Hrub´ y


Charakteristika Best-response, formálnˇe Mnoˇzina profil˚ u hry: S=

Y

Si

i ∈Q

Mnoˇzina sub-profil˚ u hry (pro kaˇzdého hr´ aˇce i ∈ Q !!!): S−i =

Y

Sj

j∈Q−i

Best-response hráˇce i v sub-profilu s−i ∈ S−i : BRi (s−i ) = arg max [Ui (si , s−i )] si ∈Si

Poznámka: promyslete si algoritmus výpoˇctu BRi (s−i ). Jaké má vstupy a výstupy? Martin Hrub´ y


Charakteristika Best-response Z definice: BRi (s−i ) ⊆ Si . ◮

◮

◮

◮

ˇ BRi (s−i ). Hráˇc v kontextu s−i vol´ı svou nejlepˇs´ı odpovˇed Takto se zˇrejmˇe budou chovat vˇsichni. ˇ bude asi rovnov´ Vzájemná nejlepˇs´ı odpovˇed aˇzný profil ve hˇre – tzn. rovnováha – ˇz´ adný hr´ aˇc nechce mˇenit svou strategii. Situace, kdy pro nˇejaké i ∈ Q a s−i ∈ S−i je |BRi (s−i )| > 1 vyjadˇruje urˇcitou nejistotu hr´ aˇce v jeho tahu. Vede na sm´ıˇsené chován´ı (pozdˇeji). Zˇrejmˇe vˇzdy plat´ı: ∀i ∈ Q, ∀s−i ∈ S−i : |BRi (s−i )| > 0. Proˇc??

Best-response je základ vˇsech hernˇe-teoretických algoritm˚ u. Best-response je korespondence: BRi : S−i →→ Si Martin Hrub´ y


Dominantnost strategi´ı ve hˇre Pedro/Juana Rozdˇelit spravedlivˇe Rozdˇelit vychytrale

Spolupracovat 10,10 100,1

Trestat 0,0 0,0

V nˇekterých rozhodovac´ıch situac´ıch jasnˇe c´ıt´ıme, ˇze jedna strategie s 1 je výraznˇe lepˇs´ı neˇz druh´ a s 2 bez ohledu na dalˇs´ı ˇ ıkáme, ˇze takov´ okolnosti. R´ a strategie s 1 striktnˇe dominuje nad s 2 .

Definition Mˇejme hru Γ = (Q; {Si }i ∈Q ; {Ui }i ∈Q ). Strategie si1 hráˇce i ∈ Q striktnˇe dominuje nad jeho strategi´ı si2 , pokud plat´ı ˇze: ∀s−i ∈ S−i : Ui (si1 , s−i ) > Ui (si2 , s−i ) Co z toho plyne? Racion´ aln´ı hr´ aˇc i ∈ Q bude vˇzdy preferovat si1 nad si2 . Strategie si1 je dominantn´ı (dominant) a strategie si2 je dominovaná (dominated). Martin Hrub´ y


Dominantnost strategi´ı ve hˇre ◮

◮

Pokud plat´ı, ˇze si1 striktnˇe dominuje nad vˇsemi Si \ {si1 }, pak je si1 pro hráˇce i striktnˇe dominantn´ı. Pokud ∀si1 ∈ Si \ {si2 } plat´ı, ˇze si1 striktnˇe dominuje nad si2 , pak je si2 striktnˇe dominovan´ a.

◮

Pokud má racionáln´ı hr´ aˇc striktnˇe dominantn´ı strategii, bude ji vˇzdy hrát.

◮

Pokud má racionáln´ı hr´ aˇc striktnˇe dominovanou strategii, tak ji nikdy hrát nebude.

◮

Racionáln´ı hráˇc si uvˇedomuje existenci dominantn´ıch strategi´ı svých protihráˇc˚ u.

◮

Má kaˇzdá hra striktnˇe dominantn´ı strategii?

Poznámka: promyslete si algoritmus výpoˇctu dominance strategi´ı. Jaké má vstupy a výstupy? Martin Hrub´ y


Dominantnost strategi´ı ve hˇre Striktn´ı dominance zav´ ad´ı opˇet formu preference hráˇce. Jaká je to relace? ≻i ⊆ S i × S i ◮

Je u ´plná? Plat´ı ∀si1 , si2 ∈ Si ; si1 6= si2 : si1 ≻i si2 ∨ si2 ≻i si1 ??

◮

Je reflexivn´ı?

◮

Je tranzitivn´ı?

◮

Je symetrická?

◮

Je asymetrická?

◮

Je antisymetrická?

Dá se o striktn´ı preferenci nad strategiemi nˇeco ˇr´ıci?

Martin Hrub´ y


Pˇr´ıklad: Vˇezˇnovo dilema Jedna z nejslavnˇejˇs´ıch hern´ıch situac´ı. Mnoho výklad˚ u. ◮

◮

◮

◮

◮

Policie zadrˇz´ı Petera a Johna, kteˇr´ı jsou podezˇrel´ı z bankovn´ı loupeˇze. Neexistuje vˇsak proti nim pˇr´ımý d˚ ukaz. Podezˇrel´ı Peter a John jsou um´ıstˇeni do oddˇelených cel a vyslýcháni zvláˇsˇt ⇒ nemohou spolu komunikovat (kooperace, vyjednáván´ı). Maj´ı kaˇzdý dvˇe moˇznosti: vypov´ıdat (pˇriznat se a zradit kumpána), mlˇcet (spolupracovat s kump´ anem). C´ılem policie je z nich dostat pˇrizn´ an´ı. Policie kaˇzdému sdˇel´ı: pokud budeˇs vypov´ıdat a tv˚ uj kumpán mlˇcet, pak tˇe pust´ıme a tv˚ uj kump´ an dostane 20 let. Pokud budete vypov´ıdat oba (pˇrizn´ ate se), dostanete oba 10 let. Pokud budete oba mlˇcet, dostanete aspoˇ n kaˇzdý 1 rok za nedovolené drˇzen´ı zbranˇe. Kaˇzdý podezˇrelý pˇredpokl´ ad´ a: racionalitu protihráˇce, kompletn´ı informaci o hˇre. Martin Hrub´ y


Pˇr´ıklad: Vˇezˇnovo dilema Peter/John vypov´ıdat mlˇcet

vypov´ıdat -10,-10 -20,0

mlˇcet 0,-20 -1,-1

◮

Jaká je BRPeter (vypovidat) a BRPeter (mlcet)?

◮

Dominuje vypovidat nad mlcet?

◮

vypovidat je striknˇe dominantn´ı strategie, racionáln´ı hráˇc ji bude vˇzdy hrát.

◮

Oba hráˇci maj´ı striktnˇe dominantn´ı strategii. Vzniká ekvilibrium striktnˇ e dominantn´ıch strategi´ı (nepˇr´ıliˇs v realitˇe ˇcasté).

◮

Ekvilibrium: s ∗ = (vypovidat, vypovidat) ⇒ Ui (s ∗ ) = −10

Martin Hrub´ y


Pˇr´ıklady vˇezˇnova dilematu v naˇsem ˇzivotˇe ◮

Vˇezˇ novo dilema m´ a pˇrekvapivˇe hodnˇe realizac´ı v naˇsem ˇzivotˇe. Ve vˇsech je pak patrné, ˇze sobeckost a neschopnost kooperovat vede na ménˇe optim´ aln´ı výsledek hry.

◮

Vˇsechny aspekty reklamy a obchodu: investovat do reklamy, uvádˇet DPH u výrobk˚ u, ...

◮

Zbrojen´ı, mezinárodn´ı vztahy.

◮

Uˇz´ıván´ı hromadné dopravy versus osobn´ı auta. A/B Zrada Spolupráce

Zrada (trest,trest) (oˇskub´ an´ı,pokuˇsen´ı)

Spolupráce (pokuˇsen´ı,oˇskubán´ı) (odmˇena,odmˇena)

oˇskub´ an´ı < trest < odmˇ ena < pokuˇsen´ı

Jsme jako spoleˇcnost urˇceni k z´ aniku? , Martin Hrub´ y


Varianty vˇezˇnova dilematu Peter/John vypov´ıdat mlˇcet

vypov´ıdat -10,-10 -20,0

mlˇcet 0,-20 -1,-1

Zlepˇs´ı se výsledek, kdyˇz: ◮

vˇezni maj´ı moˇznost komunikace pˇred proveden´ım rozhodnut´ı?

◮

se situace opakuje?

◮

je common knowledge, ˇze zr´ adce bude b´ıdnˇe zastˇrelen kumpány venku? (d˚ uvˇeryhodn´ a hrozba): Peter/John vypov´ıdat mlˇcet

vypov´ıdat -500,-500 -20,-1000

Martin Hrub´ y

mlˇcet -1000,-20 -1,-1


Iterativn´ı eliminace dominovaných strategi´ı Myˇslenka: pokud hráˇc nikdy nebude hr´ at striktnˇe dominovanou strategii, pak je tato ve hˇre zbyteˇcn´ a (resp. v jeho mnoˇzinˇe strategi´ı). ◮

Které strategie jsou pro hr´ aˇce racion´ aln´ı?

◮

Hru Γ = (Q; {Si }i ∈Q ; {Ui }i ∈Q ) je tedy moˇzno redukovat na Γ′ = (Q; {Si′ }i ∈Q ; {Ui′ }i ∈Q ) bez ztr´ aty strategické vˇerohodnosti.

◮

Redukce Γ ⊢ Γ′

◮

Redukce iterativnˇe prob´ıh´ a, dokud je ve hˇre nˇejaká dominovaná strategie

◮

Γ ⊢ Γ1 ⊢ ... ⊢ Γj−1 ⊢ Γj , kde Γj = Γj−1

Martin Hrub´ y


Iterativn´ı eliminace dominovaných strategi´ı: ⊢

Vstup: hra Γ = (Q; {Si }i ∈Q ; {Ui }i ∈Q ) Výstup: hra Γ′ = (Q; {Si′ }i ∈Q ; {Ui′ }i ∈Q ) 1. ∀i ∈ Q: Sdi := {si ∈ Si |si je striktnˇe dominovaná }. 2. Γ′ = (Q; {Si \ Sdi }i ∈Q ; {Ui′ }i ∈Q ) 3. ∀i ∈ Q : ∀s ′ ∈ S ′ : Ui′ (s ′ ) = Ui (s ′ ) jsou redukované funkce uˇzitku (restrikce Ui na Ui′ )

Martin Hrub´ y


Slabá dominance ◮

Podobný druh dominance, který vˇsak uˇz nen´ı striktn´ı.

◮

Nen´ı jiˇz zcela korektn´ı eliminovat slabˇe dominované strategie (mohly by tvoˇrit ekvilibrium).

Definition Strategie si1 hráˇce i ∈ Q slabˇe (weakly) dominuje nad jeho strategi´ı si2 , pokud plat´ı, ˇze: ∀s−i ∈ S−i : Ui (si1 , s−i ) ≥ Ui (si2 , s−i ) a souˇcasnˇe ∃s−i ∈ S−i : Ui (si1 , s−i ) > Ui (si2 , s−i ) Pozn.: Aplikace eliminace zaloˇzené na slabé dominanci jsou moˇzné v politických vˇedách (volebn´ı mechanismy). Pˇr´ıklad viz McCarthy. Martin Hrub´ y


Eliminace her algoritmicky

Zaj´ımavé pojednán´ı je v ˇcl´ anku: Itzhak Gilboa, Ehud Kalai, Eitan Zemel: The Complexity of Eliminating Dominated Strategies, MATHEMATICS OF OPERATIONS RESEARCH, Vol. 18, No. 3, August 1993, pp. 553-565

Martin Hrub´ y


(Strategická) ekvivalence her

Definition Hra Γ = (Q, {Si }i ∈Q , {Ui }i ∈Q ) je ekvivalentn´ı s hrou Γ′ = (Q, {Si }i ∈Q , {Ui′ }i ∈Q ), pokud existuj´ı pro kaˇzdého hráˇce i ∈ Q reálná ˇc´ısla Ai , Bi , kde Ai > 0 a plat´ı ∀s ∈ S: Ui′ (s) = Ai Ui (s) + Bi

Tzn., pokud ke hˇre pˇripoˇctu nˇejaké ˇc´ıslo (resp. vynásob´ım konstantou), strategick´ y charakter hry se nezmˇ en´ı. Poznámka: Problém finanˇcn´ıho poradce.

Martin Hrub´ y


Best-response ekvivalence

Definition Mˇejme hru Γ = (Q; {Si }i ∈Q ; {Ui }i ∈Q ). Nechˇt BRsi =

[

BRi (s−i )

s−i ∈S−i

Pak je hra Γ′ = (Q; {BRsi }i ∈Q ; {Ui′ }i ∈Q ) BR-ekvivalentn´ı s Γ. Pozn.: zamyslete se nad algoritmem výpoˇctu BR-ekvivalentn´ı hry. Pozn.: m˚ uˇze Γ′ obsahovat striktnˇe nebo slabˇe dominované strategie?

Martin Hrub´ y


Never Best-response strategie

Definition Mˇejme hru Γ = (Q; {Si }i ∈Q ; {Ui }i ∈Q ). Pro kaˇzdého hráˇce i ∈ Q lze strategie z hlediska BR rozdˇelit do tˇechto kategori´ı: ◮

BR strategie – BRsi .

◮

Always-BR (vˇzdy) strategie – ABRi ⊆ BRsi a plat´ı ∀si ∈ ABRi : si ∈ BRi (s−i ) pro vˇsechny s−i ∈ S−i

◮

Never-BR (nikdy) strategie – NBRi = Si \ BRsi .

Jaký je vztah BR a strategické dominance? Vˇeta, d˚ ukaz...

Martin Hrub´ y


Hry bez striktnˇe dominantn´ıch strategi´ı Striktn´ı dominance je neobvykl´ a. Situace (Skinner˚ uv chl´ıvek): máme dvˇe prasata (dominantn´ı a submisivn´ı) zavˇrená ve chl´ıvku vybavaném pákou a korytem. Kdyˇz se stiskne p´ aka, do koryta spadne ˇzrádlo s energetickou hodnotou 10 jednotek. Cesta k páce a zpátky ke korytu spotˇrebuje dvˇe jednotky energie. Pˇredpokládáme, ˇze dominantn´ı prase v souboji o koryto vˇzdy v´ıtˇez´ı.

dominantn´ı/submisivn´ı stiskni p´ aku stiskni páku 8,-2 ˇ u koryta sed 10,-2 Martin Hrub´ y

ˇ u koryta sed 5,3 0,0


Nashovo ekvilibrium v ryz´ıch strategi´ıch

◮

Hráˇc bude vˇzdy hr´ at Best-response. Vˇsichni hráˇci budou vˇzdy hrát best-response na best-response protivn´ıka, na BR na BR na BR, ...

◮

Vzájemná BR je rovnov´ aha.

◮

Snaha hrát BR je zˇrejmˇe common knowledge ve hˇre.

◮

Ekvilibrium je strategický profil, ve kterém ˇza´dný hráˇc nem˚ uˇze zlepˇsit sv˚ uj uˇzitek zmˇenou své strategie (tzn. zmˇenou své strategie si m˚ uˇze zhorˇsit uˇzitek).

◮

Pure Nash Equilibrium (PNE).

◮

Mixed Nash Equilibrium (MNE).

Martin Hrub´ y


Definice Nashova ekvilibria v ryz´ıch strategi´ıch Definition Mˇejme hru Γ. Profil s ∗ ∈ S se nazýv´ a Nashovo ekvilibrium v ryz´ıch strategi´ıch, pokud plat´ı: ∗ ∗ ∀i ∈ Q : ∀si ∈ Si : Ui (si∗ , s−i ) ≥ Ui (si , s−i )

Definice plat´ı bez ohledu na to, zda-li si = si∗ nebo si 6= si∗ . Nashovo ekvilibrium je nejv´ yznamnˇ ejˇs´ı solution concept v nekooperativn´ıch strategick´ ych hr´ ach s nenulov´ ym souˇ ctem. Celkovˇe je NE z´ akladn´ı koncept vˇsech her. Pozn.: Znalost definice NE a jeho pochopen´ı je absolutnˇe nezbytné pro pˇredmˇet THE. Martin Hrub´ y


John Forbes Nash jr., (nar. 1928) Nashovo ekvilibrium bylo poprvé definov´ ano v tˇechto ˇclánc´ıch: ◮

Nash, J.: Equilibrium points in n-person games, Proceedings of the National Academy of Sciences 36(1):48-49., 1950

◮

Nash, J.: Non-Cooperative Games, The Annals of Mathematics 54(2):286-295, 1951

Martin Hrub´ y


Alternativn´ı definice NE

Vycház´ıme z poznán´ı, ˇze NE je sloˇzeno ze vz´ ajemnˇe nejlepˇs´ıch odpovˇed´ı, tud´ıˇz:

Definition Mˇejme hru Γ. Profil s ∗ ∈ S se nazýv´ a Nashovo ekvilibrium v ryz´ıch strategi´ıch, pokud plat´ı: ∗ ∀i ∈ Q : si∗ ∈ BRi (s−i )

Pozn.: vˇsimnˇeme si, ˇze matematika definuje pojem výsledku, ale neukazuje cestu k jeho výpoˇctu. Budeme zkoumat algoritmy výpoˇctu PNE (a ˇcasem MNE).

Martin Hrub´ y


Vlastnosti PNE Pojem efektivnost profilu/ekvilibria: E (s) =

X

U(s)

i ∈Q ◮

Pokud je hra Γ modelem nˇejaké re´ alné situace a Γ má PNE, pak je velmi pravdˇepodobné, ˇze i hr´ aˇci v realitˇe se budou chovat podle PNE (PNE je self-enforcing).

◮

Hra m˚ uˇze m´ıt v´ıce PNE. Pak si pˇredstavme PNE jako energetickou stabiln´ı hladinu, kter´ a udrˇzuje hráˇce v nˇejakém chován´ı. Pokud pˇripust´ıme opakov´ an´ı hry, tak m˚ uˇze doj´ıt k pˇresunu chován´ı hr´ aˇc˚ u z jednoho ekvilibria do jiného (obvykle efektivnˇejˇs´ıho).

◮

M˚ uˇze existovat hra bez PNE, ale nˇejaké chován´ı v n´ı hráˇci pˇresto maj´ı (bude m´ıt stochastický charakter). Martin Hrub´ y


Vlastnosti PNE: NE je neeliminovatelné

Theorem Je-li (s1∗ , s2∗ , ..., sN∗ ) Nashovo ekvilibrium, pak ˇz´ adná z jeho strategi´ı si∗ nem˚ uˇze být ze hry eliminov´ ana iterativn´ı eliminac´ı striktnˇe dominovaných strategi´ı. Intuitivnˇe chápeme, ˇze strategie hr´ aˇc˚ u v ekvilibriu jsou jaksi v´ıtˇez´ıc´ı a ˇze nem˚ uˇze pro ˇzádného hr´ aˇce i ∈ Q existovat taková strategie ∗ ) > U (s ∗ ). s ′ ∈ Si \ {si∗ }, ˇze by Ui (s ′ , s−i i Tento fakt je pro analýzu her velmi d˚ uleˇzitý. Plyne z toho, ˇze iterativn´ı eliminace dominovaných strategi´ı m˚ uˇze být pouˇzita jako nˇejaké ”pˇredzpracován´ı” hry.

Martin Hrub´ y


Vlastnosti PNE

Theorem ustal po iterativn´ı eliminaci Je-li (s1∗ , s2∗ , ..., sN∗ ) jediný profil, který z˚ striktnˇe dominovaných strategi´ı, pak je tento profil jediným Nashovým ekvilibriem. Toto je taky jasné, protoˇze pak je tento profil ekvilibrium striktnˇe dominantn´ıch strategi´ı. Mimo to, pokud m´ a hra Γ = (Q; S; U) mnoˇzinu profil˚ u takovou, ˇze S = {s} (tzn. |S| = 1), pak s je ekvilibrium, protoˇze neexistuje pro ˇz´ adného hr´ aˇce jin´ a (lepˇs´ı) strategie.

Martin Hrub´ y


Algoritmy nalezen´ı PNE Algoritmy pro nalezen´ı PNE jsou v z´ akladu jednoduché. Jejich problematiˇcnost m˚ uˇze spoˇc´ıvat v algoritmické ˇcasové sloˇzitosti. Algoritmy: ◮ PNEs(Γ) = {s ∈ S|s je ekvilibrium} ◮ Redukce na BR-ekvivalentn´ ı hru, n´ aslednˇe konvenˇcn´ı algoritmus ◮ Redukce iterativn´ ı eliminac´ı striktnˇe dominovaných strategi´ı, ... Konvenˇcn´ı výpoˇcet: S 1. Let BRprofsi = s−i ∈S−i {(b, s−i )|b ∈ BRi (s−i )} T 2. PNEs = i ∈Q BRprofsi dominantn´ı/submisivn´ı stiskni p´ aku stiskni páku 8,-2 ˇ u koryta sed 10,-2 Martin Hrub´ y

ˇ u koryta sed 5,3 0,0


Efektivita výsledku hry, dominance nad profily Pˇredpokládejme, ˇze výpoˇctem dos´ ahneme mnoˇziny ekvilibri´ı ∗,1 ∗,2 PNEs = {s , s ...}. ◮

Zkoumáme, je-li nˇejaký profil efektivnˇejˇs´ı neˇz druhý, tzn. E (s ∗,1 ) >? E (s ∗,2 ).

◮

Otázkou je opˇet naˇse schopnost predikovat chován´ı hráˇc˚ u– ∗,j tedy, který profil s zvol´ı.

◮

Známým modelem této situace jsou koordinaˇcn´ı hry.

Pochopme, ˇze TH ned´ av´ a odpovˇedi na ot´ azky, co hráˇci udˇelaj´ı. Teorie her je dle jedné hezké definice (Osborne,Rubinstein) pytel analytických nástroj˚ u pro pochopen´ı chov´ an´ı jedinc˚ u pˇri strategickém rozhodov´ an´ı.

Martin Hrub´ y


Jak naloˇzit s výsledkem?

Interpretace výsledk˚ u analýzy hern´ıho modelu je proto d˚ uleˇzitá. ˇ pak je tˇreba Pokud trváme na to, ˇze chceme od modelu odpovˇed, dodat model chován´ı v situaci v´ıce ekvilibri´ı. R˚ uzné varianty pojet´ı optim´ aln´ıho výsledku. Nejznámˇejˇs´ı je pojet´ı pojmenované podle Vilfreda Pareto (1848–1923, italský ekonom).

Martin Hrub´ y


Pareto efektivita (optimalita) Mˇejme hru Γ = (Q; {Si }i ∈Q ; {Ui }i ∈Q ):

Definition Strategický profil (ekvilibrium) s ∈ S pareto dominuje nad profilem s ′ ∈ S, jestliˇze plat´ı: ∀i ∈ Q : Ui (s) ≥ Ui (s ′ ) a souˇcasnˇe existuje alespoˇ n jedno i ∈ Q, ˇze Ui (s) > Ui (s ′ ) Pak m˚ uˇzeme pokraˇcovat v rozhodov´ an´ı nad ekvilibrii tak, ˇze hledáme Pareto efektivn´ı ˇreˇsen´ı.

Definition Strategický profil (ekvilibrium) s ∈ S je pareto efektivn´ı (optimáln´ı), pokud neexistuje jiný profil s ′ ∈ S, který by pareto dominoval s. Martin Hrub´ y


Koordinaˇcn´ı hra Koordinaˇcn´ı hra je speci´ aln´ım pˇr´ıpadem hry, kdy je pro hr´ aˇce lepˇs´ı se domluvit na spoleˇcné volbˇe strategie (napˇr. stejného IT standardu). Pˇr´ıklady: j´ızda po silnici, Battle of sexes, Stag hunt (Lov na jelena, modeluje konflikt ”zabezpeˇcen´ı se” versus soci´ aln´ı kooperace, Jean-Jacques Rousseau) A/B left right

left 10,10 0,0

right 0,0 10,10

A/B lovit jelena lovit zaj´ıce

ˇzena/muˇz box balet

lovit jelena 10,10 7,0

Martin Hrub´ y

box 2,3 1,1

balet 1,1 3,2

lovit zaj´ıce 0,7 7,7


Antikoordinaˇcn´ı hra Slavná je hra ”Game of chicken”. Dva puberˇt´ aci se potˇrebuj´ı veˇrejnˇe zviditelnit. Sednou do svých aut a jedou proti sobˇe. Kdo uhne, je srab (ovˇsem zp˚ usob´ı, ˇze oba pˇreˇzij´ı). A/B srab drsˇ n´ ak

srab 0,0 1,-1

drsˇ n´ ak -1,1 -100,-100

Je to ukázka hry, kdy je lépe volit navz´ ajem opaˇcné strategie. Tuto situaci budeme studovat d˚ ukladnˇeji v dynamických hrách, kde si zavedeme pojem ”d˚ uvˇeryhodn´ a/ned˚ uvˇeryhodn´ a hrozba”. Tuˇs´ıme, ˇze c´ılem je pˇresvˇedˇcit protivn´ıka, ˇze vy rozhodnˇe neuhnete, pak je jeho BR uhnout. Tato situace je zn´ am´ a tak´ e z tzv. Kub´ ansk´ e krize (Cuban missile crisis, ˇr´ıjen 1962). Martin Hrub´ y


Ultimatum game

Dva hráˇci se maj´ı podˇelit o 100 duk´ at˚ u. Dˇelba prob´ıh´ a tak, ˇze ˇ ˇra´dkový hráˇc navrhne rozdˇelen´ı a sloupcový ho bud pˇrijme (a pak je provedeno) nebo odm´ıtne (a pak pen´ıze nedostane nikdo). Jaký je model hry? M´ a hra PNE? Vˇeˇr´ıte tomu PNE?

Martin Hrub´ y


Nekooperativn´ı versus kooperativn´ı chován´ı Peter/John pˇriznat se zatloukat

pˇriznat se -10,-10 -20,0

zatloukat 0,-20 -1,-1

◮

PNE je stabiln´ı ˇreˇsen´ı hry. Býv´ a pˇrekvapuj´ıc´ı, jak tento outcome m˚ uˇze být neefektivn´ı ve srovn´ an´ı s jinými profily (které ovˇsem nejsou self-enforcing).

◮

Pˇr´ıkladem je profil (zatloukat,zatloukat) ve Vˇezˇ novˇe dilematu.

◮

Kooperativn´ı ˇreˇsen´ı hry m˚ uˇze být efektivnˇejˇs´ı pro spoleˇcnost, ale dominováno jinou strategi´ı jedince.

◮

Budeme zkoumat moˇznosti tvorby koalic a vyjednáván´ı.

◮

Kooperativnost do chov´ an´ı zav´ ad´ı taky opakován´ı hern´ı situace (kde hráˇci mus´ı ˇcelit n´ asledk˚ um pˇredchoz´ı hry) – model: restaurace v turistické z´ onˇe versus hospoda pro m´ıstn´ı. Martin Hrub´ y


Pˇr´ıklad hry bez PNE: Matching pennies Kaˇzdý hráˇc má penny. Tajnˇe otoˇc´ı svoje penny na heads/tails (t´ım vol´ı strategii). A/B heads tails

heads 1,-1 -1,1

tails -1,1 1,-1

◮

Jak se zachovaj´ı hr´ aˇci, pokud nemaj´ı PNE?

◮

Co znamená, ˇze neexistuje PNE?

◮

Budou hráˇci hru hr´ at? Zˇrejmˇe mus´ı...

◮

Zopakujme si, ˇze TH je analytický n´ astroj pro zkouman´ı interakc´ı.

◮

Hráˇci hru hraj´ı, rozhoduj´ı se, takˇze mus´ı existovat jej´ı matematický model. Martin Hrub´ y


Závˇer

◮

Definice a význam hry v norm´ aln´ı formˇe.

◮

Best-response, strategick´ a dominance, ...

◮

Nashovo ekvilibrium v ryz´ıch strategi´ıch (PNE).

◮

Existuj´ı hry bez PNE, ale zˇrejmˇe maj´ı jinou formu ˇreˇsen´ı.

ˇ sen´ı sm´ıˇseného NE. Pˇr´ıˇstˇe: Reˇ

Martin Hrub´ y


(Non-cooperative Normal-Form Games)

Recommend Documents