OBLICZANIE NUKLEOLUSA W 3 OSOBOWYCH GRACH KOOPERACYJNYCH.
Obliczanie nukleolusa dla gier o większej liczbie graczy jest trudniejsze i nie obowi ˛
azuje na egzaminie.
nukleolus w grze: Trio jazzowe
Oznaczamy: pianista - gracz A; perkusista - gracz B; śpiewak - gracz C.
W poszukiwaniu nukleolusa zaczynamy jak zawsze od następującej tabelki: I
II
III
IV
V
v(A)=300
e = 300 − xA
{(A), (B), (C)}
-500
-500/3
v(B)=0
e = −xB
{(AB), (AC), (BC)}
-50
-50/3
v(C)=200
e = 200 − xC
{(A), (BC)}
-200
-200/2
v(A,B)=650
e = 650 − xA − xB
{(B), (AC)}
-200
-200/2
v(A,C)=800
e = 800 − xA − xC
{(C), (AB)}
-150
-150/2
v(B,C)=500
e = 500 − xB − xC
v(A,B,C)=1000
e = 0
wyjaśnienia do tabelki:
w poszczególnych kolumnach znajdują się:
I - funkcja charakterystyczna gry kooperacyjnej; II - wektor niezadowoleń każdej koalicji z pewnego podziału 0
x = (xA, xB , xC ). Podział definicyjnie
spełnia warunek x
0
A + xB + xC = 1000 = v(A, B, C ).
Niezadowolenie koalicji S z podziału x
P
obliczamy ze wzoru eS = v(S) −
x0
j∈S
j ;
III- zbalansowane rodziny koalicji. Zbalansowane rodziny koalicji tworzą koalicje, dla których zacho-dzi warunek, że każdy gracz należy do tej samej liczby koalicji w rodzinie. W grach 3 osobowych jest takich rodzin 5, (uwaga koalicję największą (A,B,C) pomijamy); IV- suma niezadowoleń koalicji należących do danej rodziny (jest niezależna od podziału dla rodzin zbalansowanych);
1
OBLICZANIE NUKLEOLUSA W 3 OSOBOWYCH GRACH KOOPERACYJNYCH.
V - przeciętne niezadowolenie koalicji w danej rodzinie (obliczane po tych koalicjach, których niezadowolenie możemy jeszcze regulować - zobacz ostatni przykład).
Nukleolus znajdujemy minimalizując leksykograficznie największe niezadowolenia poszczególnych koalicji. Zaczynamy od koalicji należących do rodziny o największym przeciętnym niezadowoleniu.
W przypadku tej gry najwyższe przeciętne niezadowolenie wynosi −50/3. Aby zminimalizować największe z niezadowoleń w tej rodzinie {(AB), (AC), (BC)} każdej koalicji przypisujemy przeciętne niezadowolenie w tej rodzinie.
Przypisanie koalicjom dwuosobowym niezadowolenia −50/3 powoduje, że w rodzinie {(B), (AC)}
koalicji B musimy przypisać niezadowolenie −(200 − 50/3) = −550/3. W rodzinie {(C), (AB)}
koalicji C musimy przypisać niezadowolenie −(150 − 50/3) = −400/3, a w rodzinie {(A), (BC)}
koalicji A musimy przypisać niezadowolenie −(200 − 50/3) = −550/3.
W sposób konieczny dostajemy więc waruneki: eC = 200 − xC = −(150 − 50/3), eB = −xB =
−550/3 i eA = 300 − xA = −550/3, otrzymując: xC = 1000/3 = 333 1 , x
,
3
B = 550/3 = 183 1
3
xA = 1450/3 = 483 1 .
3
Nukleolus tej gry wynosi więc (xA = 483 1 , x
, x
).
3
B = 183 1
3
C = 333 1
3
nukleolus w grze z piwem (zadanie 10 pula kooperacyjna) I
II
III
IV
V
v(A)=0
e = −xA
{(A), (B), (C)}
-7
-7/3
v(B)=0
e = −xB
{(AB), (AC), (BC)} -10 -10/3
v(C)=0
e = −xC
{(A), (BC)}
-5
-5/2
v(A,B)=2
e = 2 − xA − xB
{(B), (AC)}
-5
-5/2
v(A,C)=0
e = −xA − xC
{(C), (AB)}
-7
-7/2
v(B,C)=2
e = 2 − xB − xC
v(A,B,C)=7
e = 0
Zaczynamy od największego przeciętnego niezadowolenia −7/3 i dostajemy od razu nukleolus (xA =
2 1 , x
, x
).
3
B = 2 1
3
C = 2 1
3
nukleolus w grze z dwoma firmami i prezydentem (zadanie 5 pula kooperacyjna)
OBLICZANIE NUKLEOLUSA W 3 OSOBOWYCH GRACH KOOPERACYJNYCH.
3
I
II
III
IV
V
v(A)=3
e = 3 − xA
{(A), (B), (C)}
-6
-2
v(B)=2
e = 2 − xB
{(AB), (AC), (BC)} -12 -4
v(C)=0
e = −xC
{(A), (BC)}
-6
-3
v(A,B)=5
e = 5 − xA − xB
{(B), (AC)}
-6
-3
v(A,C)=3
e = 3 − xA − xC
{(C), (AB)}
-6
-3
v(B,C)=2
e = 2 − xB − xC
v(A,B,C)=11
e = 0
Zaczynamy od największego przeciętnego niezadowolenia −2 i dostajemy od razu nukleolus (xA =
5, xB = 4, xC = 2).
nukleolus w grze z koniem wyścigowym (zadanie 6 pula kooperacyjna) oznaczenia: gracz 1 - A; gracz 2 - B; gracz 3 - C.
I
II
III
IV
V
v(A)=0
e = −xA
{(A), (B), (C)}
-3
-1
v(B)=0
e = −xB
{(AB), (AC), (BC)}
-3
-1
v(C)=0
e = −xC
{(A), (BC)}
-3
-3/2
v(A,B)=1
e = 1 − xA − xB
{(B), (AC)}
-1
-1/2
v(A,C)=2
e = 2 − xA − xC
{(C), (AB)}
-2
-1
v(B,C)=0
e = −xB − xC
v(A,B,C)=3
e = 0
Zaczynamy od największego przeciętnego niezadowolenia −1/2 i dostajemy od razu warunek na niezadowolenie dla gracza (B): e = −xB = −1/2 oraz koalicji (AC): e = 2 − xA − xC = −1/2. Stąd xB = 1/2 a xA + xC = 5/2.
Te warunki nie prowadzą nas jeszcze jednoznacznie do otrzymania nukleolusa.
W dalszym ciągu liczenia nukleolusa nadal minimalizujemy leksykograficznie niezadowolenia koalicji, a więc zaczynamy od tych rodzin w których mamy najwyższą średnią po rodzinie liczoną dla tych koalicji, których niezadowolenie możemy jeszcze regulować.
OBLICZANIE NUKLEOLUSA W 3 OSOBOWYCH GRACH KOOPERACYJNYCH.
Na przykład w rodzinie {(A), (B), (C)} do rozdziału zostało już tylko 2, 5 między A i C i przeciętne niezadowolenie w tej rodzinie liczymy już tylko dla tych dwóch koalicji. Wynosi ono 1,25 podobnie jak w rodzinie {(AB), (AC), (BC)}.
Nowa tabelka dla tej gry ma postać:
I
II
III
IV
V
v(A)=0
e = −xA
{(A), (B), (C)}
-3
-1,25
v(B)=0
e = −xB
{(AB), (AC), (BC)}
-3
-1,25
v(C)=0
e = −xC
{(A), (BC)}
-3
-3/2
v(A,B)=1
e = 1 − xA − xB
{(B), (AC)}
-1
-1/2
v(A,C)=2
e = 2 − xA − xC
{(C), (AB)}
-2
-1
v(B,C)=0
e = −xB − xC
v(A,B,C)=3
e = 0
Kolejne najwyższe przeciętne niezadowolenie wynosi −1 w rodzinie {(C), (AB)}. Dostajemy więc warunek na niezadowolenie koalicji C: eC = −1. Zatem niezadowolenie koalicji A musi wynosić eA = −(2, 5 − 1) = −1, 5.
Nukleolusem w tej grze jest podział (xA = 3/2, xB = 1/2, xC = 1).