THE: Smíšené Nashovo ekvilibrium ve strategických hrách (Mixed Nash Equilibria in Normal-Form Games)

THE: Sm´ıˇsené Nashovo ekvilibrium ve strategických hrách (Mixed Nash Equilibria in Normal-Form Games) Martin Hrubý Brno University of Technology Brno Czech Republic

October 9, 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

´ Uvod: ◮

Strategické hry a z´ akladn´ı pojmy. Ryz´ı (pure) strategie.

◮

Best response - BRi (s−i ) ⊆ Si , i ∈ Q, s−i ∈ S−i .

◮

◮

Ryz´ı Nashovo ekvilibrium (PNE) - s ∗ ∈ S, ˇz´ adný hráˇc nemá ∗ ∗ si ∈ Si , ˇze Ui (si , s−i ) > Ui (s ). Oˇcekávaný zisk a s n´ım spojené sm´ıˇsené chován´ı.

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 umˇ et hru hr´ at? Um´ıte hr´ at k´ amen-n˚ uˇzky-pap´ır?

◮

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


Pˇr´ıklad hry bez PNE: Matching pennies A/B heads tails

heads 1,-1 -1,1

tails -1,1 1,-1

Sledujme ˇrádkového hr´ aˇce. Ryz´ı BR jsou jasné. ◮

◮

◮

adkový indiferentn´ı (ve Pokud sloupcový hraje ( 21 , 12 ), pak je ˇr´ svých oˇcekáván´ıch) v˚ uˇci obˇema svým strategi´ım. ˇ Rádkový m˚ uˇze jednor´ azovˇe hr´ at cokoliv z (p, 1 − p), p ∈ h0, 1i. Hráˇci oˇ cek´ avaj´ı výsledek 0. M˚ uˇze ˇrádkový zvýˇsit sv´ a oˇcek´ av´ an´ı výsledku, resp. m˚ uˇze pro sebe garantovat lepˇs´ı výsledek? Pokud ˇr´ adkový vyboˇc´ı z rovnováˇzné strategie na napˇr. ( 43 , 14 ), pak se mˇen´ı sloupcového BR. Martin Hrub´ y


Pˇr´ıklad hry bez PNE: Matching pennies A/B heads tails

heads 1,-1 -1,1

tails -1,1 1,-1

Pokud ˇrádkový vyboˇc´ı z rovnov´ aˇzné strategie na napˇr. ( 34 , 14 ), pak se mˇen´ı sloupcového BR. πs (( 43 , 41 ), heads) = − 43 + 14 = − 21 πs (( 43 , 41 ), tails) = 34 − 14 = 21 ... tud´ıˇz je sloupcového BRs (( 34 , 14 )) = tails. Pak sloupcový hraje tails. πr (( 43 , 41 ), tails) = − 43 + 14 = − 21 ˇ adkový nezlepˇsil svá oˇcek´ R´ av´ an´ı (ani výsledek), naopak zhorˇsil z 0 na −0.5, kdyˇz vyboˇcil z rovnov´ aˇzné strategie. Martin Hrub´ y


Rozhodován´ı jedince za jistoty

volba a b c d zisk 10 20 40 40 Hr´ aˇ c je indiferentn´ı mezi c a d, tzn. rozhoduje se n´ ahodnˇ e podle pravdˇ epodobnostn´ı distribuce (0, 0, 0.5, 0.5). Rozhodnut´ı v:

Pˇresto je jisté, ˇze dosáhne výsledku 40.

Martin Hrub´ y


Oˇcekáván´ı ve hˇre, oˇcekávaný zisk Jaké je oˇcekáván´ı zisku pˇri loterii: volba zisk pravdˇepodobnost

a 10 0.1

b 20 0.2

c 30 0.6

d 1000 0.1

π = 10 · 0.1 + 20 · 0.2 + 30 · 0.6 + 1000 · 0.1 = 123 Oˇcekáván´ı je 123 a to i pˇresto, ˇze s pravdˇepodobnost´ı 0.9 dostanu nˇeco z h10, 30i. Kdo vytváˇr´ı ty pravdˇepodobnosti? Co kdyˇz je to protihráˇc?

Martin Hrub´ y


Vˇzdy nás zaj´ımá Best-Response

c d

a 3,2 -1,4

b 1,3 2,1

