Does Egalitarian Fairness Lead to Instability? The Fairness Bounds in Stable Federated Learning Under Altruistic Behaviors

Authors: jiashi  gao
ziwei  wang
xiangyu  zhao
xin  yao
xuetao  wei
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-10 05:55:09

Abstract: Federated learning (FL) offers a machine learning paradigm that protects privacy, allowing multiple clients to collaboratively train a global model while only accessing their local data. Recent research in FL has increasingly focused on improving the uniformity of model performance across clients, a fairness principle known as egalitarian fairness. However,  achieving egalitarian fairness in FL may sacrifice the model performance for data-rich clients to benefit those with less data. This trade-off raises concerns about the stability of FL,  as data-rich clients may opt to leave the current coalition and join another that is more closely aligned with its expected high performance.  In this context, our work rigorously addresses the critical concern:  **Does egalitarian fairness lead to instability?** Drawing from game theory and social choice theory, we initially characterize fair FL systems as altruism  coalition formation games (ACFGs) and reveal that the instability issues emerging from the pursuit of egalitarian fairness are significantly related to the clients’ altruism within the coalition and the configuration of the friends-relationship networks among the clients. Then, we theoretically propose the  optimal egalitarian fairness bounds that an FL coalition can achieve while maintaining core stability under various types of altruistic behaviors.  The theoretical contributions clarify the quantitative relationships between achievable egalitarian fairness and the disparities in the sizes of local datasets, disproving the misconception that egalitarian fairness inevitably leads to instability. Finally, we conduct experiments to evaluate the consistency of our theoretically derived egalitarian fairness bounds with the empirically achieved egalitarian fairness in fair FL settings.

Main paper: 
 introduction: 
 Federated learning (FL) has emerged as a significant learning paradigm in which clients utilize their local data to train a global model collaboratively without sharing data and has attracted researchers from various fields, especially in domains where data privacy and security are critical, such as healthcare, finance, and social networks [1, 2, 3] . In vanilla FLs, different clients sharing the same global model may experience varying performance (i.e., error) due to differences in the amount of data contributed by each client. As clients may lack access to significant data resources due to objective or unavoidable factors, such as regional specificity and historical inequalities, recent works [4, 5, 6, 7, 8, 9] have focused on ensuring that the performance of global model across the clients roughly comparable or even equal, termed as "egalitarian fairness". In FLs complying with egalitarian fairness, the performance of the global model on clients contributing high data resources may decrease to enhance the performance on other clients contributing lower data resources, particularly when local datasets are heterogeneous. This case could potentially cause higher-resource clients to leave the current grand coalition and form a sub-coalition to achieve desired performance, thereby disrupting the core stability [10, 11] of the FL. In game theory, a coalition is said to be core-stable if no subcoalition exists such that the players of that sub-coalition can obtain a payoff no less than they are allocated in the original coalition and at least one player of that sub-coalition can obtain a payoff greater than it was allocated in the original coalition. Otherwise, the original coalition is said to be blocked.Prior works [12, 13, 14, 15] have primarily examined the effects of pursuing performance optimality on the core stability of FLs, leaving the effect of fairness unexplored. These works view the FL process as a hedonic game [16] and assume that clients are selfish, with clients' utility functions being their own performance and only influenced by other individuals in the same coalition. However, in the real world, clients' behaviors are more complex: clients may form friends-relationships and exhibit altruism towards each other. Various external factors, such as commercial ties, welfare purpose, or shared research interests, etc, influence the relationships between clients. For instance, branches of the same corporation can be considered as friends due to common commercial goals. In contrast, branches from rival companies may be viewed as non-friends. Hospitals collaborating on developing a diagnostic model for welfare purposes can also be regarded as friends. Under altruistic behavior, a player's utility depends not only on their own performance but also on the performance of their friends. Furthermore, altruistic behaviors in FL, which have been largely overlooked in previous work, are particularly crucial when considering the impact of egalitarian fairness on stability. Altruistic behaviors influence the willingness of clients to sacrifice a certain degree from optimal performance [17, 18] . Considering the friend-relationships, Nguyen et al. [19] introduced altruistic hedonic games (AHGs), wherein players gain utility from their own valuation of the current coalition and the valuation of their friends within the same coalition. However, players who are friends may not be in the same coalition, but they can still influence each other's utility in the coalitions. For instance, altruistic hospital clients might choose to leave one coalition to join another where their friend hospitals are, aiming to enhance each other's performance collaboratively. When the FL process is described as AHGs, which excludes some friends' influence on a player's altruistic behavior, it may lead to a core-stable coalition in terms of local utilities but non-Pareto optimal in local errors. An alternative coalition structure exists where each client encounters an error not higher than that observed within the core-stable coalition structure, with at least one client experiencing a lower error.In this context, we pose the following open questions: How does egalitarian fairness affect the stability of FLs? How does this impact vary when clients exhibit altruistic behaviors? What is the optimal egalitarian fairness that a stable FL can achieve? Our contributions. We initiate discussions to address the above questions by proposing the game model under altruistic behaviors in Section 4. Based on the degree of altruism, we define three types of client behavior: purely selfish (non-altruistic), purely altruistic, and friendly altruistic. Existing research on egalitarian fairness mainly involves two implementations: optimizing the global model towards the worst-performing client [5, 20, 6] or simultaneously to all clients [4, 7, 8] . Correspondingly, we further distinguish altruism into a min-based and a mean-based aggregation of the friends' performance: welfare altruism and equal altruism. We model the collaborative training involving clients with altruistic behavior as altruism coalition formation games (ACFGs), where clients' utilities depend on a network of friends via one of the above cases of altruism. We theoretically demonstrate that the ACFGs result in a core-stable grand coalition, which is also Pareto-optimal in local errors.In Section 5, we demonstrate in detail that egalitarian fairness does not necessarily lead to instability; rather, it depends on the behaviors of the clients and the topology of the friends-relationship networks. We theoretically propose the optimal egalitarian fairness bounds that a core-stable FL can obtain. These bounds are functions of the disparities between the dataset sizes within the clients' friends network and the global minimal one. The established fairness bounds can be utilized to set a reasonable level of fairness in fair FLs. The proofs for these fairness bounds are modular. Beyond establishing tight fairness bounds, part of the contribution of this work lies in the analysis methodology used to derive these bounds.The main contributions in this paper are primarily theoretical. However, we also conduct experiments to assess the consistency of the theoretically proposed fairness bounds with the empirically achieved fairness in fair FLs. 
