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 – 6. Gry Bayesa – MIM UW

Zagadnienia

6. Gry Bayesa

6.1. Uwagi wstępne

W dotychczas rozpatrywanym modelu gry strategicznej gracze którzy podejmowali decyzje mieli pełną informację dotyczącą gry, w szczególności znali macierze wypłat wszystkich graczy. W wielu rzeczywistych sytuacjach w ekonomii, w polityce, w konfliktach militarnych, w relacjach społecznych gracze mają zróznicowaną informację o pewnych aspektach gry, istotnych dla podjęcia decyzji o wyborze akcji. Gry w których przynajmniej jeden gracz posiada taka informację, tzn. nieznana conajmniej jednemu innemu graczowi, będziemy nazywać grami Bayesa (Bayesian games), albo grami z niepełną informacją. Używa się też terminu: gry z asymetryczną informacją.

W dotychczasowych rozważaniach dla GS gracze znali w szczególności akcje i wypłaty swoje i przeciwników. W rzeczywistych konfliktach często tak nie jest, walczący nie znaja siły przeciwników, firmy nie znaja kosztów produkcji konkurentów, uczestnicy aukcji nie znają waluacji obiektu aukcji przez innych uczestników aukcji. W grach opisujących takie sytuacje dochodzi więc element ryzyka związany z niepełną informacją.

W grach Bayesa definicja równowagi Nasha musi zostać zmieniona tak aby uwzględnić zróżnicowaną informację graczy o grze. Odpowiednie uogólnienie pojęcia równowagi będziemy nazywali równowagą Nasha–Bayesa, lub po prostu równowagą Bayesa. W takiej równowadze akcje graczy będa optymalne (będą najlepszymi odpowiedziami) przy ich określonych przekonaniach (beliefs) dotyczących innych graczy.

W formalnym modelu gry strategicznej uwzględniającym niepełną informację dojda dodatkowe obiekty–stany świata, i subiektywne, zależne od gracza prawdopodobieństwa wystąpienia różnych stanów świata. Odpowiednim modyfikacjom ulegną wypłaty, które będą wartościami oczekiwanymi odpowiednich zmiennych losowych, i w konsekwencji pojęcia najlepszej odpowiedzi.

Uwaga 6.1

Innym rodzajem niepełnej informacji o grze może być brak informacji gracza co inni gracze wiedzą o tym co wie dany gracz na temat gry. W grach ekstensywnych, będących tematem kolejnych rozdziałów, rozważa się jeszcze inny rodzaj niepewności w grze: brak pewności jaka akcję grał ostatnio przeciwnik (przeciwnicy). Gry tego typu nazwiemy grami z niedoskonałą informacją (imperfect information).

W poniższych przykładach (por. [19]) rozważymy gry dwuosobowe w których przynajmniej jeden gracz nie będzie miał pewności na temat wypłat swojego przeciwnika czy też partnera gry.

Przykład 6.2 (Duopol Cournota z asymetryczną informacją)

Niech C_{1}(q_{1})=cq_{1} jest funkcja kosztów 1-ej firmy. Funkcja kosztów 2-ej jest równa C_{2}(q_{2})=c_{L}q_{2} z prawdopodobieństwem p, C_{2}(q_{2})=c_{H}q_{2} z prawdopodobieństwem 1-p. Informacja graczy o grze jest asymetryczna w nastepującym sensie: 2 zna C_{2} and C_{1}, 1 zna C_{1} i wie że koszt koszt wyprodukowania jednostki towaru przez firmę 2 wynosi c_{L} z prawdopodobieństwem p, c_{H} z prawdopodobieństwem 1-p. Przykładowo, firma 2 może dopiero wchodzić na rynek lub wprowadzać nową technologię produkcji rozważanego towaru. Zakładamy ”common knowledge”: 1 wie co 2 wie o grze, 2 wie że 1 wie co 2 wie o grze itd.

Przykład 6.3

Walka Płci (przy niepełnej informacji)

Rozważmy symetryczną GS: N=\{ 1,2\},A_{1}=A_{2}=\{ B,S\}. 1-y gracz to Mężczyzna, 2-i gracz to Kobieta. B oznacza Boks, S–Siatkówkę. 1 and 2 muszą zdecydować jednocześnie: wybrać B czy S.

Gracz 1 ma macierz wypłat
B S
B 2 0
S 0 1

Gracz 2 może być jednym z dwóch typów: l i h (od ang.: love, hate). Gdy jest typu l to jego macierz wypłat ma postać
B S
B 1 0
S 0 2

