Der Shapley-Wert verständlich erklärt

Drei kleine Lieferdienste können eine Runde gemeinsam fahren und sparen dabei Strecke. Wer zahlt wie viel? Eine Antwort fragt, in welcher Reihenfolge die drei der Runde beitreten. Die Seite zeigt, was daran gerecht ist und wo es nicht reicht.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Drei Lieferdienste, eine Runde

Anna, Ben und Chris betreiben je einen kleinen Lieferdienst. Jeder beliefert einen Kunden, alle starten am selben Lager. Bisher fährt jeder allein.

Nun fährt ein Wagen eine Runde vom Lager zu allen drei Kunden und zurück. Auf dem Weg teilen sich die drei einen Teil der Strecke, deshalb ist die Runde kürzer als drei Einzelfahrten. Offen bleibt, wer wie viel von ihr bezahlt.

Nehmen wir ein Zahlenbeispiel. Die Längen in Kilometern sind ausgedacht und passen zu keiner echten Karte:

Wer fährt	Länge der Fahrt in Kilometern
Anna allein	4
Ben allein	6
Chris allein	8
Anna und Ben	9
Anna und Chris	10
Ben und Chris	11
alle drei	12

Allein führen die drei zusammen 4 plus 6 plus 8 Kilometer. Gemeinsam sind es nur 12. Sie sparen sechs Kilometer.

Die erste Idee: alle zahlen gleich viel

Der erste Gedanke ist, die 12 Kilometer durch drei zu teilen. Jeder zahlt dann 4. Anna zahlt damit so viel wie bei der Alleinfahrt. Sie spart nichts und hätte keinen Grund mitzufahren. Chris spart dagegen 4 Kilometer, weil seine Alleinfahrt am längsten wäre.

Gleiche Beträge übersehen also, dass die Kunden verschieden weit weg liegen. Besser wäre eine Regel, die berücksichtigt, was jeder zur Runde beiträgt.

Die zweite Idee: der Reihe nach beitreten

Stellen Sie sich vor, die drei schließen sich nacheinander der Runde an. Jeder zahlt, was sein Beitritt die Fahrt verlängert. Das sind seine Mehrkosten.

Kommen sie in der Reihenfolge Anna, Ben, Chris, zahlt Anna 4, denn sie fährt zuerst allein. Mit Ben wächst die Fahrt von 4 auf 9, er zahlt 5. Mit Chris wächst sie auf 12, er zahlt 3. Zusammen sind das 12.

Kommt Chris zuerst, dann Ben, dann Anna, zahlt Chris 8, Ben 3 und Anna nur noch einen Kilometer. Je nach Reihenfolge zahlt Anna also viel oder wenig. Der Grund: Wer zuerst kommt, zahlt die ganze Fahrt allein. Wer später kommt, fährt auf einem schon bezahlten Stück mit. Dass jemand früh oder spät kommt, ist aber Zufall.

Der Ausweg ist, alle sechs möglichen Reihenfolgen durchzuspielen und für jeden den Durchschnitt zu bilden. Dieser Durchschnitt heißt Shapley-Wert. Im Beispiel zahlt Anna zweieinhalb Kilometer, Ben vier und Chris fünfeinhalb, zusammen 12. Jeder zahlt weniger als bei der Alleinfahrt.

Was an diesem Durchschnitt gerecht ist

Der Mathematiker Shapley hat vier Forderungen aufgestellt, die man leicht für gerecht hält. Er hat gezeigt: Nur dieser Durchschnitt erfüllt alle vier, wenn man beliebige Kostenfälle zulässt.

• Alles wird verteilt. Die Anteile ergeben genau die Kosten der Runde.
• Gleiches wird gleich behandelt. Zwei Betriebe mit demselben Kundenort zahlen gleich viel.
• Wer nichts beiträgt, zahlt nichts. Ein Kunde direkt am Lager verlängert keine Fahrt.
• Kostenarten dürfen sich addieren. Setzen sich die Kosten aus Sprit und Fahrerlohn zusammen, ergibt dasselbe: beides getrennt teilen und die Anteile addieren, oder die Summe teilen.

Fachleute nennen das Effizienz, Symmetrie, Nullspieler und Additivität.

Das Programm zum Ausprobieren