π1 (p, q) = 5pq − p − 3q + 2 , π2 (p, q) = −4pq + 2p + 3q + 1 Funkce π1 (p, q), kde hr´ aˇc pˇremýˇsl´ı o nejlepˇs´ım p ∈ h0, 1i. 1 9 BR1 (q = 10 , 10 ) ⇒ −0.5p − 0.7 ⇒ p := 0, tj. vol´ı d Problém: BR2 (d) = {a}, tj. U1 (d, a) = −1, tj. uhne do a. BR1 (q =

9 1 10 , 10

) ⇒ 3.5p − 0.7 ⇒ p := 1

BR1 (q = 51 , 54 ) ⇒ 5p · 0.2 − p − 3 · 0.2 + 2 = 1.4 Zde jiˇz BR nen´ı závislé nap, tzn. BR1 (q = 0.2) = ∆1 . MNE = (σ1∗ , σ2∗ ) = 34 , 14 , 51 , 45 Martin Hrub´ y


Výpoˇcet sm´ıˇsené rovnováhy analyticky c d

a 3,2 -1,4

b 1,3 2,1

p je pravdˇepodobnost hran´ı strategie a, tzn. 1 − p je prst hran´ı b. Podobnˇe q. 1 πi je funkce v promˇenných p a q, hled´ ame jej´ı extrém podle p, ∂π ∂p . π1 = 3pq +1p(1−q)−1(1−p)q +2(1−p)(1−q) = 5pq −p −3q +2 1 ∂π1 = 5q − 1 ⇒ q = ∂p 5 π2 = 2pq+3p(1−q)+4(1−p)q+(1−p)(1−q) = −4pq+2p+3q+1 ∂π2 3 = −4p + 3 ⇒ p = ∂q 4 Martin Hrub´ y


Sm´ıˇsené strategie Zavedeme pravdˇepodobnostn´ı rozˇs´ıˇren´ı do strategi´ı, oˇcekávaných zisk˚ u a rozhodován´ı.

Definition

|S |

Mˇejme hru Γ. Vektor pravdˇepodobnost´ı σi = (σi1 , σi2 , ..., σi i ) se nazývá sm´ıˇsená strategie hr´ aˇce i ∈ Q ve hˇre Γ, pokud plat´ı: ◮ ◮

σij ∈ h0, 1i pro vˇsechna 1 ≤ j ≤ |Si | P|Si | j j=1 σi = 1

Podobnˇe, jako pojem profil, zav´ ad´ıme i sm´ıˇsený profil jako vektor sm´ıˇsených strategi´ı, tedy σ = (σi )i ∈Q , kde σi je sm´ıˇsená strategie hráˇce i ∈ Q.

Martin Hrub´ y


Sm´ıˇsené strategie Sm´ıˇsenou strategii σi hr´ aˇce i interpretujeme jako pˇredpoklad, ˇze hráˇc i pouˇzije svou ryz´ı strategii sj ∈ Si (zde výjimeˇcnˇe chápejme Si = (s1 , s2 , ..., s|Si | ) jako vektor) s pravdˇepodobnost´ı σij . Sm´ıˇsená strategie je zobecnˇen´ım ryz´ı strategie, neboˇt σi = (σi1 , σi2 , ...) = (1, 0, ...) vyjadˇruje ryz´ı strategii si1 . Notace: σ je sm´ıˇsený profil, s ∈ S, si ∈ Si pro nˇejaké i ∈ Q ◮

σi (si ) je pravdˇepodobnost, ˇze hr´ aˇc i bude hr´ at si pˇri σ (resp. σi )

◮

σi (s) je ekvivalentn´ı z´ apis

Martin Hrub´ y


Sm´ıˇsené rozˇs´ıˇren´ı hry v normáln´ı formˇe Definition Mˇejme hru Γ = (Q; {Si }i ∈Q ; {Ui }i ∈Q ). Hru Γm = (Q; {∆i }i ∈Q ; {πi }i ∈Q ) nazveme sm´ıˇseným rozˇs´ıˇren´ım hry Γ, pokud ∀i ∈ Q: ◮

∆i je mnoˇzina sm´ıˇsených strategi´ı hr´ aˇce i (vektory délky |Si |). ˇ σi ∈ ∆i . C´ıslo σi (si ) oznaˇcuje pravdˇepodobnost pˇQ riˇrazenou ryz´ı strategii si ∈ Si ve strategii σi . Celkovˇe ∆ = i ∆i .     X mi ∆i = σi ∈ h0, 1i | σi (si ) = 1 ; mi = |Si |   si ∈Si

