Optimality and Stability in Federated Learning: A Game-theoretic Approach
Authors: Kate Donahue
Jon Kleinberg
Venue: NeurIPS 2021 Poster (2021)
Keywords: Price of Anarchy
Price of Stability
cooperative game theory
hedonic game theory
federated learning

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

Optimality and Stability in Federated Learning:
A Game-theoretic Approach
Kate Donahue
Jon Kleinberg
Department of Computer Science
Departments of Computer Science and Information Science
Cornell University
kdonahue@cs.
cornell. kdonahue@cs.ccrmeel..comm
Coreell University kleinber&cs. cornell. cornelll edu
Abstract
Federated learning is distributed learning paradigm where multiple agents, each only with access to local data, jointly learn 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 total error. One branch of this research has taken a game-theoretic approach, and in particular, prior work has viewed federated learning error-minimizing players arrange themselves into federating coalitions. This past work proves the existence of stable coalition partitions, but leaves open wide range of questions, including how far from optimal these stable solutions are. In this work, motivate and define notion of optimality given by the average error rates among federating agents (players). First, we provide and prove the correctness of an efficient algorithm calculate an optimal (error minimizing) arrangement of players. Next, we analyze the relationship between the stability and optimality 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 higher than 9 times the total error an optimal solution (Price of Anarchy bound 9).
hedonic game, where
Introduction
Recent advances machine learning techniques has made it possible to apply powerful prediction algorithms to 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 student educational data at different schools. In each case, the individual agents (hospitals or schools) who hold the data wish to find model that minimizes their error. However, the data each location may be insufficient to train 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 produce model with much higher accuracy, providing more powerful predictions to each agent and increasing overall welfare. However, it may be infeasible transfer the data some coordinating entity to build global model: privacy, data size, and data format are all possible reasons that would make transferring data not a reasonable solution.
Federated learning is novel distributed learning paradigm that aims solve this problem McMMahan et al. 2016)). Data remains at separate local sites, which individual agents use to learn local model parameters parameter updates. Then, only the parameters are transferred to the coordinating entity
35th Conference on Neural Information Processing Systems (NcurIPS 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 a rapidly growing area of research (Li et al. 2020 Kairouz et al. 2019 Lim et al. (020
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]. [Baddasaryan and Shmatikov 2011)) Li et al. [2019) Mohri 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 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. Simultancously, every other agent also attempting to identify and join federating group that it prefers- and agents may have conflicting preferences. Prior work (Donahue and Kleinberg [202T] Hasan [202T] has formulated this problem as 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 '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 reduce their error, society whole also has 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 's overall cost falls under the game theoretic notion of optimality.
One natural question relates to the tension between these two goals: the self- eeff-interested goal of the individual actors (stability) and the overall goal of reducing total cost (optimality). Given 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 game, the canonical approach to study optimality and stability jointly (Papadimitriou (200T). 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 I, 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 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 address this gap. First, we provide an efficient, constructive algorithm for calculating an optimal federating arrangement. Secondly, we prove the first-ever constant bound 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 [ optimality and stability are not always simultancously 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, 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 our proof 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 gi github. com/kpdonahue hwrtoonaaueemoodeeeaeaeeee ltwdemoshariineeeeeeeeaaeeeeeeee
2 Related work
Federated learning As we mentioned previously, federated learning has recently seen numerous advances. In this section, we highlight 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) commonly acknowledged in the federated learning literature. For example. Yu et al. 22200] [Badaasarynn and Shmatikov [2019] empirically demonstrate that federated learning, and especially privacy-related additions, can cause 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. 20200). Many other works also relate to clustering, such as (Lee et al. [2020] Sattler et al. 22020. SShlezinger et al. (2020), (022]). ). Nagalapatti and
Wang et al. 2020]] Duan al.) Jamali- Rad et al. 1021]. Caldarola et al.
Narayanam [221] 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 known, such as the data distribution at each location.
Other work aims to improve accuracy rates by selecting acquiring additional data BBlum et al. 2017 Duan 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. [021] Kumar et all [021] Zhang et al. 202T)). )). 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 prior paper Donahue and Kleinberg (021]. which we discuss in greater detail in Section S Another paper using hedonic game theory to analyze federated learning games is Hasan (02T which gives conditions for Nash stability in federated learning. Other works analyze the incentives of players to contribute resources towards federated learning: Blum al. [202T] analyzes fairness and efficiency in sampling additional points for federated learning and Le et al. [[02]] analyzes incentives for agents to contribute computational resources in federated learning. Interestingly, multiple works take game theoretic approach towards coalition formation in cloud computing, but with the aim of minimizing some cost besides error, such electricity usage Guazzone al. [2014]. Anglano al. (0188
Model and assumptions
We assume that there are M total agents (sometimes referred as players). Each agent i e [M]] has drawn n, data points from their true local distribution ((t), where 0; are their true local parameters and g(-) is some true labeling function. A player's goal is to learn model with low expected error on its own distribution. If player opts for local learning, then it uses its local estimate of these parameters g(O,) to predict future data points, obtaining eтror err,(fi)) 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 single federated estimate, governed by the weighted average of their parameters:
Ôc Eieo T4
-.n.. Em.. iEC
(1)
A federating player obtains error (Cr: note that this value may differ between players in the same coalition. For example, if player j has more samples than player k; then Oc will be weighted more towards player j, meaning that player j will have lower expected error than k.
3

---

The weighted average method in Equation iss commonly used in federated learning McMahan et al. (2016). Because it 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, DDnnhuue and Kleinberg [202T] 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 D in this work. First of all, this federation method is the most straightforward method, and as such it is the natural candidate 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: reduces the tension between an individual's 's incentives and the optimal overall arrangement. Because of this, for Price of Anarchy it is more valuable and challenging to where incentives are more opposed.
explore the case in Equation |
3.1 Theoretical model of federation from Donahue and Kleinberg 2021
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 be feasible, we need model that gives exact errors (costs) for each player, rather than bounds: these are needed in order to be able to argue that certain arrangement is optimal, for example.
We opt to use the model developed in our prior work Donahue and Kleinberg 2021 the closed-form eπror value seen in Lemma below. While we work within this model, emphasize that Donahue and Kleinberg [021] asked different questions from this paper's 's focus: our prior work focused developing the federated learning model and analyzing the stability of federating coalitions, while our current work analyzes optimality and Price of Anarchy.
which produces
Lemma 1 (Lemma 4.2, from Donahue and Kleinberg (2021)). Consider mean estimation task as follows: player is trying to learn its true mean 0z. It has access to nj samples drawn i.i.d. Y ~ (,) a distribution with mean 83 and variance e7 Given a population of players, each has drawn parameters (0,, 2]) ~ θ from some common distribution θ, A coalition C' federating together produces single model based on the weighted average of local means (Eq. D Then, the expected mean squared error player experiences in coalition C is:
Eiec, n2 + (Erec.sA) m1)
(C)
Pe Eiec ni
+ 0²
Ti)
where He = - (et) (the average noise in data sampling) and 0² = Var(0:) (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 Donahue and Kleinberg 2021]. For example, we use C' to refer to a coalition of federating agents and II to refer to a collection of coalitions that partitions the M agents. We will use No to refer to the total number of samples present in coalition C: Nc = Eigo ns. 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 {n,) is fixed and known by all. We also assume that the parameters Me, o² He, are approximately known: in particular, results will depend on whether the number of samples is larger or smaller than the critical threshold H.. We assume that player does not know anything else about its true parameters 0, the parameters of other players: for example, 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 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 [202T]. The focus of Donahue and Kleinberg [202] 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
4

