summaries: This paper examines the game theoretic aspect of federated learning. In the proposed model, the players are strategic and may not provide their data to the learning platform and choose to federate in a small coalition. The authors provide an algorithm to compute the optimal federating arrangement, and also analyze the bound of the price of anarchy in theory. The paper studies a coalition formation process in federated learning. When agents form a coalition, they aggregate their learned parameters in the hope of a more accurate result. The paper presented an algorithm to obtain the optimal way of partitioning the agents in coalitions, so that the total weighted error of the agents is minimized. In addtion, the paper also analyzed the price of anarchy and provided upper bounds of it. This paper studies price of anarchy (PoA) in federated learning. Following the prior work of Donahue and Kleinberg [2021] which initiate a game theoretic model for federated learning, the authors propose a notion of optimality given the average error rates among agents. Under this notion of optimality, the authors first provide an efficient algorithm to compute the optimal solution, and then give PoA bounds that depend on parameters of settings. This paper studies a basic federated learning problem, in which some agents, each one with their own dataset, have to jointly agree on a global model. The paper focuses on the trade-off between stability (enforcing that agents are incentivized to collaborate in the global model) and optimality (maximizing social welfare). The paper studies this trade-off by means of a Price of Anarchy analysis. This paper studies the stable coalition in federated learning, where the agents can choose to join one coalition or leave with incentives to minimize their own errors. The paper focuses on the task of mean estimation, where the error has a closed-form solution. The main contributions are: 1. proposing an optimal algorithm to minimize the weighted sum of errors; 2. providing the upper bound on PoA.
abstractText: 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).
authors.name: Kate Donahue
authors.name: Jon Kleinberg
references.authors: C. Anglano M. Canonico Paolo Castagno Marco Guazzone M. Sereno
references.title: A game-theoretic approach to coalition formation in fog provider federations
references.venue: Third International Conference on Fog and Mobile Edge Computing (FMEC),
references.authors: Elliot Anshelevich Anirban Dasgupta Jon Kleinberg Éva Tardos Tom Wexler Tim Roughgarden
references.title: The price of stability for network design with fair cost allocation
references.venue: SIAM Journal on Computing,
references.authors: Eugene Bagdasaryan Vitaly Shmatikov
references.title: Differential privacy has disparate impact on model accuracy, 2019
references.authors: Avrim Blum Nika Haghtalab Ariel D Procaccia Mingda Qiao
references.title: Collaborative pac learning
references.venue: Advances in Neural Information Processing Systems
references.authors: Avrim Blum Nika Haghtalab Richard Lanas Phillips Han Shao
references.title: One for one, or all for all: Equilibria and optimality of collaboration in federated learning
references.venue: arXiv preprint arXiv:2103.03228,
references.authors: Anna Bogomolnaia Matthew O. Jackson
references.title: The stability of hedonic coalition structures
references.venue: Games and Economic Behavior,
references.authors: Debora Caldarola Massimiliano Mancini Fabio Galasso Marco Ciccone Emanuele Rodolà Barbara Caputo
references.title: Cluster-driven graph federated learning over multiple domains
references.venue: arXiv preprint arXiv:2104.14628,
references.authors: Shengbo Chen Cong Shen Lanxue Zhang Yuanmin Tang
references.title: Dynamic aggregation for heterogeneous quantization in federated learning
references.venue: IEEE Transactions on Wireless Communications,
references.authors: Kate Donahue Jon Kleinberg
references.title: Model-sharing games: Analyzing federated learning under voluntary participation
references.venue: AAAI 2021,
references.authors: M. Duan D. Liu X. Chen R. Liu Y. Tan L. Liang
references.title: Self-balancing federated learning with global imbalanced data in mobile systems
references.venue: IEEE Transactions on Parallel and Distributed Systems,
references.authors: Marco Guazzone Cosimo Anglano Matteo Sereno
references.title: A game-theoretic approach to coalition formation in green cloud federations
references.venue: 14th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing,
references.authors: Pengfei Guo Puyang Wang Jinyuan Zhou Shanshan Jiang Vishal M Patel
references.title: Multi-institutional collaborations for improving deep learning-based magnetic resonance image reconstruction using federated learning
references.venue: arXiv preprint arXiv:2103.02148,
references.authors: Cengis Hasan
references.title: Incentive mechanism design for federated learning: Hedonic game approach, 2021
references.authors: Hadi Jamali-Rad Mohammad Abdizadeh Attila Szabo
references.title: Federated learning with taskonomy for non-iid data
references.venue: arXiv preprint arXiv:2103.15947,
references.authors: Elias Koutsoupias Christos Papadimitriou
references.title: Worst-case equilibria
references.venue: In Annual Symposium on Theoretical Aspects of Computer Science,
references.authors: Rajesh Kumar Abdullah Aman Khan Jay Kumar A Zakria Noorbakhsh Amiri Golilarz Simin Zhang Yang Ting Chengyu Zheng WenYong Wang
references.title: Blockchain-federated-learning and deep learning models for covid-19 detection using ct imaging
references.venue: IEEE Sensors Journal,
references.authors: Yassine Laguel Krishna Pillutla Jerôme Malick Zaid Harchaoui
references.title: A superquantile approach to federated learning with heterogeneous devices
references.venue: 55th Annual Conference on Information Sciences and Systems (CISS),
references.authors: Tra Huong Thi Le Nguyen H. Tran Yan Kyaw Tun Minh N.H. Nguyen Shashi Raj Pandey Zhu Han Choong Seon Hong
references.title: An incentive mechanism for federated learning in wireless cellular network: An auction approach
references.venue: IEEE Transactions on Wireless Communications,
references.authors: J. Lee Jaehoon Oh Yooju Shin S. Yoon
references.title: Accurate and fast federated learning via iid and communication-aware
references.venue: grouping. ArXiv,
references.authors: Tian Li Maziar Sanjabi Ahmad Beirami Virginia Smith
references.title: Fair resource allocation in federated learning, 2019
references.authors: Tian Li Anit Kumar Sahu Ameet Talwalkar Virginia Smith
references.title: Federated learning: Challenges, methods, and future directions
references.venue: IEEE Signal Processing Magazine,
references.authors: W.Y.B. Lim N.C. Luong D.T. Hoang Y. Jiao Y.C. Liang Q. Yang D. Niyato C. Miao
references.title: Federated learning in mobile edge networks: A comprehensive survey
references.venue: IEEE Communications Surveys Tutorials,
references.authors: Tao Lin Sebastian U. Stich Kumar Kshitij Patel Martin Jaggi
references.title: Don’t use large mini-batches, use local sgd, 2018
references.authors: Lumin Liu Jun Zhang S.H. Song Khaled B. Letaief
references.title: Client-edge-cloud hierarchical federated learning
references.venue: IEEE International Conference on Communications (ICC), Jun 2020. doi: 10.1109/icc40277.2020.9148862. URL http://dx.doi.org/10.1109/icc40277.2020
references.authors: H. Brendan McMahan Eider Moore Daniel Ramage Seth Hampson Blaise Agüera y Arcas
references.title: Communication-efficient learning of deep networks from decentralized data, 2016
references.authors: Lokesh Nagalapatti Ramasuri Narayanam
references.title: Game of gradients: Mitigating irrelevant clients in federated learning
references.venue: Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Christos Papadimitriou
references.title: Algorithms, games, and the internet
references.venue: In Proceedings of the thirty-third annual ACM symposium on Theory of computing,
references.authors: Felix Sattler Klaus-Robert Muller Wojciech Samek
references.title: Clustered federated learning: Modelagnostic distributed multitask optimization under privacy constraints
references.venue: IEEE Transactions on Neural Networks and Learning Systems,
references.authors: N. Shlezinger S. Rini Y.C. Eldar
references.title: The communication-aware clustered federated learning problem
references.venue: IEEE International Symposium on Information Theory (ISIT),
references.authors: Akhil Vaid Suraj K Jaladanki Jie Xu Shelly Teng Arvind Kumar Samuel Lee Sulaiman Somani Ishan Paranjpe Jessica K De Freitas Tingyi Wanyan
references.title: Federated learning of electronic health records to improve mortality prediction in hospitalized patients with covid-19: Machine learning approach
references.venue: JMIR medical informatics,
references.authors: Hao Wang Hsiang Hsu Mario Diaz Flavio P. Calmon
references.title: To split or not to split: The impact of disparate treatment
references.venue: in classification,
references.authors: Yingda Xia Dong Yang Wenqi Li Andriy Myronenko Daguang Xu Hirofumi Obinata Hitoshi Mori Peng An Stephanie Harmon Evrim Turkbey
references.title: Auto-fedavg: Learnable federated averaging for multi-institutional medical image segmentation
references.venue: arXiv preprint arXiv:2104.10195,
references.authors: Tao Yu Eugene Bagdasaryan Vitaly Shmatikov
references.title: Salvaging federated learning by local adaptation, 2020
references.authors: Weishan Zhang Tao Zhou Qinghua Lu Xiao Wang Chunsheng Zhu Haoyun Sun Zhipeng Wang Sin Kit Lo Fei-Yue Wang
references.title: Dynamic fusion-based federated learning for covid-19 detection
references.venue: IEEE Internet of Things Journal,
sections.heading: 1 Introduction
sections.text: Recent advances of machine learning techniques has made it possible to apply powerful prediction algorithms to a variety of domains. However, in real-world situations, data is often distributed across multiple locations and cannot be combined to a central repository for training. For example, consider patient medical data located at hospitals or student educational data at different schools. In each case, the individual agents (hospitals or schools) who hold the data wish to find a model that minimizes their error. However, the data at each location may be insufficient to train a robust model. Instead, the agents may prefer to build a model using data from multiple agents: multiple hospitals or schools. Collectively, the combined data may be able to produce a model with much higher accuracy, providing more powerful predictions to each agent and increasing overall welfare. However, it may be infeasible to transfer the data to some coordinating entity to build a global model: privacy, data size, and data format are all possible reasons that would make transferring data not a reasonable solution.
  Federated learning is a novel distributed learning paradigm that aims to solve this problem (McMahan et al. [2016]). Data remains at separate local sites, which individual agents use to learn local model parameters or parameter updates. Then, only the parameters are transferred to the coordinating entity
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  (for example, a technology company), which averages together all of the parameters in order to form a single global model, which all of the agents use. Federated learning is a rapidly growing area of research (Li et al. [2020], Kairouz et al. [2019], Lim et al. [2020]).
  However, research has also noted that federated learning, in its traditional form, may not be the best option for each agent (Yu et al. [2020], Bagdasaryan and Shmatikov [2019], Li et al. [2019], Mohri et al. [2019]). In the real world, agents may differ in their true distribution: the true model of patient outcomes at hospital A may differ from the true model at hospital B, for example. If these differences are large enough, federating agents may see their error increase under certain situations, potentially even beyond what they would have obtained with only local learning. For example, a player with relatively few samples may end up seeing its model “torqued” by the presence of a player with many samples. For this reason, agents may not wish to federate with every other potential agent.
  Instead, each agent faces a choice: given the costs and benefits of federating with different players, it must determine which of the exponentially many combinations of players it would prefer to federate with. Simultaneously, every other agent is also attempting to identify and join a federating group that it prefers - and agents may have conflicting preferences. Prior work (Donahue and Kleinberg [2021], Hasan [2021]) has formulated this problem as a hedonic game, which each player derives some cost (error) from the coalition they join. The aim of such research has been to identify partitions of players that are stable against deviations, for varying definitions of stability. A hedonic game in general may not have any stable arrangements, so the area’s contributions in the analysis of stability adds valuable insight into the incentives of federating agents.
  However, this framework also leaves open multiple game theoretic questions. While the federating agents have individual incentives to reduce their error, society as a whole also has an interest in minimizing the overall error. In the school example, individual schools wish to find coalitions that work well on their own sub-populations, while the overall district or state may have an interest in finding an overall set of coalitions that minimizes the overall error. This analysis of a coalition partition’s overall cost falls under the game theoretic notion of optimality.
  One natural question relates to the tension between these two goals: the self-interested goal of the individual actors (stability) and the overall goal of reducing total cost (optimality). Given a that set of self-interested agents has found a stable solution, how far from optimal could it be? This is reflected by the Price of Anarchy of a game, the canonical approach to study optimality and stability jointly (Papadimitriou [2001], Koutsoupias and Papadimitriou [1999]). The Price of Anarchy (PoA) is a ratio where the numerator is equal to the highest-cost stable arrangement and the denominator is equal to the lowest-cost arrangement (the optimal arrangement). It is lower bounded by 1, a bound that it achieves only if all stable arrangements are optimal. A higher Price of Anarchy value implies a greater trade off between stability and optimality, and bounding the Price of Anarchy for a particular game puts a limit on this trade-off. Federated learning is a situation where questions of stability have been analyzed, but to our knowledge there has been no systematic analysis of the Price of Anarchy in a model of federated learning.
  The present work: A framework for optimality and stability in federated learning In this work, we make two main contributions to address this gap. First, we provide an efficient, constructive algorithm for calculating an optimal federating arrangement. Secondly, we prove the first-ever constant bound on the Price of Anarchy for this game, showing that the worst stable arrangement is no more than 9 times the cost of the best arrangement.
  We begin Section 4 by defining optimality, drawing on a notion of weighted error derived from the standard objective in federated learning literature. The main contribution of this section is an efficient, constructive algorithm for calculating an optimal arrangement, along with a proof of its optimality. However, as demonstrated in Section 5, optimality and stability are not always simultaneously achieved. This section analyzes the Price of Anarchy, which measures how far from optimal the worst stable arrangement can be. First, we demonstrate that the optimal arrangement is not always stable. Next, we show that there exist sub-regions where the Price of Anarchy is equal to 1. Finally, this section proves an overall Price of Anarchy bound of 9, the first constant bound for this game.
  It is worth emphasizing that, beyond the Price of Anarchy bound itself, part of the contribution of this work is the optimization and analysis to produce this bound. The proofs for this contribution are modular and illuminate multiple properties about the broader federated learning game under study.
  As such, these contributions could be useful for further investigating this model. For example, the modular structure of our proof is what enables us to establish stronger bounds for certain sub-cases.
  The results in this paper are theoretical and do not depend on any experiments or code. However, while writing the paper, we found it useful to write and work with code to check conjectures. Some of that code is publicly available at github.com/kpdonahue/model_sharing_games.
