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

This paper addresses the economic and strategic challenges of clustered federated learning, where participants must be organized into coalitions to train specialized models. The author investigates how to design a system that simultaneously satisfies three requirements: participants must be incentivized to join coalitions, the coordinating entity must remain budget-feasible, and the resulting coalition structure must be stable against unilateral deviations. The study models this as a hedonic coalition-formation game, where a transferable-surplus framework separates learning benefits, system costs, and participant-specific costs.

The core contribution is the proof that for symmetric pairwise surplus allocations, the coalition-formation game is an exact potential game. This property guarantees that a Nash-stable partition always exists and that decentralized, better-response dynamics will converge to such a partition. The author further demonstrates that when retained budget slack is submodular, the exponentially many budget constraints can be verified in polynomial oracle time.

Efficiency is analyzed by decomposing welfare into participant potential and coordinator-retained slack. The study shows that while exact budget balance leads to welfare-optimal stability in pairwise-representable classes, budget feasibility alone can lead to significant welfare loss. Experimental results on CIFAR-10 datasets confirm that the proposed mechanism consistently reaches the certified welfare optimum, outperforming equal-surplus sharing methods which often fail to produce stable outcomes.

This work provides a rigorous bridge between the statistical goals of federated learning and the economic realities of participant cooperation. By formalizing the relationship between monetary transfers, stability, and computational tractability, the paper offers a practical blueprint for designers to build sustainable federated systems. It moves beyond simple heuristic clustering by providing explicit, verifiable conditions that ensure both the coordinator and the participants are satisfied with the resulting collaboration structure.