Zu dieser Seite gehört ein Programm zum Ausprobieren, die Demo. Am Ende dieses Teils stehen zwei Knöpfe. Der erste, „Demo ausprobieren“, öffnet sie. Der zweite, „Weiter zum Fachteil“, führt zum zweiten Teil dieser Seite. Zum Verstehen brauchen Sie die Demo nicht.

Die Demo würfelt Fälle: Sie legt bis zu zwölf Betriebe mit je einem Kunden zufällig in ein Gebiet und rechnet die kürzeste gemeinsame Runde aus. Deren Kosten teilt sie auf drei Arten auf, mit dem Shapley-Wert und mit zwei einfacheren Regeln. Das ist ein vereinfachtes Rechenbild (Fachwort: Modell). Die Aussagen unten beschreiben dieses Rechenbild, nicht echte Speditionen.

Eine zweite Art von Gerechtigkeit: stabil

Eine praktische Frage bleibt: Würde eine Teilgruppe der Betriebe lieber allein fahren? Eine Aufteilung heißt stabil (Fachwort: im Kern), wenn keine Teilgruppe zusammen mehr zahlt, als ihre eigene Runde kosten würde. Sonst hätte diese Teilgruppe einen Grund auszusteigen.

Im Beispiel ist die Aufteilung stabil. Anna und Ben zahlen zusammen sechseinhalb Kilometer, ihre eigene Runde wäre 9 lang. Bei Anna und Chris und bei Ben und Chris zahlen die Paare ebenfalls weniger als ihre eigene Runde.

Der Durchschnitt über die Reihenfolgen garantiert das nicht. Die Demo prüft es in Fällen mit acht Betrieben und gleichmäßig verteilten Kunden. In 85 % dieser Fälle war der Shapley-Wert stabil. In den übrigen zahlte eine Teilgruppe etwas zu viel. Dieses Zuviel, die Überschreitung, lag über alle Fälle gemittelt unter einem Prozent der Gesamtstrecke. Was dann zu tun ist, etwa nachverhandeln oder eine andere Regel wählen, rechnet die Demo nicht.

Zum Vergleich rechnet die Demo zwei einfachere Regeln. Bei der einen zahlt jeder im Verhältnis zu seiner Alleinfahrt. Bei der anderen spart jeder gleich viel. Die erste war nur in 10 % der Fälle stabil, die zweite in keinem.

Bei der Regel „jeder spart gleich viel“ gibt es noch einen Haken. Jeder erhält denselben Sparbetrag, nämlich die gesparte Strecke geteilt durch die Zahl der Betriebe. Ist die Alleinfahrt eines Betriebs kürzer als dieser Betrag, müsste er einen negativen Betrag zahlen, also Geld bekommen. In dem Fall mit acht Betrieben, den die Demo beim Öffnen zeigt, trifft das einen Betrieb. Das ist eine Nachrechnung dieser Seite.

Mit jedem Betrieb mehr wächst die Zahl der Teilgruppen, die aussteigen könnten, rasch. Bei gleichmäßig verteilten Kunden war der Shapley-Wert bei vier Betrieben in allen durchgespielten Fällen stabil, bei zehn nicht mehr in allen.

Alle Reihenfolgen durchzuspielen wird bei vielen Betrieben unmöglich: Bei zehn Betrieben sind es über drei Millionen. Die Demo mittelt dann zufällig gezogene Reihenfolgen. Je mehr sie zieht, desto kleiner wird der Fehler, weil Zufallsausreißer sich herausmitteln.

Häufige Missverständnisse

• „Gerecht heißt: alle zahlen gleich viel.“ Nein. Im Beispiel zahlt Chris mehr als Anna. Gleich behandelt werden Gleiche: Zwei Betriebe mit demselben Kundenort zahlen gleich viel. Wer verschieden viel zur Runde beiträgt, zahlt verschieden viel.
• „Was gerecht verteilt ist, ist auch stabil.“ Nein. In einem Fall der Demo mit acht Betrieben zahlen sieben von ihnen zusammen mehr, als ihre eigene Runde kosten würde.

Woran Sie das im Alltag erkennen

