(Microsoft Word - Teoria Decyzj nr 12 - N-Osobowe Gry Kooperacyjne

-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}

{ Pianista}

{ Basista}

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 taka 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 moŜliwoś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:

≥ 50

Xp ≥

Xb ≥

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 1000 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

Wypłata

{ Zyga, Wiesiek, Mietek }

100

{ Wiesiek, Mietek }

100

{ Zyga, Mietek }

100

{ Zyga, Wiesiek }

100

{ Mietek }

{ Zyga, }

{ Wiesiek }

Jak gracze podzielą między siebie 100 dolarów. 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

) 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

)

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 Neumanna-

Morgensterna) 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.