Jak poznáme, že máme spolupracovat ?

Seminář ČSKI, DAR a odd. AS

Milan Mareš 20. říina 2009.

Kde se vzala teorie her

1944 – John von Neumann, Oscar Morgenstern: Theory of Games and Economic Behaviour.

────────────────

Už první tvůrci počtu pravděpodobnosti, Girolamo Cardano a Blaise Pascal s Pierrem de Fermat se inspirovali hazardními hrami.

Von Neumannova a Morgensternova kniha má 2 části:

o nekooperativních (strategických) hrách a

o kooperativních (koaličních) hrách.

To nejzákladnější o strategických hrách

Omezíme se na hry dvou hráčůMnožina hráčů {1,2}Strategie hráčů mohou být ryzí (= reálné tahy) a smíšené

(= rozložení pravděpodobností nad množinami ryzích strategií).

Množiny strategií : Ryzí strategie - R1 , R2

Smíšené strategie - S1 , S2

Výherní funkce hráčů S1 S2 R , i{1,2}

s1 , s2) je výhra hráče i {1,2}, pokud hráč 1 zvolil strategii s1S1 a hráč 2 zvolil s2S2 .

Výhry hráčů

Pro i∈{1,2} , s1S1 a s2S2 ,

R1 ={r1(1), … , rk

(1)}, R2 ={r1(2), … , rl

(2)},

i s1 , s2 =

=Σi=1,…,k, j=1,…,l i ri(1), rj

(2)·s1(ri(1))· s2(rj

(2)),

kde s1(ri(1)) a s2(rj

(2)), jsou pravděpodobnosti.

Popis výher

Výhry hráčů pak můžeme popsat dvěma maticemi, Π1 a Π2 , jejichž políčka jsou hodnoty 1ri

(1), rj(2)a 2 ri

(1), rj(2)Každá z nich uvádí

výhry příslušného hráče.

Nebo můžeme výhry hráčů zobrazit graficky jako oblast ve dvojrozměrném prostoru se souřadnicemi 1 a 2 . Oblast je ohraničená a uzavřená, každý bod v ní odpovídá některé dvojici výher (1s1 , s2,2s1 , s2) a je podmnožinou konvexního obalu bodů o souřadnicích (ri

(1), rj(2),ri

), rj(2)).

Graf pro hry, kde hráč 1 má 2 ryzí strategie a hráč 2 má 3 ryzí strategie

*** Každý bod uvnitř oblasti obsahuje jednu dvojici výher pro každého z hráčů.

Hvězdičky označují vektory výher pro dvojice ryzích strategií.

Oblast může být menší než jejich konvexní obal.

((ri(1),rj

(2)), (ri(1),rj

(2)))

(s1,s2,s1,s2)

Matice pro hru, kde každý hráč má 2 ryzí strategie

Π1 r1(1) r2

(1)

r1(2) 1r1

(1),r1(2) 1r2

(1),r1(2)

r2(2) 1r1

(1),r2(2) 1r2

(1),r2(2)

Π2 r1(1) r1

(1)

r1(1)

2r1(1),r1

(2) 2r2(1),r1

(2)

r1(1)

2r1(1),r2

(2) 2r2(1),r2

(2)

Nejznámější řešení strategické hry

Garanční (minimaxové) řešení: dvojice strategií (s‘1 ,s‘2) ∈ S1S2 , taková, že

1(s‘1 ,s‘2) = max[min(1 (s1,s2):s2∈ S2): s1∈ S1],

2(s‘1 ,s‘2) = max[min(2 (s1,s2):s1∈ S1): s2∈ S2]

(J. von Neumann, O. Morgenstern).

Rovnovážné řešení: dvojice (s*1 ,s*2)∈S1S2 , taková, že

∀(s1∈S1): 1(s*1 ,s*2) ≥ 1(s1 ,s*2),

∀(s2∈S2): 2(s*1 ,s*2) ≥ 2(s*1 ,s2),(J. von Neumann, O. Morgenstern, J. F. Nash).

Hodnota hry pro hráče

Při zachování dosavadního značení nazveme čísla

v(1)= 1(s‘1 ,s‘2) a v(2)= 2(s‘1 ,s‘2) (hodnoty výher obou hráčů při uplatnění

garančních strategií) hodnotami hry pro hráče 1 a pro hráče 2.

