You Get What You Give: Reciprocally Fair Federated Learning

Thank you for your time and comments. We respond to your questions below.

Q: The paper makes the claim that no other mechanism can simultaneously Pareto-dominate MShap in both data share and total welfare. However, only two baselines have been used for comparison. More complex baselines are missing.

A: We would like to point out that our claim of "no other mechanism can simultaneously Pareto-dominate $\mathcal{M}^{Shap}$ in both data share and total welfare" is formally proven in Theorem 4.8. Since the claim is theoretically proven, it holds for all comparative baselines. Nevertheless, to empirically demonstrate the guarantees of our mechanism, we have included comparisons to two existing mechanisms for federated learning. We also conducted many new experiments, for which we request the reviewer to kindly refer to the response to reviewer Dvs1.

Q: Datasets on real-world use cases, e.e., healthcare, could show how the results could generalize to new situations

A: Thank you for the suggestion. As per your suggestion, we added one benchmark on lumpy skin disease prediction [4], where the input is the information of patients (regions, detection metrics, etc), and the output is whether to be identified as lumpy skin disease. We observe that there are unbalanced labels in the training datasets (much more negative data than positive data). Intuitively, positive data points are more helpful for forecasting disease, and our experiment also verifies this point.

We have two agents, each with 2000 data points. 70% of agent 1's data is positive, and 30% of agent 2's is positive. We train the model with varying numbers of samples from the two agents and learn closed-form accuracy functions given by:

Observe that the weight of $s_1$ is larger than that of $s_2$, which indicates agent 1's dataset is more valuable than agent 2. We ran best response dynamics for the three mechanisms and found the following results.

• The results of fraction shares are: (i) FedBR: (30.5%, 18.1%); (ii) FedBR-BG: (30.6%, 18.1%); (iii) FedBR-Shap: (38.1%, 55.4%).
• The accuracies of the two agents are: (i) FedBR: (93.5%, 95%); (ii) FedBR-BG: (93.5%, 93.5%); (iii) FedBR-Shap: (96%, 96.25%).

Thus, our mechanism outperforms the two baselines in terms of both data sharing and accuracy. Importantly, Agent 1 has a smaller fraction than Agent 2 in the equilibrium of our mechanism, which contrasts with the other methods. This aligns with the fairness guarantee of our mechanism: An agent with low-quality data should contribute more data points to balance the benefit (s)he receives from other agents.

The above results, along with the results of many new experiments, are detailed in Experiments.

Q: A formal complexity analysis of the Shapley value computation in FL settings is missing

A: Thank you for this question. We note that in the worst case, computing the Shapley value can take exponential time in the number of clients. For this reason, we turn to Monte Carlo estimation for computing the Shapley value approximately, as is common [1,2,3]. As shown in these works, to compute the Shapley value for $n$ agents within an error of $\varepsilon\in(0,1)$ and a confidence of $1-\delta$, it suffices to use $m = \frac{2n}{\varepsilon^2}\cdot\log(\frac{2n}{\delta})$. We will mention this formal analysis in our paper. We use $\varepsilon = \delta = 0.1$ in our new experiments.

References:

[1] Addressing The Computational Issues of the Shapley Value With Applications in The Smart Grid, Sasan Maleki. 2015

[2] Towards Efficient Data Valuation Based on the Shapley Value, Jia et al. 2019

[3] Efficient Sampling Approaches to Shapley Value Approximation, Zhang et al. 2023

[4] Lumpy Skin Disease Dataset, Afshari Safavi, Ehsanallah. 2021

Thank you for your time and comments. We respond to your questions below.

Q: I understand the benefits of not relying on the individual cost functions, however, I don't fully understand why not considering costs is a feature. To me, it seems like a simplification of the reciprocity requirement. The cost is part of the total utility an agent derives, so a perfectly balanced system could also balance this cost out, while ensuring no misreporting. I understand this is hard to do, but why would this not be better if it is possible?