related work: 
 Stability in FL. Existing results on stability in FL mainly focus on a particular aspect of the entire issue. For instance, Donahue et al. [12] have first formulated the model sharing problem as a hedonic game, in which each player derives some cost (error) from the coalition they join. The aim of their research is to identify the conditions when the grand coalition or partitions of players are stable for varying federation aggregation mechanisms. In their subsequent work [15] , they have further contributed to calculating an optimal (minimum error) federating arrangement and analyzing the differences between stable arrangements and optimal arrangements using the canonical game-theoretic tools of the Price of Anarchy and the Price of Stability. Chaudhury et al. [14] have defined a fairness concept based on core stability, which requires that no subset of agents can benefit significantly than in grand coalition, and proposed CoreFed, an FL protocol to implement a core-stable predictor. Blum et al. [21] have proposed a stable and envy-free equilibrium-based collaboration protocol to meet the client's learning objectives while keeping their local data collection burden low. However, the impact of fairness on FL stability remains unexplored in existing work. Moreover, current research on the stability of FL is limited to the assumption of selfish individuals who compete with each other to win the game and maximize their own profits.Altruism in game theory. From more background on game theory and social choice theory, altruism [22, 23, 24] has been considered for cooperative games to date, in which the players' payoffs in the resulting game do not only depend on their individual payoffs but also on the neighborhood graph and the aggregation functions that reflect the social context. Numerous studies [25, 26, 27, 28] have highlighted the ubiquity and rationality of human altruism from economic, neural, and evolutionary perspectives. Rothe [22] has systematically introduced certain notions of altruism into existing game-theoretic models in both non-cooperative and cooperative games. Kerkmann et al. [29] have formally distinguished three degrees of altruism: selfish-first, equal-treatment, and altruistic-treatment preferences and studied both the axiomatic properties and the computational complexity of stability in altruistic hedonic games. In their other work [30] , they have additionally studied stability notions and computational analysis of altruism in coalition formation games. These works in game theory, where altruistic players only prefer coalitions with more friends, are constrained in the FL setting when additional model performance on both the player and their friends need to be considered. 
preliminaries: 
 Model and assumptions. Let's consider a setup involving N clients, where the i-client possesses a local dataset D i of size n i . The local datasets are samples drawn from data distribution P i (y|x). Each client can train a model M with parameter θ i locally, resulting in P (M(x, θ i )|x) → P i (y|x). In addition to local training, clients can participate in collaborative training with other clients and form an FL coalition, denoted as π. Within this coalition, clients share their local model parameters. These shared parameters are then aggregated according to a specific rule, θ = i∈π (ni•θi) i∈π ni . The above weighted aggregation known as FedAvg [31] is a widely used FL aggregation mechanism. We measure the aggregated global model's performance on the client's local dataset in the coalition through the expected error err i (π) = E x,y∼Di [∥M(x, θ) -y∥]. A lower err i (π) implies that the coalition π is more valuable for the i-th client. To determine a tight fairness bound, an FL model that gives exact errors for each client is necessary. Therefore, we build our work on the mean estimation task developed by Donahue et al. [12] , which develops the closed-form local errors as in Lemma 1. It's important to note that while we utilize this model, the questions posed by Donahue et al. [12] significantly differ from the focus of this paper: they focused on developing the error models in FL setting and identifying the stable conditions for selfish-clients forming coalitions, while our work explores the relations between fairness and core-stability in FL settings when clients exhibit altruistic behaviors.Lemma 1 (Corollary 4.3 in [12] ) In an FL setting with N clients, each client possesses a local dataset D i of size n i . The local dataset of each client D i is with mean θ i and standard deviation ϵ i , where θ i , ϵ 2 i ∼ Θ. When FL trains a global model for mean estimation and employs FedAvg for aggregation, the expected mean squared error (MSE) for a client with n i samples within coalition π is as follows,EQUATIONwhere µ e = E (θi,ϵ 2 i )∼Θ ϵ 2 i denotes the expected value of the variance of the dataset distribution, and σ 2 = var (θ i ) denotes the variance between the means of the clients' local datasets.Fairness definition. We explore egalitarian fairness in Definition 1, a fairness notion that assesses whether the global model exhibits equitable performance across clients with varying data resources. Definition 1 (Egalitarian fairness) For the clients within a coalition π holding datasets of varying sizes {n 1 , n 2 , ..., n N } and experiencing errors {err 1 (π), err 2 (π), ..., err N (π)}, the coalition structure π satisfy λ-egalitarian fairness if there exists a constant λ such that,EQUATIONHere, λ is the fairness bound. When λ = 1, the coalition π is said to satisfy strict egalitarian fairness. 