a gdy typu h, to
B S
B 0 2
S 1 0

W tym przykładzie gracz 1 ma tylko jeden typ. Zakładamy że przy realizacji gry każdy gracz wie jakiego jest typu.

Gracz 1 nie wie z jakim typem gracza 2 będzie grał. Zakładając prawdopodobieństwo każdego typu równe (w naszym przykładzie) 0.5 i wiedząc jaką akcję wybierze (z prawdopodobieństwem 1) gracz 2 gdy jest każdego z typów, gracz 1 może obliczyć wypłaty ze swoich strategii czystych jako wartości oczekiwane zmiennej losowej ”typ gracza 2”.

Niech para (A,B) oznacza: gracz 2 gra A gdy jest typu l, B gdy jest typu h. Otrzymujemy macierz wartości oczekiwanych wypłat gracza 1 przy danych założeniach o graczu 2:
(B,B) (B,S) (S,B) (S,S)
B 2 1 1 0
S 0 1/2 1/2 1

Zauważmy że macierz tę można traktować jako macierz wypłat pewnej gry trzyosobowej.

Za profil strategii czystych gry przyjmiemy trójkę

(X,A,B)\equiv(X,(A,B)),\  X,A,B\in\{ B,S\}.

Za profil rówowagowy (strategii czystych) przyjmiemy taki profil (X,(A,B)) dla którego:

