Balanced Contributions in Networks and Games with Externalities

Die Arbeit charakterisiert die eindeutige, komponenteneffiziente Zuweisungsregel (BCE-Regel) für Netzwerke mit Externalitäten, die das Prinzip der ausgeglichenen Beiträge erfüllt, und zeigt auf, wie diese Regel durch eine Zyklus-Summen-Identität konstruiert wird, um die Herausforderung zu meistern, dass die Bedingung für alle Kanten gelten muss, obwohl die Konstruktion nur Spannbäume nutzt.

Das Wesentliche

Das Grundproblem: Wer bekommt was im Team?

Stellen Sie sich vor, Sie spielen ein Spiel mit Freunden. Manchmal arbeiten Sie nur in kleinen Gruppen zusammen, manchmal hängt der Erfolg einer Gruppe davon ab, was die anderen Gruppen tun.

In der Wirtschaftswissenschaft gibt es zwei klassische Regeln, um zu entscheiden, wie man den Gewinn fair aufteilt:

1. Die "Freundschafts-Regel" (Fairness): Wenn zwei Freunde eine Verbindung haben, sollten sie den gleichen Vorteil daraus ziehen, wenn sie sich trennen. Es geht nur um die eine Verbindung zwischen ihnen.
2. Die "Abwanderungs-Regel" (Ausgewogene Beiträge): Wenn ein Spieler das Spiel komplett verlässt (alle seine Verbindungen kappen), wie verändert sich das für die anderen? Die Regel besagt: Der Verlust, den Spieler A durch das Weggehen von Spieler B erleidet, muss genau dem Verlust entsprechen, den B erleidet, wenn A geht. Es geht um den kompletten Rückzug, nicht nur um eine einzelne Freundschaft.

Das neue Szenario: Wenn alles alles beeinflusst

Das Besondere an diesem Papier ist, dass es sich mit Netzwerken mit "Externalitäten" beschäftigt. Das ist ein kompliziertes Wort für: Das, was Gruppe A verdient, hängt davon ab, wie Gruppe B aussieht.

Ein einfaches Beispiel:
Stellen Sie sich drei Spieler vor: Anna (1), Ben (2) und Clara (3).

• Anna und Ben können zusammenarbeiten und 100 € verdienen.
• Clara ist eigentlich nur Zuschauerin.
• Aber: Clara bekommt 100 € nur dann, wenn Anna und Ben verbunden sind.

Szenario A: Anna und Ben sind verbunden, Clara ist isoliert.

• Anna und Ben teilen sich die 100 €. Clara bekommt nichts.
• Warte! Die Regel sagt: Wenn Anna und Ben verbunden sind, verdient Clara 100 €. Da sie aber isoliert ist, kann sie den Gewinn nicht "mitnehmen". Also bleibt sie bei 0.

Szenario B: Anna und Ben sind verbunden, und Anna ist auch mit Clara verbunden.

• Jetzt ist alles in einer großen Gruppe.
• Die alte "Freundschafts-Regel" würde sagen: Wenn Anna und Clara ihre Verbindung trennen, passiert für Anna und Ben nichts (sie bleiben verbunden). Also bekommt Clara nichts.
• Die neue "Abwanderungs-Regel" (die in diesem Papier erforscht wird) sagt: Wenn Anna das Spiel verlässt, zerfällt die Verbindung zwischen Anna und Ben. Dann verdient Clara nichts mehr! Anna ist also für Claras Gewinn verantwortlich. Clara muss also einen Teil des Gewinns an Anna abgeben, weil Anna ihr "Schutzschild" ist.

Die Entdeckung: Die "BCE-Regel"

Der Autor Frank Huettner hat herausgefunden, dass man in solchen komplexen Situationen (wo alles alles beeinflusst) die beiden klassischen Regeln nicht gleichzeitig anwenden kann. Sie widersprechen sich.

Er hat daher eine neue, einzige Regel entwickelt, die er BCE-Regel (Balanced Contributions with Externalities) nennt.

Wie funktioniert sie? (Die Metapher des Baumes)

Stellen Sie sich das Netzwerk als einen Wald vor. Um den Gewinn gerecht aufzuteilen, baut die BCE-Regel einen "Baum" (eine Art Rückgrat) innerhalb jeder Gruppe.

