# Optimality and Stability in Federated Learning: A Game-theoretic Approach

arXiv: https://arxiv.org/abs/2106.09580 · HTML: https://mlsanity.com/paper/2106.09580/

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 38 references that are in the map.
- First posted on arXiv 17 Jun 2021.

## Builds on (most cited first, 23 of 23)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Clustered Federated Learning: Model-Agnostic Distributed Multi-Task Optimization under Privacy Constraints](https://mlsanity.com/paper/1910.01991/) (2019)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Federated Learning in Mobile Edge Networks: A Comprehensive Survey](https://mlsanity.com/paper/1909.11875/) (2019)
- [Fair Resource Allocation in Federated Learning](https://mlsanity.com/paper/1905.10497/) (2019)
- [Differential Privacy Has Disparate Impact on Model Accuracy](https://mlsanity.com/paper/1905.12101/) (2019)
- [Don't Use Large Mini-Batches, Use Local SGD](https://mlsanity.com/paper/1808.07217/) (2018)
- [Client-Edge-Cloud Hierarchical Federated Learning](https://mlsanity.com/paper/1905.06641/) (2019)
- [Salvaging Federated Learning by Local Adaptation](https://mlsanity.com/paper/2002.04758/) (2020)
- [Multi-institutional Collaborations for Improving Deep Learning-based Magnetic Resonance Image Reconstruction Using Federated Learning](https://mlsanity.com/paper/2103.02148/) (2021)
- [Model-sharing Games: Analyzing Federated Learning Under Voluntary Participation](https://mlsanity.com/paper/2010.00753/) (2020)
- [Blockchain-Federated-Learning and Deep Learning Models for COVID-19 detection using CT Imaging](https://mlsanity.com/paper/2007.06537/) (2020)
- [Cluster-driven Graph Federated Learning over Multiple Domains](https://mlsanity.com/paper/2104.14628/) (2021)
- [An Incentive Mechanism for Federated Learning in Wireless Cellular network: An Auction Approach](https://mlsanity.com/paper/2009.10269/) (2020)
- [One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning](https://mlsanity.com/paper/2103.03228/) (2021)
- [Dynamic Fusion based Federated Learning for COVID-19 Detection](https://mlsanity.com/paper/2009.10401/) (2020)
- [Federated Learning with Taskonomy for Non-IID Data](https://mlsanity.com/paper/2103.15947/) (2021)
- [Auto-FedAvg: Learnable Federated Averaging for Multi-Institutional Medical Image Segmentation](https://mlsanity.com/paper/2104.10195/) (2021)
- [To Split or Not to Split: The Impact of Disparate Treatment in Classification](https://mlsanity.com/paper/2002.04788/) (2020)
- [Incentive Mechanism Design for Federated Learning: Hedonic Game Approach](https://mlsanity.com/paper/2101.09673/) (2021)
- [Accurate and Fast Federated Learning via IID and Communication-Aware Grouping](https://mlsanity.com/paper/2012.04857/) (2020)
- [A Game-Theoretic Approach to Distributed Coalition Formation in Energy-Aware Cloud Federations (Extended Version)](https://mlsanity.com/paper/1309.2444/) (2013)

## Built on by (most cited first, 30 of 40)

- [Mechanisms that Incentivize Data Sharing in Federated Learning](https://mlsanity.com/paper/2207.04557/) (2022)
- [Fairness in Federated Learning via Core-Stability](https://mlsanity.com/paper/2211.02091/) (2022)
- [Collaboration Equilibrium in Federated Learning](https://mlsanity.com/paper/2108.07926/) (2021)
- [DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation](https://mlsanity.com/paper/2306.02071/) (2023)
- [Provably Personalized and Robust Federated Learning](https://mlsanity.com/paper/2306.08393/) (2023)
- [Models of fairness in federated learning](https://mlsanity.com/paper/2112.00818/) (2021)
- [Evaluating and Incentivizing Diverse Data Contributions in Collaborative Learning](https://mlsanity.com/paper/2306.05592/) (2023)
- [A Comprehensive Survey of Federated Transfer Learning: Challenges, Methods and Applications](https://mlsanity.com/paper/2403.01387/) (2024)
- [Free-Rider Games for Federated Learning with Selfish Clients in NextG Wireless Networks](https://mlsanity.com/paper/2212.11194/) (2022)
- [Incentivizing Honesty among Competitors in Collaborative Learning and Optimization](https://mlsanity.com/paper/2305.16272/) (2023)
- [Aequa: Fair Model Rewards in Collaborative Learning via Slimmable Networks](https://mlsanity.com/paper/2502.04850/) (2025)
- [Truthful Incentive Mechanism for Federated Learning with Crowdsourced Data Labeling](https://mlsanity.com/paper/2302.00106/) (2023)
- [Maximizing Global Model Appeal in Federated Learning](https://mlsanity.com/paper/2205.14840/) (2022)
- [Incentivizing Truthful Collaboration in Heterogeneous Federated Learning](https://mlsanity.com/paper/2412.00980/) (2024)
- [pFedWN: A Personalized Federated Learning Framework for D2D Wireless Networks with Heterogeneous Data](https://mlsanity.com/paper/2501.09822/) (2025)
- [How to Collaborate: Towards Maximizing the Generalization Performance in Cross-Silo Federated Learning](https://mlsanity.com/paper/2401.13236/) (2024)
- [pFedGame -- Decentralized Federated Learning using Game Theory in Dynamic Topology](https://mlsanity.com/paper/2410.04058/) (2024)
- [Decentralized Dynamic Cooperation of Personalized Models for Federated Continual Learning](https://mlsanity.com/paper/2509.23683/) (2025)
- [FadMan: Federated Anomaly Detection across Multiple Attributed Networks](https://mlsanity.com/paper/2205.14196/) (2022)
- [Federated Learning as a Network Effects Game](https://mlsanity.com/paper/2302.08533/) (2023)
- [Efficient Core-selecting Incentive Mechanism for Data Sharing in Federated Learning](https://mlsanity.com/paper/2309.11722/) (2023)
- [Cross-Silo Federated Learning Across Divergent Domains with Iterative Parameter Alignment](https://mlsanity.com/paper/2311.04818/) (2023)
- [Online Federation For Mixtures of Proprietary Agents with Black-Box Encoders](https://mlsanity.com/paper/2505.00216/) (2025)
- [Cooperative Game-Theoretic Credit Assignment for Multi-Agent Policy Gradients via the Core](https://mlsanity.com/paper/2506.04265/) (2025)
- [Federated Offline Policy Learning](https://mlsanity.com/paper/2305.12407/) (2023)
- [Price of Stability in Quality-Aware Federated Learning](https://mlsanity.com/paper/2310.08790/) (2023)
- [Incentivized Collaboration in Active Learning](https://mlsanity.com/paper/2311.00260/) (2023)
- [varepsilon-fractional Core Stability in Hedonic Games](https://mlsanity.com/paper/2311.11101/) (2023)
- [On the Decomposition of Differential Game](https://mlsanity.com/paper/2411.03802/) (2024)
- [Nonlinear Equilibrium Transitions in a Potential Game Model for Federated Learning](https://mlsanity.com/paper/2411.11793/) (2024)

## Abstract (arXiv)

Federated learning is a distributed learning paradigm where multiple agents, each only with access to local data, jointly learn a global model. There has recently been an explosion of research aiming not only to improve the accuracy rates of federated learning, but also provide certain guarantees around social good properties such as total error. One branch of this research has taken a game-theoretic approach, and in particular, prior work has viewed federated learning as a hedonic game, where error-minimizing players arrange themselves into federating coalitions. This past work proves the existence of stable coalition partitions, but leaves open a wide range of questions, including how far from optimal these stable solutions are. In this work, we motivate and define a notion of optimality given by the average error rates among federating agents (players). First, we provide and prove the correctness of an efficient algorithm to calculate an optimal (error minimizing) arrangement of players. Next, we analyze the relationship between the stability and optimality of an arrangement. First, we show that for some regions of parameter space, all stable arrangements are optimal (Price of Anarchy equal to 1). However, we show this is not true for all settings: there exist examples of stable arrangements with higher cost than optimal (Price of Anarchy greater than 1). Finally, we give the first constant-factor bound on the performance gap between stability and optimality, proving that the total error of the worst stable solution can be no higher than 9 times the total error of an optimal solution (Price of Anarchy bound of 9).