game model: 
 Before delving into the impact of fairness on the stability of the FL, we first define the concepts from the perspective of game theory and social choice theory. All proofs for this section are in Appendix. Definition 2 (Value) In the context of collaborative gaming, the value quantifies the payoff accrued to the i-th player as a result of participating within the current coalition π. Within the framework of FL, the value is defined as the error of the global model evaluated on the i-th client's local dataset as v i (π) = err i (π). Definition 3 (Friend) In a broader sociological context, the friend is considered the most intimate, trustful, and voluntarily chosen tie people maintain. Within the framework of FL, the friend set of the i-th client, denoted as F i , is defined as the clients whose value is also expected to be better when i-th client makes a coalition participation decision. Definition 4 (Core stability) The grand coalition π g (the coalition consisting of all players) is considered to be core-stable if there does not exist nonempty sub-coalition π s ⊂ π g such that π s ≻ i π g for ∀i ∈ π s , where ≻ is used to denote a preference relation. In other words, no nonempty sub-coalition π s ⊂ π g blocks π g .Based on the above notions, we define altruism in FL as the client's choice to remain within or exit the existing coalition π, influenced by the acquired values of their friends ∀f ∈ F i . Previous research on egalitarian fairness has primarily focused on two approaches: optimizing the global model towards the worst-performing client [5] or simultaneously to all clients [6] . Correspondingly, we classify altruism into two categories: welfare altruism and equal altruism. In the case of welfare altruism, a client's primary concern is for the friend who is in the worst situation. On the other hand, equal altruism implies that a client shows equal concern for all friends. The aggregate values for welfare and equal altruism are defined as min f ∈Fi ({v f (π)}) and 1 |Fi| f ∈Fi v f (π), respectively.We divide client behavior into three types based on the degree of altruism: purely selfish (nonaltruistic), purely altruistic and friendly altruistic.• Purely selfish: A purely selfish client opts to stay or leave the current coalition π, based solely on its own value, i.e., according to value definition, a purely selfish client prefers to join a coalition that offers a lower value v i and conversely, to leave a coalition that results in a higher value v i . The utility function of a purely selfish client is defined as u ps i (π) = v i (π).• Purely altruistic: A purely altruistic client chooses to stay or leave the current coalition π, only based on the value received by its friends. Corresponding to welfare and equal altruism, the utilities of a purely altruistic client are defined as u pa i (π) = min f ∈Fi ({v f (π)}) and u pa i (π) =1 |Fi| f ∈Fi v f (π), respectively.• Friendly altruistic: A friendly altruistic client decides whether to stay or leave the current coalition, π, based on its own value and the value its friends receive. Corresponding to welfare and equal altruism, the utility function of a friendly altruistic client is defined asu f a i (π) = w • v i (π) + (1 -w) • min f ∈Fi∪{i} ({v f (π)}) and u f a i (π) = w • v i (π) + (1 -w) • 1 |Fi|+1 f ∈Fi∪{i} v f (π)respectively, where w ∈ (0, 1) is selfishness degree parameter.Given two coalitions π 1 and π 2 , π 1 ≻ i π 2 occurs if and only if u i (π 1 ) ≤ u i (π 2 ). Donahue et al. [15] have established the sufficient conditions for achieving core-stability under the assumption of selfish clients, as in Lemma 2. Building upon their findings, we further introduce these conditions to cover scenarios of altruistic behaviors, as in Corollary 1.Lemma 2 (Lemma 10 in [15] ) When clients are purely selfish, for a set of clients with n i ≤ µe σ 2 , the grand coalition π g is core-stable.Corollary 1 For a set of players where n i ≤ µe σ 2 , the grand coalition π g remains core-stable when the clients are either purely altruistic or friendly altruistic. The proof is provided in Appendix A.2.Existing research [12, 14, 32] views FL as a hedonic game, where the players only care about the identity of the players in their coalition. Correspondingly, within the framework of the altruism hedonic game (AHG), the set of friends influencing the i-th client's participation decision is confined to F i → F i ∩ π i , where π i represents the coalition to which the i-th client belongs. In AHG, excluding some friends from a client's altruistic behavior can result in a core-stable coalition structure that is non-Pareto optimal in terms of local errors. The non-Pareto optimal indicates that an alternative coalition structure can be established where each client encounters an error not higher than that observed within the core-stable coalition structure, with at least one client experiencing a lower error. Such a core-stable coalition structure contradicts the assumption of rationality among clients. For example, Table 1 shows the error and utility of 4 friendly welfare altruistic (w = 0.5) clients in the mean estimation task. In a fully connected friendsrelationship network (Relation I in Figure 1 ), we first employ the AHG model to analyze the FL system. We recognize that the core-stable coalition structure Π stable = {{1, 2} , {3} , {4}} is non-Pareto optimal in local errors as there exists another alternative structure, i.e., Π alter = {{1, 2, 3} , {4}}, in which the errors are not greater than in Π stable (i.e., err i (Π alter ) ≤ err i (Π stable ), ∀i ∈ {1, 2, 3, 4}) and at least one client exhibits less error than that in Π stable (i.e., err i (Π alter ) ≤ err i (Π stable ), ∀i ∈ {1, 2, 3}). To ensure a corestable coalition structure that guarantees Pareto optimality and adheres to the rationality assumptions of the players, we model the FL process with altruistic behavior as an altruism coalition formation game (ACFG), where a client's utility is derived from the entire friend-network, regardless of whether the friends belong to the same coalition as the client. The ACFG fully captures the impact of altruistic behavior on a client's decision to stay or leave a coalition; for example, a client may opt to leave the current coalition to satisfy the needs of friends in other coalitions, a scenario that AHG can not capture. As shown in Table 1 , the core-stable coalition structure of a fully connected friends-relationship network under ACFG, Π stable = {{1, 2, 3, 4}}, is Pareto-optimal in local errors across clients.Proposition 1 (Pareto-optimality in error, Appendix A.3) Consider the FL system described as an ACFG, a core-stable coalition structure is also Pareto-optimal in local errors across all clients. To achieve egalitarian fairness in FL [4, 5, 20, 6, 7, 8] , resource-advantaged clients may sacrifice local error to improve error uniformity of global model across all participants, creating a motivation for these resource-advantaged clients to leave the FL framework. In this part, we initially reveal the factors that impact the emergence of issue "egalitarian fairness leads to instability". As demonstrated in Table 1 , the most egalitarian fair coalition structure is grand coalition, Π G = {π g } = {{1, 2, 3, 4}}, with a fairness bound λ = 1.306/0.734 ≈ 1.78. The complement coalition of a coalition πs: πc = πg \ πs.The sum of the dataset sizes in πs: Ns = i∈πs ni.The sum of the dataset sizes in πc:Nc = i∈πc ni. NgThe sum of the dataset sizes in the grand coalition:Ng = i∈πg ni. mThe index of the client with the smallest dataset size in πg: m = arg min i∈πg {ni}. lThe index of the client with the largest dataset size in πg: l = arg max i∈πg {ni}.When all clients are purely selfish and focus solely on minimizing their local error, the coalition structure Π G is not core-stable.The current core stable coalition structure is Π stable = {{1, 2} , {3} , {4}} with a fairness bound λ = 1.5/0.666 ≈ 2.25. However, when clients exhibit altruistic behavior, and the friends-relationship network is fully connected (Relation I), the most egalitarian fair coalition structureΠ stable = Π G = {{1, 2, 3, 4}}is also core stable. The finding demonstrates whether "egalitarian fairness leads to instability" is influenced by the clients' behavior. Furthermore, when the friends-relationship network among the clients changes to partially connected (Relation II), leading to the coalition structure Π G = {{1, 2, 3, 4}} becoming not core-stable anymore and the current core stable coalition structure is Π stable = {{1, 2, 3} , {4}} with a fairness bound λ = 1.375/0.666 ≈ 2.06. The observation demonstrates that, under altruistic behaviors, the diverse friends-relationship networks also impact whether "egalitarian fairness leads to instability".From the above analysis, we observe a varying optimal fairness achieved within the core-stable coalition under diverse client behaviors and friends-relationship networks, highlighting a significant problem to guide the setting of fairness in FL: for an FL system, what is the optimal egalitarian fairness that can be achieved without compromising the core-stability of the FL system? 