• Eine Rechnung wird nach der Reihenfolge verteilt, in der man dazugekommen ist, und die Letzten zahlen weniger als die Ersten.
• Jemand in der Gruppe sagt: Allein oder zu zweit wäre ich billiger dran.
• Jemand sagt: Ich fahre nur ein kurzes Stück mit, warum zahle ich gleich viel wie die anderen?

Wie ernst ist das Modell zu nehmen?

Das Rechenbild kennt nur einen Kunden je Betrieb und keine Grenzen für die Ladung. Zeitfenster und ehrliche Angaben fehlen. Die Zahlen gelten für zufällig erzeugte Fälle, nicht für Ihre Lieferdienste.

Was Sie mitnehmen:

• Fragen Sie bei jeder geteilten Rechnung: Wer wäre allein oder zu zweit günstiger dran?
• Klären Sie vor dem Teilen, welche Gerechtigkeit Sie meinen: gleiche Behandlung oder dass niemand aussteigen will.
• Prüfen Sie bei jeder Zahl, für welche Annahmen sie gilt, etwa ein Kunde je Betrieb.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er beschreibt ein kooperatives Kostenspiel, bei dem Spediteure eine gemeinsame Tour fahren, und drei Arten, die Gesamtkosten aufzuteilen.

• Spieler und Gebiet: \(N = \{1,\dots,n\}\) sind die Spediteure mit je genau einem Stopp. Das Depot liegt in der Mitte eines Gebiets von 100 × 100 km, die Entfernungen sind euklidisch, Kapazitäten gibt es nicht. Die Stopps liegen gleichmäßig verteilt oder um zwei Ballungszentren. Die Zahl \(n\) reicht von 3 bis 12, voreingestellt sind 8.
• Koalitionswert: Für eine Gruppe (Koalition) \(S \subseteq N\) ist \(c(S)\) die Länge der kürzesten Rundtour ab Depot durch alle Stopps in \(S\), und \(c(\emptyset) = 0\) (Traveling-Salesman-Spiel). \(c(\{i\})\) ist die Alleinfahrt Depot, Stopp, Depot. Wegen der Dreiecksungleichung gilt \(c(S \cup T) \le c(S) + c(T)\), die Kooperation ist also nie teurer als getrennte Fahrten. Ob sie tatsächlich Strecke spart und wie viel, ist ein Befund der Instanz (siehe Befunde).
• Berechnung: Alle \(2^n\) Werte \(c(S)\) liefert eine einzige Held-Karp-Rechnung in \(O(2^n n^2)\).
• Aufteilungen: Eine Aufteilung ist ein Vektor \(x = (x_1,\dots,x_n)\) mit \(\sum_i x_i = c(N)\). Verglichen werden der Shapley-Wert, die zu den Alleinkosten proportionale Aufteilung und die Aufteilung mit gleicher Ersparnis für alle.
• Stabilität: Eine Aufteilung heißt stabil, wenn sie im Kern liegt, wenn also keine Gruppe allein günstiger führe, als sie zusammen zahlt. Dafür werden alle \(2^n - 1\) nichtleeren Gruppen geprüft. Eine Gruppe \(S\) mit \(\sum_{i \in S} x_i > c(S)\) heißt blockierend.
• Messreihen: Jede Reihe läuft über feste Zufallsinstanzen mit festen Zufallszahlen, getrennt nach der Lage der Stopps; nur die Stichprobenreihe nutzt ausschließlich gleichmäßig verteilte Stopps. Ein Teil der Rechnungen (Held-Karp, Shapley-Formel, Kern-Prüfung) ist exakt und wird gegen Aufzählungen aller Koalitionen und aller Reihenfolgen geprüft; nur die Stichprobe ist zufällig.

Die Formeln

Der Koalitionswert folgt der Held-Karp-Rekursion. Sei \(d(S, j)\) der kürzeste Weg vom Depot durch genau die Stopps in \(S\) mit Ende bei \(j \in S\):

\[d(S, j) = \min_{k \in S \setminus \{j\}} d(S \setminus \{j\}, k) + \text{dist}(k, j)\]

Anfang der Rekursion ist \(d(\{j\}, j) = \text{dist}(\text{Depot}, j)\); für \(|S| \ge 2\) ist das Minimum über eine nichtleere Menge.

Die Rundtour schließt am Depot:

\[c(S) = \min_{j \in S} d(S, j) + \text{dist}(j, \text{Depot})\]

