New paper solves stable coalition formation in federated learning with hedonic game theory

A new theoretical framework from researcher Cengis Hasan tackles a core challenge in clustered federated learning: how to group heterogeneous participants into stable, budget-feasible coalitions that train shared models. The model separates learning benefit, system cost, participant cost, and monetary transfers, then converts coalition surplus into hedonic preferences via an allocation rule. Weak budget feasibility ensures the coordinator retains nonnegative surplus. The resulting game is an exact potential game, meaning a Nash-stable partition always exists and every strict better-response process converges to a stable outcome. The author also provides price-of-stability guarantees, showing both additive and multiplicative bounds on welfare loss, with the latter asymptotically tight.

In a preregistered CIFAR-10 study with five random seeds, the mechanism reached the certified estimated-table welfare optimum on every primary instance—a perfect record. However, equal-surplus sharing produced no Nash-stable outcome in three of the five seeds, underscoring the importance of the proposed allocation rule. The paper also introduces a pairwise validation gain metric that yields far more reliable pair signs than conventional gradient alignment, making coalition formation more robust. The work is an extended version of an OptLearnMAS 2021 paper and includes 30 pages of proofs, 5 figures, and open-source code.