optimal egalitarian fairness bound: 
 We define a distance function to measure the dataset size of a client relative to all other clients within the same coalition π,EQUATIONGiven the grand coalition π g in an FL system consists of a set of N clients with local dataset size n i ≤ µe σ 2 and based on the properties of mean estimation task in Corollary 1, the grand coalition π g is core-stable. In this context, we give the tight egalitarian fairness bound achieved by π g in Proposition 2∼ 6. For any coalition π s ⊂ π g , we unify the common notations to represent the data size within this subset and its complement, as well as the specific individual indices in Table 2 . Proposition 2 (Optimal egalitarian fairness under purely selfish behaviors, Appendix A.4.1) Considering all clients act purely selfish, the grand coalition π g remains core-stable if the achieved egalitarian fairness is bounded by: λ ≥ max πs⊂πg Ns 2 Ng 2 • Ng•n l +d(πg,nm) Ns•n l +d(Proposition 3 demonstrates that the achieved egalitarian fairness declines as the gap between the smallest dataset size overall and the smallest dataset size within any given friends-relationship network increases. This gap is significantly smaller than that in purely selfish cases, thereby facilitating improved egalitarian fairness and creating a more relaxed condition for achieving strict egalitarian fairness as in Corollary 3.The core-stable grand coalition π g , consisting of purely welfare clients, can asymptotically achieve strict egalitarian fairness if all clients are friends with the client possessing the smallest dataset size and N g → ∞. The proof is given in Appendix A.4.4.Proposition 4 (Optimal egalitarian fairness under purely equal altruistic behaviors, Appendix A.4.5) Considering all clients act purely equal altruistic, the grand coalition π g remains core-stable if the achieved egalitarian fairness is bounded by:λ ≥ max πs∈πg |F kπ s |•Ns 2 Nc 2 Ng 2 • Ng•n l +d(πg,nm) Q ,where k πs = arg min i∈πsEQUATIONProposition 4 shows that the egalitarian fairness bound for purely equal altruistic clients is influenced by the gap between the smallest dataset size overall and the weighted sum of dataset sizes within any given friends-relationship network. , where k πs,1 = arg min i∈πs wEQUATIONProposition 6 (Optimal egalitarian fairness under friendly equal altruistic behaviors, Appendix A.4.7) Considering all clients act friendly equal altruistic, the grand coalition π g remains core-stable if the achieved egalitarian fairness is bounded by:EQUATIONThe given propositions establish tight egalitarian fairness bounds in core-stable FLs and demonstrate that the achievable egalitarian fairness for a collection of clients varies depending on the clients' behaviors and friends-relationship networks. Furthermore, these propositions can be adapted to situations where clients exhibit heterogeneous behaviors within an FL system as follows.When client behaviors exhibit heterogeneity in an FL system, the achievable egalitarian fairness for a core-stable grand coalition π g is determined by the maximum egalitarian fairness bounds calculated across sub-coalitions formed by clients with homogeneous behaviors.Example 1 An example to calculate the achievable egalitarian fairness bound under heterogeneous behaviors is as follows: for a set of N clients, where clients i ∈ C = {1, 2, ..., S} act selfishly and the remaining act purely welfare altruistic, the achieved egalitarian fairness of π g is bounded by,EQUATION 
evaluation: 
 In following experiments, we validate the tightness and applicability of the analyzed fairness bounds for the given tasks. To conduct the experiments, we first give a fair FL framework to implement egalitarian fairness, where a coefficient p is introduced to increase the aggregation weight of clients who received higher local errors:θ C = i∈C (ni• err p i •θi) i∈C (ni•err p i ). The preceding discussions are independent of the fair FL framework chosen. We follow up on the task models proposed by Donahue et al. [12] . The first case is a mean estimation task involving a fixed set of 4 players. Each player has a fixed number of samples, specifically {20, 40, 50, 100}. Each player draws their local data samples from their true distribution with parameters Y i ∼ (θ i , ϵ i ), where the samples are independent and identically distributed (i.i.d.).Here, θ i ∼ N (µ = 0, σ 2 = 1) and ϵ i ∼ 125×Beta(a = 8, b = 2). To further validate the adaptability of this theoretical results, we introduce additional linear regression task with a fixed set of 3 players. Each player has a fixed number of samples, specifically {50, 100, 200}. Each player draws 2-dimensional input features from their own input distribution, X 1 i , X 2 i ∼ N (µ = 0, σ 2 = 1). The output label is drawn from Y i ∼ 250×Beta(a = 8, b = 2). All experiments are conducted on Intel(R) Xeon(R) Gold 5318Y CPU @ 2.10GHz.We conduct the effectiveness and tightness validation of the theoretical egalitarian fairness bound across diverse scenarios include (1) different client behaviors (Figure 2 ), (2) different structures of friends-relationship networks (Figure 3 ). The results demonstrate the alignment between our theoretically derived egalitarian fairness bound (green dashed line) and the empirically achieved egalitarian fairness within the core-stable grand coalition (red solid line) under both fully connected and partially connected friends-relationship networks.In Appendix A.5, we conduct additional experiments to further validate the effectiveness of the theoretical results under (3) heterogeneous client behaviors (Figure 4 ) and (4) additional regression task (Figure 5 ).Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: We provided the experimental setting/details in Section 6.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
discussion and limitations: 
 In this section, we outline the scope of our work and identify several limitations of our theoretical and experimental results, which could serve as potential starting points for future work.More complex task scenarios. This work paves the way for future research within the domain of FL. Initially, it would be insightful to explore the impact of other notions of fairness, such as proportional fairness [33] -where a client's payoff is proportional to its data contribution-on the stability of FL. Moreover, for theoretical proofs, our work is built upon the exact-error task models developed by Donahue et al. [12] ; future work could be extended to more complex collaborative training tasks. Initially, we chose the maximum and linear weighting of errors to construct the utility functions because they are simple and typical examples for theoretical analysis. Moving forward, our key theoretical ideas can be extended to a broader class of utility functions in the form of generalized mean, which encompasses many prominent social welfare functions, i.e., weighted power-mean welfare function [34] (as in Appendix A.4.8).Incentive Mechanisms and Client Behavior Dynamics. As we discover the bounds of egalitarian fairness that a stable coalition can achieve, a practical question arises: How can we correspondingly design suitable incentive mechanisms to retain clients in the coalition when high egalitarian fairness is a mandatory requirement? Given that altruism is closely related to stability when pursuing fairness, further exploration into how various human behaviors-such as reciprocity, bounded rationality, risk aversion, and risk tolerance-impact the stability of FLs in achieving specific objectives would be of profound interest.Overfitting. Centering on exploring the relationship between egalitarian fairness and stability, we use the stylized model in Lemma 1, which provides a closed-form error to derive precise relations and generate insights into fairness settings in fair FLs. However, overfitting [35] in machine learning leads to uncertainty in the error outlined in Equation 1, which is influenced by model structure and parameters, choice of training algorithms, and the specific data distributions of clients, etc. Extending our theoretical analysis to establish fairness bounds in specific model states, such as overfitting, is considerably more complex and remains an open area of research; however, our approach may still provide a valuable foundation for further exploration.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [NA]Justification: The experimental results in this paper ARE NOT influenced by random seed setting, and the error bar is not applicable.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
conclusion: 
 In this work, we have rigorously answered a previously unexplored but critical question: Does egalitarian fairness lead to instability? Through our analysis, we have explored the influence of clients' altruistic behaviors and the configuration of the friend-relationship network on the achievable egalitarian fairness within a core-stable federated learning (FL) coalition. Our research has identified the optimal egalitarian fairness bounds without compromising core stability from a theoretical standpoint. The outcomes of our research can be leveraged to establish appropriate egalitarian fairness in FL implementation, which plays a crucial role in improving the alignment of FL processes with societal welfare and ethical standards. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper posed no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We properly credited the uses of existing assets in Section 6 and the license and terms of use were explicitly mentioned and properly respected.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: A.1 Monotonicity of error with dataset size Lemma 3 (Monotonicity) For any two clients within the same coalition, i, j ∈ π, if n i > n j , err i (π) < err j (π). Conversely, if err i < err j , n i > n j .Proof Based on the exact errors in Lemma 1, it's natural that if n i > n j , err i (π) < err j (π). DenoteEQUATIONA.2 Core-stable conditions Corollary 1 For a set of players where n i ≤ µe σ 2 , the grand coalition π g remains core-stable when the clients are either purely altruistic or friendly altruistic.Proof In a grand coalition π g comprising N clients, each client holds a local dataset with size n i ≤ µe σ 2 . Based on Lemma 2, when n i ≤ µe σ 2 , it holds that err i (π g ) ≤ err i (π s ). Whether within π g or a subset π s ⊂ π g , the i-th purely welfare altruistic client focuses on the same friend, that is, the k-th client, where k = arg minEQUATIONTherefore, the π g is core-stable for purely welfare altruistic clients. For the purely equal altruistic client, the optimal individual error under π g also leads to the optimality of the average multiindividual error and the following equation holds:EQUATIONTherefore, the π g is core-stable for purely equal altruistic clients.The utilities of friendly altruistic clients are a weighted combination of the utilities under selfish and purely altruistic behaviors. According to the established core-stability when clients are selfish and purely altruism, the condition n i ≤ µe σ 2 facilitates utility minimization within the grand coalition π g for clients with selfish and purely altruistic behaviors. Thus, this condition also leads to the utilities within the grand coalition π g being minimized for clients exhibiting friendly altruistic behaviors.Proportion 1 (Pareto-Optimality in error) Consider the FL system described as an ACFG, a corestable coalition structure is also Pareto-optimal in local errors across all clients.Proof We prove the Proportion 1 by contradiction. Consider N clients. Assume that a core-stable coalition structure Π CS is not Pareto-optimal. Then, there exists a Pareto-optimal coalition structure Π P O that satisfies the following conditions:EQUATION)For clients exhibit altruism with selfishness degree parameter w ∈ [0, 1], it holds that:EQUATIONwhich is contradicts the assumption of Π CS is core-stable. Based on the above, a core-stable federation structure is also Pareto-optimal under ACFG.Proposition 2 (Optimal egalitarian fairness under purely selfish behaviors) Considering all clients act purely selfish, the grand coalition π g remains core-stable if the achieved egalitarian fairness is bounded by:λ ≥ max πs⊂πg Ns 2 Ng 2 • Ng•n l +d(πg,nm)Ns•n l +d(πs,n kπ s ) , where k πs = arg min i∈πs {n i } .(15) Proof In a coalition structure with N clients, denoted by π g = {1, 2, ..., N }, where each client possesses a local dataset of size n j , the concept of λ-egalitarian fairness stipulates that erri(πg) errj (πg) ≥ λ, n i ≤ n j . In a context where clients are purely selfish, the coalition π g maintains core-stable if, for any potential sub-coalition π s ⊂ π g , there is at least one client who prefers π g over π s , this means that ∃i ∈ π s , u i (π g ) ≤ u i (π s ), or equivalently, ∃i ∈ π s , err i (π g ) ≤ err i (π s ). According to the egalitarian fairness definition, it holds that,EQUATION)To satisfy for ∀π s ⊂ π g , ∃i ∈ π s , err i (π g ) ≤ err i (π s ), the lowest λ is bounded by Equation (17) .EQUATIONBased on Lemma 3, we denote m = arg max We first give the lowest fairness bound λ for a specific π s ,EQUATIONBased on Lemma 1, the above equation can be transformed as,EQUATION)Denote N s = i∈πs n i and N g = i∈πg n i , we have,EQUATION)Multiplying each side of the above equation byEQUATION)Thus, the lowest fairness bound λ satisfies,EQUATION)Taking the derivative of f RHS with respect to σ, we have:EQUATION.(EQUATIONForf 1 = N s • i∈πg,i̸ =m n 2 i -N g • i∈πs,i̸ =kπ s n 2 i, since the growth rate of i∈πs,i̸ =kπ s n 2 i is faster than that of N s , it is reasonable to assume that f 1 is decreasing with respect to N s . The minimum value occurs when π s = π g , at which point,EQUATION)Also, f 2 = N s • (N g -n m ) 2 -N g • N s -n kπ s 2 > 0: f 2 = N s • (N g -n m ) 2 -N g • N s -n kπ s 2 = N s N g (N g -N s ) -N g n 2 kπ s + N s n 2 m + 2N g N s (n kπ s -n m ) = N g (N g N s -N 2 s -n 2 kπ s + n 2 m + 2N s (n kπ s -n m )) = N g (N g N s -N 2 s >0 + (n m -N s ) 2 -(n kπ s -N s ) 2 >0).Based on the above derivation, we can conclude that f ′ RHS,σ > 0. Therefore, the maximum value of f RHS occurs at the maximum value of σ 2 . Given our assumption that n i ≤ µe σ 2 , ∀i = 1, ..., N , the maximum of σ 2 is µe n l , l = arg max i∈πg {n i }. Consequently, the Eq. ( 23) transforms into,EQUATION)Above all, we can determine the optimal egalitarian fairness bound to maintain the core stability of the coalition structure π g ,EQUATIONCorollary 2 The core-stable grand coalition π g , comprising all selfish clients, can asymptotically achieve strict egalitarian fairness, provided that the local dataset sizes of all clients are equal. Proof Let's consider a grand coalition π g that consists of M clients, and a subset π s ⊂ π g that consists of m clients. According to Proposition 2, when the local dataset sizes of all clients are equal, the optimal egalitarian fairness that can be achieved is:EQUATIONTherefore, it is proven that the grand coalition π g is capable of achieving strict egalitarian fairness.Proposition 3 (Optimal egalitarian fairness under purely welfare altruistic behaviors) Considering all clients act purely welfare altruistic, the grand coalition π g remains core-stable if the achieved egalitarian fairness is bounded by:λ ≥ max πs∈πg min Ns 2 Ng 2 • Ng•n l +d(πg,nm) Ns•n l +d(πs,f opt πs,1 ) , Nc 2 Ng 2 • Ng•n l +d(πg,nm) Nc•n l +d(πc,f opt πs,2 ), where k πs,1 = arg min i∈πs {min f ∈Fi∩πs n f } , k πs,2 = arg min i∈πs {min f ∈Fi∩πc n f } , f opt πs,1 = arg min f ∈F k πs ,1 ∩πs n f , f opt πs,2 = arg min f ∈F k πs,2 ∩πc n f . (30) Proof In a context where clients are purely welfare altruistic, the coalition π g maintains core-stable if, for any potential sub-coalition π s ⊂ π g , there is at least one client who prefers π g over π s , this means that ∃i ∈ π s , u i (π g ) ≤ u i (π s ), or equivalently,EQUATION)where π c = π g \ π s is the complement of π s . Consequently, to maintain the stability of FL, we can determine the lower bound of λ by,EQUATION)The fairness bound λ with respect to a specific π s is,EQUATIONwhere, EQUATION)Following the same derivation as in the proof of Proposition 2, the above equation is equivalent to,EQUATION)EQUATION)Above all,we can determine the optimal egalitarian fairness bound to maintain the core stability of the coalition structure π g ,EQUATIONA.4.4 Proof of Corollary 3Corollary 3 The core-stable grand coalition π g , consisting of purely welfare clients, can asymptotically achieve strict egalitarian fairness if all clients are friends with the client possessing the smallest dataset size and N g → ∞.Proof When all clients are friends with the client possessing the smallest dataset size, it holds that f opt πs = m or f opt πc = m. Assume that f opt πs = m, Corollary 3 can be proven by mathematical induction as follows. Define the hypothesis H 0 as:EQUATIONWhen π s contains only one player π s = {n j }, we have,nj 2 Ng 2 • Ng • n l + d(πg, nm) nj • n l + d(πs, nm) equal to 0 Ng →∞ = nj Ng approaching 0 + nj n l • i∈πg n 2 i -n 2 m i∈πg ni 2 approaching 0 + nj n l • (Ng -nm) 2 N 2 g less than 1 ≤ 1. (39)Assume that the hypothesis H 0 holds when π s contains k players, for π ′ s = {π s , n} containing k + 1 players where the new player has a dataset size of n, it holds that,EQUATIONwhereEQUATIONSince H 0 holds for any π s , the terms in the numerator are each smaller than the corresponding terms in the denominator. Thus, it follows that,EQUATIONTherefore, the hypothesis H 0 is established. A similar mathematical induction process can be applied to π c . Thus, λ optimal can approach less than 1 under the given conditions, proving the Corollary 3.Proposition 4 (Optimal egalitarian fairness under purely equal altruistic behaviors) Considering all clients act purely equal altruistic, the grand coalition π g remains core-stable if the achieved egalitarian fairness is bounded by:λ ≥ max πs∈πg |F kπ s |•Ns 2 Nc 2 Ng 2 • Ng•n l +d(πg,nm) Q ,where k πs = arg min i∈πsEQUATIONProof In a context where clients are purely equal altruistic, the coalition π g maintains core-stable if, for any potential sub-coalition π s ⊂ π g , there is at least one client who prefers π g over π s , this means that ∃i ∈ π s , u i (π g ) ≤ u i (π s ), or equivalently,EQUATIONwhere π c = π g \ π s is the complement of π s . Consequently, to maintain the stability of FL, we can determine the lowest fairness bound λ by,EQUATION)The lowest fairness bound λ with respect to a specific π s is,EQUATIONwhere,m = arg max i∈πg {err i (π g )} = arg min i∈πg {n i } , k πs = arg max i∈πs 1 |Fi| f ∈Fi∩πs err f (π s ) + f ∈Fi∩πc err f (π c ) = arg min i∈πs 1 |Fi| f ∈Fi∩πs n f + f ∈Fi∩πc n f . (47)Following the same derivation as in the proof of Proposition 2, the above equation is equivalent to,EQUATIONwhere,EQUATIONAbove all, we can determine the optimal egalitarian fairness bound to maintain the core stability of the coalition structure π g ,EQUATIONA.4.6 Proof of Proposition 5Proposition 5 (Optimal egalitarian fairness under friendly welfare altruistic behaviors) Considering all clients act friendly welfare altruistic, the grand coalition π g remains core-stable if the achieved egalitarian fairness is bounded by:λ ≥ max πs∈πg min Ns 2 Ng 2 • Ng•n l +d(πg,nm) Q1 , Ns 2 Nc 2 Ng 2 • Ng•n l +d(πg,nm) Q2, where k πs,1 = arg min i∈πs w• n i + (1 -w) • min f ∈Fi∩πs∪{i} n f , k πs,2 = arg min i∈πs {w • n i + (1 -w) • min f ∈Fi∩πc n f } , f opt πs,1 = arg min f ∈F k πs ,1 ∩πs∪{kπ s ,1} n f , f opt πs,2 = arg min f ∈F k πs,2 ∩πc n f Q 1 = N s • n l + w • d(π s , n kπ s,1 ) + (1 -w) • d(π s , f opt πs,1 ) Q 2 = N 2 c • w • N s • n l + d(π s , n kπ s ,2 ) + N 2 s • (1 -w) • N c • n l + d(π c , f opt πs,2 ) .(51) Proof In a context where clients are friendly welfare altruistic, the coalition π g maintains stability if, for any potential sub-coalition π s ⊂ π g , there is at least one client who prefers π g over π s , this means that ∃i ∈ π s , u i (π g ) ≤ u i (π s ), or equivalently,EQUATIONwhere π c = π g \ π s is the complement of π s . Consequently, to maintain the stability of FL, we can determine the lowest fairness bound of λ by,EQUATION)The lowest fairness bound λ with respect to a specific π s is,EQUATIONwhere,EQUATIONFollowing the same derivation as in the proof of Proposition 2, the above equation is equivalent to,EQUATIONwhere,EQUATION)Above all, we can determine the optimal egalitarian fairness bound to maintain the core stability of the coalition structure π g ,EQUATIONA.4.7 Proof of Proposition 6Proposition 6 (Optimal egalitarian fairness under friendly equal altruistic behaviors) Considering all clients act friendly equal altruistic, the grand coalition π g remains core-stable if the achieved egalitarian fairness is bounded by:λ ≥ max πs∈πg (|Fk πs |+1)•Ns 2 •Nc 2 Ng 2 • Ng•n l +d(πg,nm) Q , where k πs = arg min i∈πs w • n i + (1 -w) • 1 |Fi|+1 • f ∈Fi∩πs∪{i} n f + f ∈Fi∩πc n f , Fs = F kπ s ∩ π s ∪ {k πs } , Fc = F kπ s ∩ π c , Q = w • |F kπ s | + 1 • N 2 c • N s • n l + d(π s , n kπ s ) + (1 -w) • N 2 c • f ∈ Fs (N s • n l + d(π s , n f )) + N 2 s • f ∈ Fc (N c • n l + d (π c , n f )) .(59) Proof (Proposition 6) In a context where clients are friendly equal altruistic, the coalition π g maintains core-stable if, for any potential sub-coalition π s ⊂ π g , there is at least one client who prefers π g over π s , this means that ∃i ∈ π s , u i (π g ) ≤ u i (π s ), or equivalently, ∃i ∈ π s , wEQUATIONConsequently, to maintain the stability of FL, we can determine the lowest fairness bound of λ by,EQUATION)The lowest fairness bound λ with respect to a specific π s is,EQUATIONwhere,EQUATION)Following the same derivation as in the proof of Proposition 2, the above equation is equivalent to,EQUATION)where,EQUATIONEQUATIONAbove all,we can determine the optimal egalitarian fairness bound to maintain the core stability of the coalition structure π g ,EQUATIONA.4.8 Fairness Bound Analysis under Generalized-Mean-Form Utility FunctionTaking the weighted power-mean welfare function [34] to construct utility function as an example and considering scenarios where clients exhibit friendly equal altruism, the utility of the i-th client is:EQUATION)The coalition π g remains core-stable if, for any potential sub-coalition π s ⊂ π g , there is at least one client who prefers π g over π s . This implies that ∃i ∈ π s , u i (π g ) ≤ u i (π s ), or equivalently,  |Fi| i=1 w i err q i (π g )   1 q ≤   w i • err q i (π s ) + f ∈Fi∩πs w f err q f (π s ) + f ∈Fi∩πc w f err q f (π c )   1 q.(69) Consequently, to maintain the stability of FL, we can determine the lowest fairness bound of λ by,|Fi| i=1 w i • max{err q i (πg)} N i=1 λ 1 q ≤ min πs⊂πg max i∈πs w i • err q i (π s ) + f ∈Fi∩πs w f • err q f (π s ) + f ∈Fi∩πc w f • err q f (π c ) 1 q.(70) The lowest fairness bound λ with respect to a specific π s is,EQUATIONwhere,π c = π g \ π s , m = arg min i∈πg {n i }, k πs = arg min i∈πs w i • n q i + f ∈Fi∩πs w f • n q f + f ∈Fi∩πc w f • n q f , Fs = F kπ s ∩ π s , Fc = F kπ s ∩ π c . (72)Following the same derivation as in the proof of Proposition 2, the above equation is equivalent to,EQUATIONwhere,EQUATION)Above all,we can determine the optimal egalitarian fairness bound to maintain the core stability of the coalition structure π g ,EQUATIONA.5 Additional experimentsExperiments under heterogeneous client behaviors involved configuring the two clients to exhibit purely selfish behavior while the rest were modeled as friendly equal altruistic as in Figure 4 . The results verified that our theoretical bound (green dashed line) continued to align with the empirical fairness results (red solid line) under heterogeneous client behaviors. Lastly, we examined the adaptability and task-independence of the proposed egalitarian fairness bound through another linear regression task, as illustrated in Figure 5 . The experiment underscored that our theoretical bound (green dashed line), independent of task-specific hyperparameters θ i or ϵ i , consistently matched the actual fairness achieved within a core-stable grand coalition (red solid line). Justification: We provided the code in the supplemental material. Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 


