Shapley-Wert

Der Shapley-Wert (benannt nach Lloyd Shapley) ist ein punktwertiges Lösungs-Konzept aus der kooperativen Spieltheorie. Er gibt an, welche Auszahlung die Spieler in Abhängigkeit von einer Koalitionsfunktion erwarten können (positive Interpretation) oder erhalten sollten (normative Interpretation).

Sei N die Menge der Spieler, n = |N| und v die charakteristische Funktion des Spiels (v(S) ist der Wert der Koalition, also die Höhe der Kosteneinsparung durch Koalitionsbildung). Dann ist der Shapley-Wert (Auszahlung) für Spieler i definiert als

$x_i(v,N)=\sum_{S\subseteq N}{\frac{(n-|S|)!(|S|-1)!}{n!}}(v(S)-v(S\setminus\lbrace i\rbrace))$

Er ist die einzige Auszahlungsfunktion, welche die folgenden vier Axiome erfüllt:

• Pareto-Effizienz: Der Wert der großen Koalition wird an die Spieler verteilt.
• Symmetrie-Axiom: Spieler mit gleichen marginalen Beiträgen erhalten das gleiche.
• Null-Spieler-Axiom: Ein Spieler mit marginalem Beitrag null zu jeder Koalition erhält null.
• Additivitäts-Axiom: Wenn das Spiel in zwei unabhängige Spiele zerlegt werden kann, mit den charakteristischen Funktionen v und w, dann soll die Auszahlung jedes Spielers im zusammengesetzten Spiel der Summe der Auszahlungen in den aufgeteilten Spielen entsprechen.

Erklärung der Auszahlungsfunktion

Im : $\frac{(n-|S|)!(|S|-1)!}{n!}$ gibt der Zähler die Anzahl möglicher Permutationen an, in denen Spieler i zu einer in beliebiger Reihenfolge entstandenen Koalition von Spielern aus S dazukommt. n! ist die Anzahl aller möglichen Permutationen. Also ergibt der Term zusammen den Anteil an Permutationen, in denen Spieler i nach den anderen Spielern aus S und vor den Spielern aus N\S auftritt (siehe auch Multinomialkoeffizienten).

Der Term

$v(S)-v(S\setminus\lbrace i\rbrace)$

gibt den marginalen Beitrag an, der dadurch entsteht, dass Spieler i der Koalition S beitritt.

(Im Fall $i \notin S$ ist der Term Null, daher braucht in der Formel der Fall $i\notin S$ nicht unterschieden zu werden.)

Insgesamt ordnet damit der Shapley-Wert jedem Spieler den durchschnittlichen marginalen Beitrag zu.

Alternative Berechnung

Manchmal kann es einfacher sein, den Shapley-Wert gemäß folgender Formel zu berechnen, die äquivalent zur obigen Definition ist.

$x_i(v,N)= \frac{1}{n!} \sum_{P \in \mathcal{P}} v(S_i(P) \cup \{i\}) - v(S_i(P))$

Dabei ist P eine mögliche Permutation, also genau eine Möglichkeit, alle Spieler in einer Reihe anzuordnen. Es gibt n! verschiedene Permutationen. $\mathcal{P}$ bezeichnet die Menge aller möglichen Permutationen. $\; S_i(P)$ ist die Menge derjenigen Spieler, die in Permutation P vor Spieler i stehen. Für jede Permutation wird also bestimmt, welchen zusätzlichen Nutzen Spieler i durch seine Teilnahme generiert. Über diese Werte wird dann der Durchschnitt gebildet.

Literatur

• Lloyd S. Shapley: A Value for n-person Games. In: H.W. Kuhn und A.W. Tucker (Hrsg.): Contributions to the Theory of Games, volume II. (Annals of Mathematics Studies v. 28), Princeton University Press, Princeton 1953. Seiten 307-317, ISBN 0-691-07935-8.
• Harald Wiese: Kooperative Spieltheorie, Oldenbourg, München, 2005, ISBN 3-486-57745-X.