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

Technische Samenvatting: Stabiele en Budget-Haalbare Coalitievorming voor Clustered Federated Learning

Probleemstelling
Federated learning (FL)-systemen lijden vaak onder statistische heterogeniteit, waarbij een enkele "grote coalitie" van alle deelnemers een suboptimale modellen oplevert. Hoewel clustered FL dit deelt aan de statistische zijde aanpakt door compatibele deelnemers te groeperen, blijft de economische zijde onderbelicht. Specifiek ontbreekt een raamwerk dat gelijktijdig het volgende waarborgt:

1. Stabiliteit: Deelnemers hebben geen prikkel om unilateraal hun toegewezen coalitie te verlaten voor een andere (Nash-stabiliteit) of om te worden afgewezen door een bestemmingscoalitie (individuele stabiliteit).
2. Budget-haalbaarheid: De coördinerende entiteit kan de vereiste transfers financieren om deelnemers te compenseren zonder een tekort te veroorzaken.
3. Efficiëntie: De resulterende stabiele partitie benadert het globale sociale welvaartsoptimum.

Bestaande benaderingen behandelen stabiliteit en budgettaire beperkingen vaak apart of gaan uit van superadditiviteit van het surplus, wat niet geldt in heterogene, niet-convexe FL-omgevingen.

Methodologie
Het artikel modelleert het probleem als een hedonisch coalitievormingsspel met overdraagbaar surplus.

• Systeemmodel: Deelnemers $N$ worden verdeeld in coalities. Elke coalitie $S$ traint een coalitiespecifiek model $\theta_S$ met behulp van gewogen lokale doelstellingen. Het model gaat om met communicatiefouten (gedropte updates) via een veilige aggregatieregel die het model ongewijzigd laat als er geen updates arriveren.
• Economisch Model:
  • Surplus: Het totale overdraagbare surplus $W(S)$ wordt gedefinieerd als het verwachte leerevoordeel $B(S)$ minus coördinatorkosten $C_0(S)$ en deelnemerskosten $d_i(S)$.
  • Transfers: Een coördinator betaalt transfers $t_i(S)$ aan deelnemers. Het nut van de deelnemer is $U_i(S) = t_i(S) - d_i(S)$.
  • Budget-haalbaarheid: De allocatieregel is zwak budget-haalbaar als de coördinator in elke gevormde coalitie een niet-negatief surplus behoudt ($R_0(S) \ge 0$).
• Hedonische voorkeuren: Voorkeuren worden geïnduceerd door een allocatieregel die surplus omzet in nutten. Het artikel richt zich op symmetrische paargewijze surplus-allocaties, waarbij het nut van een deelnemer in een coalitie de som is van de paargewijze waarden $v_{ij}$ met alle andere leden $j \in S$.
• Speltheoretische analyse:
  • De auteurs bewijzen dat symmetrische paargewijze allocaties een exact potentieel spel induceren. De potentiefunctie is de som van de paargewijze waarden binnen de coalities.
  • Deze structuur garandeert het bestaan van een Nash-stabiele partitie en zorgt ervoor dat elke sequentie van strikte better-response bewegingen in een eindig aantal stappen eindigt.
  • Individuele Stabiliteit (waarbij de leden van de bestemming een nieuwkomer moeten toestemmen) wordt eveneens geanalyseerd, waarbij wordt aangetoond dat als de paargewijze waarden niet-negatief zijn, Nash-stabiliteit individuele stabiliteit impliceert.
• Welvaart en Efficiëntie:
  • Sociale welvaart wordt gedecomponeerd in deelnemersnut (gelinkt aan de potentiefunctie) en het door de coördinator behouden slack.
  • Het artikel stelt vast dat exacte budgetbalans (nul behouden slack) een welvaartsoptimale Nash-stabiele partitie oplevert alleen als het surplus exact paargewijs representeerbaar is.
  • Zonder exacte representeerbaarheid kan het welvaartsverlies onbegrensd zijn onder louter budget-haalbaarheid. Echter, als de behouden slack begrensd is ten opzichte van het optimum, wordt een multiplicatieve efficiëntiegarantie (Price of Stability) afgeleid.
  • Globale potentiamaximalisatie wordt getoond gelijk te zijn aan gewogen maximum-agreement correlation clustering. Het artikel stelt een pipeline voor: benader de clustering, pas vervolgens strikte better-response stabilisatie toe om een stabiele partitie te bereiken terwijl de benaderingsgaranties behouden blijven.
• Verificatie: Het artikel biedt een polynomiale tijd oracle-verificatie voor budget-haalbaarheid wanneer de behouden slackfunctie submodulair is.