1. Der Baum: Sie wählen einen Startpunkt und bauen einen Pfad zu allen anderen Mitgliedern der Gruppe.
2. Die Kaskade: Die Regel schaut sich an, was passiert, wenn jemand diesen Baum verlässt. Sie berechnet, wie sehr der "Vater" (derjenige, der den Pfad führt) den "Sohn" braucht und umgekehrt.
3. Der Ausgleich: Am Ende wird der gesamte Gewinn der Gruppe so aufgeteilt, dass jeder genau so viel bekommt, wie er durch seine spezifische Position im Baum zum Gesamterfolg beiträgt – unter Berücksichtigung aller versteckten Abhängigkeiten.

Der Clou:
Obwohl die Regel nur den "Baum" betrachtet, funktioniert sie mathematisch perfekt für alle Verbindungen im Netzwerk, auch für die, die nicht im Baum sind. Der Autor hat ein mathematisches Werkzeug (die "Zyklus-Summen-Identität") entwickelt, das wie ein Zauberstab wirkt: Es beweist, dass die Berechnung auf dem Baum automatisch auch für alle anderen Kreise im Netzwerk stimmt.

Warum ist das wichtig?

• Fairness vs. Realität: Die alte "Freundschafts-Regel" ignoriert oft, dass ein Spieler indirekt von einem anderen abhängt. Die neue BCE-Regel fängt diese versteckten Abhängigkeiten ein.
• Keine einfache Formel: Im Gegensatz zu anderen bekannten Methoden (wie dem Shapley-Wert) gibt es für die BCE-Regel keine einfache Formel, die man einfach in einen Taschenrechner eingeben kann. Man muss sie schrittweise berechnen (rekursiv), wie ein Koch, der ein komplexes Gericht Schicht für Schicht zubereitet.
• Vollständigkeit: Wenn alle miteinander verbunden sind (ein "vollständiges Netzwerk"), fällt die BCE-Regel mit bekannten, fairen Methoden zusammen. Aber in komplexen Netzwerken ist sie die einzige Lösung, die mathematisch konsistent ist.

Zusammenfassung in einem Satz

Frank Huettner hat eine neue Methode entwickelt, um Geld in Gruppen fair zu verteilen, wenn die Leistung eines Teilnehmers davon abhängt, wie die ganze Welt um ihn herum aussieht – und zwar so, dass niemand durch das Weggehen eines anderen unfair benachteiligt wird, selbst wenn die Verbindungen kompliziert verschlungen sind.

Es ist wie eine neue Art, den "Beitrag" eines jeden Mitglieds in einem riesigen, vernetzten Web zu messen, bei dem man nicht nur auf die direkte Hand reicht, sondern auf das gesamte Netz schaut, das den anderen zusammenhält.

Technische Zusammenfassung

1. Problemstellung und Motivation

Das Paper adressiert ein zentrales Problem in der kooperativen Spieltheorie mit Netzwerken: Die Verteilung von Gewinnen (Allokation) in Spielen mit Externalitäten.

• Kontext: In klassischen Netzwerkspielen (z. B. Myerson [1977]) hängt der Wert einer Koalition nur von ihrer internen Struktur ab. In modernen Modellen (Navarro [2007], Jackson & Wolinsky [1996]) kann der Wert einer Komponente jedoch von der gesamten Netzwerkstruktur abhängen (Externalitäten zwischen Komponenten).
• Das Dilemma: Zwei etablierte Axiome zur Charakterisierung von Allokationsregeln führen in Anwesenheit von Externalitäten zu unterschiedlichen Ergebnissen:
  1. Fairness (F): Betrachtet das Entfernen einer einzelnen Verbindung (Link).
  2. Balanced Contributions (BC): Betrachtet den vollständigen Rückzug eines Spielers (Entfernung aller seiner Verbindungen).
