Fairness in Federated Learning via Core-Stability
Authors: Bhaskar Ray Chaudhury
Linyi Li
Mintong Kang
Bo Li
Ruta Mehta
Venue: NeurIPS 2022 Accept (2022)
Keywords: Fairness
Federated Learning
Core-Stability
Social Choice

Abstract: Federated learning provides an effective paradigm to jointly optimize a model benefited from rich distributed data while protecting data privacy. Nonetheless, the heterogeneity nature of distributed data, especially in the non-IID setting, makes it challenging to define and ensure fairness among local agents. For instance, it is intuitively ``unfair" for agents with data of high quality to sacrifice their performance due to other agents with low quality data. Currently popular egalitarian and weighted equity-based fairness measures suffer from the aforementioned pitfall. In this work, we aim to formally represent this problem and address these fairness issues using concepts from co-operative game theory and social choice theory. We model the task of learning a shared predictor in the federated setting as a fair public decision making problem, and then define the notion of core-stable fairness: Given $N$ agents, there is no subset of agents $S$ that can benefit significantly by forming a coalition among themselves based on their utilities $U_N$ and $U_S$ (i.e., $ (|S|/ N) U_S \geq U_N$). Core-stable predictors are robust to low quality local data from some agents, and additionally they satisfy Proportionality (each agent gets at least $1/n$ fraction of the best utility that she can get from any predictor) and Pareto-optimality (there exists no model that can increase the utility of an agent without decreasing the utility of another), two well sought-after fairness and efficiency notions within social choice. We then propose an efficient federated learning protocol CoreFed to optimize a core stable predictor. CoreFed determines a core-stable predictor when the loss functions of the agents are convex. CoreFed also determines approximate core-stable predictors when the loss functions are not convex, like smooth neural networks. We further show the existence of core-stable predictors in more general settings using Kakutani's fixed point theorem. Finally, we empirically validate our analysis on two real-world datasets, and we show that CoreFed achieves higher core-stability fairness than FedAvg while maintaining similar accuracy. 

Fairness in Federated Learning via Core-Stability
Bhaskar Ray Chaudhury Linyi Li University of Illinois at Urbana Champaign
Ruta Mehta Mintong Kang
Bo Li
Abstract
Federated learning provides effective paradigm to jointly optimize model benefited from rich distributed data while protecting data privacy. Nonetheless, the heterogeneity nature of distributed data, especially in the non-IlI setting, makes it challenging to define and ensure fairness among local agents. For instance, it is intuitively "unfair" for agents with data of high quality sacrifice their performance due to other agents with low quality data. Currently popular egalitarian and weighted equity-based fairness measures suffer from the aforementioned pitfall. In this work, we aim to formally represent this problem and address these fairness issues using concepts from co-operative game theory and social choice theory. We model the task of learning a shared predictor in the federated setting as a fair public decision making problem, and then define the notion of core-stable fairness: Given N agents, there is no subset of agents S that can henefit significantly by forming a coalition among themselves based their utilities UN and Us (i.e., N Us 2 Un). Core-stable predictors are robust to low quality local data from some agents, and additionally they satisfy Proportionality (each agent gets at least 1 1/n fraction of the best utility that she can get from any predictor) and Parito--ptimality (there exists no model that can increase the utility of an agent without decreasing the utility of another), two well sought-after fairness and efficiency notions within social choice. We then propose an efficient federated learning protocol CoreFed optimize a core stable predictor. CoreFed determines a core-stable predictor when the loss functions of the agents convex. CoreFed also determines approximate core-stable predictors when the loss functions are not convex, like smooth neural networks. We further show the existence of core-stable predictors in more general settings using Kakutani's fixed point theorem. Finally, we empirically validate our analysis two real-world datasets, and we show that CoreFed achieves higher core-stable fairness than FedAvg while maintaining similar accuracy.
Introduction
The success of many deployed machine learning (ML) systems crucially hinges on the availability of high-quality data. However, a single entity might not own all the data it needs to train the ML model it wants; instead, valuable data instances or features might be scattered in different organizations or entities. Distributed learning schemes such as federated learning (FL) [15] provide training scheme that focuses on training a single ML model using all the data available cooperative way without moving the training data across the organizational or personal boundaries to protect data privacy.
On the other hand, given the heterogeneity in the local data distributions of different clients partici- pating in FL. it has become quite challenging to design a classifier that performs reasonably across all of them. In fact, such objective directly transfers ensuring fair performance of the classifier across all local data distributions. Therefore, fairness in FL has attracted substantial interest in the recent past 22
35
In this work, we ask: Is it possible to jointly optimize a centralized model with fairness guarantees regarding the heterogeneity of local agents? How define such fairness such that no agents would
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