Decision: The reviewers all saw merit in the contributions of the paper, with some having concerns about the significance of the results for practical applications, seeing various important aspects underexplored.  This lead to some feeling that the contribution of the paper as currently written is borderline.  The author response included some additional results that move things in a positive direction in this regard, but there is still room for further refinement.

Reviews: review: paper_summary: paper_summary: This paper rigorously answered a critical question regarding fair federated learning: Does egalitarian fairness lead to instability? It analyzed and presented the influence of clients’ altruistic behaviors and the configuration of the friend-relationship network on the achievable egalitarian fairness within a core-stable federated learning (FL) coalition.

The optimal egalitarian fairness bounds without compromising core stability are explored theoretically. These novel insights can be leveraged to establish appropriate egalitarian fairness in improving the alignment of FL processes with societal welfare and ethical standards.
strength_weakness: strength_weakness: - In subsections 4.2 and 5.1, it is better to briefly clarify what the colors (blue, red, orange) mean in this context. Do you intend to use colors to better illustrate the results in Table 1? 

- In Line 261, though "Proofs for propositions are given in Appendix" was stated, and each proof can be located, it is better to make a clearer pointer for each proposition. For example, which location of the proof in the Appendix is for which proposition? 

- In Line 307, Example 1 is used to show which proposition? Better to clarify.
questions: questions: Please refer to the identified weak points for details.
limitations: limitations: NA
paper_summary: paper_summary: This paper examines the relationship between egalitarian fairness concepts and stability in federated learning, where multiple clients collaboratively train a shared model while retaining local data privacy. Egalitarian fairness promotes uniform model performance across clients, but this can reduce performance for data-rich clients, potentially causing instability, as these clients might leave for better-performing coalitions. This work employs cooperative game theory and social choice to frame FL systems as altruism coalition formation games, suggesting that core instability issues are linked to clients' altruism and their network of relationships. The authors propose optimal egalitarian fairness bounds that maintain core stability under various altruistic behaviors, suggesting that egalitarian fairness does not necessarily lead to instability.
strength_weakness: strength_weakness: I'm left with some questions about the motivations for the model, though the authors do a good job motivating it with prior work. I'm also left wondering whether some results and assumptions can be generalized, as the analysis is somewhat rigid; the paper would be much stronger if some results held in greater generality. I also question the model of FL used here (FedAvg), as it simply averages over model parameters (it would be nice to see models where clients submit gradient updates rather than complete models, and also where the central authority itself optimizes for egalitarian or other fairness objectives, rather than averaging). Finally, I argue the client utilities don't fully reflect the impact of overfitting.
questions: questions: Clearly the FedAvg rule for $\theta$ (line 126) promotes privacy in some sense, but with modest added noise, is the mechanism differentially private?

