Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Wstęp do teorii gier – 8. Równowagi skorelowane – MIM UW

Zagadnienia

8. Równowagi skorelowane

8.1. Wprowadzenie

Równowaga skorelowana (RS), wprowadzona przez R. Aumanna w 1974 r. jest uogólnieniem RN dla gier w których występują korelacje w odbiorze sygnałów (o stanie świata) przez graczy. Pojęcie to wymaga wprowadzenia zewnętrznego informatora (”koordynatora”, ”choreografa”), przysyłającego sygnały wpływające na decyzje graczy o wyborze strategii. Model który pozwoli na zdefiniowanie RS dopuszcza aby gracze podejmowali swoje decyzje stosując pewien stochastyczny mechanizm koordynacji wyboru akcji. W szczególności jeżeli taki mechanizm będzie asymetryczny, czyli będzie dawał inne sygnały różnym graczom, to uzyskiwane przez graczy wypłaty mogą być wyższe niż osiągalne w jakiejkolwiek istniejacej w danej grze RN.

8.2. Przykłady

Przykład 8.1

\

Rozważmy dwuosobową GS o macierzy wypłat
L R
U 5,1 0,0
D 4,4 1,5

Gra ma 3 RN: (U,L),(D,R),((1/2,1/2),(1/2,1/2). Wypłata każdego gracza z mieszanej RN wynosi 2\frac{1}{2}.

Załóżmy że gracze obserwują jednoczesnie ciąg realizacji zmiennej losowej: rzut monetą symetryczną, i że grają po każdej realizacji w nastepujący sposób:

Gracz 1: U jeśli wypadnie orzeł, D jeśli reszka.

Gracz 2: L jeśli wypadnie orzeł, R jeśli reszka.

Wtedy każdy ma średnią wypłatę 3.

Uwaga 8.1

Rozważmy wypukłą kombinację liniową wypłat w czysrych RN:

\lambda(5,1)+(1-\lambda)(1,5)=(4\lambda+1,5-4\lambda) (8.1)

Wartość \lambda możemy interpretować jako stopień symetrii monety–prawdopodobieństwa że wypadnie orzeł. Dla odpowiednio niesymetrycznej monety gracze mogą mieć każdą wypłatę z wypukłej kombinacji liniowej czystych RN.

Okazuje się że mając do dyspozycji pewne ”urządzenie” generujące określone sygnały (”urządzenie korelujące”) i różnicując w odpowiedni sposób informację otrzymywaną z tego urządzenia obaj gracze moga otrzymać wyższe wypłaty niż 3. Niech urządzenie generuje z jednakowym prawdopodobieństwem 3 sygnały: A,B,C. Załóżmy że jeśli zaszło A to gracz 1 wie że zaszło A, jeśli B lub C to przypisuje każdemu z nich prawdopodobieństwo 1/2. Załóżmy że jeśli zaszło C to 2 wie że zaszło C, a jeśli A lub B to przypisuje każdemu z nich prawdopodobieństwo 1/2.

Niech 1 gra U gdy zaszło A, D gdy B lub C. Niech 2 gra R gdy zaszło C, L gdy A lub B.

Jeżeli zaszlo A to 1 wie że 2 wie że zaszło A lub B, więc wie że 2 zagra L. U jest najlepszą odpowiedzią gracza 1.

Jesli zaszło B lub C to 1 wie tylko że zaszło jedno z nich z prawdopodobieństwem 1/2, czyli wie że 2 zagra L z prawdopodobieństwem 1/2 i R z prawdopodobieństwem 1/2. Ponieważ wypłata 1 jest wtedy równa 2.5 zarówno z D jak i z U, więc jest tez najlepszą odpowiedzią.

Dla gracza 2 rozumowanie jest analogiczne.

Skonstruowaliśmy nową grę, w której strategie to ciągi trzyelementowe o wyrazach: U, D dla gracza 1, R, L dla gracza 2. Para strategii: 1 gra U gdy zaszło A, D gdy B lub C. Niech 2 gra R gdy zaszło C, L gdy A lub B jest równowaga Nasha.

Mówimy że w tej równowadze akcje graczy są skorelowane. Ponieważ A, B, C zachodzą z prawdopodobieństwem 1/3 każde, więc w tej równowadze pary akcji (U,L), (D,L) i (D,R) sa grane z prawdopodobieństwem 1/3 każda, a para (U,R) nigdy. W tej nowej równowadze średnia wypłata każdego gracza jest równa 3 1/3, gdyż:

\bar{u}_{1}=\frac{1}{3}(u_{1}(U,L)+u_{1}(D,L)+u_{1}(D,R))=\frac{10}{3},
\bar{u}_{2}=\frac{1}{3}(u_{2}(U,L)+u_{2}(D,L)+u_{2}(D,R))=\frac{10}{3},
Uwaga 8.2

Para s^{*}=(s_{1}^{*},s_{2}^{*})=((D,D,D),(L,L,L)) nie jest równowagą Nasha. Mamy u_{1}(s^{*})=1/3(4+4+4)=4, ale gdy 1 zmieni strategię na s_{1}=(U,U,U), to u_{1}((s_{1},s_{2}^{*}))=1/3(5+5+5)=5.

Uwaga 8.3

Analogicznie jak w poprzednim przykładzie, zmieniając rozkład prawdopodobieństwa zdarzeń: p(A)=\alpha,p(B)=\beta,p(C)=1-\alpha-\beta możemy uzyskać dowolna wypłatę z wypukłej kombinacji \alpha(5,1)+\beta(1,5)+(1-\alpha-\beta)(4,4).

Przykład 8.2 (”Niekiedy jest lepiej wiedzieć mniej”)

Podamy przykład w którym jeden z graczy (trzeci) ograniczy swoją informację, a pozostali gracze będąc o tym poinformowani będa zmuszeni do zagrania w pożądany przez trzeciego gracza sposób, podwyższając wypłate wzystkich graczy w stosunku do wypłaty z RN.

Rozważmy grę trzyosobowa, w której gracz 1 gra wierszami, 2 kolumnami a 3 macierzami. Macierze wypłat graczy 1,2,3 mają postać odpowiednio:
L R
U 0,1,3 0,0,0
D 1,1,1 1,0,0

L R
U 2,2,2 0,0,0
D 2,2,0 2,2,2
L R
U 0,1,0 0,0,0
D 1,1,0 1,0,2

Jedyną RN jest (D,L,A), w której każdy gracz otrzymuje wypłatę 1. Niech urządzeniem korelującym będzie symetryczna moneta z wunikami O, R. Niech 1 i 2 znają wynik rzutu, a 3 nie. Otrzymujemy nową grę w której strategie graczy to odpowiednie pary akcji: np. dla gracza 1 są 4 strategie: pary (U,U), (U,D), (D,U), (D,D); dla gracza 3 strategie to pary macierzy. Pierwszy element pary to macierz którą gra 3 gdy wypadnie O, drugi–gdy R. Gracz 3 ma 8 strategii.

Stwierdzenie 8.1

RN to trójka strategii (s_{1},s_{2},s_{3}):

s_{1}: graj U jeśli O, D jeśli R

s_{2}: graj L jeśli O, R jeśli R.

s_{3}: graj drugą macierzą jeśli O, drugą macierzą jeśli R (czli graj zawsze drugą macierzą).

Pokażemy że strategia każdego gracza to najlepsza odpowiedż.

Gracz 1:

jeśli O to 1 wie że 2 wie że O i że 2 gra L, 3 gra drugą macierzą, a więc U daje najwyższą wypłatę.

jeśli R to 1 wie że 2 wie że R i że 2 gra R, 3 gra drugą macierzą, a więc D daje najwyższą wypłatę.

Tak więc strategia s_{1} jest najlepszą odpowiedzią.

Gracz 2: analogicznie. Najwyższe wypłaty dają odpowiednio L przy O i R przy R.

Gracz 3:

wie że para graczy (1,2) gra (U,L) z prawdopodobieństwem 1/2, (D,R) z prawdopodobieństwem 1/2. Najwyższą wypłatę, równą 2, daje mu gra drugą macierzą (gracze 1 i 2 otrzymuja też po 2).

Uwaga 8.4

Ważne jest że 1 i 2 wiedzą że 3 ma ograniczoną informację, tzn. że wiedzą że 3 nie wie czy wypadł O czy R. Gdyby 3 wiedział, czyli miał taką samą informację jak 1 i 2, to grałby nastepującą strategią \tilde{s}_{3}: graj pierwszą macierza jeśli O, trzecią jeśli R. Wtedy (s_{1},s_{2},\tilde{s}_{3}) nie byłaby RN, gracze wróciliby wtedy do RN (s_{1},s_{2},s_{3}) z wypłatami po 1 dla każdego.

8.3. Definicja równowagi skorelowanej

Rozważmy GS:\left\langle N,(A_{i})_{{i\in N}},(u_{i})_{{i\in N}}\right\rangle. Zdefiniujemy ”rozszerzoną” gre, strategie i RN dla gry rozszerzonej. Wpierw zdefiniujemy

Definicja 8.1

Urządzenie korelujące jest to trójka (\Omega,\{ H_{i}\},i\in N,p), gdzie:

\Omega–skończony zbiór (stanów świata). W powyższych przykładach odpowiada realizacjom odpowiedniej zmiennej losowej.

\{ H_{i}\}–podział \Omega dla gracza i\in N. Podział \{ H_{i}\} opisuje informację gracza i o realizacji zmiennej losowej (”zajściu stanu”). Jeśli zaszedł \omega\in\Omega to gracz i wie że stan który zaszedł leży w H_{i}, gdzie H_{i} jest elementem podziały H_{i} takim że \omega\in H_{i}.

Podział \{ H_{i}\} przyporządkowuje każdemu \omega\in\Omega zbiór H_{i} t. że \omega\in H_{i}.

Uwaga 8.5

W Przykładzie 8.1 \Omega=\{ A,B,C\},H_{1}=\{\{ A\},\{ B,C\}\},H_{2}=\{\{ A,B\},\{ C\}\}.

W Przykładzie 8.2 \Omega=\{ O,R\},H_{1}=H_{2}=\{\{ O\},\{ R\}\},H_{3}=\Omega.

p–miara probabilistyczna na \Omega.

Zdefiniujemy strategie czyste graczy:

Definicja 8.2

Strategia gracza i jest to funkcja s_{i}:\Omega\rightarrow A_{i}: jeżeli \omega,\omega^{{{}^{{\prime}}}}\in h_{i}(\omega) dla pewnego h_{i}\in H_{i}, to s_{i}(\omega)=s_{i}(\omega^{{{}^{{\prime}}}}).

Tak więc jeżeli \omega,\omega^{{{}^{{\prime}}}}\in h_{i}(\omega), to strategia s_{i} implikuje tę samą akcję gracza i zarówno jeżeli zaszło \omega, jak i jeżeli zaszło \omega^{{{}^{{\prime}}}}. Mówimy że strategie gracza i są adoptowane do jego zbioru informacyjnego (czyli do podziału H_{i}).

Definicja 8.3

(s_{1},...,s_{N}) jest równowagą skorelowana gdy \forall j\forall\tilde{s}_{i} (dla każdej strategii adaptowanej)

\sum _{{\omega\in\Omega}}p(\omega)u_{i}(\tilde{s}_{i}(\omega,s_{{-i}}(\omega))\le\sum _{{\omega\in\Omega}}p(\omega)u_{i}(s_{i}(\omega),s_{{-i}}(\omega)).
Uwaga 8.6

1. W tej definicji p jest takie same dla każdego gracza i. Taką RS nazywamy obiektywną. Jeżeli dla każdego gracza mielibyśmy określona miarę p_{i}, to taką RS nazwiemy subiektywna.

2. p,p_{i} nazywamy przekonaniami (beliefs) graczy.

Powyższa definicja RS zależy od urządzenia korelacyjnego. Podamy definicje równoważną.

Definicja 8.4

Równowagą skorelowaną nazywamy (każdy) rozkład prawdopodobieństwa na A:=\prod A_{i} t. że \forall i oraz dla każdej funkcji d_{i}:A_{i}\rightarrow A_{i}

\sum _{{a\in A}}p(a)u_{i}(d_{i}(a_{i}),a_{{-i}})\le\sum _{{a\in A}}p(a)u_{i}(a_{i},a_{{-i}}). (8.2)
Przykład 8.3

W grze walka płci o macierzy wypłat
B S
B 2,1 0,0
S 0,0 1,2

niech \Omega=\{ x,y\},p(x)=p(y)=1/2,H_{1}=H_{2}=\{\{ x\},\{ y\}\}. RS stanowi para strategii adaptowanych s_{i}(x)=B,s_{i}(y)=S,\  i=1,2 Tę RS można interpretować tak że gracze obserwują wynik rzutu monetą symetryczna który wyznacza która z RN będzie grana.

Przykład 8.4 (RS a programowanie liniowe)

Rozważmy dwuosobową GS o macierzy wypłat (patrz Przykład 8.1)
L R
U 5,1 0,0
D 4,4 1,5

Zdefiniujemy rodzinę urządzeń korelujących. Niech \Omega=\{\omega _{1},\omega _{2},\omega _{3}\},

H_{1}=\{\{\omega _{1}\},\{\omega _{2},\omega _{3}\}\},H_{2}=\{\{\omega _{1},\omega _{2}\},\{\omega _{3}\}\},

p(\omega _{1})=\alpha,p(\omega _{2})=\beta,p(\omega _{3})=1-\alpha-\beta:\alpha,\beta\ge 0,\alpha+\beta\le 1.

Znajdziemy odpowiednie równowagi skorelowane. Rozważmy parę strategii adaptowanych

s_{1}: graj U gdy \omega\in\{\omega _{1}\} (czyli \omega=\omega _{1}), D gdy \omega\in\{\omega _{2},\omega _{3}\},

s_{1}: graj L gdy \omega\in\{\omega _{1},\omega _{2}\}, R gdy \omega\in\{\omega _{3}\}.

Znajdziemy \alpha,\beta dla których (s_{1},s_{2}) jest Rn w grze rozszerzonej.

Rozważmy wpierw gracza 1. Jeśli \omega=\omega _{1} to 1 wie że 2 zagra L, więc U daje najwyższą wypłatę, a zatem s_{1} jest najlepszą odpowiedzią. Jeśli \omega=\omega _{2} to 1 wie tylko że \omega\in\{\omega _{2},\omega _{3}\}. Gracz 1 nie wie czy zaszło \omega _{2} czy \omega _{3} (a zatem czy 2 zagra L czy R) i oblicza te prawdopodobieństwa z wzoru Bayesa : p(\omega _{2}|\omega _{2}\vee\omega _{3})=\frac{\beta}{\beta+1-\alpha-\beta}=\frac{\beta}{1-\alpha},

p(\omega _{3}|\omega _{2}\vee\omega _{3})=\frac{1-\alpha-\beta}{1-\alpha}.

Inaczej mówiąc, gracz 1 gra przeciw strategii mieszanej gracza 2: (p(\omega _{2}|\omega _{2}\vee\omega _{3}),p(\omega _{3}|\omega _{2}\vee\omega _{3})) i jego wypłata wynosi:

z U: 5\frac{\beta}{1-\alpha}+0,

z D: 4\frac{\beta}{1-\alpha}+1\frac{1-\alpha-\beta}{1-\alpha}.

Aby para strategii adaptowanych (s_{1},s_{2}) była RN, wypłata gracza 1 z D musi być nie mniejsza niż z U, co daje warunek

1\ge\alpha+2\beta. (8.3)

Jeśli \omega=\omega _{3} to dla gracza 1 otrzymujemy ten sam warunek.

Gracz 2:

Jeśli zaszło \omega _{1} to gracz 2 wie tylko, że zaszło \omega _{1} lub \omega _{2}, a więc wie że gracz 1 gra:

U z prawdopodobieństwem p(\omega _{1}|\omega _{1}\vee\omega _{2})=\frac{\alpha}{\alpha+\beta},

D z prawdopodobieństwem p(\omega _{2}|\omega _{1}\vee\omega _{2})=\frac{\beta}{\alpha+\beta}.

Wypłaty gracza 2 przeciwko tej strategii mieszanej to:

z L: 1\frac{\alpha}{\alpha+\beta}+4\frac{\beta}{\alpha+\beta},

z R: 0+5\frac{\alpha}{\alpha+\beta}.

Aby s_{2} było najlepszą odpowiedzią, wypłata z l musi być nie mniejsza niż z R, co implikuje nierówność:

1\ge\alpha+2\beta. (8.4)

Jeśli zaszło \omega _{2} to otrzymujemy identyczny warunek.

Jeśli zaszło \omega _{3} to gracz 2 wie że zaszło \omega _{3}, czyli że gracz 1 gra D, a więc gracz 2 zagra R. Tak więc s_{2} jest najlepszą odpowiedzią.

Wniosek 8.1

Dla każdej pary liczb \alpha\ge 0,\beta\ge 0:\alpha+\beta\le 1: spełniającej warunki 8.3, 8.4 określona powyżej para strategii adaptowanych (s_{1},s_{2}) jest RS.

Srednie wypłaty graczy w tych równowagach:

Pamiętając że p(\omega _{1})=p(U,L)=\alpha,p(\omega _{2}=p(D,L)=\beta,p(\omega _{3})=p(D,R)=1-\alpha-\beta, znajdujemy średnie wypłaty obu graczy:

(u_{1},u_{2})=(5,1)p(\omega _{1})+(1,5)p(\omega _{2})+(4,4)p(\omega _{3})=(4\alpha+3\beta+1,5-4\alpha-\beta), (8.5)

przy warunkach 8.3, 8.4. Jest to zagadnienie programowania liniowego. Rozwiązaniem są, w pierwszej ćwiartce układu współrzędnych o osiach u_{1},u_{2}, odcinki łączące punkty (1,5) z (10/3,10/3) oraz (10/3,10/3) z (5,1). Każdy punkt obu odcinkow odpowiada pewnej równowadze Pareto-optymalnej. W szczególności punkt (10/3,0/3) odpowiada wyborowi \alpha=\beta=1/3.

Zachodzi interesujące twierdzenie, które podamy bez dowodu (patrz [18]):

Twierdzenie 8.1

Każda wypukła kombinacja liniowa profili wypłat w RS jest profilem wypłat pewnej RS.

Ćwiczenie 8.1

Znajdź urządzenie korelacyjne i RS w grze trzyosobowej (patrz podobny przykład 8.2) w której gracz 1 gra wierszami, 2 kolumnami a 3 macierzami. Macierze A, B, C wypłat graczy 1,2,3 mają postać odpowiednio:
A L R
T 0,0,3 0,0,0
B 1,0,0 0,0,0

B L R
T 2,2,2 0,0,0
B 0,0,0 2,2,2
C L R
T 0,0,0 0,0,0
B 0,1,0 0,0,3

Pokaż że RN w wyjściowej GS to (B,L,A),(B,L,C),(T,R,A),((T,R,C). Pokaż że istnieje RS w której gracz 3 gra B, gracze 1 i 2 graja (T,L) i (B,R) z prawdopodobieństwami 1/2. Wyjaśnij w jakim sensie gracz 3 woli nie wiedzieć że gracze 1 i 2 koordynują swoje akcje.

Rozwiązanie: 

Urządzenie korelujące: \Omega=\{ x,y\},H_{1}=H_{2}=\{\{ x\},\{ y\}\},H_{3}=\Omega,p(x)=p(y)=1/2.

RS: Trójka strategii: (s_{1},s_{2},s_{3}):

s_{1}(\{ x\})=T,\  s_{1}(\{ y\})=B,

s_{2}(\{ x\})=L,\  s_{1}(\{ y\})=R,

s_{3}(\Omega)=L.

Uwaga 8.7

Gracz 3 wie że pary akcji gracza 1 i 2: (T,L) i (B,R) zachodzą z jednakowymi prawdopodobieństwami, więc jesli zmieni akcję na A lub C to otrzyma 3/2<2.

Niech urządzeniem korelującym będzie symetryczna moneta z wynikami O, R. Niech 1 i 2 znają wynik rzutu, a 3 nie. Otrzymujemy nową gre w której strategie graczy to odpowiednie pary akcji: np. dla gracza 1 są 4 strategie: pary (U,U), (U,D), (D,U), (D,D); dla gracza 3 strategie to pary macierzy. Pierwszy element pary to macierz która gra 3 gdy wypadnie O, drugi–gdy R. Gracz 3 ma 8 strategii.

Stwierdzenie 8.2

RN to trójka strategii (s_{1},s_{2},s_{3}):

s_{1}: graj U jeśli O, D jeśli R

s_{2}: graj L jeśli O, R jeśli R.

s_{3}: graj drugą macierzą jeśli O, drugą macierzą jeśli R (czli graj zawsze drugą macierzą).

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.