• Lücken im Wissen: Während die Kombination aus Component Efficiency (CE) und Fairness (FCE-Regel) bereits charakterisiert ist, fehlte bisher eine Existenz- und Eindeutigkeitsanalyse für eine Regel, die Component Efficiency und Balanced Contributions in Netzwerken mit Externalitäten erfüllt.
• Beispiel: Das Paper zeigt, dass Fairness indirekte Abhängigkeiten ignoriert, die Balanced Contributions erfasst. Wenn Spieler 3 von der Verbindung zwischen 1 und 2 profitiert, aber nur über 1 erreichbar ist, führt der Rückzug von 1 zum Zusammenbruch des Gewinns für 3. BC erfasst diese Abhängigkeit, F nicht.

2. Methodik und Konstruktion

Der Autor entwickelt eine neue Allokationsregel, die BCE-Regel (Balanced Contributions with Externalities), und beweist deren Existenz und Eindeutigkeit.

A. Axiome

Die Regel wird durch folgende Axiome definiert:

1. Component Efficiency (CE): Die Summe der Auszahlungen aller Spieler in einer verbundenen Komponente $C$ entspricht dem Wert dieser Komponente im Netzwerk $g$: $\sum_{i \in C} \phi_i(w, g) = w(C, g)$.
2. Balanced Contributions (BC): Für jeden direkten Link $\{i, j\}$ im Netzwerk gilt: Der Gewinn, den Spieler $i$ durch die Anwesenheit von $j$ erzielt, ist gleich dem Gewinn, den $j$ durch die Anwesenheit von $i$ erzielt.
   • Formel: $\phi_i(w, g) - \phi_i(w, g-j) = \phi_j(w, g) - \phi_j(w, g-i)$.
   • Wichtig: Hier wird der vollständige Rückzug ($g-j$) betrachtet, nicht nur das Löschen des Links.

B. Konstruktion der BCE-Regel

Da die Gleichungen für BC auf allen Links gleichzeitig gelten müssen, ist die direkte Lösung schwierig. Huettner konstruiert die Regel induktiv:

1. Induktionsbasis: Für leere Netzwerke erhält jeder Spieler den Wert seiner Einzelkomponente.
2. Induktionsschritt: Für ein Netzwerk mit $m$ Links wird ein minimaler BFS-Baum (Breitensuche, sortiert nach Index) innerhalb jeder Komponente gewählt.
3. Berechnung:
   • Es werden Offset-Werte $\gamma_j$ entlang des Baumes berechnet, die die Asymmetrie der Beiträge in den Subnetzwerken (ohne den jeweiligen Nachbarn) widerspiegeln.
   • Die Auszahlung setzt sich zusammen aus einem gleichverteilten Restwert der Komponente plus dem individuellen Offset $\gamma_i$.
   • Hinweis: Obwohl die Konstruktion einen spezifischen Baum nutzt, wird später gezeigt, dass das Ergebnis unabhängig von der Wahl des Baumes ist.

C. Der Beweis der Existenz: Die Cycle-Sum-Identität

Die größte Herausforderung besteht darin zu zeigen, dass die induktiv konstruierte Regel (die nur BC auf Baumkanten garantiert) auch BC auf Nicht-Baum-Kanten (Zyklen) erfüllt.

• Lemma 4 (Cycle-Sum Identity): Der Autor leitet eine Identität her, die den BC-Residualwert (die Abweichung von der BC-Bedingung) auf einer Nicht-Baum-Kante als alternierende Summe von BC-Residualwerten in echten Teilnetzwerken (Subnetzwerken) ausdrückt.
• Induktionsargument: Da die BC-Bedingung in allen kleineren Netzwerken (weniger Links) per Induktionsannahme gilt, sind die Residualwerte in den Teilnetzwerken null. Daraus folgt, dass auch der Residualwert auf der Nicht-Baum-Kante null ist. Dies schließt die Lücke und beweist, dass BC auf allen Links gilt.

3. Hauptergebnisse und Theoreme

• Theorem 3 (Hauptsatz): Die BCE-Regel ist die einzige Allokationsregel, die Component Efficiency (CE) und Balanced Contributions (BC) für Netzwerke mit Externalitäten erfüllt.
• Unvereinbarkeit der Axiome:
  • Corollary 7: CE und Pair-wise Balanced Contributions (BC+, die BC für alle verbundenen Paare, nicht nur direkte Nachbarn, fordert) sind in Anwesenheit von Externalitäten unvereinbar.
  • Corollary 9: CE, BC und Fairness (F) sind in Netzwerken mit Externalitäten gegenseitig unvereinbar. Man kann nicht alle drei gleichzeitig erfüllen.
