Kooperative Spieltheorie

Aus Wikiludia
Wechseln zu: Navigation, Suche

Die kooperative Spieltheorie behandelt die Bildung von Koalitionen in kooperativen Spielen. Dabei versuchen die Spieler durch günstiges Koalieren, ihren eigenen Nutzen zu maximieren. Jeder möglichen Koalition (=Teilmenge der Menge aller Spieler) ist eine Auszahlung zugeordnet, die die Koalitionäre unter sich aufteilen können. Ziel ist nun, eine Koalition und eine Aufteilung des Koalitionsgewinnes zu finden, so dass es sich für keinen der Koalitionäre lohnt, ein anderes Bündnis einzugehen.

Lässt man in nichtkooperativen Spielen zu, dass die Spieler bindende Absprachen und eine Umverteilung der Auszahlungen vereinbaren können, kann man aus diesen nichtkooperativen Spielen kooperative Spiele entwickeln. Zum anderen können Spiele auf natürliche Weise, wie das Beispiel des Jazz-Orchesters zeigt, kooperative Spiele sein.

Inhaltsverzeichnis

Grundbegriffe der kooperativen Spieltheorie



Definition: Kooperatives Spiel

Ein kooperatives Spiel Γ ist ein Tupel (N,V), wobei der N = {1,...,m} mit m > 1 die Menge der Spieler bezeichnet und

 V: \mathcal{P}(N) \rightarrow \mathbf{\Re} mit    V(\emptyset)=0 und

 V(S \cup T)\geq V(S)+V(T) \qquad \forall S,T \subset N, S \cap T=\emptyset

eine Abbildung ist, die jeder Teilmenge der Menge N einen rellen Wert zuordnet. Die Abbildung V wird als Koalitionbewertung oder charakteristische Funktion bezeichnet. Teilmengen von N heißen Koalitionen.

Als Auszahlung oder Zuteilung (Imputation) bezeichnet man jeden Vektor u = (u1,u2,...,um) mit den Eigenschaften

 u_i \geq V(\{i\})\qquad \forall i \in \{1,...,m\} und  \sum_{i=1}^m  u_i=V(N) .


Bemerkung 1:
Ein kooperatives Spiel besteht also aus der Menge von Spieler und aus der Abbildung V, die jeder Koalition eine Auszahlung zuordnet. Die Subadditivität bedeutet, dass eine Koalition  S \cup T keine schlechteren Handlungsmöglichkeiten hat als die unabhängig handelnen Koalitionen S und T. Die Auszahlung können die Koalitionsmitglieder unter sich aufteilen. Eine solche Aufteilung des Koalitionsgewinns nennt man Imputation oder Zuteilung.

Bemerkung 2:
Die Komponente ui ist dabei der Teil des Gewinnes V(K) der gesamten Koalition K, den Spieler {i} schließlich erhält, falls die Koalition K gebildet wird.
 u_i \geq V(\{i\}) \qquad \forall i bedeutet, dass jeder Spieler bei einer Gewinnverteilung mindestens die Auszahlung erhält, die er erhalten würde, falls er mit keinem anderen koalieren würde.(Individuelle Rationalität)
 \sum_{i=1}^n  z_i=V(N) bedeutet, dass die Summe aller Auszahlung an die Spieler immer gleich der maximal möglichen Auszahlung V(N) an die gesamte Gruppe der Spieler ist.(Gruppen-Rationalität)

Satz (Koalitionsbewertung)

Die menge der zulässigen Koalitionsbewertungen ist bei festem N ein Vektorreaum über  \Re .
Das Nullellement ist

 V_0(S) \equiv 0 \quad \forall S \subset N

und eine Basis besteht z.B aus den folgenden Elementen:

 V_B :  \mathcal{P}(N) \rightarrow \mathbf{\Re} \quad mit \quad V_0(S) = \begin{cases} 1, & \mbox{falls }B \subset S \\ 0, & \mbox{falls }B \not\subset S  \end{cases} ,\qquad  B \not= \emptyset .