A: We agree that a system that ensures costs are not misreported would be ideal. However, we consider that not relying on costs is a feature, because a fair mechanism under our definition of fairness (i) avoids the burden of verifying costs, (ii) retains its guarantees even if agents misreport costs, (iii) does not penalize high quality, low cost agents while still incentivizing high quality, high cost agents. In contrast, the above features will not hold for a "fair" mechanism where fairness is defined to incorporate costs.

Nevertheless, we agree that fairness can be defined in various ways, and alternative definitions of reciprocity could include agents costs. One such definition could be the minimum ratio of an agent’s total utility to their contribution to the federation’s welfare:

$\min_{s \in \mathit{NE}(\mathcal M)} \min_{i \in N} \frac{u_i(s)}{\varphi^W_i(s)} = \frac{a_i(s) + p_i(s) - c_i(s_i)}{\varphi^A_i(s) - c_i(s_i)}$

Under this definition, our mechanism $\mathcal{M}^{Shap}$ still achieves reciprocity 1. Further, note that $\min_{s \in \mathit{NE}(\mathcal M)} \min_{i \in N} \frac{a_i(s) + p_i(s)}{\varphi^A_i(s)} \leq 1$ for any weakly-budget balanced mechanism $\mathcal{M}$. Thus, we have:

$

\min_{s \in \mathit{NE}(\mathcal M)} \min_{i \in N}  \frac{a_i(s) + p_i(s) - c_i(s_i)}{ \varphi^A_i(s) - c_i(s_i)} &\leq \min_{s \in \mathit{NE}(\mathcal M)} \min_{i \in N} \frac{a_i(s) + p_i(s)}{\varphi^A_i(s)},

$

This implies that other baseline mechanisms will have even lower reciprocity under the new definition than under the current definition of reprocity (as reported in Table 1). Moreover, all our guarantees on data, welfare, and accuracy will continue to hold under this definition.

Q: There could be large costs (in terms of payments due) for someone participating with less data. Since the payment is decided only after training the model, is there any bound on how large this payment might be when agent i commits data s_i? Agents might have limited budgets which may affect their participation in the system.

A: At a sample vector $s$, the payment to agent $i$ is given by $p_i = \varphi_i^A(s) - a_i(s)$. If agent $i$ has to pay, i.e., $p_i < 0$, we obtain that an upper bound on $p_i$ is $a_i(s)$. That is, in the worst case, an agent will essentially have to pay $a_i(s)$ to obtain the data from other agents. That said, we agree that studying this problem when agents have limited budgets is a very interesting question for future work.

Q: On a related note, how is the payment system communicated to the agents? Are agents able to estimate their expected payments locally? It would be useful to walk through an example of how agents compute their best response share s_i, since this would depend on the payment they expect.

A: The payment scheme is published upfront. The share of agents are updated during best response dynamics by communication with the server, i.e., through evaluations on models to compute the Shapley share. However, if the accuracy functions of the agents are common knowledge and have a common test set (e.g. when small number of organizations with standard classification tasks), then agents can estimate their payments locally.

Thank you for your time and comments. We respond to the questions below.

1. Indeed, there are blockchain-based mechanisms for FL that involve payments based on contributions, such as FedToken [1] and FedCoin [2]. FedCoin uses a "proof of Shapley" protocol, while FedToken distributes tokens based on performance. Both require an initial budget, unlike our budget-balanced approach, which penalizes poor data quality and rewards high-quality data. Also in IoT, BOppCL [3] incentivizes vehicles in intelligent transportation systems, rewarding those with more useful data via cryptocurrency.

2.1. Although we work on the same data-sharing framework as of [4, 5] our specific problem objective and solution concepts are fundamentally different. Our primary contribution is a fair mechanism for FL that admits Nash equilibria with strong guarantees on data shared, accuracy, and welfare.

