Incentives in Federated Learning: Equilibria, Dynamics, and Mechanisms for Welfare Maximization
Authors: Aniket Murhekar
Zhuowen Yuan
Bhaskar Ray Chaudhury
Bo Li
Ruta Mehta
Venue: NeurIPS 2023 poster (2023)
Keywords: Federated learning
Nash equilibrium
Mechanism design
Welfare maximization

Abstract: Federated learning (FL) has emerged as a powerful scheme to facilitate the collaborative learning of models amongst a set of agents holding their own private data.  Although the agents benefit from the global model trained on shared data, by participating in federated learning, they may also incur costs (related to privacy and communication) due to data sharing. In this paper, we model a collaborative FL framework, where every agent attempts to achieve an optimal trade-off between her learning payoff and data sharing cost. We show the existence of Nash equilibrium (NE) under mild assumptions on agents' payoff and costs. Furthermore, we show that agents can discover the NE via best response dynamics. However, some of the NE may be bad in terms of overall welfare for the agents, implying little incentive for some fraction of the agents to participate in the learning. To remedy this, we design a budget-balanced mechanism involving payments to the agents, that ensures that any $p$-mean welfare function of the agents' utilities is maximized at NE. In addition, we introduce a FL protocol FedBR-BG that incorporates our budget-balanced mechanism, utilizing best response dynamics. Our empirical validation on MNIST and CIFAR-10 substantiates our theoretical analysis. We show that FedBR-BG outperforms the basic best-response-based protocol without additional incentivization, the standard federated learning protocol FedAvg, as well as a recent baseline MWFed in terms of achieving superior $p$-mean welfare.