Die Funktionen VB bezeichnet man auch als elementare Koalitionsbewertung.

Für den Beweis des Satzes erweist sich der Begriff des Randwertes einer Koalition als nützlich. Der Randwert könnte als Koalitionsgewinn aufgefasst werden, der erst durch die Bildung der Koalition entsteht (Synergieeffekt).

Definition (Randwerte von Koalitionen)

Unter den Randwerten von Koalitionen B werden folgende rekursiv definierte Größen Größen rB verstanden:

 r_{\{i\}}(V) = V(\{i\}) \quad \forall i \in N

 r_B(V) = V(B) - \sum_{L: L \subset \not= B} r_L(V)\quad \forall B : B \subset N \wedge \mid B \mid > 1 .

Satz (Randwerte von Koalitionen)

Für den Randwert rB einer Koalition B gilt:

 r_B(V) = \sum_{L: L \subset B} (-1)^{\mid B \mid - \mid L \mid} V(L) .

Der Beweis erfolgt durch Induktion über die Anzahl der Elemente der Teilmengen.

Beweis (zu Satz (Koalitionsbewertung))

1. Zunächst zeigen wir die lineare Unabhängigkeit dieser elementaren Koalitionsbewertungen. Der Beweis erfolgt durch Induktion über die Anzahl von  \mid R \mid . Es ist zu zeigen, dass

 V_0(S) = \sum_{B \subset N, B \not= \emptyset} \lambda_B V_B (S) = \sum _{j = 1}^m \left[ {\sum _{B \subset N, B \not= \emptyset}\lambda_B V_B (S)}\right]

nur für λB = 0 erfüllt ist. Als Erstes werden die einelementigen Koalitionen S = {i},i = 1,...,m eingesetzt. Berücksichtigt man

 V_B (\{i\}) = \begin{cases} 1, & \mbox{falls }B = \{i\} \\ 0, & \mbox{sonst } \end{cases} ,

so ergibt sich 0 = V0({i}) = λ{i}.
Nun nehmen wir an, dass bereits gezeigt wurde, dass  \lambda_B = 0 \quad \forall B: \mid B \mid \ge k . Es gilt also

 V_0(S) = \sum _{j =k + 1}^m \left[ {\sum _{B \subseteq  N, B \not= \emptyset}\lambda_B V_B (S)}\right]

Wir setzen nun für S ein  \{i_1 .... i_k+1\} \subseteq N ein und erhalten für alle  B: \mid B \mid \ge 2

 V_B (\{i_1,...,i_k+1\}) = \begin{cases} 1, & \mbox{falls }B = \{i_1,...,i_k+1\} \\ 0, & \mbox{falls } \mid B \mid \ge 2  und B \not= \{i_1,...,i_k+1\}\end{cases}

Somit folgt aus  0 = V_0 (\{i\}) = \lambda_{\{i_1,...,i_k+1\}} ebenfalls λR = 0 für alle  R: \mid R \mid = k + 1 . Letztendlich ergibt sich, dass alle λB = 0 sein müssen.
Dies war zu zeigen.

2. Es wird jetzt gezeigt,dass es für jede beliebige Koalitionsbewertung V geeignete λB = λB(V) gibt, so dass
 V = \sum_{B \subseteq N, B \not= \emptyset} \lambda_B V_B

gilt. Es muss gezeigt werden:

 V(M) = \gamma \qquad \gamma = \sum_{B: B \subset N, B \not= \emptyset} \lambda_B (V) V_B (M)\quad \forall M \subseteq N .

Für λB(V) setzen wir ein:

 \lambda_B(V) = \sum_{L: L \subset B} (-1)^{\mid B \mid - \mid L \mid} V(L) .