• Spezialfälle:
  • Keine Externalitäten: Wenn der Wert nur von der internen Struktur abhängt, fällt die BCE-Regel mit dem Myerson-Wert (für TU-Spiele) und der Jackson-Wolinsky-Regel zusammen.
  • Vollständiges Netzwerk: Auf dem vollständigen Graphen ($g_N$) reduziert sich die BCE-Regel auf den externality-free Shapley-Wert (basierend auf einem transformierten TU-Spiel $\bar{v}_{EF}$), ohne dass eine spezifische Unabhängigkeitsannahme getroffen werden muss.

4. Vergleich mit der FCE-Regel (Fairness-basiert)

Ein wesentlicher Teil des Papers kontrastiert die BCE-Regel mit der bereits bekannten FCE-Regel (Navarro [2007]):

Merkmal	BCE-Regel (Balanced Contributions)	FCE-Regel (Fairness)
Axiom	BC (vollständiger Rückzug)	F (Einzelner Link-Entzug)
Abhängigkeit vom Graphen	Genuin: Die Regel reagiert auf die spezifische Topologie, auch wenn die graph-restricted Spielwerte gleich sind.	Reduzierbar: Die Regel hängt nur vom graph-restricted PFF-Spiel ab ($\Psi_{FCE}(v, g) = \Phi^{\preceq}(v_g)$).
Beispiel (Fig. 5)	Unterscheidet zwischen $g$ und $g'$, auch wenn $v_g = v_{g'}$. Der Link $\{1,3\}$ ändert die Machtverteilung durch BC.	Liefert für $g$ und $g'$ das gleiche Ergebnis, da der Link $\{1,3\}$ im graph-restricted Spiel keine Rolle spielt.
Formel	Keine geschlossene Formel bekannt; definiert durch induktive Konstruktion.	Hat eine geschlossene Formel (Myersons PFF-Formel angewendet auf das restringierte Spiel).

Wichtiges Ergebnis (Corollary 22): Es existieren Netzwerke $g, g'$ und ein Spiel $v$, für die $v_g = v_{g'}$ gilt, aber $\Psi_{BCE}(v, g) \neq \Psi_{BCE}(v, g')$. Die BCE-Regel kann also nicht auf eine graph-unabhängige Formel angewendet auf das restringierte Spiel reduziert werden.

5. Signifikanz und Implikationen

• Theoretische Lücke: Das Paper schließt eine fundamentale Lücke in der Netzwerkspieltheorie, indem es zeigt, dass Balanced Contributions auch mit Externalitäten konsistent ist, aber zu einer anderen, strukturell komplexeren Regel führt als Fairness.
• Strukturelle Komplexität: Die BCE-Regel lässt sich nicht durch einen Potentialansatz (wie den Hart-Mas-Colell-Potential für den Shapley-Wert) oder einfache Dividenden-Formeln darstellen. Dies liegt daran, dass die Bedingung "Balanced Contributions für alle Paare" (BC+) in diesem Setting mit CE kollidiert.
• Praktische Relevanz: Die Regel ist relevant für Situationen, in denen die Drohung des vollständigen Austritts eines Akteurs (und nicht nur des Lösens einer Verbindung) die Verhandlungsmacht bestimmt.
• Offene Fragen: Das Paper wirft die Frage auf, ob die BCE-Regel durch nicht-kooperative Verhandlungsprotokolle (z. B. auf Baumstrukturen basierend) implementiert werden kann, da die Standard-Mechanismen (wie Bidding) auf BC+ angewiesen sind.

Fazit: Frank Huettner zeigt, dass Balanced Contributions in Netzwerken mit Externalitäten eine wohldefinierte, eindeutige, aber mathematisch anspruchsvolle Allokationsregel (BCE) erzwingt, die sich fundamental von der Fairness-basierten FCE-Regel unterscheidet und nicht auf bekannte graph-unabhängige Formeln reduzierbar ist.