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

Beispiel

Gegeben seien drei Spieler, welche mit den Kürzeln ${\displaystyle a,b}$ und ${\displaystyle c}$ bezeichnet werden, d. h. ${\displaystyle N=\left\{a,b,c\right\}}$, und die folgende Werte erzielen können:

Dabei steht beispielsweise ${\displaystyle v(\left\{b\right\})=6}$ dafür, dass die „Koalition“ bestehend nur aus Spieler ${\displaystyle b}$ allein den Wert ${\displaystyle 6}$ erreichen kann; ${\displaystyle v(\left\{a,b\right\})=24}$ bedeutet, dass eine Koalition aus Spieler ${\displaystyle a}$ zusammen mit ${\displaystyle b}$ den Wert ${\displaystyle 24}$ erschaffen kann; wegen ${\displaystyle v(\left\{a,b,c\right\})=36}$ können alle Spieler gemeinsam den Wert ${\displaystyle 36}$ erzeugen.

Der Shapley-Wert dient der Aufteilung des Wertes ${\displaystyle v(\left\{a,b,c\right\})=36}$. Folgendes Verfahren ist möglich, um den Shapley-Wert eines Spielers ${\displaystyle i}$ zu bestimmen: Man notiert sämtliche Reihenfolgen, in denen die Spieler angeordnet werden können. Für jede Reihenfolge ermittelt man den Wert der Koalition, die aus jenen Spielern besteht, die vor dem betrachteten Spieler ${\displaystyle i}$ gelistet sind. Man notiert den Wert, den diese Koalition gemeinsam mit dem Spieler ${\displaystyle i}$ hat, und bildet die Differenz, also den sogenannten marginalen Beitrag von Spieler ${\displaystyle i}$ in der betrachteten Reihenfolge. Schließlich nimmt man den Durchschnitt von diesen marginalen Beiträgen und erhält den Shapley-Wert des Spielers ${\displaystyle i}$. Die folgende Tabelle gibt diese Überlegungen für Spieler ${\displaystyle b}$ wieder:

Der Durchschnitt der marginalen Beiträge ergibt für Spieler ${\displaystyle b}$ den Shapley-Wert

${\displaystyle \mathrm {Sh} _{b}(\{a,b,c\},v)=(12+9+6+6+9+6)/6=8.}$

Analog bestimmt man die Shapley-Werte der Spieler ${\displaystyle a}$ und ${\displaystyle c}$ und erhält

${\displaystyle \mathrm {Sh} _{a}(\{a,b,c\},v)=17}$      und      ${\displaystyle \mathrm {Sh} _{c}(\{a,b,c\},v)=11.}$

Allgemeine Definition

Gegeben sei ein kooperatives Spiel mit transferierbarem Nutzen, das heißt gegeben sei

• eine endliche Spielermenge ${\displaystyle N}$ mit ${\displaystyle n:=|N|}$ Elementen und
• eine Koalitionsfunktion ${\displaystyle v}$, die jeder Teilmenge von ${\displaystyle N}$ eine reelle Zahl zuweist und insbesondere der leeren Koalition den Wert ${\displaystyle 0}$ gibt:

${\displaystyle {\begin{array}{rcccl}v&:&{\mathcal {P}}(N)&\longrightarrow &\mathbb {R} \\&:&v(\emptyset )&\mapsto &0\\\end{array}}}$

wobei ${\displaystyle {\mathcal {P}}(N)}$ die Potenzmenge von ${\displaystyle N}$ bezeichnet, also die Menge aller Teilmengen. Eine Teilmenge der Spieler ${\displaystyle S\subseteq N}$ heißt Koalition. Den Ausdruck ${\displaystyle v(S)}$ nennt man den Wert der Koalition ${\displaystyle S}$.

Der Shapley-Wert ordnet nun jedem Spieler aus ${\displaystyle N}$ eine Auszahlung für das Spiel ${\displaystyle v}$ zu. Hierzu gibt es unterschiedliche Formeln, die zum gleichen Ergebnis führen.

Reihenfolgendefinition

Zunächst wird der marginale Beitrag eines Spielers ${\displaystyle i\in N}$ für eine gegebene Reihenfolge der Spieler definiert. Sei ${\displaystyle \sigma }$ eine Reihenfolge der Spielermenge mit der Interpretation, dass Spieler ${\displaystyle i}$ an Position ${\displaystyle \sigma (i)}$ in ${\displaystyle \sigma }$ gelistet ist. Für einen Spieler ${\displaystyle j\in N}$, der vor Spieler ${\displaystyle i}$ in ${\displaystyle \sigma }$ aufgelistet ist, gilt ${\displaystyle \sigma (j)<\sigma (i)}$. Die Vorgänger von ${\displaystyle i}$ in ${\displaystyle \sigma }$ befinden sich also in der Menge

