mlsanityData to 7 Oct 2026

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

arXiv 2106.09580 ↗First posted 17 Jun 2021cs.GT cs.CY cs.DCcited by 40

Not on the map. Why?

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).

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

Builds on

23 of 38 references.

References · 23

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,531
  3. 2019Clustered Federated Learning: Model-Agnostic Distributed Multi-Task Optimization under Privacy Constraintscited by 499
  4. 2019Agnostic Federated Learningcited by 451
  5. 2019Federated Learning in Mobile Edge Networks: A Comprehensive Surveycited by 407
  6. 2019Fair Resource Allocation in Federated Learningcited by 389
  7. 2019Differential Privacy Has Disparate Impact on Model Accuracycited by 316
  8. 2019Client-Edge-Cloud Hierarchical Federated Learningcited by 202
  9. 2018Don't Use Large Mini-Batches, Use Local SGDcited by 201
  10. 2020Salvaging Federated Learning by Local Adaptationcited by 142
  11. 2021Multi-institutional Collaborations for Improving Deep Learning-based Magnetic Resonance Image Reconstruction Using Federated Learningcited by 78
  12. 2020Model-sharing Games: Analyzing Federated Learning Under Voluntary Participationcited by 60
11 more
  1. 2020Blockchain-Federated-Learning and Deep Learning Models for COVID-19 detection using CT Imagingcited by 56
  2. 2021Cluster-driven Graph Federated Learning over Multiple Domainscited by 43
  3. 2020An Incentive Mechanism for Federated Learning in Wireless Cellular network: An Auction Approachcited by 39
  4. 2021One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learningcited by 39
  5. 2020Dynamic Fusion based Federated Learning for COVID-19 Detectioncited by 36
  6. 2021Federated Learning with Taskonomy for Non-IID Datacited by 21
  7. 2021Auto-FedAvg: Learnable Federated Averaging for Multi-Institutional Medical Image Segmentationcited by 19
  8. 2020To Split or Not to Split: The Impact of Disparate Treatment in Classificationcited by 14
  9. 2021Incentive Mechanism Design for Federated Learning: Hedonic Game Approachcited by 8
  10. 2020Accurate and Fast Federated Learning via IID and Communication-Aware Groupingcited by 6
  11. 2013A Game-Theoretic Approach to Distributed Coalition Formation in Energy-Aware Cloud Federations (Extended Version)cited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 5; 2023: 12; 2024: 7; 2025: 11; 2026: 3.

40 papers.

Sort:

By area:

  1. 2022Mechanisms that Incentivize Data Sharing in Federated Learningcited by 38
  2. 2022Fairness in Federated Learning via Core-Stabilitycited by 22
  3. 2021Collaboration Equilibrium in Federated Learningcited by 15
  4. 2023DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuationcited by 12
  5. 2023Provably Personalized and Robust Federated Learningcited by 11
  6. 2021Models of fairness in federated learningcited by 8
  7. 2023Evaluating and Incentivizing Diverse Data Contributions in Collaborative Learningcited by 8
  8. 2024A Comprehensive Survey of Federated Transfer Learning: Challenges, Methods and Applicationscited by 8
  9. 2022Free-Rider Games for Federated Learning with Selfish Clients in NextG Wireless Networkscited by 6
  10. 2023Incentivizing Honesty among Competitors in Collaborative Learning and Optimizationcited by 6
  11. 2025Aequa: Fair Model Rewards in Collaborative Learning via Slimmable Networkscited by 6
  12. 2023Truthful Incentive Mechanism for Federated Learning with Crowdsourced Data Labelingcited by 4
28 more
  1. 2022Maximizing Global Model Appeal in Federated Learningcited by 3
  2. 2024Incentivizing Truthful Collaboration in Heterogeneous Federated Learningcited by 3
  3. 2025pFedWN: A Personalized Federated Learning Framework for D2D Wireless Networks with Heterogeneous Datacited by 3
  4. 2024How to Collaborate: Towards Maximizing the Generalization Performance in Cross-Silo Federated Learningcited by 2
  5. 2024pFedGame -- Decentralized Federated Learning using Game Theory in Dynamic Topologycited by 2
  6. 2022FadMan: Federated Anomaly Detection across Multiple Attributed Networkscited by 1
  7. 2023Federated Learning as a Network Effects Gamecited by 1
  8. 2023Efficient Core-selecting Incentive Mechanism for Data Sharing in Federated Learningcited by 1
  9. 2023Cross-Silo Federated Learning Across Divergent Domains with Iterative Parameter Alignmentcited by 1
  10. 2025Online Federation For Mixtures of Proprietary Agents with Black-Box Encoderscited by 1
  11. 2025Cooperative Game-Theoretic Credit Assignment for Multi-Agent Policy Gradients via the Corecited by 1
  12. 2025Decentralized Dynamic Cooperation of Personalized Models for Federated Continual Learningcited by 1
  13. 2023Federated Offline Policy Learningcited by 0
  14. 2023Price of Stability in Quality-Aware Federated Learningcited by 0
  15. 2023Incentivized Collaboration in Active Learningcited by 0
  16. 2023varepsilon-fractional Core Stability in Hedonic Gamescited by 0
  17. 2024On the Decomposition of Differential Gamecited by 0
  18. 2024Nonlinear Equilibrium Transitions in a Potential Game Model for Federated Learningcited by 0
  19. 2024FedCross: Intertemporal Federated Learning Under Evolutionary Gamescited by 0
  20. 2025Energy Minimization for Participatory Federated Learning in IoT Analyzed via Game Theorycited by 0
  21. 2025Tackling Heterogeneity in Federated Learning via Variance-Reduced Boltzmann Sampling within Homogeneous Social Coalitionscited by 0
  22. 2025Incentivizing High-quality Participation From Federated Learning Agentscited by 0
  23. 2025Strategic Incentivization for Locally Differentially Private Federated Learningcited by 0
  24. 2025Gaming and Cooperation in Federated Learning: What Can Happen and How to Monitor Itcited by 0
  25. 2025Semi-overlapping Multi-bandit Best Arm Identification for Sequential Support Network Learningcited by 0
  26. 2026MEMOA: Massive Mixtures of Online Agents via Mean-Field Decentralized Nash Equilibriacited by 0
  27. 2026SCOPE-FL: A Strategy-proof Chain-based Optimal pareto efficient Federated Learning Systemcited by 0
  28. 2026Stable and Budget-Feasible Coalition Formation for Clustered Federated Learning: A Hedonic Potential-Game Approachcited by 0