Kernbijdragen

1. Modellering: Introduceert een coalitiespecifiek FL-model dat onsuccesvolle communicatierondes zonder ongedefinieerde aggregatie afhandelt en geen superadditiviteit veronderstelt.
2. Economische Separatie: Scheidt expliciet leervoordelen, kosten, transfers en het door de coördinator behouden surplus, en leidt voorwaarden af voor budget-haalbaarheid en individuele rationaliteit.
3. Stabiliteitsgaranties: Bewijst dat symmetrische paargewijze allocaties een exact potentieel spel creëren, wat de existentie van Nash-stabiele en individueel stabiele partities en eindige convergentie garandeert.
4. Efficiëntiegrenzen: Karakteriseert de relatie tussen de door de coördinator behouden slack en welvaartsefficiëntie. Het bewijst dat exacte balans alleen optimale stabiliteit oplevert bij een specifieke klasse van surpluses, terwijl een begrensde relatieve slack een strakke multiplicatieve efficiëntiebound biedt.
5. Computationele Complexiteit: Koppelt globale potentiamaximalisatie aan correlation clustering (NP-hard) en leidt end-to-end welvaart guarantees af voor benaderings-plus-stabilisatie pipelines.
6. Verificatie: Toont aan dat exponentieel veel budgetbeperkingen in polynomiale oracle-tijd geverifieerd kunnen worden als de behouden slack submodulair is.
7. Empirische Validatie: Voert een gepre-geregistreerde studie uit op CIFAR-10 met $n=4$ deelnemers.

Experimentele Resultaten
De studie evalueert het mechanisme op vijf seeds van CIFAR-10 data met heterogene distributies:

• Welvaartsoptimaliteit: In een "welwillende" kalibratie bereikte het gedecentraliseerde mechanisme de gecertificeerde geschatte tabel-welvaart voor alle vijf de seeds. De empirische Price of Stability was exact 1.
• Stabiliteit vs. Baselines: In contrast hiermee slaagde een "equal-surplus sharing" baseline er niet in om een Nash-stabiele uitkomst te produceren op drie van de vijf seeds (de Nash-stabiele verzameling was leeg en de dynamiek cycleerde).
• Convergentie: Het gedecentraliseerde better-response proces convergeerde snel (gemiddeld 1,53 bewegingen) vanuit diverse initialisaties.
• Sensitiviteit: In een "lean" (kostengevoelige) kalibratie namen de stabiliteitskosten toe (Price of Stability tot 1,29), en werd de optimale partitie gevoelig voor schattingsfouten, wat de trade-off tussen budget-tightness en stabiliteit benadrukt.
• Estimatie: Pairwise Validation Gain (PVG) estimators boden aanzienlijk betrouwbaardere paar-tekens dan gradient alignment, dat gevoelig was voor vals-positieven.

Betekenis en Claims
Het artikel claimt een verbinding te leggen tussen leerwaarde, monetaire transfers, stabiliteit en economische efficiëntie zonder lokaal evenwicht, globale optimaliteit en computationele tractabiliteit te verwarren.

• Theoretisch: Het corrigeert beperkingen van voorlopig werk door Nash-evenwicht correct te interpreteren als een lokaal potentieel optimum en door geen superadditiviteit te veronderstellen. Het stelt vast dat stabiliteit en efficiëntie twee verschillende concepten zijn die verbonden zijn door de behouden slack van de coördinator.
• Praktisch: Het voorgestelde mechanisme biedt een bewijsbaar stabiele en budget-haalbare manier om heterogene FL-deelnemers te organiseren. De empirische resultaten demonstreren dat hoewel eenvoudige surplus-splitting regels kunnen falen in het stabiliseren, de voorgestelde paargewijze potentie-aanpak convergentie naar een stabiele staat garandeert die samen kan vallen met het welvaartsoptimum.
• Beperkingen: De auteurs merken op dat het huidige model ervan uitgaat dat de coördinator kosten en voordelen kent of schat (incentive allocation in plaats van truthful mechanism design). De empirische validatie is beperkt tot $n=4$ deelnemers om exacte enumeratie en certificering mogelijk te maken, en de resultaten zijn specifiek voor de geschatte waardetabellen van het experiment.

Het werk concludeert dat hoewel exacte budgetbalans in het algemeen geen welvaartsoptimaliteit garandeert, het voorgestelde raamwerk een robuuste theoretische basis en een praktisch mechanisme biedt voor stabiele, budget-haalbare coalitievorming in clustered federated learning.