You Get What You Give: Reciprocally Fair Federated Learning
Authors: Aniket Murhekar
Jiaxin Song
Parnian Shahkar
Bhaskar Ray Chaudhury
Ruta Mehta
Venue: ICML 2025 poster (2025)
Keywords: Federated learning
Nash equilibrium
mechanism design
fairness
Primary area: social_aspects->fairness
TL;DR: We design a mechanism for federated learning which is fair and encourages high accuracy, welfare, and data collection.

Abstract: Federated learning (FL) is a popular collaborative learning paradigm, whereby agents with individual datasets can jointly train an ML model. 
While higher data sharing improves model accuracy and leads to higher payoffs, it also raises costs associated with data acquisition or loss of privacy, causing agents to be strategic about their data contribution. 
This leads to undesirable behavior at a Nash equilibrium (NE) such as *free-riding*, resulting in sub-optimal fairness, data sharing, and welfare.
To address this, we design $\mathcal{M}^{Shap}$, a budget-balanced payment mechanism for FL, that admits Nash equilibria under mild conditions, and achieves *reciprocal fairness*: where each agent's payoff equals her contribution to the collaboration, as measured by the Shapley share. 
In addition to fairness, we show that the NE under $\mathcal{M}^{Shap}$ has desirable guarantees in terms of accuracy, welfare, and total data collected.
We validate our theoretical results through experiments, demonstrating that $\mathcal{M}^{Shap}$ outperforms baselines in terms of fairness and efficiency.

You Get What You Give: Reciprocally Fair Federated Learning
Aniket Murhekar'
Jiaxin Song² Parnian Shahkar
Bhaskar Ray Chaudhury 12 Ruta Mehta
Abstract
effective training. However, data sharing is often costly due to factors such acquisition costs (Tu et al., 2022), compu- tational expenses, and privacy concerns (Chen et al., 2020). As a result, agents may act strategically and reduce their data contributions, particularly if they bear high data shar- ing costs. This can lead to undesirable outcomes in terms of both fairness where agents receive benefits disproportion- ate to their data contributions and efficiency resulting in low data sharing. reduced total welfare, and suboptimal learning outcomes. To address these challenges, it is crucial to design mechanisms for federated learning that incentivize participation from strategic agents and also ensure faimess and efficiency at stable solutions (like a Nash equilibrium).
Federated learning (FL) is popular collaborative learning paradigm, whereby agents with individ- ual datasets can jointly train ML model. While higher data sharing improves model accuracy and leads to higher payoffs, it also raises costs as- sociated with data acquisition or loss of privacy, causing agents to be strategic about their data con- tribution. This leads to undesirable behavior at Nash equilibrium (NE) such as free-riding, re- sulting in sub sub-optimal faimess, data sharing, and welfare. To address this, we design MShap, a budget-balanced balanced payment mechanism for FI., that admits Nash equilibria under mild conditions, and achieves reciprocal fairness: where each agent's s payoff equals her contribution to the collaboration, as measured by the Shapley share. In addition fairness, we show that the NE under Shhapp has desirable guarantees in terms of accuracy, welfare, and total data collected. We validate our theoret- ical results through experiments, demonstrating that Shhpp outperforms baselines in terms of fairness and efficiency.
To this end, (Karimireddy al., 2022) introduce the data sharing incentivization frrentiizationfrrmeeooot in FL, where each feder- ating agent's 's net utility can be measured as the difference between the accuracy gained in the federation and the cost of data-sharing, and the agents are strategic about data con- tributions. (Karimireddy et al., 2022) then consider a mech- anism based on contract theory, where each agent receives a personalized model whose accuracy is tuned based on data contribution of the agent to the training (data-share maximizing mechanism). In a similar spirit, (Murhekar et al., 2023) study mechanism in the same framework with pay- ments, where agents may be charged/rewarded with money, such that any Nash equilibrium (NE) achieves the maximum utilitarian welfare possible under the mechanism (welfare maximizing mechanism). Observe that both the foregoing guarantees at NE are efficiency guarantees: they ensure max- imal data gain maximal welfare gain out of the federation.
1. Introduction
Federated learning (FL) provides an effective distributed learning paradigm where group of agents holding local data samples can train joint machine learning model. The paradigm has extensive applications, including autonomous vehicles (Elbir et al., 2020) and digital hcalthcare (Dayan et al., 2021; Xu et al., 2021a).
In this paper, we investigate mechanisms for FL, which are fair in addition to being efficient. Our notion of fair- ness is reciprocity: a mechanism is considered reciprocally fair each agent is guaranteed a "reciprocal" final utility commensurate with her contribution to the learning process. Naturally, a reciprocal mechanism incentivizes participation from agents holding valuable data, which is in line with the goals of a mechanism designer for FL. Empirical evidence from behavioral economics (Fehr & Schmidt, 2006) further shows that contrast to the self-interest hypothesis', users seem to trust reciprocal mechanisms, especially in bargain- ing and co-operative environments (like FL), and this trust
The success of federated learning hinges on the availability of diverse, high-quality data from variety of agents for
'Department of Computer Science, University of Illinois, Urhana-Chann Champaaga,,,,,,,, Urbana, USA DDpparmment of Industrial Sys- tems Engineering, University of Illinois Chaama-Chammaagn, Ur- bana, USA 'Department of Computer Science, University of California, Irvine, Irvine, USA. Correspondence Bhaskar Ray Chaudhury <braycha illinois. Ruta Mchta <rutame- hta@ es. illiinoss.euu>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada, PMLR 267, 2025. Copyright 2025 by the author(s).
'Only material self-interest motivates all user participation

---

You Get What You Give: Reciprocally Fair Federated Learning
can lead to large voluntary participation.
metrics to measure the efficiency of a mechanism, namely, data gain and accuracy gain (formally defined in Sec. 3). For structured payoff' and cost functions used in the liter- ature (Karimireddy et al., 2022; Murhekar et al., 2023), we establish strong lower bounds (II(V)) on the data gain and accuracy gain of MS which improve as the number of agents n increases.
To formalize the foregoing statements in the context of FL, we define the reciprocity of a mechanism as the minimum over all Nash equilibria, the minimum over all agents, of the ratio of the benefit that an agent receives from the mecha- nism, 2 and her contribution to the benefit (accuracy) of all agents. In our work, we measure an agent's contribution to the total accuracy of all agents using the classical notion of Shapley value (Shapley, 1953) from cooperative game theory, as done in (Bhaskara et al., 2024; Wang et al., 2019; Sim et al., 2020; Ghorbani & Zou, 2019; Agarwal et al., 2019). We note that reciprocity r of any budget-balancee mechanism lies in [o, 1], with higher r implying better fair- ness. We observe that the efficiency-focused mechanisms in (Karimireddy et al., 2022) and (Murhekar et al., 2023) are not reciprocal (see Example 7 and Section 5), which brings us to the driving question of the paper:
We empirically evaluate our mechanisms on five datasets: MNIST, FashionMNIST, CIFAR-IO, Lumpy Skin Dis- ease, and a synthetic quadratic regression dataset. We compare the performance of the Nash equilibria of MMShaap and two baseline mechanisms - the mechanism M with- out payments, and the celfare-maximizing mechanism (Murhekar al., 2023). Our mechanism outperforms in metrics of reciprocity, data gain, accuracy gain, and total welfare (see Table 1).
We design distributed FL protocol FedBR-Shap to approximately compute the NE of MSShap, Unlike prior work (Karimireddy et al., 2022; Murhekar et al., 2023), our protocol relies exclusively on gradient information, eliminating the need for sharing actual data points and uses actual model accuracies instead of assuming a closed form of accuracies, marking departure from prior work.
Are there reciprocal mechanisms that admit a Nash equilibrium? ? Do the Nash equilibria also provide effi- ciency guarantees in terms of total data contributed (as in (Karimireddy et al., 2022)), and total welfare achieved (as in (Murhekar et al., 2023))?
Our Contributions. We propose ballace- mech- anism for federated learning called MShhap which is recip- rocally fair and admits efficient Nash equilibria.
Although our theoretical results apply broadly, our proposed method is especially well suited to cross-sil silo federated learn- ing (see (Zeng et al., 2022)), where only a moderate number of clients participate in collaboration, and thereby Shapley- value computations remain tractable.
Shap admits Nash equilibria, which can be computed ef- ficiently through stochastic best response dynamics, under mild assumptions on agents accuracy and cost functions.
MShap is cost-agnostic, meaning it does not require knowledge of each agent's 's private data-sharing cost, thus alleviating the burden of cost- -ost-vrifiiation for the central server. Importantly, unlike previous cost-based payment schemes like (Murhekar et al., 2023) that unfairly reward agents with gigh-aqquisition-com and low-quality data, SShap only rewards agents with high-quality data.
1.1. Related Work
The subject of incentives in federated learning has received substantial attention (see (Tu et al., 2022) for detailed survey) as the federating agents indeed have benefits and costs (communication and computation (Tu et al., 2022), privacy loss due to generative adversarial attacks (Chen et al., 2020)). Several concepts from game theory (Stack- elberg games (Khan et al., 2020; Pandey et al., 2019), non co-operative games (Zou et al., 2019; Cheng al., 2021), auctions (Roy et al., 2021)) have been adopted for incentiviz- ing participation in FL. We remark that rewarding agents according to their contribution levels has been well moti- vated 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 (in line with the works of (Karimireddy et al., 2022; Murhekar et al., 2023) studying NE proper- ties, and (Chen et al., 2023; Cai et al., 2014) incentivizing the supply of high-quality data). In contrast, Chaudhury et
Shhap is fair: it is fully reciprocal, satisfies equal treat- ment of equals, and is individually rational.
Surprisingly, SSaha admits efficient Nash equilibria (NH), despite being designed for faimess. In particu- lar, there is no other mechanism that simultaneously Pareto-dominates the final data share and total welfare of MSShap, In other words, for every data share & that Pareto- dominates the data share at an NE of MShap, the total welfare at s will be strictly lower. Conversely, for every data share where the total welfare greater than that achieved at NE of Shhpp, there exists at least one agent whose data share is strictly lower in 8. We then define
Since this is the benefit the mechanism provides, this excludes the cost which is private to an agent
2

---

You Get What You Give: Reciprocally Fair Federated Learning
al. (Chaudhury et al., 2022) assume non-strategic agents who share their complete datasets, and under this setting guarantee coalition stability.
2.1. Payoff and cost functions: examples and properties
PayofT functions. We assume that each payoft function a; is bounded, non-decreasing and concave in the contribution of all agents. This is standard assumption in literature (Blum et al., 2021; Karimireddy et al., 2022; Murhekar et al., 2023), and captures decreasing marginal returns on increased data sharing. Below we present canonical exam- ples of payoff functions in common learning frameworks that satisfy the above assumptions.
The Shapley value (Shapley, 1953) is a well-studied con- cept from cooperative game theory, used to distribute the benefit of cooperation among participating agents. In feder- ated learning. Shapley value has been used to measure the contribution of participants (Wang et al., 2019; Xu et al., 2021b), interpret models (Wang, 2019), value data (Wang et al., 2020), and allocate profit (Song et al., 2019).
Example 1 (Generalization bounds from general PAC learning (Mohri et al., 2018)). Consider a general learn- ing problem of learning a model h from a hypothesis class H which minimizes the expected error R(h) B(e.))eee(h(())..) y) over a data distribution D, for some loss function e(-). Given m. i...d samples from D, the empirical risk minimizer (ERM) is the model hm arg minscH Eieim e(h(Iz), ye). (Mohri et al., 2018) prove that with high probability, the error of hm is bounded:
Finally, to illustrate practical payment mechanisms in FL, we highlight blockchain- bbase approaches that reward par- ticipants according to their individual contributions. Fed- Coin (Liu et al., 2020) uses a proof-of-Shapley protocol, while FedToken (Pandey et al., 2022) distributes tokens based on performance. Both require an initial budget, unlike our budget-balancee approach, which penalizes poor data quality and rewards high-quality data. Also in 1oT, BOppCL (Li et al., 2024) incentivizes vehicles in intelligent trans- portation systems, rewarding those with more useful data via eryptocurrency.
4 /2k(2 + log log(m/k) (m/k)))))))))))))))
1 1- R(hm)) 2 a(m) == ag
vm
(2)
where (1-6o) is the accuracy of the optimal model from H. and k: is a (constant) measure of the difficulty of the learning problem depending on e(-) and H.
2. Preliminaries
Problem formulation. We study the data-sharing incen- tivization framework introduced by (Karimireddy et al., 2022). There is a set N = [n]] of n agents who wish to solve a learning problem by training a joint model, and central server that coordinates among them. Agent transmits set Tú D of 8, i..dd data points sampled from the distribution D; of data samples available to i. Let S; = [0, π.] denote the set of feasible number of samples agent can contribute, and S ;= X, Sy. For sample vec- E S specifying the data contribu- tions of the agents, the central server returns model trained using the data set U, T, which has size || = Σ, 85.
In fact, there are other examples like linear, random discov- ery, and random coverage based accuracy functions (Blum et al., 2021) that also satisfy our desired criterion, and they are discussed in more detail in Appendix B.
Example (Empirical evidence). (Kaplan et al., 2020) and (Henighan et al., 2020) discuss empirical scaling laws re- lating to cross-entropy loss neural and large-language models for number of ML tasks relating to language, im- age, and video. They observe that the loss scales with the dataset size m as a power law {(m) = a m- for some parameters a, B E (0, 1].
tor ($1, .2..... s,.)
Every agent receives a payoff or benefit from federation as well as incurs a cost of sharing data samples. We measure the payoff to agent i from the jointly trained model using a payoff function a; : S > Rzo. Generally, we assume the payoff (s) represents the accuracy of the jointly trained model at the contribution level on agent i's learning task. However, our model allows for more general payoff func- tions. Moreover, each agent i incurs a cost associated with data sharing modeled using a cost function q St + ->o- Thus, each agent obtains a utility (s) at sample vector s given by the difference between the payoff received and the cost incurred, i.e.,
The above examples indicate the dependence of the accuracy (mm) on a learning task given m data points varies as a . m -3 both in theory and in practice.
Cost functions. We assume that each cost function c, is continuous, non-decreasing, and convex in 8;. This is also a standard assumption (Blum et al., 2021; Karimireddy et al., 2022; Murhekar et al., 2023), and captures non-decreasing marginal costs (Li & Raghunathan, 2014).
2.2. Nash Equilibrium
Recall from Equation (1) that the net utility of agent i is the difference between the payoff received and the cost incurred, Lee. (s = a, (s) - -s.)).. Since agents are net-utility max- imizers, the goal of an agent is to strategically decide how many samples to contribute so that her net utility is max-
4 = c,
(L)
We now discuss some canonical examples and properties of the payoff and cost functions.
3

