Nucleolus (Spieltheorie)

Der Nucleolus (auch Nukleolus geschrieben) ist ein einzelwertiges Lösungskonzept der kooperativen Spieltheorie. Dabei unterbreitet ein fairer Schlichter solange Aufteilungsvorschläge, bis der Wert der großen Koalition so verteilt wird, dass kein Spieler einen Nachteil daraus zieht. Um die Benachteiligung der Spieler zu messen, wird der sogenannte Koalitionsüberschuss verwendet.

Koalitionsüberschuss

Der (Koalitions-)Überschuss (engl.: excess) $e(S,x)$ beschreibt die Differenz zwischen dem Koalitionswert und der Auszahlung an diese Koalition. Eine Koalition ist bezüglich eines Auszahlungsvektors $x$ umso schlechtergestellt, je größer der Koalitionsüberschuss $e(S,x)$ ist. Deshalb kann der Koalitionsüberschuss auch als „Maß der Unzufriedenheit“ der Koalition $S$ bezüglich des Auszahlungsvektors $x$ angesehen werden. Die Funktion $(-1)\cdot e(S,x)$ wird als Zufriedenheit von $S$ mit $x$ bezeichnet. Bezüglich $e(S,x)$ ist darauf zu achten, wenn diese negative Zahlen annehmen. Dementsprechend sind diese Koalitionsüberschusse umso größer, je näher sie an der Null liegen.

In einem Spiel $\mathrm{\Gamma }(N,v)$ wird der Überschuss einer Koalition $S\subseteq N$ bezüglich eines Auszahlungsvektor $x\in I(v)$ beschrieben durch:

$e(S,x)=v(S)-\sum _{i\in S}{x}_i$.

Vektor der Koalitionsüberschüsse

Die Koalitionüberschüsse $e(S_i,x)$ mit $i\in \{1,2,...,2^n\}$ seien nicht-aufsteigend sortiert, sodass $e(S_1,x)$ die größte Unzufriedenheit beschreibt.

$e(S_1,x)$ wird in diesem Fall verkürzend durch ${\theta }_i(x)$ beschrieben.

Insgesamt ist der Vektor der geordneten Koalitionsüberschüsse $\mathrm{\Theta }(x)$ definiert mit:

$\mathrm{\Theta }(x)=({\theta }_1(x);{\theta }_2(x);{\theta }_3(x);....;{\theta }_{2^n}(x))$

wobei ${\theta }_i(x)\ge {\theta }_j(x)$ und $i\le j$ mit $i,j\in \{1,2,...,2^n\}$ gilt.

Dabei betragen die Überschusse der leeren Koalition als auch der großen Koalition Null.

Definition Nucleolus

Der Nucleolus wird nachfolgend in verbaler Form als auch mathematisch formaler Form beschrieben.

Nucleolus in verbaler Form

1. Schritt: Finde zunächst alle Imputationen, für die der größte Koalitionüberschuss, unter allen Koalitionen (außer der großen Koalition oder der leeren Koalition), so klein wie möglich ist. Wenn es nur genau eine solche Imputation gibt, dann ist der Nucleolus gefunden.

2. Schritt: Ist dies nicht der Fall, dann bestimme die Koalitionen, für die der gefundene größte Koalitionüberschuss, aus dem ersten Schritt, nicht weiter verringert werden kann. Fahre dann mit den verbleibenden Koalitionen fort und finde unter den im ersten Schritt gefundenen Imputationen diejenigen Imputationen, für die der größte Koalitionüberschuss, unter diesen verbleibenden Koalitionen, so gering wie möglich ist. Wenn es nur genau eine solche Imputation gibt, dann ist der Nucleolus gefunden.

3. Schritt: Ist dies nicht der Fall, dann bestimme die Koalitionen, für die der gefundene größte Koalitionüberschuss, aus dem zweiten Schritt, nicht weiter verringert werden kann. Fahre dann mit den verbleibenden Koalitionen fort und finde unter den im zweiten Schritt gefundenen Imputationen diejenigen Imputationen, für die der größte Koalitionüberschuss, unter diesen verbleibenden Koalitionen, so gering wie möglich ist. Wenn es nur genau eine solche Imputation gibt, dann ist der Nucleolus gefunden.

4. Schritt: usw.

Das Prinzip des Nucleolus ist somit die größte Unzufriedenheit zu minimieren. Gibt es dafür mehrere Möglichkeiten, dann wird auch die zweitgrößte Unzufriedenheit minimiert, und so weiter, bis eine eindeutige Verteilung erreicht ist.

Nucleolus in formaler Form

Der Nucleolus $nuc(v)$ eines Spieles $\mathrm{\Gamma }(N,v)$ ist ein Element $x$ der Menge aller Imputationen $I(v)$, die $\mathrm{\Theta }(x)$ lexikografisch minimiert:

$nuc(v)=\{x\in I(v)|\mathrm{\Theta }(x){\le }_{Lex}\mathrm{\Theta }(y)f\ddot{u}ralley\in I(v)\}.$

Beispiel

Koalitionsfunktion des (Bei-)Spiels

$S$	$\mathrm{\varnothing }$	$\{A\}$	$\{B\}$	$\{C\}$	$\{A,B\}$	$\{A,C\}$	$\{B,C\}$	$\{A,B,C\}$
$v(S)$	$0$	$200$	$200$	$200$	$700$	$500$	$500$	$1200$

Die Überschüsse des Spieles sind berechnet mit:

$S$	$\mathrm{\varnothing }$	$\{A\}$	$\{B\}$	$\{C\}$	$\{A,B\}$	$\{A,C\}$	$\{B,C\}$	$\{A,B,C\}$
$e(S,x)$	$0$	$200-x_A$	$200-x_B$	$200-x_C$	$700-(x_A+x_B)$	$500-(x_A+x_C)$	$500-(x_B+x_C)$	$0$