1. Przy ustalonych akcjach (A,B) 2-ego gracza gdy jest typu odpowiednio l,h (i przy znanym graczowi 1 prawdopodobieństwie każdego typu gracza 2 (w maszym przykładzie 0.5) akcja X daje graczowi 1 maksymalna wypłatę

2. Przy ustalonej akcji X 1-ego: gdy 2-i jest typu l (typu h) to akcja A (akcja B) daje 2-emu maksymalna wypłatę.

Jak łatwo sprawdzić, w naszym przykładzie warunki te spełnia trójka (B,(B,S)).

6.2. Definicje

Definicja 6.3

Przekonanie (belief) \mu _{i} gracza i (o akcjach pozostałych graczy) jest to rozkład prawdopodobieństwa na A_{{-i}}.

Gracz i jest racjonalny jeżeli wybiera strategię a_{i} taką że

a_{i}\in argmax_{{\tilde{a}_{i}}}E_{{\mu _{i}(a_{{-i}})}}u_{i}(\tilde{a}_{i},a_{{-i}}),

czyli taką która maksymalizuje wyrażenie

\sum _{{\tilde{a}_{i}}}u_{i}(\tilde{a}_{i},a_{{-i}})\mu _{i}(a_{{-i}}).

Przykładowo \{(C,0.6),(D,0.4)\} jest przekonaniem gracza 1 w grze koordynacyjnej
C D
C 1 0
D 0 1

Gracz 1 jest racjonalny jeżeli wybiera C.

Definicja 6.4

Niech \Omega będzie zbiorem skończonym. Elementy \Omega bedziemy nazywać stanami świata. Przekonanie \mu _{i} gracza i o stanach świata jest to rozkład prawdopodobieństwa na \Omega.

Definicja 6.5

Gra Bayesowska

GB=\left\langle N,\Omega,(A_{i},T_{i},\tau _{i},p_{i},u_{i})_{{i\in N}}\right\rangle,

składa się z następujących elementów:

N=\{ 1,...n\} – skończony zbiór graczy.

\Omega – skończony zbiór stanów świata.

Dla każdego gracza i\in N określamy

  • A_{i} – zbiór akcji gracza i.

  • T_{i}=\{ t_{i}^{1},...,t_{i}^{{k_{i}}}\} – skończony zbiór k_{i} typów gracza i (sygnałów które może otrzymać). W dalszym ciągu dla uproszczenia górny wskaźnik numerujący typ będziemy pomijać.

  • \tau _{i}:\Omega\rightarrow T_{i} – funkcja sygnału gracza i. Przyporządkowuje ona stanom świata typ gracza i.

    Moc zbioru stanów które generują ryp t_{i} opisuje stopień pewności gracza i o stanie świata. Na przykład jeżeli \tau _{i}(\omega _{1})\neq\tau _{i}(\omega _{2})\ \ \forall\omega _{1},\omega _{2}\in\Omega to gracz i wie, po otrzymaniu sygnału, jaki jest stan świata (jaki stan ”zaszedł”), a zatem zna typy wszystkich graczy.

    Jeżeli natomiast \tau _{i}(\omega _{1})=\tau _{i}(\omega _{2})\ \ \forall\omega _{1},\omega _{2}\in\Omega to sygnął który otrzymuje gracz (a zatem jego typ) nie daje mu żadnej informacji o stanie świata.

    W pozostałych przypadkach informacja ma charakter częściowy. Niech np. świat ma trzy stany: \Omega=\{\omega _{1},\omega _{2},\omega _{3}\}, \ \ \tau _{i}(\omega _{1})\neq\tau _{i}(\omega _{2})=\tau _{i}(\omega _{3}). Jeżeli świat jest w stanie \omega _{1}, to gracz i wie że świat jest w stanie \omega _{1}, jesli \omega _{2} lub \omega _{3} to gracz i nie wie w którym z tych stanów.

  • Dla każdego typu t_{i}\ P_{i}=Pr(\omega|t_{i}) jest prawdopodobieństwem apriori (prior belief) jakie typ t_{i} assigns stanowi \omega.

    Funkcja sygnału \tau _{i} wraz ze zbiorem prawdopodobieństw apriori opisują wiedzę i o stanie świata.

  • u_{i}:A\times\Omega\rightarrow\Re,\ \  A=\times A_{i},\  i\in N – funkcja wypłat gracza i.

Gra odbywa się w następstwie realizacji pewnego stanu świata \omega\in\Omega.

Gracz i otrzymuje sygnał (dla uproszczenia oznaczeń pomijamy numer sygnału) t_{i}=\tau _{i}(\omega), czyli jest typu t_{i}. Typ t_{i} definiuje podzbiór stanów świata \tau _{i}^{{-1}}(t_{i}) (które implikują typ t_{i}). Dla każdego takiego stanu \omega\in\tau _{i}^{{-1}}(t_{i}) otrzymujemy Pr(\omega|t_{i}) - aprioryczne prawdobodobieństwa gracza i w stanie t_{i} że stan świata jest \omega. Mając te prawdopodobieństwa obliczamy wypłaty gracza i.

Przykład 6.4

W rozpatrywanej grze Walka Płci (przy niepełnej informacji):

N=\{ 1,2\}

\Omega=\{ razem,osobno\}

A_{i}=\{ B,S\},\ \  i=1,2

Funkcje sygnału: gracza 1: \tau _{1}(razem)=\tau _{1}(osobno)=t_{1}^{1},\  T_{1}=\{ t_{1}^{1}\} – gracz 1 może otrzymać tylko jeden sygnał, jest tylko jednego typu.

gracza 2: \tau _{2}(razem)=l=t_{2}^{1},\ \tau _{2}(osobno)=h=t_{2}^{2},\  T=\{ l,h\} – gracz 2 może być typu l lub typu h.

Prawdopodobieństwa aprioryczne gracza 1:

Pr(razem|t_{1}^{1})=Pr(osobno|t_{1}^{1})=1/2.

Mówimy że gracz 1 przypisuje każdemu stanowi świata prawdopodobieństwo 1/2 po otrzymaniu sygnału t_{1}^{1}.

Prawdopodobieństwa aprioryczne gracza 2:

P(razem|t_{2}^{1})=1=P(osobno|t_{2}^{2}),\ \  P(osobno|(t_{2}^{1})=P(razem|t_{2}^{2})=0.

Gracz 2 przypisuje prawdopodobieństwo 1 stanowi razem po otrzymaniu synału t_{2}^{1} i stanowi osobno po otrzymaniu sygnału t_{2}^{2}.

Wypłaty: dla a=(a_{1},a_{2}),\  a_{i}\in\{ B,S\}:

Liczby u_{i}(a,razem) są elementami macierzy wypłat gdy 2 jest typu l,

Liczby u_{i}(a,osobno) są elementami macierzy wypłat gdy 2 jest typu h.

Definicja 6.6

Równowaga Nasha Gry Bayesowskiej GB jest to RN następującej GS:

Gracze: pary (i,t_{i}), gdzie i\in N,\ \  t_{i}\in T_{i}

Zbiór akcji gracza (i,t_{i}) jest to zbiór akcji A_{i} gracza i w GS

Wypłaty gracza (i,t_{i}) definiujemy następująco:

Oznaczmy: a_{i}(j,t_{i})=:\hat{a}_{i}(\omega) –akcja typu t_{i} gracza i,\  i\in N.

Wypłata gracza (i,t_{i}) wybierającego akcję a_{i} jest równa

u_{i}^{{t_{i}}}(a_{i},\cdot)=\sum _{{\omega\in\Omega}}u_{i}(a_{i},\hat{a}_{{-i}}(\omega)),\omega)Pr(\omega|t_{i}).

(a_{i},\hat{a}_{{-i}}(\omega)) jest profilem GS w której gracz i typu t_{i} gra a_{i}, a pozostali grają \hat{a}_{j}(\omega),\  j=1,...,i-1,i+1,...n, \hat{a}_{j}(\omega) jest wprowadzonym wyżej oznaczeniem akcji gracz j typu \tau _{j}(\omega) gdy stan świata jest \omega.

Zauważmy że u_{i}^{{t_{i}}}(a_{i},\cdot) zależy od akcji wszystkich typów wszystkich pozostałych graczy, a nie zależy od akcji żadnego z typów gracza i.

6.3. Przykłady

Przykład 6.5

W rozważanym wyżej Przykładzie 6.4 policzymy oczekiwaną wypłatę (jedynego) typu t_{1}^{1} gracza 1 z akcji a_{1}=B, gdy \hat{a}_{2}(\omega _{1})=B,\ \hat{a}_{2}(\omega _{2})=S:

u_{1}^{{t_{1}}}(B,\cdot)=u_{1}((B,B),\omega _{1})Pr(\omega _{1}|t_{1}^{1})+u_{1}((B,S),\omega _{2})Pr(\omega _{2}|t_{1}^{1})=2\cdot 1/2+0\cdot 1/2=1.
Przykład 6.6 (Battle of the Sexes (with incomplete information))

Niech obaj gracze mogą być jednego z dwóch typów: l,\  h, i że nie wiedzą jakiego typu jest przeciwnik: 1 przypisuje typowi 2-go prawdopodobieństwo 1/2, 2-i przypisuje 1-mu typ l z prawdopodobieństwem 2/3, h z prawdopodobieństwem 1/3. Gracze znają swoje typy.

Tę sytuację modelujemy jako następującą GB:

\Omega=\{ yy,yn,ny,nn\}

A_{i}=\{ B,S\},\ \  i=1,2

Funkcja sygnału gracza 1: \tau _{1}(yy)=\tau _{1}(yn)=:y_{1},\ \ \tau _{1}(ny)=\tau _{1}(nn)=:n_{1},\ \  T_{1}=\{ y_{1},n_{1}\}

Funkcja sygnału gracza 2: \tau _{2}(yy)=\tau _{2}(ny)=y_{2},\ \ \tau _{2}(yn)=\tau _{2}(nn)=:n_{2},\ \  T_{2}=\{ y_{2},n_{2}\}

Prawdopodobieństwa aprioryczne (beliefs) gracza 1:

Pr(yy|y_{1})=Pr(yn|y_{1})=1/2=Pr(ny|n_{1})=Pr(nn|n_{1})=1/2\ \

Prawdopodobieństwa aprioryczne (beliefs) gracza 2:

Pr(yy|y_{2})=Pr(yn|n_{2})=2/3,\ \  Pr(ny|y_{2})=Pr(nn|n_{2})=1/3\ \

Wypłaty: dla a=(a_{1},a_{2}),\  a_{i}\in\{ B,S\}: liczby u_{i}(a,\omega),\ \omega\in\{ yy,yn,ny,nn\} są elementami macierzy M_{1},...M_{4}.

M_{1}:
B S
B 2,1 0,0
S 0,0 1,2

M_{2}:
B S
B 2,0 0,2
S 0,1 1,0

M_{3}:
B S
B 0,1 2,0
S 1,0 0,2

M_{4}:
B S
B 0,0 2,2
S 1,1 0,1

Przykład 6.7 (Duopol Cournota z asymetryczną informacją)

\

W Przykładzie 6.2 gra Bayesa ma postać:

N=\{ 1,2\}, \ \Omega=\{ L,H\}, \  A_{i}=\Re _{+},\  i=1,2.

Funkcje sygnału: \tau _{1}(H)=\tau _{1}(L),\ \ \tau _{2}(L)\neq\tau _{2}(H).

Prawdopodobieństwa aprioryczne: jedyny typ gracza 1 przypisuje prwadopodobieństwo p stanowi L, 1-p stanowi H. Każdy typ gracza 2 przypisuje prawdopodobieństwo 1 każdemu stanowi konsystentnemu ze swoim sygnałem Pr_{2}(L.,t_{2}^{1})=1=Pr_{2}(H,t_{2}^{2}), natomiast prawdopodobieństwo 0 w przeciwnym przypadku.

Funkcje wypłaty: u_{1}(q_{1},q_{2})=q_{1}P(Q)-cq_{1},\ \  u_{2}(q_{1},q_{2})=q_{2}P(Q)-c_{I}q_{2}, gdzie Q=q_{1}+q_{2},\ \  I\in\Omega, a P(Q) jest rynkową ceną jednostki towaru którego całkowita produkcja wynosi Q.

Ćwiczenie 6.1

\

W duopolu Cournota z Przykładu 9.7 dla c_{L},c_{H} dostatecznie bliskich by istniała RN z dodatnimi produkcjami znaleźć tę RN i porównać z RN gier w których 1 zna c_{L} i c_{H}.

Niech P(Q)=\alpha-Q dla Q\le\alpha, P(Q)=0 dla Q>\alpha. Niech (q_{1}^{*},(q^{*}L,q^{*}_{H})) – RN. Wtedy

q_{1}^{*}=B_{1}(q_{L}^{*},q_{H}^{*})=max_{{q_{1}}}[pP(q_{1}+q_{L}^{*})-c)q_{1}+(1-p)(P(q_{1}+q_{H}^{*})-c)q_{1}],