sections.heading: 2 Related work
sections.text: Federated learning As we mentioned previously, federated learning has recently seen numerous advances. In this section, we highlight a few papers in federated learning that are especially related to our work.
  The idea that agents might differ in their true models (that data might be generated non-i.i.d. across multiple agents) is commonly acknowledged in the federated learning literature. For example, Yu et al. [2020], Bagdasaryan and Shmatikov [2019] empirically demonstrate that federated learning, and especially privacy-related additions, can cause a wide disparity in error rates. Some techniques have been developed specifically towards this problem. For example, hierarchical federated learning adds an additional layer of hierarchical structure to federated learning, which could be used to reduce latency or to cluster together similar players (Lin et al. [2018], Liu et al. [2020]). Many other works also relate to clustering, such as (Lee et al. [2020], Sattler et al. [2020], Shlezinger et al. [2020], Wang et al. [2020], Duan et al., Jamali-Rad et al. [2021], Caldarola et al. [2021]). Nagalapatti and Narayanam [2021] uses tools from cooperative game theory to selectively combine gradient updates from multiple agents. These works, which tend to be more applied than our work, may also differ in that they analyze situations where additional information is known, such as the data distribution at each location.
  Other work aims to improve accuracy rates by selecting acquiring additional data (Blum et al. [2017], Duan et al. [2021]). Some papers specifically analyze federated learning for high-stakes situations such as medical settings (Xia et al. [2021], Guo et al. [2021], Vaid et al. [2021], Kumar et al. [2021], Zhang et al. [2021]). In general, all of these works have the goal of reducing the average error over all federating agents, which we will use to motivate our definition of optimality in later sections.
  Game theory in federated learning The closest work to this current paper is our prior paper Donahue and Kleinberg [2021], which we discuss in greater detail in Section 3. Another paper using hedonic game theory to analyze federated learning games is Hasan [2021], which gives conditions for Nash stability in federated learning. Other works analyze the incentives of players to contribute resources towards federated learning: Blum et al. [2021] analyzes fairness and efficiency in sampling additional points for federated learning and Le et al. [2021] analyzes incentives for agents to contribute computational resources in federated learning. Interestingly, multiple works take a game theoretic approach towards coalition formation in cloud computing, but with the aim of minimizing some cost besides error, such as electricity usage Guazzone et al. [2014], Anglano et al. [2018].
