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 2024 poster (2024)
Keywords: Fairness
Stability
Federated Learning
Altruism
Primary area: fairness

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.

Does Egalitarian Fairness Lead to Instability? The Fairness Bounds in Stable Federated Learning Under Altruistic Behaviors
Jiashi Gao', Ziwei Wang' Xiangyu Zhao", Xin Yao*, Xuetao Weil*
Southern University of Science and Technology
University of Birmingham
City University of Hong Kong 4 "Lingnam University
(12131101, 12250053) htw.m/aa....m......amaaammmm
sustech. edu.
xy xy.zhao@cityy. edu, hk
xinyaoθln.edu hk
weixt@sustech.edu.
Abstract
Federated learning (FL.) offers machine learning paradigm that protects privacy, allowing multiple clients collaboratively train a global model while only access- ing their local data. Recent research in FL. has increasingly focused on improving the uniformity 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, 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, cer:: Does egalitarian fairness lead to instability? Drawing from game theory and social choice theory, we initially characterize fair FL systems altruism coalition formation games (ACFGs) and reveal that the instability issues emerging from the pursuit of egalitarian fairness significantly related to the clients' altruism within the coalition and the configuration of the frienns-relationshii 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 FI. settings.
work rigorously addresses the critical con-
Introduction
Federated learning (FL) has emerged as a significant learning paradigm in which clients utilize their local data to train 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 [ 2 B. In vanilla FLs, different clients sharing the same global model may experience varying performance (i.e., error) due to differences in the amount
*Corespondiigg author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 450 6 7 8 D have focused on ensuring that the performance of global model across the clients roughly comparable or even equal, termed as "egalitarian fairness". In FL.s 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 [IO [1] of the FL. In game theory, coalition is said to be core-stable if no sub- coalition 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 payoff greater than it was allocated in the original coalition. Otherwise, the original coalition is said to be blocked.
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 fiiend--reaatoonsiis 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 diagnostic model for welfare purposes can also be regarded 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 certain degree from optimal performance
Prior works 12
[7 18). Considering the rrenddrelationships.. 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 player's 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 the optimal egalitarian fairness that a stable FL can achieve?
Our contributions. We initiate discussions 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 g.
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 core-stable grand coalition, which is also Pareto-optimal in local errors.
In Section 5 we demonstrate in detail that egalitarian faireess does not necessarily lead to instability; rather, it depends on the behaviors of the clients and the topology of the rration-rl 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
2

---

establishing tight faimess bounds, part of the contribution of this work lies in the analysis methodology used 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 faimess bounds with the empirically achieved fairness in fair FLs.
2 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 [5], 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 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 [2] has systematically introduced certain notions of altruism into existing game- theorete models in both con-coopeete and cooperative games. Kerkmann et al. 29 have formally distinguished three degrees of altruism: selfish-firg first, equal-treatmen, and altruistic- 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 both the player and their friends need to be considered.
3 Preliminaries
Model and assumptions. Let's consider setup involving N clients, where the i-client possesses a local dataset D; of size n,, The local datasets are samples drawn from data distribution P. (z) Each client can train model M with parameter 0; locally, resulting in P(M(I, 0,) Ir) + P. (z) 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, 0 Ex5x(1.0)
n4
The above weighted aggregation known as FedAvg 31 is a widely used FI. aggregation mechanism. We measure the aggregated global model's performance on the client's local dataset in the coalition through the expected error (T)) = Ee. Mz, 0) - y/I]- A lower err;(T) implies that the coalition is more valuable for the i-th client. To determine 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. [1]], which develops the closed-form local errors as in Lemma [ 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.
3

---

Lemma (Corollary 4.3 in (12V) In an FL setting with N clients, each client possesses a local dataset D; of size ni. The local dataset of each client D; with mean 8 and standard deviation e,, where (0., () ~ A. When FL trains a global model for mean estimation and employs FedAvg for aggregation, the expected mean squared error (MSE) for a client with ne samples within coalition a is as follows,
+ o² Eserssi (ESErISti Rj
err((T)= = He
(I)
Ejes
where pe (o, and a² var (0:) denotes the variance between the means of the clients' local datasets.
[c]] denotes the expected value of the variance of the dataset distribution,
Fairness definition. We explore egalitarian fairness in Definition I fairmess notion that assesses whether the global model exhibits equitable performance across chents with varying data resources. Definition 1 (Egalitarian fairness) For the clients within a coalition holding datasets of vary- ing sizes {ni, n...... nN and experiencing errors (erri(T) erre()),..., "..,,,rrrr,,, erTN (TT), the coalition structure satisfy X-egalitarian fairness if there exists a constant À such that,
(rr((n) erry (T))
2 X, S nz-
(2)
Here, À is the fairness bound.
When À the coalition ı is said to satisfy strict egalitarian faimess.
4
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 Appendix. Definition 2 (Value) In the context of collaborative gaming, the value quantifies the payoff accrued to the i-th player as 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 's local dataset as ve(TT) = -err; (T)).
Definition (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,, 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 Tg (the coalition consisting of all players) is considered to be core-stable if there does not exist nonempty sub-coalition n. C Tg such that where > is used to denote a preference relation. In other words, no nonempty
T. >: for Vi sub-coalition n. C. Fg blocks Tg.
Based on the above notions, we define altruism in Fl. as the client's choice to remain within exit the existing coalition æ, influenced by the acquired values their friends ff E F,. Previous research on egalitarian fairness has primarily focused 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 for the friend who is 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 minjeF, ({Vy(T)}) and
F. Σ (T).,, respectively.
4.1 Client behavior
We divide client behavior into three types based on the degree of altruism: purely selfish (non- altruistic), purely altruistic and friendly altruistic.
Purely selfish: purely selfish client opts to stay or leave the current coalition x, based solely on its own value, i.e., according to value definition, purely selfish client prefers to join a coalition that offers a lower value o; and conversely, to leave a coalition that results in a higher value v,. The utility function of purely selfish client is defined as u. (T) 22 (TT).
ps

---

. Purely altruistic: A purety 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 ut (πr) max ([v((T)}) and pa (TT)
[F EeP, (T(T), respectively.
1
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 as u, o (TT) = w (a(()) + (1 -w----
FFF (ey(T)) and (T) w (T( + (1 w) |iI+ EiERuto (T) respectively. where w 10 is selfishness degree parameter.
Given two coalitions 1 and T2. #1 by T2 occurs if and only if (11 S (, Donahue et al. [5] have established the sufficient conditions for achieving core-stability under the assumption of selfish clients, as in I Lemma 2 Building upon their findings, we further introduce these conditions to cover scenarios of altruistic behaviors, as in Corollary |
Lemma 2 (Lemma 10 in (I5)) When clients are purely selfish, for a set of clients with n, S fz. the grand coalition Tg core-stable.
Corollary For a set of players where n, S Lss the grand coalition Rg remains core-stable when the clients are either purely altruistic friendly altruistic. The proof is provided in Appendix A.2
4.2 Altruism hedonic game vs. altruism coalition formation game
views FL as 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; - F; n πe where n, 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 least one client experiencing a lower error. Such core-stable coalition structure contradicts the assumption of rationality among clients. For example, Table [ shows the error and utility of 4 friendly welfare altruistic (w 0.5) clients in the mean estimation task. In fully connected friends- relationship network (Relation in Figure [T. we first employ the AHG model to analyze the FL system. We recognize that the core-stable coalition strueture lstable {(1,2) (3))) (4)) is non-Pareto optimal in local errors as there exists another alternative structure, ie., Hatter the errors are not greater than in Tstable (i.e., err,(Taatees
Existing research [2 14 32
((1,2,3). {4]}, in which
Client
Client
Clienz 1
Client
err; (TT Vi E (1,2,3, 43) and at least one client exhibits less error than that in llstable (i.e., err, err;t(latter) < elri(llataMe) Vi E 21, 2.)). To ensure a core- stable coalition structure that guarantees Pareto optimality and adheres to the rationality assump- tions of the players, we model the FL process with altruistic behavior as an altruism coalition formation game (ACFG), where client's 's utility
Client 3
Client
Client 3
Client
Figure I: Friends-relationship networks: fully con- nected relation (left) and partially connected rela- tion II (right).
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 client's decision to stay or leave 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 [ the core-stable coalition structure of a fully connected friends-relationship network under ACFG, Ilstable = ((1,2, 2, }, is Pareto-optimal in local errors across clients.
Proposition 1 -arreto-ottimality in error, Appendix A.3 Consider the FL system described as ACFG, a core stable coalition structure also Pareto optimal in local errors across all clients.
5

---

Table 1: The error and utility for friendly welfare altruistic clients within fully connected and partially connected friendship networks under AHG and ACFG frameworks, respectively.
U Utility u in AHG (Relation
Utility xf in ACFG
Utility o l in ACFG
Error (=u"))
Coalition
(Relation I)
(Relation II)
Structure
I
2.0
1
2,0
2.0
1
2.0
I
/
[2)
/
2.0
/
2.0
2.0
/
1
/
2.0
/
[3]
/
/
1,0
1
1.0
1.22
1
1
1.22
/
[4)
/
/
1
0.666
1
0.666
/
1.020
/
/
/
0.770
[1,2]
1,5
1.5
/
1.5
1.5
1.5
1.5
1,5
1,5
[2.3]
1,555
0.888
1,555
1.222
1,590
1.256
1,590
1.222
/
[3.4]
/
1.12
0.72
0.92
1.31
1.11
1.31
0.92
[1,3] 1,555
/
0.888
1,555
1.222
1,590
1.256
1,590
1,256
/
[1,4]
1.625
/
0.625
1.625
1.125
1.625
1.125
1.625
0.756
[2,4]
/ 1.625
/ 0.625
1.625
1.125
1.625
1.125
/ 1.625
/ 0.756
[1,2,3]
1,375
1.375
0.875
1.375
1.375
1.125
1,375
1.375
1.125
/
1.375
1.375
1.125
[1,2,4]
1.44
1.44
7 0.64
1.44
1.44
1
1.04
1.44
1.44
/
1.04
1.44
1.44
7 0.82
[1,34]
1.388
/
1.055 0.722
1.388
/
1.222
1.055
1.694
1.527
1.361
1.694
/
1.527 0.888
(2,34)
1
1,388
1.055
0.722
1.388
1.222
1.055
1.694
1.527
1.361
/
1.694
1.222
0.888
112,3,44
1.306
1.306
1.020
0.734
1.306
1,306
1.163
1.020
1.306
1.306
1.163
1.020
1.306
1.306
1.163 0.877
5 Egalitarian fairness bound in core-stable federated learning
5.1 Does egalitarian fairness lead to instability?
To achieve egalitarian faimess in FL
resource-advantaged clients may sacri- fice local error to improve error uniformity of global model across all participants, creating 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 in- stability". As demonstrated in Table [I] the most egalitarian fair coalition structure is grand coalition, Hl = [my] = [11,2,, 3,4, with a fairness bound = 1.306/0.734 ~ 1.78. When all clients purely selfish and fo- cus solely on minimizing their local error, the coalition structure He is not core-stable. The current core stable coalition structure Sstable ((1, 3) {4]} with faimess bound X = 1.375/0.66 & 2.06. However, when clients exhibit altruistic behavior, and the reland--elationship network is fully connected (Relation I), the most egalitarian fair coalition structure Hstable = Il {11, 2, 3, } with 1.306/0.734
4
5 20
Table 2: Notation Definitions.
Notation
Description
The complement coalition of coali- tion T.. Te Tg. \ T.
N₂
The sum of the dataset sizes my N. = Σie=, nk.
No
The of the dataset sizes in m.:
No -ie.." n4. The sum of the dataset sizes in the grand coalition: N₂ Eie,, ni-
1.78 is also core stable. The finding demonstrates whether "egalitarian fairness leads instabil- ity" is influenced by the clients' behavior. Fur- thermore, when the friends-relationse among the clients changes to partially connected (Relation II), leading to the coalition structure ll. {[1, 2, 3, }}} becoming not core-stable anymore and the current core stable coalition
fairness bound
No
The index of the client with the smallest dataset size Ty.
arg argmin {n,)
network
The index of the client with the largest dataset size in ne. arg max (n.).
structure is IIstable = (11, 2) {4}} with a fairness bound X = 1..75/00.66 R 2.06. The obser- vation demonstrates that, under altruistic behaviors, the diverse relatins-l networks also impact whether "egalitarian fairness leads instability".
From the above analysis, we observe a varying optimal fairness achieved within the core-stable coalition under diverse client behaviors and friends--elationship networks, highlighting 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?

---

5.2 Optimal egalitarian fairness bound
We define distance function to measure the dataset size client relative to other clients within the same coalition T
d(TT, n1) (Eien n
igr n1)²
Given the grand coalition 7g in an FL system consists of set of N clients with local dataset size n, fs and based on the properties of mean estimation task in Corollary the grand coalition Ty is core-stable. In this context, we give the tight egalitarian fairness bound achieved by To in Proposition 2~6 For any coalition H, Tg. unify the common notations to represent the data size within this subset and its complement, as well as the specific individual indices in T2
Proposition 2 (Optimal egalitarian fairness under purely selfish behaviors, Appendix(A.4.I. Con- sidering all clients act purely selfish, the grand coalition Tg remains core-stable if the achieved egalitarian fairness bounded by:
{ N22 N2 Ny + (a Raskka,
Ny. + (dg
1 where kr, arg wergmin,,,, (ni).
A 2 max Crg
Proposition demonstrates that an increase in the heterogeneity of clients' local dataset sizes-reflecti by the difference between the smallest dataset size overall and those within any given subset coalition- achievable egalitarian fairness of a core-stable grand coalition becomes poorer. Furthermore,
obtain a sufficient condition for achieving strict egalitarian fairness () 1) in core-stable coalition with purely selfish clients based on Equation (4).
Corollary 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. The proof is given in Appendix (4.4.)
Proposition 3 (Optimal egalitarian fairness under purely welfare altruistic behaviors, Appendix A.4.3) Considering all clients act purety welfare altruistic, the grand coalition Tg remains core-stable if the achieved egalitarian fairness is bounded by:
min N-2 No v
Ny g. N 2 N."
X 2 EaX
Nomi
No- pope
where
(5)
km,,1 arg min munin k = arg minlex, (minseronn,yy) popt arg min fR.,,. De, n ST.22 arg min n..
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 more relaxed condition for achieving strict egalitarian fairness as in Corollary 3
Corollary The core-stable grand coalition aa. consisting of purely welfare clients, can asymptoti- cally achieve strict egalitarian fairness if all clients are friends with the client possessing the smallest dataset size and Ng + sc. The proof is given in Appendix[A.44
Proposition 4 (Optimal egalitarian faiita under purely equal altruistic behaviors, Appendix A.4.5) Considering all clients act purely equal altruistic, the grand coalition Tg remains core-stable if the achieved egalitarian fairness is bounded by:
[2., I.N,N. N₂¹
X max H.E
Q
where
(6)
n1): Q -N3 Eser n., (Ns + ((Ts, + N2 Exer no, (No. ny + d(Fey
li, arg min men, [ET (ESERim ny n ESERinE nz)
Proposition 4 shows that the egalitarian fairness bound for purely equal altruistic clients influenced by the gap between the smallest dutaset size overall and the weighted sum of dataset sizes within any given Friends-relaionnsen bounds in the context of friendly altruism behavior are shaped by two factors: (1) the heterogeneity
network. According to Propositions and the egalitarian fairness
7

---

of clients' local dataset sizes and (2) the difference between the smallest dataset size in the grand coalition and either the smallest dataset size or weighted sum of dataset sizes within established friends-relationship networks. The selfishness degree parameter (w) balances the relative significance of these two factors.
Proposition 5 (Optimal egalitarian fairness under friendly welfare altruistic behaviors, Appendix A.4.0p Considering all clients act friendly welfare altruistic, the grand coulition mg remains core- stable if the achieved egalitarian fairness is bounded by:
A max R.
min
N,2 Na
No dd me)
N. 2 No
No To- --dt--dl..g
Q1
Q2
where
k arg argminger, {w- {w.m: n4 (1 w) u n5)
2 2 arg millieo, {w + w) minser.na Rfj,
(7)
jont arg min SEFU NM,Ut )) f = arg min SEF= 2 Tif
Q1 = N. mi + d(TT. nkk + (1 w)- (T
Q2 N (N, n4 d( n)), + N3 (1 ww- (Ne + dim l2,2))
Proposition 6 (Optimal egalitarian fairness under friendly equal altruistic behaviors, Appendix
A.4.7 Considering all clients act friendly equal altruistic, the grand coalition Fg remains core-stable if the achieved egalitarian faineess is bounded by:
(1 H11)-N,--N -N.
A 2 maX
N₂
where
kx, = arg iin
w Th + (1 -- w) FIIFI (EseRnnLU))) By + EsERino mI)):
(8)
Fs FKF. O n (kr,) ) Fe Frr. ATter
Q w. (IFe... 1) N2 (N.- + d(TTs
(1 (1-w) w)
No E (N, ni + d(TT. + N². Σ (No ni + d (TTT.n))))
SEF.
feR.
The given propositions establish tight egalitarian fairness bounds in core-stable FLs and demonstrate that the achievable egalitarian fairness for collection of clients varies depending the clients' behaviors and fiends-relationship networks. Furthermore, these propositions can be adapted to situations where clients exhibit heterogeneous behaviors within an FL system as follows.
5.3 Heterogeneous behaviors
When client behaviors exhibit heterogeneity in an FL system, the achievable egalitarian fairness for a core-stable grand coalition Tg is determined by the maximum egalitarian faimeess bounds calculated across sub-coalitions formed by clients with homogeneous behaviors.
An example calculate the achievable egalitarian fairness bound under heterogeneous behaviors is as follows: for a set of N clients, where clients E C C= (1,2, .......... S} act selfishly and the remaining act purely welfare altruistic, the achieved egalitarian fairness of ag is bounded by,
Example 1
N N₂
N, my + +( Bem +.-m+dla o. Salersiution) N₂ my t. Pem)
2 max CF,
max
N.2 N,
No min (a(Taa
N
N₂
where
kseffish = arg minl {m+}, (minseF,ns, n Koltruistie,, = arg minler.Y.G (minseROs. ny}.
Kaltruistic.1 arg min C popt
Jaltruistie,1 = arg min FeFt antuisiion Ox, ny, a = arg min FalllfeFe.rrieeee Flattriisti Cx. Rz.
copt
6 Evaluation
In following experiments, we validate the tightness and applicability of the analyzed fairness bounds for the given tasks.

---

Friends-relationshpp network
Purely selfish
Purely welfare altruistic
stable
Coce-stabin
Client
Client
18
Calculated bound
1.5
1.6
Client
Client 3
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Purely equal altruistic
Friendly welfare ultruistic
Friendly equal altruistic
Care stable
stable Calculated bound
Culsulated bound
Calculated
1.5
1.5
1.5
1.0
1.0
1.0
Figure 2: Fully connected: theoretically derived egalitarian fairness bounds (green dashed line) align with empirically achieved egalitarian fairness within the core-stable grand coalition (red solid line) under different client behaviors.
6.1 Settings
To conduct the experiments, first give fair FL framework to implement egalitarian faimesss where a coefficient p is introduced to increase the aggregation weight of clients who received higher
local errors: Ic Σico (na err The preceding discussions are independent of the fair FL Eieo (ncerr)))
framework chosen. We follow up on the task models proposed by Donahue et al. [12] The first case a mean estimation task involving a fixed set of players. Each player has a fixed number of samples, specifically {20, 40, 50, 1003. Each player draws their local data samples from their true distribution with parameters 3 ~ (0,, where the samples are independent and identically distributed (i.i.d)). Here, 0, (i adaptability of this theoretical results, we introduce additional linear regression task with a fixed set of 3 players. Each player has fixed number of samples, specifically (50, 100, 200). Each player draws 2-dimensional input features from their own input distribution, X, X² ~ N(u 0, o
0, 1) and E; 125x Beta(a 8, b 2). To further validate the
1). The output label is drawn from Vd 250 Bela(a 8, b 2). All experiments are conducted on Intel(R) Re) Gold 5318Y CPU @ 2.10GHz.
6.2 Results
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-relationshipp networks (Figure 3). The results demonstrate the alignment between our
theoretically derived egalitarian fairness bound (green dashed line) and the empirically achieved egalitarian faireess 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).
7 Discussion and Limitations
In this section, we outline the scope 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 -here a client's 's payoff is proportional Moreover, for theoretical proofs, our work is built upon the exact-error task models developed by Donahue al. [12]: future work could be extended to more complex collaborative training tasks. Initially, chose the maximum and linear weighting of errors to construct the utility functions
its data contribution-on the stability FL.

---

Client
Client
Client
Client 2
Client I
Client 2
Client
Client
Client
Client
Purely welfare altruistic under Relation
Friendly welfare altruistic under Relution II
Friendly equal altruistic under Relation III
Core-stable
Curu-stable Caloulted bound
Calculated A bound
1.5
155
1.80
Coce-stable
1.55
Celicolnted brand
1.0
1.0
0.4
Figure 3: Partially connected: theoretically derived egalitarian fairness bounds (green dashed line) align with empirically achieved egalitarian fairness within the core-stable grand coalition (red solid line) under different client behaviors.
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.c., weighted power-mean welfare function 34 in Appendix (.nendiix.4.8))
Incentive Mechanisms and Client Behavior Dynamics. As we discover the bounds of egalitarian fairness that stable coalition achieve, practical question arises: How can we correspondingly design suitable incentive mechanisms to retain clients in the coalition when high egalitarian fairness mandatory requirement? Given that altruism closely related to stability when pursuing faimess, further exploration into how various human behaviors- as reciprocity, bounded rationality, risk aversion, and risk tolerance-impact the stability of FLs in achieving specific objectives would be of profound interest.
Overlitting, Centering on exploring the relationship between egalitarian fairness and stability, use the stylized model in Lemma]] which provides closed-form error to derive precise relations and generate insights into faimeess settings in fair FLs. However, overfitting (35) in machine learning leads to uncertainty in the error outlined in Equation [ 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 open area of research; however, approach may still provide a valuable foundation for further exploration.
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 faimess within core-stable federated learning (FL) coalition. Our research has identified the optimal egalitarian fairness bounds without compromising core stability from theoretical standpoint. The outcomes of our research can be leveraged to establish appropriate egalitarian fairness in FL implementation, which plays a crucial role improving the alignment of FL processes with societal welfare and ethical standards.
Acknowledgements
This work was supported by Key Programs of Guangdong Province under Grant 2021QN021 166. Any opinions, findings, and conclusions recommendations expressed in this material those of the author(s) and do not necessarily reflect the views of the funding parties.
10

---

References
[1] Dinh C. Nguyen, Quoc-Vice Pham, Pubudu N. Pathirana, Ming Ding, Aruna Seneviratne, Zihuai
Lin, Octavia Dobre, and Won-Joo Hwang. Federated learning for smart healthcare: A survey. ACM Comput. Surv., 55(3):1337, 2022.
[2] Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Trans. Intell. Syst. Technol, 10(2):1-19, 2019.
[3] Guodong Long, Yue Tan, Jing Jiang, and Chengqi Zhang. Federated Learning for Open Banking. Springer, 2020.
[4] Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning, pages 6357-6368. PMLR, 2021.
[5] Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In International Conference on Machine Learning, pages 4615-4625, PMLR, 2019.
[6] Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. In International Conference on Learning Representations. OpenReviow, 2019.
[7] Zibin Pan, Shuyi Wang, Chi Li, Haijin Wang, Xiaoying Tang, and Junhua Zhao. Fedmdfg: Federated learning with multi-gradient descent and fair guidance. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 9364-9371. AAAI Press, 2023.
[8] Xiaoqiang Lin, Xinyi Xu, See- Kiong Ng. Chuan-Sheng Foo, and Bryan Kian Hsiang Low. Fair yet asymptotically equal collaborative learning. Proceedings of the 40th International Conference Machine Learning, pages 21223-21 21259. PMLR, 2023.
[9] Xiaoqiang Lin, Xinyi Xu, Zhaoxuan Wu, Rachael Hwee Ling Sim, See-Kiong Ng. Chuan-Sheng Foo, Patrick Jaillet, Trong Nghia Hoang, and Bryan Kian Hsiang Low. Chapter 8 fairness in federated learning. In Federated Learning, pages 143-160. Academic Press, 2024.
[10] Jean Lemaire. Cooperative game theory and its insurance applications. ASTIN Bulletin, 21(1):17-40, 1991.
[11] Matthias Hoffjan, Anna Maria Kerkmann, and Jörg Rothe. Core stability in altruistic coalition formation games. In Latin American Theoretical Informatics Symposium, pages 320-333 Springer, 2024.
[12] Kate Donahue and Jon Kleinberg. Model-sharing games: Analyzing federated learning under voluntary participation. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 5303-5311. AAAI Press, 2021.
[13] Kate Donahue and Jon Kleinberg. Fairness in model-sharing games. In Proceedings of the ACM Web Conference, page 3775-3783. ACM, 2023.
[14] Bhaskar Ray Chaudhury, Linyi Li, Mintong Kang, Bo Li, and Ruta Mehta. Faimess in federated learning via core-stability. In Advances in Neural Information Processing Systems, pages 1738-5750. Curran Associates, Inc., 2022.
[15] Kate Donahue and Jon Kleinberg. Optimality and stability in federated learning: game- theoretic approach. In Advances in Neural Information Processing Systems, pages 1287-1298. Curran Associates, Inc., 2021.
[16] Haris Aziz and Rahul Savani. Hedonic Games. Cambridge University Press, 2016.
[17] Xinyi Xu, Lingjuan Lyu, Xingjun Ma, Chenglin Miao, Chuan Sheng Foo, and Bryan Kian Hsiang Low. Gradient driven rewards to guarantee fairness in collaborative machine learning. In Advances Neural Information Processing Systems, pages 16104-16117. Curran Associates, Inc., 2021.

---

[18] Rashidul Islam, Shimei Pan, and James R. Foulds. Can we obtain faimess for free? In Proceedings of the 2021 AAAT/ACM Conference on AI, Ethics, and Society, pages 586-596.
ACM, 2021.
[19] Nhan-Tam Nguyen, Anja Rey, Lisa Rey, Jörg Rothe, and Lena Schend. Altruistic hedonic games. In Proceedings of the 2016 International Conference Autonomous Agents & Multiagent Systems, pages 251-259. IFAAMAS, 2016.
[20] Sen Cui, Weishen Pan, Jian Liang, Changshui Zhang, and Fei Wang. Addressing algorith- mic disparity and performance inconsistency in federated learning. In Advances in Neural Information Processing Systems, pages 26091-26102. Curran Associates, Inc., 2021.
[21] Avrim Blum, Nika Haghtalab, Richard Lanas Phillips, and Han Shao. One for one, or all for all: Equilibria and optimality of collaboration federated learning. In Proceedings of the 38th International Conference on Machine Learning, pages 1005-1014. PMLR, 2021.
[22] Jörg Rothe. Thou shalt love thy neighbor as thyself when thou playest: Altruism in game theory. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 15070-15077. AAAI Press, 2021.
[23] Jacob Schlueter and Judy Goldsmith. Super altruistic hedonic games. In The Thirty- Third International Flairs Conference. Florida Online Journals, 2020.
[24] Martin Bullinger and Stefan Kober. Loyalty in cardinal hedonic games. In International Joint Conferences on Artificial Intelligence, pages 66-72. IJCAI, 2021.
[25] Ernst Fehr and Bettina Rockenbach. Human altruism: perspectives. Current Opinion in Neurobiology, 14(6):784-799) 2004.
economic, neural, and evolutionary
[26] Ernst Fehr and Klaus M. Schmidt. Chapter 8 the economics of fairness, reciprocity and altruism experimental evidence and new theories. In Foundations, volume of Handbook of the Economics of Giving, Altruism and Reciprocity, pages 615-691. Elsevier, 2006.
[27] Ernst Fehr and Urs Fischbacher. The nature of human altruism. Nuture, 425(6960),785-791 2003.
[28] Altruism may arise from individual selection. Journal of Theoretical Biology, 235(2):233-240, 2005.
[29] Anna Maria Kerkmann, Nhan-Tam Nguyen, Anja Rey, Lisa Rey. Jörg Rothe, Lena Schend, and Alessandra Wiechers. Altruistic hedonic games. Journal of Artificial Intelligence Research, 75: 15:1,9-169, 2022.
[30] Anna Maria Kerkmann, Simon Cramer, and Jörg Rothe. Altruism in coalition formation games. Annals of Mathematics and Artificial Intelligence, pages 1-29, 2023.
[31] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Ciammunication-Effiiieeee Learning of Deep Networks from Decentralized Data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pages 1273-1282. PMLR, 2017.
[32] Jer Shyuan Ng, Wei Yang Bryan Lim, Zehui Xiong, Xianbin Cao, Jiangming Jin, Dusit Niyato, Cyril Leung, and Chunyan Miao. Reputation-awar hedonic coalition formation for efficient serverless hierarchical federated learning. IEEE Transactions on Parallel and Distributed Systems, 33(11):275--6666 2022.
[33] Lingjuan Lyu, Xinyi Xu, Qian Wang, and Han Yu. Collaborative Fairness in Federated Learning, pages 189-204. Springer International Publishing. 2020.
[34] Kanad Shrikar Pardeshi, Itai Shapira, Ariel D. Procaccia, and Aarti Singh. Learning social welfare functions, 2024.
[35] Cyrus Cousins, I. Elizabeth Kumar, and Suresh Venkatasubrammnnin. To pool or not to pool: Analyzing the regularizing effects of group-fair training on shared models. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, pages 4573 4581. PMLR, 2024.
12

---

A Appendix
A.1 Monotonicity of error with dataset size
Lemma 3 (Monotonicity) For any two clients within the same coalition, i.j E n. if ni > nt. ( < (Trry(T). Conversely, if err; < eeryy, n4 nzj-
Proof Based the exact errors in Lemmal 1 it's natural that if > nij erri(T) < crry(T)) Denote N, Eker lik, N₂ Eker n irrr, < err;, holds that,
+ N 8.-n, (.-n,+(N.-ni))
+ 0².
No-n (N, (N,-n,)
No
N7
(10)
20 N.
2n 2,...N.n3 14
N2
N2
A.2 Core-stable conditions
Corollary I For set of players where S 5, the grand coalition 7g remains core-stable when the clients are either purely altruistic or friendly altruistic.
Proof In a grand coalition Tg comprising N clients, each client holds a local dataset with size n, I H.. Based Lemma 2 when S #s, it holds that (rr,(Tg) S err;(TT). Whether within Fg or a subset Ws C kg. the i-thl purely welfare altruistic client focuses on the same friend, that is, the k-th client, where k = arg min {ny}- fEF.
erru(T))) erru((Ts) min (ferr)(Tg))) min ((erry(na))), Vi, Tg. JeP,
(11)
TEF,
Therefore, the ug core-stable for purely welfare altruistic clients. For the purely equal altruistic client, the optimal individual error under Tg also leads to the optimality of the average multi- individual error and the following equation holds:
Σ (
S
Σ FEF
err (Tx), C Tg-
(12)
F
[F
FEF
Therefore, the Fg is core-stable for purely equal altruistic clients.
The utilities of friendly altruistic clients are weighted combination of the utilities under selfish and purely altruistic behaviors. According to the established core- stabiitay when clients selfish and purely altruism, the condition n,, S #ts facilitates utility minimization within the grand coalition Ta for clients with selfish and purely altruistic behaviors. Thus, this condition also leads to the utilities within the grand coalition Tg being minimized for clients exhibiting friendly altruistic behaviors.
A.3 Pareto-Optimality
Proportion (Pareto- ((Preto-Optimalle Optimality in error) Consider the FL system described an ACFG, core- stable coalition structure is also Pareto-optimal in local errors across all clients.
Proof We prove the Proportion 7by by contradiction. Consider N clients. Assume that core-stable coalition structure Tess is not Pareto-optimal. Then, there exists a Pareto-optimal coalition structure Io that satisfies the following conditions:
erri (lles) 2 err: (IIpo). . Vi (N). erry (Hes)) err, (IIp)) 3j E (N).
(13)
For clients exhibit altruism with selfishness degree parameter w [0, 1], holds that:
w. (Iess) +1 (t-w) (KEFJU() (Iles) > by (IIr)) + (1 - (w-w) UREFFULs (Iloo),
(14)
which contradicts the assumption of Tis core-stable. Based on the above, a core-stable federation structure is also Pareto-optimal under ACFG.
13

---

A.4 Egalitarian fairness bound
A.4.1 Proof of Proposition 2
Proposition 2 (Optimal egalitarian fairness under purely selfish behaviors) Considering all clients act purely selfish, the grand coalition Fg remains core-stable if the achieved egalitarian fairness is bounded by:
N.2 Namm++llaa max Cog No Nometddoa
where
kg. arg min {n:}-
(15) Proof In a coalition structure with N clients, denoted by Fg 21, where each client possesses local dataset of size nj the concept X-egalitarian, fairness stipulates that erv((ma)
ery Z
X, n. S nz. a context where clients are purely selfish, the coalition Rg maintains core-stable if. for any potential sub-coulition TT ag there is at least one client who prefers Bi over this means that 3i Wxy (z(Tg) ) S uz (T.), or equivalently, Ei E Tay Ts, (rr:((gg))))))))))))))())()))e S erri(Ta). According to the egalitarian fairness definition, it holds that,
max (Frr,(Fg))))
err((#g) S
(16)
To satisfy for Vxs C ag. 3i E Ts (rr) S (r.;((T)). the lowest À is bounded by Equation (17
max (erri
max (errs(na))
A < min n, C
(17)
iEE.
Based on Lemma
we denote m arg max (erri(ng))
arg argmin {n,} and kn, sem,
iens
arg max (erra) = arg min {n,}, then the above equation is equivalent to,
iEm. ie
ETTm (T)) < min ferrkr, (TT))
(18)
J,C
We first give the lowest fairness bound for specific T.
(T)
Errk, (T.).
(19)
Based on Lemma 7 the above equation can be transformed as,
Exergitto o (Ercegittm n.
Me + 0². +02.
Eierg
(EnEr, n.)
(20)
A Eler, "1 + 0². Eierentter of (EEEennnt nt) (Erers m.)
Denote N. = Lier, and Ng = =EEE, The we have,
De. + o² Eiery ne +N, nmd Ng
+ 02 Exer, )²)
Me N,
(21)
N₂
Multiplying each side of the above equation by N2
He N₂ N o² N.2. (Evengaam oo + (N, - nm))² S (e N N₂2 + N₂²
(22)
(EEEAAAAA n² + (N, - mk..) )2))
Thus, the lowest fairness bound X satisfies,
N, to? N.. ? N, 2...., Eierantto, az 12+(N, (N,-NAa pknm))
E Exgny smm n² ui+(N, (o,+(N,1u -mm))?
Jaus-
(23)
14

---

Taking the derivative of fRHS with respect to 0, we have:
SRHS, = Ne -o?.N, E Eiergaee ni (N+ am )
(Mo 2,2 2- Sghe ni W2-(No (No-m
(24)
Pee N2. N2. (N.(N.. (2. (N - nm) No -2 (Cienontthr, mi N2 mK
No..N. 2 No2.Ng" (Er ni PR+(N, (N.-
For f1===:00 N₂ Eienge ni Ng Eien,ifhe, ni since the growth rate of Eien, ifthe mf is faster than that of No, reasonable to assume that fi is decreasing with respect to No. The minimum value occurs when n
gg.. which point.
fi LiEr, n4 Σ bE nj mm
EiEn, ni (IjEx, n2 -
= LiET
Σ jE=, nij - nm
((EjET, n2 -/ )]
0.
(25)
Also, f2 = No (Ng nm )²m)²= -g- (N₂ 1KT. )² >0. 0:
f2 = N₂ (Ng - 1m )² - Ng. (N₂ - nk=,) )²
(N, N₂) Ng KTr
+ N,,
2N (Nkke 7mm
= =N, N2 n Rk.,
+ n 2N2 m2m)
(26)
= =NGNN N
+ (Nm N,)² (NNe, -Na)²)
>0
Based on the above derivation, we can conclude that fRRHS > O. Therefore, the maximum value of faHS occurs at the maximum value of o². Given our assumption that S H Vi = 1,... N, the = arg max {n:}. Consequently, the Eq. (3) transforms into,
maximum of o² is Re ni
He N. +N.
2.N.NNN,,,,,..... (Eieggittm ne +2+ mmm) mnm
A
Me MoNN,,N PetteeN N,² (EieT, Jek,, w/+ (N,- mnke
(27)
N.2 Ny Eiengisem n +NNN--nnn
No N. Exer nz 12+(N, mnke)
Above all, we can determine the optimal egalitarian fairiess bound to maintain the core stability of the coalition structure Tg.
N
Ny (EieT (N, (NN,N,,))) mm.)))
maX
No²
N. (Eicsiint, Of+(NN-nk., nk., )²)
(28)
N.3
=max Eng
No
A.4.2 Proof of Corollary 2
Corollary The core-stable grand coalition Tg. comprising all selfish clients, can asymptotically achieve stritt egalitarian faimess,, provided that the local dataset sizes of all clients are equal.
Proof Let's consider grand coalition my that consists of M clients, and subset Fg that consists of m clients. According to Proposition when the local dataset sizes of all clients are equal, the optimal egalitarian fairness that can be achieved is:
N.2
Ng m. + cl(TT..mm) Rom)
Aoptimal
max To C.y
N
N₂ - m. + d(Tss 1kke))
(29)
m
(M + M
(M - 1)²)
=
C.g
M (m m - 14 (m 1)2)
Therefore, it is proven that the grand coalition Tg is capable of achieving strict egalitarian fairness.
15

---

A.4.3 Proof of Proposition 3
Proposition 3 (Optimal egalitarian faimess under purely welfare altruistic behaviors) Considering all clients act purely welfare altruistic, the grand coalition 2g remains core-stable if the achieved egalitarian fairness is bounded by:
A 2 maXn,EF, min
N.2 Nomeedlaammm No² Nom-td(sa N₂² No No² Nemitd(se. )
where
1 arg min (minsernm,, not kn.22 arg min (minserom. nf) pep arg minnerri De, nfz 1 arg min f
(30)
Proof In context where clients are purely welfare altruistic, the coalition Tg maintains core-stable if. for any potential sub-coalition n, C ag there is at least one client who prefers ng over ug. this means that 3i E TT, (,)g)((T)))))))) (T,T)), equivalently,
Ei E nT. max (ferr (Tg)) S max JEF:
max SEPinA, (ferry(m.))), fEF;nm.
max ((errs(me)))).
(31)
where Tg \ is the complement of Te. Consequently, to maintain the stability of FL, we can determine the lower bound of X by.
max(err((Ma)))
Sminx, (max (maxiex, {maxyeFinw, (Fr max,e, {max (rrr((T))))))))))))))))))))))))
(32)
The fairness bound À with respect to a specific n, is,
(Frm((Tg) < max [eaa nr, maxye Oxe erry(Tee)
(33)
max (err jopt (mx), err 1ar (mTa)
where,
m Baaggmax max (err:(TT)) = org min (ni), Eет kx,,1 arg max (max)eR, (Tr)) arg min (minser n/)
iET,
fEx,
kT,,2 arg max (maxfcRinse erry arg argmin min (mingeRinse nf} kEW,
(34)
igss
jopt arg maxjEft, na, erry (T.)
min f 72fs
jopt arg max, na, err (me) arg min min p nae ni..
Following the same derivation in the proof of Proposition the above equation is equivalent to,
(T
errm erTm((Tg)
A 2 min
erT (Ta)
porp pope (Te) erT
(35)
N.2
N.2
do fopt
min
N,7
Nomitdlan (eg.))
N₂
where
= arg
max mag tEn
Nng,NN g = Σ n4 N₂
Σ N,
Σ n₁.
(36)
iE
iET.
iET
Above all,wa we can determine the optimal egalitarian fairness bound to maintain the core stability of the coalition structure gg.
X max ETy min
N.2
Mymne N, + 1
N.2 No
(37)
N,
N₂ Ne
A.4.4 Proof of Corollary
Corollary 3 The core-stable grand coalition kg. consisting of purely welfare clients, can asymptoti- cally achieve strict egalitarian fairness if all clients are friends with the client possessing the smallest dataset size and N, +
16

---

Proof When all clients are friends with the client possessing the smallest dataset size, it holds that f m or f m. Assume that fि m. Corollary 3 can be proven by mathematical
induction as follows. Define the hypothesis Ho as:
N₂2 Ng (otttad)))) Ng
Ho
S 1, VT. Tg.
(38)
When Tg contains only one player Ts = {ny}. we have,
n Ng + d( 1mm)
n
nlj
Eier, mi - nm
Vi
(N, 7m )
1. (39)
N 2 ny + d( 1m equal
(Ereny 14
approaching
approaching
Assume that the hypothesis Ho holds when n, contains k players, for n² (T n containing k + players where the new player has a dataset size of n, it holds that,
Nº Ng -(m d( No
No - des Rmn)
(40)
< N,2.(N, my + y Rem t (N, mi tl Rom 1) mi, titds
No "NN + a non + (n-m +dll 22
where N' = Eier, nue As No + 0o, we have,
2N (dl Pm)) No-000
Eecra n
(N, (2m-Rm)) 1.
(41)
n.
Ng
N;
Ng
Since Ho holds for any Tss the terms in the numerator are each smaller than the corresponding terms in the denominator: Thus, it follows that,
N22 Ny-m=+d(7y.mm))
N₂² Momitdlri. 1.
(42)
Therefore, the hypothesis Ho is established. A similar mathematical induction process can be applied to Te. Thus, Noptimal can approach less than 1 under the given conditions, proving the Corollary
A.4.5 Proof of Proposition 4
Proposition 4 (Optimal egalitarian fairness under purely equal altruistic behaviors) Considering all clients act purely equal altruistic, the grand coalition Ty remains core-stable if the achieved egalitarian fairess is bounded by:
Fkr,, I.N. No? No
Na + d(
A max K.ENg
Q
where
(43)
kx, arg min [PT (EjERnA,, ny + EseFsm. n1). Q Nº ESeP ne. (N, nu + d(TTs, N Eser. no (Ne. nu + d(
nr,
Proof In a context where clients are purely equal altruistic, the coalition Tg maintains core-stable if. for any potential sub-coalition T, C. Fg. there is at least client who prefers Tg over ne this means that 3i E Ts, TT, (Tgg) I (T,),, or equivalently.
E To: F
Σ (Tg) S [FI FER
Σ
(T.) + Σ err err, ((Te(
(44)
FERnA
fEFiNa
where The = Fg \ TTy is the complement of Te- Consequently, to maintain the stability of FL, we can determine the lowest fairness bound X by.
max(errs(MT))i minn,Con
(maxien.
[iT (ESERnS, err, (TT))(T) +EE))=EEEE........ err (Fr)(Te))
(45)
The lowest fairness bound X with respect to a specific is.
eF)m(TT))
(EreFi,, na, err + +SEEFr, Dx. errs(Tte)
(46)
Feza
17

---

where,
arg max (err: arg min fnet. iEN,
k arg max
[PT
(EjERAm. erry(TT)) + EjErimm erry (ESERO,, ny EsEFiRA nz)
(47)
arg min iem
FFll
Following the same derivation in the proof of Proposition the above equation is equivalent to,
[F (errm
Fir, N.? +
x FEFke,
(48)
erry (Ta Aime erry(Re))
N₂
where,
1= arg {n;} Ng = EiER, R4, n4, EiER. nis Ne Eien. ni.
1E%y
(49)
Q No EjEPt,, nr, rum (N, ni + d( ns)) + N² ESEFL,, rmme (No . n + d( n2)).
Above all, we can determine the optimal faiiness bound to maintain the core stability of the coalition structure g..
(1eee I.N, Ne
max R,ERg
Ng¹
Q
(50)
A.4.6 Proof of Proposition
Proposition 5 (Optimal egalitarian fairness under friendly welfare altruistic behaviors) Considering all clients act friendly welfare altruistic, the grand coalition Tg remains core-stable if the achieved egalitarian fairness bounded by:
A max min m.E
N22 N. my +-(x, 2
N. N. No tl N₂²
Q2
where
ka,,1 arg min {w + (1 - w) mi n(r) k = arg mingen, (w n, + (1 w) minferrnn, nz),
ng).
popt = arg min nn.utka.. ff " J = arg mimmine Je 2mm "ff
Q1 = N₂ n. + w d(T,, ak + w) ) d(Tss 1
Q2 = N2 w (N, n4 + d(T,, m)., + N (1- w) (No m4 + d(Tes 2
(51)
Proof In a context where clients are friendly welfare altruistic, the coalition ma maintains stability if. for any potential sub-coalition To C. ag there is at least one client who prefers Tg over wao this means that 3i E Tay (z(Tg) I (T.)), equivalently,
3i E w (Tr((TT))))))))))))))))))))))( + (1 10--w) w)
SEAUIA max (ferr)(My)))
w (rr((T)) + (1 11ww) w) max )EF:NA.U())
((err)(Ta))),
(52)
< max
w errrr (1 w) max feFinx.
((erry(πe)))
, E (0,
where The =Tg \. is the complement of ne Consequently, to maintain the stability of FL, we can determine the lowest fairness bound of X by,
(F + (1 [w) max (ax())r:(TT (ax
maxies, {w (uu-erri(TT)) (1 w) mmaxeernn.uu)) err err (TA)( mnxx
maXiER, {w- ( + (1 (--ww max/eF.ne err (Te) ))
(53)
< C
The lowest fairness bound À with respect to a specific n,
ertm (mg)
maxiem,
+ (1 w) max ( maxies, (w err; (T)) (1 -w) maxfeRRna err (Tr)( w err (Te) + (1 (--w) w) err sopt (T₂)) erTk (T.) (1 w) err pere (Ie))
< max
A
(54)
max
18

---

where,
arg max (err.(mg)) ary min {n.). T
Rn,,1 arg max (w- err; (T (1 w) mex
iEx,
arg min (w- nn + (1 w) min n/)
li,,2 arg max {w (T.)) + w) maxfannm err (
(55)
iER,
=arg min fw n. + (1 w) mense ny)
SER,
Fo.l arg max (Ra,a)) erry (m,) org ge (kow fif
J = arg faF 2 nue err (Te) = arg minjePt., niee nt..
Following the same derivation as in the proof of Proposition 2 the above equation is equivalent to, errm(TT))
eFrm (Tg)
A M min
worrkey, (1.)+(1-MM) err (T.)) worrkey, 2 (1,)+(1 11) yorr (Te)
fail
(56)
min
N
N. N.N
N. No
Q1
No
Q₂
where,
arg max (ni): N2 = Eien, ni, N. = Eien, ni, No Eiene Réi, KETy
Q N. ni + d(TT. Uk.,, )) + (1 w) d(T.. s2pl1) Q2 No w (N, + d( Thx,, + N? w) (Ne -m d( seg:))
(57)
Above all, we can determine the optimal egalitarian bound to maintain the core stability of the coalition structure TT..
N No
do Q
N. N Nonltd
}
max Tx
min
N₂"
Q2
(58)
A.4.7 Proof of Proposition 6
Proposition 6 (Optimal egalitarian fairness under friendly equal altruistic behaviors) Considering all clients act friendly equal altruistic, the grand coalition Tg remains core-stable if the achieved egalitarian fairness is bounded by:
(1) Ng²
2 max= ETTy
Q
where
kr, = arg min
W n4 + (1-w) [Fl+11 (EsERioAua)) ny + EsEFEmEn ng))
F, = FRF. AT, U (kr,) b.r,,.Fe =Fkr, Aiter
Q = w (IFr... 1)- .No (N.
.N2..... ny di(Ts, (...))..))))).)..
(1 w) N2 Σ (Ns ni + d(ms: N2. Σ (Ne ni + (Te: (ee)))))))))))
fEF.
SeP.
(59)
Proof (Proposition 6 In a context where clients are friendly equal altruistic, the coalition Ta maintains core-stable if. for any potential sub-coalition TTs C Tg. there is at least one client who prefers Tg over wa. this means that E nay uy (Tg) S us (T(T)),, or equivalently,
Bi E nay w err,(ag) (1 w) |F++1
Σ
(erry(mg))
SERUIA)
(60)
S w (er;(r;) + - (1- FAl+1 Consequently, maintain the stability of FL, we can determine the lowest fairness bound of X by,
Σ
(erry(T.)) +
E (erry(ae)) JEFiNEe
(EFFNTLU
w (rx +
}
(Tx &
1-w +1
Σ
SEFLIA
mille,Cs CFg
maxiER.
Σ
(arrs(Ta)) +
Σ (errs(Fe)) SER
SEFinm.u
(61)
19

---

The lowest fairness bound À with respect to a specific is,
crTm (T) S errka, (TTs)
1-wi Pke, +1
Σ
(erry(Ta)}+
E (errs(to))) (62)
fEF
scF.
where,
m ary max (crri(TT)) arg min [ni]:
iEng
1679
k7, = arg max i
w. err, . + (1 - w)
Σ
(erry(T=)) + E (errs(
Fil+T
(ERNIL
SEFITRE
w nu + (1 w) PH- arg min
Exerinouus) Ty + =EtEFinne (4)
F. = Fkc, O n. (Kn,). Fks, NTa..
(63)
Following the same derivation in the proof of Proposition the above equation is equivalent to,
(1Fko, N,2),
Ng No
(64)
Ng"
where,
arg max mag {ni} NN,-- Σ n4, No Σ TE
nii No Σ nii
(65)
iE
iET
iETO
Q w (1Fki., 1) N? (N₂ ni + d(TTS, Tix,, +
N E (N₂ - + d( ny)) + N?? Σ (Ne. mm + +dd (Te: (1).
(66)
(1 - w)
fEP.
fEP.
Above all,we we can determine the optimal egalitarian fairness bound to maintain the core stability of the coalition structure g.
maxx,E59
(1
(+1) N₂²
N Nomm-dlr
(67)
A.4.8 Fairness Bound Analysis under Generallzed-MMen--FFooe Utility Function
Taking the weighted power-mean welfare function 34 to construct utility function an example and considering scenarios where clients exhibit friendly equal altruism, the utility of the i-th client is:
F Σ
u (Ty)
weert?
(68)
The coalition T, remains core-stable for any potential sub-coalition wa Tg. there is at least one client who prefers Tg over n.. This implies that Di E Ta, (;(TT) S u,(T)), or equivalently,
Σ w.err?
S wi eTT?((T)) +
Σ (Terr?((Ts) +
Σ
wyyerr
JEFNNK
JERnNe
(69)
Consequently, to maintain the stability of FL, we can determine the lowest fairness bound of À by.
maxfer?((m)))) NN
E w
S
mi, (maxier. (w: (Tr) + Exeinn, Wy (gpeer(((m)) Eferin wy - ( $14
(70)
The lowest fairness bound À with respect to specific is.
err (Tg) < Wh., erri. (TTS) +
Σ
wy - err (TT) + Σ wy aug-errie err (71)
feR.
fef.
20

---

where,
Fi TT., arg min (1,),
SE
kim, arg min ke
wi n + EsEPor.. Wy ng EsERon wy n.))
(72)
F. Fk., (T. FR., TT.
Following the same derivation as in the proof of Proposition 2 the above equation is equivalent to,
N. N. N₂
(N, mN mmitaae mm(
(73)
Q
where,
N₂ Lien, T1i No Eiex. n4 n4; Ng = Eier,
74e
(74)
Wk... N22 (N₂ my d(T.: nk.,
+N24. Σ wf (N, my d(fT)
fEF.
(75)
+N2g. E wf (Ne my + d (f)) fef Above all, we can determine the optimal egalitarian fairness bound to maintain the core stability of coalition structure kg
(( (N +dl amm))
maX
(76)
Q
A.5
Additional experiments
A.5.1 Heterogeneous client behaviors
Experiments under heterogeneous client behaviors involved configuring the two clients to exhibit purely selfish behavior while the rest modeled as friendly equal altruistic as in Figure 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.
Purely Setfish
I riienlly Equul-Attruism Altruism
Clienr
Clienr
Core ctbie Calcmated boand
Clienr
Clienr
Core rbabl
1.5
1.5
Calcultted Abound
Client 4
Clienr 3
Clicnr
Cliour
1.-
Figure 4: Heterogeneous clients' behaviors: theoretically derived egalitarian fairness bounds (green dashed line) align with empirically achieved egalitarian fairness within the core-stable grand coalition (red solid line).
A.5.2 Adaptability
Lastly, examined the adaptability and lask-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 0 or e,, consistently matched the actual fairness achieved within a core-stable grand coalition (red solid line).
Fandly beftak
Pardy vellare diretat
Phincy egui strdettc
Frieadss netirre stideee
Pricads opal dirabdee
Figure 5: Linear regression: theoretically derived egalitarian faimess bounds (green dashed line) align with empirically achieved egalitarian fairness within the core-stable grand coalition (red solid line) under different client behaviors.
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We accurately defined the research scope and contributions in both the abstract and the introduction (Section]
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer:
[Yes]
Justification:
We discussed the limitations of our paper in the Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
22

---

For the theoretical results in our paper, including propositions, lemmas, and corollaries, the assumptions are detailed in the Section and the complete (and correct) proofs are provided in the Appendix A
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provided the code to reproduce the experimental results in the supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
23

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We provided the code in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips //ipsscc//pill wttpcccpppppppppeeeeeeeeeeeeeeee httpa//gguudeee/eeeeabiiissssss /Cc////oddiiisssseeeeeee ssiiiiiiccyyyyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
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 the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
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, confi- dence intervals, statistical significance tests, 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 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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provided compute resources in Section 6
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: This paper conformed with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We provided societal impacts in Section
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.
25

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
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)?
Question:
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 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 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 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 dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.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 Datasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
26

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We provided the open-source code in the supplemental material.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper did not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper did not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "45gRpAbddd", "reviewer": "Reviewer_LduT", "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.\n\nThe 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.", "questions": "Please refer to the identified weak points for details.", "limitations": "NA", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "+ A novel research on the influence of clients' altruistic behaviors is well explored, which offers deep insights and a significant impact on the domain of fair Federated Learning. \n\n+ A solid Modelling of fair FL systems as altruism coalition formation games (ACFGs) based on game theory and social choice theory.  \n\n+ Concrete bounds of optimal egalitarian fairness that an FL coalition can achieve while maintaining core stability under various altruistic behaviors. \n\n+ Novel key insights are obtained: (1) 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; (2) 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. \n\n+ Extensive experiments are conducted to evaluate the consistency of theoretically derived egalitarian fairness bounds with the empirically achieved egalitarian fairness in fair FL settings.", "weaknesses": "- 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? \n\n- 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? \n\n- In Line 307, Example 1 is used to show which proposition? Better to clarify.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are delighted that the reviewer recognized the significance of our research and its novel key insights. Thank you for your positive feedback and insightful comments.\n> **W1 (Illustration):**\n\nThank you for your comment. In Sections 4.2 and 5.1, we utilize color text to better illustrate the results in Table 1. Different colors (blue, red, orange, green) are used to indicate stable coalition structures under different behaviors. \n\n>**W2 (Navigation):**\n\n\nThank you for your suggestion. We'd like to revise Section 5.2 and connect the propositions to their corresponding proofs in the Appendix to improve clarity and navigation.\n\n> **W3 (Example 1):**\n\nThank you for your comment.  **Example 1 shows how to calculate the achievable egalitarian fairness bound for heterogeneous behaviors (Lines 303-306)**. To improve clarity, we'd like to revise this paragraph (Lines 303-306) by adding \"An example to calculate the achievable egalitarian fairness bound heterogeneous behaviors is as follows:\".", "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": "", "extra_scores": {}}, {"review_id": "HzvzyLYrmt", "reviewer": "Reviewer_CtFP", "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.", "questions": "Clearly the FedAvg rule for $\\theta$ (line 126) promotes privacy in some sense, but with modest added noise, is the mechanism differentially private?\n\nI 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.\n\nLemma 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.\n\nI 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.\n\nIn 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?).\n\nI 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)?\n\n\nIn 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.\n\nMoreover, 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.\n\n\n\nMinor points:\n\n149 “satisfy” should be “satisfies.” Moreover this definition feels a bit redundant with (1).\n\n158 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?\n\nPerhaps definitions 2 3 and 4 can be merged to describe the coalitional game?\n\n163 “does not exist” to “does not exist a”\n\n\n171 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": "FedAvg\n\nI 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.\n\nThe 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).\n\nHowever, 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.\n\nOverfitting\n\nI 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.\n\n\nReferences:\n\n[1] An axiomatic theory of provably-fair welfare-centric machine learning\nC Cousins\nAdvances in Neural Information Processing Systems 34, 16610-16621\n\n[2] Revisiting fair-PAC learning and the axioms of cardinal welfare\nC Cousins\nInternational Conference on Artificial Intelligence and Statistics, 6422-6442\n\n[3] Jacob D Abernethy, Pranjal Awasthi, Matthäus Kleindessner, Jamie Morgenstern, Chris Russell, and Jie Zhang. Active sampling for min-max fairness. In International\nConference on Machine Learning, volume 162, 2022.\n\n[4] A guide through the zoo of biased SGD\nY Demidovich, G Malinovsky… - Advances in Neural …, 2024 - proceedings.neurips.cc,\n\n[5] Uncertainty and the social planner’s problem: Why sample complexity matters\nC Cousins\nProceedings of the 2022 ACM Conference on Fairness, Accountability, and …\n\n[6] Algorithms and Analysis for Optimizing Robust Objectives in Fair Machine Learning\nCyrus Cousins\n\n[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.\n\n[8] John Rawls. A theory of justice. Harvard University Press, 1971.\n\n[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.\n\n[10] Dwork, Cynthia, et al. \"Fairness through awareness.\" Proceedings of the 3rd innovations in theoretical computer science conference. 2012.\n\n[11] Deschamps, R., Gevers, L.: Leximin and utilitarian rules: A joint characterization. Journal of Economic Theory 17(2), 143–163 (1978)", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The main strength of this paper is its comprehensive approach to analyzing federated learning under both selfish and altruistic behavior. By considering both the performance of machine learners and the game-theoretic aspects of how federated learners interact, the authors provide a well-rounded analysis of the relationship between egalitarian fairness and stability. The use of game theory and social choice theory to frame FL systems as altruism coalition formation games is particularly innovative, linking instability issues to clients' altruism and their network of relationships. The proposed optimal egalitarian fairness bounds that maintain core stability under various altruistic behaviors are a significant theoretical advancement, disproving the assumption that egalitarian fairness inevitably leads to instability. The technical correctness of the results, subject to the model assumed, further solidifies the paper's contribution to advancing the state of the art in this field. Experimental validation then convincingly supports these theoretical findings with empirical outcomes.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are delighted that the reviewer found our motivations and  methods innovative and significant  towards an important research question. Thank you for your positive opinions and insightful comments.\n\n**Weakness:** Thank you for your thoughtful comments. We provided responses to the points in Q4 and L2 (Overfitting), Q7 and  Q8 (Welfare function), L1 (FedAvg).\n\n>**Q1 (Privacy):**\n\nFedAvg can provide differential privacy with modest added noise, i.e., DP-FedAvg [1] adding Gaussian noise to the final averaged update to ensure privacy.\n\n[1] McMahan, H. Brendan, et al. \"Learning Differentially Private Recurrent Language Models.\" ICLR. 2018.\n\n>**Q2 (Terminology):**\n\nThe distinction between egalitarian fairness and demographic parity lies in the focus on fairness, whether it's between individual clients or between protected groups defined by sensitive attributes. In FL,  improving the model's performance on some clients inevitably reduces performance on others; thus, minimizing the maximum loss over an average of agents becomes a sufficient condition for equalized error among clients and vice versa. Therefore, we adopt equalized error among clients to quantify egalitarian fairness, consistent with [2]. \n\n[2] Kate Donahue and Jon Kleinberg. Fairness in model-sharing games. WWW '23. 2023. \n\n>**Q3 (Variables in Lemma 1):**\n\nThe notation $\\mu_e$ does not specify a particular $i$ because, according to Lemma 1, the mean value $\\theta_i$ and standard deviation $\\epsilon_i$ of each client's dataset $\\mathcal D_i$ is i.i.d. sampled from $\\Theta$, resulting in a **consistent**  $\\mu_e$ across clients. Additionally, the error in Eq. (1) is derived from $err_i=\\left(\\boldsymbol{x}^{T} \\hat{\\boldsymbol{\\theta}}_{i}-y\\right)^{2}$,  which is actually a generic loss. \n\n\n>**Q4 and L2 (Overfitting):**\n\nOverfitting in machine learning leads to uncertainty in the error outlined in Eq. (1), which is influenced by model structure and parameters, choice of training algorithms, and the specific data distributions of clients, etc.  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.  We'd like to revise Lines 349-351's discussion by clarifying the overfitting challenges in more generalized machine learning scenarios. Thank you for highlighting this point!\n\n>**Q5 (Lemmas 2,3,&4):**\n\nThe requirement $n_i\\le \\frac{\\mu_e}{\\sigma^2}$ holds for all $i=1,...,N$, as explained in Q3 that $\\mu_e$ is consistent across clients. Lemmas 2–4 provide sufficient conditions for core stability across these behaviors. This setup ensures that each lemma is tailored to specific scenarios, supporting the tightness of our subsequent propositions. \n\n> **Q6 (IID and Variance):**\n\nClients are **heterogeneous**  as they have different parameters governing their data distribution and different\namounts of data they have noisily drawn from their own distribution in Lemma 1.  Regarding your second question, the mentioned variance refers to **distribution variance** rather than sample variance.\n\n> **Q7 and  Q8 (Welfare function):**\n\n We'd like to clarify how the key ideas in our work **extend** to more utility functions. Taking the weighted power-mean welfare function to construct utility functions as an example and considering scenarios where clients exhibit friendly equal altruism, the utility of the  $i$-th client is:\n$u_i(\\pi_g) = \\left( \\sum_{i=1}^{|F_i|} w_i err_i^q(\\pi_g) \\right)^{\\frac{1}{q}}$.\n\nThe coalition $\\pi_g$ remains core-stable if,\n$\\exists i\\in \\pi_s,\\left( \\sum_{i=1}^{|F_i|} w_i err_i^q(\\pi_g) \\right)^{\\frac{1}{q}} \\le\n\\left(w_i \\cdot err_i^q(\\pi_s)+\\sum_{f \\in  F_i \\cap \\pi_s} w_f err_f^q(\\pi_s)+\\sum_{f \\in  F_i \\cap \\pi_c} w_f err_f^q(\\pi_c)  \\right)^{\\frac{1}{q}}$.\n\nFollowing a similar process in Appendix Eq. (16)-(27), \nwe have $\\lambda \\ge  \\frac{\\left ( {N_s}^2\\cdot{N_c}^{2}\\cdot (N_g\\cdot n_l+d(\\pi_g,n_m)) \\right )^q }{{N_g}^{2q}\\left ( w_{k_{\\pi_s}}\\cdot N_c^{2q}\\cdot \\left (N_s\\cdot n_l+d(\\pi_s,n_{k_{\\pi_s}}) \\right )^q  + N_c^{2q}\\cdot \\underset{f\\in \\hat{F_s}}{\\sum} w_f\\cdot  \\left (  N_s\\cdot n_l+d(\\pi_s,n_{f})   \\right )^q \n  +N_s^{2q}\\cdot \\underset{f\\in \\hat{F_c} }{\\sum} w_f\\cdot \\left ( N_c\\cdot n_l+d\\left ( \\pi_c,n_f \\right )\\right )^q\\right ) }$. \nWhen setting weights w=[0.7,0.1,0.1,0.1] and $q$=1.2, the actually achieved egalitarian fairness was **1.45**, aligned with the calculated fairness bound of **1.44**. Minor deviations exist due to discretization errors of $p$ in Line 312.\n\n> **Minor points (Sociological definition and  terminology):**\n\nThank you for pointing out the typo errors. Regarding \"friend\" in Definition 3, we attempt to draw an analogy from sociological friendships to describe how \"friends\" are in FL. We think **removing** the sociological definition of \"friend\" will be better. Examples of \"friendship\" in FL, such as  Lines 47-49, are enough for readers to better understand the \"friend \" in FL. We agree that \"**utilitarian**\" better reflects the focus on the worst-off client than \"welfare\" and revise it following your suggestion. Thank you for your suggestion!\n\n> **L1 (FedAvg):**\n\nRegarding the expansion into broader FL models, our mean estimation task model, adapted from Donahue & Kleinberg, serves as a prototypical task for analyzing the stability of federating coalitions. However, the broader point is well-taken: We should clarify that our paper is investigating an FL model with errors exactly  enough to allow for **tight** theoretical analysis. We explained this point in Section 3, **Lines 131-133**, and gave this limitation in **Lines 349-351**. We would like to revise the paper, particularly the abstract and introduction, to further clarify that \"we use a **stylized** model to generate the following **insights** in fairness.\"\n\n> **L2 (Overfitting):**\n\nPlease refer to Q4 and L2 (Overfitting).", "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": "", "extra_scores": {}}, {"review_id": "i8MWyuYDfW", "reviewer": "Reviewer_r5t6", "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.", "questions": "1. How do the proposed fairness bounds perform in more complex FL scenarios?\n2. 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": "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.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors presented a novel perspective by integrating concepts from game theory and social choice theory to analyze the stability of FL systems under the influence of egalitarian fairness.\n2. The theoretical contributions are robust and well-supported by rigorous mathematical proofs. The proposed fairness bounds provide valuable insights into maintaining stability in FL systems.\n3. The paper is well-organized, with clear definitions and logical progression of ideas. The use of examples and detailed explanations helps in understanding the complex concepts.", "weaknesses": "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. \n2. 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.\n3. The use of clients' and client's is not rigorous enough (such as Line 22 and Line 128) and needs to be carefully checked.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are delighted that the reviewer found our work novel and valuable, with robust theoretical support.\nThank you for your positive opinions and insightful comments.\n\n> **W1 & Q1 (More complex and diverse FL scenarios):**\n\nThank you for your comment.  Following your suggestion, we first add more experiments on more complex scenarios, as in Tab.1 and Tab.2. The results confirm that the calculated egalitarian fairness bounds are closely aligned with the actual achieved fairness values (minor deviations due to discretization errors from adjustments in the fairness constraint parameter, $p$).\n\n\n**Tab. 1 Calculated egalitarian fairness bound and Actual achieved egalitarian fairness under fully-connected**\n|        | Selfish | Purely Welfare Altruism | Friendly Welfare Altruism | Purely Equal Altruism | Friendly Equal Altruism | 6 Selfish + others Friendly Equal Altruism |\n|--------------------------------------|---------|--------------------------|----------------------------|------------------------|--------------------------|-----------------------------------------|\n| **10 Clients [10,20,30,40,50,60,70,80,90,100]**           |\n| Calculated egalitarian fairness bound | 1.27    | 1.02    | 1.04     | 1.16   | 1.17     | 1.27   |\n| Actual achieved egalitarian fairness  | 1.27    | 1.03     | 1.05   | 1.16   | 1.17     | 1.27  |\n| **15 clients [10,10,30,30,40,40,50,50,60,60,70,80,90,100,100]**    |\n| Calculated egalitarian fairness bound | 1.18    | 0.99     | 1.04  | 1.10   | 1.12     | 1.13   |\n| Actual achieved egalitarian fairness  | 1.18    | 1.00     | 1.04 | 1.10   | 1.13     | 1.14   |\n\n**Tab. 2 Calculated egalitarian fairness bound and Actual achieved egalitarian fairness under partially-connected**\n|        | Selfish | Purely Welfare Altruism | Friendly Welfare Altruism | Purely Equal Altruism | Friendly Equal Altruism | 6 Selfish + others Friendly Equal Altruism |\n|--------------------------------------|---------|--------------------------|----------------------------|------------------------|--------------------------|-----------------------------------------|\n| **0 - 2 - 4 - 6 - 8 - 0, 1 - 3 - 5 -7 - 9 - 1**           |\n| Calculated egalitarian fairness bound | 1.27    | 1.08     | 1.07      | 1.20   | 1.18     | 1.27   |\n| Actual achieved egalitarian fairness  | 1.27    | 1.09     | 1.07       | 1.20   | 1.19     | 1.27  |\n| **0 - 2 - 4 - 6 - 8 - 10 - 12 - 14 - 0, 1 - 3 - 5 -7 -9 -11 - 13 - 1**           |\n| Calculated egalitarian fairness bound | 1.18    | 1.04     | 1.04       | 1.13   | 1.12     | 1.18   |\n| Actual achieved egalitarian fairness  | 1.18    | 1.04     | 1.05       | 1.13  | 1.12     | 1.18   |\n\nWe'd also like to clarify why we currently use mean estimation and linear regression for our experiments: the error in these tasks is exact and can be expressed in closed form, which allows us to do the following **tight** theoretical analysis. For more complex tasks, such as neural network training, the error is uncertain and influenced by model parameters, training methods, and specific client data distributions.  However, the suggested point is well taken:    We acknowledge that our paper focuses on FL tasks with errors exactly  enough to facilitate rigorous theoretical analysis. We explained this point in Section 3, **Lines 131-133**, and gave this limitation in **Lines 349-351**. We would like to revise the paper, particularly the abstract and introduction, to further clarify that \"we use the **stylized** model to generate the following **insights** in fairness.\" \n \n\n>**W2 & Q2  (Sensitivity):**\n\nThank you for your comment. Based on Eq. (3) to (7), we'd like to analyze how the theoretical bounds are sensitive to client behavior and network topology.  Taking the fairness bound under purely welfare altruistic behaviors in Eq. (4) as an example,  the set of friends $F_i$ for each client $i$ changes with different network topologies, resulting the variance on parameters **$f^{opt} _{\\pi_s,1}$, $f^{opt} _{\\pi_s,2}$** (variables that identify the client with the smallest data volume within the network topologies of each sub-coalition), thereby leading to different theoretical bounds.\nFollowing the same settings as the mean estimation task in Section 6, we constructed three types of network topologies: \n\n- T1: fully connected; \n\n- T2: 0 (20), 1 (40) - 2 (50) - 3 (100) - 1 (40) , where only clients 1, 2, and 3 are connected; \n\n-  T3: 0 (20), 1 (40), 2 (50) - 3 (100), where only clients 2 and 3 are connected. \n\nAccording to our analysis, the values of  $f^{opt} _{\\pi_s,1}$, $f^{opt} _{\\pi_s,2}$ will gradually increase from T1 to T3, leading to a decrease in the denominator value in the theoretical bounds. Consequently, the theoretical bounds are expected to increase. \nThe experimental results, as shown in the table below, are **consistent** with our expectations. The analysis and experiments demonstrate that the theoretical bound calculation is **effective** under varying client behavior and network topology. \n\n\n\n\n|        |  Purely Welfare Altruism | Friendly Welfare Altruism | Purely Equal Altruism | Friendly Equal Altruism | \n|---------|--------------------------|----------------------------|------------------------|--------------------------|\n| **fully-connected**           |\n| Calculated egalitarian fairness bound |  1.08| 0.98| 1.30| 1.23| \n| Actual achieved egalitarian fairness  |  1.08    |0.98| 1.31| 1.24| \n| **0,1-2-3-1** |\n| Calculated egalitarian fairness bound |  1.12     | 1.16| 1.40| 1.32| \n| Actual achieved egalitarian fairness  |  1.12     | 1.16| 1.41| 1.33| \n| **0, 1 , 2-3**  |\n| Calculated egalitarian fairness bound |  1.91 ↑    | 1.29 ↑ | 1.91 ↑| 1.43  ↑| \n| Actual achieved egalitarian fairness  |  1.91 ↑      | 1.30  ↑| 1.91 ↑| 1.44   ↑| \n\n> **W3 (Check the use of \"clients'\" and \"client's\"):**\n\nThank you for your comment. We have checked the use of 'clients'' and 'client's' throughout the paper and verified their logical and grammatical correctness.", "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": "", "extra_scores": {}}, {"review_id": "5gZ0ja8jh5", "reviewer": "Reviewer_X2VX", "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.", "questions": "- What do we learn from the experiments? What is the take away message?\n\n- Are the bounds that you provide in Section 5.2 tight?", "limitations": "No limitations", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "- The idea of introducing the altruistic behavior of the agents in an FL setting is very interesting and well-motivated.\n\n- The modeling of the altruistic behaviors is very clear and reasonable.", "weaknesses": "- 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.  \n\n- 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.\n\n- 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.\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for finding our work interesting and well-motivated. We also appreciate the detailed comments posed by the reviewer. Please find below the point-to-point responses to the reviewer's comments.\n\n> **W1 (Question addressing):**\n\nWe'd like to clarify how the obtained egalitarian fairness bounds address our original question: *Does Egalitarian Fairness Lead to Instability?*\n\n- We derives the lower bounds of achievable egalitarian fairness under different client behaviors for an FL system to maintain core stability. These bounds clarify that   **\"egalitarian fairness leads to instability\" happens only when a model trainer prioritizes fairness below the derived fairness bounds**, answering the original question with **tight theoretical support**.\n\n\n\nWe  develop egalitarian fairness bounds for stable FL systems **instead of** designing egalitarian fair solutions and assessing their stability for:\n\n-  Rationality: Core stability is a prerequisite for the healthy operation of FL systems. As a result, we investigate the egalitarian fairness bounds under core stability.\n\n-  Tightness：Designing egalitarian fair solutions and assessing their stability does not provide a tight solution about egalitarian fairness bound.  As $\\lambda$ is a continuous variable, it does not yield a tight solution to adjust the achieved egalitarian fairness $\\lambda$ and monitor when stability is compromised. \n\n\n> **W2 (Findings in Section 5.2):**\n\nThank you for your comment. The **significance** of Section 5.2 lies in offering **tightly theoretical support** to clarify the misconception that \"egalitarian fairness leads to instability in FL\" in previous work **rather than relying on intuition**.\n\nSpecifically, Section 5.2 theoretically analyzes the achievable egalitarian fairness bounds under **various client behavior scenarios**, providing insights into **establishing appropriate egalitarian fairness** in fair FLs. Additionally, we discuss how to extend the calculation of fairness bounds to accommodate clients with **heterogeneous behaviors** within the coalition.\n\n\nUnder behaviors such as equal altruistic or friendly altruistic, the complexity of the egalitarian fairness bounds increases because each individual must consider multi-related clients, which introduces additional variables into the calculations. \n\n> **W3 (Findings in Section 5.1):**\n\nThank you for your comment. We provide Section 5.1 to **highlight** that clients' altruistic behaviors and friendship relationships affect optimal egalitarian fairness in a core-stable coalition and **empirically refute** the misconception that \"egalitarian fairness leads to instability.\"\n\n> **W4 (More clients):**\n\n Following your suggestion, we add experiments on more clients. The results below verify that the egalitarian fairness bounds in a stable FL system are influenced by varying client behaviors and friendship networks and verify that the calculated egalitarian fairness bounds are closely aligned with the actual results (minor deviations exist due to discretization errors from adjustments in the fairness constraint parameter, $p$).\n\n**Tab. 1 Calculated egalitarian fairness bound and Actual achieved egalitarian fairness under fully-connected**\n|        | Selfish | Purely Welfare Altruism | Friendly Welfare Altruism | Purely Equal Altruism | Friendly Equal Altruism | 6 Selfish + others Friendly Equal Altruism |\n|--------------------------------------|---------|--------------------------|----------------------------|------------------------|--------------------------|-----------------------------------------|\n| **10 Clients [10,20,30,40,50,60,70,80,90,100]**  |\n| Calculated egalitarian fairness bound | 1.27    | 1.02     | 1.04      | 1.16   | 1.17     | 1.27   |\n| Actual achieved egalitarian fairness  | 1.27    | 1.03     | 1.05   | 1.16   | 1.17     | 1.27  |\n| **15 clients [10,10,30,30,40,40,50,50,60,60,70,80,90,100,100]**   |\n| Calculated egalitarian fairness bound | 1.18    | 0.99 | 1.04   | 1.10   | 1.12     | 1.13   |\n| Actual achieved egalitarian fairness  | 1.18    | 1.00 | 1.04   | 1.10   | 1.13     | 1.14   |\n\n**Tab. 2 Calculated egalitarian fairness bound and Actual achieved egalitarian fairness under partially-connected**\n|        | Selfish | Purely Welfare Altruism | Friendly Welfare Altruism | Purely Equal Altruism | Friendly Equal Altruism | 6 Selfish + others Friendly Equal Altruism |\n|--------------------------------------|---------|--------------------------|----------------------------|------------------------|--------------------------|-----------------------------------------|\n| **0 - 2 - 4 - 6 - 8 - 0, 1 - 3 - 5 -7 - 9 - 1**           |\n| Calculated egalitarian fairness bound | 1.27    | 1.08     | 1.07      | 1.20   | 1.18     | 1.27   |\n| Actual achieved egalitarian fairness  | 1.27    | 1.09     | 1.07       | 1.20   | 1.19     | 1.27  |\n| **0 - 2 - 4 - 6 - 8 - 10 - 12 - 14 - 0, 1 - 3 - 5 -7 -9 -11 - 13 - 1**   |\n| Calculated egalitarian fairness bound | 1.18    | 1.04     | 1.04  | 1.13   | 1.12     | 1.18   |\n| Actual achieved egalitarian fairness  | 1.18    | 1.04     | 1.05   | 1.13  | 1.12     | 1.18   |\n\n>**Q1 (Experiments):**\n\nThank you for your question. Our experiments highlight two key findings:\n- The theoretically derived achievable egalitarian fairness bounds align closely with the fairness achieved in a stable FL system, confirming their **tightness**.\n- The **adaptability** of these bounds is further validated by Figure 5, which compares the theoretical and actual egalitarian fairness in an additional linear regression task.\n\n>**Q2 (Tightness):**\n\nThank you for your question. The theoretical bounds are **tight**, which are rigorously derived under the framework set by Lemma 1 and adhere to the conditions for core stability specified in Lemma 2 to 4.", "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": "", "extra_scores": {}}]

Author rebuttal:
Dear Chairs and Reviewers,

We kindly thank all the reviewers for their time and for providing valuable feedback on our work. We appreciate that reviewers have pointed out that our work is novel (Reviewer LduT, r5t6),  significant (Reviewer LduT, CtFP) with valuable insights (Reviewer LduT, r5t6), interesting and well-motivated (Reviewer X2VX), and our results are convincing with solid analysis (Reviewers LduT, CtFP, r5t6).

In response to the reviews, we ran a series of experiments to show the generality of our findings under weighted utilitarian welfare function  (Reviewer  CtFP),  network topology  (Reviewer r5t6), number of agents (Reviewer r5t6 and Reviewer X2VX).

Kind regards,

The authors

Meta-review: 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.
Decision: Accept (poster)