1. Schritt: Vorschlag: $x_1=(x_A,x_B,x_C)=(400,400,400)$

$S$	$\mathrm{\varnothing }$	$\{A\}$	$\{B\}$	$\{C\}$	$\{A,B\}$	$\{A,C\}$	$\{B,C\}$	$\{A,B,C\}$
$e(S,x)=\mathit{\theta }(x_1)$	$0$	$-200$	$-200$	$-200$	$-100$	$-300$	$-300$	$0$

Resultat: Vektor der geordneten Überschüsse: $\mathrm{\Theta }(x_1)=(0,0,-100,-200,-200,-200,-300,-300)$.

Fazit: Koalition $\{A,B\}$ ist am unzufriedensten.

Schlussfolgerung: Den Anteil der Koalition $\{A,B\}$ im nächsten Schritt erhöhen.

2. Schritt: Vorschlag: $x_2=(x_A,x_B,x_C)=(450,450,300)$

$S$	$\mathrm{\varnothing }$	$\{A\}$	$\{B\}$	$\{C\}$	$\{A,B\}$	$\{A,C\}$	$\{B,C\}$	$\{A,B,C\}$
$e(S,x)=\mathit{\theta }(x_2)$	$0$	$-250$	$-250$	$-100$	$-200$	$-250$	$-250$	$0$

Resultat: Vektor der geordneten Überschüsse: $\mathrm{\Theta }(x_2)=(0,0,-100,-200,-250,-250,-250,-250)$.

Vergleich beider Vektoren: Vektor $\mathrm{\Theta }(x_2)$ ist lexikografisch kleiner als Vektor $\mathrm{\Theta }(x_1)$: $\mathrm{\Theta }(x_2){<}_{Lex}\mathrm{\Theta }(x_1)$.

Fazit: Der Vektor der geordneter Überschüsse ist lexikografisch kleiner geworden, aber Koalitionär $\{C\}$ ist am unzufriedensten.

Schlussfolgerung: Den Anteil des Koalitionär $\{C\}$ im nächsten Schritt erhöhen.

3. Schritt: Vorschlag: $x_3=(x_A,x_B,x_C)=(420,420,360)$

$S$	$\mathrm{\varnothing }$	$\{A\}$	$\{B\}$	$\{C\}$	$\{A,B\}$	$\{A,C\}$	$\{B,C\}$	$\{A,B,C\}$
$e(S,x)=\mathit{\theta }(x_2)$	$0$	$-220$	$-220$	$-160$	$-140$	$-280$	$-280$	$0$

Resultat: Vektor der geordneten Überschüsse: $\mathrm{\Theta }(x_3)=(0,0,-140,-160,-220,-220,-280,-280)$.

Vergleich beider Vektoren: Vektor $\mathrm{\Theta }(x_3)$ ist lexikografisch kleiner als Vektor $\mathrm{\Theta }(x_2)$: $\mathrm{\Theta }(x_3){<}_{Lex}\mathrm{\Theta }(x_2)$.

Fazit: Der Vektor der geordneter Überschüsse ist lexikografisch kleiner geworden, aber Koalition $\{A,B\}$ ist am unzufriedensten.

Schlussfolgerung: Den Anteil der Koalition $\{A,B\}$ im nächsten Schritt erhöhen.

4. Schritt: Vorschlag: $x_4=(x_A,x_B,x_C)=(425,425,350)$

$S$	$\mathrm{\varnothing }$	$\{A\}$	$\{B\}$	$\{C\}$	$\{A,B\}$	$\{A,C\}$	$\{B,C\}$	$\{A,B,C\}$
$e(S,x)=\mathit{\theta }(x_2)$	$0$	$-225$	$-225$	$-150$	$-150$	$-275$	$-275$	$0$

Resultat: Vektor der geordneten Überschüsse: $\mathrm{\Theta }(x_4)=(0,0,-150,-150,-225,-225,-275,-275)$.

Vergleich beider Vektoren: Vektor $\mathrm{\Theta }(x_4)$ ist lexikografisch kleiner als Vektor $\mathrm{\Theta }(x_3)$: $\mathrm{\Theta }(x_4){<}_{Lex}\mathrm{\Theta }(x_3)$.

Fazit: Der Vektor der geordneter Überschüsse ist lexikografisch kleiner geworden. Außerdem ist keine Verbesserung im Sinne des Nucleolus mehr möglich.

Schlussfolgerung: Der Nucleolus ist gefunden mit $nuc(v)=(425,425,350)$.

Literatur

• Bastian Fromen: Faire Aufteilung in Unternehmensnetzwerken. Lösungsvorschläge auf der Basis der kooperativen Spieltheorie. Deutscher Universitäts-Verlag, Wiesbaden 2004, ISBN 978-3-8244-8164-4.
• Michael Maschler, Eilon Solan, Shmuel Zamir: Game Theory, 2nd Edition. Cambridge University Press, Cambridge 2020, ISBN 978-1-108-49345-1
• David Müller: Investitionscontrolling: Entscheidungsfindung bei Investitionen II: Entscheidungstheorie. 3. Aufl. Springer Gabler, Berlin u. a. 2022, ISBN 978-3-658-36596-7.
• Hans Peters: Game Theory, A Multi-Leveled Approach, Second Edition. Springer, Berlin u. a. 2015, ISBN 3-662-46949-9.
• David Schmeidler: The nucleolus of a characteristic function game. In: Journal of Applied Mathematics, Volume 17, Issue 6, 1969, Vorlage:DOI, S. 1163–1170.
• Harald Wiese: Kooperative Spieltheorie. Oldenbourg, München 2005, ISBN 3-486-57745-X, doi:10.1524/9783486837469.