Strategie s‘1 a s‘2 nazýváme garančními strategiemi hráčů.

Hodnoty hry představují zaručenou výhru každého hráče, pokud se bude chovat dostatečně „rozumně“ a zabezpečí se svou garanční strategií proti jakémukoliv chování protivníka.

Slavný příklad: DILEMA VĚZNĚ:ryzí strategie – r1= Přiznat, r2 = Nepřiznat

Π1P N

P(P,P)

-12

(N,P)

-20

N(P,N)

0

(N,N)

-1

Π2

P N

P (P,P)

-12

(N,P)

0

N (P,N)

-20

(N,N)

-1

DILEMA VĚZNĚ - Graf výher

*** Garanční i rovnovážné řešení je (P,P), i když se intuitivně jeví jako nesmyslné.

Je ale jediné stabilní – žádný hráč je nemůže jednostranně zlepšit a zabezpečuje každého z hráčů proti všem možným akcím protihráče.

Spolupráce není možná

00

(P,P)

(N,P)

(P,N)

(N,N)

v(1)= -12

v(2)= -12

Jiná úloha: PARTNERSKÝ SPOR ryzí strategie – r1= Kino, r2 = Fotbal

ΠONK F

K(K,K)

5

(F,K)

3

F(K,F)

0

(F,F)

10

ΠONA

K F

K(K,K)

10

(F,K)

3

F(K,F)

0

(F,F)

5

PARTNERSKÝ SPOR – Graf výher

*** Garanční řešení je (F,K), rovnovážná řešení jsou dvě, (K,K) a (F,F).

Garanční řešení sice zaručuje, že „se nic horšího nemůže stát“, je ale značně neuspokojivé.

0

(K,K)

(F,F)(F,K)

(K,F)

v(1)= 5

v(2)= 5

Jsou nabízená řešenírozumná?

Pokud se nemohou oba partneři domluvit, budou se nejspíš chovat garančně a může se stát, že půjdou každý jinam (a dokonce každý tam, kam nechtěl).

Je proto v jejich zájmu, vybrat nějak (třeba i náhodně) jenom mezi rovnovážnými možnostmi (K,K) a (F,F). Jinými slovy, mezi vektory výher (5,10) a (10,5).

To ale bez dohody nejde!

Cesta k dohodě

Rozumné dohody mohou být jenom ty, jejichž „výhry“ leží na čárkované spojnici.

Například náhodný pokus s pravděpodobnostmi P(K,K) a P(F,F) (třeba ½, ½) – s výsledkem označeným zeleně.

To ale už není dvojice strategií jednotlivých hráčů, ale společná strategie koalice.

***

(F,K)

(K,K)

(F,F)

Koaliční (kooperativní) hra

Množina hráčů: I ,Koalice: K⊂I .Z hlediska každé koalice K≠∅ se hra stává hrou

dvou hráčů: K, a I–K , pro které je možné pomocí garančního řešení odvodit jejich hodnotu hry v.

Hodnota hry pro koalici K⊂I , K≠∅, je v(K).

Kromě toho se definuje v(∅)=0.

Kooperativní hra - (I,v)

Důležité typy kooperativních her

Kooperativní hra (I,v) je:Superaditivní, jestliže

∀(K,L⊂I): K∩L=∅ ⇒ v(K⋃L) ≥ v(K)+v(L).Subaditivní, jestliže

∀(K,L⊂I): K∩L=∅ ⇒ v(K⋃L) ≤ v(K)+v(L).Aditivní, jestliže

∀(K,L⊂I): K∩L=∅ ⇒ v(K⋃L) = v(K)+v(L).Konvexní, jestliže

∀(K,L⊂I): v(K⋃L)+v(K∩L) ≥ v(K)+v(L).

Řešení kooperativní hry – jádro hry

Označme #I = n.Reálný vektor x=(xi)i∈I ∈ Rn nazveme podílovým

vektorem, jestliže

Σi∈I xi ≤ v(I) .

(Množina všech hráčů ho může uskutečnit.)

Jádro hry je množina reálných vektorů