${\displaystyle P_{i}^{\sigma }=\{j\in N\colon \sigma (j)<\sigma (i)\}}$.

Werden die Spieler gemäß der Reihenfolge ${\displaystyle \sigma }$ nacheinander zu einer Koalition hinzugefügt, so trägt der Spieler ${\displaystyle i}$ folgenden marginalen Beitrag in ${\displaystyle \sigma }$ bei:

${\displaystyle v(P_{i}^{\sigma }\cup \{i\})-v(P_{i}^{\sigma })}$.

Der Shapley-Wert eines Spielers ${\displaystyle i}$ errechnet sich als der Durchschnitt der marginalen Beiträge über alle möglichen ${\displaystyle n!}$ Reihenfolgen:

${\displaystyle \mathrm {Sh} _{i}(N,v)={\frac {1}{n!}}\cdot \sum _{\sigma \in {\mathcal {R}}}[v(P_{i}^{\sigma }\cup \{i\})-v(P_{i}^{\sigma })]}$

wobei ${\displaystyle {\mathcal {R}}}$ die Menge aller möglicher Reihenfolgen der Spieler bezeichnet.

Hinweis: Obiges Beispiel ist gemäß dieser Definition berechnet. Für ${\displaystyle \sigma =(c,a,b)}$ ist z. B. ${\displaystyle P_{b}^{\sigma }=\{a,c\}}$ und ${\displaystyle v(P_{b}^{\sigma }\cup \{b\})-v(P_{b}^{\sigma })=36-27=9.}$

Teilmengendefinition

Der marginale Beitrag eines Spielers ${\displaystyle i\in N}$ zu einer gegebenen Koalition ${\displaystyle S\subseteq N}$ ist

${\displaystyle v(S\cup \{i\})-v(S).}$

Der Shapley-Wert eines Spielers ${\displaystyle i}$ errechnet sich als das gewichtete Mittel der marginalen Beiträge zu allen möglichen Koalitionen:

${\displaystyle \mathrm {Sh} _{i}(N,v)=\sum _{S\subseteq N\setminus \{i\}}{\frac {(n-1-|S|)!\cdot |S|!}{n!}}(v(S\cup \{i\})-v(S))}$

Ausgehend von der Reihenfolgendefinition des Shapley-Wertes lässt sich diese Formel nun wie folgt verstehen: Für jedes ${\displaystyle S\subseteq N\setminus \{i\}}$ gibt es

${\displaystyle (n-1-|S|)!\cdot |S|!}$

Reihenfolgen, so dass ${\displaystyle P_{i}^{\sigma }=S}$ gilt, denn es gibt ${\displaystyle |S|!}$ Möglichkeiten, die Spieler aus ${\displaystyle S}$ vor dem Spieler ${\displaystyle i}$ anzuordnen und ${\displaystyle (n-|S|-1)!}$ Möglichkeiten, die Spieler aus ${\displaystyle N\setminus \{S\cup \{i\}\}}$ hinter dem Spieler ${\displaystyle i}$ anzuordnen (siehe auch Multinomialkoeffizienten).

Beispiel

Man betrachte erneut obiges Beispiel und nehme den Fall ${\displaystyle S=\{a,c\}}$. Es ist dann ${\displaystyle P_{b}^{\sigma }=S}$ genau für die beiden Reihenfolgen ${\displaystyle (a,c,b)}$ und ${\displaystyle (c,a,b)}$. Es gilt also ${\displaystyle (n-1-|S|)!\cdot |S|!=(3-2-1)!\cdot 2!=2}$. Anstatt über alle Reihenfolgen zu gehen, könne man also auch folgende Tabelle aufstellen:

Der Durchschnitt der marginalen Beiträge ergibt für Spiele ${\displaystyle b}$ in der Menge ${\displaystyle N=\{a,b,c\}}$ den Shapley-Wert

${\displaystyle \mathrm {Sh} _{b}(N,v)=(2\cdot 6+1\cdot 12+1\cdot 6+2\cdot 9)/6=8.}$

Definition via Harsanyi-Dividenden

Eine weitere Berechnungsmöglichkeit liefert zugleich eine bessere Einsicht in die Struktur einer Koalitionsfunktion.

Harsanyi-Dividenden