sections.heading: 3 Model and assumptions
sections.text: We assume that there are M total agents (sometimes referred to as players). Each agent i 2 [M ] has drawn ni data points from their true local distribution g(✓i), where ✓i are their true local parameters and g(·) is some true labeling function. A player’s goal is to learn a model with low expected error on its own distribution. If a player opts for local learning, then it uses its local estimate of these parameters g(✓̂i) to predict future data points, obtaining error erri({i}). If a set of players C are federating together, we say that they are in a coalition or cluster together. They combine their local estimates of parameters into a single federated estimate, governed by the weighted average of their parameters:
  ✓̂C = 1P i2C ni · X i2C ni · ✓̂i (1)
  A federating player i obtains error erri(C): note that this value may differ between players in the same coalition. For example, if player j has more samples than player k, then ✓̂C will be weighted more towards player j, meaning that player j will have lower expected error than k.
  The weighted average method in Equation 1 is commonly used in federated learning (McMahan et al. [2016]). Because it is the most straightforward method, it is sometimes called “vanilla” federated learning. Alternative ways of federation might involve customizing the model for individuals, as in domain adaptation. For example, Donahue and Kleinberg [2021] models three methods of federation: vanilla (called “uniform”), as well as two models of domain adaptation.
  There are multiple reasons why we opted to analyze the federation method in Equation 1 in this work. First of all, this federation method is the most straightforward method, and as such it is the natural candidate to begin analysis. Secondly, this federation method is the most interesting to analyze technically. Domain adaptation serves to increase the incentives of an individual agent to participate in federation: it reduces the tension between an individual’s incentives and the optimal overall arrangement. Because of this, for Price of Anarchy it is more valuable and challenging to explore the case in Equation 1, where incentives are more opposed.