C(I,v) = {x=(xi)i∈I ∈ Rn: Σi∈I xi ≤ v(I) a

∀(K⊂I): Σi∈K xi ≥v(K)}.

(Je to množina všech podílových vektorů, proti kterým nemůže vznést účinné námitky žádná koalice.)

Vlastnosti jádra hry

Jen ty hlavní:Nemusí být nutně neprázdné.Pokud je neprázdné, je to konvexní a uzavřená podmnožina Rn .Pro konvexní hry je vždy neprázdné (ale nemusí tomu být naopak – např. I={1,2,3} v(I)=6, v(i,j)=4, v(i)=1).Existuje nutná a postačující podmínka pro neprázdnost jádra.

Kdy může vzniknout spolupráce ?

K tomu, aby hráči byli ochotni uzavřít koalici, je potřeba splnit dvě podmínky:Musí hráčům nabídnout takový podíl na výhře, aby jim žádná odštěpená koalice nemohla nabídnout víc.Taková nabídka musí být splnitelná.

To ale má dva háčky:Hráči musí mít realistickou představu o očekávaných výhrách koalic (hodnotách v(K)).Nabízené rozdělení výhry mezi hráče jim musí připadat alespoň přijatelně „spravedlivé“.

Na druhou podmínku se podíváme blíž.

Hodnota koaliční hry pro hráče

Pokud je jádro neprázdné, bývá jen málokdy jednoprvkové.

Každý z jeho vektorů je pro všechny hráče lepší (nebo není horší) než nespolupracovat vůbec.

Přesto mají hráči zcela odlišné představy, který z nich je „spravedlivý“.

Je tedy nutná existence nějakého kompromisu.Výsledkem je vektor s=(si)i∈I ∈ Rn , který stanovuje

„kompromisní“ podíl každého hráče. Nazývá se hodnota koaliční hry.

Jaké vlastnosti má mít hodnota koaliční hry

Hodnoty si jsou nezávislé na pořadí, ve kterém jsou počítány. Vektor s je podílovým vektorem.Nechť (I,v) a (I,w) jsou dvě kooperativní hry hrané stejnou množinou hráčů, a nechť s∈Rn , t∈Rn jsou vektory jejich hodnot. Kooperativní hra (I,(v+w)), kde

∀(K⊂I): (v+w)(K)=v(K)+v(K),má vektor hodnot s+t=(si+ti)i∈I .

Shapleyova hodnota hry

R. Shapley dokázal, že existuje jediný vektor, který splňuje uvedené podmínky. Pro každého hráče i∈I je definován vztahem

si = ΣK⊂I,K≠∅ [n!·(n-k)! / k!]·(v(K)-v(K-{i})).

Shapleyova hodnota není jediný pokus o definování jednoznačného výsledku dohody koalice všech hráčů, díky splnění předchozích podmínek (a díky vlastnostem, které hned uvedeme) je nejuznávanější.

Další vlastnosti Shapleyovy hodnoty

Pokud je jádro hry C(I,v) neprázdné, je Shapleyova hodnota jeho prvkem,

s=(si )i∈I ∈ C(I,v).Je vyváženým rozdělením zisku „podle zásluh“ (je to jakési těžiště jádra hry).Pokud je C(I,v) prázdné, splňuje vektor Shapleyových hodnot s pořád definiční požadavky (včetně toho, že je podílovým vektorem). Jen je „vyváženě nepřijatelný“ pro všechny hráče. Je tedy nejvhodnějším východiskem, pokud jsou hráči ke spolupráci nuceni.

Poučení do životaPoučení do života

Aby hráči správně rozhodli o spolupráci, musí mít dobrou představu o výhrách možných koalic (přitom vyjednávání probíhá před realizací hry a tedy dřív, než je znám skutečný výsledek).K tomu, aby poznali výhodnost spolupráce před konfliktem, jim stačí znalost pravidel hry (množina hráčů, výherní funkce, případně množina přípustných koalic) a znalost vlastních preferencí.Ke „spravedlivému“ rozdělení výhry už ale samotná pravidla hry nestačí. Musí existovat „soudce“ – buď osoba arbitra nebo respektované neosobní pravidlo typu Shapleyovy hodnoty. To už je něco navíc k pravidlům i k preferencím hráčů.

Děkuji za výdrž