Transcript
Teoria Decyzji Wykład 12 N-OSOBOWE GRY KOOPERACYJNE POSTAĆ CHARAKTERYSTYCZNA GRY Na poprzednich wykładach zajmowaliśmy się głównie takimi sytuacjami, w których gracze podejmowali decyzje jednocześnie i niezależnie, a wynik gry był wypadkową tych działań. Współdziałanie czyli kooperację w grach zwykle rozumie się jako zawarcie, jeszcze przed rozegraniem gry, pewnego porozumienia, które może być potem przestrzegane, albo nie (w teorii Nasha musi być przestrzegane). O współdziałaniu była już kilkakrotnie mowa np. przy okazji wytwórców whisky. Gracze — producenci mogli wówczas porozumieć się i uzyskać znacznie większe zyski niż w przypadku działań nieskoordynowanych. Gry kooperacyjne dwuosobowe nie są specjalnie ciekawe, gdyż niewielkie są możliwości tworzenia koalicji. Jako ciekawszy przedstawimy przykład gry trzyosobowej. Opowiadanie jest następujące. Trzej muzycy: Skrzypek, Pianista i Basista wylądowali razem w dalekim kraju za oceanem. Po wyspaniu się i zjedzeniu śniadania wyszli rozejrzeć się za pracą. Gdy spotkali się wieczorem okazało się, że stoją przed nimi następujące możliwości. Mogą występować razem w pewnym klubie nocnym i za jeden występ otrzymają łącznie 200 dolarów. Okazuje się też, że gdyby w innym klubie występowali tylko Skrzypek z Pianistą, to zarobiliby 160 dolarów, natomiast Pianista i Basista mogliby zarobić we dwóch 130 dolarów. W sąsiednim klubie Basista ze Skrzypkiem mogą liczyć na zarobek w wysokości 100 dolarów, a sam Pianista dostałby za występ 60 dolarów. Jeszcze inny klub zatrudniłby Skrzypka samego i skłonny byłby zapłacić mu 40 dolarów. Tylko Perkusisty solo nikt nie chce zatrudnić. Tak opisaną grę kooperacyjną możemy przedstawić w formie przedstawionej w poniższej tabeli. Koalicja Wypłata {Skrzypek, Pianista, Basista} 200 { Pianista, Basista} 130 {Skrzypek,Basista} 100 {Skrzypek, Pianista} 160 {Skrzypek} 40 { Pianista} 60 { Basista} 0
Taka tabela to tzw. postać charakterystyczna gry kooperacyjnej.
Formalnie taką postać gry definiuje się opisując: zbiór wszystkich graczy G = {Pl, P2, .... Pn}, zbiór wszystkich koalicji, tzn wszystkich podzbiorów zbioru graczy (całe G i zbiory złożone z jednego tylko gracza też są koalicjami) przyporządkowanie każdej koalicji K
jakiejś liczby v(K), która opisuje
możliwości tej koalicji. Pewnego komentarza wymaga wartość v(K) przypisana koalicji K (zwana wartością koalicji). Można wyobrażać sobie, że jest to wypłata którą jest wstanie koalicja sobie wypracować. Ale uwaga – trzeba dla dalszych rozważań założyć, że tak jak w naszym przykładzie wypłata ta realizowana jest w pewnych jednostkach, które dadzą się między graczami wymieniać i tyle samo dla nich znaczą! Możliwa jest do sformułowania teoria, w której wypłaty są wyrażane w funkcjach użyteczności właściwych dla każdego z graczy z osobna i nieporównywalnych między nimi, ale byłoby to zbyt skomplikowane jak na możliwości naszego wykładu. Wróćmy zatem do naszego przykładu. Aby zadość uczynić postulatowi wymienialności wypłat zakładamy, że decydującą kwestią jest zarobek (i, co sugeruje przykład , gracze mają analogiczna funkcje użyteczności pieniądza). Świadomie w tym miejscu pomijamy sprawy związane z chęcią występowania przed publicznością, pomocy kolegom, bezinteresownością itp. Gdyby zostały one uwzględnione w wypłatach, to już pojawiłby się wspomniany przed chwilą kłopot związany z międzyosobowym transferem użyteczności. Zostawmy to teraz, wszak nie o to w tej chwili chodzi, by zbudować właściwy model konkretnej sytuacji, ale na odwrót – by pewna wyimaginowana konkretna sytuacja była modelem pewnych koncepcji pojawiających się na gruncie teorii decyzji. Zatem w jaki sposób muzycy
rozstrzygną kwestię swojego zatrudnienia i
indywidualnego wynagrodzenia? Po pierwsze zauważmy, że nasza gra ma pewną naturalną własność, która nazywa się superaddytywnosią : każdych dwóch muzyków razem zarobi więcej niż zarobiliby łącznie, ale występując osobno. Tak samo, każdej koalicji złożonej z dwóch muzyków i pozostałemu trzeciemu artyście bardziej opłaci się wystąpić w pełnym składzie. Zatem największą masę pieniędzy dostaną w największej koalicji. W przypadku
takich gier (tj. posiadających
własność superaddytywności) nie ulega więc wątpliwości, że największa koalicja jest najbardziej opłacalna. Pozostaje jeszcze kwestia podziału zarobionych pieniędzy w ramach takiej koalicji. Jak to zrobić? Formalnie taki podział tworzą trzy liczby Xs, Xp oraz Xb dające w sumie 200. Można
się spodziewać, że żaden muzyk nie zgodzi się przyjąć wypłaty niższej, niż kwota, jaką mógłby sam zarobić. Otrzymujemy więc warunki indywidualnej racjonalności: Xs ≥ 50 Xp ≥ 60 Xb ≥ 0 Weźmy teraz pod uwagę dalsze ograniczenia nazywane warunkami koalicyjnej racjonalności. Xs+Xp ≥ 160 Xb+Xp ≥ 130 Xs+Xb ≥ 100 Warunki te mówią tyle, że żadna koalicja nie zgodzi się na podział, przy którym suma kwot przypadających członkom tej koalicji będzie niższa niż kwota, jaką taka koalicja mogłaby sama zarobić. Mówimy też w takiej sytuacji, że dana koalicja, na przykład {Skrzypek, Pianista}, dla której podział (Xs, Xp, Xb) dawałby Xs+Xp<160, kwestionowałaby taki podział – mogłaby przecież oddzielić się z całości i sama wypracowałaby dla siebie Xs+Xp=160.
Przekształcając
wszystkie
powyższe
nierówności,
możemy
teraz
scharakteryzować podziały koalicyjnie racjonalne. Ale z tych ograniczeń wynikają dalsze! Okazuje się np. że , wbrew temu co mogłoby się naiwnie wydawać, Basista może żądać dla siebie znacznie więcej niż zero! Na pewno nie otrzyma mniej niż 30! Wynika to z tego, że skrzypek nie może dla siebie żądać więcej niż 70 (bo wtedy Xb+Xp < 130) pianista nie może dla siebie żądać więcej niż 100 (bo wtedy Xs+Xb < 100) ale zatem Basista dostanie co najmniej 130-100 lub 100-70 (wartości kolacji dwuosobowych z perkusistą minus potencjalnie największe wymagania drugiego z muzyków) Oczywiście Basista nie może liczyć na więcej niż 200 – 160 (tj całość pieniędzy minus gwarantowana wypłata dla duetu Pianisty ze Skrzypkiem). Analogiczne rozumowanie można przeprowadzić dla pozostałych muzyków. Ostatecznie wszystkie podziały spełniające warunki racjonalności koalicyjnej i indywidualnej muszą spełniać następujące warunki:
Suma kwot uzyskanych łącznie przez trzech muzyków wyniesie 200 dolarów.
Kwota Xs uzyskana przez Skrzypka nie będzie niższa od 60 dolarów, ani wyższa od 70 dolarów. Kwota Xp uzyskana przez Pianistę nie będzie niższa od 90 dolarów, ani wyższa od 100 dolarów. Łącznie Skrzypek i Pianista dostaną co najmniej 160 dolarów. Reszta przypadnie Perkusiście — jak pokazaliśmy będzie to kwota Xb między 30 a 40 dolarów. Warunki te pozwalają na dosyć dokładne określenie spodziewanego podziału, dla każdego muzyka z dokładnością do 10 dolarów. W tych ramach trudno już cokolwiek graczom zaproponować na podstawie samych reguł gry. Sytuacja przypomina tę z kooperacyjnych gier dwuosobowych - pamiętamy, że gracze powinni wybrać strategie prowadzące do wypłaty ze zbioru negocjacji, ale do której z nich – teoria nie mówi. Dopiero odwołanie się do pewnych poza growych argumentów takich jak np. sprawiedliwość – doprowadziło do propozycji rozwiązania arbitrażowego (rozwiązanie problemu targu w sensie Nasha). W grach n-osobowych zaproponujemy postępowanie analogiczne. Ale zanim się tym zajmiemy (na następnym wykładzie) omówimy kilka innych ważnych kwestii związanych z różnymi koncepcjami rozwiązania gry kooperacyjnej. Zbiór wszystkich koalicyjnie racjonalnych podziałów, czyli takich, których nie zakwestionuje żadna koalicja, nazywa się rdzeniem gry. Jest to pojęcie intuicyjnie bardzo oczywiste. Można by spodziewać się, że podziały należące do rdzenia będą stanowić sensowne „rozwiązanie" każdej gry. Niestety tak nie jest. Okazuje się, że w wielu grach w ogóle nie ma żadnego podziału koalicyjnie racjonalnego! Co zrobić w takim wypadku? Tą sprawą zajmiemy się w następnych częściach wykładu. Zbiór stabilny W poprzedniej części mówiliśmy o grze kooperacyjnej dotyczącej muzyków szukających pracy w obcym kraju. Rozpatrzmy następny przykład związane z emigrantami niewykwalifikowanymi. Trzech kolegów, Zyga, Wiesiek i Mietek, poszukuje pracy. W okolicy jest tylko jedna oferta pracy. Praca ma polegać na przenoszeniu długich i ciężkich skrzyń i jest płatna 100 dolarów za dniówkę dla całej ekipy. Jest to robota którą może wykonać dwóch pracowników: jeden bierze jeden koniec skrzyni, drugi za drugi, i niosą. Jeden robotnik sobie z tym nie
poradzi, a trzeci jest po prostu niepotrzebny. Dla tej gry otrzymujemy następującą postać charakterystyczną: Koalicja { Zyga, Wiesiek, Mietek } { Wiesiek, Mietek } { Zyga, Mietek } { Zyga, Wiesiek } { Mietek } { Zyga, } { Wiesiek }
Wypłata 100 100 100 100 0 0 0
Jak gracze podzielą między siebie 100 dolaró ? Okazuje się, że warunki opisane w poprzednim rozdziale do niczego nas nie doprowadzą. Każdy koalicyjnie racjonalny podział (Xz, Xw, Xm) musiałby spełniać warunki: Xz +Xw+ Xm=100 Xz+ Xm ≥ 100 Xz+ Xw ≥ 100 Xw+ Xm ≥ 100 Xz ≥ 0, Xw ≥ 0, Xm ≥ 0 Niestety wypisane wyżej warunki są sprzeczne: w ogóle nie ma takiego układu liczb Xz, Xw, Xm, który by je spełniał, a więc każdy zaproponowany podział będzie przez jakąś koalicję zakwestionowany. Na przykład podział (40; 40; 20) zostanie zakwestionowany przez każdą koalicję dwuosobową: obaj gracze mogą zarobić więcej (czyli 100) niż suma zaproponowanych im wypłat przy takim podziale (60 lub 80). Co można więc zrobić w takiej sytuacji? Pewne rozwiązanie zaproponowali John von Neumann i Oskar Morgenstern już w 1944 roku. Rozwiązanie to opiera się o pojęcie dominacji. Mówimy, że w grze kooperacyjnej n-osobowej podział (X1, X2, ... , Xn) jest zdominowany przez podział (Y1, Y2, ... , Yn), gdy istnieje taka koalicja K, dla której spełnione są dwa warunki: • koalicja K jest w stanie sama „wypracować" podział (Y1, Y2, ...
, Yn), tzn.
formalnie, suma wypłat graczy z koalicji K przy podziale y (czyli suma wszystkich liczb Yi takich, że i K) nie przekracza liczby v(K) opisującej możliwości tej koalicji, oraz
• przy podziale (Y1, Y2, ... , Yn) kwota przypadająca każdemu graczowi należącemu do koalicji K jest większa niż kwota przypadająca mu przy podziale (X1, X2, ... , Xn) , tzn. Yi>Xi dla wszystkich i takich, że i K) Na przykład podział (40; 40; 20) w naszej grze jest zdominowany przez podział (50; 50; 0), a dzieje się tak za sprawą koalicji złożonej z dwóch pierwszych graczy: Zyga i Wiesiek umawiają się, że to właśnie oni podejmą pracę, zarobią 100 złotych i podzielą się po połowie, co da im wyższe wypłaty, niż proponowane 40 złotych. Podziały koalicyjnie racjonalne, które badaliśmy w poprzednim rozdziale, to z definicji takie podziały, które nie są zdominowane przez żaden inny podział. Skoro jednak w naszej grze nie ma takich podziałów, więc spróbujemy, posługując się pojęciem dominacji, skonstruować jakieś inne pojęcie „rozwiązania" gry. Nie będzie to jeden konkretny podział, ale pewien zbiór podziałów. W określonej sytuacji społecznej można się spodziewać, że konkretny podział, jaki nastąpi, będzie elementem tego zbioru. Formalnie zbiór stabilny (czasem nazywany też rozwiązaniem von NeumannaMorgensterna) definiuje się jako dowolny zbiór podziałów S, który spełnia dwa warunki: • jest wewnętrznie stabilny, to znaczy żaden podział, który należy do S nie dominuje żadnego innego podziału z S, oraz • jest zewnętrznie stabilny w tym sensie, że każdy podział, który nie należy do S jest zdominowany przez jakiś podział należący do S. Zilustrujmy to pojęcie na konkretnym przykładzie w naszej grze. Weźmy pod uwagę zbiór S* złożony z trzech podziałów (50; 50; 0), (50; 0; 50), (0; 50; 50), a więc ze wszystkich takich podziałów, przy których dwaj gracze dogadują się, biorą całą wypłatę, dzielą się nią po połowie, a trzeciemu graczowi nie dają nic. Można sprawdzić, że ten zbiór jest wewnętrznie i zewnętrznie stabilny: żaden z tych trzech podziałów nie dominuje żadnego z pozostałych, natomiast każdy podział, który nie jest takiej postaci jest zdominowany przez jeden z tych trzech podziałów. Zbiór S* jest więc stabilny. Taka koncepcja rozwiązania to odpowiada pewnym znanym sytuacjom społecznym i może być interpretowana jako opis pewnej normy zachowania. Tą normą jest: postępować w sposób bezwzględny, za wszelką cenę próbować się z kimś dogadać nie licząc się z losem trzeciego gracza, który nie zostanie dopuszczony do umowy. Nie wiemy, jaki podział faktycznie nastąpi, ale na pewno będzie to jeden z trzech podziałów wyliczonych powyżej. Oczywiście – wracamy znowu do naszych rozważań związanych z modelowaniem sytuacji
decyzyjnych – problemu tego rodzaju można by uniknąć rozważając wypłaty w użytecznościach graczy, te mogłyby uwzględniać społeczne normy
i, ewentualne,
zachowania altruistyczne (jak w problemie architekt-kreślarz). Jednak przy rozważaniach gier n-osobowych koalicyjnych, ze względu na znaczną pojęciową i formalną komplikację problemu, z takiej interpretacji wypłat zrezygnowaliśmy – zatem w tym przypadku ewentualny kłopot z akceptacją zachowań bezwzględnych pozostaje. Wracamy do naszej analizy możliwych rozwiązań. Jedna gra może mieć wiele różnych zbiorów stabilnych i każdy z nich jest interpretowany jako jakaś norma postępowania społecznego. Podobnie jest i w przypadku naszej gry. Znaleziony zbiór stabilny nie jest jedyny, tak jak opisany schemat postępowania nie jest jedyną normą. Przedstawimy jeszcze dwa przykłady zbiorów stabilnych w naszej grze. Przypuśćmy, że wszyscy gracze to ludzie porządni, którzy nikogo nie chcą skrzywdzić, ale z jakichś względów Wiesiek i Mietek uważają Zygę za nieudacznika, który nie bardzo nadaje się do pracy. W takim społeczeństwie normy postępowania może opisywać zbiór S0 wszystkich podziałów postaci (20; b; c) gdzie b i c są dowolnymi liczbami nieujemnymi dającymi w sumie 80. W tym społeczeństwie obowiązuje więc następująca norma: Zyga to „jednostka słaba, która do pracy się nie nadaje", my jesteśmy porządni, więc damy mu 20 dolarów, ale pracować chcemy sami i resztą, czyli 80 złotymi podzielimy się, jak nam się będzie chciało. Gdyby to Mietek był uważany za nieudacznika, a Zyga z Wiesiekem byli trochę mniej szczodrzy niż przedtem Wiesiek i Mietek, to tej sytuacji odpowiadałby zbiór stabilny S0 złożony ze wszystkich podziałów postaci {a, b, 10) gdzie a i b są dowolnymi liczbami nieujemnymi dającymi w sumie 90. W odróżnieniu od podziałów koalicyjnie racjonalnych, których często w ogóle nie ma, zbiorów stabilnych jest zwykle wiele (w naszej grze jest ich nawet nieskończenie wiele). Przez długi czas nie wiedziano, czy są w ogóle takie gry, które nie mają żadnego zbioru stabilnego. Po wielu latach Lucas skonstruował taką grę dziesięcioosobową w 1969 roku, ale do tej pory nie znaleziono dla niej żadnej naturalnej „życiowej" interpretacji. Von Neumann i Morgenstern spodziewali się, że zbiór stabilny, pojęcie w naturalny sposób oddające intuicje i odegra wielką rolę w badaniach ekonomicznych. Do dzisiaj tak się jednak nie stało. Zbiór stabilny jest pojęciem funkcjonującym raczej na obrzeżach teorii gier i jej zastosowań. Jest pojęciem ciągle słabo zbadanym, może ze względu na konieczność stosowania żmudnych i nieefektownych środków matematycznych. Wielu fachowców uważa jednak, że teraz nastąpi powrót do zbiorów stabilnych.