Der Shapley-Anteil von Spediteur \(i\) ist die gewichtete Summe seiner Grenzkosten \(c(S \cup \{i\}) - c(S)\) über alle Gruppen \(S\) ohne \(i\). Er ist zugleich der Durchschnitt der Grenzkosten über alle \(n!\) Beitrittsreihenfolgen:

\[\phi_i = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!\,(n - |S| - 1)!}{n!}\,\big[c(S \cup \{i\}) - c(S)\big]\]

Der Shapley-Wert hat vier Eigenschaften: Effizienz (\(\sum_i \phi_i = c(N)\)); Symmetrie (Spieler, die zu jeder Gruppe gleich viel beitragen, zahlen gleich viel); Nullspieler (wer zu jeder Gruppe nichts beiträgt, zahlt nichts); Additivität (für zwei Kostenspiele \(c\) und \(c'\) ist der Wert von \(c + c'\) die Summe der beiden Werte). Nach Shapley (1953) ist er auf der Klasse aller Kostenspiele der einzige Wert mit diesen vier Eigenschaften.

Der Kern ist die Menge der effizienten Aufteilungen, die keiner Gruppe mehr abverlangen, als ihre eigene Tour kostet:

\[\{x : \sum_i x_i = c(N),\ \sum_{i \in S} x_i \le c(S)\ \forall S \subseteq N\}\]

Die beiden Vergleichsregeln: proportional zu den Alleinkosten, und gleiche Ersparnis für alle.

\[x_i = c(N)\,c(\{i\}) / \sum_j c(\{j\})\]

\[x_i = c(\{i\}) - \big(\sum_j c(\{j\}) - c(N)\big)/n\]

Die Stichprobe mittelt die Grenzkosten über \(K\) zufällige Reihenfolgen. \(P_i^k\) sind die Vorgänger von \(i\) in der \(k\)-ten Reihenfolge:

\[\hat\phi_i = \frac1K \sum_{k=1}^K \big[c(P_i^k \cup \{i\}) - c(P_i^k)\big]\]

Herleitung Schritt für Schritt

Alles in diesem Abschnitt ist eine Rechnung dieser Seite mit elementaren Argumenten, keine Messung der Demo. Ausgenommen ist die Prüfung in Schritt 3, die mit dem Code der Demo gerechnet wurde.

• Schritt 1, Summe gleich Durchschnitt über Reihenfolgen. Für festes \(i\) und eine Gruppe \(S\) ohne \(i\) gibt es genau \(|S|!\,(n - |S| - 1)!\) Reihenfolgen, in denen genau die Mitglieder von \(S\) vor \(i\) stehen (erst \(S\) in beliebiger Reihenfolge, dann \(i\), dann der Rest). Teilt man durch \(n!\), erhält man das Gewicht der Formel. Die gewichtete Summe ist also der Durchschnitt der Grenzkosten von \(i\) über alle Reihenfolgen.
• Schritt 2, Effizienz. In jeder festen Reihenfolge teleskopiert die Summe der Grenzkosten aller Spediteure zu \(c(N) - c(\emptyset) = c(N)\). Der Durchschnitt dieser Summen ist \(c(N)\), also gilt \(\sum_i \phi_i = c(N)\).
• Schritt 3, niemand zahlt mehr als allein. Aus der Dreiecksungleichung folgt \(c(S \cup \{i\}) \le c(S) + c(\{i\})\): Die Tour für \(S\) und die Alleinfahrt von \(i\) zusammen ergeben eine Rundreise durch alle Stopps von \(S \cup \{i\}\), und Abkürzen verkürzt sie. Jede Grenzkostenzahl von \(i\) ist daher höchstens \(c(\{i\})\), und damit auch \(\phi_i \le c(\{i\})\). Die Kernungleichungen für Einzelspediteure sind für den Shapley-Wert also automatisch erfüllt; eine Verletzung kann nur von Gruppen mit mindestens zwei Mitgliedern kommen. Die Prüfung dieser Seite an den Instanzen der Stabilitätsreihe fand keinen Anteil über den Alleinkosten.
• Schritt 4, Handrechnung mit drei Spielern. Angenommen sei ein abstraktes Kostenspiel mit den Werten \(c(\{1\}) = 4\), \(c(\{2\}) = 6\), \(c(\{3\}) = 8\), \(c(\{1, 2\}) = 9\), \(c(\{1, 3\}) = 10\), \(c(\{2, 3\}) = 11\) und \(c(\{1, 2, 3\}) = 12\). Es stammt nicht aus einer Tourenkarte: Als Tourenspiel mit einem Depot und einem Stopp je Spieler wären diese sieben Werte nicht gleichzeitig möglich (Rechnung dieser Seite: Die Alleinwerte und die Paarwerte legen die Abstände fest und erzwingen eine längere kürzeste Dreierrunde). Die Shapley-Rechnung hängt nur an den sieben Werten. Die Grenzkosten je Beitrittsreihenfolge stehen in der folgenden Tabelle. Beispiel Reihenfolge 2, 3, 1: Spieler 2 zahlt 6, Spieler 3 zahlt \(11 - 6 = 5\), Spieler 1 zahlt \(12 - 11 = 1\).

