Zagadnienia

8.1 Wprowadzenie
8.2 Przykłady
8.3 Definicja równowagi skorelowanej

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