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, .... P n} ,

•

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:

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

0

{ Zyga, }

0

{ Wiesiek }

0

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, ... , X n) jest

zdominowany przez podział (Y1, Y2, ... , Y n), gdy istnieje taka koalicja K, dla której

spełnione są dwa warunki:

• koalicja K jest w stanie sama „wypracować" podział (Y1, Y2, ... , Y n), tzn.

formalnie, suma wypłat graczy z koalicji K przy podziale y (czyli suma wszystkich liczb Y i

takich, że iœ K) nie przekracza liczby v( K) opisującej możliwości tej koalicji, oraz

• przy podziale (Y1, Y2, ... , Y n) kwota przypadająca każdemu graczowi należącemu

do koalicji K jest większa niż kwota przypadająca mu przy podziale (X1, X2, ... , X n) , tzn.

Y i>X i 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 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 S 0 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.