---

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 Klembber [02T] only allow players 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 function of the questions analyzed in each paper: questions of stability (as in Donahue and Kleinberg [021] are much harder to analyze for players with arbitrarily many different sizes.
Optimality
We will begin with the question of optimality. As motivation, it is useful consider the objective function of most federated learning papers McMahan el al. [016]:
M
M
min wr (0)
Σ 1=1
Pi (0); (0)= E 2i=1 1=1
(
While the weights can be any > O, E P: = 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 IT is optimal if it minimizes the weighted sum of errors across players, as defined below:
(1I) E (C) = Σ> (Crr(C)
CEn
CENIEC
We will say that coalition partition II is in OPT if it achieves minimal cost. Note that multiple partitions may achieve minimal cost, so OPT a set of partitions.
Because II is disjoint partition the M players, fw (II) is simply the (f) scaled by constant. Therefore, minimizing fw (II) 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 al. 2019 Mohri et al. [2099] 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 below, gives the specific form of cost for federated learning using the model from Donahue and Kleinberg (202T).
The remaining analysis in this paper will assume this cost function. Proots for results in this section are given in Appendix B
Lemma 2. Consider a partition II made up of coalitions {C.). Then, using the error form given in Equation the total cost of II is given by
Me 02 2 No 0² Eiec n
fw
Σ CEN
No
The two most common arrangements machine learning tasks are local learning (which we will denote by at) and the federation in the grand coalition (xg). where all of the players are federating together single coalition. However, Lemmas S and demonstrate that either of these could perform arbitrarily poorly as compared the cost-minimizing (optimal) arrangement.
Lemma 3. Vp 1, there exists a setting where local learning results in average error more than {=(m)
times higher than optimal: [OPT] p.
Lemma 4. Vp 1, there exists a setting where federating in the grand coalition results in average (G))
error more than p times higher than optimal: (=(OPT) p.
priori, finding a partition 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 arbitrarily far from optimal. However, the next section will provide an efficient, constructive algorithm to calculate optimal partition of players into federating coalitions.
5

---

4.1 Calculating an optimal arrangement
The main contribution of this section is Theorem which gives an algorithm for minimizing the total weighted error of the federating agents.
Theorem 1. Consider a set of players {ne). 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 II is optimal.
Though the algorithm in Theorem Jis straightforward, proving the optimality the resulting partition Il requires several sub-lemmas, Each sub-lemma is a building- -boiing--bokkk--- that describes certain operations that either increase or decrease total cost. The proof of Theorem [ largely consists sequentially using these sub-lemmas in order to demonstrate the optimality of the calculated partition.
Statement and description of supporting lemmas First, Lemma demonstrates a close relation- ship between movements of players that reduce total cost and movements of players that in that player's ss self-interest (recall that players always wish to minimize their expected error). Specifically, it shows that player wishes to join coalition from local learning if and only if that move would reduce total cost for the entire partition.
Lemma (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 (tm,))) + (w) 2 fu((nz)UQ) + erry((n,)) (trr((t))
Next, Lemma 6 shows that "swapping" the roles of two players (one doing local learning, one federating a coalition) reduces total cost when the larger player is removed to local learning.
Lemma (Swapping). Take any Q including player nz > nu. where the player ny is doing local learning. Then, swapping the roles of players ls and j always decreases total cost.
[w U (nz)) ((ma)) [n {mx)) (fa)))+ ((n())))
Lemmas 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 not.
Lemma (Monotonicity of joining). If a player of size n, would prefer local learning to joining a coalition Q, then any player of size nu n. also prefers local learning to joining the same coalition. That is, for ni 2 Ttj.
err (n₂)) 2 erry((ng))
erri(Qu (ma)) 2 erra((ru3)
Conversely, if a player wishes to join Q, then any other player of size ni S ny would have also wanted to join. That is, for nj 2 nig
err,(Qu (n²}) S err,(ing))
+ errs(Quu (nc)) S erra((nx))
Lemma 8 (Monotonicity of leaving). Take any coalition Q Then, if any player Q of size n. wishes to leave Q for local learning, then any player of size ni 2 ni also wishes to leave for local learning. That is, for Tu Z n
err, (Q) 2 err,((nn)))
errx(Q) 2 erra((ng))
Conversely, if player j Q of size nj does not wish leave Q for local learning, then any player k E Q of size ny S nj also does not wish to leave. That is, for ni S nz
(rr,(Q) err,(tn,))
( I crrx(fnu))
All the above lemmas have analyzed situations where a single player is moving between coalitions. I 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 reduce total cost.

---

Coalition structure
erTa (+),
erro(-), nb 8
eTT (7Te()),,
n0
15
(1I
errw (II)
1a. [b..(c) [ct
I0
1.25
0.667
30
1.25
{a), [b
10
1.285
0.677
30.435
1.268
[a,c), {b}
2.382
1.25
0.633
21.875
0.911
[a, (1,bb.ie ic}
2.691
1.136
0,667
21.778
0.907
{a, b,
1.834
I.253
0.670
21.917
0,913
Table 1: Example with pe. = 10, o² example with three players of size n, = 1,ng, = 8, n. = 15.
Note that {a,b) {e} minimizes total cost, but is not individually stable: player wishes to leave its coalition to join player e, which welcomes that player joining it. This produces {a,c), (b), which is the only individually stable arrangement, giving Price of Anarchy value of 21.875/21.771
1.0045.
Lemma 9 (Merging). Consider two groups of players, Q. First, merge together the two groups to form PUQ. Then, remove players from P PUQ Q to local learning. removing them descending order of size. Stop removing players when the first player would prefer to stay (removing would increase its error). Then, this overall process maintains or decreases total error. In other words,
(c(Q)+ fo Emu((n))
(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 the first, up to renaming of players, and is not the case that all the players have the exact same size.
The proof of Theorem D given simply by applying the lemmas sequentially to show that any other partition II' can be converted to the described partition through a series of operations that decrease or hold constant total cost.
5 Price of Anarchy
The previous section defined the "optimality" of 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 202T] Hasan 202T] 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 proof's for this section in Appendix C
First, 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 11 is core stable there does not exist a set of players that all would prefer leave their location in II and form a coalition together. A partition is individually stable (IS) if there does not exist single player i that wishes to join some existing coalition C, where all members of C' weakly prefer that 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 is stable not) (Anshelevich et al. (2008] ). Note that the Price of Stability is 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 f each), the grand coalition Tg is core stable, implying a Price of (Core) Stability of 1. Recall that He and o² 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 n, S He Vi, the grand coalition Tg is always core stable.
On the other hand, Lemma 11 shows that when all players have relatively many samples (at least Ais each), every core or individually stable arrangement is also optimal, which means that the Price of Anarchy for this situation is I.
7

---

Lemma 11. For a set of players with n, 2 be Vi, 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 ! 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 1I to be a maximum-cost individually stable (IS) partition and copt to be an optimal (lowest-cost) partition. Then,
fu((IM)
Pod
La (Hopp)
In Theorem the numerator is the cost of IIM, a maximum-cost partition, and the denominator is Hopp. an optimal (lowest-cost) partition. Recall that Definition D 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 II and lower bound on the error players experience Hopt.
Summary of proof technique Again, this section will show how the larger theorem is the result of several lemmas that act as building blocks. particular, the lemmas will take two separate approaches towards creating the bound. Lemmas of the first type lower bounds on the errors certain players can experience. These conditions depend on the size 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 3 taken together show that a
all provide upper or
20 samples has a worst-case error no more than 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 9:07 and Peto²
player with at least Meto²
20t Finally, Lemmas and 13 together give a factor of 7.5 for players with fewer than I samples that are federating with other players of total size at least 3,57 Taken together, these errors show that, for almost all cases, the highest error player experiences is more than times higher than the lowest error it might experience.
ite
The final case that needs to be addressed is when player of size < 9 is federating in a group with other players of total size S 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 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 specif- ically. Lemma 12 gives an upper bound of Pe on the error any player experiences in aa
Lemma 12. If 11 is a maximum-cost IS partition, then err, (11 Ue for all players i. ns
Proof. Because IIM is individually stable, every player must get error no more than the error it would receive alone (doing local learning). By Lemma [ with C' = n4, a player with samples n, player gets error Me alone. ng
Next, Lemma 13 provides lower bounds on the error a player can receive in Nopt- It does this by bounding the minimum error a player could get in any arrangement. Again, because the cost of Hopt 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 Muto" samples, the lowest possible error could experience Hy. which a factor of 2 off from its worst-case error in
Lemma 12
For players with fewer samples than M=to² 2
Lemma
13 says that the lowest error player
8

---

could experience is o². This means that the ratio between the two errors is lower than 9 so long as nj 2 Ne_.. Therefore, in order get a factor of bound for the overall Price of Anarchy, we need to 9igz handle the case of players with size I 3zzz. when players have very few samples.
Lemma 13. Consider a player n and any set of players C. Then, we can lower bound the error player j recieves by federating with C:
1 nj
(rr,(CU(ng)))
n
0²
otherwise
Lemma 14 is the first of two lemmas handling the case of players with very few samples. It shows that, if player size S 3 is federating with a set of players of total size at least _e it possible to upper bound on the error players in Ha by 7.5 o². Given the lower bound of o in Lemma I3 these together show that there is ratio of 7.5 at most between the error this player experiences in its best and worst-case arrangements.
Lemma 14. Consider player j federating with coalition C. the total number of samples Ne is at least 3 then err,(CU {mz})= S 7.25 o².
Pe
However, Lemma 14 does not handle one situation: what if a player of size S 9.0" is federating with a group of players of total size I s/z²? ? Lemma 15] addresses this last case: shows that the only such arrangement that is stable is where all such players are grouped together into 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 the Theorem
2 to create an overall bound of 9.
Lemma 15. Consider arrangement of players, all of size S Sr. where at least player is in a federating cluster where the total mass of its partners is no more than the Then, the only stable arrangement of these players is to have all of them federating together.
The full proof of Theorem 2 uuees 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.
Conclusion
In this work, we have given the first Price of Anarchy bound for a game-theoretic model of federated learning. This bound quantifies key tension between individual incentives and overall societal goals, answering 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 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 eтror 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.
Ethics and societal impact
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 motivates the definition we use and Appendix discusses the merits of other definitions. In particular, it is worth emphasizing that "optimality"" a technical term in optimization and game theory which is always with respect to given objective function and does not imply more holistic notion of how desirable a certain solution is. For example, an arrangement could "optimal" and still be unfair in how errors are distributed among players.

---

Although our methodology is auplicatiin-agnostiee federated learning is 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, 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 solution beyond machine learning would be preferable, such as interventions to reduce the need for predictive model.
Acknowledgments and Disclosure of Funding
This work was supported in part by Simons Investigator Award, a Vannevar Bush Faculty Fellowship, MURI grant W91 INF-19-0217, AFOSR grant FA9550-19-1-0183, ARO grant W91 INF19-1-0007 a Simons Collaboration grant, a grant from the MacArthur Foundation, and NSF grant We are grateful to the AI, Policy, and Practice working group at Cornell for invaluable discussions.
References
C. Anglano, M. Canonico, Paolo Castagno, Marco Guazzone, and M. Sereno. A game-theoretic approach coalition formation in fog provider federations. 2018 Third International Conference on Fog and Mobile Edge Computing (FMEC), pages 123-130, 2018
Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, léva Tardos, Tom Wexler, and Tim Rough- garden. The price of stability for network design with fair cost allocation. SIAM Journal on Computing, 3804)11602-1623, 2008
Eugene Bagdasaryan and Vitaly Shmatikov. Differential privacy has disparate impact on model accuracy, 2019.
Avrim Blum, Nika Haghtalab, Ariel D Procaccia, and Mingda Qiao. Collaborative pac learning. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, edi- tors, Advances in Neural Information Processing Systems 30, pages 2392-2401. Curran Associates, Inc., 2017. URL httt:://papers.ntt httppp..ccpppe///33llolbbaaeeeee pdf
Avrim Blum, Nika Haghtalab, Richard Lanas Phillips, and Han Shao. One for one, or all for all: Equilibria and optimality of collaboration in federated learning. arXiv preprint axXv:2103.03322) 2021.
Anna Bogomolnaia and Matthew O. Jackson. The stability of hedonic coalition structures. Games
and Economic Behavior, 38(2):201 230, 2002. ISSN 0899-8256. doi: https///oi.orr/ 10. www110006game..emm 2001.0877. URL http: /www.w http::/www.ccienceeeee......ee www.siceiieeet......./. http:///w....eeeccccceeerrreeeee
50899825601908779
Debora Caldarola, Massimiliano Mancini, Fabio Galasso, Marco Ciccone, Emanuele Rodolå, and Barbara Caputo. Cluster-driven graph federated learning over multiple domains. arXiv preprint 1.Xx::2004.1468, 2021.
Shengbo Chen, Cong Shen, Lanxue Zhang, and Yuanmin Tang. Dynamic aggregation for hetero- geneous quantization in federated learning. IEEE Transactions on Wireless Communications, 2021.
Kate Donahue and Jon Kleinberg. Model-sharing games: Analyzing federated learning under voluntary participation. AAAI 2021, 2021. URL http:::://axxivoor///a// 00753
M. Duan, Liu, X. Chen, R. Liu, Y. Tan, and L. Liang. Self-balancing federated learning with global imbalanced data in mobile systems. IEEE Transactions on Parallel and Distributed Systems, 32(1):59-71, 2021.
Moming Duan, Duo Liu, Xinyuan Ji, Renping Liu, Liang Liang, Xianzhang Chen, and Yujuan Tan. Fedgroup: Efficient clustered federated learning via decomposed data-driven measure.
10

---

Marco Guazzone, Cosimo Anglano, and Matteo Sereno. A game-theoretic approach to coalition formation in green cloud federations. 2014 14th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, May 2014. doi: 10.1 10. 109. URL http://da doi
prg/10.1 1109/ /tt09//Crri.... 2014.37
Pengfei Guo, Puyang Wang, Jinyuan Zhou, Shanshan Jiang, and Vishal M Patel. collaborations for improving deep learning-bas based magnetic resonance image reconstruction using federated learning. arXiv preprini arXiv:2103.022 048, 2021.
Cengis Hasan, Incentive mechanism design for federated learning: Hedonic game approach, 2021.
Hadi Jamali-Rad, Mohammad Abdizadeh, and Attila Szabo. Federated learning with taskonomy for non-iid data. arXiv preprint arXiv:2103.
2021.
Peter Kairouz, H. Brendan McMaaan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Salim EI Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo. Tanerède Lepoint, Yang Liu, Prateek Mittal, Mchryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi. Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning, 2019.
Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In Annual Symposium on Theoretical Aspects of Computer Science, pages 404-413 Springer, 1999.
Rajesh Kumar, Abdullah Aman Khan, Jay Kumar, A Zakria, Noorbakhsh Amiri Golilarz, Simin Zhang, Yang Ting. Chengyu Zheng, and WenYong Wang. fbockchain-federattelllee learning models for covid-19 detection using imaging. IEEE Sensors Journal, 2021.
and deep
Yassine Laguel, Krishna Pillutla, Jerôme Malick, and Zaid Harchaoui. A superquantile approach to federated learning with heterogeneous devices. In 2021 55th Annual Conference on Information Sciences and Systems (CISS), pages 1-6. IEEE, 2021.
Tra Huong Thi Le, Nguyen H. Tran, Yan Kyaw Tun, Minh N. H. Nguyen, Shashi Raj Pandey, Zhu Han, and Choong Seon Hong. An incentive mechanism for federated learning in wireless cellular network: An auction approach. IEEE Transactions Wireless Communications, pages 1-1, 2021.
doi: 10. 11.11199/111 10.100/9...2221336627777
J. Lee, Jaehoon Oh, Yooju Shin, and S. Yoon. Accurate and fast federated learning via iid and communication-awan grouping. ArXiv, abs/2012.0450 2020.
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning, 2019.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. JEEE Signal Processing Magazine, 37(3):50 60, May 2020. ISSN 1558-0792. doi: 10. 20..00///pp.222229754444 URL http: //dx dww. 1ttg://.0.119915551 2020 29757749
W. Y. B. Lim, N. C. Luong. D. T. Hoang, Y. Jiao, Y. C. Liang, Q. Yang, D. Niyato, and C. Miao. Federated learning in mobile edge networks: A comprehensive survey, IEEE Communications Surveys Tutorials, 22(3):20312000
2020. doi: 10. 10.1009/CMMST.2222298666
Tao Lin, Sebastian U. Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local sgd, 2018
Lumin Liu, Jun Zhang, S.H. Song, and Khaled B. Letaief. Client-edge-clouud hierarchical federated learning. ICC 2020 2020 IEEE International Conference on Communicattions (ICC), Jun 2020. doi: 10. 1 10911/9//44277..0000..033
URL http:// //dxx doi wtg/10gg///oo 10w.:/..111iiccc htw.110000/1111771... 2020
9148862

---

H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera Arcas. Communication-efite learning deep networks from decentralized data, 2016.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning, 2019.
Lokesh Nagalapatti and Ramasuri Narayanam. Game of gradients: Mitigating irrelevant clients in federated learning. Proceedings of the AAAI Conference Artificial Intelligence, 35(10))9046- 9054, May 2021. URL https://ojje aaai caaai.or///aaaa pwrg/index.or php http://AAAarttilleeee/a////////
Christos Papadimitriou. Algorithms, games, and the internet. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 749-753, 2001.
Felix Sattler, Klaus-Robert Muller, and Wojeiech Samek. Clustered federated learning: Model- agnostic distributed multitask optimization under privacy constraints. IEEE Transactions on Neural Networks and Learning Systems, page 1-13, 2020. ISSN 2162-2388. doi: 10. 10.1109ttnns. 2020.3015958. URL http:ttp://ee //dx doi owo.rog//// 10. 1109/ 1109/TNNLS. TNNLS. 2020 3015958
N. Shlezinger, S. Rini, and Y. C. Eldar. The communication-avye aware clustered federated learning problem. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 2610-2615, 2020.
Akhil Vaid, Suraj K Jaladanki, Jie Xu, Shelly Teng, Arvind Kumar, Samuel Lee, Sulaiman Somani, Ishan Paranjpe, Jessica K De Freitas, Tingyi Wanyan, et al. Federated learning of electronic health records to improve mortality prediction in hospitalized patients with covid-19: Machine learning approach. JMIR medical informatics, 9()):244277 2021.
Hao Wang, Hsiang Hsu, Mario Diaz, and Flavio P. Calmon. To split or not to split: The impact of disparate treatment in classification, 2020.
Yingda Xia, Dong Yang. Wenqi Li, Andriy Myronenko, Daguang Xu, Hirofumi Obinata, Hitoshi Mori, Peng An, Stephanie Harmon, Evrim Turkbey, et al. Auto-fedavg: Learnale federated averaging for multi-institutional medical image segmentation. arXiv preprint arXiv:2104.10195, 2021.
Tao Yu, Eugene Bagdasaryan, and Vitaly Shmatikov. Salvaging federated learning by local adaptation, 2020.
Weishan Zhang. Tao Zhou, Qinghua Lu, Xiao Wang, Chunsheng Zhu, Haoyun Sun, Zhipeng Wang, Sin Kit Lo, and Yue Wang. Dynamic fusion-based federated learning for covid 19 detection. IEEE Internet of Things Journal, 2021.
12


Reviews:
[{"review_id": "zA0eIPYDmz5", "reviewer": "Reviewer_cBBM", "summary": "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:\n1. proposing an optimal algorithm to minimize the weighted sum of errors;\n2. providing the upper bound on PoA.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The task and the methods are new. The paper provides an optimal algorithm and an upper bound on PoA, which have not been studied before.\n\nQuality: The submission is technically sound. All claims are well supported.\n\nClarity: The writing is clear. But some important notions should be addressed more formally, e.g., core stable and individually stable. It would be better if both notions could be defined mathematically. Besides, in line 261, the authors states \"all members of $C$ weakly prefer...\", where I don't understand what \"weakly\" means here. \n\nSignificance: The paper studies an interesting problem on the stable coalition in federated learning. \nIt looks like this paper only discusses the results of the mean estimation problem. In this specific task,  the error has a closed-form solution, which makes the analysis easier than that in a more general task. But it is still a good first step towards analyzing a more general problem. The results are important.  The paper provides an elegant algorithm achieving optimality and shows that PoA w.r.t. individually stability is upper bounded by 9.\n\nOther comments:\n1. The paper mentions that it focuses on mean estimation game in Line 163. If this submission only focuses on the mean estimation task, this should be addressed earlier, including the abstract, intro and even the title, as the paper does not study the general problem of federated learning.\n2. Typo: In line 131, it should be \" if agent $j$ has \\emph{more} samples than ...\"\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "uComn0tdRi0", "reviewer": "Reviewer_WHyG", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper presented some interesting and novel results. The topic about incentives in federated learning also looks important for this research area and is likely to inspire new ideas. \n\nThe paper is well-written. The presentation is mostly clear and the results look sound (though I didn't check details in the appendix). \n\nOne question I have is about the emptiness of the core: Does a core (or individual) stable arrangement always exist? If this is not guaranteed, I wonder how meaningful the PoA bounds are.\n\nSeveral typos:\n\n- 131, Page 3, \"...if player j has samples than...\" --> if player j has more samples?\n\n- 205, Page 5, \"could could\"\n\n- 216, Page 5, there's a grammar issue.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "lKq-xx7-PgZ", "reviewer": "Reviewer_15pL", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is written in a nice way and easy to understand. The concept of price of anarchy is worth investigating in this setting as a low price means the federtion is beneficial to the welfare. The theoretic results are interesting and obtained through careful analyses (did not check all the details though). However, I am concerned with one of the fundamental assumptions of the paper. Lemma 1, which is from another paper, assumes that the parameter \\theta_j of player j is drawn from a common distribution. This paper also implicitly used the same assumption. Line 169 further assumes that n_i is fixed and known by all player. With this assumption, all players know the actual underlying data distribution and can just learn any model by simply sample enough points from this distribution. One of the implicit but fundamental assumptions of federated learning is that each player does not know the data distribution of others so they cannot get more useful data to train their own model. Can the authors provide more justifications to their modeling choice?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please refer to the main review for details.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "f3uBBNTZWlJ", "reviewer": "Reviewer_KY9P", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well-written, clear, and easy to follow. The problem studied is well-motivated from the context of federated learning and is important for practical applications. The collection of results seems novel and technically strong, and they give useful insight for real practice. The reviewer did not check all the proofs but they all look plausible in hindsight.\n\nComments:\n\n1. In line 131-132, it seems something is missing in the sentence? Do you mean \"player j has *more* or *less* samples than k\"? The reviewer wonders whether the claim that \"player j will have lower expected error than k\" is always true in either situation. Doesn't it also depend on noise and dissimilarity of the distributions?\n\n2. It seems that all the lemmas and theorems in section 4.1 highly depend on the modeling assumption, such as the notion of optimality and utility models of agents. How robust are these results? Could they be extended to more broader models?\n\n3. The reviewer finds that the contrast of PoA bounds due to sample sizes v.s. noise and dissimilarity is very interesting. Could you provide more insights about these results? It seems that the results are driven by the fact that the only difference across agents is the number of samples they have (as their distributions are drawn from the same prior). It would be interesting to see what happen if their priors are different.\n\nMinors:\n\n1. Line 56: \"leaves open\" remove one of them\n2. Line 237: Lemma 9 here?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The reviewer is curious about whether the results can be generalized to other game-theoretic models of federated learning, e.g., for different notion of optimality and utility models of agents.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "VLO3HL8xep", "reviewer": "Reviewer_2WfY", "summary": "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The problem studied in the paper is interesting, being part of a rather new research filed that is receiving a growing attention from the literature in recent years. As far as I am concerned, the Price of anarchy analysis is novel in this field.\n\nQuality: As far as I am concerned, all the proofs are correct.\n\nClarity: The paper has some major problem in the presentation. First, it is not clear from the first three sections which elements are introduced in this paper and which ones are taken from the literature. I think that re-organizing the sections so as to have one section entirely devoted to preliminaries and model definition would help improve clarity.\n\nSignificance: The approach of the paper to federated learning is mainly theoretical, I think that some more experimental analysis would be expected for a NeurIPS paper on this topic.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequate.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The rebuttals helped the Reviewers to understand better the original contributions provided in the paper. However, I have two major suggestions for the authors when producing the camera-ready version of the paper:
1. clarify better the assumptions, even those made implicitly, and clarifying them in the formal statements;
2. re-organize the first three sections to clarify which are the original contributions and which are related works, in particular it would be nice to have one section entirely devoted to preliminaries and model definition.
Decision: Accept (Poster)