Incentives in Federated Learning: Equilibria, Dynamics, and Mechanisms for Welfare Maximization
Aniket Murhekar
Zhuowen Yuan'
Bhaskar Ray Chaudhury' Bo Li
Ruta Mehta
University of Illinois, Urbana-Champaign faniket2,zhuosen brycce bryacha, 1bo,
rutamohh))eillnoos 1
edu
Abstract
Federated learning (FL) has emerged as a powerful scheme to facilitate the col- laborative learning of models amongst set of agents holding their own private data. Although the agents benefit from the global model trained on shared data, by participating in federated learning, they may also incur communication) due to data sharing. In this paper, we model a collaborative FL framework, where every agent attempts achieve optimal trade-off between her learning payoff and data sharing cost. We show the existence of Nash equilibrium (NE) under mild assumptions on agents' payoff and costs. Furthermore. we show that agents can discover the NE via best response dynamics. However, some of the NE may be bad in terms of overall welfare for the agents, implying little incentive for some fraction of the agents to participate in the learning. To remedy this, we design budget-balll balanced mechanism involving payments to the agents, that ensures that any p-mean welfare function of the agents' utilities is maximized at NE. In addition, we introduce a FL protocol FedBR-BG that incorporates our budget- balanced mechanism, utilizing best response dynamics. Our empirical validation on MNIST and CIFAR-IE 10 substantiates our theoretical analysis. We show that FedBR-BG outperforms the basic best-response-base protocol without additional incentivization, the standard federated learning protocol FedAvg (McMahan et al. [2017), as well as a recent baseline MWFed (Blum al. 222 achieving superior p-mean welfare.
(related privacy and
terms of
Introduction
Federated Learning (FL) has emerged as an effective collaborative training paradigm, where group of agents can jointly train a common machine learning model. The success of collaborative learning paradigms is visible in the domains autonomous vehicles (Elbir et al. (2020), digital healthcare (Dayan et al. [202] Xu et al. [2021]. Nvidia 2019)). multi-devices (Learning) (2017). and biology (Bergen and Petryshen ( Although such collaborative learning is immensely beneficial to the agents, individually, they may not be incentivized to share their data. This is because sharing data may incur costs attributed to bandwidth use, privacy leakage, and the use computing resources. In turn, high costs and low learning payoff's may cause some of the agents to drop out of FL, resulting in subpar learning. As noted by Blum et al. [202T], the success of FL systems depends on its ability attract and retain large number of federating agents.
Thus, it is crucial to achieve fairness and welfare guarantees for all participating agents.
This calls for ghme-theoretic modeling and analysis of the agent's payoff and costs, and subsequent mechanism design to incentivize participation. Towards the former, [Blum et al.) (202T) introduce a model, where every agent receives payoff from the collaboration measuring the "learning benefit" the agent derives from the total data shared. In particular, when each agent contributes s; units of data, the payoff for agent is captured by (s(s), where (51, $2, ... .n) is the data contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

profile, or sample vector. Blum et al. [202T] consider the constrained cost-minimizing model, where each agent minimizes her data contribution (s,) subject to the requirement that her payoff should be larger than a threshold (ar(s; 8-i) 2 (4). They show that a Nash equilibrium (NE) (Nash (1951)) ) arguably the most sought after solution concept in game theory, may not always exist this model. They derive sufficient conditions for existence of NE, as well as provide novel structural results about the equilibria.
We note that an agent's 's cost for sharing data may be more complex than just the size of the total data shared. There are studies dedicated to quantifying the losses (attributed data collection, processing. and privacy) that are incurred with increased sharing of data (Li and Raghunathan [2014). Laudon (1996), Jaisingh et al. (2008]). Furthermore, within game theory (and economics) typically agents are considered as net utility maximizers, i.e., maximizing payoff minus cost, for example value minus payment in auctions (Myerson [198T), and revenue minus cost in markets (Huber et al. (200T), Börgers (0155). To capture these aspects, in this paper we propose an unconstrained utilitarian model, where we define the utility (s(s) of each agent as the difference between her payoff and her cost of sharing data, i.e., (s) (s) (5;), where (5:)) denotes the cost incurred by agent i on sharing & data samples. Each agent aims to maximize their utility. This model is natural in FL settings where there is natural coupling between payoff's and costs, and there are no hard cost constraints, i.e., having an upper bound on the total cost that an agent can incur. Since utility functions are directly indicative of the welfare for the agents, this facilitates defining global faimesss and welfare criteria in terms of the utilities of the agents. This motivates the following questions:
When agents strategize on data contribution to maximize their net utility, does Nash equilibrium always exist? If yes, then can agents actually discover Nash equilibrium when acting independently? Can any welfare function of utilities of the agents be optimized at such a Nash equilibrium by designing new rules (mechanisms)?
The goal of this paper is to address the above questions. Before we describe our contributions, we note that Karimireddy function to be payoff minus cost. However, their focus is data maximization and avoiding free-riding, while the focus of our paper is to design mechanisms that achieve fairness and welfare for all agents. Furthermore, our model generalizes the model of Karimireddy et al. (2022) as we do not require the agents' data to be identically distributed and in turn to have identical payoff functions.
al. 2022 also consider a framework similar to ours, by defining the utility
1.1 Our Contributions
We work under the concavity assumption on the utility functions. particular, we assume that the payoff functions are concave and cost functions are convex. These assumptions are standard in the literature (Blum et al. [202T]. Karimireddy et al. [2022). ). Convexity of cost functions is a natural choice since it captures the property of increasing marginal costs. For instance, data sharing through ordered selection, i.c., sharing records in ascending order of costs involved for collecting the records, results in convex cost functions. There are more models that result in strictly convex cost functions (Li and Raghunathan (2014). ). Similarly, several important ML. models exhibit concave payoff functions; for instance payofi's in linear random discovery models, random coverage models, and general PAC learning are all concave see Section 2.1 Furthermore, there is empirical evidence that the accuracy function in neural networks under the cross-entropy loss is also concave (Kaplan et al. (2020) ).
Existence and Reachability of Nash Equilibrium: Under the concavity assumptions, we show that a Nash equilibrium (NE) is guaranteed to exist. We note that our existence result holds for more general settings than those of Blum et al. [2021] we do not assume that the cost functions are linear, or that the utility functions have bounded derivatives. In particular, our result shows the existence of NE under the general PAC learning framework (see Section 2) under this setting an equilibrium in the model of lum et al. (0221) fails to exist. We also demonstrate that if the concavity assumption is relaxed, there exist instances which do not admit NE.
Furthermore, we show that the agents can discover a NE through an intuitive best response dynamics, where agents update their data contribution proportional to the gradient of their utility functions in the direction that increases their utility. We show that for strongly concave utility functions and under the mild assumption of the gradient of the utilities being bounded, the best response dynamics converges

---

to an approximate NE in time polynomial in O(log(="))) This contribution may be of independent interest to equilibrium computation in concave games.
A Fair and Welfare Maximizing Mechanism: In general, Nash equilibrium need not be fair maximize any notion of welfare for the agents (see [xample[]. Therefore, we next focus on designing mechanisms that optimize welfare of the agents at its NE. The generalized p-mean welfare, defined to be the pd -nrm of the utilities of the agents ( Eig(n) (((s)P) for p E (-oc, 1], constitutes a family of functions characterized by natural faimess axioms including the Pigou-Dalton principle (Moulin 2003)). This notion encompasses well studied notions of fairness and economic welfare, such as (i) the average social welfare & Eie(n) (x())) when p 1, (ii) the egalitarian welfare (mince(m) (s)) when = -oo, which is a fundamental measure of faimesss and (iii) the Nash welfare (e u.(s))//n in the limiting p + case, which is popular notion in social choice theory that achieves a balance between welfare and fairness (Varian 1974]. Caragiannis et al. (2019)
As our second main contribution, for linear costs, we design a budget-balanced mechanism that always admits Nash equilibrium. The mechanism involves payments, however, audget-balancedde ensures that the total payment of all the agents is zero, and thereby the central server operates on no-profit-no-los: Moreover we show that when the sample vector NE is positive, i.e., all agents contribute positive amount of data samples, then the NE maximizes the p-mean welfare among all positive sample vectors. Since we can ensure the server does not communicate with agent who does not contribute any data points, insisting on positive sample vectors is a mild assumption.
Our mechanism builds on ideas from mechanism of Falkinger et al. [2000] for the efficient provisioning of public goods. The key idea is to compensate an agent who incurs a cost higher than the average cost incurred by other agents via a subsidy proportional to her excess cost; likewise, agents incurring a lower cost than average of others are proportionally taxed. By setting the level of tax/subsidy carefully, we show that the NE of the mechanism are p-mean welfare maximizing. To the hest of our knowledge, our work is the first to explore this intimate connection between FL. and public goods provisioning. Our results highlight the promise of bridging the fields of machine learning and social choice theory.
Once we have established the mechanism, we show that corollary of our first main result implies that the best response dynamics under this mechanism will lead to the discovery of the p-mean welfare maximizing Nash equilibrium.
Empirical Evaluation: We design a distributed training protocol for FL based on our mechanism, called FedBR-BG. We compare our algorithm with three other algorithms: the distributed protocol for the vanilla mechanism without budget balancing FedBR, the standard federated learning protocol FedAvg (McMahan et al.] [2017)). and recent adaptation of FedAvg called FWFed (Blum al.) (202T)) We show that our budget-balancing algorithm achieves superior p-mean welfare under different settings on two datasets, MNIST (LeCun et al. (2010) and CIFAR-10 (Krizhevsky (009)).
1.2 Related Work
We mention some additional literature on welfare maximization and incentives in FL, as well as other related mechanisms in public goods theory.
Welfare maximization in FL. Typically federated learning protocols compute a model which maximize some weighted sum of agent accuracies (i.e. utilties). Examples of such protocols include the standard FedAvg (McMahan et al. (2077). AFL (agnostic FL) (Mohri et al. 2019), and g F-FFL (Li et al. (2020). However, unlike work, all these methods ignore the strategic aspects arising from costs involved in data sharing, and instead assume agents honestly contribute all their data.
Incentives in FL. This line of work adopts game theory for incentivizing the contribution of data owners. Common models include the Stackelberg game, non-cooperative game, and coalition game. More specifically, the Stackelberg game is employed to optimize the utility of both the server and agents Feng et al. [019). On the other hand, in non-cooperative games, the server or the agent seeks to maximize its own utility Zou et al. 2019). While most previous methods analyze the properties of certain scenario, aim to design mechanisms that achieve fairness and welfare for all agents.
3

---

Mechanisms for public good provisioning, There is long line of work for the efficient provi- sioning of public goods, beginning from Samuelson [1954). Several works such as Falkinger et al.) [2000), Andreoni and Bergstrom [996)] and Bergsttrom et al. (1986) use the idea of imposing tax/subsidy on the agents but differ in the specific manner which this tax/subsidy is imposed.
While our mechanism is inspired by Falkinger et al. (2000), our model is more general than theirs.
The design of our mechanism for this general model and the proof of its properties are our novel contributions.
2 Problem formulation
We consider federated learning problem with n agents who wish to jointly solve a common learning problem. Let D; be the distribution of data points available to agent i. Towards jointly solving the learning problem, each agent contributes some set T; D.' of s; data samples. Under the assumption that agent i's data is i.i.d. from their distribution D., each agent's contribution can be captured simply by their contribution level, i.e., amount of data samples they contribute. Let S; C 2 be the set of feasible contribution levels of agent and let S == X Sj. Given sample vector s (si,..., E S, the central server returns model(s) trained using the samples U, Ti-
In our model, each agent i derives a payoff from the jointly learned model, e.g. the payoff could be the accuracy of the model. We assume general framework which models the payoff of agent as function a; : S + Rgo. We typically assume each payoff function a; is bounded, continuous in 8, and nonddecrgas in the contribution s; of agent Moreover each agent incurs cost associated with data sharing captured through a non-decreasing cost function G: S - 1 The net utility of agent is the payoff minus cost, i.e., (.(s) (s()) (8))))
Given the above framework, the goal of an agent is to decide how many samples to contribute so that her net utility (-) is maximized. Note that the utility of agent depends on the contributions of other agents as well. Further, for some threshold T; > O. This is because we can discard contribution levels where an agent gets negative utility. Since the payoff (s) is bounded above by some constant A; > 0 and costs are increasing, agent cannot obtain positive utility by contributing more than T; C, (A,) samples.
assume without loss of generality that each set S; [0, 7
Payoff and cost functions are assumed to be concave and convex respectively (Blum et al. (2021). Karimireddy et al. [2022)). ). As discussed in Section I.I it is natural to assume that cost functions are convex to capture increasing marginal costs (Li and Raghunathani (2014). Similarly, there are ample justifications to concave payoff functions, as discussed in Section 2.1 where we analyze payoff functions arising from some of the canonical learning paradigms, and their concavity properties.
Remark Our framework generalizes those of Blum et al. [202T] and Karimireddy et al.) 2022). In the former, an agent's 's goal is to contribute the fewest number of data samples subject to ensuring that their payoff crosses certain threshold; and in the latter all agents have common payoff function that is a function of || 31 +... + sn. and linear cost functions.
Nash Equilibrium (NE), Arguably the most sought after solution concept within game theory is of Nash Equilibrium Nash [951)). ). stable state or an equilibrium state of the system where no agent gains by unilaterally changing their data contribution level. Formally.
Definition (Nash equilibrium (NE).. sample vector 8 E S is said to be at Nash equilibrium if for every E [n], and every sy we have (s(s) 2 u, s_,) where (s/, s-,) (S1....,$$ S sn).
An alternate view of a Nash equilibrium relies on the concept of best response. Given the sample contributions s-; of other agents, the set fi(s-;) of contribution levels agent i that maximize her utility is the best response set of agent i:
fs arg max zeS
{a:(z, (_.) cx(x)} C
The best response correspondence f is then defined set-valued function S 2 where [f())], fi(s..). It is then clear that: Proposition sample vector s E S is a Nash equilibrium and only if is a fixed point of the best response correspondence, i.e., s E f(s).

---

2.1 Canonical examples of payoff' functions
We now discuss few examples of payoff functions that are captured by our general framework. In all the examples below, the payoff functions (s)s) are non-negative, bounded, continuous, non- decreasing, and concave in s; for any fixed strategy profile s-t of the other agents.
Linear or Random discovery. In this model, the payoff' is linear in the sample vector and is given by (s) (Ws); for matrix W. For example, Blum al. [2021) consider setting where each agent has a sampling probability distribution qi over the instance space X and gets reward equalling lix whenever the instance z is sampled by any agent. Then the expected payoff to agent i is (8) (QQ' s); where Q is a matrix given by Q/i, 2] fiz for [n] and x E X. Here W = QQ is a symmetric PSD matrix with an all one diagonal.
Random coverage. In the above setting, agent i obtains a reward Air each time some agent samples instance z. In the random coverage model arising in binary classification (Blum al. [202T]) [), an agent gets this reward only once. Under this model, the payoff given by expected accuracy takes the form:
(s()) =
1 2
Σ Ti I ØEX
(j0) ) [0.
(1)
Generalization bounds from general PAC learning. Consider general learning setting where we want to learn a model / from a hypothesis class H which minimizes the error over data distribution D given by R(h) = (h(()))))(((()) y), for some loss function e(-). Given m i.i.d. data points, the pirical risk minimizer (ERM) can be computed the model hm arg min Eee(mg e(h(2zz) ve)- Mohri al. [2018) show the following bound on the error of hm. which holds with high probability:
R(hm)) 2 a(m) == ao 4 v 2k(2 + log(m/k))
Vm
where (1- a0) is the accuracy of the optimal model from H. and & is (constant) measure of the difficulty of the learning problem depending on e(-) and H. Using this we define the agent payoff a, function as the accuracy of the learning task as (s()) (8) = a(I
Empirical evidence. Kaplan al. (0200) discuss empirical scaling laws relating the cross-entropy loss on neural language models. They observe that the loss scales with the dataset size m as a power law f(m) a 3 for some parameters a 0 and (0, 1]. This naturally defines the payoff function as the accuracy of the learning task as
(;(s) 1 aq || &
In addition, the pfy- functions of current large language models (e.g., accuracies) are also non- negative and non-decreasing as a function the data size (Henighan et al. 20000).
3 Nash Equilibrium: Existence and Best Response Dynamics
In this section, investigate the existence and computation of a Nash equilibrium. We start with two positive results showing the existence of a Nash equilibrium for a broad class of payoff and cost functions.
Theorem 3.1. A Nash equilibrium exists in any federated learning problem where for every agent i the payoff function (s(s) is continuous in s and concave in 8;, and cost function c; is increasing and convex in 8,.
Proof. We will show the existence of a Nash equilibrium by showing that the best response cor- respondence ʃ has a fixed point. First observe that f is defined over compact, convex domain S S=X, Sj since each Sj is convex. Next, note that agent i's utility function uz(s) = az(s) - (x(*)) is continuous in due to the continuity of a, and The continuity of u, in and the concavity of
We define a0)) 0.
5

---

U; in 8; implies the upper cemi-continuity of the best response correspondence ft. Moreover, 2, is concave in 8; for each fixed 8 s-i, since a, and -c; are concave in s;. Thus for each fixed s s- the best response set ii) S Rgo is non-empty interval, and hence is also convex. Thus ʃ is upper semi-continuous non-empty and convex valued correspondence defined over a compact, convex domain. By the Kakutani fixed-point theorem (Kakutani 1941]) f admits fixed point.
The above result can also be proved directly by invoking Rosen 1965 who showed the existence of a Nash equilibrium of n-person concave games, where the utility function of an agent is defined over closed, compact set, continuous and concave in i's own strategy.
Implications. Theorem 3.1 shows that a Nash equilibrium exists when payoffs are concave and costs are convex. All our motivating examples from Section 2.J lie under this concave/convex regime and therefore admit NE. In Appendix A we discuss existence and non-existence of Nash equilibrium in our model when we go beyond the concave-convex regime of payoff and cost functions. In particular, we show that Nash equilibrium exists even with decreasing payoff function of an agent as long as the function is separable between her and other agents' data contribution. We also show that NE need not exist even with linear cost functions if the payoff functions are non-concave.
Best response dynamics. We turn to computation and consider natural procedure by which agents can find a Nash equilibrium: best response (BR) dynamics. Agents start with some initial sample vector s In each step of the BR dynamics, every agent updates their sample contribution proportional to the gradient 0s;
du; in the direction of increasing utility. Concretely, for scalar step size
5" > 0, the updates take the following form:
g g s 8 g(ss, ,²),
(4)
where g(s", (=)); = (m;(x') Ds: + uu and n¹ is chosen so that the updated sample vector s lies in the feasible region S. Specifically, 2e' E arg min llg(s", 12ll2- where K = {or : st + 8 g(s p))
S}. For instance, if 0 S s, S Ti, then:
Oug if 8; = 0 and
Ou:
< 0, or and Da:
Ou Dec
0
1
ōs."
0, otherwise.
We measure convergence of the above dynamics to a Nash equilibrium via the L norm of the update direction g(s", n²). Under mild assumptions on the utility functions, we show the dynamics converges to an approximate Nash equilibrium where (lg(s', 1l2 <:
sa.(a))
Theorem 3.2. Lei G(s) be the Jucobian of u : S R", iee, G(8) = utility functions u, satisfy
Assuming agent Dsyds:"
1. Strong concavity: (G+ Inxn) is negative semi- semi-definite,
2. Bounded derivatives: |G,yl L
for constants A, L O, the best response dynamics
with step size 8' मीं converges to an Il2 < in T iterations, where
approximate Nash equilibrium sT where [lg(sT 1 T
2n 22
(19(s",14))),
T= X2 log
Below we sketch the proof and defer the full proof to Appendix A
Proof sketch. We measure convergence of the above dynamics by the error term [l9(s', "ipss","")l #²)ll2 We show the following bound:
1 / 1a)) S llg(s', 10)) 57 [IG(s') ((s's")(s',,,) /² n²)) 25.g(s', (()) n²).
(00(ssH1')) +4)) and the bounded We then use strong concavity to show g(s", G(=))) ,²² < -lllg(s
derivatives property show |[G(s")g( 4²) I)2 I nLlll(ss n p2)ll2 For our choice of the step size
8' n..Z, we can relate the error subsequent iterations as follows:
X²
||g n 1 <
-lg(s', 4
n² 1

---

This then allows us to conclude that after T 2n² log approximate Nash equilibrium 8 with [|g(s"
[l0(a* "o(aa,,">\ls iterations, we will have an
" 1 )11 S E.
Implications. The above theorem implies that agents playing the natural best response update strategy will converge quickly (in Ollog(e-)) iterations) to a NE, We note that our theorem applies to the payoff functions defined by generalization bounds (eq. (2) and observed in practice (eq. (3)
as they are strongly concave and have bounded derivatives. Moreover, under the assumptions of Theorem 3.2 our proof also implies the fast convergence of the best response dynamics in the budget-balanced mechanism we discuss in the next section.
4 Welfare Maximization: A
Mechanism
We first note through example that Nash equilibria need not be welfare maximizing.
Example 1. Consider two agents with identical payoff functions a(*) = 8 (81 + 82) and linear cost functions given by (s1) = 5c1 and (2(52) = 4c2. The NE is given by 8* = (0, 0.5), i.c. agent does not contribute any data samples. The Nash welfare (which is the p-mean welfare in = 24. However consider another sample vector s' (0.2, 0.4) where agent increases her contribution and agent 2 reduces her contribution. Then s' has a higher Nash welfare of un (s') uz(ss) ) = 25.25 > 24.
p + 0 limiting case) of this NE un (8*) u²(s
To address the issue of NE not being for agents with linear cost functions. Our mechanism is inspired from mechanism for the efficient provisioning public goods (Falkinger et al. (2000). We show that our mechanism always admits NE. Moreover, when the sample vector at NE is positive, i.e. every agent participates by contributing data, the NE maximizes the p-mean welfare among all positive sample vectors. For the FL setting, assuming positive sample vectors is natural since the only way for an agent to participate is by making some positive data contribution.
by designing a budget-balanced mechanism
We present our result for more general model than one discussed so far. Not only does this generalization strengthen taxes/subsidies they receive from our mechanism. In this generalization, each agent i has a budget B, of which b; is unspent and the remaining used towards the cost of sampling 8; data points, i.e. by + (s()) = B, We assume agents have arbitrary continuous, concave utility functions of the form u,(b,, || Agents have linear cost functions (s²)) C. 8; + d,, with e 0. This model already captures some previously discussed settings (Sec 2.1 as follows. For e.g., when payoff functions are derived from generalization bounds (Mohri al. (0188) ) or empirical evidence Kaplan et al. (0200). ). they take the form (s) = a,([s || for some function à; which depends on |- Then for uz:(b, (b, ||s I2) b, + a([I=|l the budget constraint implies the utility takes the form à, (,([s) (s,) - B,, which is the same as the utility under the original model with a constant
result, it also naturally allows expressing agent utilities in terms of the
offset. We also assume that for all i, (b.
88 > 0 and (b. + O.
86,
Mechanism Mg. We design a mechanism parametrized by a scalar 8 (0, 1). uses the following payment scheme. At data contribution vector each agent i is rewarded an amount
Pr(s) ((c(se))
Σ E(())). J41
Thus if an agent incurs higher (resp. lower) sampling cost than the average cost borne by other agents, we compensate (resp. penalize) her by subsidy (resp. tax) of I times her excess cost. By design, our mechanism is budget-balanced: at any sample vector s, we have:
Ep((s) (ols)=B(C)
3[ c((s))
1 Eg(()) = 0.
7

---

Under this mechanism, given a vector of contributions 8-; of agents other than agent i, the best response of agent is any solution the following optimization problem:
max uilbi 8: + ||=<!li)
s.t. Vi: b, + (1 (1- (1-3)) B
Eg((s) B3
(5)
Vi: 0
We next define value that plays crucial role in mechanism. Definition 2. (Optimal parameter (*) Let A the solution to the following equation.
(E and C === C.. Then we define 3 as
C (An(n - 2) + C)B + A(n 1)² =0,
(6)
which satisfies 5 8 < - 1/n.
The next lemma shows that (6) indeed has such root the proof is deferred to Appendix B
Lemma 1. The equation C (An(n 2) C)3 A(n 1)² 0 of 6 has real root 3 where 0 < 3 < 1/n.
We state the main result of this section. We show that for every librium of Mg exists. Additionally, for a specific value of 3 = 8 (Definition 2 our mech- anism admits Nash equilibria which are socially efficient: it maximizes the p-mean welfare: W,(b, s) (E, u(bb, ) for p 1 among all positive sample vectors
[0, 1), Nash equi-
Theorem 4.1. For each 3 E [0, 1], the mechanism Ma admits Nash equilibrium. For B 3" (Definition 2) whenever NE 8* of Mg. satisfies s > O, the NE s maximizes the p-mean welfare among all vectors > 0, for any p 1.
We now sketch the proof the above theorem. The full proof is deferred to Appendix B
Proof sketch. sketch. When 0 < 3 < 1, the first constraint the above program a convex constraint even for general convex cost functions. Since u.(-) is concave, proof similar to the proof of Theorem 3.1 shows the existence of a Nash equilibrium.
The program maximizing p-mean welfare as follows.
(b 8) = Σ us (hi, 1/>11))))1p>
max
s.t.
Vi: + (1 ()((())) + n-1
Σ (5(s)) B₁ j#1
vi: b 2
We first show that the above program is convex. With and 74 as the dual variables to the first and second constraints respectively, we write down the KKT conditions of program 7 with s; 0. We then use the KKT conditions satisfied by NE (b" ) to find values of the dual variables fr" and y*
so that (b* s* μ Y²) satisfy the KKT conditions of (7). Since KKT conditions are sufficient for optimality, this shows that the NE (b" s*) also maximizes p-mean welfare.
Implications. Theorem 4.1 shows that by augmenting the federated learning with simple payment protocol that is budget-balanced, one obtain NE that maximize any p-mean welfare function of the net-utilities of the agents. Furthermore, note that the payment augmented utility function still essentially of the form u,(s) (s( - (1 - ()c) - (s;), with constant offset. Since 3 E [0. 11, when a:(-) are X-strongly concave and c.(-) are A-strongly convex, the functions u.(-) are X-strongly concave. Therefore Theorem 3.2 appliie, which ensures that the welfare maximizing NE can be reached through the simple best response dynamics quickly. Finally, we remark that when cost functions are identical, the value of the optimal parameter 8 - 1/n), which exactly the value used by Falkinger al. 2000).

---

Remark 2. Our mechanism requires that costs of the agents be publicly known in order to calculate the value of 3 by solving (6) Definition? This a common assumption made in previous work (e.g. Karimiredyy et al. 2022 and Blum et al. 2021 | and is justified in practice. Indeed, costs are common knowledge in many real-world applications e.g. (1) in many MI. applications, each agent derives their training data from manually labeling a subset of publicly available dataset like CIFAR or ImageNet, and the cost of labeling dataset is usually known; (2) in autonomous driving, where each data point is random path taken under random external conditions.
Distributed Algorithm and Empirical Evaluation
In this section, we realize our budget- balanced mechanism in a real-world FL system. We perform the evaluation on the MNIST (LeCun et al. (2010) and CIFAR-1Q R-10 (Krizhevsky (009) datasets. We compare our mechanism with two baselines: the standard FedAvg and MWFed Blum et al. [202T). We denote the vanilla mechanism without budget balancing as FedBR and the budget-balancee
mechanism as FedBR-BG We demonstrate that compared to the FedBR, FedBR- -B achieves better p-mean welfare for p S 1. We also show that the standard FL protocol FedAvg gives significantly lower welfare since it does not allow agents to change their contribution.
5.1 Algorithm Details
We first define the concrete forms for payoff and cost functions. According to standard practice in FL, an agents payoff is measured through the accuracy evaluated on her local test data given model 8, which has the form (s , 0) [P:]] [(..)ED; 1[((x)) = yl. where D; is the test data for agent i.
We note that this form inherently aligns with (s) à, ([[ because the received global model A is trained on ||ا| samples. We consider linear cost functions where (s(ss) = CzSt.
Now we derive the update rule for agent contributions for FedBR-BG based on best-response dynamics. We rewrite the utility of agent i the budget- budget-balancing mechanism as u, u,( = á; à 8:)
(1- 9--3) - Eit; Cj.j. We then compute its gradient with respect 8j: de.
Ou: 86, 2 *1)
0s.
(1- ()c Since the accuracy function is generally unknown in practice, the server can train a public accuracy function ā S + R and broadcast to all agents. We obtain an estimate the accuracy à by evaluating models trained on different numbers of samples, in increasing intervals of As. For example, if the server trains models on 0, samples and evaluates their accuracy to obtain the estimated accuracy à, the interval As = 2 in this case. We assume (T1,..., Tx) E S as the server can be service provider with plenty of data sources. With ā, we can approximate the gradient as ou. a(E, 5; As)- 8s,
au, atE. 4 As) -ā s,) c for FedBR, (1 3)c₁- Similarly, De, and (s()) = az (, 81) c;s; for FedAvg, MWFed and FedBR.
Ae
We further assume that s; is a multiple of As to ensure that à is always well-defined for our chosen contributions. Finally, we leverage best-response dynamics to update agent contributions. We present the full description of the algorithm for FedBR-BG and FedBR as Algorithm and Algorithm 2 in Appendix C respectively.
5.2 Experiment Setup
We conduct the experiments with 10 agents for MNIST and 100 agents for CIFAR-10. For MNIST, we use a CNN as the global model, which has two 5 x 5 convolution layers followed by two fully connected layers with ReLU activation. For CIFAR-10, we use VGG11 (Simonyan and Zisserman (2014). We consider the i.i.d. setting, i.c. the local data of agents are sampled from the same distribution. For both datasets, each agent has 100 training images and 10 testing images, i.c.,T, = 100, Vi E [n)]
We randomly initialize the contributions as multiplier of 10 J0. 100). In each contribution updating step, we re-initialize the global model and perform FedAvg for 50 communication rounds. We set global learning rate y) to 1.0, local learning rate a to 0.01, and momentum to 0.9. We set the number of contribution updating steps to 100 and the sample number interval to 10. For evaluating FedAvg, we simply optimize the global model with the same hyperparameters while keeping individual contribution to 7,.

---

5.3
Experiment Results
We show the p-mean welfare of our method and baselines on MNIST and CIFAR-10 in Table I We observe that FedBR-BC achieves better p-mean welfare on both datasets compared to FedBR and FedAvg, verifying our theoretical results. Note that the p-mean of FedAvg is significantly lower since agents always contribute all their data in FedAvg, which incurs high cost so that the marginal gain becomes limited.
Table p-mean welfare our budget-balancee mechanism FedBR B-BBR-GG-- and basclines on MNIST and CIFAR- 10. We report the results for different p. The cost for adding one data sample is 0.005 for every agent.
MNIST
CIFAR-10
Method
0.2
0.4
0.6
p 0.8
p 1.0
0.2
0.4
0.6
0.8
p 1.0
FedAvg
48985.23
154.99
22.763
8.726
4.909
42386.21
135.92
23.528
8.381
4,582
MWFed
51326.49
158.92
21 21.648
8.803
5.230
18178.29
142.91
23.981
8.879
4.891
FedBR
53395.21
168.85
24.784
9.495
5,340
58297.23
178.32
26.187
9.675
5.681
FedBR-BG
54589.31
172.63
25.340
9.708
5.459
60385.32
183.23
27.958
9,981
5.891
6 Discussion
In this paper, we formulated federated learning framework which incorporates both payoff's an agent receives from sharing data as well as the cost she incurs due to sharing data. We show the existence of Nash equilibria under the assumption of concave payoff's and convex costs, which are mild assumptions observed in practice. We then note that while NE exist, they may not maximize any notion of welfare for the agents, leaving agents with less incentive to participate. We address this issue via budget-balanced mechanism with payments whose NE maximize the p-mean welfare of the agent utilitics. Our experiments show that FedBR-BG -BG achieves better p-mean welfare compared to FedBR and FedAvg, verifying theoretical results.
We conclude by discussion some directions for future work. Our mechanism required that costs of the agents be publicly known, or at least verifiable. Studying incentives when costs are not common knowledge is an interesting question. Another assumption of our mechanism was that an agent's payoff depends on the number of data samples. Designing welfare-maxinn maximizix mechanisms for general settings where payoff functions take more general forms another direction for future work.
Acknowledgements. This work is partially supported by the National Science Foundation under grant No. 1750436, No. 1910100, No. 2046726, No. 2229876. DARPA GARD, the National Aeronautics and Space Administration (NASA) under grant no. 8ONSSC20M0229, the Alfred P. Sloan Fellowship. and the Amazon research award.
10

---

References
James Andreoni and Ted Bergstrom. Do government subsidies increase the private supply of public goods? Public Choice, 88(3-4):255-308, 1996. o
kap pubcho:c:hoo:::00 199:: 295-333
Sarah E Bergen and Tracey L Petryshen. Genome-wide association studies of schizophrenia: does bigger lead to better results? Current opinion in psychiatry, 25(2):76-82, 2012.
Theodore Bergstrom, Lawrence Blume, and Hal Varian. On the private provision of public goods.
Journal of Public Economics, 29(1):25-49, 1986. ISSN 0047-2727. doi: https://doi.org///// 0047-2727(66)900241 1. https::s::// http://www..ccicccceeeeettteeeet cow httm///iicnc//rrrcl/ppp.... 0047272786900221
Avrim Blum, Nika Haghtalab, Richard Lanas Phillips, and Han Shao. One for one, or all for all: Equilibria and optimality of collaboration in federated learning, In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1005-1014. PMLR, 18-24 Jul 2021. URL attps://proceedie .mw.eddiinsmm.........mmmm.r mlr. press/ v139/blum21a html
Tilman Börgers. An introduction to the theory of mechanism design. Oxford University Press, USA, 2015.
S.P. Boyd and L.. Vandenberghe. Convex Optimization. Number 1 in Berichte über verteilte messysteme. Cambridge University Press, 2004. ISBN 9780521833783, URL https://books google.
Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum Nash welfare. ACM Trans. Econ. Comput., 7(3),
sep 2019. ISSN 2167-8375.
Ittai Dayan, Holger R Roth, Aoxiao Zhong, Ahmed Harouni, Amilcare Gentili, Anas Z Abidin, Andrew Liu, Anthony Beardsworth Costa, Bradford J Wood, Chien-Sung Tsai, et al. Federated learning for predicting clinical outcomes in patients with covid-19. Nature medicine, 27(10):
1735,1743,200 2021.
Ahmet M Elbir, Burak Soner, and Sinem Coleri. Federated learning in vehicular networks. arXiv preprint 2rX1v:2006.0/412, 2020.
Josef Falkinger, Emst Fehr, Simon Gächter, and Rudolf Winter-Ebmer. A simple mechanism for the efficient provision of public goods: Experimental evidence. The American Economic Review, 90 (1):247-264, 2000. ISSN 00028282. URL hhttp://wwitt jstor wttp///aaateee/e99/9/9/9
Shaohan Feng, Dusit Niyato, Ping Wang, Dong In Kim, and Ying-Chang Liang. Joint service pricing and cooperative relay communication for federated learning. In 2019 International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber; Physical and Social Computing (CPSCom) and IEEE Smart Data (SmarDDtta) pages 815-88 820. IEEE, 2019.
Tom Henighan. Jared Kaplan, Mor Katz, Mark Chen, Christopher Hesse, Jacob Jackson, Heewoo Jun, Tom B Brown, Prafulla Dhariwal, Scott Gray, et al. Scaling laws for autoregressive generative modeling. arXiv preprint arXiv:2010. 14701, 2020.
Frank Huber, Andreas Herrmann, and Robert E Morgan. Gaining competitive advantage through customer value oriented management. Journal of consumer marketing, 18(1):41-53, 2001.
Jeevan Jaisingh, Jack Barron, Shailendra Mehta, and Alok Chaturvedi. Privacy and pricing personal information. European Journal of Operational Research, (3773)8577-870 2008
Shizuo Kakutani. A generalization of Brouwer's fixed point theorem. Duke Mathematical Journal, 8 (3):457 459, 1941. doi: 10.12155500127700444400000:::::0 URI, htttps://doi. http::::://ioooo///////// 1215/ S0012 7097779-----0088--1

---

Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford. Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. CoRR, abs/2001 abs/2001.08361, 2020. URI.bttps://arxiv www.:org//aaae. abs/ 2001 08361
Sai Praneeth Karimireddy, Wenshuo Guo, and Michael Jordan. Mechanisms that incentivize data sharing in federated learning. Workshop on Federated Learning: Recent Advances and New Chal- lenges (in Conjunction with NeurlPS 2022), 2022. URL https:://pperrrviiee http:/iwwwwwwweeeeeeee net/
1d=Bx4Sz-N5K3
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical Report TR- 2009, University of Toronto, Toronto, 2009. URL https://www cs toronto..du. edu/"kriz) featunns-eaauuuss222220000 TR.
Kenneth C Laudon. Markets and privacy. Communications of ACM, 39(9):22-104, 1996.
Federated Learning. Collaborative machine learning without centralized training data. Publication date: Thursday, April, 6, 2017.
Yann LeCun, Corinna Cortes, and CJ Burges. MNIST handwritten digit database. ATT Labs [Online]. 2, 2010.
Available: haaiaabbehtg/yaaan....u...o/o// www...w...o///e///misssstt
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. ICLR. OpenReview.net, 2020.
Xiao-Bat Li and Srinivasan Raghunathan. Pricing and disseminating customer data with privacy awareness, Decision support systems, 59:63-73, 2014.
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. ciapiiattttooefffiiittt efficient learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
Communication
M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning, second edition.
Adaptive Computation and Machine Learning series. MIT Press, 2018. ISBN 9780262039406. URL https::/books.. watboooksgoogo. google. www/boomooeeeeeeeooooo http/boookssddd-22aaApppp
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Interna- tional Conference on Machine Learning, pages 4615 4625. PMLR, 2019.
Hervé Moulin. Fair Division and Collective Welfare. The MIT Press, 01 2003. ISBN 9780262280297. doi: 10755//iitpess2254..1..000
URL http::::/aool.org/0...55////////
000100011
Roger B Myerson. Optimal auction design. Mathematics of operations research, 6(1):58-73, 1981.
John Nash. Non-cooperative games. Ann. Math., 54(2):286 -95, 1951.
N Nvidia. Nvidia clara federated learning deliver ai hospitals while protecting patient data. NVIDIA Clara Federated Learning to Deliver Al to Hospitals While Protecting Patient Data, 2019.
J. B. Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Econo- metrica, 53035,4 1965. ISSN 001 00129682, 14680262. URL hattp://wwwz jstor org/ stable/191174
Paul A. Samuelson. The pure theory of public expenditure. The Review of Economics and Statistics, 36(4):387-38, 1954. ISSN 00346535, 15309142. URL http:///wwwe http:://www.. wwwwr.jsto.... www.jj.tttossseee.....ooo 1925895
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1oXiv:1409.15.. 1556, 2014.
Hal R Varian. Equity, envy, and efficiency. Journal of Economic Theory, 9(1):6( - 1974.
Jie Xu, Benjamin S Glicksherg, Chang Su, Peter Walker, Jiang Bian, and Fei Wang. Federated learning for healthcare informatics. Journal of Healthcare Informatics Research, 5(1):1-19, 2021.
12

---

Yuze Zou, Shaohan Feng, Dusit Niyato, Yutao Jiao, Shimin Gong, and Wenqing Cheng. Mobile device training strategies in federated learning: An evolutionary game approach. In 2019 International Conference on Internet of Things (iThings) and IEFF Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEFE Smart Data (SmartData), pages 874-879. IEFE, 2019.
13

---

A Appendix to Section 3
We first show that a Nash equilibrium exists when agent payoff funetions are separable, i.e., for every agent there are functions S; + Rzo and h; X S + R2 s.t. for all 8 E S, (s(s) (s (s()).).
Theorem A.I. In any federated learning problem where agent payoff functions are separable, Nash equilibrium exists.
Proof. When the payoff function of an agent i is separable, the best response to any contribution vector s-; is independent of s-
f((s-:) arg max ai (I, 8-2) cx(x) arg max ((() h.(s_.) c2(2) =ES; arg max (x) c(()). (since h,(s .) is independent of x))
=ES;
sES;
Let Fj == arg ma 9: (z) 8 E f() by definition. By Proposition any such sample vector a Nash equilibrium.
(x)) Clearly Fi * 0 since S; * 0. Then any E X, Fi satisfies
Next, we present a negative result showing that there are federated learning settings where a Nash equilibrium is not guaranteed exist.
Theorem A.2. There exists a federated learning problem in which Nash equilibrium does not exist. Moreover, the instance has three agents with continuous, non-decreasing, non-concave payoff functions and linear cost functions.
Proof. Let (0, 1 Lete: [0, 1] [0, 1] be function given by:
0, if0 <x = 22-5 -,
e(x)
7 (-- 1) if
- - +e,
(8)
if
Essentially the function is continuous, piece-wise linear function connecting (0, ( - -, 0),0), ( e, 1) and 1).
Now consider the following federated learning instance with n = 3 agents, where S = S2 S3 =
[0, 1]. The payoff functions are given by:
a (8) e(si) e(sa) e(si) e(sa)
02 8) = e(s2) + e(s1) e(s2) ) e(s1)
(9)
0g e(8g) e(22) e(83) e(82),
and the cost functions are (*x) s for all i E [3]. Notice that the payoff functions are increasing in 82 for every (3) and are continuous since continuous.
We now show that this instance does not admit Nash equilibrium. Let us first evaluate the best
response set fi (s2, s3). Note that us(s) e(s1) (1 e(s3)) + e(sa) $11. Since un (s) is
independent of 82, fa (82, $a) only depends on 83-
Case 1. 83 < - E. Then in (8) = e(s1) - s1, which is maximized at 81 = 2 + E and results in
2
a utility of 7
g - 4
Case 2. 83 2 2221
+ E. Then un (s) 11 which is maximized $1 and results utility
of 1.
Case 3. 1 < 83 < + We consider the intervals in which the best response to such an 83 can lie:
81 J e. this range, u1(s) e(sg) 81, which is maximized at 81 = 0 and results in utility of e(ss).
14

---

222 + E. In this range, (1(s) = 1 - 1, which is maximized at + E and results in
utillity of 1.
$ S 1
2 + In this range, using the definition of e(s1) (eq.) we obtain:
e(s3) 1 1) $1 +1 (1-c((ss))
(2
un un(s) =
+ e(ss).
2x
4
4=
Thus in (8) a linear function in 81 with slope 1-e(=a) best response in the current interval is
1 If the slope is positive, then the and gives utility of 7 8 1. If the slope
2
is negative, then $1 = 1 is the best response in the current interval and gives utility of cannot be best response. Finally if the slope is zero, then it must mean that e(sa) = 1 2. and the utility is 5(2 ) +
e(s3) { 5). However 51 0 gives a utility of e(s3) implying that $1
4. However responding with = 0 gives utility of e($3) = - द. which exceeds 1. since TØ. Thus, the best response does not lie in ( E, + e) and 81 0 the overall best response.
The above discussion shows that the best response fi s3) S {0, + By symmetry, the same holds for fz and fs. Suppose there exists a Nash equilibrium s* = (s1 S s5). By Proposition | s f(s"). Since the above discussion implies sz {0, 2
1 + E}, we consider two cases:
Suppose s
0. Then
$/ 0
81 +
+
(Case for agent 1)
2
7
8
(Case for agent 2)
1
$
+ E, (Case for agent 3)
2
which is contradiction.
Suppose sg + Then
$
+ =
bs =
(Case 2 for agent 1)
82
(Case for agent
83 (Case 2 for agent
which is also a contradiction.
This shows that there is no such that s* f(*),, implying that the above instance does not admit a Nash equilibrium.
We now prove the fast convergence of best response dynamics.
Theorem 3.2. Let G(s) be the Jacobian of : Ra, iee, G(8) utility functions u, satisfy
Pel(s) Dsyde; Assuming agent
1. Strong concavity: (G+ X Inxx) is negative semi-definite
2. Bounded derivatives: |G L
for constants X, L > 0, the best response dynamics
with step size 8' का converges to an
A
approximate Nash equilibrium SJ where !!g(s". 11" || < S in T iterations, where
L2 T
(l ((ls).40))1 21))
log
X
15

---

Proof. Observe that je is chosen s.t. llg(s', =²)l2 is minimized among all s.t. the updated sample
vector s s remains in S. Thus:
lla(s 1+ 112 - 11g(s 12)112
(10)
Using Taylor's expansion, we have:
1²) g(
g(s"s' ,²) H(s' (8s - s');
where Hiy(s', 11') 0o(e' n²) and s' s a +1 - ss)) for some a E [0, 1].
0a;
By definition, g(8", ,r)); Oui('') +u.. Thus Hig x²) ((s',,')
D'u,(a') = Gij(s'), hence H ,²) Da
Ba,
G( The BR dynamics update rule 44) implies g 8¹ 8' (()), We therefore have
g(s 1²) (Laxn + G(s')) g(s", j²). Taking the L norm, we get:
(ls(t n2)1 llg(s"; " of [[G(s')g(s' (isiss,x'))) x2)ll 20.g(s', (()" n²), (11) By the strong concavity assumption, for constant À > G + A Lux is negative semi-definite, ie.. v² (" + A Laxn]o S 0 for any v E R.. With v = g(s", μ²), we have:
g(s', 1²) G(s)) 1²)) S - |lgg(s ((((","²)) 22)) Next we use the fact that the T,2 norm ||A||2 of an n matrix bounded by its Frobenius norm ||
(12)
| lg
| || == sup x=0
- ||
ΣΣ Agy
||>|||
By the bounded derivatives assumption, we have (ss))) s J., which implies that ||G(s')ll
/ EE 12= nL. This gives:
|| ((s)))((', ,²)l22 S nT x1))22
(13)
Using
12 and in
we get:
l1g(s 112 = (1 + 8% n² 28*2) "lg(s" 1 12))1
Since 8¹ n= the above equation together with (Tpp gives:
110sttt, 112 S (1-
X²
lla(s 11 11))122
n²1.2)
Using (1 x1=x)² -e repeatedly we obtain that:
lla(s', w²)ll2 S E =0-zz 11 11 )l))
Thus if we want the error llg(s', 4² )|2 I E, T 2n²+² log ( I [I"ad""")) (1)ll)) iterations suffice, as claimed.
B Appendix to Section 4
Lemma 1. The equation C - (An(n -2) -C)3 A(n 1)2 0 of 66) has real root 3
where 0 < 3r < 12-1-/11 1/n.
Proof. Using the quadratic formula, we see that 8* given by:
8 An(n 2) + C - / (An(n - 2) + C)² - 4AC 1)2
(14)
20
We first argue 8" is real, by showing (An(n - 2) + 2 4AC(n 1)2 2 0. This is equivalent to showing q(v) := (y + n1nn 2) 4(n - 1)2y 2 0, where
C/ A. Expanding we have ((v) y² 22(n2 2n + 2)y + n²(n - 2)2. The roots are:
2(n - 2n + 2) + /4(n² 2n 2)2 4n n 2)2
(n² 2n + 2) = 2(n 1),
V1 1/2
16

---

B; iee. 81 = (n 2) and y/2 = n². Since (vv) has positive leading coefficient, we have that g(v) 2 0 for all y 2 y/2 n². Thus remains to show that y = C/A n To see this, we use the AM-HM inequality:
C
(15)
n
A
implying C/A 2 n² desired. This shows that the root 3r of equation (6 is real, hence well-defined.
We now show 0 S 1 1/n. From 14 we see:
8 An(n 2) C v (An(n - -2) C) 4AC(n - 1)
20
An(n 2) C 100-VAAn (An(n -2) 0)
20
Further, from
we also have:
- 8 An(n + C- (An(n-))) (m 1)2
20
An(n 2)
Cn(n 22)/n² +C
-
2C
2C
Ti'
where we used A/C S 1/n²
T5) in the last inequality. This concludes the proof of Lemma
Theorem 4.1. For each 3 E 10, I,, the mechanism Ma admits Nash equilibrium. For B = 3"
(Definition 2) whenever the NE s* of MMg satisfies s > 0, the NE s maximizes the p-mean welfare among all vectors > 0, for any p S 1.
Proof. When S S 1, the program 5 is convex program for general convex cost functions. Since (-) is concave, proof similar to the proof of Theorem 3.1 shows the existence of a Nash equilibrium.
We now show the welfare- maxifiainm property. For simplicity, only consider feasible strategies where each agent participates the mechanism, i.e., 8; >> Let O; and X as the dual variables the first and second constraints respectively for each i, and let S = ||s|||- Writing the KKT conditions and eliminating all Pss we get that NE (b", "** together with dual variables X satisfies:
Du (b;,S*
0b, (
(Ou;(b;,S*) + X;
vi:
(1 - 3).
(from stationarity conditions)
(16)
as
Vi:
X 2 0
(dual feasibility)
(17)
Vi:
X 0
(complimentary slackness)
(18)
Now turn to the p-mean welfare maximizing solution which is an optimal solution to the following program.
Wp 8) Σ u, (b,,,, P/
max
s.t. Vi: by + - ()-(s)) + n-1
3
Σ c5(8)
(19)
341
W: 2
The following lemma establishes that 19 is convex program. For case readability we defer its proof to B.I
Lemma 2. For 3 E [0, 1] and p < 1, the program 19 is convex.
We can now write the KKT conditions of program 19) By letting μ4 and 7/ denote the dual variables corresponding the first and second constraints respectively for each and S ||s|| the KKT conditions (considering only solutions with > 0) are:
vi
1/P
p
Oup as
[u, - B) +
3
Σ WM]
(stationarity)
(20)
17

---

Vi: Σ u/)1//0 1/1111102
u
(stationarity)
(21)
bb.
Vi: 7/
(dual feasibility) (22)
VE: b; =0 0
(complimentary slackness)
(23)
Since KKT conditions are sufficient for optimality, to prove Theorem it suffices show that for an NE (b", s"), there exist dual variables fe" and y which satisfy 20 23 for = 6
Let E3 uy(b), 8* (-)) Σx (x, st)=-1 Bux (b). i.e., the common value of the equality as
(20 at the NE s²)). The equation 200 then becomes q Mi(1 9) + n-1 Exzi Pk.
8
Summing these over all i and letting T Σj Mij we obtain:
Σ G ) Eiu(L- B)
Σ
px] =T
Putting this back in 20
obtain the following expression for ut, which be computed from the NE (b', s*) with T (E,
Te:
ST
1
5
(24)
8m 1
Recall that the NE (b", s*) satisfies
T6 18
for some dual variables X" We define 7f as follows:
X
(25)
Bu, (0, .*]
ab:
The next lemma proves Theorem
Lemma 3. A NE (b' s*) with μ² and x defined by 24 and 25 of program 19
satisfy the KKT conditions
Proof. First observe that at the NE, (1 (1-B)c-
(5) Bb,
+ X3
Su, (b) ( 0 by assumption.
Since 3 E (0, 1) and > O, we have
(b, 2b,
+
0. Together with A;
this shows
7f 2 0 thus satisfying dual feasibility 22).
Next show complimentary slackness definition of 7²' we have " b, = for all
2 holds. For any i, X b, 0 due to 18 Then by the
Finally, we show that equations 20 and 21 are satisfied for specific choice of 8r. Together, 200 and imply that an optimal solution to program (9) satisfies:
Vi: Σ (HE - -x) Oux/OS &
C [ux(1 - B) + Ouz Ouz/Obe
(26)
The choice of 7 from equation
25 implies that pu 7/- p³: (ar, (b, .//bb/b Moreover the
0u, (8, /8//86,
NE, equation (16) implies that:
(M] >)) Du, (b: a)/
Ou, (b;, s)/OS
pr @uu(b; s)/Ob, X3 )
, s)/Ob:
(1 (1- 3)a (1-3)a
(1+ (
X
14 (1 8)c.
Using the above in 26 it only remains to be argued that ye", ba and s* satisfy:
B
Vi: (1 - B) Σ uh c₁ c: Lu (1 3)
p = a,
18

---

for 3 = 8". By plugging in the value of μu; from 24
and using a =T (Ex '-'=²
we get:
(1- Σ
Te
(2 1-) OT
9
Cs =T ② x
1 n
8n
Let us define A : (2: 2 and C' = Ei C₁. Manipulating the above expression, the above equation then becomes:
CB (An(n - 2) + C) + A(n 1)3 =0,
which is true for B = 3 since it is exactly the definition of 3 (Definition)
Thus for B3 = fr, the NE (b", s*) with dual variables μ and r defined in and 25 respectively
satisfy the KKT conditions of program [9]
B.1 Proof of Lemma 2
Lemma 2. For B E [0, 1] and p S 1, the program (99) is convex.
Proof. For B E [0, the constraints of program
19 convex since ca(-) convex functions.
It remains to be shown that the objective (b (,, (b (r) to be maximized is concave.
We use the following standard fact about the concavity of composition of functions (see e.g. Boyd and Vandenberghe [2004), Page 86).
Proposition 2. Ler h R" + R and B² + R and let f R + R be given by f(x) = h(g(z)) h(gi (z),...... (n()). Then f is concave if concave, h is non non-decreasing in each argument and 9: are concave.
Note that (b,b, h(g(b, s)), where h(r,,...., In) E, 2/ and (b, (u;(bs)) s).
We now observe that:
is non-decreasing in each argument. This is because:
Öh dz,
= h²' 11- 2 0.
is concave. Using the above, we can compute the Hessian H given by:
8hh
p)h (x;a,,) (1 {a (1
(ffi)) j) (if = j)
Hy = 0x,
(11 - p)- - 2 p-2 -(x7 -PP)
Thus for any R", we have:
Hu ΣΣ v 0,
=(1 =11-10 - p)h''
1- 2p Σ
EHOUj
Hijuy + Σ EoTHi
iti
(1 p)h
Σ
| m - mook
+ E
(1 2p-2 11225-2)
(1 22
1 1)2 Σ (1 Σ 22
Σ
2 02
(1 -2p
1
of
Σ 25
S 0
19

---

Algorithm FedBR-BG
1: Input: Number of iterations in game H, number of iterations of gradient descent T, learning
rate a, step size 6, data increasing interval As
2: Output: Model weights 8", individual contributions
3: for = 1,2, ..... H do
4: Server sends 0 to agents:
5: for (. = 0, 1,...... _ do
6: for [n] in parallel do
7:
i computes ge (0*) on its local dataset D;; sends (e* to server;
8:
9: end for
Server aggregates the gradients following
Vgr
DDil Vor
Eie(n) DDi sE(n]
11: Server updates 0++1 following
g++1 t 8¹ a Vg L(8)):
end for
13:
for i E [n] in parallel do
at)
# As) a s:) (1 -B
Ds:
As
15:
(s; = 0 and Oui
0) or (s; т; and
Oui Os.
0) then
16:
8
h+1 + :
else
h+1 = of +
Bus.
18:
Os:
19:
end if
20:
end for
21:
end for
since 1, h 2 0, and by the Stuchy-Schward inequality (E,a) (E, with
a, = / and b, = x p/2-1 Thus H negative semi-definite and hence h is concave.
For each g: 8) u, (b, 8) concave.
Using Proposition 2 and the fact that (b,b, 8) = 1L(g(b, 8)) we conclude that (, 8) is concave.
C Distributed Algorithms
In this section, we present the distributed algorithms of our two mechanisms, FedBR and FedBR-BG.
20

---

Algorithm 2 FedBR
Input: Number of iterations in game H, number of iterations of gradient descent T, learning rate a, step size 6, data increasing interval As
Output: Model weights 8", individual contributions for 1,2,....
do Server sends 0c to agents; for = 0, 1,. ... T do
for E [n.] in parallel do computes V. on its local dataset D3 i sends (6t to server;
end for
Server aggregates the gradients following
aa 2(0') + Eielni Dii
Σ iE|n)
DDi V C;
Server updates 6t+1 following
ac+1 +- 0¹ - a Vo L(0');
end for
for E [n] in parallel do
Oug et>.. 81 -a) sc)
as,
C2
if
dus < 0) or (s: and 0ug (s; 0 and
> 0) then
88,
A+1 $
else
8 A+1
o + 5.
Ou.
De."
end if
end for
end for
21


Reviews:
[{"review_id": "vfj7Uxm9h3", "reviewer": "Reviewer_t7td", "summary": "The authors study the Nash equilibrium in federated learning, under the assumption of concave utility and convex cost, and design welfare maximizing payment for users. Experiments are conducted to verify the mechanism.", "questions": "1. More details on the payment (knowledge required, performance comparison with state-of-the-art mechanism) would help.", "limitations": "Not applicable.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The topic is of important value, and the paper is well written.", "weaknesses": "My major concern is technical novelty and contribution.\n\n1. The analysis of equilibrium and best response dynamic is standard, especially under the assumptions such as convex cost and concave utilities.\n\n2. Though the authors discuss the definition of fairness and welfare maximization, there is lack of discussion on literature about welfare maximization in federated learning, let alone fair subsidies in mechanism design. \n\n3. The design of the payment seems to require the knowledge of the true cost of every user, which is not practical and incentive comptible.\n\n4. The performance of fairness (in Table 1) is compared with methods that are not designed to maximize welfare, which is not meaningful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and questions.\n\n**Weakness 1:** The analysis of equilibrium and best response dynamic is standard, especially under the assumptions such as convex cost and concave utilities. \n\n**Response:** Using fixed point theorems to prove the existence of Nash equilibrium is a widely used technique in many settings, including under our assumptions of concave payoffs and convex costs. Although these assumptions may seem restrictive, we show that NE need not exist when we go even slightly beyond the concave/convex regime: Theorem A.2 shows an example where no Nash equilibrium exists for agents with non-concave payoffs and linear costs (also stated in see Line 206). \n\n**Weakness 2:** Though the authors discuss the definition of fairness and welfare maximization, there is lack of discussion on literature about welfare maximization in federated learning, let alone fair subsidies in mechanism design.\n\n**Response:** We will add a thorough discussion of prior literature studying welfare maximization in FL. Typically, FL methods compute a model which maximizes some weighted sum of a function of agent’s accuracies; e.g. FedAvg, AFL [1], q-FFL [2]. However these methods ignore data sharing costs and assume agents honestly contribute their available data. Unlike our work, they do not consider the strategic aspects arising from the cost of data sharing.\n\n**Weakness 3:** The design of the payment seems to require the knowledge of the true cost of every user, which is not practical and incentive compatible. \n\n**Response:** We agree that we require costs to be publicly known, or at least verifiable by the mechanism designer. This is a standard assumption made in previous works, e.g. Karimireddy et al [3], and Blum et al. [4] (who assume data sharing cost is known and is linear). It seems, costs are common knowledge in many applications e.g. (1) in many ML applications, each agent derives their training data from manually labeling a subset of a publicly available dataset like CIFAR or ImageNet (2) in autonomous driving, where each data point is a random path taken under random external conditions. Studying incentives when costs are not public is an interesting direction for future work.\n\n**Weakness 4:** The performance of fairness (in Table 1) is compared with methods that are not designed to maximize welfare, which is not meaningful.\n\n**Response:** Table 1 compares the p-mean welfare of our methods, and not fairness. We compare three distributed FL protocols: FedAvg (where agents are not strategic and contribute all data), FedBR (where agents are strategic but there are no payments), and FedBR-BG (our budget balanced mechanism with payments for strategic agents). Both FedBR and FedBR-BG admit Nash equilibria (are fair), while FedAvg ignores strategic aspects of data sharing. We observe from Table 1 that:\n\n(1) FedAvg has lower welfare (i.e. accuracy/payoff minus cost), since agents contribute all data even if it is costly.\n\n(2) When agents are strategic about sharing data but there are no payments, Nash equilibria may not maximize welfare (see the FedBR column of Table 1), and some agents may contribute zero data points (see Example 1 in Sec. 4).\n\n(3) FedBR-BG obtains the highest welfare, thus experimentally supporting our result proving that our mechanism with payments maximizes the welfare of the agents at Nash equilibria. \n\nWe also compare with a recent baseline MWFed in [4] on MNIST. MWFed is an adaptation of FedAvg, where the agents adjust their contributions based on the accuracy of the received model. We show that our mechanism outperforms MWFed in terms of p-mean welfare, empirically verifying our theoretical results. Specifically, the p-mean welfare for MWFed is 21.648 (p=0.6), 8.803 (p=0.8), and 5.203 (p=1), in contrast with 24.784 (p=0.6), 9.495 (p=0.8), and 5.340 (p=1) for FedBR, and 25.430 (p=0.6), 9.708 (p=0.8), and 5.459 (p=1) for FedBR-BG.\n\n**Question:** More details on the payment (knowledge required, performance comparison with state-of-the-art mechanism) would help.\n\n**Response:** Thanks for the suggestions for improving this paper. We will include the explanations mentioned above, including (1) details about costs being known, (2) thorough literature survey and comparison to existing methods which maximize welfare but ignore data sharing costs and strategic aspects. \n\nAs suggested, we include new experimental results, comparing our method with a recent baseline MWFed of [4], and observe that our mechanism outperforms MWFed in terms of p mean welfare (please refer to the response to weakness 4 above). \n\nWe also remark that there is no “state-of-the-art” mechanism for a direct comparison. For instance, Karimireddy et al. [3] compare their mechanism against different self-proposed baseline mechanisms inspired from fairness notions, e.g. proportional data mechanism (which returns to an agent i a model that gives a payoff proportional to number of data points contributed by agent i) (see Appendix C.2 of [3]).\n\nReferences:\n\n[1] Mohri et al. “Agnostic Federated Learning”, ICML 2019.\n\n[2] Li et al. “Fair Resource Allocation in Federated Learning”, ICLR 2020.\n\n[3] Karimireddy et al. “Mechanisms that Incentivize Data Sharing in Federated Learning”, NeurIPS 2022 FL Workshop.\n\n[4] Blum et al. “One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning”, ICML 2021.\n"}, {"review_id": "lPNFuyosxI", "reviewer": "Reviewer_NtpC", "summary": "The paper proposes a simple and elegant mechanism for incentivizing data sharing in FL. The mechanism is budget balanced, and any p-mean welfare is maximized at Nash equilibrium. We show the existence of Nash equilibrium (NE) under mild assumptions on agents' payoff and costs. They also show that agents can discover the NE via best response dynamics. In addition, they introduce a FL protocol FedBR-BG based on the budget-balanced mechanism, utilizing best response dynamics. They empirically validate that FedBR-BG outperforms the basic best-response-based protocol without additional incentivization, as well as the standard federated learning protocol FedAvg, in terms of achieving p-mean welfare.", "questions": "Is the derivation of \\beta^* entirely novel, or does it build upon prior work? If it is a novel derivation, why not frame the paper as a study on public good provision? The outcomes seem to have broader implications beyond FL.\n\nDoes \\beta^* depend on the value of p? Falkinger et. al (2000) seem to suggest that \\beta = 1-1/n is optimal for p=1. Does that mean \\beta=1-1/n is optimal for all p<= 1?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper introduces public-good-provision approaches to the problem of incentivizing data sharing in FL. They propose a simple and elegant mechanism that achieves desirable properties (based on Falkinger et. al, 2000). The theoretical results are elegant and solid. The presentation is crystal clear.\n\nThe results do not seem to rely on any specific feature of FL (not sure whether this is an advantage or disadvantage). There is one result that seems novel and surprising, which is the characterization of the optimal \\beta^* (Definition 2) and the fact that it optimizes all p-mean welfare. The proof for the optimality of \\beta^* is non-trivial. My evaluation will highly depend on the novelty of this specific result.", "weaknesses": "The mechanism seems to be largely based on the previous literature on the public good provision, especially (Falkinger et. al 2000). The mechanism is basically the same as the one in (Falkinger et. al 2000).\n\nThe comparison to the existing literature is extremely inadequate. (I didn't see a related work section and the references in the intro barely cover the large literature.) There is a large literature on incentive mechanisms for FL, see [1] for example.\n\n[1] Tu et al., 2021, \"Incentive Mechanisms for Federated Learning: From Economic and Game Theoretic Perspective\" ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and questions.\n\n**Weakness 1:** The mechanism seems to be largely based on the previous literature on the public good provision, especially (Falkinger et. al 2000). The mechanism is basically the same as the one in (Falkinger et. al 2000).\n\n**Response:** Indeed our mechanism is inspired from Falkinger et al. (2020). The latter assume a simpler model of public goods provision, whereas our model is more general. In Falkinger et al. (2020) (see also [1]), each agent $i$ has a fixed income $B_i$ which is split between private consumption $b_i$ and contribution to the public good $g_i$, and her utility $u_i$ is a function of $b_i$ and $G = \\sum_k g_k$, the total monetary contribution to the public good. In our model, agent $i$ spends part of her budget towards the cost $c_i(s_i)$ of sharing $s_i$ data points while $b_i = B_i - c_i(s_i)$ is unspent. Her utility then depends on $b_i$ and $s = \\sum_k s_k$, the total data contribution. Our model thus subsumes that of Falkinger et al. when $c_i(s_i) = s_i$ for all $i$. \n\nAs far as we know, this intimate connection between FL and public goods provisioning has not been explored before, and is novel. Furthermore, imposing tax/subsidy per agent in our mechanism and that of Falkinger et al. is a common technique used in many other mechanisms for public goods, for eg. see [2]. Our novel contribution is the derivation of the optimal parameter $\\beta^*$ for a more general model. \n\n**Weakness 2:** The comparison to the existing literature is extremely inadequate. (I didn't see a related work section and the references in the intro barely cover the large literature.) There is a large literature on incentive mechanisms for FL, see [1] for example. [1] Tu et al., 2021, \"Incentive Mechanisms for Federated Learning: From Economic and Game Theoretic Perspective\"\n\n**Response:** Thank you for the suggestion. We will add a related work section with detailed discussion of prior works on incentives in FL, including the suggested reference.\n\n**Question 1:** Is the derivation of $\\beta^*$ entirely novel, or does it build upon prior work? If it is a novel derivation, why not frame the paper as a study on public good provision? The outcomes seem to have broader implications beyond FL.\n\n**Response:** The derivation of $\\beta^*$ is novel, as our model is more general than that of Falkinger et al. We were motivated to address the specific issue of data sharing incentives in FL, but the paper could indeed be more broadly framed as a study on public good provision. We will mention the same in the final version. Again, thank you for the suggestion.\n\n**Question 2:** Does $\\beta^*$ depend on the value of $p$? Falkinger et. al (2000) seems to suggest that $\\beta = 1-1/n$ is optimal for $p=1$. Does that mean $\\beta=1-1/n$ is optimal for all $p \\le 1$?\n\n**Response:** We note that $\\beta = 1-1/n$ is optimal only when $c_i(s_i) = s_i$ for all $i$ (the result of Falkinger et al.). In general, $\\beta^*$ is given by Lemma 6, and depends on the cost functions $c_i$ of the agents, and not on $p$. Our main result has two important elements. First, we show that our mechanism always admits a Nash equilibrium. The second has a technical subtlety: whenever the agents contribute positively at a NE, say $s^*$ (thus $s^* > 0$), then $s^*$ also maximizes the $p$-mean welfare for $p \\le 1$ among all utility vectors corresponding to sample vectors where all agents contribute positively. Thus the value $\\beta^*$ is optimal for all $p \\le1$ whenever the NE has every agent contributing positively. In our specific application, the assumption of “every agent contributing positively” makes sense since an agent can not participate without contributing data in the sense that the server will not communicate with an agent who does not respond!\n\nReferences:\n\n[1] Falkinger. \"Efficient Private Provision of Public Goods by Rewarding Deviations from Average.\" Journal of Public Economics, 1996.\n\n[2] Andreoni and Bergstrom. “Do Government Subsidies Increase the Private Supply of Public Goods?”, Public Choice, 1996."}, {"review_id": "Et2opdO7MA", "reviewer": "Reviewer_VcZd", "summary": "This paper studies a collaborative Federated Learning framework. Specifically, the authors proposed a utility model, which is the agent’s payoff function minus the data sharing cost function. Under the assumption that the payoff function is concave and the cost function is convex, the authors show the existence of NE. In addition, they proposed a budget-balanced mechanism, which involves payments to the agents, to maximize the agents’ utilities at NE. Experimental results are provided to demonstrate the proposed algorithm's performance, compared with the previous work FedAvg by Blum et al. [2021]. ", "questions": "Can you provide more justification for why the agents always prefer to participate in the collaboration, even if the data-sharing cost is zero when the agent quits the collaboration?", "limitations": "N/A.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Overall, I found the paper to be well-written, and if you take the model as given, the paper gives a fairly satisfying and complete first investigation – the questions asked are exactly the ones I would hope are answered first.", "weaknesses": "One major weakness of the paper lies in the utility model proposed. While the paper's key idea of explicitly defining the data-sharing cost is illuminative and contributes to addressing the existence question prevalent in the literature, the utility model itself raises concerns. The critical assumption made in the model is that an agent cannot achieve better utility on its own, even when the cost is zero. Additionally, the assumption suggests that collaboration with the crowd leads to a better utility at the equilibrium state, as opposed to the option of an agent choosing to quit after some rounds of collaboration.\n\nThis assumption poses limitations and potentially oversimplifies the complexities of real-world scenarios. It overlooks the possibility that an agent might achieve better utility by pursuing an independent course of action, disregarding the collaborative approach altogether. By not considering the potential benefits an agent could gain from individual efforts, the utility model fails to capture the nuanced dynamics of decision-making and potential trade-offs that exist in real-world situations. Therefore, this utility model undermines the paper's overall conclusions and hinders its practical applicability. I would have liked a more concrete/precise discussion of the motivation for the utility model, for example, what if the cost is too high and the agent prefers to quit the collaboration?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed comments. \n\n**Question:** Can you provide more justification for why the agents always prefer to participate in the collaboration, even if the data-sharing cost is zero when the agent quits the collaboration?\n\n**Response:** In a general federated learning framework an agent may not want to participate due to high data sharing cost. However, our mechanism will subsidize such agents (see Line 262), and therefore they may tend to gain by participating compared to the utility they can achieve on their own. \nWe also remark that federated learning as a paradigm is most useful for agents who cannot get high utility on their own, and will benefit from the collaboration. For instance, agents having individual data sets on which trained models do not generalize well will benefit from models trained on data from other agents. Naturally, if an agent has extremely high cost of data sharing, for e.g. due to privacy laws, and the payment from our mechanism is insufficient, she will not participate in the collaboration."}, {"review_id": "a64c4BC7vR", "reviewer": "Reviewer_KoDx", "summary": "The paper shows that when every agent has a known concave utility function, the Nash equilibrium exists and can be reached independently via best response updates. Moreover, when all agents have linear costs, the proposed budget mechanism (which modifies the utility function) will lead to Nash equilibrium that maximizes p-mean welfare and fairness across agents. ", "questions": "1. Theorem 1 states that the NE using $\\beta^*$ will maximize the $p$-mean welfare for any $p ≤ 1$. Does that require the maximizer of the p-mean welfare for every $p ≤ 1$ to be the same? If so, why and how?\n\nOne potential counterexample with 2 agents is: out of the utility sample vectors (2,2) and (1,4), (2,2) has higher egalitarian welfare while (1,4) have higher utilitarian welfare.\n\n\nMinor suggestions (not affecting scores) \n* Line 217: explain that $||g(.)||_2 = 0$ at a Nash equilibrium\n* Line 255: $c_i$ is used as both the cost function and the per unit cost. The latter should use another notation for less ambiguity.\n* Equation after Line 264: add brackets for the summation\n* Line 271: spelling ‘defferred’\n* Line 289 can be clearer: the maximization problem can be converted to a convex minimization problem.", "limitations": "The conclusion briefly identifies the two limitations: 1) the assumption that cost and payoff functions are common knowledge and 2) agents may not report truthfully. The limitations (and weakness 1) can be further elaborated on in the appendix.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The differences with existing works are clearly highlighted. The paper novelly considers (i) the unconstrained setting where agents maximize their concave net utility functions, (ii) optimizing the p-mean welfare of the Nash equilibrium and (iii) the derivation of $\\beta^*$.\n2. Most of the claims and assumptions of the paper (e.g., concave payoff function, convex cost functions) are well justified.\n3. The paper is well-written and easy to follow. The implications described after the theorems aid understanding.", "weaknesses": "1. The paper makes two assumptions: a) the cost and payoff functions are common knowledge, and b) any agent utility (payoff and cost) only depends on the number of samples contributed. These assumptions limit the applicability/significance of the work and should be better justified. \n\nFor a), Line 317 proposes that the server can train a public accuracy function and broadcast it to all agents. However, in many FL applications, the server may lack data to do so, and clients may be unwilling to share due to the cost incurred. Moreover, the agents may disagree on the relative weightage of the cost/utility function (e.g., how much monetary cost should one unit of payoff function improvement be worth?) \n\nFor b), different subsets will lead to models with different performance and costs (e.g., lower if an agent only clones data or one agent may have noisier data). Further justifications (e.g., a trusted data sharing platform ensuring that agent’s i. (or i and j) data is sampled i.i.d) would help. \n\n2. In Sec 4, the definition of $u_i$ is unclear (re-defined on Line 260; 297) and is not explicitly expressed as a function of $p_i$ and $\\beta^*$. The descriptions can be improved. My interpretation is that $p_i$ acts as a cost subsidy; hence $u_i = a_i - (c_i - p_i)$ and $(b_i + c_i - p_i = B_i)$. From Theorem 4.1 onwards, $p_i$ uses $\\beta^*$ instead of any $\\beta$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the comments, suggestions and questions.\n\n**Weakness 1:** The paper makes two assumptions: a) the cost and payoff functions are common knowledge, and b) any agent utility (payoff and cost) only depends on the number of samples contributed. These assumptions limit the applicability/significance of the work and should be better justified.\n\nFor a), Line 317 proposes that the server can train a public accuracy function and broadcast it to all agents. However, in many FL applications, the server may lack data to do so, and clients may be unwilling to share due to the cost incurred. Moreover, the agents may disagree on the relative weightage of the cost/utility function (e.g., how much monetary cost should one unit of payoff function improvement be worth?)\n\nFor b), different subsets will lead to models with different performance and costs (e.g., lower if an agent only clones data or one agent may have noisier data). Further justifications (e.g., a trusted data sharing platform ensuring that agent’s i. (or i and j) data is sampled i.i.d) would help.\n\n**Response:** We will add further justifications on the assumptions. We believe this will help improve the paper, and we thank you for the suggestions.\n\n\na) We agree that we require costs to be publicly known, or at least verifiable by the mechanism designer. This is a common assumption made in previous work, e.g. Karimireddy et al [1].  Indeed, costs are common knowledge in many real-world applications e.g. (1) in many ML applications, each agent derives their training data from manually labeling a subset of a publicly available dataset like CIFAR or ImageNet, and the cost of labeling dataset is usually known; (2) in autonomous driving, where each data point is a random path taken under random external conditions. Studying incentives when costs are not public is an interesting direction for future work. \n\nSecondly you raise a great point about comparing the scales of cost and utility. However enterprises can (and often need to) correlate the model accuracy and their revenue. For e.g. improved accuracy of a diagnostic test in a hospital via FL will lead to reduced costs in terms of time, salary, and labor of the hospital employees, all of which can be quantified. Likewise for examples (1) and (2) above.\n\nb) This is an excellent point, and studying the model where agent utilities depend on the shared data set (and not just the size of the data set) is an interesting question for future work. Our goal is to make progress on the setting initiated by [1] and [2] where utility functions of the agents depend only on the amount of data shared. This assumption is justified in several practical scenarios, e.g. (1) and (2) above, and we will emphasize this in the paper by incorporating the suggested justification. Thank you so much!\n\n**Weakness 2:** In Sec 4, the definition of $u_i$ is unclear (re-defined on Line 260; 297) and is not explicitly expressed as a function of $p_i$ and $\\beta*$. The descriptions can be improved. My interpretation is that $p_i$ acts as a cost subsidy; hence $u_i = a_i - c_i + p_i$ and $b_i + c_i - p_i = B_i$. From Theorem 4.1 onwards, $p_i$ uses $\\beta^*$ instead of any $\\beta$.\n\n**Response:** Your interpretation of the subsidy $p_i$ is right. We will improve our exposition to make the definitions and intuitive interpretations clearer.\n\n**Question:** Theorem 1 states that the NE using will maximize the $p$-mean welfare for any $p\\le 1$. Does that require the maximizer of the p-mean welfare for every $p$ to be the same? If so, why and how? One potential counterexample with 2 agents is: out of the utility sample vectors (2,2) and (1,4), (2,2) has higher egalitarian welfare while (1,4) have higher utilitarian welfare.\n\n**Response:** Our Theorem 1 shows that our mechanism always admits a NE. Secondly, it shows that whenever agents contribute positively at NE $s^*$ (i.e. $s^* > 0$), then $s^*$ also maximizes the $p$-mean welfare among all feasible utility vectors arising from strictly positive data contribution vectors – call the latter set $U^+$. This implies that there is one point in $U^+$ that (weakly) dominates all the other points in $U^+$. Therefore, in your example there should exist a utility vector that dominates both (2,2) and (1,4) and hence that will be the NE as well as p-mean welfare maximizer. We will clarify this in the final version. \n\nReferences:\n\n[1] Karimireddy et al. “Mechanisms that Incentivize Data Sharing in Federated Learning”, NeurIPS 2022 FL Workshop.\n\n[2] Blum et al. “One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning”, ICML 2021.\n"}]

Author rebuttal:
We thank the reviewers for their time, suggestions and questions that we believe will improve the quality of the paper. Below we summarize our overall response to the reviewer’s questions and comments.

- We discuss our assumption of agent costs being common knowledge. We borrow this assumption from the significant previous works, which seems to be justified in many applications. We described these in detail in our response to Reviewers t7td and KoDx. Thank you for bringing this up, we will add discussion to this end in our final version. 

- We will add a discussion comparing other related work studying welfare maximization and incentives in FL, as suggested by Reviewers t7td and NtpC.  In summary, FL methods typically compute a model which maximizes some weighted sum of a function of agent’s accuracies. However these methods ignore data sharing costs and assume agents honestly contribute their available data. Unlike our work, they do not consider the strategic aspects arising from the cost of data sharing.

- We will clarify the novelty about our mechanism and the statement of Theorem 4.1, as suggested by Reviewers t7td, NtpC and KoDx. The derivation of the optimal parameter $\beta^*$ in our mechanism is novel. Moreover, Theorem 4.1 states that the mechanism admits a Nash equilibrium (NE), and whenever agents contribute positively at NE, it also maximizes the p-mean welfare among all utility vectors corresponding to positive sample vectors, for $p\le 1$.

- We perform a new experimental comparison with a relatively recent baseline MWFed from [1]. Our new experiments also show that our mechanism outperforms MWFed in terms of $p$-mean welfare, further supporting our theoretical results. Please refer to the response to Reviewer t7td for the new empirical results.

References:

[1] Blum et al. “One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning”, ICML 2021.

Meta-review: This work explores approaches for incentivizing collaborative learning while taking into account both payoffs and costs for each agent. All reviewers agreed that the topic was interesting and timely and that the paper was well-written and executed. It also noted that the analyses approaches themselves are somewhat standard and the assumptions potentially limiting for realistic federated settings. However, as one of the first works rigorously exploring these ideas, the analysis framework and application of it to federated learning seem to be a useful resource for the field, which could potentially be expanded on in future work to consider more complex scenarios. The authors are encouraged to incorporate feedback from the reviewers, especially regarding more thorough discussion of related work (both work on incentives in FL, as well as the discussion of how the proposed mechanism/analysis differ more generally from prior work in mechanism design).
Decision: Accept (poster)