Somit ergibt sich

 \gamma = \sum_{B: B \subset M, B \not= \emptyset} \sum_{L: L \subset B} (-1)^{\mid B \mid - \mid L \mid} V(L)V_B(M) .

Berücksichtigt man die Definition von VB(M) , so folgt weiter

 \gamma = \sum_{B: B \subset M, B \not= \emptyset} \sum_{L: L \subset B} (-1)^{\mid B \mid - \mid L \mid} V(L) .

Vertauschen der beiden Summen und abzählen der  (-1)^{\mid B \mid - \mid L \mid} liefert

 \gamma = \sum_{L \subset M} \left[ \sum_{B: L \subset B \subset M} (-1)^{\mid B \mid - \mid L \mid} \right] V(L)

 = \sum_{L \subset M} \left[ \sum_{b = \mid L \mid}^{\mid M \mid} \sum_{\mid B \mid = b, B: L \subset B \subset M} (-1)^{\mid B \mid - \mid L \mid} \right]  V(L) .

Da eine Menge B von b Elementen, die eine Menge L enthält, aus einer Menge M auf  {\mid M \mid - \mid L \mid \choose b - \mid L \mid} verschiedene Weisen gewählt werden kann, folgt weiter

 \gamma = \sum_{L \subset M} \left[ \sum_{b = \mid L \mid}^{\mid M \mid} {\mid M \mid - \mid L \mid \choose b - \mid L \mid}  (-1)^{\mid B \mid - \mid L \mid} \right]  V(L) .

Die Indextransformation  \beta = b - \mid L \mid und die Anwendung der binomischen Formel liefert

 \sum_{b = \mid L \mid}^{\mid M \mid} {\mid M \mid - \mid L \mid \choose b - \mid L \mid} (-1)^{\mid B \mid - \mid L \mid} = \sum_{\beta = 0}^{\mid M \mid - \mid L \mid} {\mid M \mid - \mid L \mid \choose \beta}(-1)^\beta (+1)^{\mid M \mid - \mid L \mid - \beta} = (-1+1)^\mid M \mid - \mid L \mid = \begin{cases} 0, & \mbox{falls } \mid M \mid - \mid L \mid > 0 \\ 1, & \mbox{falls } \mid M \mid - \mid L \mid = 0 \end{cases} .

Eingesetzt ergibt sich

 \gamma = \sum_{L = M} \left[ \sum_{b = \mid L \mid}^{\mid M \mid} {\mid M \mid - \mid L \mid \choose b - \mid L \mid}  (-1)^{\mid B \mid - \mid L \mid} \right]  V(L) = \sum_{L \subset M, L \not= M} \left[ \sum_{b = \mid L \mid}^{\mid M \mid} {\mid M \mid - \mid L \mid \choose b - \mid L \mid}  (-1)^{\mid B \mid - \mid L \mid} \right]  V(L) = V(M) + 0 .

Damit ist die Darstellung einer Koalitionsbewertung durch elementare Koalitionsbewertungen gezeigt. Bleibt noch die Eindeutigkeit. Diese folgt aus der Eigenschaft, dass die elementaren Koalitionsbewertungen eine Basis bilden.

Bemerkung
Es gibt sicher noch andere Basen des Vektorraums der Koalitionsbewertungen, aber genau die genannte dient späteren Überlegungen über die Shaplay-Zuteilung.

Definiton (Dummy-Spieler)

Ein Spieler heißt Dummy-Spieler, falls

 V(S \cup  \{i\}) = V(S) \quad \forall S \subseteq N.

Definiton (unkooperativer Spieler)

Ein Spieler heißt unkooperativ, falls

 V(S \cup  \{i\}) - V(S) \leq   V(\{i\}) \quad \forall S \subseteq N.

Definiton (superadditive Koalitionsbewertung)

Eine Koalitionsbewertung heißt superadditiv, wenn

 V(S) + V(T) \leq V(S \cup T) - V(S) \quad \forall S, T \subseteq N: S \cap T = \emptyset .