---

You Get What You Give: Reciprocally Fair Federated Learning
imized. To analyze agent strategic behavior arising in FL, use the standard game-theoretic concept of Nash equi- librium (Nash, 1951)). Intuitively, the NE is a stable state of the system where no agent can increase their utility by unilaterally changing their data contribution level. Formally:
distribute the cumulative payoff' (see Appendix C). Lemma 2.3. For any E S, A(s) EiEN vf (s).
3. Mechanisms and Metrics for FL
Since NE is an intuitive and well-established solution con- cept that is guaranteed to exist, it is natural to examine the properties of a NE in the context of federated learning.
Definition 2.1 (Nash equilibrium (NE)). A sample vector E S is a Nash equilibrium if for every E N, and every s S we have (s) 2 uu(5), s-)) where (5% s-1) (81,...,,8 ...,,,,,..,.).. ).)).
Example 3. Consider two agents with identical payoff func-
tion a(s) 1 - [I|s]] + 1)-1 and linear cost functions given by (81) 0.1s1 and (2 0.2582. The only NE is given by S = (2.16,0).
The concept of best response provides an alternate, dynamic view of Nash equilibrium. Facing the sample vector 8-; of agents other than i, the set (i(s-:) of contribution levels of agent that maximizes her utility is defined as the best response set of agent i:
The above example shows that NE can be quite far from desirable: at NE, only agent 1 contributes data samples while agent 2 does not contribute at all and free-rides. Similar examples illustrate that NE can be far from optimal in terms of fairess, overall data shared (Blum et al., 2021), and overall agent welfare (Murhekar et al., 2023), all of which are part of the desiderata for federated learning solutions. To address some of these issues, prior works (e.g. (Blum et al., 2021; Murhekar et al., 2023)) studied mechanisms for FL that incentivize agents to contribute more data or admit NE with good welfare. Like (Murhekar et al., 2023), our work focuses on mechanisms with payments, formalized as follows.
fi(s-i) arg max { {a:(z, 8-1) - c()) S S. #ES;
The best response correspondence f is the set-valued func- tion given by f ; + X, 2 where [f(ss]] f((s-.). Thus, Nash equilibria are fixed points of this correspondence.
Proposition 2.2. A sample vector E S is a Nash equi- librium if and only if is fixed point of the best response correspondence, i.e., 8 E f()).
(Murhekar et al., 2023) proved that an FL problem admits a NE with concave payoffs and convex costs, but not without these assumptions.
Definition 3.1 (Mechanisms with payments). A mechanism M models the interaction between the central server and the participating agents. First, the server publishes the mech- anism by specifying a payment scheme p which indicates the payment (s) to each agent i at the sample vector 8. Second, the agents observe the mechanism, decide their data contribution levels {s; JEeN individually, and transmit the data to the server. Third, the server computes and returns a model trained on data contributed by all agents at the sample vector s, and returns the payment p: (s) to each agent j².
2.3. Shapley value
The Shapley value (Shapley, 1953) is a classic solution concept from cooperative game theory that specifies a fair way of distributing the surplus generated in a cooperative game. We adapt this concept in the federated learning con- text as follows. The total surplus generated at a sample vector 8 is the cumulative payoff to all agents given by A(s) := Σ (s). Let s[X] denote the sample vector restricted to agents in X, i.e., s[X] is the vector s' given by of = 8; for E X and s/ = O for i & X. To mea- sure the "contribution" of agent i A(s), we compute for every coalition X C N \ {i} of agents the marginal gain A(siX U (i))) - A(s(X]) of adding to X, and average it over all ways of forming the coalition. This represents the Shapley value of federation (s)) at 8, and is formally expressed as:
Thus, under a mechanism M with payment scheme p. the resulting utility of an agent E N is given by u,(s) 0g (8) - (s.:) + ps()).
A mechanism is said to weakly balance its budget if the total payment to the agents is not positive. A stronger condition is budget- which requires that the total payment to the agents is zero, i.e., the central server operates on no profit or loss.
Definition 3.2 (Budget-balanced mechanism). A mecha- nism is said to be weakly budget-balanced if for every 8 E S, ΣiEN (s(s) < 0. If the latter is an equality, then the mech- anism is budget-balanced.
-1 Σ n (1xI)
()
(A(sIX
n
XENVO)
(3)
NNte that if pa(s) < O. agent i must pay the server. We can enforce this by transmitting the model only after receiving payment from the agent. Thus for simplicity, we assume agent can only strategize on 8;-
The following lemma (adapted from the well-known prop- erties of Shapley values) shows that the Shapley values
4

---

You Get What You Give: Reciprocally Fair Federated Learning
We now define some fairness and efficiency metries to mea- sure the quality of mechanism M and its set of NE denoted by NE(M). Naturally, we are only interested in mechanisms that admit a NE
solution, efficiency is global property measuring aggre- gate quantities (like total payoff data shared) and must be contrasted against appropriate baseline. Our metries compare the NE of a mechanism M against the NE of the baseline mechanism M in the absence of payments. That is. (;( = 0 for all E N, 8 E S for the mechanism M
3.1. Metrics to Evaluate FL Mechanisms
Individual rationality. A mechanism M is said to be indi- vidually rational if every agent gets non-negative utility at its NE, i.e., for all & E NE(M), for all i, u:(8) 2 0. Thus, no agent can receive a negative utility by participating in an individually rational mechanism.
The first metric, called DataGain, compares the total quan- tity of data shared in the worst NE of M the total quantity of data shared in the best NE of the baseline M
Definition 3.6 (Data Gain of mechanism). The data gain of a mechanism M is defined as:
Fairness metries. By participating in the mechanism, each agent contributes towards the benefit of other agents while also reaping benefits from others. At sample vector 8, the contribution of an agent i from the mechanism is (s) + (s)) while the contribution to the mechanism is ( (s). The
min .ENE(M)
|s||
DataGain(M)
(5)
|
max EN
In similar spirit, we define metric AccGain to compare the cumulative payoff/accuracy of agents in a mechanism as compared to the baseline.
following fairness metric, termed Reciprocity, measures the
degree to which the worst NE of mechanism reciprocates the contribution of any agent.
Definition 3.7 (Accuracy Gain of a mechanism). The accu- racy gain of a mechanism M is defined as:
Definition 3.3 (Reciprocity of mechanism), The reci- procity of mechanism M is defined as:
min .ENE(M)
Σ/= (1(8)
min min (s(s) + p.(s) sENE(M) IEN (s)
Reciprocity(M))
(4)
Acc
Σ (s))
(6)
max EEEN((M))
Thus, mechanism M with reciprocity r < 1 has some NE 8 E NE(M) that reciprocates some agent i less than her contribution at s, ie.. is unfair. On the other hand, r > 1 implies that every NE reciprocates every agent strietly more than they contribute, The following lemma proves the intuitive fact that such mechanism must make total positive payment to the agents.
4. Shap: A Fair and Efficient FL Mechanism
Recall from Example 3 that NE of M in the absence of payments can force single agent to contribute data sam- ples while other agents are free-riding. Therefore, we seek mechanisms that admit a NE and are both fair and efficient. Towards this goal, we present a mechanism SSShap based on the Shapley value of FL.
Lemma 3.4. Any mechanism M satisfying weak budget- balance cannot have Reciprocity(M) > 1.
Definition 4.1 (Mechanism SSShap). Shahp is the mecha- nism with the payment scheme p given by
We note that reciprocates an agent exactly as much as their contribution. We refer to such 'truly fair' mechanisms as fully reciprocal (or just reciprocal for convenience). Lemma 3.4 shows that reciprocal mechanisms are the best one can aim for in terms of fairness among weakly budget-balanced mechanisms.
implies that every NE of the mechanism
p:(s) = p. - as(s), for any i N.N.S.. (7)
Note that ( is the contribution of agent i towards the cumulative payoff of the agents, while a;(s) is her payoff the sample vector Therefore, the above payment scheme can be interpreted as a fair compensation scheme: if an agent i contributes more than what she gets as a payoff, then she is compensated via a subsidy; conversely, if her contribution is less than her payoff, she is charged via a tax.
We now define a second fairness notion in the FL setting in- spired by the faimesss principle of equal treatment of equals (Moulin, 2002).
Definition 3.5 (Equal treatment of equals). Mechanism M satisfies equal treatment of equal contributors if for any sample vector s and two identical agents and j, (s))== Py (s))).
Cost-agnostic nature of SShap, In contrast to the mecha- nisms in (Karimireddy et al., 2022; Murhekar et al., 2023), MMShap is cost-agnostic since it does not require knowledge of the agent cost functions. This feature offers practical advantage: the central server (or other agents) does not need knowledge of an agent's 's cost function, which can some- times prove difficult for third-parties to estimate or verify
Efficiency metrics. We define two natural metrics to eval- uate the efficiency of a mechanism for federated learning. While faimesss a local property and can be evaluated at
5

---

You Get What You Give: Reciprocally Fair Federated Learning
in practice. Moreover, since the payment only depends on the actual contribution of agents to the cumulative payoff, no agent can gain by misreporting their cost functions, i.e., claiming they have a higher data collection cost than actual.
On the other hand, the NE of MS is 8* (3, 1.17). Thus both agents contribute the NE in MMShap and in fact s Pareto-dominates 8 Moreover, almost twice the amount of data is shared in the NE of MM as compared to M
Mechanisms that attempt to compensate agents with high acquisition costs and low data quality (e.g. the mechanism of (Murhekar et al.. 2023)) may unfairly penalize agents with high data quality and lower acquisition costs. In con- trast, our mechanism MShaa ensures that high-quality, high- acquisition-cost data is still incentivized for sharing, as the agent's 's payment will compensate their data sharing costs. However, Shap will not incentive agents with low data quality and high acquisition costs to share their data.
4.2. Nash equilibria of SSShap Best- Best-Response Dynamics
We next turn to the question of computing the NE of S For FL instances with strongly concave utility functions, it is known from prior work (Murhekar et al., 2023) that NE can be computed by following intuitive best-response (BR) dynamics. The dynamics begins with an initial sample vector s In step with sample vector s', each agent i updates her sample contribution proportional to the gradient (s") in the direction of increasing utility, while ensuring that the resulting vector s'+1 lies in the feasible region S. Formally, for a step size 8t > 0, the update in step t is:
By construction, the server operates on no profit or loss in our mechanism MShap (proof in Appendix D).
Lemma 4.2. The mechanism SSha is budget-balancee balanced.
s'41 =s +5 g(sss "²),,
(8)
4.1. Nash equilibria of SShap; Existence
where g(s", n²)) == Vu((') + ut for a specific choice of vector ju which ensures that si11 E S, given by:
We now prove that SShha admits a Nash equilibrium under standard assumptions on the utility functions as in Sec. 2.1.
V.ur(s')-
st sf + +5 (s) <0
Theorem 4.3, In any federated learning instance where for
at: 7
every agent E N the payoff function as(s) is concave in 8, and cost function ea non-decreasing and convex in sú the mechanism Shap admits Nash equilibrium.
p
Viui(s')+ + ge it v,u > >. 0, otherwise.
(9)
(Murhekar et al., 2023) show that for strongly concave utili- ties, the above BR dynamics converges to an s-approximate NE in Ollog ()-)) iterations.
Proof Sketch. The key idea is to prove that for a fixed s-i. uz (81, = bf (-)) 8-:)
is concave in 8,- This uses the concavity of payoffs a, and the convexity of costs G. Therefore, the best response set (s is non-empty interval, and hence that / is convex valued. Lastly, the con- tinuity of un in s implies the upper semi-continuity of f- Then Kakutani's fixed point theorem implies that f admits a fixed point, which then corresponds to a NE of Shap The detailed proof can be viewed in Appendix D).
(s))
In this section, we prove a stronger result: the convergence of stochastic best-response dynamics when utility functions are strongly concave. In stochastic BR, in each step t, we randomly sample set Rs of size k and perform BR dy- namics only for agents in Rt, for some fixed k E [n]. With g(s u²) defined as above, we define f(s', n², R³) E R" as the random vector given by:
Implications. Theorem 4.3 shows that our mechanism SShhap always admits a NE, i.e., stable-state of data contri- bution levels, as long as agent payoffs are concave and costs are convex. These mild assumptions are commonly satis- fied in practice, e.g. for all our motivating examples from Section 2. In the absence of this assumption, a NE is not guaranteed to exist even without any payments (Murhekar et al., 2023).
{ (g(st.u), u²), 0,
ifee
f(s", u', R²); Rt);
(10)
otherwise.
Then, for a step size 8¹, the stochastic BR update is:
+ = 8¹ + 8² f(s", ,,,rt)) R²).
(I))
Theorem 4.4. For a concave game where agent utility func- tions are (i) X-strongly concave: (G + X Inxn) is negative semi-defiitee and (ii) L-bounded derivatives: |Gyy S L. for constants X, L. > O, stochastic best response dynamics (11) with step size 8 = x=1 > converges to an approx- imate Nash equilibrium sf where l|g(ST 11=" )1/2 & in T iterations, where:
To illustrate how our mechanism circumvents free-riding by reciprocally sharing profits of collaboration, we revisit the setting of Example 3 and examine the NE under Shapp As shown below, we observe that all agents contribute data samples in the NE of Shaap as opposed the NE of M Example 4. Consider two agents with identical payoff func- tions a(s) = 1 [[|=|| + +1)-1, and linear costs given by (11) = 0.1s; and C2 ($2) ) = 0.25sg. Recall that the NE of
T = 2n²
(0(s8,10)))
M is given by 8 = (2.16,0 0) where agent 2 fiee-rides.
X2
log
E
6

---

You Get What You Give: Reciprocally Fair Federated Learning
The proof is deferred to App. D. Finally, we show that ShShap does satisfy conditions of Theorem 4.4, proving that its NE can be computed via stochastic BR dynamics.
Implications. Theorem 4.8 allows us to compare any sam- ple vector (e.g. the NE of some mechanism MM with the NE st of our mechanism SM in terms of data contribu- tions and utilitarian welfare. In particular:
Lemma 4.5. For a federated learning instance where agent (i) functions are X1 Ar-strongly concave and cost func- tions are X2 xz-strongly concave, and (ii) second derivatives of payoff's and costs are bounded: 88 Tsy S In and S'al S Inz for constants X1, 2,, I1, I/2 > 0, stochas- 88.
1. If all agents share equal or strictly higher data in than 8", then the welfare satisfies (s)) < W(s*). Thus, there is no mechanism M in whose NE agents contribute at least as much data as they would in the NE of MSShap while also achieving higher welfare.
tic best response dynamics (11) with step size 8 n=1 tho *22n converges to an approximate Nash equilib- rium SJ where I1a(s", 112) < E in T iterations, where:
2. Conversely, if W(s) 2 W(s*), then 8 does not weakly Pareto-dominate s". Thus, any mechanism M whose NE achieves higher welfare than the NE of MShhap, will nec- essarily have at least one agent who contributes strictly less data at the NE of M than at the NE of M SShap.
T 2n (2nL1 + L2)² (nd1 + A2)²
log |g(ss) )12
Implications of Theorem 4.4 and Lemma 4.5. The above results show that stochastic BR dynamics convergences for strongly concave games in O(log(=-)) iterations with an e-approximate NE. Indeed, we employ stochastic BR dynamics to compute NE of SSShap in our experiments (see Section 5.2). Note that the payoff and cost functions defined by generalization bounds (Equation (2)) and those observed in practice (Equation (12)) satisfy the assumptions of results.
Theorem 4.8 thus underscores that our reciprocal mecha- nism MShap exhibits favorable properties in terms of both data contribution at equilibrium (in the spirit of the mech- anism of (Karimireddy al., 2022)), and welfare (in the spirit of the mechanism of (Murhekar et al., 2023)).
We further formalize this by explicitly quantifying the data gain and accuracy gain of ShShap when the accuracy func- tions are identical and take a tractable form, and costs are (possibly different, but) linear. Examples and indicate that the accuracy (m) on a learning task with m data points varies as a(m) tivates us to assume the following canonical form for the accuracy a(s) of an agent i as function of the contribution vector s.
4.3. Fairness and Efficiency Properties of Shap
pu-m-1 -m- for a, B (0, 1]. This mo-
We now establish desirable properties of our mechanism SShpp, focusing on individual rationality, faimess, and ef- ficiency. We defer proof's to Appendix D due to space con- straints and highlight the key implications of our results.
a (() = ([|s]] + 1)8"
(12)
Lemma 4.6. Shap is individually rational.
Note that the normalization ensures that a(-) concave, and a(s) E [o, 1] for all S.
This shows that no agent will receive a negative utility by participating in our mechanism. Next, we show that MSShap satisfies the fairness principles outlined in Def. 3.3 and 3.5. Theorem 4.7. SShap satisfies Reciprocity(MMShhn = 1, i... is fully reciprocal. Moreover, MShap satisfies equal treatment of equals.
Theorem 4.9. Consider any FL instance with n agents
where agents have (i) identical payoff function a(s) =1 a . ([|s|] + 1)- for a > O and B (0, 1), and (ii) linear cost functions cs(s.) = %-- 8, + de for Yi d2 2 0. Then SShap satisfies:
Therefore, Shap ensures that every agent receives as much from the mechanism as their contribution to other agents.
(i) (ataGain(MMShap) 2 n - and
Having shown that Shhap is reciprocally fair, we next inves- tigate its efficiency properties in terms of data contributions, welfare, and accuracy. We first prove general tradeoff be- tween the data contribution and overall welfare (i.e., total accuracy minus costs) at the NE of our mechanism SShhp as compared to any other sample vector.
(ii) AccGain(MMShap > 1+ Bott (min, 76) ou
(1 (1-n 173) (1=)=1#))
Implications. The above theorem establishes lower bounds on aggregate quantities (total amount of data shared and cumulative payoff) in any NE of our mechanism Shahap compared to any NE in the absence of payments. We note that the gain in total data shared is at least π which is at least vn since 3 E (0, 1). This establishes that the gain in data shared increases with the number of agents n
Theorem 4.8. Let W(s) A(s) - Eve(n (8:) denote the total welfare of the agents, and let s" E NE(MSSh Consider any data contribution vector s that weakly Pareto- dominates s*, ie., 8; 2 8t for all i. Then W(s) < W(s*)
7

---

You Get What You Give: Reciprocally Fair Federated Learning
joining the federation, which is the natural expectation from mechanisms for FI.. Likewise, we observe that the gain in cumulative payoft' is strictly more than 1, and increases with an increasing number of agents.
by particular angles 10", 90" and 180", respectively. For the other two datasets, we set the dataset of one agent to consist of 70% positive data points and 30% negative data points, and the other agent vice versa.
The assumptions of linear costs and identical payoffs with forms similar to Eq. (12) are standard in prior works (Blum et al., 2021; Karimireddy et al., 2022: Murhekar et al., 2023). In our experiments (Sec. 5), we observe that SM outper- forms other mechanisms in terms of data gain, accuracy gain, and reciprocity, even without making any assumption on payoff functions taking a particular form, e.g., (12).
Interpretation of sample vector s. We note that, in our implementation, unlike the model described in Sec. 2, we do not ask agents to transmit data the central server. Instead, agents perform training locally and only transmit the gra- dient information to the central server. Hence, the number of data samples is interpreted as the number of batches trained by agent i during each local training.
5. Empirical Evaluation
Closed-form accuracy and cost. We assume the accuracy function of an agent in the i-th group is in the form of
In this section, we compare the performance of our mecha- nism Shap with two baselines M and .M (Murhekar et al., 2023) tailored to maximize welfare. In See 5.1, we compare the performance of the NEs found by the best response dynamics of the three mechanisms when the accu- racy and cost functions are given as closed-form functions. In Sec 5.2, we provide a practical distributed FL protocol FedBR-Shap to approximately find an NE,
(5(8) 1+ Ltm Wi, EJEA, Sj
i i E
Before running the best-response dynamics, we randomly sample a number of data points from each group and per- form a normal federated training without strategic behaviors. After collecting a set of accuracy results, we fit the accuracy functions using the non-linear least squares method. After that, we assume the central server broadcasts all the param- eters {ws,e) (,E[[]] all agents. Meanwhile, each agent is assumed to incur linear cost: (s) 7/4 7 Sg, where % is set randomly in advance.
Datasets and local training. We evaluate the mecha- nisms on five datasets, including three magee-based datasets: MNIST, FashionMNIST, and CIFAR-10, a healtheare dataset (Afshari Safavi, 2021), and synthetic dataset. A simple CNN network is used for the local training for MNIST and FashionMNIST, and ResNet-10 10 (He et al., 2016) is used for CIFAR-10. We use ResMLP (Touvron et al., 2022) for local training of the healthcare dataset, which contains meteorological and geospatial features re- lated to Lumpy Skin Disease. In addition, create syn- thetic binary classification dataset with 10 input variables and perform a quadratic regression.
Based on the closed-form utility function, each agent can (approximately) compute the derivatives of the Shapley share at a specific sample vector 8. Note that our mech- anism requires that all agents operate with a synchronized sample vector. In cross-silo FL setting, where the number of participating clients is relatively small, this synchroniza- tion overhead is practical. For the case of n = 30 agents, the agents perform the Monte-Carie Carlo approximation by randomly sampling n log n = 102 permutations and computing the average. In contrast, for two agents, we directly compute the exact derivative of the Shapley value. We duplicate each experiment 3 times, and the appropriateness of the number of sampled permutations is supported by the low standard deviation of the reported results.
5.1. Performance of Nash Equilibria
In this part, we implement the best response dynamics (as described in Sec 4.2) for the three mechanisms and compare the performance of the NE found by best response dynamics.
Setup. We set the number of agents as 30 for the three image-based datasets (MNIST, FashionMNIST, and CIFAR- 10) and randomly sample 10 agents to update their shares in each iteration. For the remaining two datasets, we set the number of agents to two and perform no sampling. We adopt the statistical heterogeneous setting: the datasets of the agents are Non- Jon-Indepnnd Identically Distributed (Non- IID) (Ye et al., 2023). We partition all the agents into T groups. Denote the agents in the t-th group by A,. In the three image-based datasets, the agents are equally parti- tioned into three groups (i.e., T = 3), each of which con- tains 10 agents. The images of the three groups are rotated
Experimental results. Table reports the performance of the NEs of SSShap and the two baseline mechanisms. The tables report the model accuracy, welfare, data gain, and the reciprocity of the mechanisms. The "Avg Accuracy" column reports the average accuracy of the final model evaluated on all agents' test datasets. It is worth noting that Table I reports the actual accuracies of the models trained using the data contributions at NE. The "Data Share" column shows the ratio of shared data to total data. For the two columns "Data Gain" and "Accuracy Gain",, we report the relative
8

---

You Get What You Give: Reciprocally Fair Federated Learning
Table I. Performance of the NEs of Shap and the two baselines M and M
Avg.
Accuracy (%)
Data Share (%)
Data Gain
Accuracy Gain
Reciprocity
Dataset
M
M
M
M
M
M
.M'
M
M
M
M
M
M
M
M
MNIST
88.3
87.6
90.4
5,8
7.6
54.9
1.00
1.32
9.51
1.00
0.99
1.02
0.61
0.70
1.00
FashionMNISTT
60.9
61.5
63.3
4.1
6,2
54.8
1.00
1.51
13.43
1.00
1.02
1.05
0.47
0.75
1.00
CIFAR-I0 10
43.6
44.7
48.5
25.6
28.9
99.6
1.00
1.13
3.89
1.00
1.02
1.11
0.50
0.57
1.00
Humpy-Skin-Diseeee
94.2
94.0
95.2
46.7
46.7
81.3
1.00
1.00
1.73
1.00
0.98
1.01
0.92
0.02
1.00
Quadratic
67.2
65.8
90.8
3.3
4.0
99.6
1.00
1.25
31.18
1.00
0.98
1.36
0.93
0.95
1.00
values of data share and accuracy compared to the baseline mechanism M
model. For example, an agent may skip local training if the current model is already good enough for her.
Our results demonstrate that our mechanism Shap outper- forms baselines in terms of both faimess and efficiency.
To address the limitations mentioned above, design distributed FL protocol, FedBR-Shap, which implements MSShap in practice and approximately computes NE in more realistic scenarios.
Shap significantly incentivizes agents to contribute more data compared to both baselines, evidenced by a 9.51 x data gain for MNIST, a 13.43x data gain for FashionMNIST, and a 3.89x data gain for the CIFAR- 10. FedBR-Shap also outperforms baselines in terms of accuracy, reporting an accuracy gain of x.02x to 1.11x x for the three mmage-based datasets. The accuracy gain is extremely high (1.36x) in the synthetic dataset.
computes NE while si- multaneously training a global model for the underlying FL task. FeaBR-Shap runs for T iterations. In each iteration, the central server updates the global model, and set of agents updates their sample vectors according to the transi- tion relation (Equation (8)) of best response dynamics. The update differs from the previous approaches as follows:
The central server gives payments to the agents at the end of every iteration. Each agent is allowed to change the number of samples s, during the training. The pay- ment follows M/Shap according to their contribution to the accuracy improvement for the current itcration.
We observe that the reciprocity of the baselines is strictly lower than 1, indicating that they force some agents to contribute more to the federation than what they receive. SShap is fairer as it is always fully reciprocal.
Our mechanism Shap guarantees reciprocal fairness in more practically meaningful scenarios. In the skin disease prediction task, the first agent possesses a large number of positive (i.e.. discase- pressett patient samples, which are expected to be more informative for the prediction task. The fitted accuracy functions in Sec E also reflect this.
There are no publicly known closed-form accuracy func- tions. Instead, at iteration f, each agent E [n]] locally trains two models T. and 7F using of and sf + batches of its local dataset. The central server updates its global model 0--1 1 to O using all the T;. In addition, aggregates set of intermediate models using subsets of T, and Tу. The central server then distributes the intermediate mod- els to the agents, which enables them to approximately estimate the derivative of the utility function and update their samples correspondingly.
Observe that, in the NEs of the two baselines, agent even needs to share more data than the second agent (who possesses lower-quality data): the NEs in M and BB are respectively (30.5%, , 18.1%) 1%) and (30.6%, 18. 18). In contrast, in Shapp the NE is (38.1%) 1%,5% 55)4%)...... indicating that agent 2 should contribute more than agent in the NE. The finding also highlights the reciprocal faimesss ensured by Shap
We emphasize that FedBR-Shar is truly distributed pro- tocol for FL, as it does not involve actual data sharing, only relies on the gradients of each agent's 's local datasets, and does not make any assumptions about accuracy functions obcying a closed-fore -orredd-oommmo expression. This is unlike prior im- plementations of mechanisms for FL (e.g., Sec. 5.1, (Karim- ireddy et al., 2022; Murhekar et al., 2023)). Moreover, F FedBR-Shap does not merely calculate a single NE. We take an observation window size W and treat the sample vector collected over every W iterations as the NE for that stage. We defer the complete description and pseudo-codes of F redBR-Shap to Appendix F.
5.2. FedBR-Shap: FL. Protocol for Shahp
Note that the above computation of NE relies on known closed-form accuracy functions. Unfortunately, a closed- form accuracy function may not always be possible, espe- cially when the information about the agents' dataset is inaccessible. Moreover, another restriction of the above im- plementation is assuming agents are always training on fixed number of batches throughout the learning process. How- ever, an agent may not always follow a static strategy in real training and can adjust it strategically based on the current
9

---

You Get What You Give: Reciprocally Fair Federated Learning
Acknowledgements
Chen, Z., Fu, A., Zhang, Y., Liu, Z., Zeng, F., and Deng, R. H. Secure collaborative deep learning against gan attacks in the internet of things. IEEE Internet of Things Journal, 8(7):5839-555 5849, 2020.
The research of Bhaskar Ray Chaudhury is supported by the NSF CAREER grant CCF No. 2441580. The research of Aniket Murhekar and Ruta Mehta is supported by NSF grant CCF 2334461.
Cheng. W. Zou, Y., Xu, J., and Liu, W. Dynamic games for social model training service market via federated learning approach. JEEE Transactions on Computational Social Systems, 91):644-55 2021.
Impact Statement
The goal of this paper is to advance fairness in machine learning, specifically in the context of federated learning- Potential societal consequences of our work include the design of fairer federated learning protocols. Since fairesss often subjective notion, it is conceivable for fairness notion of reciprocity to conflict with other desiderata.
Dayan, I., Roth, H. R., Zhong, A., Harouni, A., Gentili, A., Abidin, A. Z., Liu, A., Costa, A. B., Wood, B. J., Tsai, C.-S., et al. Federated learning for predicting clinical outcomes in patients with covid-19. Nature medicine, 27 (10):1735-1743, 2021.
Elbir, A. M., Soner, B., and Coleri, S. Federated learning in vehicular networks, arXiv preprint arXiv:2006.014 01412, 2020.
References
Afshari Safavi, H. Lumpy skin disease dataset, 2021. URL https: / ootoi.org/ii www.1166////bbbbnmm
Fehr, E. and Schmidt, K. M. The economics of fairness, reciprocity and altruism experimental evidence and new theories. Handbook of the economics of giving, altruism and reciprocity, 1615-691, 2006.
Agarwal, A., Dahleh, M. A., and Sarkar, T. marketplace for data: An algorithmic solution. In EC, pp. 701-726. ACM, 2019.
Bhaskara, A., Gollapudi, S., Im, S., Kollias, K., Munagala, K., and Sankar, G. S. Data exchange markets via utility balancing. CoRR, abs/2401.1 13053, 2024.
Ghorbani, A. and Zou, J. Y. Data shapley: Equitable valua- tion of data for machine learning. In ICML, volume 97 of Proceedings of Machine Learning Research, pp. 2242- 2251. PMLR, 2019.
Blum, A., Haghtalab, N., Phillips, R. L., and Shao, H. One for one, or all for all: Equilibria and optimality of collab- oration in federated learning. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Confer- ence on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 1005-1014. PMIR, 18-24 Jul 2021. httptt //tp////////////reee/eaaoo mlr. press/v133 htt////199//ll111 htm.l.l....mm......mmmmmmmmm.m..
He, K.,, Zhang, X., Ren, S., and Sun, J. Deep residual leamn ing for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Henighan, T., Kaplan, J., Katz, M., Chen, M.. Hesse, C., Jackson, J., Jun, H., Brown, T. B., Dhariwal, P., Gray, S., et al. Scaling laws for autoregressive generative modeling. arXiv preprint arXiv:2010.14701 2020.
Cai, Y., Daskalakis, C., and Papadimitriou, C. Optimum statistical estimation with strategic data sources. 08 2014.
Jia, R., Dao, D., Wang, B., Hubis, A., Gürel, N. M., Hynes, N., Li, B., Zhang, C., Song, D., and Spanos, C. J. Towards efficient data valuation based on the shapley value. Proceedings of AISTATS 2019, 2019.
Chaudhury, B. R., Li, L., Kang, M., Li. B., and Mchta, R. Faimess in federated learning via core-stability. arXiv preprint arXiv:2211 1.02091, 2022.
Kakutani, S. A generalization of Brouwer's fixed point theorem. Duke Mathematical Journal, 8(3):457 459, 1941. doi: 10.1215/50012-7704441--000 URL
Chen, Y. Zhu, J., and Kandasamy, K. Mechanism design for collaborative normal mean estimation. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M.. and Levine, S. (eds.), Advances in Neural Information Processing Systems, vol- ume 36. pp. 49405- Curran Associates, Inc., 2023. URL https::/pproceednngs.. neurips. ce ce/paper cc/paper_files/eeeeepppppeereeee [aaper_fflees/ppper/22//////// baf2blefaccf5lla1fe44e776556. http:///ae..aaaaaaeoooooooaaaaan
https: http://.....//...2../..
Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D. Scaling laws for neural language models.
2020. URL https: //arxiv.. org/abs.. /00p 08361.
pdf.
10

---

You Get What You Give: Reciprocally Fair Federated Learning
Karimireddy, S. P., Guo, W., and Jordan, M. Mechanisms that incentivize data sharing in federated learning- In Workshop Federated Learning: Recent Advances and New Challenges (in Conjunction with NeurlPS 2022), 2022. URL https: /ttpttps:///peeeevveeeeeee www./epww..ww...ome forum?
Nash, J. Non-cooperative games. Ann. Math., 54(2):286- 295, 1951.
Pandey, S. R., Tran, N. H., Bennis, M., Tun, Y. K., Han, Z., and Hong, C. S. Incentivize to build: A crowdsoureing framework for federated learning. In Proceedings-IFFFs Global Communications Conference, GLOBECOM, pp. 9014329, 2019.
1d=Bx4S2- 12x4422-55333 N5K3J.
Khan, L. U., Pandey. S. R., Tran, N. H., Saad, W., Han, Z., Nguyen, M. N., and Hong, C. S. Federated learning for edge networks: Resource optimization and incentive mechanism. IEEE Communications Magazine, 58(10): 88 98-93,22 2020.
Pandey, S. R., Nguyen, L. D., and Popovski, P. Fedtoken: Tokenized incentives for data contribution in federated learning, 2022. URL https: /ttp/aaaw....g....a....../o. abs/ 2209.09775.
Li, Q.. Wang. W., Zhu, Y., and Ying. Z. Boppel: Blockchain- enabled opportunistic federated learning applied in intel- ligent transportation systems. Electronics, 13(1), 2024. ISSN 2079-9292. doi: 10.33900electroniisss3000 13000136. URL httpttt/:/// www. htt/:/wwmpppppp mmpp....... www/ 9002/199921111 1/136.
Roy, P., Sarker, S., Razzaque, M. A., Mamun-or Rashid, M., Hassan, M. M., and Fortino, G. Distributed task allocation in mobile device cloud exploiting federated learning and subjective logic. Journal of Systems Architecture, 113: 101972, 2021.
Li, X.-B. and Raghunathan, S. Pricing and disseminating customer data with privacy awareness. Decision support systems, 59:63-73, 2014.
Shapley, L. S. pp. 307-318. ton, 1953. ISBN 978140088199 1970. doi: 10i:10.1515/ 9781400881990-0018 URL /ttt::://doi.orr//
17. A Value for n-Person Games, Princeton University Press, Prince-
Liu, Y., Sun, S., Ai, Z., Zhang, S., Liu, Z., and Yu, H. Fed- coin: A peer-to-peer payment system for federated leam- ing, 2020. URL httpsts::// arxiv wrgg /aaabb//00000 2002. 11711.
Sim, R. H. L., Zhang, Y., Chan, M. C., and Low, B. K. H. Collaborative machine learning with incentive-aware model rewards. In International conference on machine learning, pp. 8927-8923 PMLR, 2020.
Maleki, S. Addressing the computational issues of the Shap- ley value with applications in the smart grid. PhD thesis, University of Southampton, 2015.
Song, T., Tong, Y., and Wei, S. Profit allocation for federated learning. In 2019 IEEE International Conference Big Data (Big Data), pp. 2577-2586, 2019. doi: 10.1109/ SBDDate77900221999000
Mann, I. and Shapley, L. Values of large games, IV: Eval- uating the electoral college by Montecarlo techniques. Rand Corporation, 1960.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. Founda- fions of Machine Learning, second edition. Adaptive Computation and Machine Learning series. MIT Press, 2018. ISBN 9780262039406. URL battps://book.. google e. www
Touvton, H., Bojanowski, P., Caron, M., Cord, M., EI- Nouby, A., Grave, E., Izacard, G., Joulin, A., Synnaeve, G., Verbeek, J., et al. Resmlp: Feedforward networks for image classification with data-efficient training. IEEE transactions on pattern analysis and machine intelligence, 45(4):5314-53211 2022.
Moulin, H. Chapter 6 axiomatic cost and surplus sharing. In Handbook of Social Choice and Wel- fare, volume of Handbook of Social Choice and Welfare, pp. 289-357, Elsevier, 2002. doi: com/ Murhekar, A., Yuan, Z., Ray Chaudhury, B., Li, B., and Mehta, R. Incentives in federated learning: Equilibria, dynamics, and mechanisms for welfare maximization. In Oh, A., Neumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Informa- tion Processing Systems, volume 36, pp. 17811-17831. Curran Associates, Inc., 2023.
Tu, X., Zhu, K., Luong, N. C., Niyato, D., Zhang, Y., and J. Incentive mechanisms for federated learning: From economic and game theoretic perspective. IEEE transac- tions on cognitive communications and networking, 8(3): 1566-1593, 2022.
URL
Wang, G. Interpret federated learning with shapley values. arXiv preprint arXiv:/905.00 1905.04599, 2019.
Wang. G., Dang, C. X., and Zhou, Z. Measure contribu- tion of participants in federated learning. In 2019 IEEE international conference on big data (Big Data), pp. 2597- 2604. IEFE, 2019.

---

You Get What You Give: Reciprocally Fair Federated Learning
Wang, T., Rausch, J., Zhang, C., Jia, R., and Song, D. A Principled Approach to Data Valuation for Federated Learning, pp. 153-167. Springer International Publishing. Cham, 2020. ISBN 978-3-030-63076-8, doi: 10.1007/ 978-3-030-63307-88811 URL. https:ttt//..... /ttp//oooorrroooooooo//oooooooo. 10.1007/978 3 030 63076-8.80 8_
Xu, J., Glicksberg, B. S., Su, C.. Walker, P., Bian, J., and Wang, F. Federated learning for healthcare informatics.
Journal of Healthcare Informatics Research, 5(1):1-19, 2021a.
Xu, X., Lyu, L., Ma, X., Miao, C.,, Foo, C. S., and Low, B. K. H. Gradient driven rewards to guarantee fairness in collaborative machine learning. In Ranzato, M., Beygelz- imer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 16104-16117. Curran Associates, Inc., 2021b. URL http::: neurips. oc cc/paper_ p / 862c:3099003ccccfe44fff6a------3 pdf.
Ye, M., Fang, X., Du, B., Yuen, C., and Tao, D. Hetero- geneous federated learning: State-of-the-an and research challenges. ACM Computing Surveys, 56(3):1 (6(3))1-44, 1-44,144222 2023.
Yu, H., Liu, Z., Liu, Y., Chen, T., Cong, M., Weng, X., Niyato, D., and Yang, Q. fairnes--aware incentive scheme for federated learning. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pp. 393-399, 2020.
Zeng, R., Zeng, C.. Wang, X., Li, B., and Chu, X. Incentive mechanisms in federated learning and game-theone Iaaeettheretical approach. IEEE Network, 36(6):229-235. 2022. doi: 10.1 10.1999/ 12.211002...6
Zhang, J.. Sun, Q. Liu, J., Xiong, L.. Pei, J.. and Ren, K. Efficient sampling approaches to shapley value approxi- mation. Proceedings of the ACM on Management Data, 1(1):1-24, 2023.
Zhang. W., Lu, Q. Yu, Q. Li, Liu, Y., Lo, K., Chen, S., Xu, X., and Zhu, I.. Blockchain-baad -ased federated learning for device failure detection in industrial iot. IEEE Internet of Things Journal, 8(7):5926-500 5937, 2020.
Zou, Y., Feng, S., Xu, J., Gong, S., Niyato, D., and Cheng, W. Dynamic games in federated learning training service market. In 2019 IEEE Pacific Rim Conference Commu- nications, Computers and Signal Processing (PACRIM), 1-6. IEEE, 2019.
12

---

You Get What You Give: Reciprocally Fair Federated Learning
A. Discussion and Conclusion
Our goal in this work to address issues of fairness, efficiency, and data-sharing incentives faced by agents participating in federated learning who incur data-sharing costs. We propose a budget-balanced, reciprocally fair mechanism for federated learning, in which agents are incentivized via payments that reflect their 'contribution' the federation. We defined natural metrics called data gain and accuracy gain measure the efficiency of mechanisms for FL. We proved that our mechanism achieves significant gains for specialized forms of utility functions and substantiated this empirically.
Our work leaves several directions for future work. The first direction is establishing theoretical lower bounds on the data gain for a wider class of utility functions. Another direction is to further explore the trade-off between fairness and efficiency, by designing r-reciprocal mechanisms for < that achieve provably higher data gain. Lastly, investigating other profit-sharing methods instead of the Shapley share is another direction towards fair mechanism design for FL..
B. Examples
Example 5 (Linear or Random discovery (Blum et al., 2021)). Consider setting where each agent has a sampling probability distribution qi over given instance space X and gets a reward equalling qiz whenever the instance x is sampled by any agent. Then the expected payoff to agent i is (s) = (QQ"ss s),, where Q is a matrix given by Qii, = que for e and X. Here W QQ a symmetric PSD matrix with an all-one diagonal. Thus in this model, the payoff linear the sample vector and is given by (s) (Ws) s); for matrix W.
Example 6 (Random coverage (Blum al., 2021)). Consider modification of the setting in Example 5 where agent i obtains the reward 9tz only once if is sampled. Thus in this model, the payoff given by expected accuracy takes the form:
T Σ Qa II qin) E [0, 1]. ZEX
(1s)=1-1
(13)
Example Consider two agents with identical payoff functions a(s) = - (1|s|] + +1) and linear cost functions given by ei (s1) = 0.1s1 and ea (52) = 0.2582. Independently, the optimal contributions of the agents are sf 2.16 and s2 1 respectively.
According to the mechanism of (Karimireddy et al., 2022), the NE contribution ($1, 82) satisfies:
1
1
+ 66 (8) 8i),
81 + 82
8 +
1
1
+ (0.25 +5) (32 - -22),
81 + $2 +
$2 +1
where + 0. This leads to an NE given by 8 = (3.98, 2.46). At 8, the Shapley shares are co (s) = 00.9588 and (s) (s) = 0.7772, while the payoff is a(s) = 0.8656. This the reciprocity of the mechanism is 0.8656 0.9 < 1, i.e. the mechanism forces agent I to contribute more than she gets from the mechanism.
0.9535
C. Proofs from Section 2
Lemma 2.3. For any S, A(s) EIEN (p
Proof. Consider the summation of sp (s). For each subset X C [m], if X is non-empty and X * [m]. A(s[X] occurs in the first terms of all the (s)) for [X] times. Besides, it occurs in the second terms of all the (; for [X] times. Hence, the coefficient of A(s(X)) is given by
n 72-1 |X| - (1x - (n (n-
("
n
which is equal to zero. Besides, when X = [m], it only occurs at the second terms of yp (s). The coefficient of A(s[[n]) = A( As)) is given by 1 n- (2-1) -1 Additionally, since (0) = O, the summation of (o/(s) is equal to A(s). LI
13

---

You Get What You Give: Reciprocally Fair Federated Learning
D. Proofs from Section 4
Theorem 4.3. In any federated learning instance where for every agent i E N the payoff function (g(s) is concave in 8, and cost function e; is non non-decreasing and convex in Sy the mechanism M admits a Nash equilibrium.
Proof. We consider the best response correspondence / of agents under the mechanism MS Thus, f the correspon- dence given by:
[(8-1)= arg max arg wES,
(x) pr(ss)} arg max (z, 8-1) (x()) wES,
all i N, where the last equality used the payment rule of MShap given by (7). Using Proposition 2.2, we prove the existence of Nash equilibrium by showing that has a fixed point.
To this end, first note that f is defined over compact, convex domain S. Further, the continuity of a; and e; in implies that (8) == (s) (8:) is continuous in for each agent i. We now show that for fixed 8-in us u;(8;, 8-1) is concave in S4. Observe that:
S U
0 (s)
8cc
0
087
05?
n2 nn 1
-1
[AA(((X])
02c 0s
Σ
n
[X]
OsT
ds²
XCN\(()
1
Σ
n-
0 U
Pc 0s?
(since $ X)
X
0s7
XCNMO
0.
where the last step used the fact that A = Σ; aj is concave in and a; is convex in Since is concave in s; for any fixed 8-,. This implics that the best response set fi(s-.) is a non-empty interval, and hence that f convex valued. Lastly, the continuity of u; in s implies that f is upper semi-continuous.
8a. < 0, we conclude that uy
dsF
Kakutani's fixed-point theorem states (Kakutani, 1941) that every upper semi-continuous non-empty and convex valued correspondence defined over compact. convex domain admits fixed point. Since argued above that satisfies the conditions of Kakutani's 's fixed point theorem, we conclude that f admits a fixed point, and hence that SSShap admits Nash equilibrium.
Lemma 4.2. The mechanism MShap is budget-balanced.
Proof. At any sample vector
Eipp))))
0. using Lemma 2.3.
Theorem 4.4. For concave game where agent utility functions are (i) X-strongly concave: (G X Tuxa) negative semi-definite, and (ii) L-bounded derivatives: |Giyl S L. constants X, > O, stochastic best response dynamics (11) with step size 8¹ K-I n=
X converges to an approximate Nash equilibrium s where l[g(sT .HTT) < E in T iterations,
where:
2n T
log llg(s" 1 112
11)2
X
}|lp and [lg((t,, ,.) To do this, we first observe that by the definition of 4 +1 from (9), we have for every E [m], s* + .pe ba(+1)a >al I lg(s++1, ,,'))) This implies:
Proof. Our goal is to compare !!g(s +
|s a Ill (lg(s*+) ,n')l2
(14)
Next, we compare [|9(s*+1, p2))l22 and lg(s",, x²)llg Observe that:
( (a²) - g(s", 1x²) = (Vu(s(+1) + 11) - (Vu(s') + 1²)
(15)
= -Vuuss+t) vv((s)).
14

---

You Get What You Give: Reciprocally Fair Federated Learning
Using Taylor's expansion, we have:
Vu(stt1)- - Vu(s*) G(ss) (8 8'),
where s' = s² aasttt1 - 8²) for some a E [0, 1] and G is the Jacobian of V.. Using Equation (15), we get:
g(s uu) g(s" n²) G(s') (8 =²).
(16)
To bound the [[g(s update rule Equation (11) and relate g(s", μ²) with f(s", pe" R²).
100=,,,'))11 24)l22 in terms of llg(s', 4² 1l)1 using the above equation, we will use the stochastic BR dynamics
To this end, let D denote the uniform distribution over all subsets of size & drawn from the set of agents. By the definition of Equation (10), we have:
[[ p,, RRy] k ReD
.
(17)
Using Equation (14), we have [| 1² R1tt)l12 ||[ , 1 for all R+ This implies:
R R (1 (+
E
1 1+1 |l S
E
[ ,1", [12)]
R RD
(18)
E nーD
(1 n1, R l12)
where the equality used the fact that the sets R' and ++++1 are sampled from the same distribution D. We now relate f(s'+1 pt, R and f f(s ui, R') using (16):
f(s ,u, RT") = f(s", μ² R²) + IR- G(s') (8tt1- - st),
where Is E {0, 1jnxn is the diagonal matrix with FR [i, o] = 1 iff i E Rt. Using the update equation (11), we have:
1( R²) [(s', n², R²) + 8' Tna G(s') f(s', 1,,n0, R2").
(19)
Let us next evaluate the expected value of the rightmost term. Fix i [n].
E[ G(s'). n., R')) = E(n G(s')iis)) f(s", n², R²);
=Pr[i R Σ R
R lie l G(s))i.)) g(s k²);
(20)
k n n
Σ G(s')(i,j] g(s p²);
1-1 n n- (G(s') gos², p());
Taking the expectation of (19) and using the above equality, we get:
[f(s', 4², R²) 8t k k
[f( 11 u4, NR,R = E RD
E
(G(s') g(s" g(s",u²))
R
Using (17) in the above, we get:
0(s u²) = (Inxn + k k-1
G(s')) g(s", m²).
n n
With vy' = - 8/. (k-)
(1--1) (--T)
we get s( ,1²) (Jaxn + G(8))) g(st, n²))
15

---

You Get What You Give: Reciprocally Fair Federated Learning
Taking the 2 norm, get:
|g(s p²) = (lg(s",H')1
x²) -[G(s))) p²)ll 2n'g(s", " ,"),
(21)
By the strong concavity assumption, for a constant for any E IR". With g(s', J²),, we have:
0. G.A- Inxn negative semi-definite, i.e., x² D A Inxnuu 0
g(s', ( p²) 5 -X -A- All(ssss' : x²)l
(22)
Next we use the fact that the I norm ||l|| of an n x n matrix A is bounded by its Frobenius norm ||
||
|| sup 240 ||01|2
& ||A|F
ΣΣ Agg l
By the bounded derivatives assumption, we have (G(s')a)) S L. which implies that |[G('))l LE nL. This
gives:
[G(s")g((*) , n2)l22 S wTlllg(s x
(23)
Using (22) and (23) in (21), we get:
| (²)) (1+ n/.
-0n2- - (lg((s (0oss"''))) n²)
(24)
The definition 8 = n-1 k-1 2a1 implies that n² = n²1 Equation (24) together with Equation (14) gives:
A
llo(s 1 11 (1 (1-
12 11g(s* "l(ss,,''1
u²)l
n²T,3
Using the above inequality recursively, and using the inequality (1 - x)" vr, obtain:
llg(s' 22) se 200 " ||g( n ||2
a2
Thus in T' 2n x log (1(="M40)) iterations, we have 1 ,²2) S as claimed.
Lemma 4.5. For a federated learning instance where agent (i) payoff functions are λ1 st-stnngyyy concave and cost functions are Xz-strongly concave, and (ii) second derivatives of payoffs and costs are bounded: la,,da constants \1, X2, L1, L2 > O, stochastic best response dynamics (11) with step size 8' an approximate Nash equilibrium s where l!g(s". ,4" ,1"))l2 E in T iterations, where:
aa;
S In and 18 < T,,, for
nd converges to
k- (2nnti+
T 7n2-(2nL, + L2)² log (nd1 + +2)²
(0oss.,=))) E
Proof. We first show that each agent's 's utility function 4.(s) is (nd1 + 22) -strongyy concave as follows: for any e N,
8
n )x ( 8 ( (())))))))))
Pc
nd1 +
22 =
Σ
+ ndi + da
(By Eqn 7)
ds?
[
0s3
0s?
XCNM(
1
Σ
n (n-1)
-1
n m(--1) - d2 + nd1 X2
(By Assumption (i) and (ii)
11
X
XCN {i}
<
n + n \1 + A2 0,
16

---

You Get What You Give: Reciprocally Fair Federated Learning
which concludes the fact. Next, show that the second derivatives of uy are bounded. Observe that:
8u:
(s)
8c
Øs,
Ös,Osk
0s,Osk
1
Σ
11 (IXT) |X]
18 A(s
8a ÖsS0sk
n
Ös,Osk
Ös,0sk
1
[1 [--1) 1 -1 [X]
2nTh + L2
(By Assumption (ii) and A Σ a.)
n (1)
1
2 + L2 = 2 + L2.
n
With Theorem 4.4 and the above two inequalities, Lemma 4.5 follows.
Lemma 4.6. Shap is individually rational.
Proof. Let 8* E NE(MSShpp) Since s" is NE, each agent does not benefit from deviating unilaterally. Therefore, (s(s)) 2 (s'), where s/ = 0 and s' S} for all j * i. This shows us(s)) a;(s') ca(s,) = as('') 2 0. Thus, M individually rational.
Theorem 4.7. Shap satisfies Reciprocity(MMSnng Shaph = 1, i.e., is fully reciprocal. Moreover, MShap satisfies equal treatment of equals.
Proof. Consider any NE s E NE(A/ShaP). By definition of the payment rule of Mh given by Equation (7), (7))p(s))))(() f (s) for every E N. Thus Reciprocity(MMShng
To see why Shapp satisfies equal treatment of equals (Definition 3.5), consider two identical agents and j. az(-)) =a²(),
c. c.).) and s; Sy. Then, at NE s NE(MMShap) we have:
(s( = (8) c((s) = - E
1X (1=
(A() A(((())()))()))))))))))))))))- cs.))
XCNVH
1 Σ (7=²) |
-1
(1I) A(((())) cs(s))
n X
= (s) (s,) = (s).
where we replaced i with j in the penultimate step as they are identical agents.
Theorem 4.8. Les ((s) = A(s) EvE(n) (8:) denote the total welfare of the agents, and let s* E NE((MShap), Consider any data contribution vector s that weakly Pareto-dominates s", iee. S; 2 st for all i. Then W(s) < W(*)).
Proof. We first prove a useful Lemma.
Lemma D.I. For any sample vector E S and agent i N, 0A(x) de,
< (e)
Proof. We use the definition of the Shapley value of federation as follows to prove the lemma.
(x)
Σ
n n-
[A(s(X (U)
aA(s(X])
3s;
[X|
Os;
Øs;
XCNMH
1
Σ
n 1)
AAss[X U (i))
(since $ X)
|X]
Os;
XCMM}
17

---

You Get What You Give: Reciprocally Fair Federated Learning
Σ
(--1)
[X] 1)
-1
[A(s(N])
(using concavity of A)
n
as;
X
[A()(N])
asp
Since (s) strictly concave, we have:
W(s) < <<(<) (s
W((s)) (
(((A(s)-c((s))) (s a(A(s) c2(
a(A(s) ca((n))
,8 -
s*)
0s1
0s2
Dsn
Since 8, $ 2 0 for all i [n]. using Lemma D.I, have:
W(s) < W(*)) + ( (0(p)(s) (s1))
((p cu(Sal))
-
,8 -*)
0s1
0s2
ÜSn
Ws*))
where the last inequality follows from the fact that s is an NE.
Theorem 4.9. Consider any FL instance with agents where agents have (i) identical payolf function a(s) =
[| 1) for a > 0 and 8 E (0, 11, and (ii) linear cost functions c,(s;) = 7 8; + d, for %/s d; 2 0. Then MShap satisfies:
(i) (Mta) 2 n+7 and
( SMSSa)
F=F 9342 (min, 71) ) (1 - 1=3
Proof. We first show part (i). Let = arg minge "i be the set of agents with the least marginal cost denoted by 7kk = min Y Consider a NE 8 of the mechanism M without payments. At the NE, no agent has any incentive to change their contribution, i.e, (a,(=)
@cg(s;) Using this condition, we observe that a.f +1)0++ = % = Y for all E K.
De, = ds.
Moreover, o for all i $ K, since an agent & K has no incentive to contribute any data points. Thus, an NE 8 of M satisfies:
a
2+1
| +1=
(25)
Let consider any NE s* of MShap, By definition of NE, have that @=((s") dcg(s") for all N. Using linearity of costs and Lemma D.I, we that
Os.
Os:
BA(a") < % for all i, Explicitly computing the derivative gives us:
ds:
a.
n (1|* 11 + 1)8+1 S min 7s Yk.
In turn, this implies that ||s* + 1 ( [.-a. uo. (a मीं noo ([|s I + 1), using (25). Since n 2 1, this
implies ||s" lla 2 || Therefore:
||
88
+
DataGain(MMSaa)
2
notz
(26)
|
|
+1
thus proving part (i).
For part (ii), using the fact that agents have identical payoff functions, the accuracy gain given by:
A(s*)
a(s*)
Sccaain(MMShap
A(so)
a(s0)
18

---

You Get What You Give: Reciprocally Fair Federated Learning
1 - a (1 + 1)
a..a..l ([s"], 1)-8
(I|s 1)
([|s*] || + 1)-8
=1+a-
1 1 (1|= + 1)
(1|501 + 1)
a
2 1
[|| + 1)8
81 1)8
2
(1 (1- --1
(By Equation (26))
[||*
+ 1)8
(1 (1-n n Dीं
21+
(by Equation (25))
गगं %
2 2140011 BBtt
オहा (1 (1-n 041)
g
thus proving the theorem.
E. More Details of Best Response Dynamics
We the number of clients 30 for the three image-based datasets. Each client a) in MNIST has 175-191 batches of training data and 17-18 batches of testing data; b) in FashionMNIST has 173-192 batches of training data and 17-18 batches of testing data; c) in CIFAR has 27 batches of training data and 6 batches of testing data.
We use a simple CNN network with two x 5 convolution layers followed by two fully connected layers with ReLU activation for MNIST/FashionMNIST and the ResNet-15 18 (He et al., 2016) for CIFAR-1O. We use ResMLL (Touvron et al., 2022) for local training of the healthcare dataset and simple quadratie regression for the synthetic dataset.
Fitting the accuracy funetiinn. As described in Section 5.1, we perform a preprocessing training step to fit the accuracy functions in advance. Specifically, we first conduct lightweight standard FI. training without strategic sharing, using 0 and 200 batches from each group, respectively. We run the training for 100 epochs and the closed-form accuracy functions using the collected results. For the four non-synthetic datasets, the parameters of the closed-fome accuracy functions are as follows:
MNIST:
W11
W12
W13
3.1x 10 3
4.7 10
4.4 x 10
U121
U022
1023
6.7 10
1.9 10
6.5 10
U31
W/3
W33
9.3 10-1
8.3 10-4
2.1 x 10-3
MNShionMNISST:
W11
W12
W13
1.3 10-3
3.1 10
5.7 10
W21
UU22
U023
1.0 10
x 10-3
2.6 10
W31
W33
W33
4.9 10-4
10
1.6 10-3
CIFAR-10:
W11
Wh2
W13
5.8 10-3
1.4 10-3
7.9 x 10
W21
U022
1023
2.5 x 10-3
6.1 10-3
7.4 10
W31
W32
W33
4.2 10-3
3.0 10-3
1.8 10-3
Lumpy-Skin-Diseanl
Wi1
W12
1.2 x 10
9.1 x 10
W21
U22
1.4 x 10-2 1.6 x 10-2
The cost of adding one training data patch 7 is chosen uniformly at random from [0, 0.001] for MNIST, FashionMNIST. and CIFAR-10. We run the best response dynamics for all three mechanisms for 1000 iterations. We set the step size 8 of best response dynamics to 10, and the learning rate a is set as 0.1 for the local training.
19

---

You Get What You Give: Reciprocally Fair Federated Learning
System configuration. Our experiments were conducted on the Illinois Campus Cluster configured with one node with 16 cores, Fedora operating system, and one A100 GPU.
Approximation of Shapley value. We adopt simple Monte Carlo estimate for the Shapley value by uniformly sampling a set of permutations of clients II (Mann & Shapley. 1960; Malcki, 2015; Jia et al., 2019; Zhang et al., 2023). Let P. be the set of clients located in front of i in the permutation o. The approximate Shapley value of client i is given by:
(s) = I
Σ (A(s[P? U -il-- A(s((,))) cenl
(27)
Theoretically, for n agents, m = 2m In 2n samples ensure an error of c and confidence of 8. However, in the imple- mentation, we adopt more ambitious setting by sampling only [n log 102 permutations for the three image-base datasets, mentioned in See 5.1 of the first three image-base base datasets. To justify the soundness of the setting, report the standard deviation in Tables 2 to 4. It can be observed that all the statistics of MS has a standard deviation of no more than 0.1, which demonstrates the sufficiency of the current number of samples.
-" 5
DataShare(S) %%)
Reciprocity Avg. Med. 0 Avg. Med.
Accuracy(%)
DataGain Med. o
AceGain
Method
Avg.
Med. 0
Avg.
Avg.
Med. a
M
5.8 5.6 0.002
88.3 88.5 0.004 0.609 0.630 0.041
1.000 1.000 0.000
1.000 1.000 0.000
MBG
7.6 7.6 0.002
87.6 87.6 0.018 0.702 0.706 0.012
1.324
1.349 0.043
0.992 0.990 0.024
M Shap
54.9 54.9 0.000
90.4 90.5 0.006 1.000 1.000 0.000
9.514
9.719 0.354
1.024 1.022 0.004
Table 2. Standard deviation of MNIST
Accuracy(%) Avg. Med. 0 Avg. Med. a
DataShare (%)
Reciprocity Avg. Med.
DataGain
AceGain
Method
a
Avg.
Med.
a
Avg.
Med.
M
4.1 3.9 0.003 60.9 61.3 0.017 0.466 0.467 0.030
1.000
1.000
0.000
1.000 1.000 0.000
BB
6.2 6.2 0.001 61.5 61.1 0.011
0.752 0.759 0.020
1.513
1.558
0.078 1.023 1.023 0.012
Shap
54.8 54.8 0.000 63.3 63.4 0.016 1.000 1.000 0.000
13.436
13.895
0.795
1.054
1.069 0.055
Table 3. Standard deviation of MaShionMNIST
DataShare(f2) %))
Accuracy(%% (%)
Reciprocity Med.
DataGain
AccGain
Method
Avg. Med. a
Avg.
Med. 0
Avg.
Avg.
Med.
o
Avg.
Med.
o
M
25.6 25.7 0.005
43.6 43.9 0.009 0.504 0.505 0.007
1.000 1.000 0.000
1,000 1.000 0.000
MB
28.9 28.9 0.001
44.7 44.6 0.003
0.566 0.569 0.016
1.131
1.125 0.018
1.025
1.023 0.017
Shap
99.6 99.6 0.001
48.5 48.7 0.011 1.000 1.000 0.000
3.894
3.870
0.078
1.114
1.112 0.007
Table 4. Standard deviation of CIFAR-10
F. FedBR-Shap Protocol
F.I. Motivation of FedBR-Shap
Still, in this section, we interpret 8; as the number of batches of the local training of client i. As discussed before, the computation of NE in Section 5.1 relies on static closed-form accuracy functions of 8 and forces every client to use fixed s throughout the training. However, the influence of data sharing on the accuracy can differ across stages: data sharing can be quite beneficial in the initial phases, but may become less effective as the model converges. As result, data client may also exhibit strategic behaviors at different stages of the training, e.g., reducing the number of batches of local training when the model turns to converge. In addition, the aforementioned mechanisms only make payments at the end of the training, which makes it hard to evaluate a client's contribution to the training over various stages of the training.
Motivated by the above aspects, we propose the protocol FedBR-Shap, which is a truly distributed FL protocol. FedBR-Shap allows clients to adjust the value of 8; and also provide (budget-feasible) payments in different stages
20

---

You Get What You Give: Reciprocally Fair Federated Learning
of the training. The payment to agent i iteration depends on the contribution of agent i's data sharing towards the accuracy improvement at that iteration. We make the following assumption for the learning rate:
Assumption F.1. Assume the learning rate of model updating is set as small enough such that, within any window of W iterations, the improvement of the accuracy between two consecutive iterations, a,(0") - az (6"=1) can be approximated by some identical function og (s") that only depends on the sample vector at iteration l.
E2. Description of ShapR-Shap
SeapR-Shap computes the NEs of Shap following best response dynamics (Sec 4.2). In each iteration r, the algorithm computes global model 0', and maintains copies of local models T; trained only on agent i's dataset of size st. starting from the global model from the previous iteration, g--1, The central server then updates its global model, and the agents update their data shares according to their current gradients of the utility functions. As motivated in Appendix F.I, the growth of accuracy varies during the training process. For this reason, we divide the entire training into a series of stages and decide the payments at the end of each stage. Below, we first define our payment mechanism, which essentially adopts the same idea of Shap,, Thereafter, we provide the implementation of FedBR- Shap using best response dynamics.
Payments. A stage is defined as sequence of W iterations. The central server distributes payments at every stage according to everyone's 's contribution to accuracy improvement at that stage. Denote the accuracy of model 0 for agent i by (i()) and the model after the t-th iteration by 8'. The total accuracy increase at stage h is given by Ei= a;((") - E (f'- W), where = W. h. The central server then gives the payment
p = = s".) - (a:(0') (((--W))
to agent where (s), si denotes the Shapley value of agent towards the total accuracy increase at stage h, which is given by Eie(n) (0') a;(O'=W)
Best response dynamics. We follow the best response dynamics within every stage compute an NE of agents' strategies for the current training stage. If the clients take sample vector s, by Assumption F.1, the total accuracy increase EL= (0') - a, (0t-W) ) is given by W. ΣE= (8). Denote by ax()) the sum of (.)... Then the utility of client i is
n (s) W up (si, 8-2) 7i 83
Based on the utility function, FedER-Shap performs W rounds of best response dynamics to update s. Each agent i updates to of by computing the gradient of the current utility function, V.uV and hence the gradient of its Shapley share (st). This is estimated by the server as difference of Shapley shares, as
1 V (s)) ~ (5] +e,s")) - (s),
Approximation of Shapley share. Now consider an agent i, for which the goal is to compute the V.p? (s'). (s"). By Assumption F.1, we have (x(s) x Σj= (0++1) as (0'). Denote by 0x the model after aggregating the local models of clients from a set X starting from the global model 0% Therefore, the Shapley value of stage h can be approximated as follows:
pp (P
x
(00t) -
Σ
(100'u00-aa Σ
X=
To compute the derivative, beginning with the current global model 0², each agent E [n] updates its local model T; using
of batches of dataset. Moreover, each agent trains an extra model of TỤ on sf + batches of its local dataset, starting with 0t-1, All these models are transmitted to the server. For each subset X C [n] where &f X, the server computes a
single model: 8xx ix] Ejex T, by averaging the model parameters from the agents in X. For each subset X S [m]
where E X, the server computes two models: 0% 1 Σjex Tj. and 0% 1 (Tf + Ejex(( T3). The server then distributes these models to all agents, who report back with their accuracies.
21

---

You Get What You Give: Reciprocally Fair Federated Learning
With this information, the server computes (f((()) (s*) and yf (f + e, (.," using Eq. (3). Note that for subset X C [Tx] where i E X, the cumulative accuracy from 0xx is used for computing of ( sh while the cumulative accuracy from 0% is used for computing (f (sf + +E,s" For each subset X S [n]] where i & X, the cumulative accuracy of 8% used the computation both fpf (s), sh.;) and ( (sf + t., Since agents are aware of their costs, each agent computes V.u((s) [+1 using (11).
and updates its data share to 8;
Algorithm FedBR-Shap protocol
1: Input: number of iterations N, observation size W, learning rate a, step size 6, (0, 1), agents;
2: Output: Model weights 0 and individual contributions { Jhm1i
3: s' (1. 1). initialize 6 as gero-model and set t <- 1;
4: Each agent E [ra] transmits its local model parameters T2 to the server after training on s batches of data, initialized from the current global model 8
5: + [N/W];
6: while h S H do
7: Best response dynamics
8: for = W
1) to W H do
9:
Each agent i E [nx transmits its local model parameters T; to the server after training on sf batches of data, initialized from the current global model 0t along with model parameters T to the server, trained on more
batches of data;
10:
The central server updates the global model as 0c + EIER: Ti/n; for [n] do
The central server computes apt
(oi+e,e .) ( as described in Section 5.2, and sends
12:
dsc
along the new global model 6* to agent i;
13:
Agent i computes
Gus +-
(s
dec.
ds;
ds:
ds:
14:
if & + 8. Qu. De:
then
15:
8, ++1 +- 0;
16:
else
if s + 8-
aug 0s.
T then
17:
8 t Ti
else
8
1+1
at 8
dug. Osc
20:
end if
21:
1 ( + 1;
22:
end for
23:
end for
24:
> Payment according to the contribution of accuracy improvement
Central server computes the Shapley share of each agent of (s s'1;;
Each agent is paid p s (s
(a:(0') a0 (e0-W)) a0(t-W)))
27:
end while
28: return the model weights 0¹ and {8^ 1 J
22


Reviews:
[{"review_id": "jDc6VpNSb5", "reviewer": "Reviewer_Dvs1", "summary": "In this paper, $\\mathcal{M}^{\\text{Shap}}$ is proposed, a budget-balanced payoff mechanism for federated learning scheme: the _data-sharing game_ among strategic agents. The authors theoretically designed and elaborated that their proposed mechanism ensures _reciprocal fairness_: each agent's payoff is equal to its Shapley value contribution, admitting efficient Nash equilibria as well as achieving strong performance guarantees. Empirical results show superior fairness and efficiency compared to baselines on vision benchmark datasets.\n\n## Update after rebuttal\n---\nI updated the score to **accept** because the authors made a great effort to address all of my concerns.\nI have summarized below how my evaluation changes after the rebuttal:\n* The proposed method is theoretically sound and intriguing, but the empirical validation was not satisfactory.\n* During the rebuttal period, the empirical weaknesses are clearly resolved: the authors have faithfully performed additional experiments (**twice**) and the results are acceptable.\n* In addition, the authors have also agreed to narrow the scope of their paper based on the point raised by the review. I hope that this reconciliation will increase the visibility of the contributions of the proposed method in the field.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed feedback on our experiments and for appreciating our theoretical contributions.\n\nWe 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](https://www.dropbox.com/scl/fi/7q6m19rkdml94zo3zwrl8/submission8749_rebuttal.pdf?rlkey=797frtrobzqx62qdblefp08oy&e=1&st=9qc3dzov&dl=0)**.  We address the main weaknesses/suggestions below.\n\n**Q:** Experiments ignore statistical heterogeneity/ local evaluation\n\n**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].\n\n**Q:** Non-vision experiments\n\n**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).\n\nWe also request you to kindly read our response to Reviewer ir71 for experiments on a real-world healthcare dataset. \n\n**Q:** Theoretical justification for approximating Shapley value\n\n**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.\n\n**Q:** Additional references\n\n**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.\n\n**Q:** Consider narrowing the scope to cross-silo FL.\n\n**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.\n\n**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$...\"\n\n**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$.\n\n**Q1:** Yes, they are equivalent, and we will clarify this.\n\n**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.\n\n**References**\n\n[1] An Efficient Framework for Clustered Federated Learning, Ghosh et al. 2020 \n\n[2] Mechanisms that Incentivize Data Sharing in Federated Learning, Karimireddy et al. 2022\n\n[3] Incentives in Federated Learning: Equilibria, Dynamics, and Mechanisms for Welfare Maximization, Murhekar et al. 2023\n\n[4] Incentivizing Honesty among Competitors in Collaborative Learning and Optimization, Dorner et al. 2023\n\n[5] Addressing The Computational Issues of the Shapley Value With Applications in The Smart Grid, Sasan Maleki. 2015\n\n[6] Towards Efficient Data Valuation Based on the Shapley Value, Jia et al. 2019\n\n[7] Efficient Sampling Approaches to Shapley Value Approximation, Zhang et al. 2023\n\n[8] A Principled Approach to Data Valuation for Federated Learning, Wang et al. 2020", "claims_and_evidence": "### Main claim\n---\n$\\mathcal{M}^{\\text{Shap}}$ is a i) reciprocally fair FL mechanism that admits ii) Nash equilibria iii) with strong guarantees in performance under data-sharing scheme, iv) outperforming efficiency-focused baselines.\n\n### Breakdown  \n---\ni) *Reciprocal Fairness*: authors provided Theorem 4.7, which guarantees that the proposed mechanism is (fully) reciprocally fair, with sound derivations and acceptable assumptions (e.g., individually rational clients).\n\nii) *Nash Equilibria*: authors also provided Theorem 4.3, which guarantees the existence of Nash equilibrium under common assumptions (concave payoff and convex cost), which is supported by satisfying conditions of Kakutani’s fixed-point theorem\n\niii) *Performance Guarantee*: authors showed in Theorem 4.8 that the proposed mechanism achieves (weak) Pareto optimality at Nash equilibrium, and also guarantees data & accuracy gains by providing related lower bounds in Theorem 4.9 \n\niv) *Empirical Superiority*: in Table 1, the proposed mechanism consistently outperforms existing baselines across a few of vision benchmarks with a moderate number of agents (i.e., $n=100$).", "methods_and_evaluation_criteria": "- The experimental results assume identical payoff functions learned from local training, which may not hold in practical FL settings, especially under statistical heterogeneity (i.e., non-IIDness). The variations of real-world data quality are not fully explored in this regard.\n- While the simulated federated setting contains an acceptable number of clients with a proper client sampling ratio, the benchmark datasets are limited to vision classification tasks.\n- Existing baseline methods seems lacking; there already are incentive mechanisms similarly designed for FL (even using Shapley value), but they are not directly compared, except (Murhekar et al., 2023)", "theoretical_claims": "The theoretical expositions are well structured. I appreciate the authors' efforts since all claims are easy to follow, especially thanks to the accompanying 'implications' subsections.", "experimental_designs_or_analyses": "* The evaluation setting is a bit questionable. As stated in Appendix D.1, lines 882-883, the reported metrics are the performances of _a global model_ on a _global test dataset_. Please correct me If I understood wrong: I understood that the meaning of 'global' refers to the 'server-side holdout model or dataset'. The global evaluation scheme is valid when if we'd like to evaluate the global model's performance/generalization on unseen dataset or agents. However, the target of this paper is to evaluate the utility-fairness tradeoff _as a result_ of participating in the FL process. In this regard, I believe the local evaluation scheme should be adopted. Instead of assigning an identical local test dataset (c.f line 881), let each client has their own test set and evaluate the trained global model $\\theta^t$ on these local test set.\n* One of the main difference between FL and distributed learning is the existence of the statistical heterogeneity, i.e., non-IID nature between local distributions. While many non-IID simulation methods exist, it seems that current experimental design does not reflect this heterogeneity simulations (McMahan et al., 2018; Hsu et al., 2019). Without this, I think we can hardly believe that the empirical validation can really be extended to the _federated learning_ setting in practice.\n\n> (McMahan et al., 2018) Communication-Efficient Learning of Deep Networks from Decentralized Data  \n> (Hsu et al., 2019) Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification", "relation_to_broader_scientific_literature": "The proposed method can contribute to achieving the global welfare of federated or collaborative machine learning systems, where many participants (i.e. agents) are willing to contribute their data for local model updates, but they are also potentially free-riders. Thus, prevention of such malfare is important in practice, and it is guaranteed in terms of _reciprocal fairness_ in the proposed method.", "essential_references_not_discussed": "> (Xu et al., 2021) Gradient-Driven Rewards to Guarantee Fairness in Collaborative Machine Learning   \n> (Zeng et al., 2022) Incentive Mechanisms in Federated Learning and A Game-Theoretical Approach  \n* These to references directly used Shapley value, as the same in the proposed method, for the incentive mechanism design in federated settings, but they're neither discussed nor compared.  \n\n> (Chaudhury et al., 2022) Fairness in Federated Learning via Core-Stability  \n* This paper defines _core-stable fairness_, which is not identical to _reciprocal fairness_, but is closely related in its similarity of fairness concepts, e.g., the existence of similar fair equilibria in the collaborative setting.", "other_strengths_and_weaknesses": "Strength\n- The proposed method is well-supported by structured theories and designs.\n- The targeted problem is undoubtedly important for the overall welfare of the distributed learning system. \n \nWeakness\n- While theoretically sounding, the proposed method is not appealing in practical view. It requires full synchronization for acquiring $T_i, i\\in[n]$, which limits its applicability in practice (e.g., cross-device FL setting, where massive number of clients exist in the system). In addition, it also requires another communication for $T_i^\\epsilon$, as well as doubled local computations to obtain $T_i$ and $T_i^\\epsilon$, for the calculation of the difference of Shapley shares.\n- It is heartbreaking that the empirical validation of the proposed method seems lacking, questioning the statement of 'outperformance' of the proposed method compared to baselines. \n- While it's inevitable to use approximations (e.g., Monte-Carlo) to calculate the Shapley value in a reasonable time, using only 5 permutations is concerning as it can introduce an approximation error. Any ablation studies on this or theoretical justification would be appreciated.", "other_comments_or_suggestions": "* Please consider narrowing down the scope of the paper into _cross-silo FL_ setting (as in Zeng et al., 2022), where only a moderate number of reliable clients participate in collaboration. It's due to the statefulness design of the proposed method, such as i) the needs of full client participation as in lines 955-956 (i.e., line 7 of Algorithm 1) and ii) the existence of memory of contribution vector $\\boldsymbol{s}^t$ - which typically does not hold in cross-device setting as we cannot assume repetitive participation of clients in this setup (please see Table 1 of Kairouz et al., 2019) \n* Please change the global evaluation setting into local evaluation setting, and report corresponding results. In my humble opinion, it's more fair to evaluate how each client is benefited from participating in FL. If my thought is not aligned with the authors' intention, please generously enlighten me.  \n* Please repeat experiments with different random seeds and provide evaluation results with standard deviation.\n* Please consider conducting more experiments with smaller numbers of clients, e.g. $n=2, 10, 50$. For example, with $n=2$ and a simple quadratic model on a synthetic dataset (e.g., linear/logistic regression task), it would be more visible to understand the edge of theoretical claims provided. Regarding this, please refer to the experimental setup of (Chaudhury et al., 2022)\n* Please add more baselines, especially the ones in _Essential References Not Discussed_ section.\n* In eq. (5), the numerator should be $\\min _{\\boldsymbol{s} \\in \\mathrm{NE}(\\mathcal{M})} \\Vert \\boldsymbol{s} \\Vert_1$. \n\n> (Zeng et al., 2022) Incentive Mechanisms in Federated Learning and A Game-Theoretical Approach  \n> (Kairouz et al., 2019) Advances and Open Problems in Federated Learning  \n> (Chaudhury et al., 2022) Fairness in Federated Learning via Core-Stability", "questions_for_authors": "* In the pseudocode of Algorithm 1, what is the meaning of 'the central server runs FedAvg'? Is it equivalent to simple averaging of local updates, i.e., $\\theta^t \\leftarrow \\sum_{i \\in R^t} T_i / k$? If so, please discard the phrase, and if not, please enlighten me.\n* Can we say that $\\mathcal{M}^0$ is equivalent to the `FedAvg`, as well as utilitarian setting?", "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": "UZQC0FlZNs", "reviewer": "Reviewer_KBA3", "summary": "Summary:\n\nThe paper studies a method for incentivizing data contributions in\ncollaborative/federated learning, while also satisfying fairness criteria.\nThe authors propose evaluating the contributions from each agent via the Shapley value,\nbased on the value agents derive from the data, and design a payment scheme where agents\nget paid or need to pay based on how much value they are deriving from the aggregate data.\nThe authors show that a stochastic version of best response dynamics (BRD) converges to a\nNash equilibrium (NE), and provide guarantees on the efficiency of any NE.\nThey supplement this with experiments on three datasets.\n\n\nIncentives in FL is an important and timely problem at the intersection of machine\nlearning and game theory.  However, the novelty of the work is unclear, as several key ideas appear to be adapted from previous work (e.g., Murhekar et al.) without clear explanation of what is fundamentally new. The practicality of using payments in a federated learning scheme is not well-motivated. Moreover, several aspects of the paper, including the definition of reciprocity, the baselines for efficiency, and the need for a stochastic BRD are not properly motivated. For these reasons, I cannot recommend the paper for acceptance.\n\n\nDetailed comments:\n\n1. The paper would benefit from a more thorough discussion of when payments would be practical in a federated learning scheme. Are there real-world scenarios where payments have been successfully implemented in FL? \n- This point is particularly important since some agents may need to pay in addition to contributing data. The authors should provide a compelling use case to support the practicality of such a scheme. \n- While I acknowledge that some prior works (e.g., Murhekar et al.) have proposed similar frameworks, this does not eliminate the need for the authors to clearly justify their setting.\n\n2. The novelty of the work is not entirely clear. Several ideas seem to be inspired by Murhekar et al. (e.g., budget-balanced payments, the BRD scheme), and it is unclear which aspects are fundamentally new in this paper. \n- It appears that the primary contribution is adapting the techniques from Murhekar et al. to also account for fairness through the Shapley value. Is this understanding correct?\n- The concept of rewarding agents based on their contribution is not new in collaborative learning and has been previously explored (see [1, 2, 3] below). Moreover, prior works have also employed the Shapley value in collaborative learning schemes to determine agent rewards.\n- It would be helpful if the authors clearly summarized the key novelties and differences in the proof techniques early on in the paper under the \"Our Contributions\" section.\n\n3. The reciprocity term in Definition 3.3 does not appear to include the costs. Excluding costs from this fairness criterion seems arbitrary, especially since costs are being considered when defining the utility. The authors should clarify the rationale behind this choice.\n\n4. Regarding the BRD scheme, it is not clear what the set R_t represents in stochastic BRD. Why is a stochastic version of BRD necessary instead of using regular BRD?\n\n5. In Definitions 3.6 and 3.7, considering NE in a mechanism without payments as a baseline is somewhat unconventional. Generally, a baseline or comparator is expected to be a stronger benchmark, where the objective is for the algorithm to approximate or approach the baseline's performance. \n- Here, the baseline appears weaker since it does not allow payments, which explains why the ratio between performance is greater than 1 in Theorem 4.9. \n- A more reasonable baseline might be one that maximizes data/accuracy gain when agents are not strategic. \n- Furthermore, Theorem 4.9 is difficult to interpret, and additional discussion on how far the proposed method is from optimality would be beneficial.\n\n6. It would strengthen the paper to provide a more comprehensive discussion of related work, particularly including the following references:  \n   - [1] Cai et al., 2015, \"Optimum statistical estimation with strategic data sources\"  \n   - [2] Chen et al., 2020, \"Truthful Data Acquisition via Peer Prediction\"  \n   - [3] Chen et al., 2023, \"Mechanism Design for Collaborative Normal Mean Estimation\"", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and comments. We respond to the questions below.\n\n**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. \n\n**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. \n\n- 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). \n- Solution: [5] only use costs to determine payments, whereas we use contributions towards model accuracy. Thus the two mechanisms are fundamentally different. \n- 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].\n\n**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.\"\n\n**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.\n\n**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$.\n\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.\n\nAlso 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.\n\n**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.\n\n**References:**\n\n[1] FedToken: Tokenized Incentives for Data Contribution in Federated Learning, Pandey et al. 2022\n\n[2] FedCoin: A Peer-to-Peer Payment System for Federated Learning, Liu et al. 2020\n\n[3] BOppCL: Blockchain-Enabled Opportunistic Federated Learning in Intelligent Transportation Systems, Li et al. 2023\n\n[4] Mechanisms that Incentivize Data Sharing in Federated Learning, Karimireddy et al. 2022\n\n[5] Incentives in Federated Learning: Equilibria, Dynamics, and Mechanisms for Welfare Maximization, Murhekar et al. 2023", "claims_and_evidence": "See above.", "methods_and_evaluation_criteria": "See above.", "theoretical_claims": "See above.", "experimental_designs_or_analyses": "See above.", "relation_to_broader_scientific_literature": "See above.", "essential_references_not_discussed": "See above.", "other_strengths_and_weaknesses": "See above.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See above.", "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": "tUa4Wh82ws", "reviewer": "Reviewer_KV1s", "summary": "This paper proposes a payment-based mechanism for improving fairness in federated learning systems, allow Nash Equilibria that are fairer and incentivize strategic participants to share more data. Their approach is designed to ensure reciprocity, i.e. each agent receives exactly as much utility as their fair Shapley contribution towards the federation. The authors provide many useful theorems and properties, including the existence of efficient Nash Equilibrium, budget balancing and best-response convergence. Finally, they perform empirical evaluations with some popular image datasets and show strong performance compared to two reasonable baselines.\n\nPost-rebuttal Updates:\nThe authors addressed my questions in a satisfactory manner. I will keep my score and recommend this paper be accepted.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and comments. We respond to your questions below.\n\n**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?\n\n**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.\n\nNevertheless, 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:  \n\n$\n\\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)}\n$\n\nUnder 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:\n\\begin{align*}\n    \\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)},\n\\end{align*}\n \nThis 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.\n\n**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.\n\n**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.\n\n**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.\n\n**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.", "claims_and_evidence": "The paper supports all claims made, and provides intuition as well as proofs for them.", "methods_and_evaluation_criteria": "The proposed method is a natural construction to balance reciprocity and enjoys strong properties. The empirical evaluation is also a useful addition to the mostly theoretical paper.", "theoretical_claims": "Yes, I checked the theoretical proofs for budget balanced mechanisms and reciprocity, and for the admittance of Nash Equilibria. I also tried to check the proofs for the convergence of BR dynamics, and these seem correct to the best of my understanding.", "experimental_designs_or_analyses": "I checked the experimental design and results, and they appear sound. The evaluation compares against two reasonable baselines, and the results show the strong performance of the proposed approach on all tasks. The evaluation metrics also convey useful information in a condensed form, which helps in better evaluating the contribution.", "relation_to_broader_scientific_literature": "The paper proposes a useful payments-based mechanism for improving fairness in federated learning. This has many applications in real federated learning systems, and could encourage participation by stakeholders (particularly due to the guarantee of individual rationality), while ensuring there are no free-riders. The results show strong adherence to the reciprocity metric, which is evident by construction. I see it having applications in areas where acquisition costs are more homogenous, as that will prevent the feeling of unfairness because of varying input cost for the same return.", "essential_references_not_discussed": "The paper positions itself very well in related work.", "other_strengths_and_weaknesses": "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?", "other_comments_or_suggestions": "Page 2 \"in metrics of reciprocity, data gain, accuracy gain, data gain, and\" data gain is repeated\n\nIn the introduction, reciprocity is denoted with $\\beta$, but later on, $r$ is used (Section 3.1)", "questions_for_authors": "1. 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.\n2. 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.", "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": "afaTgnoGj8", "reviewer": "Reviewer_ir71", "summary": "The paper tackles the free-rider problem in a multi-agent federated learning environment by introducing MShap, a Shapley value-based, budget-balanced payment mechanism to enhance fairness and data gains. This mechanism achieves a Nash Equilibrium without requiring knowledge of agents' private cost functions. Experiments were conducted using the MNIST, FashionMNIST, and CIFAR-10 datasets.\n\n## update after rebuttal: \nI read the rebuttal of the authors as well as the questions of the reviewers. I maintain my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and comments. We respond to your questions below.\n\n**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.\n\n**A:** \nWe 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. \n\n**Q:** Datasets on real-world use cases, e.e., healthcare, could show how the results could generalize to new situations\n\n**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.\n\nWe 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:\n$$\na_1(\\textbf{s}) = 1- \\frac{1}{0.0129s_1 + 0.0050s_2 + 1}, \na_2(\\textbf{s}) = 1- \\frac{1}{0.0148s_1 + 0.0146s_2 + 1}.\n$$\nObserve 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. \n\n* 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%).\n* 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\\%).\n\nThus, 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.\n\nThe above results, along with the results of many new experiments, are detailed in **[Experiments](https://www.dropbox.com/scl/fi/7q6m19rkdml94zo3zwrl8/submission8749_rebuttal.pdf?rlkey=797frtrobzqx62qdblefp08oy&e=1&st=9qc3dzov&dl=0)**. \n\n**Q:** A formal complexity analysis of the Shapley value computation in FL settings is missing\n\n**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.\n\n**References:**\n\n[1] Addressing The Computational Issues of the Shapley Value With Applications in The Smart Grid, Sasan Maleki. 2015\n\n[2] Towards Efficient Data Valuation Based on the Shapley Value, Jia et al. 2019\n\n[3] Efficient Sampling Approaches to Shapley Value Approximation, Zhang et al. 2023\n\n[4] Lumpy Skin Disease Dataset, Afshari Safavi, Ehsanallah. 2021", "claims_and_evidence": "The main claims of the paper are:\n\n(1) MShap gives reciprocal fairness by rewarding agents in proportion to their contribution.\n     The payment mechanism is designed to align each agent’s utility with their Shapley value, which guarantees fairness by construction. \n     The paper provides theoretical proofs and experimental results that confirm this claim.\n\n(2) MShap achieves Nash equilibria\n    The paper proves it using Kakutani’s fixed-point theorem.", "methods_and_evaluation_criteria": "The paper uses Shapley value to achieve fairness, game theory for Nash equilibrium, and best-response dynamics for computation.\nThe datasets MNIST, FashionMNIST, CIFAR-10 have been used to evaluate the claims of the paper.", "theoretical_claims": "For example, theorem 4.3 on the existence of the Nash equilibrium. The proof makes use of Kakutani’s fixed-point theorem.", "experimental_designs_or_analyses": "The paper uses 3 datasets for experiments. It designs distributed protocol (FedBR-Shap) that \"relies exclusively on gradient information, eliminating the need for sharing actual data points\". Comparisons to baselines such as FL without payments and a welfare-maximizing mechanism have been done.", "relation_to_broader_scientific_literature": "The paper introduces reciprocal fairness by building on prior work on mechanism design such as Karimireddy et al., 2022; Murhekar et al., 2023. The use of Shapley values aligns with prior work on agent's contribution and  data valuation such as Wang et al.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths: The paper is written well and combines existing ideas in game theory and shapley values to address fairness in federated learning.\n\nSome weaknesses are lack of real-world validations, e.g., on healthcare etc. \nShapley value estimation can be computationally expensive.\nThere is no discussion on scalability when thousands of agents are involved", "other_comments_or_suggestions": "N/A", "questions_for_authors": "(1) The paper makes the claim that no other mechanism can simultaneously Pareto-dominate MShap in both data share and total welfare.\nHowever, only two baselines have been used for comparison. More complex baselines are missing.\n\n(2) Datasets on real-world use cases, e.e., healthcare, could show how the results could generalize to new situations\n\n(3) A formal complexity analysis of the Shapley value computation in FL settings is missing", "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:

Meta-review: Most Reviewers voted to accept this paper based on (1) the method is well-supported by structured theories and designs, (2) the problem is important, (3) the experiements are sound, etc., which I mostly agree with. The Reviewers also raised concerns which have been properly addressed. Thus, I recommend to accept this paper.
Decision: Accept (poster)