Shapley-Wert

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.}$

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

Der Shapley-Wert eines Spielers ${\displaystyle i}$ lässt sich alternativ berechnen mit:

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

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:

Koalition	Häufigkeit	marginaler Beitrag
${\displaystyle S\subseteq N\setminus \{i\}}$	${\displaystyle (n-1-|S|)!\cdot |S|!}$	${\displaystyle v(S\cup \{i\})-v(S)}$
${\displaystyle \emptyset }$	${\displaystyle 2}$	${\displaystyle 6}$
${\displaystyle \{a\}}$	${\displaystyle 1}$	${\displaystyle 12}$
${\displaystyle \{c\}}$	${\displaystyle 1}$	${\displaystyle 6}$
${\displaystyle \{a,c\}}$	${\displaystyle 2}$	${\displaystyle 9}$

Der Durchschnitt der marginalen Beiträge (mit ${\displaystyle n!=3!=6}$) ergibt für Spieler ${\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.}$

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

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}}$.

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.}$

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|}}.}$

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}$