Reihenfolge	Anteil Spieler 1	Anteil Spieler 2	Anteil Spieler 3
1, 2, 3	4	5	3
1, 3, 2	4	2	6
2, 1, 3	3	6	3
2, 3, 1	1	6	5
3, 1, 2	2	2	8
3, 2, 1	1	3	8
Durchschnitt (Shapley-Wert)	2,5	4,0	5,5

Die Summe der drei Anteile ist 12 und stimmt mit \(c(\{1, 2, 3\})\) überein. Alle sechs Kernungleichungen für Gruppen unterhalb des Ganzen sind erfüllt (Nachrechnung dieser Seite), diese Aufteilung ist also stabil.

• Schritt 5, Stichprobe. Eine gleichverteilt gezogene Reihenfolge liefert für \(i\) Grenzkosten mit dem Erwartungswert \(\phi_i\) (Schritt 1). Das Mittel über \(K\) unabhängige Ziehungen ist daher unverzerrt. Die Grenzkosten sind beschränkt, die Varianz ist also endlich, und der Standardfehler fällt wie \(1/\sqrt{K}\). Von \(K = 10\) auf \(K = 1000\) (hundertfacher Aufwand) sollte der Fehler also um den Faktor zehn sinken. Weil alle Anteile aus denselben Reihenfolgen stammen, teleskopiert die Summe der Schätzungen in jedem Lauf zu \(c(N)\).
• Schritt 6, wo die Stabilität herkommt. Der Shapley-Wert mittelt über Reihenfolgen und nutzt keine einzige Kernungleichung für Gruppen. Dass er oft im Kern liegt, ist ein Befund der Messreihen, kein Satz. Für Traveling-Salesman-Spiele kann der Kern sogar leer sein, auch bei Dreiecksungleichung (Potters, Curiel, Tijs 1992). Dann gibt es keine stabile Aufteilung, und jede Regel verletzt mindestens eine Gruppe. Nach Tamir (siehe Quellen) ist der Kern metrischer Tourenspiele mit höchstens vier Spielern nicht leer (nur berichtet, nicht im Original geprüft); das ist mit den gemessenen Anteilen bei vier Spediteuren verträglich, sagt aber nichts über größere Instanzen.

Befunde

Alle Zahlen stammen aus festen Messreihen. Die Stabilitätsreihe nutzt 8 Spediteure mit je 60 Instanzen je Lage der Stopps. Die Skalierungsreihe nutzt feste Instanzen für 4 bis 10 Spediteure und gleichmäßig verteilte Stopps, soweit nichts anderes steht. Die Stichprobenreihe nutzt 10 Spediteure. „Im Kern“ bedeutet: effizient und keine Gruppe zahlt mehr, als ihre eigene Tour kostet. Der relative Fehler der Stichprobe ist die Summe der Beträge der Abweichungen aller Anteile vom exakten Wert, geteilt durch die Summe der exakten Anteile. „Kippt“ heißt: Die Schätzung liegt auf der anderen Seite des Kerns als der exakte Wert.

