N-osobowe gry kooperacyjne - warto+Ť¦ç Shapleya.pdf - TeoriaGier - cathal30

N -osobowe gry kooperacyjne - wartość Shapleya

Na poprzednim wykładzie mówiliśmy o dwóch rodzajach pojęcia „rozwiązania" gry

kooperacyjnej: o rdzeniu i o zbiorach stabilnych. Oba te rozwiązania odwołują się do

koncepcji dominacji albo kwestionowania pewnych podziałów przez pewne koalicje. Pojęcia

te, pomimo swojej intuicyjnej oczywistości, mają pewne wady: zachowują się w dość

nieregularny sposób, rdzeń moŜe być zbiorem pustym, a zbiorów stabilnych moŜe być z kolei

bardzo wiele. Tych wad nie ma inna koncepcja „rozwiązania" gry, którą zajmiemy się w tym

rozdziale. Jest nią wartość Shapleya . Wprowadzimy to pojęcie posługując się przykładem

muzyków opisanym na poprzednim wykładzie. Przypomnijmy samą tylko tabelkę tej gry –

prezentującą jej postać charakterystyczną

Koalicja

Wypłata

{Skrzypek, Pianista, Basista}

200

{ Pianista, Basista}

130

{Skrzypek,Basista}

100

{Skrzypek, Pianista}

160

{Skrzypek}

{ Pianista}

{ Basista}

Przypuśćmy, Ŝe trzej muzycy umówili się w jednym miejscu, na przykład na

przystanku metra o piątej po południu. Nigdy nie przyjdą na spotkanie w tym samym

momencie: ze względów losowych będą się pojawiać w jakiejś kolejności. Co więcej –

teoretycznie nie wszyscy musza się pojawić. Jeśli się dany muzyk pojawi, to jaka jest z tego

korzyść? OtóŜ to – ta korzyść - zaleŜy nie tylko od tego, który to muzyk, ale teŜ od tego w

którym momencie tworzenia koalicji się pojawi. Ową „korzyść” z przyjścia danego muzyka,

ogólnie nazywamy wkładem w koalicję. Jest sześć moŜliwych kolejności pojawiania się

muzyków, czyli jak mówimy - tworzenia koalicji:

{Skrzypek, Pianista, Basista}

{Skrzypek, Basista, Pianista}

{Pianista, Basista, Skrzypek}

{Pianista, Skrzypek, Basista}

{Basista, Skrzypek, Pianista}

{Basista, Pianista, Skrzypek}

Wybierzmy sobie jednego z artystów, na przykład Basistę i przeanalizujmy jego

sytuację w kaŜdym z moŜliwych wymienionych wyŜej przypadków. Przypuśćmy, Ŝe kaŜdą

kolejność przyjścia interpretujemy jako proces tworzenia się zespołu w pewnej kolejności.

Interesuje nas wielkość wypłaty, jaką dany gracz — muzyk wnosi do juŜ zastanej koalicji. W

przypadku kolejności numer l, Basista zastaje koalicję {Skrzypek, Pianista} „wartą" (jak

wynika z tabeli) 160. Po jego przyjściu wartość koalicji wzrasta do 200 dolarów, czyli o 40

dolarów. W przypadku kolejności numer 2, Basista zastaje koalicję { Skrzypek } „wartą" 40

dolarów. Po jego przyjściu wartość tej koalicji wzrasta do 100 dolarów, czyli o 60 dolarów.

Postępujemy tak dalej, na przykład dla kolejności numer 5, czy 6, Perkusista przychodzi

pierwszy i wnosi 0 dolarów, jako Ŝe sam „nie jest nic wart". Otrzymujemy w ten sposób

poniŜszą tabelę, w której wypisano wszystkie moŜliwe kolejności tworzenia się zespołu, a

obok — kwoty, jakie poszczególni muzycy wnoszą przychodząc w tej właśnie kolejności.

W ostatnim wierszu tej tabeli umieściliśmy średni wkład kaŜdego z muzyków ze

względu na wszystkie moŜliwe kolejności tworzenia się zespołu. W ten sposób otrzymaliśmy

podział Xs == 70, Xp , = 95. Xb , = 35. Ten podział nazywa się wartością Shapleya danej gry.

Wartość Shapleya, ze względu na sposób, w jaki ją skonstruowano, moŜna interpretować jako

średni oczekiwany podział w danej grze przy rozegraniu duŜej ilości partii. Zaletą wartości

Shapleya jest jej matematyczna prostota. Jest jeszcze jedna bardzo waŜna rzecz: wartość

Shapleya zawsze istnieje i zawsze jest tylko jedna .

Zobaczmy jeszcze jak wygląda wartość Shapleya dla gry opisującej sytuację trzech

kolegów, Zygi, Wieśka i Mietka, a przedstawionej na poprzednim wykładzie. Postać

charakterystyczna tej gry była następująca:

Koalicja

Wypłata

{ Zyga, Wiesiek, Mietek }

100

{ Wiesiek, Mietek }

100

{ Zyga, Mietek }

100

{ Zyga, Wiesiek }

100

{ Mietek }

{ Zyga, }

{ Wiesiek }

Wkłady poszczególnych graczy w róŜnych konfiguracjach kolejności tworzenia