◮

Výplatn´ı funkce hr´ aˇce i πi (σ) =

X s∈S

Martin Hrub´ y



Ui (s) · 

Y

i ∈Q



σi (si )


Oˇcekávaný zisk (Expected payoff) ve sm´ıˇsených strategi´ıch Pˇripomeneme, ˇze v ryz´ıch strategi´ıch pˇri profilu s ∈ S je oˇcekávaný zisk hráˇce i dán: πi (s) = Ui (s). Vektor σ = (σ1 , σ2 , ..., σN ) je sm´ıˇsený strategický profil hráˇc˚ u ve hˇre. Pokud hráˇci i nehraj´ı konkrétn´ı (ryz´ı) strategii si ∈ Si , pak mus´ı být oˇcekávaný zisk hr´ aˇce i ∈ Q v profilu σ dán pravdˇepodobnostn´ım v´ ahov´ an´ım pˇres vˇsechny ryz´ı profily s ∈ S. πi (σ) =

X

pmix(s, σ) · Ui (s)

s∈S

kde pmix(s, σ) je pravdˇepodobnost profilu s ∈ S pˇri sm´ıˇsené strategii σ: pmix(s, σ) = Πi ∈Q σi (si )

Martin Hrub´ y


Sm´ıˇsené rozˇs´ıˇren´ı hry v normáln´ı formˇe Pˇripomeˇ nme definici sm´ıˇseného Nashova ekvilibria (MNE):

Definition Sm´ıˇsený profil σ ∗ ∈ ∆ je ekvilibrium ve hˇre Γm , pokud plat´ı pro vˇsechny i ∈ Q: ∗ σi∗ ∈ BRi (σ−i )

BRi (σ−i ) = arg max πi (σi , σ−i )

σi ∈∆i

Pozn.: Pˇredpokládáme, ˇze výsledkem operace BRi (σ−i ) je podmnoˇzina ∆i . Mnoˇzina ∆i m´ a jiný charakter neˇz Si ! Z toho plyne.: hráˇc i je v kontextu sub-profilu σ−i indiferentn´ı mezi vˇsemi σi ∈ BRi (σ−i ). Otázka: Jak je velká mnoˇzina BRi (σ−i )? Martin Hrub´ y


Expected payoff: pˇr´ıklad Pedro/Juana Box Balet σ∗ =

3 1 4, 4

,

1 3 4, 4

Box 3,1 0,0

Balet 0,0 1,3

Box

Balet

3 16 1 16

9 16 3 16

Pedro/Juana Box Balet

3 9 1 3 16 + + + = =1 16 16 16 16 16 πPedro (σ ∗ ) = 3 · Martin Hrub´ y

3 3 12 +1· = 16 16 16 THE: Nekooperativn´ı hry v norm´ aln´ı formˇ e

Expected payoff: pˇr´ıklad

Pedro/Juana Box Balet σ∗ =

3 1 4, 4

,

1 3 4, 4

Box 3,1 0,0

Balet 0,0 1,3

3 1 ∗ = 1 · = πPedro (Balet, σ−i ) 4 4 V MNE σ ∗ bude platit, ˇze je hr´ aˇc indiferentn´ı v˚ uˇci vˇsem svým ryz´ım strategi´ım, kterým jeho sm´ıˇsen´ a strategie σi∗ pˇriˇrazuje nenulovou pravdˇepodobnost. ∗ πPedro (Box, σ−i ) =3·

Martin Hrub´ y


NE ve sm´ıˇsených strategi´ıch – MNE (Mixed Nash Equilibrium)

Fakticky stejná definice jako pro PNE, ovˇsem se zaveden´ım expected payoff (pouze zobecnˇen´ı).

Definition Mˇejme hru Γ = (Q; {Si }i ∈Q ; {Ui }i ∈Q ). Sm´ıˇsený profil σ ∗ ∈ ∆ nazveme sm´ıˇsené Nashovo ekvilibrium ve hˇre Γ, pokud plat´ı pro vˇsechny hráˇce i ∈ Q a vˇsechny moˇzné sm´ıˇsené profily σ ∈ ∆: ∗ πi (σ ∗ ) ≥ πi (σi , σ−i )

Martin Hrub´ y


Sm´ıˇsené ekvilibrium: pˇr´ıklad A/B T B ∗

σ =

L 1,3 2,1

3 2 , 5 5

R 2,1 1,4

1 1 , , 2 2

