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 und bezeichnet werden, d. h. , und die folgende Werte erzielen können:

Dabei steht beispielsweise dafür, dass die „Koalition“ bestehend nur aus Spieler allein den Wert erreichen kann; bedeutet, dass eine Koalition aus Spieler zusammen mit den Wert erschaffen kann; wegen können alle Spieler gemeinsam den Wert erzeugen.

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

ReihenfolgeSpieler vor bSpieler vor b plus b marginaler Beitrag von Spieler b

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

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

      und      

Allgemeine Definition

Gegeben s​ei ein kooperatives Spiel m​it transferierbarem Nutzen, d​as heißt gegeben sei

  • eine endliche Spielermenge mit Elementen und
  • eine Koalitionsfunktion , die jeder Teilmenge von eine reelle Zahl zuweist und insbesondere der leeren Koalition den Wert gibt:

wobei die Potenzmenge von bezeichnet, also die Menge aller Teilmengen. Eine Teilmenge der Spieler heißt Koalition. Den Ausdruck nennt man den Wert der Koalition .

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

Reihenfolgendefinition

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

.

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

.

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

wobei die Menge aller möglicher Reihenfolgen der Spieler bezeichnet.

Hinweis: Obiges Beispiel ist gemäß dieser Definition berechnet. Für ist z. B. und

Teilmengendefinition

Der marginale Beitrag eines Spielers zu einer gegebenen Koalition ist

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

Ausgehend von der Reihenfolgendefinition des Shapley-Wertes lässt sich diese Formel nun wie folgt verstehen: Für jedes gibt es

Reihenfolgen, so dass gilt, denn es gibt Möglichkeiten, die Spieler aus vor dem Spieler anzuordnen und Möglichkeiten, die Spieler aus hinter dem Spieler anzuordnen (siehe auch Multinomialkoeffizienten).

Beispiel

Man betrachte erneut obiges Beispiel und nehme den Fall . Es ist dann genau für die beiden Reihenfolgen und . Es gilt also . Anstatt über alle Reihenfolgen zu gehen, könne man also auch folgende Tabelle aufstellen:

KoalitionHäufigkeitmarginaler Beitrag

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

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 und ihren Wert . Welcher Anteil von entsteht wirklich durch die Kombination von allen Mitgliedern aus , und nicht schon durch die Kombination der in enthaltenen Untergruppierungen? Das heißt, welcher Teil von 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, . Die weiteren tatsächlichen Leistungen ergeben sich rekursiv als der Wert einer Koalition abzüglich der Leistungen, die durch enthaltene Koalitionen bereits erbracht werden:

Diese Ausdrücke werden als Harsanyi-Dividenden bezeichnet. Man beachte: Anstelle von schreibe man einfach oder lediglich .

Beispiel

Man betrachte erneut obiges Beispiel und stelle fest, dass tatsächlich vom Spieler erbracht wird. Die tatsächliche Leistung vom Spieler allein ist also . Genauso lassen sich die genuinen Leistungen der anderen Einzelkoalitionen bestimmen,

.

Für die Koalition muss nun die bereits durch die enthaltenen Koalitionen erbrachten Leistungen abgezogen werden:

.

Analog gelten:

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:

Beispiel

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

enthalten ist. Daher bekommt er

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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.