intend to form an alternative coalition with a subset of agents? What could be the federated learning protocol that is able to ensure such fairness?
To address the above research questions, we bring to bear notions from game theory and social choice theory. We first observe that federated learning can be cast into public decision making, where all agents derive their respective utilities from a common global decision, namely the globally learned model. Now the goal is to make this global decision fairly. One of the fundamental fairness measures in public decision making is that of core-stability (24 Intuitively, we say that a set of agents can form a "blocking coalition" if each one of them can gain utility sigmificantly (proportional to the size of their coalition) by training a unified model amongst themselves than the globally trained model. A globally trained model core stable if there are no blocking coalitions.
We briefly justify the advantages of core-stability (a.k.a. core-stable fairness) over some of the existing notions of fairness in federated learning. Two commonly used faimess notions in federated learning are the egalitarian fairness [32 [2 7 [|5 36 25 22] and proportional fairness (6] () The
In a proportional fairness, we want the ratios of the losses of any pair of the agents to be (super/ sub) proportional to the size of their respective datasets (this incentivizes the agents share more of their data with the server). To avoid naming conflicts with our notion of proportionality, from here on, we refer to the proportional fairness introduced in [6] as weighted equity based fairness as this fairesss compares the losses of every pair of agents. Usually, fairness notions that compare the utilities/ losses of agents with each other are called equity based fairness in social choice theory. We remark that both the notions are vulnerable if some agents have poor quality datasets. In particular, if one of the agents have high levels of noise in their data, call them noisy-agent, then their loss values will tend to be higher for most learnt predictors. The egalitarian fairness and the weighted equity based faimess may be unfair to the other agents as both may make decisions aiming to reduce the large loss incurred by the noisy-agent, thereby biasing the learning towards the data of the noisy-agent. A more desirable fairness property in this scenario maybe to compare the loss percentage of agents, i.e., the ratio of the loss incurred to the maximum loss that can be incurred, or equivalently utility percentage of agents, i.e., the ratio of the utility incurred to the maximum utility that can be incurred. Core-stability achieves this, together with other desirable properties (elaborated in Section 3).
egalitarian fairness aims to maximize the utility of the least happy agen |
Our Contribution. We formally define the core-stable fairness in federated learning by appropri- ately modeling agent's utility functions to capture their learning loss error. In particular, given group of N local agents, an aggregation protocol P. and an aggregated model f. we say that the model s achieves core-stablle core-stability there are no coalition S of agents that could benefit significantly by training a model with only their data (see Definition [T]. Intuitively, this means that under a core-stable FL model, no agent has the incentive to deviate from current group and thereby obtain proportionally better aggregate utility from the final trained model. Additionally, we note that such model f will ensure sought-after guarantees of Proportionality (each agent gets 1 1/n times their best possible utility) 30 and Pareto-optimalit (there is no predictor that can increase the utility of any agent without decreasing the utility of another agent) that qqual-treatment based models 6 32 may fail to.
Core-stability is a well-sought-after but a rare-to-exist notion. In case of public goods that resembles FL, existence of core-stable outcome was known only when agent's utility functions are linear [ While the utility functions that capture learning errors are inherently non-linear and highly complex making existing results inapplicable. We summarize our contributions as below.
We formally extend core-stability from co-operative game theory to fairness in federated learning. We show that core-stability exists (in Section 4.1) as long as agent's s utility functions are continuous with respect to the model parameters, and their non-negativ conical combinations have a convex set of (local) optima. We prove this result using a fixed point formulation. In particular, we define a correspondence &: P - P on the set of all feasible predictors P. and ensure that any predictor 0* E P such that 0+ E x(00) is core-stable. Thereafter we show that & satisfies nice continuity like properties and therefore must admit a fixed point by Kakutani's 's fixed-point theorem [14.
Next, we design an effective federated learning protocol CoreFed, which optimizes the final model by maximizing the protocol of agent's 's utilitics. We prove that this protocol efficiently finds the core-stable model whenever the underlying utility functions are concave (see Section 4.2 Our protocol only needs gradient information from agents in each round.
'Equivalently maximize the minimum loss.
2

---

We prove that above method directly applies to learning through linear regression or logistic regression, since their resulting utility functions are convex (see Section 4.3). For Smooth Neural Nets (DNN), although the utility functions are (highly) non-convex, we manage to show that an approximate core-stable model can be learned within a local neighborhood (see Section (44).
To capture cases where agents may have varying importance, we extend core-stability to weighted core-stability (in Section 4.5). We show that a weighted core-stable model is weighted proportional and Pareto-optimal, and that CoreFed protocol can be generalized to Weighted CoreFed to get the desired weighted guarantees.
We conduct experiments three datasets, and show that CoreFed achieves the core-stable faimess, while maintaining similar utility with the standard FedAvg protocol (see Section
2 Related Work
Fairness in Social Choice. Faireess is one of the fundamental goals in many multi-agen settings. Over the years, motivated by applications, several notions of faimesss have been proposed and investigated. Two fairness notions that are studied in many applications are that of proportionality [30] and envy-freeness [ Proportionality requires every agent to receive their proportional share of the best outcome, i.e., least 1 /nn times their best possible utility. The notion of envy-freeness is defined in the context of resource allocation, where one aims to divide a set of items among agents fairly. In an envy-free allocation, no agent prefers the bundle of the other agent to her own. However, in public decision making, where all agents derive utility from a common global decision, this notion not applicable! In public decision making, one of the most sought out fairness notion is that of core- stre-stability [24]. Core-stabiliy, generalizes the notion of proportionality alongside other desirable properties like Pareto- optrimattt The concepts of Core-stability find applications in many other settings in social choice and game theory and is well known to exist in some special settings [3 Another popular fairness notion is equitability which states that every agent should be equally happy. i.e., the utilities/ losses of all the agents should be the same. However, as explained in 1 using relaxations of equitability, may lead to undesirable outcomes if some agents have poor data quality. Over the last seven decades, several relaxations of envy-freeness [20 26), proportionality [4 23 and cquitability [0] have been studied in computational social choice.
Fairness in Federated Learning. There have been several results on faimess in federated learning. each focusing on a particular aspect of the entire paradigm. For instance some work [12 3 aim to establish fairness at the agent selection phase, where the server requests for updates from selected subset of the agents. There are studies that aim to study fairness while training the global model
such that it does not discriminate against protected groups [34] or that the model does not overfit the data of some agents at the expense of others [19 22]. Earlier mentioned egalitarian fairness will fall under this category. Then, there are studies that consider fairness by evaluating the contribution of the agents towards training the joint model- for instance weighted equity fairness [6] does this based on the size of the data shared by the agents. Other studies assign significance to the agents based on Shapley values [29]. For a full taxanomy of fairness in federated learning, we urge the reader to
check (28). At large, most of the fairness notions are incomparable. As remarked in [6], "no one set of definitions is going to resolve the complex questions it raises".
3 Core-Stability in Federated Learning
Problem Setup. In any predictive modelling task, one would like to learn function mapping from X' C I2dd 3o C R. This includes both regression and binary classification where extension to multi- class classification is also feasible. We denote the space of such mappings as F = (Jo | 0 E P S IR)). where each fo: _d - IR is mapping function parameterized by the model weights vector 0. Our goal is to determine fo E F, such that for data sample (æ, y) drawn from the distribution P, (z) R y. ie., fz learns y well. Since we identify mapping function with each d E P. we refer to 0 as predictor for the model
Utility Functions of the Agents. The quality of predictor 0 is usually measured by the expected loss over the data distribution P, i.c., (( ÿ), where E(.))) is a prede-
Peach 0 is predictor
3

---

fined loss function. Ideally, the training process would minimize this expected loss, i.e., attain 8" arg minger [(s.))-p((f(( y). Since we are trying to determine a single predictor for several heterogeneous agents/ groups, we may not be able to give every group its best predictor. However, we want to choose the predictor that achieves fairness across all the groups. To define any notion of fairness from the classical economics literature, we need to define the utility function of a group for a predictor 0. Intuitively, the utility is a measure of how good the predictor is for the group and its data. We define,
m0))= = M - E(r.y))p (ff (fa(z),
(I)
where M is a constant more than (1 (1+ E) times the loss incurred from the worst predictor for agent i, i.e., M (1 + +) supee ((r.))/2'' ((f((z)))) The scaling by (1 E) is to avoid unnecessary
degeneracies resulting from zero utilities, and we choose & utility function is from 0 < ME to (11+e).
< 10-5. Observe that the range of the
Federated Learning and Fairness. In the federated learning setting, we are given n groups. Each group i has their loss function 40( and correspondingly urility function u,() for each choice of a predictor E P. We now define the fairnsss criterion. Recall that given n groups, our goal is to choose a f E P, such that we are fair to all the involved agents. The faimesss notion here is core-stability.
Definition (Core-Stability). predictor P. is called core stable if there exists no other O' P. and no subset of agents, such that 18] u, (0') 2 u,(0) (0) for all E S. with at least one strict inequality.
Intuitively, stre-itability implies that there is no subset of agents that can benefit "significantly" by forming a coalition among themselves, i.e., if we were to choose any other 6' E P only considering the utility functions of the agents in S S then there is some agent who's 's (multiplicatiie) gain in utility will be strictly less than a factor n/|S),i... there is no substantial benefit for this agent if she chooses belong the set S. Furthermore, core-stability gives some classical fairness and welfare guarantees. In particular, note that every agent gets at least 1/n times her best utility, i.e., the utility derived from the best possible mapping for agent i. Mathematically u, (0) 2 1/n (((') for all O' E P (setting S = {i} in Definition D. This fairness is called Proportionality [30] Formally,
Definition 2 (Proportionality). A predictor 0 E P is proportional if and only if for all 6' E P. we have (0) > (,.(") for all i E [n).
Similarly, observe that there exists no predictor 0' E P where Eiejn]
12(0] > n (setting S = [n]
in Definition D. This implies that there is no predictor that can increase the utility of some agent without decreasing the utility of another. We call this property carteto-ptimalityy Formally,
Definition 3 (Pareto-optimmlity.. A predictor 9 e P is Pareto-optimal if and only if there exists no other 0' E P. such that u, (,'(") 2 (0) for all i E [m] with at least one strict inequality.
Core is a central concept within cooperative game theory, defined to capture "no deviating sub- uub-group" property and is considered very strong. However, it is well known to exist only in special cases [BI.. We now elaborate the advantages of core-stability over some of the existing fairness concepts in federated learning.
3.1 Advantages of Core-Stability
As briefly mentioned in the introduction, core-stability is robust to low local data qualities of some agents, unlike the FedAvg or federated learning based on egalitarian or weighted equity based fairness. We elaborate this with a small example: consider three agents that contribute equal amount of data, and say agent 3 has poor data quality, i.c., there exists no proper predictor for agent 3's data, or cquivalently for all predictors low). Concretely, consider two predictors 01 and 0z. Under 02, agents and 2 incur a loss of and agent 3 incurs loss of M a (think of M as a very large integer). Now, under fg, agents and 2 have loss of 10a and agent 3 has loss of 0. Observe that fg is preferable over 0 under egalitarian fairness (as 0.9.a >>> 10a) and also by FedAvg as has a lower total average loss (0. Ma >> 9a). Similarly, a learning algorithm based on weighted equity fairness would prefer O2. as ratio of the losses between agents (or 2) and is significantly high in both 0 and 0g and lesser in 0g. However, intuitively, 0 seems fairer, agent 3 is not substantially worse off in 02 than it is in
P. the loss function of this agent very high (and utility is very

---

82 (by a factor 1.1), while agents and 2 are significantly better off in 81 (by factor 10). Note that in this example 02 a core-stable predictor, as agents and have an incentive break off and improve substantially (intuitively 02 is very unfair to them). We say that core-stable predictors are robust to low data quality of specific agents, as we never compare the losses of two agents with each other; rather our comparison is more along the lines of loss percentages, i.e., the ratio of the loss to the maximum possible loss incurred by the agent.
The robustness to poor local data quality of agents of core-stable predictors is a parallel to the property of ceale-invariance that strelstable allocations exhibit in social choice theory. In particular, scaling the utility of any single agent does not alter the core-stable allocation. Similarly, Egalitarian, utilitarian and equity based fairness suffer from being responsive scaling (3).
Core-Stability in Federated Learning
In this section, we prove the existence of core-stability under certain assumptions on the loss functions of the individual agents/ groups (Section 4.T). Then, in Section 4.2 we give a distributive training protocol CoreFed to determine core-stable predictor when the loss functions are convex"] Finally, by applying the theory developed in Sections 4.2] we show that CoreFed determines core stable predictor in Linear Regression, and in Classification with Logistic Regression (Section 4.3)
Finally, Section 4.4 we show that CoreFed determines an approximate core stable predictor in Deep Neural Networks.
4.1 Existence of Core-Stability in Federated Learning
We show that core stable predictors exist the federated setting the utility functions of the agents satisfy the following conditions:
1. The utility function of each agent is continuous.
2. The set of maximizers of any conical combination of the utility functions convex i.e., for all (01, 02 .2,,.., On) E R2 the set C = Eigjn) (0);(() is maximum is convex.
To the best of our knowledge, prior to this work, the existence of core-stability in public fair division was shown only for linear utility functions by [8). Utility functions that satisfy the above two conditions cover several other utility functions and is therefore a strict generalization of linear utility functions. We show the existence of core-stability for instances satisfying conditions and 2 above using Kakutani's ' fixed point theorem. For completeness, we state the Kakutani's 's fixed point theorem.
Definition [Kakutani's ' Fixed Point Theorem] correspondence or equivalently a set valued function o: D 2d admits fixed point, .ie., there exists a point d D, such that d E ((d), if
1. is non-empty, compact, and convex.
2. For all d E D, ((d) is non-empty, convex and compact.
3. <() has a closed graph, i.e., for all sequences (di) converging to d' and (c))een converg- ing to e*, such that d, E D and e; ((d+), we have e* E ((d").
We define a correspondence or set valued function Φ: P 2P where P is the set of all feasible predictors. In particular, for all 0 P, we set
(0) = { {dll Eie(n)
(e(d) is maximum } w.
We first observe that any fixed point of e corresponds to a core stable classifier. Lemma 4.1. Let 0 P be such that f E @(0). Then, is core-stable predictor.
The proof of Lemma 4.1 can be found in the Appendix. Now, it suffices to show that á admits a fixed point. In particular, note that the domain of P is non-empty, compact, and convex. Similarly, for
TThis the parallel to FedAvg in social choice theory. 'The assumptions made in Section 4.1 to show only existence of core-stability are weaker than the convexity assumptions in Section 4.2
5

---

every 0 E P. 6(0) is non-empty. compact, and convex. By Kakutani's 's fixed point theorem, it only remains to show that @() has a closed graph, ensure that Φ() admits a fixed point.
Lemma 4.2. The correspondence Φ() has closed graph.
The detailed proof can be found in the Appendix. Intuitively, since the utility functions are continuous over E P, also changes continuously with 0. We are
and non-zero, the optima of Σie uz(
we(d)
ready to prove the main result of this section.
Theorem 1. In any federated learning setting, where the agent's utilities are continuous and the set of maximizers of any conical combination of the agents utilities is convex, a core-stable predictor exists.
Proof Sketch. Any fixed point of Φ() corresponds to core stable predictor (Lemma 4.1 It suffices to show that Φ admits a fixed point under assumptions in Theorem To this end, note that domain P of 6() is non-empty, compact, and convex. For all 0 E P, 6(0) is convex by assumption in Theorem Finally +() has closed graph by Lemma 4.2 and thus 6() admits a fixed point.
Implications. Theorem describes the conditions under which core-stable predictors exist. We briefly state how to adapt the proofs to show the existence of locally core-stable predictors for more general utility functions. Lemmas 4.1 4.2 and Theorem I are valid even if we change the definition of ((0) to the set maximizers > E uy (,,d)/u,(0) over E =B00, r) (instead of d E P), i.e., we define @()) to be the set of maximizers in the local neighbourhood of 0 (within distance r to 0). In such a case, we only need conditions and 2 to be true within a radius of of every point, i.c., within B(0,r) ) for all / E P. These guarantees typically tend to be true for small values of in Deep Neural Networks. Thus, the predictor corresponding to the fixed point of will satisfy core-stability when restricted to predictors within distance to it, i.e., it is locally core-stable predictor.
4.2 Computation of a Core-Stable Predictor When Utility Functions are Concave
In this section, we show that under certain assumptions the utility functions,
describe an efficient distributed protocol that computes the core-stable predictor. In particular, we look into the scenario, where the utility function of each agent is concave. Note that this would automatically satisfy the conditions in Theorem [ as any conical combination of concave functions is also concave and will admit convex set of maximizers.
We first show that a core stable predictor can be expressed as an optima of a convex program. In partic- ular, any predictor that maximizes the product of utilities of the agents, i.e., argmatte I u, (0) (or equivalently the sum of logarithms of the utilities of the agents), is core stable.
maximize
(())
Σ EE[M]
log(u: (u (0))
subject to 8
Observe that if the utility of each agent is concave, then the above program is convex. Since the logarithm is concave increasing function, each log(u,() is a concave in and the sum of concave functions is concave. Thus, is concave maximization subject to convex constraints.
Theorem 2. If (u(() is concave for all i E [n]. then any predictor 6* that maximizes the convex program 2 is core-stable.
Proof Sketch. We defer a formal proof to Appendix C The main technical ingredient of our proof is to show that if 8" is a solution to the convex program 2 then, for any other predictor 0' E P.
we have Eie(o) x..(B) < n. Now if 8* is not core-stable, then there exists an S S [n] and 6 P.
such that u,(0")
11(S)u((0)) for all i E S with at least one strict inequality, then we have (:(0) / S S n. which a contradiction.
EiE(o)
(:(0)
Σ Eies (())
Implications. The proof of Theorem shows that the strong utilitarian property of E
[.(o-] S n
":(0')
for any 0' E P implies core-stability of 0* under any (non-negative) utility functions. Clearly, such H" must be Pareto-optimal, and furthermore, the inequality implies that 0' computed by any other classical method, if some agents gain, then some other agents must be loosing by a lot. Secondly,

---

under concave utilities optima of convex program equation satisfies this property, and hence can be computed in efficiently. Below we discuss distributed protocol for the same.
Tightness of Our Guarantees. We make a remark that there are instances, where the guarantees provided by core-stability is tight. These instances typically exhibit large heterogeneous behaviour in their training data. Our guarantees work under the assumption that the utility functions are concave and the domain of predictor is a convex set. Consider the following scenario: Our goal is choose 11 (so C is a convex set). Now, let there for all [n], and E C (utility functions
a predictor E C, where C. = {c 12 Eiejni
be agents, and (,(c) concave). Intuitively, each agent has their ideal predictor to be a distinct axis aligned hyperplane (capturing the heterogeneity in data). Observe that for each agent, the best possible utility is as there exists a predictor et such that c = and cx for all k * i. Now, note that, for any predictor E C, have Eie(n] Q 1. Thus, for any classifier chosen, there exists agent such that uy (c) = C S 1/n. Thus, for each predictor c, there exists a set = {i} and a another predictor c" E C such that Lies (:((")/u((c) > Observe that even our guarantees of proportionality are
linear and therefore
tight in this example. This example shows that the scaling factor of |S|/n is unavoidable.
We now propose a distributed SGD framework to determine a core stable predictor. We call our Algorithm as CoreFed (Fully outlined in Algorithm [ in the appendix).
CoreFed. Observe that for convex losses, we can directly solve this maximization to the optimal to achieve core-stability. For non-convex losses such as those for DNNs, we apply gradient descent to maximize the objective. Suppose we are training on n finite samples {(x, si) drawn from the data distribution P, which constitute empirical distribution Pn. We observe that, the gradient can be expressed as an conical combination of the gradients of each group:
vo,,(0) EE(m) Us
VOR (ma)) p(: ((f(()).))
VoL(O)=
=
Mi E (a (ff(()))))))
(3)
KE(M)
Therefore, for each group. we reweight its gradients or weight updates by (M; ( (ff(z)) and then sum up to get the final weight update in each iteration, which leads to distributed training protocol shown in Algorithm
((.y)))p))
This protocol is similar to standard FedAvg. However, in CoreFed the model weight updates are weighted then aggregated at each iteration, while in FedAvg, model weights are directly averaged and aggregated at each iteration. In the limit that each local update uses single step with entire IP-l
< < the training dataset on device Therefore, the global update is unbias gradient descent step of the objective Σ. log
dataset, A0, 7 pp ElPrl Vo (z.6)) () where D. = ((x15) (1) v))
[D.I} is
p. I!Drl E(for (x. (1)) ye )²)) = C(0,) where C(-) is defined in
4.3 Core-Stability in Linear Regression and Classification with Logistic Regression
We now discuss some of the predictive models, where the concavity requirements of the utility function satisifed. Note that a necessary and sufficient condition for u(( to be concave is that the loss function E() should be convex in Here we elaborate few scenarios where this is true. Suppose we are training on n finite samples {(x,, 3:) )eej drawn from the data distribution P. which constitute empirical distribution P...
Linear Regression. These are the scenarios where we map our input variables to a real number (not discrete class labels). In this case, we have fo(z) 0Tz. Observe that the regression loss, then E (aa))> (ff( = =E (Z (f'x (exxyy) y)² would be convex in 0.
Lemma 4.3. CoreFed determines a core-stable predictor a federated learning setting training linear regression.
7

---

Classification with Logistic Regression. In classification tasks we map the input variables to dis- crete class labels. commonly used loss function in classification is logistic regression. Given clas- sifier 8 and a scalar c E IR, an agent i's loss is given by (a c) = |10| + Eigjn) log(e 1.ce-iil. 16 (6' 2.+0)
1) 27 1 11. It is well known that (,(0,c) c) is convex (see, e.g.. Thus, us (,(0,) c) Mj (0, where M2- arg P, (0,c)) is concave.
Lemma 4.4. CoreFed determines a core-stable predictor in a federated learning setting training classification with logistic regression.
4.4 Approximate Core-Stability in Deep Neural Networks
Theorem 2 requires that (0) is concave in terms of I and global optimality for the objective ( = Injn (8) to achieve core-stability. However, these two conditions are challenging to be satisfied for DNNs, where the training loss is non-convex and common training methods, which are based on first-order gradients, not guaranteed to absolutely converge. In this more general scenario, the following theorem shows the relaxed local core-stability that we can attain for approximately first-order converged predictor (i.e., predictor with small local gradient [Vo[(0)]|2 S e).
Definition 5. A predictor 0 E P. is called (d, k)-pseudo core stable, where d > 0, k > 1 if there [S] kn uj (0') 2 us (0)
exists no other 0' E P such that ||0' - 0||2 < d, and no subset S of agents, such that for all i E S, with at least one strict inequality.
Theorem 3. For all i E [m]], if (0) is B-smooth in terms of 0 within (0' : -10-- 0'1l2 z d}. and [|VoL())1l2 S E, then 0 is a (d. k) -i)-sseudo core stable predictor, where
-c+ Ve +B(k 1)m Eie(n) (((0)- d d=
(4)
3 Eie(n) (0)
Implications. We defer the proof to Appendix E Theorem states that, for smooth neural net- works, there exists no predictor 6' in the neighborhood with lg radius d, that any subset of agents prefer "significantly". Although our guarantees are local guarantees, remark that global fairness guarantees are unlikely for DNNs. Most of the fairness guarantees in computational social choice and game theory crucially require the agents to have convex preferences, i.c., the level sets of the utility functions need to be convex. There are impossibility results for fairness when the agent's preferences non-convex. However, while non-convex consumer preferences are not interesting from an economic standpoint, our current work finds an application for these preferences in fairness in federated learning with DNNs.
4.5 Weighted Core-Stability
In this section, we show how to generalize all of our results (Theorems 2 and when we want to train the joint predictor to fit the data of certain agents more than some others. In particular, for each agent i, if we assign weight we indicating the desired bias of the final trained model towards agent { then with subtle modifications, we show the existence of weighted core stable predictor, when the utility functions of the agents satisfy the conditions in Theorem |
Formally,
Definition (Weighted Core-Stability). Given the weight vector w (W1, W2..... wp), predictor 0 E P. is weighted core-stable if and only if there exists no other predictor 0' E P and subset of
agents S C [ri] such that 2ies My
Ex(1) wy (,,)') 2 un (0) for all i E S with at least one strict incquality.
Note that, when all the agents have the same weight, egg., w. = 1, E [n]. then weighted core- stability matches core-stability. At high-level the concept is the same, no group of agents can significantly benefit by forming a coalition within themselves. However "significantly" means a
multiplicative increase by Eycte) wi (instead of |S] /1/n for the unweighted case), i.e., is dependent Eyes "y;"
on the total weight of the set S. We make the aforementioned guarantee more intuitive by considering special cases of S. When S = {i}, our guarantees say that agent i gets a utility of w. /E wzy)
'Following the light of (6). one possible candidate can be = D.. i.e., set w. to the size of the data shared by agent with the model.
8

---

fraction of her maximum utility, i... the utility of agents with higher weights are prioritized. We call this weighted proportionality. Also note that by setting [nl,, we get Pareto-optimality (similar to the unweighted case).
Furthermore, by changing the convex program maximizing Σ Ljem Wy (og((;((0) instead of
Eje(n] log(u,(() (0)), we can get the weighted version of Theorem 2
This also suggests a simple
generalization of CoreFed to Brighted-CoreFed and all our extensions in Sections 4.3 and 4.4 will
also generalize to the weighted setting.
Empirical Evaluation
We evaluate fair ML method CoreFed and baseline FedAvg (1 three datasets (Adult, MNIST and CIFAR-I0) on linear model and deep neural networks. We show that the model trained with CoreFed is able to achieve core-stable fairness, while maintaining similar utility with the standard FedAvg protocol, which cannot guarantee to achieve core-stable fairness.
5.1 Experiment Setup
Dataset. evaluate our algorithm CoreFed on Adult 2). MNIST 17] and CIFAR-IO [6 datasets. To perform federated learning heterogeneous data, construct the non-IID data by sampling the proportion of each label from Dirichlet distribution for every agent, following the literature [18].
Models. We train a logistic regression classifier on Adult data. We use a CNN, which has two 5x5 convolution layers followed by 2x2 max pooling and two fully connected layer with ReLU activation for MNIST and CIFAR-10. 10. We also evaluate with more complex network VGG-11 on CIFAR- 10. For Adult dataset, the utitility selected as M 4og where Log is the logistic loss. For CIFAR-10 and MNIST, we cross entropy loss Lee as the training loss with utility U becomes M fee M is set to 3.0, 1.0 and 3.0 for Adult, MNIST, and CIFAR-1O, respectively, based on statistical analysis during training. All experiments are conducted on 1080 Ti GPU.
Table 1: Comparison of utility (M - lce) for each agent trained with CoreFed and FedAvg. We (,')))
that Σte(n) m.(0")
< n holds, where 0' denotes the weights of shared model trained by FedAvg and
o- by CoreFed.
U, (6')
Dataset
Method
Agent
Agent
Agent 2
U(Average)
U(Multi)
Σ Ei((n) (a+)))
FedAvg
2.59
0.77
1.46
1.61
2.91
Adult
2.80 (<3)
CoreFed
2.62
0.90
1.53
1.68
3.61
FedAvg
0.34
0.29
0.92
0.52
0.091
MNIST
2.66 (<3)
CoreFed
0.36
0.41
0.91
0.56
0.13
FedAvg
0.63
1.40
0.51
0.84
0.45
CIFAR-10
2.62 (<3)
CoreFed
0.73
1.35
0.71
0.93
0.70
Table 2: Comparison of utility (M tee) for each agent trained with CoreFed and FedAvg on CIFAR-10 with network VGG-11.
Σie(n) (60)))
Method
Agent 0
Agent
Agent 2
U(Average)
U(Multi)
(0-)
FedAvg
0.25
3.25
3.46
2.35
2.89
2.25 (43)
CoreFed
1.63
3.17
3.32
2.71
17.15
5.2 Evaluation Results
We demonstrate that our CoreFed distributed training protocol T the core-stable fairess through comparison with FedAvg on different datasets and settings. Concretely, we perform training with FedAvg and our proposed CoreFed, and then validate whether the utility inequality
(a(0') (see Implications after Theorem 2 holds under different settings. Here we treat the Eiejo (.

---

Table 3: Comparison of utility (M - kee) for each agent trained with CoreFed and FedAvg on CIFAR-10 in the scenario that some agents have data of low quality (i.e., with added Gaussian noise). The variance of added Gaussian noise is 0.0,0.5,1.0 for agent 0,1,2, respectively.
ExE(n) 21(6"))
Method
Agent 0
Agent
Agent 2
U(Average)
U(Multi)
u. (0*)
FedAvg
3.28
3.30
1.42
2.67
15.37
2.74 (<3)
CoreFed
3.26
3.27
1.95
2.83
20.79
model trained by FedAvg parameterized by 0', while the model trained by our CoreFed parameterized by 8" That is to say, since the model trained by CoreFed achieves core-stable faireess, we expect the model parameterized by would have pareto-optimality Indeed, results in Section Juggest that CoreFed achieves core-stable fairness compared with FedAvg while maintaining similar utility. We also report the average and multiplicative utility of the trained global model in "U(Average)" and "U(Multi)" columns. We can see that CoreFed achieves higher overall utilities, especially for the multiplicative case since FedAvg favors the average case in general. We validate the conclusion on more complex DNN VGG-11 on LIFAR-10 in Table 2 In addition, with low quality data by adding Gaussian noises to some agents as shown in Table 3 demonstrating the optimality of CoreFed. We also perform the evaluation with more agents as shown in Table 4
explicitly consider agents
Table 4: Comparison of utility (M - kce) for each agent trained with CoreFed and FedAvg on CIFAR- 10 with agents. Ai represents the i-th agent. UA and UMs denote the average and multiplication of the utility respectively.
Σ, u: (:
Method
A0
Al
A2
A3
A4
A5
A6
A7
A8
A9
UA
UM
((+)
FedAvg
2.11
2.30
3.04
3.28
1.15
2.70
2.00
2.72
2.76
3.14
2.52
7084
9.77(<10)
CoreFed
2.26
2.50
3.12
3.32
1.42
2.50
1.99
2.80
2.65
2.99
2.55
9173
Conclusion
In this work, we introduce new notion fairness in federated learning, inspired from a fundamental concept in social choice theory. We show that the new faimess notion is more resilient to noisy data from certain clients, in comparison to FedAvg or egalitarian fair federated learning methods. We believe this work would open up new research directions on connecting game theoretic analysis and statistical machine learning under different learning paradigms, objective, and utilities.
This work is supported by the NSF CAREER grant CCF No. 1000466,36, NSF grant No. 1910100, NSF CAREER grant CNS No.2046726, C3 AI, and the Alfred P. Sloan Foundation.
Acknowledgements
10

---

References
[1] Alan Agresti. Categorical data analysis. John Wiley & Sons, 2003.
[2] Arthur Asuncion and David Newman. Uci machine learning repository. 2007.
[3] Haris Aziz. Justifications welfare guarantees under normalized utilitics. SIGecom Exch., 17(2):71-75, 2019.
[4] Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 11966):161-11100 2011.
[5] Kate Donahue and Jon M. Kleinberg. Models of fairness federated learning. CoRR, abs/2112.008 18, 2021.
[6] Kate Donahue and Jon M. Kleinberg. Optimality and stability in federated learning: A game- theoretic approach. In NeurIPS, pages 1287-1298, 2021.
[7] Wei Du, Depeng Xu, Xintao Wu, and Hanghang Tong. Pairness-aware agnostic federated learning. In SDM, pages 181-189. SIAM, 2021.
[8] Brandon Fain, Kamesh Munagala, and Nisarg Shah. Fair allocation indivisible public goods. In EC, pages 575-592. ACM, 2018.
[9] Duncan Karl Foley. Resource allocation and the public sector. Yale University, 1966.
[10] Laurent Gourvès, Jérôme Monnot, and Lydia Tlilane. Near fairness in matroids. In ECAI, volume 263 of Frontiers Artificial Intelligence and Applications, pages 393-398. IOS Press, 2014.
[11] David Hosmer Jr, Stanley Lemeshow, and Rodney X Sturdivant. Applied logistic regression, volume 398. John Wiley & Sons, 2013.
[12] Tiansheng Huang, Weiwei Lin, Wentai Wu, Ligang He, Keqin Li, and Albert Zomaya. An ffficiency-boostion client selection scheme for federated learning with fairness guarantee. IEEE Trans. Parallel Distributed Syst., 325751155--1564 2021.
[13] Wei Huang, Tianrui Li, Dexian Wang. Shengdong Du, Junbo Zhang, and Tianqiang Huang. Fairness and accuracy horizontal federated learning. Information Sciences, 589:170-185, 2022.
[14] Shizuo Kakutani. generalization of Brouwer's fixed point theorem. Duke mathernatiaa journal, 833):457-459, 1941.
[15] Jakub Konečny, H Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492 2016.
[16] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[17] Yann LeCun, Léon Botton, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applicd to document recognition. Proceedings of the IEEE, 86(1 (6:211):277822 2324, 1998.
[18] Qinbin Li, Yiqun Diao, Quan Chen, and Bingsheng He. Federated learning on non-iid data silos: An experimental study. arXiv preprint arXiv:2102.000779 2021.
[19] Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. In ICLR. OpenReview.net, 2020.
[20] Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, pages 125-131, 2004.
11

---

[21] H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera Arcas. communication-effiiiee learning of deep networks from decentralized data. In International Conference Artificial Intelligence and Statistics (AISTATS), 2017.
[22] Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. International Conference on Machine Learning, pages 4613-4625. PMLR, 2019.
Agnostic federated learning. In
[23] Herve Moulin, Fair division in the internet age. Annual Review of Economics, 11, 2019.
[24] Thomas J Muench, The core and the lindahl equilibrium of economy with a public good: example. Journal of Economic Theory, 4(2):241-255) 1972.
[25] Afroditi Papadaki, Natalia Martínez, Martín Bertrán, Guillermo Sapiro, and Miguel R. D. Rodrigues. Federating for learning group fair models. CoRR, abs/21 10.01999, 2021.
[26] Benjamin Plaut and Tim Roughgarden. Almost envy-freeness with general valuations. SIAM J. Discret. Math., 14(2):1039-11) 2020.
[27] scikit-learn developers. 1.1. linear models scikit-learn 1.1.0 documentation. https //scikit-lears http://aaee/mmdlleeeeeeeeeeeeeea 2022.
[28] Yuxin Shi, Han Yu, and Cyril Leung. A survey of fairness-aware federated learning. CoRR, abs/2111.01872, 2021.
[29] Tianshu Song, Yongxin Tong, and Shuyue Wei. Profit allocation for federated learning. In 2019
IEEE International Conference on Big Data (Big Data), pages 2577-2586, 2019.
[30] Hugo Steinhaus. The problem of fair division. Econometrica, 16:101-104, 1948.
[31] Wikipedia. Core (game theory) wikipedia.
igame_theory] 2022.
[32] Xinyi Xu and Lingjuan Lyu. Towards building a robust and fair federated learning system. CoRR, abs/201 104644 2020.
[33] Miao Yang, Ximin Wang, Hongbin Zhu, Haifeng Wang, and Hua Qian. Federated learning with class imbalance reduction. In 2021 29th European Signal Processing Conference (EUSIPCO), pages 2174-2177 IEEE, 2021.
[34] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodrigucee and Krishna P. Gummadi. Fairness beyond disparate treatment & disparate impact: Learning classification without dis- parate mistreatment. In WWW, pages 1171-1180 ACM, 2017.
[35] Yuchen Zeng, Hongxu Chen, and Kangwook Lee. Improving faimesss via federated learning. CoRR, abs/21 10.1 15545, 2021.
[36] Fengda Zhang, Kun Kuang, Yuxuan Liu, Chao Wu, Fei Wu, Jiaxun Lu, Yunfeng Shao, and Jun Xiao. Unified group fairness federated learning. CoRR, abs/2111 11.4986, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We clearly specify the assumptions and application scopes, if exists, of all our results.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We discuss broader impacts in Appendix A
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
12

---

(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] We include complete proof's for results the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We include them in Section 5.1
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] Indeed, we rigorously compute the confidence intervals due to the finite sampling (see Section 5.2). and guarantee that all fairness certificates reported in the paper holds with probability 90%.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] We provide them in Section 5.1
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No] We only use public data.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [No] We only use public data.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "buQPKT2Nwq-", "reviewer": "Reviewer_WXrM", "summary": "This paper introduces a definition for fairness between agents in federated learning that is derived from social choice theory. The authors name it core-stability. Intuitively, core-stability ensures that there is no incentive for any subgroup $S$ of agents to defect from the rest and create their own centralized model. The authors point out how core stability ensures that two basic conditions of proportionality, and Pareto optimality are satisfied. Moreover, the authors offer an optimization objective CoreFed which provably converges to a core-stable network under a set of reasonable assumptions (the definition of core-stability can be slightly relaxed to be local in order for the theory to extend more diverse settings). Finally, the authors provide some empirical results to show that CoreFed does better than the existing FedAvg objective at achieving core-stable fairness.", "questions": "I have decided to accept this paper. I would raise my score even further if the authors could better contextualize their work to offer an explanation of perhaps why this notion of core-stability (which is quite natural) has not been used in the past, and the impact they believe it will have now.", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Originality\n---\n### Strengths\n- Though I am not familiar with the literature on the intersection of fair federated learning schemes and social choice theory, I was unable to find any work that used this notion of core-stability. As far as I can tell, this goal of essentially subgroup indifference has not been proposed before in federated learning. Moreover, I believe this is a fresh perspective that should be further explored in future work.\n\n## Quality and Clarity\n---\n### Weaknesses\n- Some of the writing in the paper was needlessly wordy, particularly in the introduction and the abstract, and there were some minor grammatical issues throughout the paper. I think for the camera ready version it would be good to trim down these sections and polish the prose a bit further, but these problems do not get in the way of understanding the paper.\n- The authors could have performed more empirical results to further investigate CoreFed on more commonly used and complex models than the simple CNN used for section 5.2. More comprehensive empirical results in general would be a great avenue for future work.\n\n### Strengths\n- The quality of the theoretical analysis in this paper is exceptional. The authors demonstrate that they have thought deeply about this problem from many different angles, and the math in the main body was all easy to follow (intuition for omitted proofs was quite good too). Though I didn't carefully read the proofs in the appendix, everything looked sound at a glance.\n\n## Significance\n---\nIt's difficult for me to assess the significance of this work in the absence of experience in this line of research. What I can say is the claims are ostensibly sound, and the idea is very well motivated. \n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "ZryFORN4MEC", "reviewer": "Reviewer_JpwV", "summary": "The paper introduces a new notion of fairness dubbed as core-stable fairness in FL setting, by borrowing ideas from game theory and social choice theory. Core-stable fairness indicates there is no subset of agents that can benefit significantly by forming a coalition. The authors propose a new FL Protocol based on this new notion of fairness called CoreFed. The authors prove that CoreFed finds a core-stable model when the loss functions of agents are convex, and CoreFed can find an approximate model when loss functions are non-convex.  Finally the authors do an empirical comparison between CoreFed and FedAvg in which they show CoreFed achieves higher core-stable fairness than FedAvg while maintaining similar accuracy.  ", "questions": "1. What are the $privacy$ implications of Core-stable fairness ? Some discussion around this in the paper would be useful. \n2. Similarly, What are the implications of CoreFed protocol, in regards to communication-cost given that in addition to local updates, local losses need to be also communicated back to the server. How scalable this protocol is in real world applications ?", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n* The paper appears to be theoretically sound as well as the claims seem to be supported by theoretical proofs. \n* The paper introduces a new notion of fairness in FL settings, that has not been studied in the literature.  \n\n**Weaknesses:**\n\nMainly is due to limited empirical evaluation. In particular:\n* The proposed protocol/algo only compared to FedAvg, and not with some existing recent works in the Literature, e.g., Ref 20 [Li et al., 2020].\n* Limited experiments and few number of agents (i.e., 3 agent in Table 1 ).\n* Lack of experiments in settings with low quality data from some agents. This was a promise of the proposed algorithm to be robust against low quality agents in the summary and main body of the paper but was not supported by experiments. \n\n*Minor Comments (not affecting review score):*\n\nDuplicate references in introduction [32, 23, 8, 35, 36, 26, 23] \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KHIjhSVaSxV", "reviewer": "Reviewer_qZPM", "summary": "This paper studies core stability, where no subset of agents can benefit much from forming a new coalition, in federated learning. This paper shows that:\n1. Core-stable solution exists when the utilities are continuous and the set of maximizers of any conical combination of the utilities is convex.\n2. Maximizing $\\sum \\log(u_i(\\theta))$ derives a core stable solution when $u_i$s are concave. The objective can be maximized efficiently through SGD. Interestingly, the gradient update is similar to FedAvg.\n3. The work then extend the core-stability to approximate core-stability in the non-convex case.", "questions": "For the definition of core-stability, could the authors explain the intuition/motivation that the multiplicative constant is $\\frac{|S|}{n}$? Intuitively, the players in $S$ have incentives to form a new coalition if $u_i(\\theta')>u_i(\\theta)$ for all $i\\in S$ or approximately $u_i(\\theta')>(1+\\alpha)u_i(\\theta)$ for some $\\alpha>0$. \n\nIs there any technical challenge of extending the results to the setting where core stability is defined as $\\nexists \\theta', u_i(\\theta')>(1+\\alpha)u_i(\\theta)$ for all $i\\in S$? If so, could the authors list some of them?", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper studies the core-stability in federated learning, showing the existence of core-stable solutions and providing an efficient algorithm to find the solution. The results are novel and clean. The presentation is clear. The algorithm CoreFed is quite subtle as it is similar to FedAvg only with different weight updates. Overall, it is a good work.\n\nMy only concern is about the definition of core-stability, where players are incentivized to form a new coalition only when $\\frac{|S|}{n}u_i(\\theta')\\geq u_i(\\theta)$. That is to say, a single player would prefer to learn by herself only if her utility can be increased to $n$ times the currently utility. The multiplier $\\frac{|S|}{n}$ seems a little weird to me. It seems like that the results make more sense when $n$ is small.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept