Stable and Budget-Feasible Coalition Formation for Clustered Federated Learning: A Hedonic Potential-Game Approach

Technische Zusammenfassung: Stabile und budgetführbare Koalitionsbildung für Clustered Federated Learning

Problemstellung
Federated-Learning-Systeme (FL) leiden häufig unter statistischer Heterogenität, wobei eine einzige „Großkoalition“ aller Teilnehmer zu suboptimalen Modellen führt. Während Clustered FL dieses statistische Problem durch die Gruppierung kompatibler Teilnehmer adressiert, bleibt die ökonomische Seite untererforscht. Speziell mangelt es an Frameworks, die gleichzeitig sicherstellen:

1. Stabilität: Teilnehmer haben keinen Anreiz, ihre zugewiesene Koalition einseitig zu verlassen, um zu einer anderen zu wechseln (Nash-Stabilität) oder von einer Zielkoalition abgelehnt zu werden (individuelle Stabilität).
2. Budgetführigkeit: Die koordinierende Entität kann die zur Kompensation der Teilnehmer erforderlichen Transfers finanzieren, ohne ein Defizit zu verursachen.
3. Effizienz: Die resultierende stabile Partition approximiert das globale Sozialwohl-Optimum.

Bestehende Ansätze behandeln Stabilität und Budgetbeschränkungen oft getrennt oder setzen Superadditivität des Überschusses voraus, was in heterogenen, nicht-konvexen FL-Umgebungen nicht der Fall ist.

Methodik
Das Paper modelliert das Problem als ein hedonisches Koalitionsbildungsspiel mit übertragbarem Überschuss.

• Systemmodell: Teilnehmer $N$ werden in Koalitionen partitioniert. Jede Koalition $S$ trainiert ein koalitionsspezifisches Modell $\theta_S$ unter Verwendung gewichteter lokaler Zielfunktionen. Das Modell handhabt Kommunikationsfehler (verlorene Updates) mittels einer Safe-Aggregation-Regel, die das Modell unverändert lässt, falls keine Updates eintreffen.
• Ökonomisches Modell:
  • Überschuss: Der gesamte übertragbare Überschuss $W(S)$ ist definiert als der erwartete Lernvorteil $B(S)$ abzüglich der Koordinatorenkosten $C_0(S)$ und der Teilnehmerkosten $d_i(S)$.
  • Transfers: Ein Koordinator zahlt Transfers $t_i(S)$ an die Teilnehmer. Die Partizipanten-Utility ist $U_i(S) = t_i(S) - d_i(S)$.
  • Budgetführigkeit: Die Allokationsregel ist schwach budgetführig, wenn der Koordinator in jeder gebildeten Koalition einen nicht-negativen Überschuss behält ($R_0(S) \ge 0$).
• Hedonische Präferenzen: Präferenzen werden durch eine Allokationsregel induziert, die den Überschuss in Utilities umwandelt. Das Paper konzentriert sich auf symmetrische paarweise Überschussallokationen, bei denen die Utility eines Teilnehmers in einer Koalition die Summe der paarweisen Werte $v_{ij}$ mit allen anderen Mitgliedern $j \in S$ ist.
• Spieltheoretische Analyse:
  • Die Autoren beweisen, dass symmetrische paarweise Allokationen ein exaktes Potenzialspiel induzieren. Die Potenzfunktion ist die Summe der paarweisen Werte innerhalb der Koalitionen.
  • Diese Struktur garantiert die Existenz einer Nash-stabilen Partition und stellt sicher, dass jede Sequenz strikterter Best-Response-Bewegungen in endlichen Schritten terminiert.
  • Individuelle Stabilität (bei der die Mitglieder der Zielkoalition einem Eintritt zustimmen müssen) wird ebenfalls analysiert und zeigt, dass bei nicht-negativen paarweisen Werten Nash-Stabilität die individuelle Stabilität impliziert.
• Wohlfahrt und Effizienz:
  • Die soziale Wohlfahrt wird in Teilnehmer-Utility (verknüpft mit der Potenzfunktion) und den vom Koordinator zurückbehaltenen Slack zerlegt.
  • Das Paper stellt fest, dass eine exakte Budgetbilanz (Null-Slack beim Koordinator) nur dann eine wohlfahrtsoptimale Nash-stabile Partition liefert, wenn der Überschuss exakt paarweise repräsentierbar ist.
  • Ohne exakte Repräsentierbarkeit kann der Wohlfahrtsverlust unter Budgetführigkeit unbeschränkt sein. Wenn der zurückbehaltene Slack jedoch im Verhältnis zum Optimum beschränkt ist, wird eine multiplikative Effizienzzusicherung (Price of Stability) hergeleitet.
  • Die globale Potenzmaximierung wird als gleichwertig mit gewichteter Maximum-Agreement Correlation Clustering gezeigt. Das Paper schlägt eine Pipeline vor: Approximiere das Clustering, wende dann eine strikte Best-Response-Stabilisierung an, um eine stabile Partition zu erreichen, während die Approximationsgarantien erhalten bleiben.
• Verifikation: Das Paper bietet eine Polynomialzeit-Orakelverifikation für die Budgetführigkeit, wenn die zurückbehaltene Slack-Funktion submodular ist.

Zentrale Beiträge

1. Modellierung: Führt ein koalitionsspezifisches FL-Modell ein, das erfolglose Kommunikationsrunden ohne undefinierte Aggregation handhabt und keine Superadditivität voraussetzt.
2. Ökonomische Trennung: Trennt explizit Lernvorteile, Kosten, Transfers und den zurückbehaltenen Koordinator-Überschuss und leitet Bedingungen für Budgetführigkeit und individuelle Rationalität ab.
3. Stabilitätsgarantien: Beweist, dass symmetrische paarweise Allokationen ein exaktes Potenzialspiel erzeugen, was die Existenz von Nash-stabilen und individuell stabilen Partitionen sowie die endliche Konvergenz garantiert.
4. Effizienzhöhen: Charakterisiert das Verhältnis zwischen dem vom Koordinator zurückbehaltenen Slack und der Wohlfahrtseffizienz. Es beweist, dass exakte Bilanzierung nur bei einer spezifischen Klasse von Überschüssen zur optimalen Stabilität führt, während ein beschränkter relativer Slack eine enge multiplikative Effizienzzusicherung liefert.
5. Komplexität: Verknüpft die globale Potenzmaximierung mit Correlation Clustering (NP-hart) und leitet End-to-End-Wohlfahrtsgarantien für Approximations-plus-Stabilisierungs-Pipelines ab.
6. Verifikation: Zeigt, dass exponentiell viele Budgetbeschränkungen in Polynomialzeit-Orakelzeit verifiziert werden können, wenn der zurückbehaltene Slack submodular ist.
7. Empirische Validierung: Führt eine preregistrierte Studie auf CIFAR-10 Daten mit $n=4$ Teilnehmern durch.

Experimentelle Ergebnisse
Die Studie evaluiert den Mechanismus an fünf Seeds von CIFAR-10 Daten mit heterogenen Verteilungen:

• Wohlfahrtsoptimierung: In einer „benignen“ Kalibrierung erreichte der dezentrale Mechanismus für alle fünf Seeds das zertifizierte geschätzte Tabellen-Wohlfahrtsoptimum. Der empirische Price of Stability war exakt 1.
• Stabilität vs. Baselines: Im Gegensatz dazu scheiterte eine „Equal-Surplus-Sharing“-Baseline in drei von fünf Seeds daran, ein Nash-stabiles Ergebnis zu produzieren (die Menge der Nash-stabilen Zustände war leer, und die Dynamik oszillierte).
• Konvergenz: Der dezentrale Best-Response-Prozess konvergierte schnell (durchschnittlich 1,53 Züge) aus verschiedenen Initialisierungen.
• Sensitivität: In einer „Lean“-(kostensensitiven) Kalibrierung stiegen die Stabilitätskosten (Price of Stability bis zu 1,29), und die optimale Partition wurde sensitiv gegenüber Schätzfehlern, was den Trade-off zwischen Budget-Tightness und Stabilität verdeutlicht.
• Schätzung: Pairwise Validation Gain (PVG) Schätzer lieferten signifikant zuverlässigere Paar-Vorzeichen als Gradient Alignment, welches zu False Positives neigte.

Bedeutung und Ansprüche
Das Paper beansprucht, Lernwert, monetäre Transfers, Stabilität und ökonomische Effizienz zu verbinden, ohne lokales Gleichgewicht, globale Optimalität und rechnerische Handhabbarkeit zu vermengen.

• Theoretisch: Es korrigiert Einschränkungen vorläufiger Arbeiten, indem es das Nash-Gleichgewicht korrekt als lokales Potenzialoptimum interpretiert und keine Superadditivität voraussetzt. Es etabliert, dass Stabilität und Effizienz zwei unterschiedliche Konzepte sind, die durch den zurückbehaltenen Slack des Koordinators verknüpft sind.
• Praktisch: Der vorgeschlagene Mechanismus bietet einen nachweislich stabilen und budgetführigen Weg zur Organisation heterogener FL-Teilnehmer. Die empirischen Ergebnisse zeigen, dass einfache Surplus-Splitting-Regeln zwar scheitern können, der vorgeschlagene paarweise Potenz-Ansatz jedoch die Konvergenz zu einem stabilen Zustand garantiert, der mit dem Wohlfahrtsoptimum übereinstimmen kann.
• Limitierungen: Die Autoren merken an, dass das aktuelle Modell voraussetzt, dass der Koordinator Kosten und Vorteile kennt oder schätzt (Incentive Allocation statt wahrheitsgetreuer Mechanism Design). Die empirische Validierung ist auf $n=4$ Teilnehmer beschränkt, um eine exakte Enumeration und Zertifizierung zu ermöglichen, und die Ergebnisse sind spezifisch für die verwendeten Schätzwert-Tabellen des Experiments.

Das Werk kommt zu dem Schluss, dass eine exakte Budgetbilanz zwar im Allgemeinen keine Wohlfahrtsoptimalität garantiert, das vorgeschlagene Framework jedoch eine robuste theoretische Grundlage und einen praktischen Mechanismus für die stabile, budgetführige Koalitionsbildung im Clustered Federated Learning bietet.