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⁢12.

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:

λ⁢5,1+1-λ⁢1,5=4⁢λ+1,5-4⁢λ

(8.1)

Wartość λ 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ż:

u¯1=13⁢u1⁢U,L+u1⁢D,L+u1⁢D,R=103,

u¯2=13⁢u2⁢U,L+u2⁢D,L+u2⁢D,R=103,

Uwaga 8.2

Para s*=s1*,s2*=D,D,D,L,L,L nie jest równowagą Nasha. Mamy u1⁢s*=1/3⁢4+4+4=4, ale gdy 1 zmieni strategię na s1=U,U,U, to u1⁢s1,s2*=1/3⁢5+5+5=5.

Uwaga 8.3

Analogicznie jak w poprzednim przykładzie, zmieniając rozkład prawdopodobieństwa zdarzeń: p⁢A=α,p⁢B=β,p⁢C=1-α-β możemy uzyskać dowolna wypłatę z wypukłej kombinacji α⁢5,1+β⁢1,5+1-α-β⁢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 s1,s2,s3:

s1: graj U jeśli O, D jeśli R

s2: graj L jeśli O, R jeśli R.

s3: 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 s1 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ą s~3: graj pierwszą macierza jeśli O, trzecią jeśli R. Wtedy s1,s2,s~3 nie byłaby RN, gracze wróciliby wtedy do RN s1,s2,s3 z wypłatami po 1 dla każdego.

8.3. Definicja równowagi skorelowanej

Rozważmy G⁢S:N,Aii∈N,uii∈N. Zdefiniujemy ”rozszerzoną” gre, strategie i RN dla gry rozszerzonej. Wpierw zdefiniujemy

Definicja 8.1

Urządzenie korelujące jest to trójka Ω,Hi,i∈N,p, gdzie:

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

Hi–podział Ω dla gracza i∈N. Podział Hi opisuje informację gracza i o realizacji zmiennej losowej (”zajściu stanu”). Jeśli zaszedł ω∈Ω to gracz i wie że stan który zaszedł leży w Hi, gdzie Hi jest elementem podziały Hi takim że ω∈Hi.

Podział Hi przyporządkowuje każdemu ω∈Ω zbiór Hi t. że ω∈Hi.

Uwaga 8.5

W Przykładzie 8.1 Ω=A,B,C,H1=A,B,C,H2=A,B,C.

W Przykładzie 8.2 Ω=O,R,H1=H2=O,R,H3=Ω.

p–miara probabilistyczna na Ω.

Zdefiniujemy strategie czyste graczy:

Definicja 8.2

Strategia gracza i jest to funkcja si:Ω→Ai: jeżeli ω,ω′∈hi⁢ω dla pewnego hi∈Hi, to si⁢ω=si⁢ω′.

Tak więc jeżeli ω,ω′∈hi⁢ω, to strategia si implikuje tę samą akcję gracza i zarówno jeżeli zaszło ω, jak i jeżeli zaszło ω′. Mówimy że strategie gracza i są adoptowane do jego zbioru informacyjnego (czyli do podziału Hi).

Definicja 8.3

s1,…,sN jest równowagą skorelowana gdy ∀j⁢∀s~i (dla każdej strategii adaptowanej)

∑ω∈Ωp(ω)ui(s~i(ω,s-i(ω))≤∑ω∈Ωp(ω)ui(si(ω),s-i(ω)).

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ę pi, to taką RS nazwiemy subiektywna.

2. p,pi 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:=∏Ai t. że ∀i oraz dla każdej funkcji di:Ai→Ai

∑a∈Ap⁢a⁢ui⁢di⁢ai,a-i≤∑a∈Ap⁢a⁢ui⁢ai,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 Ω=x,y,p⁢x=p⁢y=1/2,H1=H2=x,y. RS stanowi para strategii adaptowanych si⁢x=B,si⁢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 Ω=ω1,ω2,ω3,

H1=ω1,ω2,ω3,H2=ω1,ω2,ω3,

p(ω1)=α,p(ω2)=β,p(ω3)=1-α-β:α,β≥0,α+β≤1.

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

s1: graj U gdy ω∈ω1 (czyli ω=ω1), D gdy ω∈ω2,ω3,

s1: graj L gdy ω∈ω1,ω2, R gdy ω∈ω3.

Znajdziemy α,β dla których s1,s2 jest Rn w grze rozszerzonej.

Rozważmy wpierw gracza 1. Jeśli ω=ω1 to 1 wie że 2 zagra L, więc U daje najwyższą wypłatę, a zatem s1 jest najlepszą odpowiedzią. Jeśli ω=ω2 to 1 wie tylko że ω∈ω2,ω3. Gracz 1 nie wie czy zaszło ω2 czy ω3 (a zatem czy 2 zagra L czy R) i oblicza te prawdopodobieństwa z wzoru Bayesa : p(ω2|ω2∨ω3)=ββ+1-α-β=β1-α,

p(ω3|ω2∨ω3)=1-α-β1-α.

Inaczej mówiąc, gracz 1 gra przeciw strategii mieszanej gracza 2: (p(ω2|ω2∨ω3),p(ω3|ω2∨ω3)) i jego wypłata wynosi:

z U: 5⁢β1-α+0,

z D: 4⁢β1-α+1⁢1-α-β1-α.

Aby para strategii adaptowanych s1,s2 była RN, wypłata gracza 1 z D musi być nie mniejsza niż z U, co daje warunek

1≥α+2⁢β.

(8.3)

Jeśli ω=ω3 to dla gracza 1 otrzymujemy ten sam warunek.

Gracz 2:

Jeśli zaszło ω1 to gracz 2 wie tylko, że zaszło ω1 lub ω2, a więc wie że gracz 1 gra:

U z prawdopodobieństwem p(ω1|ω1∨ω2)=αα+β,

D z prawdopodobieństwem p(ω2|ω1∨ω2)=βα+β.

Wypłaty gracza 2 przeciwko tej strategii mieszanej to:

z L: 1⁢αα+β+4⁢βα+β,

z R: 0+5⁢αα+β.

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

1≥α+2⁢β.

(8.4)

Jeśli zaszło ω2 to otrzymujemy identyczny warunek.

Jeśli zaszło ω3 to gracz 2 wie że zaszło ω3, czyli że gracz 1 gra D, a więc gracz 2 zagra R. Tak więc s2 jest najlepszą odpowiedzią.

Wniosek 8.1

Dla każdej pary liczb α≥0,β≥0:α+β≤1: spełniającej warunki 8.3, 8.4 określona powyżej para strategii adaptowanych s1,s2 jest RS.

Srednie wypłaty graczy w tych równowagach:

Pamiętając że p(ω1)=p(U,L)=α,p(ω2=p(D,L)=β,p(ω3)=p(D,R)=1-α-β, znajdujemy średnie wypłaty obu graczy:

u1,u2=5,1⁢p⁢ω1+1,5⁢p⁢ω2+4,4⁢p⁢ω3=4⁢α+3⁢β+1,5-4⁢α-β,

(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 u1,u2, 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 α=β=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: Ω=x,y,H1=H2=x,y,H3=Ω,p⁢x=p⁢y=1/2.

RS: Trójka strategii: (s1,s2,s3):

s1⁢x=T,⁢s1⁢y=B,

s2⁢x=L,⁢s1⁢y=R,

s3⁢Ω=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