I would argue that definition 1 is more closely related to the demographic parity concept of equalized error [10], not egalitarian fairness. I would claim that in loss contexts, egalitarian welfare (or more aptly, malfare) is simply the max over average losses of agents [8], but inequality between agents is not antithetical to egalitarian fairness, rather egalitarianism is indifferent to the performance of high performing groups so long as low performing groups cannot be improved. I suppose this is more of a terminology issue, though I do ask if an additive version of this could be explored, where error values are compared to the maximum per group error.

Lemma 1 is quite confusing to me. $\mu_{e}$ depends on i, but notation does not reflect this. By expected value of the variance, you seem to mean expected value of the raw variance, but it's not clear why I care about that quantity? Is this assuming realizability, and therefore the square here corresponds to square loss? Is the method specific to square error though? Why not work directly in terms of loss? These inferences are somewhat confirmed in section 6, though I suspect a method is not really specific to square error, and I claim a more general description in terms of generic loss and loss variance would be easier to follow.

I also think this result does not properly consider overfitting, so I don't think it's very well motivated in a machine learning context. Loss variances should be model (parameter) dependent, so if this is in terms of minimum variance, I suspect it's a reasonable lower bound, and if maximum variance is considered (and multiplied by the log of the model class cardinality or some similar capacity measure), it may be a reasonable upper bound? It's also not totally clear to me which quantities refer to distributions and which refer to data sets in this definition. I would be interested to see a more general analysis, in terms of quantities like Rademacher averages that better characterize overfitting in machine learning [1,2,5]. Some discussion of how this applies to fair learning in particular would be appreciated, especially as works like [9] show that the process of optimizing fair ML objectives has a regularizing effect and can actually reduce overfitting.

