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). Dem marginalen Beitrag kommt eine besondere Bedeutung zu. Dieser misst den Wertbeitrag eines Spielers zu einer Koalition, durch seinen Beitritt.
Beispiel Bearbeiten
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:
| Reihenfolge | Spieler vor b | Spieler 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
Allgemeine Definition Bearbeiten
Gegeben sei ein kooperatives Spiel mit transferierbarem Nutzen, das 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 Bearbeiten
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 Bearbeiten
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).
Der Shapley-Wert eines Spielers lässt sich alternativ berechnen mit:
Beispiel Bearbeiten
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:
| Koalition | Häufigkeit | marginaler Beitrag |
|---|---|---|
Der Durchschnitt der marginalen Beiträge (mit ) ergibt für Spieler in der Menge den Shapley-Wert
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 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 Bearbeiten
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 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:
Beispiel Bearbeiten
Man betrachte erneut obiges Beispiel mit Spielermenge und stelle fest, dass Spieler in den Koalitionen
enthalten ist. Daher bekommt er
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, die die gleichen marginalen Beiträgen zu jeder Koalition haben, die sie nicht enthalten, erhalten das Gleiche:
- Null-Spieler-Eigenschaft bzw. Dummy-Spieler-Eigenschaft: Ein Spieler der zu jeder Koalition nichts bzw. den Wert seiner Einer-Koalition beiträgt, erhält null bzw. den Wert seiner Einer-Koalition:
- 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:
Neben diesen Axiomen existiert der Shapley-Wert für alle kooperativen Spiele und ist eindeutig definiert. Außerdem erfüllt der Shapley-Wert:
- Strenge Monotonie: Höhere marginale Beiträge eines Spielers, bzgl. zweier Koalitionsfunktionen, sind mit höheren Ergebnis-Anteilen verbunden:
Literatur Bearbeiten
- Michael Maschler, Eilon Solan, Shmuel Zamir: Game Theory, 2nd Edition. Cambridge University Press, Cambridge 2020, ISBN 978-1-108-49345-1.
- David Müller: Investitionscontrolling: Entscheidungsfindung bei Investitionen II: Entscheidungstheorie. 3. Aufl. Springer Gabler, Berlin u. a. 2022, ISBN 978-3-658-36596-7.
- Hans Peters: Game Theory, A Multi-Leveled Approach, Second Edition. Springer, Berlin u. a. 2015, ISBN 3-662-46949-9.
- 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.
- H. Peyton Young: Monotonic solutions of cooperative games. In: International Journal of Game Theory, Volume 14, Issue 2, 1985, doi:10.1007/BF01769885, S. 65–72.