Shapley-Wert

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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

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

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

Der Shapley-Wert dient der Aufteilung des Wertes v({a, b, c} )=36. Folgendes Verfahren ist möglich, um den Shapley-Wert eines Spielers 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 i gelistet sind. Man notiert den Wert, den diese Koalition gemeinsam mit dem Spieler i hat, und bildet die Differenz, also den sogenannten marginalen Beitrag von Spieler i in der betrachteten Reihenfolge. Schließlich nimmt man den Durchschnitt von diesen marginalen Beiträgen und erhält den Shapley-Wert des Spielers i. Die folgende Tabelle gibt diese Überlegungen für Spieler b wieder:

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

Der Durchschnitt der marginalen Beiträge ergibt für Spieler b den Shapley-Wert

Sh_b (\{a,b,c\},v) = (12+9+6+6+9+6)/6=8.

Analog bestimmt man die Shapley-Werte der Spieler a und c erhält

Sh_a(\{a,b,c\},v)=17      und      Sh_c(\{a,b,c\},v) =11.

Allgemeine Definition[Bearbeiten]

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


  • eine endliche Menge von Spieler N und
  • eine Koalitionsfunktion v, die jeder Teilmenge von N eine reelle Zahl zuweist, und insbesondere der leeren Koalition den Wert 0 gibt:
\begin{align}
 v\colon  \mathcal P(N)  &\to \mathbf{R} \\
 v(\varnothing ) &\mapsto 0
\end{align}

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

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

Reihenfolgendefinition[Bearbeiten]

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

P_i^\sigma =\{j\in N \colon \sigma(j) < \sigma(i)\}.

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

v( P_i^\sigma \cup \{i\})-v( P_i^\sigma ).

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

Sh_i(N,v)= \frac{1}{n!}  \cdot \sum_{\sigma \in \mathcal{R}} [v( P_i^\sigma \cup \{i\})-v( P_i^\sigma )]

wobei  \mathcal R die Menge aller möglicher Reihenfolgen der Spieler bezeichnet.
Hinweis: Obiges Beispiel ist gemäß dieser Definition berechnet. Für \sigma=(c,a,b) ist z.B. P_b^\sigma =\{a,c\} und  v( P_b^\sigma \cup \{b\})-v( P_b^\sigma )= 36-27=9.

Teilmengendefinition[Bearbeiten]

Der marginale Beitrag eines Spieler i\in N zu einer gegebenen Koalition S\subseteq N ist

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

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

Sh_i(N,v)=\frac{1}{n!}\cdot\sum_{S\subseteq N \setminus \{i\}}{(n-|S|-1)! \cdot |S|!}(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 S\subseteq N\setminus \{i\} gibt es

(n-|S|-1)! \cdot |S|!

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

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

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

Der Durchschnitt der marginalen Beiträge ergibt für Spiele b den Shapley-Wert

Sh_b (\{a,b,c\},v) = (18+12+6+12)/6=8.

Definition via Harsanyi-Dividenden[Bearbeiten]

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

Harsanyi-Dividenden[Bearbeiten]

Folgendes Argument wird häufig auf John Harsanyi zurückgeführt. Man betrachte eine Koalition S und ihren Wert v(S). Welcher Anteil von v(S) entsteht wirklich durch die Kombination von allen Mitgliedern aus S, und nicht schon durch die Kombination der in S enthaltenen Untergruppierungen? Das heißt, welcher Teil von 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, \lambda_\varnothing^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:

\lambda_S^v = v(\{S\}) -  \sum_{T\subsetneq S }\lambda_T^v .

Diese Ausdrücke werden als Harsanyi-Dividenden bezeichnet.

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

\lambda_b=6      und      \lambda_c=9.

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

\lambda_{ab}=v(\{a,b\})- \lambda_a -\lambda_b=24-12-6=6.

Analog gilt:

\lambda_{ac}=v(\{a,c\})- \lambda_a -\lambda_c=27-12-9=6      und      \lambda_{bc}=v(\{b,c\})- \lambda_b -\lambda_c=15-9-6=0

Es bleibt die tatsächliche Leistung der Kombination von a,b mit c zu bestimmen, also jene Leistung, die nicht schon durch a,b oder c allein oder durch die paarweisen Kombinationen ab,ac oder bc entstanden sind. Dazu berechnet man:

\lambda_{abc}=v(\{a,b,c\})- \lambda_a -\lambda_b -\lambda_c -\lambda_{ab} -\lambda_{ac} -\lambda_{bc} 
=36-12-9-6-6-6-0=-3.

Shapley-Wert als geteilte Harsanyi-Dividenden[Bearbeiten]

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:

Sh_i(N,v)=\sum_{S\subseteq N : i \in S} \frac{\lambda_S}{|S|}.


Beispiel
Man betrachte erneut obiges Beispiel und stelle fest, dass Spieler  b in den Koalitionen

 \{b\},\{a,b\},\{b,c\}       und      \{a,b,c\}

enthalten ist. Daher bekommt er

 Sh_b(\{a,b,c\},v)=   \frac{\lambda_ b}{| \{b\} |} + \frac{\lambda_{ab}}{| \{a,b\} |}  + \frac{\lambda_{bc}}{| \{b,c\} |}  + \frac{\lambda_{abc}}{| \{a,b,c\} |} 
= \frac{6}{1} + \frac{6}{2}  + \frac{0}{2}  + \frac{-3}{3} = 8

Charakterisierung[Bearbeiten]

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[Bearbeiten]

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