In lemmas 2,3,&4, the requirement is that this holds for all i, correct? These are a bit tricky to read, because $\mu_{e}$ depends on i, although $\sigma^{2}$ does not, and the notation does not reflect this. Moreover, it seems unfortunate that we reach the same conclusion in all three cases, is this necessary (i.e., are there counterexamples to improvement in each?).

I think these results can only be true if client distributions are drawn IID. This should be clarified in lemma 1. This is a big assumption, since I might expect friends’ distributions to be correlated (which incentivizes them to deviate, harming core stability). But I also need to ask, is the variance between distributions the sample variance or the distribution variance? I think this matters a lot, since presumably there are relatively few agents, and if the sample variance is what matters, then why can't we condition on the sample (in which case independence wouldn’t matter)?


In section 4.1, I think it would be nice to generalize this idea to define a client's utility function as some welfare function of their own value and the value of their friends. I think this would simplify the presentation, but also you would be able to use more sophisticated concepts, like weighted power-means.

Moreover, since the same result holds for purely altruistic and friendly altruistic cases, this immediately implies that the client utility functions can be the utilitarian maximum social welfare (malfare) function [6,11], and some set of weighted utilitarian welfare (malfare) functions. I suspect it could easily generalize to any weighted utilitarian welfare function. I would also be very interested to see if these results held for any unweighted power-mean welfare function, any weighted power-mean welfare function, or any Gini malfare function [6], as they do in some sense lie between welfare altruism and equal altruism, though I don't think these results follow directly from your stated lemmas.



Minor points:

149 “satisfy” should be “satisfies.” Moreover this definition feels a bit redundant with (1).

158 It seems strange to mix a sociological definition of friend with a mathematical definition. Moreover, while I am not a sociologist, it seems wrong that “friend” would be the most intimate trusted voluntary category. If so, what is a best friend, and where does that leave a partner? But is this discussion even necessary?

Perhaps definitions 2 3 and 4 can be merged to describe the coalitional game?