πA (σ ∗ ) = 1.5 σ=

(1, 0) ,

1 1 , 2 2

πA (σ) = 1.5. Tj., ˇrádkový m˚ uˇze hr´ at st´ ale T , pak ovˇsem poruˇs´ı rovnováhu. Pˇri σ by B hrál nˇeco jiného. Martin Hrub´ y


Pochopen´ı sm´ıˇsených strategi´ı BRi (σ−i ) = arg max [πi (σi , σ−i )] σi ∈∆i

σi∗

Sm´ıˇsená strategie hr´ aˇce i je nejlepˇs´ı odpovˇed´ı na sm´ıˇsený ∗ pr´ subprofil σ−i avˇe tehdy, kdyˇz kaˇzd´ a z ryz´ıch strategi´ı, kterým σi∗ ∗ . pˇriˇrazuje nenulovou pravdˇepodobnost, je nejlepˇs´ı odpovˇed´ı na σ−i Ovˇ eˇrit na pˇr´ıkladech. ∗ indiferentn´ Hráˇc i je proto pˇri hran´ı σi∗ v situaci σ−i ı v˚ uˇci vˇsem ryz´ım strategi´ım s nenulovou pravdˇepodobnost´ı (jsou pro nˇej vˇsechny stejnˇe dobré).