sections.heading: 3.1 Theoretical model of federation from Donahue and Kleinberg [2021]
sections.text: Federated learning has been the subject of both applied and theoretical analysis; our focus here is on the theoretical side. In addition, for game theoretical reasoning to be feasible, we need a model that gives exact errors (costs) for each player, rather than bounds: these are needed in order to be able to argue that a certain arrangement is optimal, for example.
  We opt to use the model developed in our prior work Donahue and Kleinberg [2021], which produces the closed-form error value seen in Lemma 1 below. While we work within this model, we emphasize that Donahue and Kleinberg [2021] asked different questions from this paper’s focus: our prior work focused on developing the federated learning model and analyzing the stability of federating coalitions, while our current work analyzes optimality and Price of Anarchy. Lemma 1 (Lemma 4.2, from Donahue and Kleinberg [2021]). Consider a mean estimation task as follows: player j is trying to learn its true mean ✓j . It has access to nj samples drawn i.i.d. Y ⇠ Dj(✓j , ✏2j ), a distribution with mean ✓j and variance ✏2j . Given a population of players, each has drawn parameters (✓j , ✏2j ) ⇠ ⇥ from some common distribution ⇥. A coalition C federating together produces a single model based on the weighted average of local means (Eq. 1). Then, the expected mean squared error player j experiences in coalition C is:
  errj(C) = µeP i2C ni + 2 ·
  P i2C,i6=j n 2 i + ⇣P i2C,i 6=j ni ⌘2
  P i2C ni 2 (2)
  where µe = E(✓i,✏2i )⇠⇥[✏ 2 i ] (the average noise in data sampling) and 2 = V ar(✓i) (the average distance between the true means of players).
  Note that Donahue and Kleinberg [2021] also analyzes a linear regression game with a similar cost function, though in this work we will restrict our attention to the mean estimation game.
  We use some of the same notion and modeling assumptions as Donahue and Kleinberg [2021]. For example, we use C to refer to a coalition of federating agents and ⇧ to refer to a collection of coalitions that partitions the M agents. We will use NC to refer to the total number of samples present in coalition C: NC = P i2C ni. In a few lemmas we will re-use minor results proven in Donahue and Kleinberg [2021], citing them for completeness.
  For technical assumptions, we assume number of samples {ni} is fixed and known by all. We also assume that the parameters µe, 2 are approximately known: in particular, results will depend on whether the number of samples is larger or smaller than the critical threshold µe 2 . We assume that a player does not know anything else about its own true parameters ✓i or the parameters of other players: for example, it does not know the true generating distribution ⇥ or if its true parameters are likely to lie far from the parameters of other players. We assume that each player has a goal of obtaining a model with low expected test error on its personal distribution, and that the federating coordinator is motivated to minimize some notion of total cost, but is otherwise impartial.
  Finally, it is worth emphasizing key differences between this current work and Donahue and Kleinberg [2021]. The focus of Donahue and Kleinberg [2021] is defining a theoretical model of federated learning and analyzing the stability of such an arrangement. As such, it focuses solely on individual incentives, rather than overall societal welfare. On this other hand, this current work focuses on
  discussions of optimality (overall welfare) and Price of Anarchy. Finally, this paper work is in some ways more general: while some results in Donahue and Kleinberg [2021] only allow players to have two different numbers of samples (“small” or “large”), every result in our work holds for arbitrarily many players with arbitrarily many different numbers of samples. This distinction is a function of the questions analyzed in each paper: questions of stability (as in Donahue and Kleinberg [2021]) are much harder to analyze for players with arbitrarily many different sizes.