163 “does not exist” to “does not exist a”


171 I dislike this terminology. I would describe both types of altruism as considering different types of the welfare among friends, but I would term them “egalitarian altruism” and “utilitarian altruism,” respectively [1].
limitations: limitations: FedAvg

I don't love the FedAvg aggregation rule of line 126 (though I appreciate that the authors analyze an established model). This seems appropriate when groups train relatively similar models on their own, and the lost surface is relatively smooth. I suspect this is a decent rule when each client has the same optimal model, but due to limited sampling wouldn't identify this from their own data.

The approach seems particularly problematic for non-convex loss surfaces, or models with symmetry (e.g., neural networks or mixture models where averaging the parameters of two identical models can produce a completely different model). I’d like to see more discussion of these limitations (or generalization of the model).

However, I would like to see some consideration of other models of FL, for instance when clients send gradient updates, rather than raw model parameters. From reading the introduction, I expected the FL to be trained to incentivize egalitarian fairness, but this simple averaging rule is neither utilitarian optimal, nor is it egalitarian optimal. Works like [3] consider sampling implications for this, and biased SGD analyses [4,7] also seem appropriate to discuss, at least in related work.

Overfitting

I would also like to see some consideration of overfitting. It seems tautological that nonaltruistic agents would prefer to train their own model when only training loss is considered, and while altruism may incentivize them to share their data, there is also the non-altruistic effect of reduced overfitting. It seems this would also disincentivize the formations of small coalitions, so I would be very interested to see what impact these factors have on the work.


References:

[1] An axiomatic theory of provably-fair welfare-centric machine learning
C Cousins
Advances in Neural Information Processing Systems 34, 16610-16621

[2] Revisiting fair-PAC learning and the axioms of cardinal welfare
C Cousins
International Conference on Artificial Intelligence and Statistics, 6422-6442

[3] Jacob D Abernethy, Pranjal Awasthi, Matthäus Kleindessner, Jamie Morgenstern, Chris Russell, and Jie Zhang. Active sampling for min-max fairness. In International
Conference on Machine Learning, volume 162, 2022.

[4] A guide through the zoo of biased SGD
Y Demidovich, G Malinovsky… - Advances in Neural …, 2024 - proceedings.neurips.cc,

[5] Uncertainty and the social planner’s problem: Why sample complexity matters
C Cousins
Proceedings of the 2022 ACM Conference on Fairness, Accountability, and …

[6] Algorithms and Analysis for Optimizing Robust Objectives in Fair Machine Learning
Cyrus Cousins

[7] Hu, Yifan, et al. "Biased stochastic first-order methods for conditional stochastic optimization and applications in meta learning." Advances in Neural Information Processing Systems 33 (2020): 2759-2770.

[8] John Rawls. A theory of justice. Harvard University Press, 1971.

[9] Cousins, Cyrus, I. Elizabeth Kumar, and Suresh Venkatasubramanian. "To Pool or Not To Pool: Analyzing the Regularizing Effects of Group-Fair Training on Shared Models." International Conference on Artificial Intelligence and Statistics. PMLR, 2024.

[10] Dwork, Cynthia, et al. "Fairness through awareness." Proceedings of the 3rd innovations in theoretical computer science conference. 2012.

[11] Deschamps, R., Gevers, L.: Leximin and utilitarian rules: A joint characterization. Journal of Economic Theory 17(2), 143–163 (1978)
paper_summary: paper_summary: The authors explored the impact of egalitarian fairness on the stability of Federated Learning (FL) systems. FL allows multiple clients to train a global model collaboratively without sharing their local data, thus preserving privacy. The authors addressed the concern that achieving egalitarian fairness, which aims to ensure uniform model performance across clients, might destabilize the FL system by prompting data-rich clients to leave. The authors modeled FL systems as altruism coalition formation games (ACFGs) and propose theoretical bounds for egalitarian fairness that maintain core stability under various types of altruistic behaviors. They disproved the notion that egalitarian fairness necessarily leads to instability and provided experimental validation of their theoretical bounds.
strength_weakness: strength_weakness: 1. The experiments conducted to validate the theoretical bounds are limited to relatively simple tasks, such as mean estimation and linear regression with a fixed number of clients. While these experiments demonstrate alignment with the theoretical results, extending the validation to more complex and diverse FL scenarios would strengthen the empirical evidence. 
2. The sensitivity of the proposed fairness bounds to variations in client behavior and network topology is not fully explored. While the authors provided insights into different types of altruistic behaviors and their impact on stability, a more detailed analysis of how changes in client behavior or the structure of the friends-relationship network affect the theoretical bounds would add depth to the findings.
3. The use of clients' and client's is not rigorous enough (such as Line 22 and Line 128) and needs to be carefully checked.
questions: questions: 1. How do the proposed fairness bounds perform in more complex FL scenarios?
2. How sensitive are the theoretical bounds to variations in client behavior and network topology? Are there specific conditions under which the bounds might fail to ensure stability?
limitations: limitations: The authors have adequately addressed the limitations and potential negative societal impacts of their work in Section 7. They have acknowledged the influence of clients' altruistic behaviors and the configuration of the friend-relationship network on the stability and fairness within federated learning (FL) coalitions. They also identified potential limitations such as the impact of proportional fairness and the necessity to design suitable incentive mechanisms to retain clients when high egalitarian fairness is mandatory.
paper_summary: paper_summary: The paper builds on a previous model of FL to study trade-offs between core stability and egalitarian fairness when agents exhibit altruistic behaviors. The authors provide egalitarian fairness bounds under core stability solutions across different cases of altruism. There is also a small experimental part where the authors verify their theoretical results over heterogeneous altruistic behaviors as well.
strength_weakness: strength_weakness: - I am not sure if the authors adequately address their intended question: Does Egalitarian Fairness Lead to Instability? As I read the text, I expected the authors to design egalitarian fair solutions and assess their stability. However, they focus on explaining how high levels of egalitarian fairness are expected under core stability.  

- In my view, the most important results are in Section 5.2. However, I am not sure how significant and interesting these findings are. It is clear that there is a trade-off between core stability and egalitarian welfare since they can be seen as two different fairness constraints with quite different goals. So, it is quite expected that we cannot have perfect egalitarian fairness when the goal is to ensure that the grand coalition is stable. Moreover, regarding the bounds of lambda, which are these long expressions, I am quite unsure how intuitive and helpful they can be.

- The findings in Section 5.1 are not surprising at all. When the utility function of the agents changes, it is expected that a core stable solution will change, and different egalitarian welfare levels will be achieved under different solutions.

- The experiments are conducted with an extremely small number of agents, namely 4. I would expect experiments with at least, say, 15 agents for the results to be more interesting.
questions: questions: - What do we learn from the experiments? What is the take away message?

- Are the bounds that you provide in Section 5.2 tight?
limitations: limitations: No limitations

Comments: title: My comments have been well addressed
No further questions
comment: Thank you for the authors' response. My comments have been well addressed.
I would like to thank the authors for their answer and the clarifications. I do not have any further questions at this point. I increase my score based on the new experiments and the further explanation regarding the scope of the paper.