q_{L}^{*}=B_{L}(q_{1}^{*})=max_{{q_{L}}}[(P(q_{1}^{*}+q_{L})-c_{L})q_{L}]

q_{H}^{*}=B_{H}(q_{1}^{*})=max_{{q_{H}}}[(P(q_{1}^{*}+q_{H})-c_{H})q_{H}].

Obliczając pierwsze pochodne otrzymujemy 3 równania algebraiczne na (q_{1}^{*},(q^{*}L,q^{*}_{H})). Ich rozwiązanie:

q_{1}^{*}=\frac{\alpha-2c+pc_{L}+(1-p)c_{H}}{3}
q_{L}^{*}=(\alpha-2c_{L}+c)/3-(1-p)(c_{H}-c_{L})/6
q_{H}^{*}=(\alpha-2c_{H}+c)/3+p(c_{H}-c_{L})/6

Przypomnijmy że dla duopolu Cournota z pełną informacją gdy koszt produkcji firmy i wynosi c_{i},\  i=1,2, to zakładając dodatniość odpowiednich wielkości produkcji, w RN wielkości te wynoszą

q_{1}^{*}=(\alpha-2c_{i}+c_{j})/3.

W szczególoności otrzymujemy więc

q_{H}^{*}>(\alpha-2c_{H}+c)/3,\quad q_{L}^{*}<(\alpha-2c_{L}+c)/3.
Przykład 6.9 (Nadmiar informacji może obniżyć wypłatę)