sections.heading: 4 Optimality
sections.text: We will begin with the question of optimality. As motivation, it is useful to consider the objective function of most federated learning papers McMahan et al. [2016]:
  min ✓
  errw(✓) = MX
  i=1
  pi · erri(✓) =⇤ 1
  P M
  i=1 ni
  MX
  i=1
  ni · erri(✓)
  While the weights can be any pi > 0, P M
  i=1 pi = 1, the ⇤ equality reflects the common setting where they are taken to be the empirical average. In this work, we will take the empirical average as our cost function: Definition 1. A coalition partition ⇧ is optimal if it minimizes the weighted sum of errors across players, as defined below:
  fw(⇧) = X
  C2⇧ fw(C) =
  X
  C2⇧
  X i2C ni · erri(C)
  We will say that a coalition partition ⇧ is in OPT if it achieves minimal cost. Note that multiple partitions may achieve minimal cost, so OPT is a set of partitions.
  Because ⇧ is a disjoint partition over the M players, fw(⇧) is simply the error errw(✓) scaled by a constant. Therefore, minimizing fw(⇧) is equivalent to minimizing the weighted average of errors.
  Some machine learning papers modify the empirical average objective to achieve other goals. For example, Li et al. [2019], Mohri et al. [2019] consider variants where this goal is re-weighted in order to achieve certain fairness goals. Appendix A discusses other possible cost functions.
  All of the above analysis holds for any model of federated learning. Lemma 2, below, gives the specific form of cost for federated learning using the model from Donahue and Kleinberg [2021]. The remaining analysis in this paper will assume this cost function. Proofs for results in this section are given in Appendix B. Lemma 2. Consider a partition ⇧ made up of coalitions {Ci}. Then, using the error form given in Equation 2, the total cost of ⇧ is given by
  fw(⇧) = X
  C2⇧
  ⇢ µe + 2 ·NC 2 P i2C n 2 i
  NC
  The two most common arrangements in machine learning tasks are local learning (which we will denote by ⇡l) and the federation in the grand coalition (⇡g), where all of the players are federating together in a single coalition. However, Lemmas 3 and 4 demonstrate that either of these could perform arbitrarily poorly as compared the cost-minimizing (optimal) arrangement. Lemma 3. 8⇢ > 1, there exists a setting where local learning results in average error more than ⇢ times higher than optimal: fw(⇡l)
  fw(OPT ) > ⇢.
  Lemma 4. 8⇢ > 1, there exists a setting where federating in the grand coalition results in average error more than ⇢ times higher than optimal: fw(⇡g)
  fw(OPT ) > ⇢.
  A priori, finding a partition of players that minimizes total cost seems extremely challenging. There are exponentially many options for partitions, and two lemmas above have shown that either of the most common choices could be arbitrarily far from optimal. However, the next section will provide an efficient, constructive algorithm to calculate an optimal partition of players into federating coalitions.