• Objective: [5] focuses on welfare maximizing mechanisms, while not worrying about fairness or data gain. Our goal is to design fair mechanisms, first and for most, that simultaneously has strong guarantees on data sharing, accuracy, and welfare (Thm 4.8 and Thm 4.9).
• Solution: [5] only use costs to determine payments, whereas we use contributions towards model accuracy. Thus the two mechanisms are fundamentally different.
• Techniques: The proofs of guarantees of our mechanism are novel. The proof of convergence of stochastic BRD generalizes the proof of [5] on BRD. Lastly, we use the standard (and one of the only) proof technique of using the Kakutani fixed point theorem to prove the existence of Nash equilibrium. The same technique is used by several other works, e.g. [4,5].

2.2. We request that you kindly revisit Sec 1.1 on Page 2 where we clarify this point: "We remark that rewarding agents according to their contribution levels has been well motivated and studied in FL (Wang et al., 2019; Sim et al., 2020; Zhang et al., 2020; Yu et al., 2020). However, the crucial difference is that our focus is to design a mechanism that incentivizes strategic agents, i.e., agents who strategize their data contributions based on the rewards they get from the federation so that desirable fairness and welfare guarantees are achieved at NE."

3. We do not include costs in the definition of reciprocal fairness, because a fair mechanism under our definition of fairness (i) avoids the burden of verifying costs, (ii) retains its guarantees even if agents misreport costs, (iii) does not penalize high quality, low cost agents while still incentivizing high quality, high cost agents, unlike [5]. In contrast, the above features will not hold for a "fair" mechanism where fairness includes costs. We also request you to read our response to Reviewer KV1s for a related discussion.

4. The set $R^t$ represents a random subset of $k$ agents chosen in round $t$. In round $t$, we perform BR dynamics (i.e., update the data shares) only for agents in $R^t$. A stochastic version is not necessary in general, but is practically useful in situations with large number of clients since it reduces computational and communication overheads in each round. Note that the convergence of stochastic BRD (Theorem 4.4) also implies the convergence of regular BRD, by setting $k=n$.

5. We agree that calling a no-payment mechanism a "baseline" is misleading and will avoid this term. Our goal was to quantify the data and accuracy gains enabled by our incentive mechanism with payments as compared to the mechanism without payments.

Also note that a mechanism maximizing total data or accuracy would require all agents to share their data fully. But with high costs, no budget-balanced mechanism can acheive this without large payments to the agents, which is not budget-balanced. Thus, a more meaningful baseline considers both accuracy and cost, like welfare maximization. In this context, we do provide theoretical guarantees against the welfare-maximizing baseline. Specifically, in Thm 4.8, we prove that a welfare-maximizing mechanism cannot achieve Pareto-dominating data contributions from individual agents compared to our mechanism. In fact, this is one of the unique and compelling features of our mechanism.

6. Thank you for highlighting the references. Although their primary focus is not on federated learning, we will include a discussion on aspects related to our work such as incentive mechanisms and avoiding free-riding.

References:

[1] FedToken: Tokenized Incentives for Data Contribution in Federated Learning, Pandey et al. 2022

[2] FedCoin: A Peer-to-Peer Payment System for Federated Learning, Liu et al. 2020

[3] BOppCL: Blockchain-Enabled Opportunistic Federated Learning in Intelligent Transportation Systems, Li et al. 2023

[4] Mechanisms that Incentivize Data Sharing in Federated Learning, Karimireddy et al. 2022

[5] Incentives in Federated Learning: Equilibria, Dynamics, and Mechanisms for Welfare Maximization, Murhekar et al. 2023

Thank you for your detailed feedback on our experiments and for appreciating our theoretical contributions.

We conducted several new experiments based on your suggestions. We ran each method thrice with different seeds, and observed that our mechanism consistently outperformed baselines in data gain, accuracy, and reciprocity. All results are in: Experiments. We address the main weaknesses/suggestions below.

Q: Experiments ignore statistical heterogeneity/ local evaluation