\

I. Rozważmy wpierw 2-osobową GB z dwoma stanami: \omega _{1},\omega _{2}, w której żaden z graczy nie zna stanu świata i każdy przypisuje prawdopodobieńtwo 1/2 każdemu z 2 stanów. Macierze wypłat odpowiadające obu stanom mają postać: M_{1}:
L M R
T 1,2a 1,0 1,3a
B 2,2 0,0 0,3

M_{2}:
L M R
T 1,2a 1,3a 1,0
B 2,2 0,3 0,0

gdzie a\in(0,1/2).

Najlepsza odpowiedź gracza 2 na każdą akcję 1-go to L:

jeśli 1 wybierze T, to L da 2a, M i R dadzą po 3a/2 każda.

jeśli 1 wybierze B, to L da 2, M i R dadzą po 3/2 każda.

Co więcej, najlepsza odpowiedź 1 na L to B. Ponieważ jest to jedyna najlepsza odpowiedż, więc para (par) (B,B),(L,L)) jest jedyną RN (także w strategiach mieszanych). W Rn każdy gracz otrzymuje 2.

II. Rozważmy teraz nastepującą modyfikację tej gry. Gracz 2 zna stan świata: \tau _{2}(\omega _{1})\neq\tau _{2}(\omega _{2}. Mamy sytuację taką jak w pierwszej wersji gry Wojna Płci z niepełną informacja. Gracz 2 ma więc więcej informacji. Zakładamy że gracz 1 jest o tym poinformowany.

W tej grze (T,(R,M)) jest jedyną RN: każdy typ gracza 2 ma strategię ścisle dominującą, wprzy której jedyną najlepszą odpowiedzią gracza 1 jest T. W tej RN gracz 2 otrzymuje 3a w każdym ze stanów, a więc wypłatę niższą niż w przypadku I!

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.