sections.heading: 4.1 Calculating an optimal arrangement
sections.text: The main contribution of this section is Theorem 1, which gives an algorithm for minimizing the total weighted error of the federating agents. Theorem 1. Consider a set of players {ni}. An optimal partition ⇧ can be created as follows: first, start with every player doing local learning. Then, begin by grouping the players together in ascending order of size, stopping when the first player would increase its error by joining the coalition from local learning. Then, the resulting partition ⇧ is optimal.
  Though the algorithm in Theorem 1 is straightforward, proving the optimality of the resulting partition ⇧ requires several sub-lemmas. Each sub-lemma is a building-block that describes certain operations that either increase or decrease total cost. The proof of Theorem 1 largely consists of sequentially using these sub-lemmas in order to demonstrate the optimality of the calculated partition.
  Statement and description of supporting lemmas First, Lemma 5 demonstrates a close relationship between movements of players that reduce total cost and movements of players that are in that player’s self-interest (recall that players always wish to minimize their expected error). Specifically, it shows that a player wishes to join a coalition from local learning if and only if that move would reduce total cost for the entire partition. Lemma 5 (Equivalence of player preference and reducing cost). Take any coalition Q and any player j. Then, a player wishes to join that coalition (from local learning) if and only if doing so would reduce total cost. That is,
  fw({nj}) + fw(Q) fw({nj} [Q) , errj({nj}) errj({nj} [Q)
  Next, Lemma 6 shows that “swapping” the roles of two players (one doing local learning, one federating in a coalition) reduces total cost when the larger player is removed to local learning. Lemma 6 (Swapping). Take any set Q including a player nj > nk, where the player nk is doing local learning. Then, swapping the roles of players k and j always decreases total cost.
  fw(Q [ {nj}) + fw({nk}) > fw(Q [ {nk}) + fw({nj})
  Lemmas 7 and 8 give results for when players are incentivized to leave or join a particular coalition: they show that such incentives are monotonic in the size of the player. By Lemma 5, these results also show the monotonicity of cost-reducing operations. Note that these lemmas are not equivalent: they differ in whether the reference player j is already in the coalition or not. Lemma 7 (Monotonicity of joining). If a player of size nj would prefer local learning to joining a coalition Q, then any player of size nk nj also prefers local learning to joining the same coalition. That is, for nk nj ,
  errj(Q [ {nj}) errj({nj}) ) errk(Q [ {nk}) errk({nk}) Conversely, if a player j wishes to join Q, then any other player of size nk  nj would have also wanted to join. That is, for nj nk,
  errj(Q [ {nj})  errj({nj}) ) errk(Q [ {nk})  errk({nk})
  Lemma 8 (Monotonicity of leaving). Take any coalition Q. Then, if any player j 2 Q of size nj wishes to leave Q for local learning, then any player of size nk nj also wishes to leave for local learning. That is, for nk nj
  errj(Q) errj({nj}) ) errk(Q) errk({nk}) Conversely, if a player j 2 Q of size nj does not wish to leave Q for local learning, then any player k 2 Q of size nk  nj also does not wish to leave. That is, for nk  nj
  errj(Q)  errj({nj}) ) errk(Q)  errk({nk})
  All of the above lemmas have analyzed situations where a single player is moving between coalitions. Lemma 9 analyzes cases where multiple players are rearranged simultaneously. Specifically, it provides an algorithm for combining together two separate groups (and then removing certain players) that is guaranteed to keep constant or reduce total cost.
  Lemma 9 (Merging). Consider two groups of players, P,Q. First, merge together the two groups to form P [Q. Then, remove players from P [Q to local learning, removing them in descending order of size. Stop removing players when the first player would prefer to stay (removing it would increase its error). Then, this overall process maintains or decreases total error. In other words,
  fw(Q) + fw(P ) fw({Q [ P} \ L) + X
  i2L fw({ni}) (3)
  where L is the set of large players removed in descending order of size. The inequality is strict so long as the final structure is not identical to the first, up to renaming of players, and it is not the case that all the players have the exact same size.
  The proof of Theorem 1 is given simply by applying the lemmas sequentially to show that any other partition ⇧0 can be converted to the described partition ⇧ through a series of operations that decrease or hold constant total cost.
sections.heading: 5 Price of Anarchy
sections.text: The previous section defined the “optimality” of a federating arrangement as its average error, and additionally provided an efficient algorithm to calculate a lowest-cost arrangement. Given that much of prior work (Donahue and Kleinberg [2021], Hasan [2021]) has studied the stability of cooperative games induced by federated learning, the next natural question is to study the relationship between stability and optimality. This section analyzes this relationship, using the canonical game theoretic tools of Price of Anarchy and Price of Stability. All proofs for this section are in Appendix C.
  First, we will define the notions of stability under analysis, which are all drawn from standard cooperative game theory literature (Bogomolnaia and Jackson [2002]). A partition of players ⇧ is core stable if there does not exist a set of players that all would prefer leave their location in ⇧ and form a coalition together. A partition is individually stable (IS) if there does not exist a single player i that wishes to join some existing coalition C, where all members of C weakly prefer that i join. Our results will primarily use the notion of individual stability.
  As a reminder, the Price of Anarchy (PoA) is the ratio between the worst (highest-cost) stable arrangement and the best (lowest-cost) arrangement. The Price of Stability is the ratio of the best stable arrangement and the best overall arrangement (regardless of if it is stable or not) (Anshelevich et al. [2008]). Note that the Price of Stability is 1 when there exists an optimal arrangement that is also stable.
  First, we will show that for certain ranges of parameter space, the Price of Anarchy and/or Price of Stability are equal to 1. Specifically, Lemma 10 shows that when all players have relatively few samples (no more than µe 2 each), the grand coalition ⇡g is core stable, implying a Price of (Core) Stability of 1. Recall that µe and 2 are parameters of the federated learning model reflecting the average noise of the data and the average dissimilarity between federating agents, respectively. Lemma 10. For a set of players with ni  µe 2 8i, the grand coalition ⇡g is always core stable.
  On the other hand, Lemma 11 shows that when all players have relatively many samples (at least µe 2 each), every core or individually stable arrangement is also optimal, which means that the Price of Anarchy for this situation is 1.
  Lemma 11. For a set of players with ni µe 2 8i, any arrangement that is core stable or individually stable is also optimal.
  However, it is not the case that either the Price of Stability or Price of Anarchy is always 1. Table 1 contains an example demonstrating this: there exists a simple three-player case where the optimal arrangement is not individually stable. However, the Price of Anarchy value here is quite small, which suggests the prospect that the Price of Anarchy in general could be bounded.
  The main result of this section is Theorem 2, which proves a Price of Anarchy bound of 9 for this problem: the cost of the highest stable arrangement is no more than 9 times the cost of the optimal (lowest cost) arrangement. Theorem 2 (Price of Anarchy). Denote ⇧M to be a maximum-cost individually stable (IS) partition and ⇧opt to be an optimal (lowest-cost) partition. Then,
  PoA = fw(⇧M )
  fw(⇧opt)  9
  In Theorem 2, the numerator is the cost of ⇧M , a maximum-cost partition, and the denominator is ⇧opt, an optimal (lowest-cost) partition. Recall that Definition 1 gives the cost of an arrangement as the weighted sum of the errors of the respective players. Therefore, to get an upper bound on the Price of Anarchy, we will upper bound the errors players experience in ⇧M and lower bound on the error players experience in ⇧opt.
  Summary of proof technique Again, this section will show how the larger theorem is the result of several lemmas that act as building blocks. In particular, the lemmas will take two separate approaches towards creating the bound. Lemmas of the first type (12, 13, 14) all provide upper or lower bounds on the errors certain players can experience. These conditions depend on the size of the player (how many samples it has) and the size of the group it is federating with (how many samples in total the rest of the coalition has). For example, Lemmas 12 and 13 taken together show that a player with at least µe+ 2
  2 2 samples has a worst-case error no more than 2 times its best-case error. The same pair of lemmas give a multiplicative bound of 9 for players with numbers of samples that falls between µe9· 2 and µe+ 2
  2 2 . Finally, Lemmas 14 and 13 together give a factor of 7.5 for players with fewer than µe9· 2 samples that are federating with other players of total size at least µe
  3· 2 . Taken together, these errors show that, for almost all cases, the highest error a player experiences is no more than 9 times higher than the lowest error it might experience.
  The final case that needs to be addressed is when a player of size  µe9· 2 is federating in a group with other players of total size  µe3· 2 . Lemma 15 handles this last case by an argument around stability. Specifically, it shows that any players in such an arrangement can only be stable if all of them are grouped together into a single federating coalition. In the proof of Theorem 2, this result ends up enabling an additive factor to the Price of Anarchy bound, which is absorbed into the other factors for a total Price of Anarchy value of 9.
  Statement and description of supporting lemmas Next, we will walk through each lemma specifically. Lemma 12 gives an upper bound of µe
  ni on the error any player experiences in ⇧M .
  Lemma 12. If ⇧M is a maximum-cost IS partition, then erri(⇧M )  µeni for all players i.
  Proof. Because ⇧M is individually stable, every player must get error no more than the error it would receive alone (doing local learning). By Lemma 1 with C = ni, a player with samples ni player gets error µe
  ni alone.
  Next, Lemma 13 provides lower bounds on the error a player can receive in ⇧opt. It does this by bounding the minimum error a player could get in any arrangement. Again, because the cost of ⇧opt is simply the weighted sum of errors of each individual player, this helps to upper bound the Price of Anarchy. First, Lemma 13 shows that for players with at least µe+ 2
  2 2 samples, the lowest possible error it could experience is 12 · µe nj , which is a factor of 2 off from its worst-case error in Lemma 12. For players with fewer samples than µe+ 2
  2 2 , Lemma 13 says that the lowest error a player
  could experience is 2. This means that the ratio between the two errors is lower than 9 so long as nj µe9· 2 . Therefore, in order to get a factor of 9 bound for the overall Price of Anarchy, we need to handle the case of players with size  µe9· 2 , when players have very few samples. Lemma 13. Consider a player nj and any set of players C. Then, we can lower bound the error player j recieves by federating with C:
  errj(C [ {nj}) ( 1 2 · µe nj nj µe+ 2 2 2
  2 otherwise
  Lemma 14 is the first of two lemmas handling the case of players with very few samples. It shows that, if a player of size  µe3· 2 is federating with a set of players of total size at least µe
  3· 2 , it is possible to upper bound on the error of players in ⇧M by 7.5 · 2. Given the lower bound of 2 in Lemma 13, these together show that there is a ratio of 7.5 at most between the error this player experiences in its best and worst-case arrangements. Lemma 14. Consider a player j federating with a coalition C. If the total number of samples NC is at least µe3 2 , then errj(C [ {nj})  7.25 · 2.
  However, Lemma 14 does not handle one situation: what if a player of size  µe9· 2 is federating with a group of players of total size  µe3· 2 ? Lemma 15 addresses this last case: it shows that the only such arrangement that is stable is one where all such players are grouped together into a single arrangement. Note that this lemma is itself should not be obvious: it is composed of multiple sub-lemmas which are stated and proved in the appendix. The fact that there can be only one group of such players is used in the Theorem 2 to create an overall bound of 9. Lemma 15. Consider an arrangement of players, all of size  µe3 2 , where at least one player is in a federating cluster where the total mass of its partners is no more than µe3 2 . Then, the only stable arrangement of these players is to have all of them federating together.
  The full proof of Theorem 2 uses these lemmas collectively in order to get an overall Price of Anarchy bound of 9, showing that the worst individually stable arrangement has total cost no more than 9 times the optimal cost.
sections.heading: 6 Conclusion
sections.text: In this work, we have given the first Price of Anarchy bound for a game-theoretic model of federated learning. This bound quantifies a key tension between individual incentives and overall societal goals, answering a key question left open in prior literature. Beyond this bound, we also provide an efficient algorithm to calculate an optimal partition of players into federating coalitions, and have characterized conditions where the Price of Anarchy and/or Price of Stability is equal to 1.
  There are multiple fascinating extensions to this work. To begin with, other definitions of societal cost (for example, weighting players’ errors differently) could produce different Price of Anarchy bounds. Additionally, further work could model more sophisticated methods of federation, including models of domain adaptation. Finally, it would be interesting to explore other notions of societal interest. For example, one vein of research is fairness: how are error rates divided among federating players? Questions might revolve around the maximum gap in error rates between players and whether players that contribute more samples are always rewarded with lower error. Beyond these avenues, though, we believe that the broad topic of federated learning will continue to contain multiple useful and interesting research directions.
sections.heading: 7 Ethics and societal impact
sections.text: Given this work’s focus defining notions of optimality, there are important ethical considerations. In particular, “optimality” can be defined in multiple different ways: Section 4 motivates the definition we use and Appendix A discusses the merits of other definitions. In particular, it is worth emphasizing that “optimality” is a technical term in optimization and game theory which is always with respect to a given objective function and does not imply a more holistic notion of how desirable a certain solution is. For example, an arrangement could be “optimal” and still be unfair in how errors are distributed among players.
  Although our methodology is application-agnostic, federated learning is a machine learning tool that could be applied towards positive goals (e.g. predicting patient outcomes at hospitals) or negative goals (e.g. used to surveil and control populations). It is also worth considering, for each application, whether there could be some other approach that would better address the need. For example, it may be worth considering whether approaches aiming at increasing the number of samples available for low-resource agents would do a better job of increasing the benefit of a federated learning solution. It may even be the case that a solution beyond machine learning would be preferable, such as interventions to reduce the need for a predictive model.
  Acknowledgments and Disclosure of Funding
  This work was supported in part by a Simons Investigator Award, a Vannevar Bush Faculty Fellowship, MURI grant W911NF-19-0217, AFOSR grant FA9550-19-1-0183, ARO grant W911NF19-1-0057, a Simons Collaboration grant, a grant from the MacArthur Foundation, and NSF grant DGE-1650441. We are grateful to the AI, Policy, and Practice working group at Cornell for invaluable discussions.
title: Optimality and Stability in Federated Learning: A Game-theoretic Approach