To znamená, ˇze pokud by byly dvˇe jeho ryz´ı strategie s1i , s2i ∈ Si s nenulovou pravdˇepodobnost´ı v r´ amci σi∗ takové, ˇze by ∗ ) > π (s i , σ ∗ ), pak by σ ∗ nebylo ekvilibrium. πi (s1i , σ−i i 2 −i Martin Hrub´ y


Pochopen´ı sm´ıˇsených strategi´ı

c d e

a 3,2 -1,4 4,1

b 1,3 2,1 -2,5

e je BR1 (a), pˇresto se ne´ uˇcastn´ı MNE; c nen´ı BR, ale v MNE je c do MNE zanáˇs´ı sloupcový hr´ aˇc, neboˇt na nˇej m´ a vázáno b jako BR MNE = (σ1∗ , σ2∗ ) = 43 , 14 , 0 , 15 , 54

Martin Hrub´ y


Vˇeta o existenci Nashova ekvilibria

Theorem Kaˇzdá koneˇcná hra má vˇzdy alespoˇ n jeden rovnov´ aˇzný bod ve sm´ıˇsených strategi´ıch. John Nash, 1951 Tento závˇer publikoval John Nash ve své pr´ aci (Non-Cooperative Games, The Annals of Mathematics 54(2)). Uk´ azal tak koncept ekvilibria ve hrách s nenulovým souˇctem a souˇcasnˇe dok´ azal, ˇze kaˇzdá hra má nˇejaké ˇreˇsen´ı. D˚ ukaz si pˇredvedeme ve 4. pˇredn´ aˇsce.

Martin Hrub´ y


Vˇeta o existenci Nashova ekvilibria

Co znamená Nashova vˇeta? ◮

Koneˇcná hra = mnoˇziny strategi´ı hr´ aˇc˚ u jsou koneˇcné.

◮

V´ıme, ˇze koneˇcná hra m´ a vˇzdy ˇreˇsen´ı. Z˚ ust´ avá jeˇstˇe problém ho naj´ıt.

◮ ◮

Máme-li bi-maticovou hru n × n, pak m´ a tato hra aˇz 2n−1 NE. v´ıce: Quint, T., Shubik, M.: A theorem on the number of Nash equilibria in a bimatrix game, International Journal of Game Theory, Volume 26, Number 3 / October, 1997

Theorem Kaˇzdá koneˇcná hra má lichý poˇcet Nashových ekvilibri´ı.

Martin Hrub´ y


Výpoˇcet Nashova ekvilibria ve sm´ıˇsených strategi´ıch (MNE)

◮

Analýza strategických her ve sm´ıˇsených strategi´ıch je stále algoritmicky obt´ıˇznˇe ˇreˇsitelný problém.

◮

Výpoˇcet MNE je ve sloˇzitostn´ı tˇr´ıdˇe NP (v r´ amci výzkumu algoritmizace výpoˇctu MNE byla zavedena specifická tˇr´ıda PPAD ⊂ NP (Ch. Papadimitriou) a byly publikovány d˚ ukazy o pˇr´ısluˇsnosti výpoˇctu MNE v N-hr´ aˇcových maticových hrách k PPAD pro jistá N – zat´ım ne obecnˇe). Obecnˇe proto pˇriˇrazujeme výpoˇcet MNE k NP sloˇzitosti.

◮

Pˇredvedeme obecný pˇredpis pro ˇreˇsen´ı dvouhráˇcových her a v pozdˇejˇs´ıch pˇrednáˇsk´ ach dalˇs´ı sloˇzitˇejˇs´ı algoritmy.

Martin Hrub´ y


Výpoˇcet ˇreˇsen´ı pro Matching pennies

A/B heads tails

heads 1,-1 -1,1 q

tails -1,1 1,-1 1−q

p 1−p

p, q jsou pravdˇepodobnosti strategie ”heads”, 1 − p (resp. 1 − q) jsou pravdˇepodobnosti ”tails”. Oˇcekávané výplaty: π1 (p, q) = 1pq − 1p(1 − q) − 1(1 − p)q + 1(1 − p)(1 − q) π2 (p, q) = −pq + 1p(1 − q) + 1(1 − p)q − 1(1 − p)(1 − q) π1 (p, q) = 4pq − 2p − 2q + 1 π2 (p, q) = −4pq + 2p + 2q − 1

Martin Hrub´ y


Výpoˇcet ˇreˇsen´ı pro Matching pennies π1 (p, q) = 4pq − 2p − 2q + 1 π2 (p, q) = −4pq + 2p + 2q − 1 ∂π1 1 = 4q − 2 = 0 ⇒ 4q = 2 ⇒ q = ∂p 2 1 ∂π2 = −4p + 2 = 0 ⇒ −4p = −2 ⇒ p = ∂q 2 Hra má jediné ˇreˇsen´ı ve formˇe Nashova ekvilibria ve sm´ıˇsených strategi´ıch. Je to 1 1 1 1 ∗ , , , s = 2 2 2 2

Martin Hrub´ y


Obecný pˇredpis pro analytický výpoˇcet MNE Uvaˇzujme hru dvou hr´ aˇc˚ u s mnoˇzinami ryz´ıch strategi´ı S1 , S2 a pravdˇepodobnostn´ı promˇenné p1 , p2 , ..., pm−1 a q1 , q2 , ..., qn−1 , kde m = |S1 |, n = |S2 |. Odvod´ıme funkce pro oˇcek´ avané výplaty π1 (p1 , p2 , ..., pm−1 ), π2 (q1 , q2 , ..., qn−1 ). ˇ s´ıme soustavu lineárn´ıch rovnic: Reˇ ∂π1 = 0; 1 ≤ i ≤ m − 1 ∂pi ∂π2 = 0; 1 ≤ j ≤ n − 1 ∂qj Kaˇzdé ˇreˇsen´ı této soustavy s pi ≥ 0, qj ≥ 0 splˇ nuj´ıc´ı P q ≤ 1 je rovnov´ a ˇ z n´ y bod zadan´ e hry. j j Martin Hrub´ y

P

i

pi ≤ 1,


Grafické ˇreˇsen´ı her

◮

Kresl´ı se ”reakˇcn´ı kˇrivky” – pr˚ ubˇeh BR na nˇejakou strategii.

◮

Jejich pr˚ useˇc´ık je ekvilibrium.

Martin Hrub´ y


Grafické ˇreˇsen´ı her Zavedeme nejdˇr´ıve hru bez PNE (Colonel Blotto Game, defender/invader, Mountain/Plains). D/I M P

M 1,-1 -1,1

P -1,1 1,-1

Nechˇt σ1 = σ1 (M) je pravdˇepodobnost, ˇze obr´ ance bude stˇreˇzit hory, resp. σ2 = σ2 (M) u ´toˇcn´ık napadne obr´ ance pˇres hory. Oˇcekávané uˇzitky hráˇc˚ u: π1 (M, σ2 ) = σ2 − (1 − σ2 ) = 2σ2 − 1 π1 (P, σ2 ) = −σ2 + (1 − σ2 ) = 1 − 2σ2 π2 (σ1 , M) = −σ1 + (1 − σ1 ) = 1 − 2σ1 π2 (σ1 , P) = σ1 − (1 − σ1 ) = 2σ1 − 1

Martin Hrub´ y


Konstrukce reakˇcn´ıch kˇrivek

π1 (M, σ2 ) = σ2 − (1 − σ2 ) = 2σ2 − 1 π1 (P, σ2 ) = −σ2 + (1 − σ2 ) = 1 − 2σ2   σ2 > 12 M BR1 (σ2 ) = P σ2 < 21   {M, P} σ2 = 12

adkový hr´ aˇc indiferentn´ı mezi V situaci, kdy σ2 = 12 je naprosto ˇr´ {M, P}. Z toho plyne, ˇze BR1 (σ2 ) = ∆1

Martin Hrub´ y


Konstrukce reakˇcn´ıch kˇrivek, sloupcový hráˇc

π2 (σ1 , M) = −σ1 + (1 − σ1 ) = 1 − 2σ1 π2 (σ1 , P) = σ1 − (1 − σ1 ) = 2σ1 − 1   σ1 < 12 M BR2 (σ1 ) = P σ1 > 21   {M, P} σ1 = 12

Martin Hrub´ y


Grafické nalezen´ı ekvilibria, Colonel’s game

Martin Hrub´ y


Grafické nalezen´ı ekvilibria, PNEs+MNEs FBI/CIA King Obyc

Martin Hrub´ y

King 2,2 1,0

Obyc 0,1 1,1


Grafické nalezen´ı ekvilibria, PNEs+MNEs

Sm´ıˇsená strategie je pˇredevˇs´ım reakce na preference protivn´ıka (paradox). Mohli bychom si myslet, ˇze v modifikované hˇre zmˇen´ı CIA své chován´ı. FBI/CIA King Obyc   K σ1 = BR1 (σ2 ) = O   [0, 1]

σ2 > σ2 < σ2 =

Martin Hrub´ y

King 2,4 1,0 1 2 1 2 1 2

Obyc 0,1 1,1   K σ2 = BR2 (σ1 ) = O   [0, 1]


σ1 > σ1 < σ1 =

1 4 1 4 1 4

Grafické nalezen´ı ekvilibria, PNEs+MNEs FBI/CIA King Obyc

King 2,4 1,0

Obyc 0,1 1,1

MNE = (( 14 , 34 ), ( 12 , 21 )) Martin Hrub´ y


Algoritmické ˇreˇsen´ı koneˇcných her

Definition Mˇejme hru Γ = (Q; {Si }i ∈Q ; {Ui }i ∈Q ). Support supp(σi ) je mnoˇzina ryz´ıch strategi´ı si ∈ Si hr´ aˇce i , kterým sm´ıˇsená strategie σi pˇriˇrazuje nenulovou pravdˇepodobnost σi (si ) ∈ h0, 1i. Tzn., supp(σi ) = {si ∈ Si |σi (si ) > 0} Mnoˇzina vˇsech support˚ u hr´ aˇce i je rovna Suppi = 2Si \ {∅}, tzn. je S jich |2 i | − 1 mnoho.

Martin Hrub´ y


Základn´ı pˇr´ıstup (silou)

Pˇredpokládejme sm´ıˇsený sub-profil ∆−i . Je-li σi ∈ BRi (∆−i ), pak je hráˇc i indiferentn´ı v˚ uˇci vˇsem ryz´ım strategi´ım supp(σi ), tzn. ∀si , sj ∈ supp(σi ) : πi (si , ∆−i ) = πi (sj , ∆−i ) Souˇcasnˇe mus´ı platit X

σi (si ) = 1

si ∈supp(σi )

To je poˇcátek pro sestaven´ı soustavy rovnic (line´ arn´ıch pro dvou-hráˇcové hry).

Martin Hrub´ y


Základn´ı pˇredpoklad pro následuj´ıc´ı algoritmus Definition Dvouhráˇcová hra je tak zvanˇe nedegenerovan´ a, pokud ˇzádná sm´ıˇsená strategie se supportem velikosti k nem´ a v´ıce neˇz k ryz´ıch best-response (pozor! nezkoum´ ame poˇcet sm´ıˇsených BR). Tuto vlastnost snadno pozn´ ame: pokud m´ a hra na ryz´ı strategii jednoho hráˇce dvˇe (a v´ıce) ryz´ıch best-response protihr´ aˇce, je degenerovaná. Plyne z toho: Kterékoliv Nash ekvilibrium (s1∗ , s2∗ ) nedegenerované dvouhráˇcové hry má supporty stejné délky. Pro dalˇs´ı studium doporuˇcuji: Nisan et al.: Algorithmic Game Theory (link na stránce THE), specificky kapitolu: Bernhard von Stengel: Equilibrium Computation for Two-Player Games in Strategic and Extensive Form Martin Hrub´ y


Ukázka degenerované hry (pˇr´ıklad od P. Zemka) c d

a 3,3 1,2

b 3,3 2,0

Hra je degenerovaná, neboˇt na ryz´ı strategii c m´ a sloupcový hráˇc best-response {a, b}. Nav´ıc vid´ıme, ˇze hru lze redukovat na |3, 3 3, 3|, kde ˇrádkový hráˇc vol´ı svou jedinou strategii, ale sloupcový je naprosto indiferentn´ı mezi a a b tak, ˇze jeho BR2 (c) = ∆2 , to znamen´ a, ˇze mnoˇzina MNE je nekoneˇcná. ˇ co Závˇer: opˇet vid´ıme, ˇze TH n´ am ned´ av´ a jednoznaˇcnou odpovˇed se ve hˇre stane, ale ukazuje n´ am, ˇze ˇr´ adkový hr´ aˇc má striktnˇe dominantn´ı strategii c a sloupcovému je za této situace naprosto jedno, co bude hrát (nez´ aleˇz´ı na tom ani ˇr´ adkovému). Martin Hrub´ y


Výpoˇcet sm´ıˇsené rovnováhy II.

c d

a 3,2 -1,4

b 1,3 2,1

Vycház´ıme z poznán´ı indiference mezi a a b pˇri hran´ı sm´ıˇsené (p, 1 − p) versus sm´ıˇsené (q, 1 − q). Pak pro ˇrádkového hráˇce vych´ az´ı uˇzitek: U1 (c, a) · q + U1 (c, b) · (1 − q) = U1 (d, a) · q + U1 (d, b) · (1 − q) 3q + 1(1 − q) = −1q + 2(1 − q) 3q = −q + (1 − q) q = 15 Podobnˇe sloupcový: 2p + 4(1 − p) = 3p + (1 − p) ⇒ p = Martin Hrub´ y

3 4


Základn´ı pˇr´ıstup (silou) – algoritmus, 2 hráˇci

Algoritmus je urˇcen pro výpoˇcet vˇsech MNE v dvouhráˇcových nedegenerovaných hrách. V pˇr´ıpadˇe degenerované hry nˇekterá ekvilibria neodhal´ı. V pˇr´ıpadˇe v´ıce-hr´ aˇcové hry se zmˇen´ı lineárn´ı rovnice na nelineárn´ı, které nejsp´ıˇs nikdo nechce ˇreˇsit. Vstup: Hra Γ = (Q; {Si }i ∈Q ; {Ui }i ∈Q ), matice A, resp. B vyjadˇruj´ıc´ı U1 , resp. U2 , m = |S1 |, n = |S2 |. Výstup: Mnoˇzina MNE, tzn. ∗ ); ∀i ∈ Q} MNEs = {σ ∗ ∈ ∆|σi∗ ∈ BRi (σ−i Nechˇt K = {1, 2, ..., min(m, n)}

Martin Hrub´ y


Základn´ı pˇr´ıstup (silou) – algoritmus, 2 hráˇci Algoritmus: 1. ∀k ∈ K : 2. ∀I ⊆ S1 , |I | = k: 3. ∀J ⊆ S2 , |J| = k: ˇ s následuj´ıc´ı soustavu rovnic. Pokud m´ a ˇreˇsen´ı, pak sm´ıˇsený 4. Reˇ ˇ profil (x, y ) zaˇrad mezi výsledky. Sloˇzky mimo I , J jsou nulové, tzn. ∀z ∈ S1 \ I : xz = 0, ∀z ∈ S2 \ J : yz = 0 Soustava obecnˇe: X

xi bij = v ; ∀j ∈ J

X

aij yj = u; ∀i ∈ I

i ∈I

X

xi = 1

X

yj = 1

i ∈I

j∈J

j∈J

Martin Hrub´ y


Pˇr´ıklad: Matching pennies

A=

A/B heads tails

heads 1,-1 -1,1

1 −1 −1 1

;B =

tails -1,1 1,-1

−1 1 1 −1

; K = {1, 2}

ˇ sen´ı pro k = 1 zavrhujeme rovnou, protoˇze v ryz´ıch strategi´ıch Reˇ neoˇcekáváme výsledek (v´ıme, ˇze tam nen´ı). Strategie heads a tails si pˇrejmenujeme na 1 a 2.

Martin Hrub´ y


Soustava pro k = 2, I = {1, 2}, J = {1, 2} −x1 + x2 = u y1 − y2 = v x1 − x2 = u −y1 + y2 = v x1 + x2 = 1 y1 + y2 = 1 Z toho plyne: −x1 + x2 = x1 − x2 −2x1 + 2x2 = 0 −2(1 − x2 ) + 2x2 = 0 −2 + 2x2 + 2x2 = 0 4x2 = 2 y2 = x2 = 12 1 x1 = 2 y1 =

1 2 1 2

Profil (( 21 , 12 ), ( 12 , 21 )) patˇr´ı mezi ˇreˇsen´ı PNEs. Martin Hrub´ y


Algoritmická sloˇzitost ˇreˇsen´ı ”silou”

◮ ◮ ◮

Pro kaˇzdé k ∈ K ˇreˇs´ıme Πi ∈Q |Ski | soustav P Pro vˇsechna k je to k∈K Πi ∈Q |Ski | soustav

U dvouhráˇcových her jsou to soustavy line´ arn´ıch rovnic,

◮

u v´ıcehráˇcových her pak soustavy neline´ arn´ıch rovnic (ponˇekud obt´ıˇzné).

◮

Výpoˇcet Nashova equilibria je ve sloˇzitostn´ı tˇr´ıdˇe PPAD (2 a v´ıce hráˇc˚ u)

V´ıce: Daskalakis, C., Goldberg, P.W., Papadimitriou, Ch.: The Complexity of Computing a Nash Equilibrium, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing

Martin Hrub´ y


Algoritmy pro MNE

Hledáme algoritmy, které by ˇreˇsily MNE efektivnˇeji, tzn. pˇrevád´ı problém výpoˇctu MNE na jiný ekvivalentn´ı problém, který ˇreˇs´ı efektivnˇeji. ◮

Lemke-Howson˚ uv algoritmus – pouze pro dvouhráˇcové hry, pouze jedno ekvilibrium

◮

Experimenty s genetickými algoritmy.

Martin Hrub´ y


Simulaˇcn´ı (numerické) ˇreˇsen´ı her Chceme modelovat konkrétn´ı strategickou situaci. ◮

Poˇc´ıtaˇcová simulace, numerick´ a metoda.

◮

Modelujeme fakt, ˇze existuje N hr´ aˇc˚ u.

◮

Modelujeme fakt, ˇze hr´ aˇci maj´ı mnoˇziny strategi´ı Si .

Jak ovˇsem vyjádˇrit uˇzitkové funkce Ui : S → U 1. Funkce (zadané analyticky nebo matic´ı) povaˇzujeme za vstup. Nˇekdo nám je dá. D´ ale hru jenom analyzujeme. 2. Funkce nejsou vstupem. Jsme ovˇsem schopni sestavit vnitˇrn´ı model, který vyhodnot´ı pro kaˇzdý profil s ∈ S, co by se stalo, kdyby hráˇci hráli strategie si . Výsledkem tohoto experimentu s vnitˇrn´ım modelem by byl vektor uˇzitk˚ u hr´ aˇc˚ u (ui )i ∈Q .

Martin Hrub´ y


Simulaˇcn´ı ˇreˇsen´ı her

Pak je kompletn´ı model d´ an f´ azemi: 1. Modelován´ı struktury hry – kdo jsou hr´ aˇci, jaké maj´ı strategie, co v´ı o hˇre, ... 2. Tvorbou vnitˇrn´ıho modelu hry cm : S → UN . 3. Implementac´ı analytických funkc´ı dle teorie her. Mˇejme pak program: for s in S: U[s] := cm(s); eq := nashEq(S,U);

Martin Hrub´ y


Pˇr´ıˇstˇe, kam to smˇeˇruje

◮

Prostudujeme hry s nulovým souˇctem

◮

Zavedeme metody line´ arn´ıho programov´ an´ı (matematický základ her)

◮

Projdeme algoritmy výpoˇctu MNE v hr´ ach dvou hráˇc˚ u, obecný základ

◮

Projdeme Nash˚ uv d˚ ukaz existence ekvilibria

◮

Dále pak: opakov´ an´ı ve hˇre, kooperativnost, vyjednáván´ı, aukce, volby, ...

Martin Hrub´ y


THE: Smíšené Nashovo ekvilibrium ve strategických hrách (Mixed Nash Equilibria in Normal-Form Games)

Recommend Documents