A: We perform new experiments with non-IID agents following Ghosh et al. [1]. We have 30 clients partitioned into 3 groups of 10 each. We equally partition the images in our benchmarks into three groups and rotate the images by 10, 90, and 180 degrees respectively, giving datasets $A_1, A_2, A_3$. We then map dataset $A_j$ to group $j$, and split it into local training and test sets. Thus, this experiment accounts for non-IIDness due to the rotated images and uses local evaluation. We observe improved data gain (3x), accuracy, and reciprocity (2x) even in this non-IID setting with local evaluation. Finally, we note that identical payoffs and IID test-data is assumed in prior work [2-4].

Q: Non-vision experiments

A: As suggested, we implement a quadratic model on a synthetic 2-classification dataset, where inputs $X\in \mathbb{R}^{10}$ has ten features and $y\in \{0, 1\}$. We randomly generate matrix $W$, vector $b$ and number $c$ by $W_{i,j}, b_i, c\sim \mathcal{N}(0, 1)$. We have 2 agents. For non-IID distributions, we sample 1000 points uniformly for each such that 80% and 20% of agent 1's and agent 2's data have positive labels. We observe significant improvements (~30x data gain).

We also request you to kindly read our response to Reviewer ir71 for experiments on a real-world healthcare dataset.

Q: Theoretical justification for approximating Shapley value

A: We approximate SV using standard Monte Carlo estimation [5-7]. For $n$ agents, $m = \frac{2n}{\varepsilon^2} \ln\frac{2n}{\delta}$ samples ensure an error of $\varepsilon$ and confidence $1-\delta$. In new experiments, we set $\varepsilon = \delta = 0.1$. We will include this analysis in our paper.

Q: Additional references

A: Thank you for pointing out the suggested references on Shapley value in FL. We will cite them. However, our work differs in both problem setting and solution. For example, Xu et al. (2021) measure contributions via Shapley value of cosine similarities in gradient updates, while Chaudhury et al. (2022) ensure coalition stability assuming full data contribution. In contrast, we study strategic data sharing with monetary rewards. Due to the differences, we did not use them as baselines. Zeng et al. (2022) survey FL incentives and mention Wang et al. (2019), whose FL Shapley share metric aligns with our Appendix D.2 setup, and we will cite this work.

Q: Consider narrowing the scope to cross-silo FL.

A: Our theoretical results are general, but we agree on focusing on the cross-silo setting (Zeng et al., 2022) with a moderate number of agents.

Q: "the proposed method... requires full synchronization for acquiring $T_i$, $i\in[n]$... it also requires another communication for $T_i^\varepsilon$, as well as doubled local computations to obtain $T_i$ and $T_i^\varepsilon$..."

A: We agree that synchronization is a challenge in our method, but this is true in almost all cross-device FL protocols with many clients. Based on your suggestion, we will focus on cross-silo FL. We note that our protocols account for scalability by sampling only $k$ agents per round for sample updates. Since we compute $T^i_\varepsilon$ only for these $k$ clients instead of all $n$, the total computations are reduced to $n+k$ from $2n$.

Q1: Yes, they are equivalent, and we will clarify this.

Q2: FedBR computes the NE of the zero-payment mechanism $\mathcal{M}^0$ is the zero-payment mechanism. Each round of FedBR employs FedAvg to train the model, so they are "equivalent" at equilibrium but not identical.

References

[1] An Efficient Framework for Clustered Federated Learning, Ghosh et al. 2020

[2] Mechanisms that Incentivize Data Sharing in Federated Learning, Karimireddy et al. 2022

[3] Incentives in Federated Learning: Equilibria, Dynamics, and Mechanisms for Welfare Maximization, Murhekar et al. 2023

[4] Incentivizing Honesty among Competitors in Collaborative Learning and Optimization, Dorner et al. 2023

[5] Addressing The Computational Issues of the Shapley Value With Applications in The Smart Grid, Sasan Maleki. 2015

[6] Towards Efficient Data Valuation Based on the Shapley Value, Jia et al. 2019

[7] Efficient Sampling Approaches to Shapley Value Approximation, Zhang et al. 2023

[8] A Principled Approach to Data Valuation for Federated Learning, Wang et al. 2020