Bemerkung
Die Bedeutung der Superadditivität liegt darin, dass der Zusammenschluss zu grösseren Koalitionen mehr an Wert bringt.
Superadditivität wird generell nicht vorausgesetzt.

Definiton (wesentliches Spiel)

Ein Spiel heißt wesentlich, wenn

 \sum_{i=1}^m V(\{i\}) < V(N) ,

andernfalls unwesentlich.

Satz (unwesentliches Spiel)

Ein unwesentliches Spiel hat höchstens eine Imputation, nämlich (V({1}),V({2}),...,V({m})).
Ein wesentliches Spiel hat unendlich viele verschiedene Imputationen.

Beweis

Es werde nun angenommen, dass das unwesentliche Spiel eine Imputation u habe. Dann gilt

 V(N) \le \sum_{i=1}^m V(\{i\}) \le \sum_{i=1}^m u_i = V(N).

Daher muss also überall Gleichheit gelten, insbesondere ui = V({i}, wegen  u_i \geq  V (\{i\} .
Im Falle der wesentlichen Spiele kann die positive Größe

 V(N) - \sum_{i=1}^m V(\{i\}) > 0

auf unendlich viele verschiedene Weisen in m positive Summanden εi zerlegt werden, so dass sich unendlich viele verschiedene Imputationen ui = V({i} + εi,i = 1,2,,...,m ergeben.

Bemerkung
Ein kooperatives Spiel mit einem Spieler (m = 1) ist unwesentlich, da immer gilt

V(N) = V({1}),

was der Definition eines unwesentlichen Spieles entspricht.

Definiton (additive Koalitionsbewertung)

Eine Koalitionsbewertung heißt additiv, wenn

 V(B) = \sum_{i \in B}V(\{1\}) \forall B \subseteq N .

Zusammenhang von kooperativen und nichtkooperativen Spiel

Kooperative Spiele können auch durch Zulassen von Absprachen der Spieler in einem nichtkooperativen Spiel in extensiver oder Normalform generiert werden. Dabei ist die für ein kooperatives Spiel benötigte Spielermenge bereits durch das nichtkooperative spiel gegeben. Somit muß lediglich eine passende Koalitionsbewertung bestimmt werden (vgl. Bestimmung einer Koalitionsbewertung).

Äquivalenz bei kooperativen Spielen

Strategische Äquivalenz

Definition (Strategische Äquivalenz kooperativen Spielen)

Zwei kooperative Spiele ΓK(N,V) und  \tilde {\Gamma}_K (N,\tilde V) mit den gleichen Spielern N heißen strategisch äquivalent, falls es ein k > 0 und  c_i \in \Re, i = 1, ... , m gibt , so dass

 \tilde V(B) = k \times V(B) + \sum _{i \in B}c_i \quad \forall B \subseteq  N.

Satz

Die Menge der Zuteilungen strategisch äquivalenter kooperativer Spiele können umkehrbar eindeutig aufeinander abgebildet werden.

Beweis

Wir gehen aus von der Beziehung

 \tilde V(B) = kV(B) + \sum _{i \in B}c_i

Es seien die Bedingungen der Imputation für das ursprungliche Spiel erfüllt, d.h.:

 u_i \geq V(\{i\}) \qquad \sum_{i=1}^m u_i = V(N) .

Die Multiplikation beider Beziehungen mit k > 0 und Addition mit ci liefert

 \tilde u_i = ku_i + c_i \quad i = 1,...,m .

und damit die Behauptung.
Der Umkehrschluss vom neuen Spiel auf das alte folgt aus:

 u_i = {1 \over k} \tilde u_i - {c_i \over k}  .

Definition (Null-Spiel)

Ein kooperatives Spiel haißt ein Null-Spiel, wenn seine Koalitionsbewertung identisch 0 ist.

Satz (Null-Spiel)

Jedes superadditive unwesentliche Spiel ist einem Null-Spiel strategisch äquivalent.

Beweis

Für das strategisch äquivalente Spiel nehmen wir k = 1 und ci = − V({i}).
Da bei diesem unwesentlichen Spiel

 V(B) = \sum_{i \in B} V(\{i\}) \qquad \forall B

ist, gilt offensichtlich

 \tilde V(B) = 0 \qquad \forall B .

'Bemerkung
Die superadditiven unwesentlichen Spiele bilden genau eine Äquivalenzklasse.

Definition (0-1 reduziertes kooperatives Spiel)

Ein kooperatives Spiel heißt ein 0-1 reduziertes kooperatives Spiel, wenn sein Koalitionsbewertung folgende Eigenschaften hat:

 V(\{i\}) = 0 \quad i = 1,...,m \quad V(N) = 1 .

Bemerkung
Die Menge aller Imputationen eines 0-1 reduzierten Spieles ist gegeben durch

 \{ (u_1,...,u_m)\mid \sum_{i=1}^m u_i = 1 \qquad u_i \geq 0 \quad i = 1,...m \} .

Beachte: Es kann für beliebige andere B keine Aussage über die Werte V(B) gemacht werden.

Satz (0-1 reduziertes kooperatives Spiel)

Jedes wesentliche kooperative Spiel ist einem 0-1 reduzierten kooperativen Spiel strategisch äquivalent.

Beweis

 \tilde V(\{i\}) = kV(\{i\}) + c_i = 0 \quad i = 1,...m

 \tilde V(N) = kV(N) + \sum_{i=1}^m c_i = 1

Hieraus lassen sich k und ci berechnen

 k = {1 \over V(N) - \sum_{i=1}^m V(\{i\})}

 c_i = {V(\{i\}) \over V(N) - \sum_{i=1}^m V(\{i\})} \quad i = 1,...m .

Wegen der Wesentlichkeit des Spieles ist wie gefordert k > 0

Dominanz-Äquivalenz

Definition

Eine Imputation x = (x1,...,xm) dominiert eine Imputation y = (y1,...,ym) bezüglich der Koaltion B (oder auch durch die Koaltion B) , falls

Bedingung der Effektivität

 \sum_{i \in B} x_i \leq V(B)

Bedingung der Präferenz

 x_i>y_i \qquad \forall i \in B

Bezeichnung:  x \, >_B \,y

Definition

Eine Imputation x dominiert die Imputation y, in Zeichen x > y, wenn es eine Koalition B gilt, so dass  x \, >_B \,y .

Definition (Dominanz-Äquivalenz)

Zwei kooperative Spiele Γk = (N,V) und Γk' = (N',V') mit  \left| N \right| = \left| N' \right| heißen dominanzäquivalent, wenn es eine umkehrbar eindeutige Abbildung gibt, die die Menge der Zuteilungen Z und Z' unter der Beibehaltung der Dominanzstruktur aufeinander abbildet.

Bemerkung
Die in der Definition angesprochene Abbildung beinhaltet unter Umständen auch eine Umnummerierung bzw. geeignete Zuordnung der Spieler der beiden Spiele. Die Dominanz bleibt bei strategischer Äquivalenz erhalten.

Satz (Dominanz bei strategischer Äquivalenz)

Seien Γk = (N,V) und  \tilde \Gamma_k = (N,\tilde V) zwei strategisch äquivalente kooperative Spiele und seien x, y bzw.  \tilde x, \tilde y strategisch äquivalente Imputationen für Γk bzw.  \tilde \Gamma_k , dann folgt aus  x \, >_B \,y die Beziehung  \tilde x \, >_B \, \tilde y .

Beweis

Sei

 \tilde V(B) = kV(B) + \sum_{i \in B} c_i \qquad mit \, \, k > 0, c_i \in \Re \quad \forall B \subset N .

Aus yi < xi folgt dann  \tilde y_i = ky_i + c_i < kx_i + c_i = \tilde x_i . Ferner gilt

 \sum_{i \in B} \tilde x_i = \sum_{i \in B} (kx_i + c_i) = k \, \sum_{i \in B} x_i + \sum_{i \in B} c_i \leq  kV(B) + \sum_{i \in B} c_i = \tilde V(B) .

Damit sind alle Eigenschaften der Dominanz für  \tilde \Gamma_k gezeigt.

Bemerkung Zur Untersuchung der Dominanzstruktur genügt es daher in vielen Fällen die strategischen Äquivalenzklassen von Spielen zu betrachten. Teilweise genügt die Betrachtung von superadditiven Spielen wie die folgende Definition und der darauf folgende Satz zeigt.

Definition (superadditive Hülle)

Als superadditive Hülle eines kooperativen Spieles ΓK = (N,V) bezeichnet man das Spiel  \tilde \Gamma _K = (N,\tilde V) mit

 \tilde V(T) = max_{S(T)} \sum_{B \in S(T)} V(B) \qquad \forall T \subseteq N ,

wobei S(T) die Menge aller Zerlegungen von  T \subseteq N ist.

Satz

Die superadditive Hülle  \tilde \Gamma _K = (N,\tilde V) eines kooperativen Spiels ΓK = (N,V) ist ein superadditives kooperatives Spiel.
Ferner gilt  \tilde V(\{i\}) = V(\{i\}) \quad \forall i \in N \quad und \quad \tilde V(B) \geq  V(B) \quad \forall B \subseteq N .

Beweis

Entsprechend der Definition der superadditiven Hülle

 \tilde V(T) = max_{S(T)} \sum_{B \in S(T)} V(B)
ist {T} eine mögliche Zerlegung von T. Daher gilt  \tilde V(T) \geq V(T) . Ist T einelementig, so ist dies die einzige Zerlegung von T und es gilt Gleichheit. Sei  T \cap  Q = \emptyset . Ferner E irgendeine Zerlegung von T, F eine Zerlegung von Q und G eien Zerlegung von  T \cup  Q .
Die Menge  T \cup  Q  = \{ B \mid  B \in E \wedge  B \in F \} ist immer eine spezielle Zerlegung von  T \cup  Q .
Damit gilt

 \tilde V(T \cup  Q) = max_G \sum_{B \in G}V(B) \geq max_E \, max_F \sum_{B \in {T \cup  Q}}V(B) = max_E \sum_{B \in E}V(B) + max_F \sum_{B \in F}V(B) = \tilde V(T) + \tilde V(Q)

Also das Spiel  \tilde \Gamma_k ist superadditiv.

Satz

Ein kooperatives Spiel Γk = (N,V) ist zu seiner superadditiven Hülle  \tilde \Gamma_k  = (N,\tilde V) dominanz-äquivalent, wenn  V(N) = \tilde V(N) .

Beweis

Unwesentliche Spiele, für die eine Zuteilung exestiert, sind einem Nullspiel strategisch, also auch dominanz-äquivalent. Null-Spiele sind superadditiv und somit identisch zu ihrer superadditiven Hülle.
Betrachten wir nun wesentliche Spiele.
Als erstes zeigen wir, dass Zuteilungen x im Spiel  \tilde \Gamma_k auch im Spiel Γk Zuteilungen sind und umgekehrt. Dies folgt aus den beiden Beziehungen

 x_i \geq \tilde V(\{i\}) = V(\{i\}) \quad \forall i \in N \qquad \sum_{i=1}^m x_i = \tilde V(N) = V(N) .

Beweis der Dominanz-Äquivalenz

Fall 1
Im Spiel Γk gelte für die Zuteilungen x und y die Relation x > y. Es gibt dann ein  B \subseteq  N mit

 x_i > y_i \quad \forall i \in B \quad \wedge \quad x(B) \leq V(B) \leq \tilde V(B) .

Somit gilt auch x > y im Spiel  \tilde \Gamma_k .

Fall 2
Im Spiel  \tilde \Gamma_k gelte für die Zuteilungen x und y die Relation x > y. Es gibt somit ein  T \subseteq N mit

 x_i > y_i \quad \forall i \in T \quad \wedge \quad x(T) \leq  \tilde V(T) .

Nehmen wir an, dass es eine Zerlegung E von T gibt, mit

 x(T) \leq  \tilde V(T) = \sum_{B \in E} V(B).

Ferner gibt es mindestens ein  B \in E , so dass  x(B) \leq V(B) . Andernfalls wäre  x(B) > V(B), \, \forall B \in E , mit der Konsequenz

 x(T) = \sum_{B \in E}x(B) >  \sum_{B \in E} V(B) = \tilde V(T),

was ein Wiederspruch zu der Annahme wäre.
Da auch  x_i > y_i \quad \forall i \in T gilt, folgt aus  B \subseteq T

 x_i > y_i \quad \forall i \in B \quad \wedge \quad x(B) \leq V(B) gilt, folgt aus  B \subseteq T
und jede Dominanz-Beziehung im Spiel  \tilde \Gamma_k gilt also auch im Spiel Γk.

Lösungskonzepte in der kooperativen Spieltheorie

Der Kern eines kooperativen Spieles

Wie bereits in der Bemerkung zur Definition des Begriffes der Dominanz erläutert, werden sich in einem kooperativen Spiel alle Spieler mit einer Imputation zufrieden sein, die von keiner anderen dominiert wird. Denn es lässt sich neben der Koalition, die der nicht dominierten Imputation x zugrunde liegt, keine weitere Koalition mit einer zugehörigen Imputation y finden, bei der alle Mitglieder mehr erhalten als bei x. Damit ist es keinem Spieler möglich erfolgreich Widerstand gegen eine nicht dominierte Imputation zu leisten. Das heißt, dass sich letztlich nur Koalitionen bilden können, zu welchen man eine nicht dominierte Imputation finden lässt.

Satz über nicht dominierte Imputationen
Alle Imputationen z, die die Ungleichungen
 V(K) \leq \sum_{i \in K} z_i
erfüllen, werden nicht dominiert.
Beweis:
Eine dominierte Zuteilung müsste insbesondere für eine Koalition K die Bedingung
 V(K) > \sum_{i \in K} z_i
erfüllen. Dies trifft jedoch für die Zuteilungen, die die Ungleichung im obenstehenden Satz erfüllen, nicht zu.

Definition: Kern eines kooperativen Spieles
Bei einem kooperativen Spiel Γ heißt die Menge der Imputationen z, die die linearen Ungleichungen
 V(K) > \sum_{i \in K} z_i
erfüllen, der Kern K(Γ) des Spieles.




Die Shapley-Auszahlung


Der Kern eines Spiels ist häufig leer oder besteht aus einem Kontinuum von Punkten (Auszahlungsprofilen). Wünschenswert wäre aber eine eindeutige Zuteilung des Gewinns einer Koalition.
Um diese Eindeutigkeit zu erreichen, formulierte Shapley 1953 drei Axiome, die zu einem eindeutigen Auszahlungsprofil führen:

Symmetrie
der Auszahlung für alle Permutationen Π von Spielern mit V(\Pi(S)) = V(S) \,\forall S gelte´ αΠ(i) = αi.
Strohmänner
sind Spieler j mit V(S) = (S\setminus\{j\}) + V(S) \, \forall S. Für sie setze αj = V({j}).
Additivität
zweier Spiele Γ und Γ' mit α(V) und α'(V) bestehe darin, daß α(V + V') = α(V) + α(V') für alle Spieler.

Beispiele:

Meine Werkzeuge