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

Technical Summary: Stable and Budget-Feasible Coalition Formation for Clustered Federated Learning

Problem Statement
Federated learning (FL) systems often suffer from statistical heterogeneity, where a single "grand coalition" of all participants yields suboptimal models. While clustered FL addresses the statistical side by grouping compatible participants, the economic side remains underexplored. Specifically, there is a lack of frameworks that simultaneously ensure:

1. Stability: Participants have no incentive to unilaterally leave their assigned coalition for another (Nash stability) or to be rejected by a destination coalition (Individual stability).
2. Budget Feasibility: The coordinating entity can finance the transfers required to compensate participants without incurring a deficit.
3. Efficiency: The resulting stable partition approximates the global social welfare optimum.

Existing approaches often treat stability and budget constraints separately or assume superadditivity of surplus, which does not hold in heterogeneous, non-convex FL settings.

Methodology
The paper models the problem as a hedonic coalition-formation game with transferable surplus.

• System Model: Participants $N$ are partitioned into coalitions. Each coalition $S$ trains a coalition-specific model $\theta_S$ using weighted local objectives. The model handles communication failures (dropped updates) via a safe-aggregation rule that leaves the model unchanged if no updates arrive.
• Economic Model:
  • Surplus: The total transferable surplus $W(S)$ is defined as the expected learning benefit $B(S)$ minus coordinator costs $C_0(S)$ and participant costs $d_i(S)$.
  • Transfers: A coordinator pays transfers $t_i(S)$ to participants. Participant utility is $U_i(S) = t_i(S) - d_i(S)$.
  • Budget Feasibility: The allocation rule is weakly budget feasible if the coordinator retains non-negative surplus ($R_0(S) \ge 0$) in every formed coalition.
• Hedonic Preferences: Preferences are induced by an allocation rule converting surplus into utilities. The paper focuses on symmetric pairwise surplus allocations, where a participant's utility in a coalition is the sum of pairwise values $v_{ij}$ with all other members $j \in S$.
• Game-Theoretic Analysis:
  • The authors prove that symmetric pairwise allocations induce an exact potential game. The potential function is the sum of pairwise values within coalitions.
  • This structure guarantees the existence of a Nash-stable partition and ensures that any sequence of strict better-response moves terminates in finite steps.
  • Individual Stability (where destination members must consent to an entrant) is also analyzed, showing that if pairwise values are non-negative, Nash stability implies individual stability.
• Welfare and Efficiency:
  • Social welfare is decomposed into participant utility (linked to the potential function) and coordinator-retained slack.
  • The paper establishes that exact budget balance (zero retained slack) yields a welfare-optimal Nash-stable partition only if the surplus is exactly pairwise-representable.
  • Without exact representability, welfare loss can be unbounded under budget feasibility alone. However, if the retained slack is bounded relative to the optimum, a multiplicative efficiency guarantee (Price of Stability) is derived.
  • Global potential maximization is shown to be equivalent to weighted maximum-agreement correlation clustering. The paper proposes a pipeline: approximate the clustering, then apply strict better-response stabilization to reach a stable partition while preserving approximation guarantees.
• Verification: The paper provides a polynomial-time oracle verification for budget feasibility when the retained slack function is submodular.

Key Contributions

1. Modeling: Introduces a coalition-specific FL model that handles unsuccessful communication rounds without undefined aggregation and does not assume superadditivity.
2. Economic Separation: Explicitly separates learning benefits, costs, transfers, and retained coordinator surplus, deriving conditions for budget feasibility and individual rationality.
3. Stability Guarantees: Proves that symmetric pairwise allocations create an exact potential game, guaranteeing the existence of Nash-stable and individually stable partitions with finite convergence.
4. Efficiency Bounds: Characterizes the relationship between coordinator-retained slack and welfare efficiency. It proves that exact balance yields optimal stability only on a specific class of surpluses, while bounded relative slack provides a tight multiplicative efficiency bound.
5. Computational Complexity: Links global potential maximization to correlation clustering (NP-hard) and derives end-to-end welfare guarantees for approximation-plus-stabilization pipelines.
6. Verification: Shows that exponentially many budget constraints can be verified in polynomial oracle time if the retained slack is submodular.
7. Empirical Validation: Conducts a preregistered study on CIFAR-10 with $n=4$ participants.

Experimental Results
The study evaluates the mechanism on five seeds of CIFAR-10 data with heterogeneous distributions:

• Welfare Optimality: In a "benign" calibration, the decentralized mechanism reached the certified estimated-table welfare optimum for all five seeds. The empirical Price of Stability was exactly 1.
• Stability vs. Baselines: In contrast, an "equal-surplus sharing" baseline failed to produce a Nash-stable outcome on three of the five seeds (the Nash-stable set was empty, and dynamics cycled).
• Convergence: The decentralized better-response process converged rapidly (mean 1.53 moves) from various initializations.
• Sensitivity: In a "lean" (cost-sensitive) calibration, stability costs increased (Price of Stability up to 1.29), and the optimal partition became sensitive to estimation errors, highlighting the trade-off between budget tightness and stability.
• Estimation: Pairwise validation gain (PVG) estimators provided significantly more reliable pair signs than gradient alignment, which was prone to false positives.

Significance and Claims
The paper claims to connect learning value, monetary transfers, stability, and economic efficiency without conflating local equilibrium, global optimality, and computational tractability.

• Theoretical: It corrects limitations of preliminary work by correctly interpreting Nash equilibrium as a local potential optimum and by not assuming superadditivity. It establishes that stability and efficiency are distinct concepts linked by the coordinator's retained slack.
• Practical: The proposed mechanism offers a provably stable and budget-feasible way to organize heterogeneous FL participants. The empirical results demonstrate that while simple surplus-splitting rules may fail to stabilize, the proposed pairwise potential approach guarantees convergence to a stable state that can coincide with the welfare optimum.
• Limitations: The authors note that the current model assumes the coordinator knows or estimates costs and benefits (incentive allocation rather than truthful mechanism design). The empirical validation is limited to $n=4$ participants to allow for exact enumeration and certification, and the results are specific to the estimated value tables of the experiment.

The work concludes that while exact budget balance does not guarantee welfare optimality in general, the proposed framework provides a robust theoretical foundation and a practical mechanism for stable, budget-feasible coalition formation in clustered federated learning.