Folgendes Argument wird häufig auf John Harsanyi zurückgeführt. Man betrachte eine Koalition ${\displaystyle S}$ und ihren Wert ${\displaystyle v(S)}$. Welcher Anteil von ${\displaystyle v(S)}$ entsteht wirklich durch die Kombination von allen Mitgliedern aus ${\displaystyle S}$, und nicht schon durch die Kombination der in ${\displaystyle S}$ enthaltenen Untergruppierungen? Das heißt, welcher Teil von ${\displaystyle v(S)}$ ist nicht bereits auf die Errungenschaft irgendeiner Untergruppierung zurückzuführen? Zur Beantwortung wird rekursiv vorgegangen. Zunächst ist die tatsächliche Leistung einer leeren Koalition nichts, ${\displaystyle \lambda _{\emptyset }^{v}=0}$. Die weiteren tatsächlichen Leistungen ergeben sich rekursiv als der Wert einer Koalition abzüglich der Leistungen, die durch enthaltene Koalitionen bereits erbracht werden:

${\displaystyle \lambda _{\emptyset }^{v}:=0,}$

${\displaystyle \lambda _{S}^{v}:=v(S)-\sum _{T\subsetneq S}\lambda _{T}^{v}.}$

Diese Ausdrücke werden als Harsanyi-Dividenden bezeichnet. Man beachte: Anstelle von ${\displaystyle \lambda _{\{a,b,\ldots ,c\}}^{v}}$ schreibe man einfach ${\displaystyle \lambda _{a,b,\ldots ,c}}$ oder lediglich ${\displaystyle \lambda _{ab\ldots c}}$.

Beispiel

Man betrachte erneut obiges Beispiel und stelle fest, dass ${\displaystyle v(\{a\})=12}$ tatsächlich vom Spieler ${\displaystyle a}$ erbracht wird. Die tatsächliche Leistung vom Spieler ${\displaystyle a}$ allein ist also ${\displaystyle \lambda _{a}=v(\{a\})=12}$. Genauso lassen sich die genuinen Leistungen der anderen Einzelkoalitionen bestimmen,

${\displaystyle \lambda _{b}=6}$

${\displaystyle \lambda _{c}=9}$.

Für die Koalition ${\displaystyle \{a,b\}}$ muss nun die bereits durch die enthaltenen Koalitionen erbrachten Leistungen abgezogen werden:

${\displaystyle \lambda _{a,b}=v(\{a,b\})-\lambda _{a}-\lambda _{b}=24-12-6=6}$.

Analog gelten:

${\displaystyle \lambda _{a,c}=v(\{a,c\})-\lambda _{a}-\lambda _{c}=27-12-9=6}$

${\displaystyle \lambda _{b,c}=v(\{b,c\})-\lambda _{b}-\lambda _{c}=15-9-6=0}$

${\displaystyle \lambda _{a,b,c}=v(\{a,b,c\})-\lambda _{a}-\lambda _{b}-\lambda _{c}-\lambda _{a,b}-\lambda _{a,c}-\lambda _{b,c}=36-12-9-6-6-6-0=-3.}$

Shapley-Wert als geteilte Harsanyi-Dividenden

Die Harsanyi-Dividende einer Koalition wird genau dann erbracht, wenn alle Spieler vorhanden sind. Es ist also plausibel, diese Leistung auf alle Spieler der Koalition zu gleichen Teilen aufzuteilen. Dies ergibt eine weitere Formel für den Shapley-Wert:

${\displaystyle \mathrm {Sh} _{i}(N,v)=\sum _{S\subseteq N:~i\in S}{\frac {\lambda _{S}}{|S|}}.}$

Beispiel

Man betrachte erneut obiges Beispiel mit Spielermenge ${\displaystyle N=\{a,b,c\}}$ und stelle fest, dass Spieler ${\displaystyle b}$ in den Koalitionen

${\displaystyle \{b\},~\{a,b\},~\{b,c\}\qquad {\text{und}}\qquad \{a,b,c\}}$

enthalten ist. Daher bekommt er

${\displaystyle \mathrm {Sh} _{b}(N,v)={\frac {\lambda _{b}}{|\{b\}|}}+{\frac {\lambda _{a,b}}{|\{a,b\}|}}+{\frac {\lambda _{b,c}}{|\{b,c\}|}}+{\frac {\lambda _{a,b,c}}{|\{a,b,c\}|}}={\frac {6}{1}}+{\frac {6}{2}}+{\frac {0}{2}}+{\frac {-3}{3}}=8}$

Charakterisierung

Der Shapley-Wert 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: Spieler mit gleichen marginalen Beiträgen erhalten das gleiche.
• Null-Spieler: Ein Spieler mit marginalem Beitrag null zu jeder Koalition erhält null.
• Additivität: Wenn das Spiel in zwei unabhängige Spiele zerlegt werden kann, dann ist die Auszahlung jedes Spielers im zusammengesetzten Spiel die Summe der Auszahlungen in den aufgeteilten Spielen.

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, ISBN 0-691-07935-8, S. 307–317.
• Harald Wiese: Kooperative Spieltheorie. Oldenbourg, München 2005, ISBN 3-486-57745-X, doi:10.1524/9783486837469.