koalicji przedstawia poniŜsza tabela:

Wartość Shapleya tej gry stanowi więc podział Xz =Xw= Xm =

33 . Otrzymany

wynik jest symetryczny, co nie jest przypadkiem. Historycznie bowiem rzecz ujmując, Lloyd

Shapley – który w latach 50 ubiegłego wieku analizował sposoby rozwiązania problemu

podziału wypłaty w koalicji - zaczął od sformułowania trzech aksjomatów, dotyczących

wartości podziału, które jego zdaniem oddają idee sprawiedliwości. Następnie wykazał, Ŝe

taka wartość istnieje i jest tylko jedna. Podał takŜe sposób jej obliczania, był on jednak

znacznie bardziej skomplikowany niŜ ten, który poznali Państwo.

Wspomnianych aksjomatów nie podamy w tym miejscu, bo wykorzystują one pewne

pojęcia formalne obce Państwu, jednak powszechnie uznano je– podobnie jak aksjomaty

sprawiedliwości sformułowane przez Nasha dla gier dwuosobowych – za sensowne i

intuicyjne i raczej wszyscy się z nimi zgadzają, choć oczywiście są sytuacje, w których idee

te budzą pewne wątpliwości.

Jeden z tych aksjomatów mówi właśnie, Ŝe jeśli sytuacje graczy w grze koalicyjnej są

w pełni symetryczne, to ich wypłaty powinny być równe. A tak właśnie było w rozwaŜanej

sytuacji trzech kolegów dźwigających skrzynie.

Wartość Shapleya bardzo szybko została zaakceptowana w teorii i praktyce jako dobra

propozycja rozwiązania problemu podziału wypłaty w koalicji. Znaleziono dla niej takŜe inne

zastosowania. O jednym z nich powiemy w kolejnej części wykładu.

WaŜone gry większości

Głosowanie na walnym zgromadzeniu akcjonariuszy spółki to równieŜ pewien

szczególny rodzaj gry kooperacyjnej. Jest to gra, której kaŜdy uczestnik dysponuje pewną

ilością głosów zaleŜną od jego udziałów w spółce. Sytuacja jest zatem taka: Mamy N graczy -

udziałowców. Udział i -tego gracza w firmie wyraŜa się liczbą w i , i= 1,…,N. Suma wszystkich

udziałów wynosi więc

∑

. Do przyjęcia dowolnej uchwały potrzebna jest większość

głosów. Jest więc jakaś ustalona liczba A większa niŜ

. ale nie większa niŜ W , która

wyznacza „większość". Koalicja, która łącznie zbierze A głosów albo więcej, decyduje o

przyjęciu albo odrzuceniu uchwały. Koalicje taka nazywać będziemy koalicją nazywana

wygrywającą Przypisujemy jej wypłatę w wysokości l. Koalicja , która nie ma większości jest

przegrywająca i przypisujemy jej wypłatę 0. Takie gry nazywamy waŜonymi grami

większości.

Weźmy pod uwagę prosty przykład: czterech akcjonariuszy, których udziały wynoszą,

odpowiednio: 30, 30, 30 i 10 procent. ZałóŜmy, Ŝe statutowa większość potrzebna do podjęcia

jakiejś uchwały wynosi 55. Taką grę będziemy umownie oznaczać przez [30, 30, 30, 10; 55].

Umówmy się, Ŝe graczy numerujemy, a zbiory indeksów oznaczają moŜliwe koalicje.

Przykładowo, koalicja {l, 2, 4} składa się z akcjonariuszy numer l, 2 i 4. Stosując tę notacje

poniŜej przedstawiamy tabelkę prezentującą postać charakterystyczna tej gry:

Na przykład, widzimy Ŝe koalicja {l, 2. 4} jest wygrywająca (suma udziałów

koalicjantów jest równa 70 i przekracza 55, zatem przypisujemy jej wypłatę l .

Przypomnijmy sobie obliczanie wartości Shapleya w poprzednim przykładzie.

Braliśmy tam pod uwagę wszystkie moŜliwe ustawienia graczy, teraz będą to 24 ustawienia

KaŜde takie ustawienie interpretuje się jako pewien proces tworzenia się koalicji i

przyjmuje się, Ŝe wszystkie ustawienia są równie prawdopodobne. Patrzymy następnie, dla

kaŜdego gracza z osobna, o ile wzrosła, w kaŜdym ustawieniu, wartość koalicji, którą ten

gracz juŜ zastał, po jego dołączeniu się do niej. W naszym przypadku tą liczbą będzie zero :

kiedy gracz zastał koalicję przegrywającą, która pozostała nadal przegrywająca po jego

dołączeniu, albo kiedy gracz zastał juŜ koalicję wygrywającą. Tą liczbą będzie natomiast

jeden , kiedy gracz zastał koalicję przegrywającą, która po jego dołączeniu stała się

wygrywająca; w takiej sytuacji mówimy, Ŝe ten gracz jest przy tym ustawieniu decydujący.

Odpowiednie ustawienia kolejności zawierania koalicji i wartość dodana przez

poszczególnych graczy przedstawione są w tabeli

N-osobowe gry kooperacyjne - warto+Ť¦ç Shapleya.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: