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

2

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ć.

4

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