OBLICZANIE NUKLEOLUSA W 3 OSOBOWYCH GRACH KOOPERACYJNYCH.

Obliczanie nukleolusa dla gier o wi˛ekszej liczbie graczy jest trudniejsze i nie obowi ˛

azuje na egzaminie.

nukleolus w grze: Trio jazzowe

Oznaczamy: pianista - gracz A; perkusista - gracz B; ´spiewak - gracz C.

W poszukiwaniu nukleolusa zaczynamy jak zawsze od nast˛epuj ˛

acej tabelki:

I

II

III

IV

V

v(A)=300

e = 300 − x

A

{(A), (B), (C)}

-500

-500/3

v(B)=0

e = −x

B

{(AB), (AC), (BC)}

-50

-50/3

v(C)=200

e = 200 − x

C

{(A), (BC)}

-200

-200/2

v(A,B)=650

e = 650 − x

A

− x

B

{(B), (AC)}

-200

-200/2

v(A,C)=800

e = 800 − x

A

− x

C

{(C), (AB)}

-150

-150/2

v(B,C)=500

e = 500 − x

B

− x

C

v(A,B,C)=1000

e = 0

wyja´snienia do tabelki:

w poszczególnych kolumnach znajduj ˛

a si˛e:

I - funkcja charakterystyczna gry kooperacyjnej;

II - wektor niezadowole´n ka˙zdej koalicji z pewnego podziału x

0

= (x

A

, x

B

, x

C

). Podział definicyjnie

spełnia warunek

x

A

+ x

B

+ x

C

= 1000 = v(A, B, C). Niezadowolenie koalicji S z podziału x

0

obliczamy ze wzoru

e

S

= v(S) −

P

j∈S

x

0
j

;

III- zbalansowane rodziny koalicji. Zbalansowane rodziny koalicji tworz ˛

a koalicje, dla których zacho-

dzi warunek, ˙ze ka˙zdy gracz nale˙zy do tej samej liczby koalicji w rodzinie. W grach 3 osobowych jest

takich rodzin 5, (uwaga koalicj˛e najwi˛eksz ˛

a (A,B,C) pomijamy);

IV- suma niezadowole´n koalicji nale˙z ˛

acych do danej rodziny (jest niezale˙zna od podziału dla rodzin

zbalansowanych);

1

2

OBLICZANIE NUKLEOLUSA W 3 OSOBOWYCH GRACH KOOPERACYJNYCH.

V - przeci˛etne niezadowolenie koalicji w danej rodzinie (obliczane po tych koalicjach, których nieza-

dowolenie mo˙zemy jeszcze regulowa´c - zobacz ostatni przykład).

Nukleolus znajdujemy minimalizuj ˛

ac leksykograficznie najwi˛eksze niezadowolenia poszczególnych

koalicji. Zaczynamy od koalicji nale˙z ˛

acych do rodziny o najwi˛ekszym przeci˛etnym niezadowoleniu.

W przypadku tej gry najwy˙zsze przeci˛etne niezadowolenie wynosi

−50/3. Aby zminimalizowa´c

najwi˛eksze z niezadowole´n w tej rodzinie

{(AB), (AC), (BC)} ka˙zdej koalicji przypisujemy przeci˛etne

niezadowolenie w tej rodzinie.

Przypisanie koalicjom dwuosobowym niezadowolenia

−50/3 powoduje, ˙ze w rodzinie {(B), (AC)}

koalicji

B musimy przypisa´c niezadowolenie −(200 − 50/3) = −550/3. W rodzinie {(C), (AB)}

koalicji

C musimy przypisa´c niezadowolenie −(150 − 50/3) = −400/3, a w rodzinie {(A), (BC)}

koalicji

A musimy przypisa´c niezadowolenie −(200 − 50/3) = −550/3.

W sposób konieczny dostajemy wi˛ec waruneki:

e

C

= 200 − x

C

= −(150 − 50/3), e

B

= −x

B

=

−550/3 i e

A

= 300 − x

A

= −550/3, otrzymuj ˛

ac:

x

C

= 1000/3 = 333

1
3

,

x

B

= 550/3 = 183

1
3

,

x

A

= 1450/3 = 483

1
3

.

Nukleolus tej gry wynosi wi˛ec

(x

A

= 483

1
3

, x

B

= 183

1
3

, x

C

= 333

1
3

).

nukleolus w grze z piwem (zadanie 10 pula kooperacyjna)

I

II

III

IV

V

v(A)=0

e = −x

A

{(A), (B), (C)}

-7

-7/3

v(B)=0

e = −x

B