Frage	Befund
Wie viel spart die gemeinsame Tour?	Standardinstanz (8 Spediteure, gleichmäßig verteilt, feste Zufallszahlen): allein zusammen 797,9 km, gemeinsam 328,7 km, das sind 58,8 % Ersparnis. Im Mittel über die Instanzen der Stabilitätsreihe 55 % (gleichmäßig verteilt) bzw. 68 % (zwei Ballungszentren).
Ist der Shapley-Wert stabil?	Bei 8 Spediteuren im Kern in 85 % (gleichmäßig) bzw. 92 % (zwei Ballungszentren) der Instanzen. Bei gleichmäßig verteilten Stopps beträgt die Überschreitung, wo er nicht im Kern liegt, über alle Instanzen gemittelt 0,1 % der Gesamtstrecke, im Einzelfall höchstens 2,2 %; blockierende Koalitionen gibt es im Mittel 0,2 je Instanz.
Sind die einfacheren Aufteilungen stabil?	Die proportionale im Kern in 10 % (gleichmäßig) bzw. 27 % (Ballung) der Instanzen, die gleiche Ersparnis in keiner. Blockierende Koalitionen bei gleichmäßig verteilten Stopps im Mittel 5,5 (proportional) bzw. 14,4 (gleiche Ersparnis) je Instanz.
Ein Fall, in dem der Shapley-Wert nicht im Kern liegt	Eine feste Instanz mit 8 Spediteuren: die Spediteure 1 bis 7 zahlen zusammen 2,95 km mehr, als ihre eigene Tour kostet. Die Tour aller acht ist 310,4 km lang.
Bleibt die Stabilität bei mehr Spediteuren?	Bei 4 Spediteuren ist der Shapley-Wert in 100 % der Instanzen stabil, bei 10 in 80 %; die proportionale Aufteilung fällt von 42 % auf 5 %. Die Ersparnis wächst von 34 % auf 61 %.
Handrechnung an einer festen Instanz	Eine einzelne Zufallsinstanz mit nur 3 Spediteuren, nicht mit den Mittelwerten der anderen Zeilen vergleichbar: Shapley-Anteile 17,9 / 123,7 / 113,7 km von zusammen 255,4 km, das sind 10,9 % Ersparnis.
Geht es ohne alle Reihenfolgen?	10 Spediteure haben 1 024 Koalitionen und 3 628 800 Reihenfolgen. Mit 10, 100 und 1000 zufälligen Reihenfolgen liegt der relative Fehler im Mittel bei 19 %, 6,1 % und 2,0 %. Die Stabilitätsaussage kippt in 14 %, 1,0 % bzw. keinem der Läufe.

Was die Messung zeigt und Grenzen

