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

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.

W1 (Question addressing):

We'd like to clarify how the obtained egalitarian fairness bounds address our original question: Does Egalitarian Fairness Lead to Instability?

• 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.

We develop egalitarian fairness bounds for stable FL systems instead of designing egalitarian fair solutions and assessing their stability for:

• 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.

• 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.

W2 (Findings in Section 5.2):

Thank 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.

Specifically, 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.

Under 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.

W3 (Findings in Section 5.1):

Thank 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."

W4 (More clients):

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$).

Tab. 1 Calculated egalitarian fairness bound and Actual achieved egalitarian fairness under fully-connected

Tab. 2 Calculated egalitarian fairness bound and Actual achieved egalitarian fairness under partially-connected

Q1 (Experiments):

Thank you for your question. Our experiments highlight two key findings:

• The theoretically derived achievable egalitarian fairness bounds align closely with the fairness achieved in a stable FL system, confirming their tightness.
• 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.

Q2 (Tightness):

Thank 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.

We are delighted that the reviewer found our work novel and valuable, with robust theoretical support. Thank you for your positive opinions and insightful comments.

W1 & Q1 (More complex and diverse FL scenarios):

Thank 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$).

Tab. 1 Calculated egalitarian fairness bound and Actual achieved egalitarian fairness under fully-connected

Tab. 2 Calculated egalitarian fairness bound and Actual achieved egalitarian fairness under partially-connected

We'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."

W2 & Q2 (Sensitivity):

Thank 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. Following the same settings as the mean estimation task in Section 6, we constructed three types of network topologies:

• T1: fully connected;

• T2: 0 (20), 1 (40) - 2 (50) - 3 (100) - 1 (40) , where only clients 1, 2, and 3 are connected;

• T3: 0 (20), 1 (40), 2 (50) - 3 (100), where only clients 2 and 3 are connected.

According 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. The 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.

W3 (Check the use of "clients'" and "client's"):

Thank you for your comment. We have checked the use of 'clients'' and 'client's' throughout the paper and verified their logical and grammatical correctness.

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.

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

Q1 (Privacy):

FedAvg can provide differential privacy with modest added noise, i.e., DP-FedAvg [1] adding Gaussian noise to the final averaged update to ensure privacy.

[1] McMahan, H. Brendan, et al. "Learning Differentially Private Recurrent Language Models." ICLR. 2018.

Q2 (Terminology):

The 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].

[2] Kate Donahue and Jon Kleinberg. Fairness in model-sharing games. WWW '23. 2023.

Q3 (Variables in Lemma 1):

The 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.

Q4 and L2 (Overfitting):

Overfitting 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!

Q5 (Lemmas 2,3,&4):

The 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.

Q6 (IID and Variance):

Clients are heterogeneous as they have different parameters governing their data distribution and different amounts 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.

Q7 and Q8 (Welfare function):

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: $u_i(\pi_g) = \left( \sum_{i=1}^{|F_i|} w_i err_i^q(\pi_g) \right)^{\frac{1}{q}}$.

The coalition $\pi_g$ remains core-stable if, $\exists i\in \pi_s,\left( \sum_{i=1}^{|F_i|} w_i err_i^q(\pi_g) \right)^{\frac{1}{q}} \le \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}}$.

Following a similar process in Appendix Eq. (16)-(27), we 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_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 ) }$. When 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.

Minor points (Sociological definition and terminology):

Thank 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!

L1 (FedAvg):

Regarding 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."

L2 (Overfitting):

Please refer to Q4 and L2 (Overfitting).

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.

W1 (Illustration):

Thank 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.

W2 (Navigation):

Thank 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.

W3 (Example 1):

Thank 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:".

Thank you for the authors' response. My comments have been well addressed.