{(AB), (AC), (BC)} -10 -10/3

v(C)=0

e = −x

C

{(A), (BC)}

-5

-5/2

v(A,B)=2

e = 2 − x

A

− x

B

{(B), (AC)}

-5

-5/2

v(A,C)=0

e = −x

A

− x

C

{(C), (AB)}

-7

-7/2

v(B,C)=2

e = 2 − x

B

− x

C

v(A,B,C)=7

e = 0

Zaczynamy od najwi˛ekszego przeci˛etnego niezadowolenia

−7/3 i dostajemy od razu nukleolus (x

A

=

2

1
3

, x

B

= 2

1
3

, x

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 − x

A

{(A), (B), (C)}

-6

-2

v(B)=2

e = 2 − x

B

{(AB), (AC), (BC)} -12 -4

v(C)=0

e = −x

C

{(A), (BC)}

-6

-3

v(A,B)=5

e = 5 − x

A

− x

B

{(B), (AC)}

-6

-3

v(A,C)=3

e = 3 − x

A

− x

C

{(C), (AB)}

-6

-3

v(B,C)=2

e = 2 − x

B

− x

C

v(A,B,C)=11

e = 0

Zaczynamy od najwi˛ekszego przeci˛etnego niezadowolenia

−2 i dostajemy od razu nukleolus (x

A

=

5, x

B

= 4, x

C

= 2).

nukleolus w grze z koniem wy´scigowym (zadanie 6 pula kooperacyjna)

oznaczenia: gracz 1 - A; gracz 2 - B; gracz 3 - C.

I

II

III

IV

V

v(A)=0

e = −x

A

{(A), (B), (C)}

-3

-1

v(B)=0

e = −x

B

{(AB), (AC), (BC)}

-3

-1

v(C)=0

e = −x

C

{(A), (BC)}

-3

-3/2

v(A,B)=1

e = 1 − x

A

− x

B

{(B), (AC)}

-1

-1/2

v(A,C)=2

e = 2 − x

A

− x

C

{(C), (AB)}

-2

-1

v(B,C)=0

e = −x

B

− x

C

v(A,B,C)=3

e = 0

Zaczynamy od najwi˛ekszego przeci˛etnego niezadowolenia

−1/2 i dostajemy od razu warunek na

niezadowolenie dla gracza

(B): e = −x

B

= −1/2 oraz koalicji (AC): e = 2 − x

A

− x

C

= −1/2. St ˛

ad

x

B

= 1/2 a x

A

+ x

C

= 5/2.

Te warunki nie prowadz ˛

a nas jeszcze jednoznacznie do otrzymania nukleolusa.

W dalszym ci ˛

agu liczenia nukleolusa nadal minimalizujemy leksykograficznie niezadowolenia

koalicji, a wi˛ec zaczynamy od tych rodzin w których mamy najwy˙zsz ˛

a ´sredni ˛

a po rodzinie

liczon ˛

a dla tych koalicji, których niezadowolenie mo˙zemy jeszcze regulowa´c.

4

OBLICZANIE NUKLEOLUSA W 3 OSOBOWYCH GRACH KOOPERACYJNYCH.

Na przykład w rodzinie

{(A), (B), (C)} do rozdziału zostało ju˙z tylko 2, 5 mi˛edzy A i C i przeci˛etne

niezadowolenie w tej rodzinie liczymy ju˙z tylko dla tych dwóch koalicji. Wynosi ono 1,25 podobnie jak

w rodzinie

{(AB), (AC), (BC)}.

Nowa tabelka dla tej gry ma posta´c:

I

II

III

IV

V

v(A)=0

e = −x

A

{(A), (B), (C)}

-3

-1,25

v(B)=0

e = −x

B

{(AB), (AC), (BC)}

-3

-1,25

v(C)=0

e = −x

C

{(A), (BC)}

-3

-3/2

v(A,B)=1

e = 1 − x

A

− x

B

{(B), (AC)}

-1

-1/2

v(A,C)=2

e = 2 − x

A

− x

C

{(C), (AB)}

-2

-1

v(B,C)=0

e = −x

B

− x

C

v(A,B,C)=3

e = 0

Kolejne najwy˙zsze przeci˛etne niezadowolenie wynosi

−1 w rodzinie {(C), (AB)}. Dostajemy wi˛ec

warunek na niezadowolenie koalicji

C: e

C

= −1. Zatem niezadowolenie koalicji A musi wynosi´c

e

A

= −(2, 5 − 1) = −1, 5.

Nukleolusem w tej grze jest podział

(x

A

= 3/2, x

B

= 1/2, x

C

= 1).