• Belegt: die Rechnungen. Held-Karp stimmt für jede Koalition bei 6 Stopps mit der Aufzählung aller Rundreisen überein. Die Shapley-Formel stimmt mit der Definition über Reihenfolgen überein, die vier Eigenschaften sind einzeln geprüft, und die Kern-Prüfung stimmt mit einer Schleife über alle Gruppen überein. Die Messzahlen sind also Zahlen des Modells, keine Rechenfehler.
• Belegt: Größenordnungen der Anteile. Ein Anteil aus 60 Instanzen hat einen Standardfehler von höchstens gut sechs Prozentpunkten, nahe 85 % etwa fünf (Rechnung dieser Seite). Kleine Unterschiede zwischen Zeilen sind kein Befund.
• Belegt nicht: ein gleichmäßiger Abfall mit der Spediteurszahl. Die Skalierungsreihe nutzt andere und weniger Instanzen je Zelle (vierzig, aus dem Quelltext der Demo gelesen) als die Stabilitätsreihe, ihre Standardfehler sind größer. In einem Nachlauf mit dem Code der Demo (Rechnung dieser Seite) lag der Anteil des Shapley-Werts bei 8 Spediteuren in der Skalierungsreihe höher als in der Stabilitätsreihe. Bei zwei Ballungszentren sank er nicht von Stufe zu Stufe, bei 10 Spediteuren lag er höher als bei 8. Auch bei gleichmäßig verteilten Stopps ist der Verlauf nicht streng monoton und fällt am stärksten am oberen Ende der Reihe. Der Satz „je mehr Spediteure, desto häufiger instabil“ ist eine Deutung, die nur für gleichmäßig verteilte Stopps im Vergleich von 4 und 10 Spediteuren gemessen ist.
• Belegt nicht: die Vergleichsregel gleiche Ersparnis. Sie kann negative Anteile liefern, weil jeder denselben Sparbetrag erhält, auch wenn dieser größer ist als seine Alleinfahrt. In der Standardinstanz ist der Anteil des Spediteurs 1 negativ, des mit der kürzesten Alleinfahrt (Rechnung dieser Seite). Als Maßstab für einfache Regeln ist sie deshalb nur begrenzt aussagekräftig.
• Stichprobe: Gemessen ist sie nur für gleichmäßig verteilte Stopps und für 10 Spediteure, mit zehn festen Instanzen und je zehn Wiederholungen je Stichprobengröße (Anzahlen wie oben aus dem Quelltext). Die Zahlen sind Mittel über diese Läufe. Der Fehler sinkt von der kleinsten zur größten Stichprobengröße um etwa den Faktor zehn, im Rahmen der Erwartung von \(1/\sqrt{K}\) für einen hundertfachen Aufwand.
• Die Stichprobe ist hier keine Ersparnis: Die Demo hat die vollständige Tabelle aller \(c(S)\) aus der Held-Karp-Rechnung ohnehin. Die exakte Formel braucht damit \(n\,2^{n-1}\) Terme (Rechnung dieser Seite), eine Stichprobe \(K\,n\) Nachschläge; für \(K\) in der Größe von \(2^{n-1}\) und mehr ist die exakte Formel nicht teurer. Die Messreihe zeigt nur, wie genau eine Schätzung in Abhängigkeit von \(K\) wäre. Sie lohnt, wenn die Tabelle nicht aufgebaut werden kann, weil jeder Koalitionswert einzeln teuer ist oder \(n\) zu groß wird.
• Eindeutigkeit: Dass nur der Shapley-Wert die vier Eigenschaften erfüllt, ist Shapleys Satz für die Klasse aller Kostenspiele. Ob die Eindeutigkeit auf der Teilklasse der Tourenspiele allein gilt, ist hier nicht geprüft; die Summe zweier Tourenspiele ist im Allgemeinen kein Tourenspiel.
• Modellgrenzen: Ein Stopp je Spediteur und keine Kapazität. Mit Kapazitäten und mehreren Stopps wird der Koalitionswert ein Tourenplanungsproblem, und die Kostenersparnis durch Kooperation ist dann nicht mehr gesichert. Zeitfenster, Beladung und Fahrerzeiten fehlen. Held-Karp braucht Zeit \(O(2^n n^2)\) und Speicher der Größe \(2^n n\); laut Dokumentation der Demo reicht es nur bis etwa 15 Stopps (nicht gemessen), die Demo rechnet bis 12.
• Nicht behandelt: Der Kern selbst (seine Leere) und der Nukleolus (die Aufteilung, die den größten Überschuss einer Gruppe lexikografisch minimiert) werden nicht berechnet, die Demo prüft nur die drei Aufteilungen. Verhandlung und Vertrauen liegen außerhalb des Modells, und ob Spediteure ihre Kosten ehrlich melden, ist eine Frage des Mechanismendesigns (Anreize für wahre Angaben).

Quellen

• Shapley, L. S.: A value for n-person games, 1953.
• Potters, J. A. M., Curiel, I. J., Tijs, S. H.: Traveling salesman games, 1992 (der Kern kann leer sein, auch bei Dreiecksungleichung).
• Castro, J., Gómez, D., Tejada, J.: Polynomial calculation of the Shapley value based on sampling, Computers & Operations Research, 2009.
• Tamir, A.: Arbeit zum Kern von Tourenspielen, 1989 (nur berichtet, Titel und Inhalt nicht geprüft).
• Held, M., Karp, R. M.: A dynamic programming approach to sequencing problems, 1962 (aus dem Gedächtnis, nicht geprüft).
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/shapley-demo.

Shapley 1953 und Potters, Curiel, Tijs 1992 sind laut Dokumentation der Demo per Recherche geprüft, aber nicht nachgebaut. Titel und Jahr von Potters, Curiel, Tijs und von Castro, Gómez, Tejada wurden für diese Seite per Websuche bestätigt. Keine der Arbeiten wurde im Original gelesen. Nicht aus der Dokumentation stammen die Herleitungen und die Nachläufe, sie sind Rechnungen dieser Seite.