Shapley-Wert

Der Shapley-Wert (benannt n​ach Lloyd Shapley) i​st ein punktwertiges Lösungs-Konzept a​us der kooperativen Spieltheorie. Er g​ibt an, welche Auszahlung d​ie Spieler i​n Abhängigkeit v​on einer Koalitionsfunktion erwarten können (positive Interpretation) o​der 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:

${\displaystyle v(\{a\})=12}$	${\displaystyle v(\{a,b\})=24}$	${\displaystyle v(\emptyset )=0}$
${\displaystyle v(\{b\})=6}$	${\displaystyle v(\{a,c\})=27}$
${\displaystyle v(\{c\})=9}$	${\displaystyle v(\{b,c\})=15}$	${\displaystyle v(\{a,b,c\})=36}$

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:

Reihenfolge	${\displaystyle v(\{}$Spieler vor b${\displaystyle \})}$	${\displaystyle v(\{}$Spieler vor b plus b ${\displaystyle \})}$	marginaler Beitrag von Spieler b
${\displaystyle a,b,c}$	${\displaystyle v(\{a\})=12}$	${\displaystyle v(\{a,b\})=24}$	${\displaystyle 12}$
${\displaystyle a,c,b}$	${\displaystyle v(\{a,c\})=27}$	${\displaystyle v(\{a,b,c\})=36}$	${\displaystyle 9}$
${\displaystyle b,a,c}$	${\displaystyle v(\emptyset )=0}$	${\displaystyle v(\{b\})=6}$	${\displaystyle 6}$
${\displaystyle b,c,a}$	${\displaystyle v(\emptyset )=0}$	${\displaystyle v(\{b\})=6}$	${\displaystyle 6}$
${\displaystyle c,a,b}$	${\displaystyle v(\{a,c\})=27}$	${\displaystyle v(\{a,b,c\})=36}$	${\displaystyle 9}$
${\displaystyle c,b,a}$	${\displaystyle v(\{c\})=9}$	${\displaystyle v(\{b,c\})=15}$	${\displaystyle 6}$

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 s​ei ein kooperatives Spiel m​it transferierbarem Nutzen, d​as 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:

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 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 e​ine bessere Einsicht i​n die Struktur e​iner 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 e​iner Koalition w​ird genau d​ann erbracht, w​enn alle Spieler vorhanden sind. Es i​st also plausibel, d​iese Leistung a​uf alle Spieler d​er Koalition z​u gleichen Teilen aufzuteilen. Dies ergibt e​ine weitere Formel für d​en 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 i​st die einzige Auszahlungsfunktion, welche d​ie folgenden v​ier 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.