The Fair Value of Data Under Heterogeneous Privacy Constraints in Federated Learning
Authors: Justin Singh Kang
Ramtin Pedarsani
Kannan Ramchandran
Venue: Accepted by TMLR ()

Abstract: Modern data aggregation often involves a platform collecting data from a network of users with various privacy options. Platforms must
 solve the problem of how to allocate incentives to users to convince them to share their data. This paper puts forth an idea for a fair amount to compensate users for their data at a given privacy level based on an axiomatic definition of fairness, along the lines of the
celebrated Shapley value. To the best of our knowledge, these are the first fairness concepts for data that explicitly consider privacy constraints. We also formulate a heterogeneous federated learning problem for the platform with privacy level options for users. By studying this problem, we investigate the amount of compensation users receive under fair allocations with different privacy levels, amounts of data, and degrees of heterogeneity. We also discuss what happens when the platform is forced to design fair incentives. Under certain conditions we find that when privacy sensitivity is low, the platform will set incentives to ensure that it collects all the data with the 
lowest privacy options. When the privacy sensitivity is above a given threshold, the platform will provide no incentives to users. Between these two extremes, the platform will set the incentives so some fraction of the users chooses the higher privacy option and the others chooses the lower privacy option.

Published in Transactions on Machine Learning Research (02/2024)
The Fair Value of Data Under Heterogeneous Privacy Constraints in Federated Learning
Justin S. Kang UC Berkeley
justin_ Keaiinn_kn@eeeeeee.cccco edu
Ramtin Pedarsani UC Sanfa Barbara
ramtin mentin&eece.. ucse.
Kannan Ramchandran UC Berkeley
kennonr@berkeleg.coo edu
Reviewed on OpenReview: https: // optp//veew....ew...mmo. net/ forum? id= ynG5Akk777
Abstract
Modern data aggregation often involves a platform collecting data from nelwork of users with various privacy options. Platforms must solve the problem of how to allocate incentives to users convince them to share their data. This paper puts forth an idea for a fair amount compensate users for their data at given privacy level based definition of fairness, along the lines of the celebrated Shapley value. To the best of our knowledge, these are the first fairness concepts for data that explicitly consider privacy constraints. We also formulate a heterogeneous federated learning problem for the platform with privacy level options for users. By studying this problem, we investigate the amount of compensation users receive under fair allocations with different privacy levels, amounts of data, and degrees of heterogeneity. We also discuss what happens when the platform forced to design fair incentives. Under certain conditions sensitivity is low, the platform will set incentives to ensure that it collects all the data with the lowest privacy options. When the privacy scnsitivity is above given threshold, the flatform will provide no incentives lo users. Between these two extremes, the platform will set the incentives so some fraction of the users chooses the higher privacy option and the others chooses the lower privacy option.
axiomatic
find that when privacy
1 Introduction
From media to healthcare transportation, the vast amount of data generated by people every day has solved difficult problems across many domains. Nearly all machine learning algorithms, including those based deep Icarning rely hcavily on data and many of the largest companics to ever exist center their business around this precious resource of data. This includes directly selling access to data to others for profit, selling targeted advertisements based on data, or by exploiting data through data-driven engineering, to better develop and market products. Simultaneously, as users become more privacy conscious, online platforms are increasingly providing privacy level options for users. Platforms may provide incentives to users to influence their privacy decisions. This manuscript investigates how platforms can fairly compensate users for their data contribution at given privacy level. Consider platform offering geo-location services with three privacy level options:
i) Users send no data to the platform - all data processing is local and private.
ii) An intermediate option with federated learning (FL) for privacy. Data remains with the users, but the platform can ask for gradients with respect to particular loss function.
im) A non-private option, where all data is stored and owned by the platform.

---

Published in Transactions on Machine Learning Research (02/2024)
If users choose option (i), the platform does not stand to gain from using that data in other tasks. If the user chooses (ii), the platform is better off, but still has limited access to the data via. FL, and may not be able to fully leverage its potential. Therefore, the platform wants to incentivize users to choose option (ii). This may be done by providing services, discounts or money to users that choose this option. Effectively, by choosing an option, users are informally selling (or not selling) their data, to platforms. Due to the lack of a formal exchange, can be difficult to understand if this sale of user data is fair. Are platforms making the cost of choosing private options like (i) or (ii) too high? Is the value of data much higher than the platform is paying?
A major shortcoming of the current understanding of data value is that it often fails to explicitly consider critical factor in an individual's decision to share data-privacy. This work puts forth two rigorous notions of the fair value of data in Section 3 that explicitly include privacy and make use of the axiomatic framework of the Shopley volue from game theory (Shapley 1952).
Compelled by the importance of data our modern ccon- onl and a growing social concern about privacy, this pa- per presents frameworks for quantifying the fair value of private data. Specifically, we consider a setting where users are willing to provide their data to platform in exchange for some sort of payment and under some pri- vacy guarantees depending on their level of privacy re- quirements. The platform is responsible for running the private learning algorithm on the gathered data and mak- ing the fair payments with the objective of maximizing its utility including statistical accuracy and total amount of payments. Our goal is to understand fair mechanisms for this procedure as depicted in Fig. !
Platform
Data
Utility
Services
Data
Discounts
Privacy Level
Money
Users
1.1 Related Work
Economics With the widespread use of the internet, interactions involving those that have data and those that want it have become an important area of study (Balazin- ska et al. 2011), and practical neccssity (Spickermann et al. 2015bh. Among these interactions, the economics of data from privacy conscious users has received signifi- cant attention in Acquisti ct al. (2016) and Wicringa et al. (2021b. The economic and social implications of privacy and data markets are considered in [Spiekermann et al.) (2015a). In Acemogll al. (2019) the impact of data ex- ternalities is investigated. The leakage of data leading to the suppression of its market value is considered.
Figure 1: Depiction of interactions between plat- form and users. Users generate data with phones, cameras, vehicles, and drones. This data goes to the platform but requires some level of privacy. The platform uses this data to generate utility, often by using the data for learning tasks. In re- turn, the platform may provide the users with payments in the form of access to services, dis- counts on products, or monetary compensation.
Privacy Currently, popular forms of privacy include federated learning (Kairouz et al. 2021 and differ- ential privacy (DP) (Dwork) 2008 Bun & Steinke 2016) either independently or in conjunction with one an- other. Our work uses a flexible framework that allows for a rage of different privacy models to be considered.
Optimal Data Acquisition One line of literature studies data acquisition, where platforms attempt to col- lect data from privacy conscious users. Ghosh & Ligett 20133 consider the case of uniform privacy guarantees (homogeneous DP), where users have unique minimum privacy constraints, focusing on characterizing equilib- ria. Ghosh & Roth 2011)) allows for heterogencous DP guarantees with the goal to design a dominant strategy truthful mechanism to acquire data and estimate the sum of users' binary data. In Fallah el al. (2022) the au- thors consider an optimal data acquisition problem in the context of private mean estimation in two different local and central heterogencous DP scttings. It assumed that players care about both the cstimation error of the common estimator generated by the platform and any payments made to them by the platform in their decision making. By assuming linear privacy sensitivity represented by scalars and drawn from a distribution,
2

---

Published in Transactions on Machine Learning Research (02/2024)
they devise a mechanism for computing the near-Bayes optimal privacy levels to provide to the players. Cum- mings et al. (2023) focuses on the central setting, under both the linear privacy sensitivity and the privacy constraints model, offering insights into the optimal solution. Hu & Gong (2020) goes beyond linear estima- tion to consider FL, where each user has a unique privacy scnsitivity function parameterized by a scalar vari- able. Users choose their privacy level, and the platform pays them via a proportional scheme. For linear pri- vacy scnsitivity functions, an efficient way to compute the Nash equilibrium derived. |oohh & Schoenebeck (2012]; Chen al.] (2018); Chen & Zheng (2019) also follow Ghosh & Roth (2011) and design randomized mechanisms that use user data with probability that depends on their reported privacy sensitivity value.
Fairness In Jia et al. 20199 Ghorbani & Zou 2019) and Ghorbani et al. (0200) framework for deter- mining the fair value of data is proposed. These works extend the foundational principles of the Shapley value (Shapley 1952). which was originally proposed as concept for utility division in coalitional games to the setting of data. Our work takes this idea further and explicitly includes privacy in the definition of the fair value of data, ultimately allowing us to consider private data acquisition in the context of fairness con- straints. Finally, we note that we consider the concept of fairness in data valuation, not algorithmic fairness, which relates to the systematic failure of machine learning systems account for data imbalances.
1.2 Main Contributions
We present an axiomatic notion of fairness that inclusive of the platforms and the users in Theo- remp [
The utility to be awarded to each user and the platform is uniquely determined, providing a useful benchmark for comparison.
In the realistic sccnario that fairness is considered between users, Theorem 2 defines a notion of fairness based axioms, but only places restriction relative amounts distributed to the players. This creates an opportunity for the platform to optimize utility under fairness constraints.
Section | contains an example inspired by online platform advertisement. to heterogeneous users. We use our framework to fairly allocate payments, noticing how those payments differ among different types of users, and how payments change as the degree of heterogeneity increases or decreases. We numerically investigate the mechanism design problem under this example and see how heterogeneity impacts the optimal behavior of the platform.
Finally, Section 5 explores the platform mechanism design problem. In Theorem we establish that there are three distinct regimes in which the platform's optimal behavior differs depending on the common privacy sensitivity of the users. While existing literature has investigated how a platform should design incentives for users to optimize its utility, this is the first work to consider fairness constraints on the platform. When privacy scnsitivity is low, the platform will set incentives to ensure that it collects all the data with the lowest privacy options. When the privacy sensitivity is above a given threshold, the platform will provide incentives users. Between these two extremes, the platform will set the incentives some fraction of the users chooses the higher privacy option and the remaining chooses the lower privacy option.
Notation Lowercase boldface x and uppercase boldface X symbols denote vectors and matrices respec- tively. X Y represents the glement-wise product of X and Y. We use Rzo for non-ncgative reals. Finally, x 2 y means that x, 2 y Vi. For a reference list of all symbols and their meaning, see Appendix A
2 PROBLEM SETTING
2.1 Privacy Levels and Utility Functions
Definition 1. A heterogeneous privacy framework on the space of random function A: N -> y is:
A set of primacy levels & C I220 U (oo), representing the amount of privacy of cach user. We use p to represent an element of & in the general case and e when the privacy levels are referring to DP parameters (defined below).
3

---

Published in Transactions on Machine Learning Research (02/2024)
2. A constraint set A(p) {A: X + +}), representing the set of random functions that respect the privacy levels E & for all i [N]. If function A E A(p) then we call it p-private algorithm.
We maintain this general notion of privacy framework because different. notions of privacy can be useful in different situations. For example, the lack of rigor associated with notions such FL, may make it unsuitable for high security applications, but it may be very useful in protecting users against data breaches on servers, by keeping their data local. One popular choice with rigorous guarantees is DP:
Definition 2. Pure heterogeneous e-DP, is a heterogeneous privacy framework with & = Rzo U (xo) and the constraint set A(E) {A: Pr(A(x) E S) S. e""Pr(A(x') e })} for all measurable sets S.
Henceforth we will use the symbol to represent privacy level when we are specifically referring to DP as our privacy framework, but if we are referring to a general privacy level, we will use P. Fig. [ depicts another heterogeneous privacy framework. P = means the user will keep their data fully private, P: = is an intermediate privacy option where user data socurely ag- gregated with other users before it is sent to the platform, which obfuscates it from the plat- form. Finally, if P; 2, the users send sufficient statistic for their data to the platform. The platform applies an p-private algorithm Ap x 4 y to process the data, providing privacy level P: to data Tr. The output of the algorithm = Ap(x) is used by the platform to derive utility U, which depends on the privacy level p.
Platform
Secure Aggregation
For example, if the platform is estimating the mean of population, the utility could depend on the mean square error of the private estimator.
Differences from prior work This formulation differs from the literature of optimal data acquisition (i.c., Fal- lah et al. (2022)) ) where privacy sensitivity reported by users, and the platform chooses privacy levels As based on this sensitivity. Privacy sensitivity is the cost that user experiences by choosing particular privacy level. Their formulation allows for relatively straightforward appli- cation of notions like incentive compatibility and individ- ual rationality from mechanism design theory. In this work, we instead emphasize that users choose a privacy level, rathor than report somewhat nebulously defined privacy sensitivity. Despite this difference, the notions of fairness described in the following section be applied more broadly.
P 0
Pe =
Pr
Figure 2: Users choose between three levels of privacy. Tf Pt = 0, users send no data to the platform. If Ps 1, user's model is securely combined with other users who also choose p = 1, and the platform receives only the combined model. If p: = 2, users send their relevant infor- mation directly to the platform.
2.2 The Data Acquisition Problem
The platform generates transferable and divisible utility U(p) from the user data. In exchange, distributes portion of the utility t( P-+) to user i, where p-: denotes the vector of privacy levels with the ith coordinate deleted. These incentives motivate users to lower their privacy level, but each user will also have some sensitivity to their data being shared, modelled by sensitivity function G : E + [0, oo), ci()) = 0.
The behavior of users can be modelled with the help a utility function:
u((p) = t.tp,,..pp - cx(p.).
(1)
The payment to user will tend to increase with a lower privacy level, as the platform can better exploit the data, but their sensitivity e; will increase with Pi: creating tradc-off. By specifying t: P-i), the platform effectively creates game among the users. This situation depicted in Fig. 3 Each user's action is the level of privacy that they request for the data they share. Users (players) select. their privacy level pa
4

---

Published in Transactions on Machine Learning Research (02/2024)
Platform
Payment (p)
(ata Pi)
User
U(p)
Payment (p)
(2))
Ptivate Algotitian
Ap
User 2
Maxiznize
U(p) Σ, (i(p)
(p(P))
(xN.PN)
(p)
Maximize:
(p) (PN)
Figure 3: Users send their data z; and a privacy level ps to the central platform in exchange for payments 4(66 p-1). The central platform extracts utility from the data at a given privacy level and optimizes incentives to maximize the difference between the utility and the sum of payments U(p) (p((p).
by considering their utility function u, and the potential actions of the other players. The platform's goal is to design the payments (pp; p-:) that maximize its net utility U(p) 1" t(p)..) One way to formulate this problem to consider maximizing this difference at equilibrium points:
maximize t(-).p
((p)-11t(pp)
(2)
subject to P NE))...
NE(t) denotes the set of NE strategies induced by the payment function which is the vector with payment function at index i. Recall that the NE is stable state such that no user gains by unilaterally changing their strategy. Depending on the circumstances, we may also want to consider equilibrium points in mixed strategies (distributions) over the privacy space. This could make sense if we expect users to continually interact with the platform, making different choice each time, such that users ultimately converge to their long-run average payoff. In such cases, we can formulate the problem for the platform as:
maximize 1(-),P
U(P)-1't(7)
subject PE PENE(t)
where we have used the shorthand S(P) E [s()) and P represents distribution the privacy space E. Note that in both equation 3 and equation 2 restrictions must be placed on t, otherwise it can be made arbitrarily negative. Individual rationality is common condition in mechanism design that says that a user can be made no worse off by participation. In Section 5 we consider a fairness constraint.
2.3 Model Limitations
Known sensitivity functions To solve equation 3 the platform requires the privacy sensitivity c, of each user, and our solution in Section5 depends on this information. This can be justified when platforms interact with businesscs. For example, an AI heath platform may interact with insurance companics and hospitals and can invest significant. resources into studying each of its partners. Another example is advertisement platforms and sellers. Another justification is that the privacy sensitivity e; is learned by the platforms over time, and we operating in regime where the estimates of c; have converged. An interesting future direction could be investigating this learning problem.
Data-correlated scnsitivity In Section 5 we trcat the scnsitivity function as fixed and known, but practical concern is that & may depends on the data T;, Say æ; is biological data pertaining to a disease. Those users with the diseases may have higher G;. Without taking this into account, the collected data will be biased. If our utility function greatly increased by those users who do have the discase though, they may receive far more payment, compensating for this correlation. We leave a investigation of cora-correlated sensitivity and fairness future work.

---

Published in Transactions on Machine Learning Research (02/2024)
Known transferable and divisible utility Solving equation 3 also requires knowledge of the utility function. In some cases, the platform may dictate the utility entirely on its own, perhaps to value diverse set of users. In other cases, like in the estimation setting of Example 3.2 it may represent a more concrete metric, like a risk function that is casily computed. In some cases, however, the utility function may not be easily compuled. For example, it may depend on the revenue of a company's product, or the downstream performance of a deep network. We also note that (:(p:: p-i) may not represent a monctary transfer. Individuals are often compensated for data via discounts or access to services. A shortcoming of our model is that assume a divisible and transferable utility, which may fail to capture these muances of compensation.
We also assume that users can compute and play their equilibrium strategy, which is standard assumption in game theory. Practically this also means that the platform must be transparent about the incentives, fully publishing this information to the users.
Informed and Strategic Users
3 Axiomatic Fairness with Privacy
What is a fair way to distribute incentives? One approach is to view the users and platforms as a coalition jointly generating utility. Following an axiomatic approach to fairness, the celebrated Shapley value (Shapley 1952) describes how to fairly divide utility among a coalition. In this section, we take a similar approach to defining fairness. This coalitional perspective is not a complete characterization of the complex dynamics between users and platforms, but we argue that it is still a useful one. One of the benefits of this concept of fairness is that it deals with intrinsic value (i.c., how much of the utility comes from the data). This is in contrast to the markel value that users are willing to sell for (potentially depressed). This information is particularly useful to economists, regulators, and investors, who are interested in characterizing the value of data as capital for the purposes of analysis, taxation, and investment respectivoly.
3.1 Platform as a Coalition Member
We define a coalition of users and a platform as collection of 8 users, with S S N and up to 1 platform. Let 2 E {0, represent the action of the platform. Let z when the platform chooses join the coalition, and 2 = 0 otherwisc. Let U() be as defined in Section - We augment the utility to take into account that the utility is zero if the platform does not participate, and define ps as follows:
U(z,p)== = U(() ==1
ps iES
[ps)
(4)
==
0
clsc
Let 6p(2, p) and dx(2, i E [N] represent the "fair" amount of utility awarded to the platform and each user i respectively, given and p. otherwise described as the "valuc" of user. Note that these values depend implicitly on both the privale algorithm Ap and the utility function U, but for brevily, we avoid writing this dependence explicitly. The result of Hart & Mas-Colell (1989) show that these values are unique and well defined if they satisfy the following three axioms:
A.i) Two equally contributing users should be paid equally. For any i,j E [N] : U(2, = (z, (su()) VS c [N][ = @1(2,p) = (z.
In addition, for any user E [N], U1L, Psu()) (11 ps) 0 VS [N] 6e(2, p) = 0.
A.ii) The sum of all payments is the total utility. The sum of values is the total utility U(z, p)
(p + E, p).
A.iii) If two utility functions are combined, the payment for the combined task should be the sum of the individual tasks. Let (p(2,p) and 01 p) be the value of the platform and users respectively for the utility function U, under the p-private Ap- Let V be a separate utility function, also based on the output of Ap, and let d,(z,p) p) and d((z, p) be the utility of the platform and individuals with respect to V. Then under the utility U + V, the value of user i is Φ,(2, p) + (() and the value of the platform is p) + p)
6

---

Published in Transactions on Machine Learning Research (02/2024)
Theorem 1. Let Φp(2,e) e) and 0z(2,e) e) satisfying arioms (A.i-fii) represent the portion of total utility awarded to the platform and each user i from ulility 622 Then they are unique and lake the form:
0p(2,p)
1
Σ SCIN]
U(2, ps).
(5)
N+1
N (is)
(z N+1
1
Σ
1
(S((()) Us)
(6)
SCIMM(
(s1+1)
Theorem is proved in Appendix B.2 and resembles the classic Shapley value result
(Shapley
1952.
3.2 Fairness Among Users
Though we can view the interactions between the platform and the users as a coalition, due to the asymmetry that exists between the platform and the users, it also makes sense to discuss fairness among the users alone. In this case, can consider analogous set of axioms that involve only the users.
B.i) Two equally contributing users should be paid equally. For any i,j E [N] U(psu()) = U(PSu()) AS c [N]Mi,J} = (((p)) (p(p).
In addition, for any user E [N], U(psu()) - (ps)) = o vS c (M]VC = (p(p) = 0.
B.ii) The sum of all payments is an ate) fraction of the total utility. The sum of values is the total utility app)U(pp) = Σ. (p). Where if U(p) = (p) then a(p) = a(p) and 0 v a(p) < 1.
B.iii) If two utility functions are combined, the payment for the combined task should be the sum of the individual tasks. Let ox(p) be the value of users for the utility function U, under the e-private algorithm Ap. Let V be scparate utility function, also based on the output of the algorithu Ac, and let (p) be the utility of the users with respect to V. Then under the utility + V, the value of user is (p(p) + (p).)
A notable difference between these axioms and (A.i-ifi) is that the efficiency condition is replaced with pscudo- efficiency. Under this condition, the platform may determine the sum of payments awarded to the players, but this sum should in general depend only on the utility itself, and not on how that utility is achieved.
Theorem 2. Let (p) satisfying arioms (B.i-iii) represent the portion of total utility awarded to each user from utility Upp). Then for a(p) that satisfies ariom (B.ii) &: takes the form:
a(p) N
(p)
Σ
(U(psu()) U(ps))
(N
SCINMM
The proof of Theorem 2 can be found in Appendix
B.2 This result is similar to the classic Shapley value (hhaply 1952 but differs in its novel asymmetric treatment of the platform.
Computational Complexity At first glance may seem that both notions of fairness have exponential computational complexity of N | This is only true for worst-case exact computation. In order for these notions to be useful in any meaningful way, we must be able to compute them. Thankfully, in practice, U typically has structure that makes the problem more tractable. In Ghorbani & Zou| (2019), Jia et al. (2019), Wang & Jial (023) and Lundberg & Lee (2017) special structures are used to compute the types of Shapley value surs we are considering with siguificantly reduced complexity, particularly in cases where the U is related to the accuracy of deep network. This is critical because we want to compute fair values for large number of users. For example, our platform could be medical data network with hundreds of hospitals as our users, or a smartphone company with millions of users, and we need be able scale computation to accurately compute these fair values.
7

---

Published in Transactions on Machine Learning Research (02/2024)
Example: Differentially Private Estimation In this example, use DP our heterogeneous privacy framework. Let X; represent independent and identically distributed data of user i respectively, with Pr(X; 1/2) P and Pr(X; = -1/2) = =1 11--1 with ~ Onif(O, 1). The platform's goal is to construct an e-DP estimator for μ = B[X;] = p-p1p1122 that minimizes Bayes risk. There is no general procedure for finding the Bayes optimal e-DP estirntor,, so restrict our attention e-DP linear-Laplace estimators of the form:
A(X) = w(e) x x
where Z ~ Laplace(1/n(e)). In Fallah et al.
(2022) the authors argue that unbiased linear estimators are nearly optimal in a minimax sense for bounded random variables. We assume a squared error loss L(a, (u) = (a - -42² and let Apn(E) be the set e-DP estimators satisfying equation S Then, we define:
Ac = argmin E[L(A(X),
= E()==
(9)
(E)
In words, As is an e-DP estimator of the form equation g where ((e) and 17(c) are chosen to minimize the Bayes risk of the estimator, and r(e) the risk achieved by Ac. Since the platform's goal is to accurately estimate the mean of the data, it is natural for the utility Ue) to depend e through the risk function r(e). Note that if U is monotone decreasing in r(e), then U is monotone increasing in e. Let now consider the case of N = 2 users, choosing from an action space of 3 = {0, for some é' > 0. Furthermore, take U to be an alline function of r(e): U(e) = cir(e) + c2. For concreteness, take (0) = 0 and suPEER U(e) = 1. Note that this ensures that U is monotone increasing in E, and is uniquely defined. Considering the example of binary privacy space & (0, ]o] (c' = oo), the utility can be written in matrix form as:
U([0, 0)) U((O,T)) = 2/3
2/3
U
(10)
U((',o)) U(K))e))
Derivations are available in Appendix B.1 Note from equation and equation 6 it is clear that Op (0 e) = 0. Let Φ and e."" represent the functions e,(1, and (1, in matrix form akin to U. Then using equation 5 and equation 6 we find that the fair allocations of the utility are given by:
Φ =
0
1/3
Φ (1)
1/3
2 11)
(11)
1/3
5/9
2/9
1/3 2/9
Consider the utility function defined in equation E = 0o). By Theorem the fair allocation satislying (B.i-iii) must be of the form:
10 for the N = user mean estimation problem with
(2)
O
0 2/3
(2)
O
0
0
A
AT,
[ S.
(12)
0 1/2
2/3
1/2
4 Fair Incentives in Federated Learning
FL is a distributed learning process used when data is either too large or too sensitive to be directly transferred in full to the platform. Instead of combining all the data together and learning the platform, each user performs some part of the lcarning locally and the results are aggregatod at the platform, providing some level of privacy. DDnahue & Kleinberg) (2021) consider setting where heterogeneous users voluntarily opt- in to federation. A natural question to ask is: how much less valuable to the platform is user that chooses to federate with others as compared to one that provides full access to their data? Furthermore, how should the platform allocate incentives to get users to federate? This section addresses these questions.
Each user E [N] has a unique mean and variance (0,, ~ θ, where is some global joint distribution. Let 6, represent some information about the user critical for advertising. We wish learn 0, as accuratoly as possible to maximize our profits, by serving the best advertisements possible to each user. User draws ny samples i.i.d. from its local distribution D,(0:, of), that is, some distribution with mean 0g and variance
8

---

Published in Transactions on Machine Learning Research (02/2024)
Figure 4: Each user E [N] has mean and variance (0:, af)) ~ O where θ a global joint distribution. Tet s² Var(O,) and p² [[] for all In this case 5² is large relative to r², and the data is very heterogeneous.
of. Let S² = Var(0.) represent the variance between users and x² E|o represent the variance within user's data. When 2² >> r² /n; the data is very heterogeneous, and it is generally not helpful to include much information from the other users when estimating 0,, however, if s² < r²/mi, the situation is reversed, and information from the other users will be very useful. The goal of the platform is to construct estimators 0f while respecting the privacy level vector p:
EMSE = E (8P(D)-
( 0.)2
(13)
Fig. 2 summarizes our FL formulation. Users can choose from a 3-level privacy space & {0, 1, In this case the privacy space not related to DP, but instead encodes how users choose to share their data with the platform. Let N, be the number of users that choose privacy level j. The heterogeneous privacy framework is given in Table Note that the error in estimating 0, depends not just the privacy level of the ith
Level
Description
Platform gets
Pi 2
Provide local estimator directly to the platform.
0,
P: = 1
Provide securely aggregated model with other users of same privacy level.
Ør = Nothing
1 Ni
Exp,=1
Pi = 0
Provide no data to the platform.
Table 1: Privacy Level Description
user Pt, but on the entire privacy vector. Let the users be ordered such that & is non-increasing sequence. Then for each i the platform constructs estimators of the form:
N₂
0 Oi
O
(14)
where, E, Wij 1 for all i. In Proposition found in Appendix B.3 we caleulate the optimal choice of way which depends p. From these estimators, the platform generates utility Up). The optimal who and wy in equation 14 are well defined in Bayesian sense if p; > 0 for some i, but this does not make sense when 0. We can get around this by defining (M) := ,2 + 2sa. For the purposes of our discussion, we assume a logarithmic form utility function. This logarithmic form is common in utility theories dating back at least to Kelly (1566). In the following section, we make a diminishing returns assumption to derive our theoretical result, which the logarithmic utility satisfics. The exact utility function we consider is:
2 U(p) = Σ log EMSE,(P)
(15)
0; represents the relative importance of each user. This is important to model because some users may spend more than others, and are thus more important to the platform i.c., the platform may care about computing their 6, more accurately than the other users. The argument of the log is increasing as the EMSE decreases. The log means there is diminishing returns as each 0, becomes more accurate.
9

---

Published in Transactions on Machine Learning Research (02/2024)
Fair Payment Deviation from Average
Pair Payment Deviation from Average
Pr 10
*
100
2
= m
P4 P4 100
100
P1=1
100
100
2m 0.1
100 A d=01P= 100 2= 100 ==011
(b)
Figure 5: (a) Plot of difference from the average utility per user Up) for each of the four different types of users, for three different regimes of s² Var(0;) and r² = E[aî), with heterogencity decrcasing from left to right. In left (most helerogeneous) plot users who choose P: = 2 are more valuable compared to those that choose P1 = 1. In the center there is an intermediate regime, where all users are paid closer to the average, with users with more data being favored slightly. the rightmost graph, with little heterogeneity users with more data are paid more, and privacy level has lesser impact on the payments.
(b) In each case there is user with a, 100 (indicated with star), while all other users f i have aj - represents the relative importance of the user in the utility function). In the two leftmost set of bars, we see that the user with A: = 2 and is high, but this becomes less dramatic as heterogeneity decreases. This shows that when users are very heterogencous, a, is large for only user i, most of the benefit terms of additional payments should go to user Likewise, comparing the second from the left and the rightmost plots we see little difference, showing that the opposite true in the homogeneous case: any user can benefit from any other user having a large ag
100 reccives by far the most payment, when heterogencity
4.1 Fair Payments Under Optional Federation
In this section, we focus on our definition of fairness in Theorem and analyze the fair values (P) that are induced when using that notion of fairness. Let there be N = 10 users. Nj 5 of these users opt for federating (p: 1), N2 directly provide their data to the platform (p; = 2), and finally, No = user chooses to not participate (p; = 0). In this subsection (and Fig. 5 without loss of generality, we assume a(p) = 1, and the results of this section can be scaled accordingly. The choices of Ps for each user depends on their individual privacy sensitivity functions G, but we defer that discussion to the next subsection.
Different Amounts of Data Fig 5a plots the difference from an equal distribution of utility, i.e., how much each user's utility differs from Upp)NN. We assume a, 1 for all users. In the bars furthest to the left, where s2 100 and 22 = 1, we are in a very heterogeneous environment. Intuitively, this means that a user j will have data that may not be helpful for estimating 0, for j * i, thus those users that choose P: = are paid the most, since the very least, the information they provide can be used to target their own 8,. Likewise, users that federate obfuscate where their data is coming from, making their data less valuable (since their own 0 cannot be targeted),
users with Pi 1 are paid less than even allocation. On the right side, we have regime where s² = 0.1 and 2 = 100, meaning users are similar and user data more exchangeable. Now users with larger n, are paid above the average utility per user, while those with lower na are paid less. Users with P; = 2 still receive more than those with p; = when n, is fixed, and this difference is significant when n, 100. Tn the center we have an intermediate regime of heterogeneity, where s² and 2 10. Differences payments appear less pronounced, interpolating between the two extremes.
except now each set of graphs, exactly one user has a; 100, meaning that estimating 8 for user 100 times more important than the others. Looking at the two leftmost sets of bars in Fig 5b that when i with P = 2 and n, 100 is the most important
More Valuable Users Fig 5b is like Fig 5a
10

---

Published in Transactions on Machine Learning Research (02/2024)
one, when s² is large compared to r², it is user i who receives most of the benefit in terms of its payment but when 8² is smaller, other users also benefit. This can be int explained as follows: if users are very heterogeneous, other users j # i do not have data that is helpful for determining 0;, thus they do not benefit when user has a larger at. Likewise, when 8² is small compared to r² not just user i benefits, but also all those users that contribute more data, as those users with p = 1 and n; = 100 are also paid over the average utility per user. Another key point is the similarity between the second and fourth set of graphs. This tells an interesting story: when users are not very heterogeneous, regardless of which user is has a, 100, is those users with large n4 that will benefit.
4.2 Platform and User Game Mechanism Design
11-30 302 Uner)
Th Usm)
n-- 110 Cler)
9. (2 User))
(1 Uec)
(Venze Cakes) Der (Yanea Cakms) Out Princy Seartntty
* Eyuilbeen
A
19
Figure 6: Plot of payments and user sensitivities & for different types of users with different sensitivity functions. Some user types are repeated, (indicated in the title), such that there is a total of N 10 Users. Users choose the privacy level P. to maximize the difference between their payment and privacy scnsitivity function. A star in each plot marks each user's top choice. The payment functions (:(p) changes based on the privacy levels of all the users. At the given configuration, which matches the left-most plot in Fig 5b (sa 100, = 1), no user benefits by changing their choice of pi, thus the configuration is a Nash Equilibrium.
Nash Equilibrium Under Fair Payments We have just discussed how the fair values (:(p) change depending on the model parameters, and the choices of privacy level ps. Now we discuss how the users come to decide their Pt- We again focus on the notion of privacy in Theorem 2 but we now restrict ((p) = a E [0, 1]. To avoid overly complicating the model, we take a; for all users. User i chooses their privacy level pi based both the payments that they receive from the platform ( p-:) well as their own unique privacy sensitivity function (p.). In this context,
view each user optimizing their own local utility function:
ue(p.. == ad(p;: -((:).
(16)
User i individually optimizes this function to determine their best response (denoted BR,) to the choices of the other users and the platform:
(p-() == arg max us(p:. p-:)
(17)
The full best response function BR(p. a)) (p-, BR N, a))² is a vector that collects all users' individual best response functions. The "fixed points" of the best response at given a constitute the pure-strategy NEs:
NE(a) == {p: p ()
(18)
Fig 6 depicts a particular fixed point of the best response function (therefore a NE) in our foderated mcan estimation example. Each of the N 10 users in assigned one of 5 unique sensitivity functions G, which are shown in the figure.
Solving the Fair Data Acquissiinn Problem The platform's goal is to set a such that it maximizes the total amount of utility it receives. Since the NE set depends on a the platform has some control over the behavior of the users. The mechanism design problem in this case reduces to:
maximize a,p
(1 (p)
(19)
subject to p E NE(o..
11

---

Published in Transactions on Machine Learning Research (02/2024)
0.16
Utlley
Objertive
Utlley
Platform Objective
2
Ri
10
14
10
R2
P4
10
12
NE2
10
10
NEa
16
10
10
10
10
10
10
10
100
1g 100
100,
(a) Homogeneous
(b) Heterogeneous
Figure 7: (a) and (b) The top of both sub-figures plot the optimization landscape for the platform design problem equation 19 The solid black line depicts the partial solution to equation 19 where we optimize over P for fixed a. Precisely that is: maxp(1 - ap)(p), P E NE(a). The bottom of each plot depicts the optimizing arg maxp (p-()aa(p()) (p), P E NE(a). Pi = O mcans that the users send no data to the platform, P: = means the users securely aggregate their data with other users, and P; = 2 means the users send all their data to the platform. Each row of bars corresponds to a unique user i. On the right-hand side, the amount of data cach user has n. given, as well as the color-code corresponding to the e of cach user. By looking al. the same color plot in Fig G the e, for the given user can be found. If there are multiple NEs that achieve the maximum utility, one is shown arbitrarily.
(a) Is in a homogeneous regime. In this example it turns out that the optimal a for the platform is such that both of the users with = 100 choose P; 1, while the other users choose p; = 0, showing the importance of the amount of data, as opposed to higher privacy options.
(b) Is in a more heterogeneous setting. We find that the optimal at ensures that most users choose p; = 2, except one user with high privacy sensitivity that chooses P: = 0, and one user that chooses P: =
Note that this is exactly equation 2 except we have used the fact that (p)) = E, Solving equation 19 is a daunting task, due to the complex structure of the constraint, however, it is numerically tractable in this case. The key idea to efficiently solve equation 19 is to exploit symmetries in the utility function. For instance, if p' is constructed from p by permuting the values Pi. where n, = nj, then Upp)= = Upp'). This allows us compute (p( for a much smaller number of representative p, rather than a full combinatorial search. Despite producing the same utility, p and p' may have very different stability properties. To deal this this, we can implement an efficient tree search identify the NEs within each group, Once we have an efficient algorithm for computing NEs, we conduct grid search to determine the optimal a. Note that for an arbitrary problem, finding the equilibria can be challenging task, and thus the more difficull. it is to compute the equilibria, the more difficult it will be to solve the design problem in equation 2 We provide a full description of our solution in Appendix D
Fig shows the mumerical solution to equation 19 for two different choices of s and r2. Fig 7a is a more homogeneous setting and we observe that the optimal a" sets the payment just high enough so that both of the users with n, 100 choose to participate at p; = while all other users choose p; = 0. Essentially, the platform identifies the two users with n, 100, and focused on collecting their data, rather than the data of the other 8 users. This configuration collects majority of the data for relatively little payment. Since the data is very homogencous anyways, the platform is not losing much utility by allowing those two users to choose P: = 1 hather than = 2. As the platform increases ar more users choose to participate, eventually with many of them choosing p: = 2, however, the benefit is minimal, and it is outweighed by the extra payments that are required to achieve that outcome. Fig 7b covers a more hetcrogencous sctting. In this setting, we see that a* is higher, and a larger fraction of the total utility is paid to users. For this a* only two of the users do not choose p 2. There is also one user with P 1, and one with p 0 that have
12

---

Published in Transactions on Machine Learning Research (02/2024)
higher privacy sensitivities. In the more heterogencous setting, allowing users to choose private option is more costly, so the extra payment to ensure more user choose Pi = 2 is worthwhile in this regime.
Other Formulations We conclude this section by remarking that this is just one particular formulation of a federated learning problem where users have privacy choice. Another interesting formulation can be found in Aldaghri et al. (2023), which comes from the litcrature on personalized federated learning Li et al. p2021p p. In this formulation, all users join the federated learning process, but some users can choose wetween private option, where their data is protected via differential privacy, standard non non-private option. Exploring fair incentives in this, and other models could be an interesting direction for future work.
5 Fairness Constraints: Data Acquisition
In the previous section, we considered a complex model, numerically studying the equilibria of the users based on fair payments from the platform, as well as how the platform optimally chooses a. In this section, we consider a tractable model and theoretically study how the optimal a" changes based on the privacy sensitivity of users, under a fairness framework based on Theorem 2 This section addresses this problem by investigating the incentives of platform designing mechanism under the constraint of fairness.
Consider N 2 2 users each with identical statistical marginal contribution, ie., for any i. we have S S (N])( U(psu(g) = (( The platform is restricted to making fair payments satisfying axioms (B.i-iii) with the additional constraint that a(p) = a E [o, 1]. Users choose one of two available privacy levels Ps E ENN, with & = (01.P2) and P > p1- We can write the utility of the user i as
u(p:: P-:)) ad(p; p-,) cl {p: p2)
(20)
Users gain utility from incentives provided by the platform but incur a cost of c they choose the less private option. For now, we assume e the same for all users; later we discuss the case where e is different. Note that we can drop the index of Φ; due to the assumption of equal marginal contribution. To enrich the problem, we allow users to employ a mixed strategy denoted by p [p, (1 - p)l", where users choose the pi with probability p and 2 with probability 1- p. This is justified because expect users to repeatedly interact with platforms and sample from their mixed strategy and ultimately converge to their expected utility.
The form is also trying to maximize the fraction of the total expected utility (p) := Ep-p [U()) that it keeps as in equation 3 The platform's goal is to choose a payment value a such that it optimizes:
maximize Or
(1 (1-a)U(p"aa))
(21)
subject to p'(a) NE(a).
The objective is simplified compared to equation 3 by exploiting the pseudo-efficiency axiom, which says that the sum of payments is a times the total utility. The constraint in equation 21 implicitly encodes the user behavior governed by equation 20 and will change with the privacy sensitivity Theorem 3 characterizes the solution of equation 21 for different values of c. To make equation we make some mild assumptions.
21 amenable to insightful analysis,
( 2 PS - - - ( U(P)) AA CN). Assumption 1. The utility U is monotone: PS
Assumption 2. The utility U has diminishing returns. Let Uprivaae (ps) represend the namber of elements of i E S such that Pt ph, i.e., the number of users choosing the higher privacy oplion. Furthermore, define (pU(ss)= == - U(p)), where P ((+)) equal to ps except pi ((+) = p/2- In other words, (pU(ps) is the marginal increase in udilily when the ith user swilches to the lower privacy option. Then U salisfies:
Meprinate (P 2 Aprivate (p' (2) - A(U(D (2))
(22)
It is helpful to define the expected relative payoff, where the expectation is taken with respect to the actions of the other players. When all other users choose a mixed strategy P. the expected relative payoff is defined as:
7(p) = o(p2: p) - ((pi:p) = Ep,>p (0(p::p)) - -(ph:
(23)
jti
13

---

Published in Transactions on Machine Learning Research (02/2024)
For convenience, we have defined y in terms of the scalar p, rather than the vector p [p, (1 p)]". This quantity represents the expected gain in incentive (normalized to make it invariant to a) if user switches to less private level from the more private level given everyone else plays the mixed strategy P.
Theorem 3. Consider a binery privacy level game with N users and platform. I satisfies Assumptions and & and the platform payments are fair as defined in Theorem 2 with constant a then the optimal a can be divided inlo three regimes depending on c. The boundaries of these regions are Tmas == maxp 7()) and some Cth "mao such that:
1. When > "max, =0 is the marimizer of
When Cth < c < Ymaz then a" is the minimizing a E [0, 1] such that p" pa(a) (a)) (c/aa)
When C < Cth: a² is the smallest a E [0, such that p(ax) = O, where
1 T/ U(D"(a)) ((0)
Gah = max
20 Va S c/Tmmnn
(24)
1 - a
Theorem 3 can be interpreted as follows. If privacy scnsitivity is above Tmaz for the given task, it is not worth the effort of the platform to participate. On the other hand, if privacy sensitivity is less than Ceb, the platform should set a to be as small as possible, while still ensuring that all users choose the low privacy setting. Finally, if privacy sensitivities lie somewhere in between, a² should be chosen based on the y function, and generally will lead to mixed strategy with some proportion of users choosing each of the two options.
Comparison to other works Two key novelties of our work is that we (1) consider constraint of fairness and (2) have users choose a privacy level, rather than report their privacy sensitivity. This is different from Fallah et al.] (0022), and Cummiings et al. (2023), which rely on incentive compatibility, and have users report their privacy parameters. In Fallah et al. (2022). a computationally efficient algorithm is proposed for computing user payments and privacy levels assign users. Both of these works consider a mcan estimation problem, where users have i.i.d. samples, and so also have the "equal marginal contribution" assumption that we have. Distinct from our model, users have an additional term in their utility where they benefit from reduced error in the estimation problem. These works focus on maximizing the platform utility, and it is very clear that the payments deviate significantly from the fair ones that satisfy the fairness axioms. Hu & Gong 22000) is perhaps the work most relevant to ours. They consider an incentive design problem where the platform fixes the total sum of payments R and the amount each user receives is proportional to their privacy level Pi: which the users choose. This proportional scheme, while potentially viewed as a type of fairness, does not satisfy our axioms. For a particular utility function, they develop a computationally efficient algorithm to compute the equilibrium privacy levels A based on the privacy sensitivities of the users and the total sum of payments R. In all of these works, users have a linear privacy sensitivity function with rate oa. Though this seems different from our binary privacy prob- lem, there is a direct correspondence here since we allow mixod strategics, so in expectation, our sensitivity is also reduced to a linear function of the mixed strategy: i.e., E [c {p- = ا2حم = c,Pr(p: = p)).
0.6
5.1 Mechanism Design: Mean Estimation Example
0.2
0.6
0.5
Let's look at the utility function from equation 11 and fair payments that we calculated from Theorem 2 in equa- tion [0] In this case there are N = 2 users, and we will assume each user has a sensitivity function as in equa- tion 20 This setting satisfics the conditions of Theo- rem 3 and so we can use our above result to character- ize the optimal at to equation [1 for a range of different e values. That is, as the privacy sensitivity parameter e changes, how is the optimal strategy of the platform im- pacted? Fig. g depicts the solution to equation 21 The
Total Utility U(aa')
Payments the Users
0
0
0.2
0.4
0.5
0.8
Figure 8: Utility of users and platform when plat- form solves cquation 21 The solution has three separate regions as predicted by Theorem 3
14

---

Published in Transactions on Machine Learning Research (02/2024)
top plot shows the optimal a" vs. c, while the bottom plot shows the total utility and the fraction of utility paid to each user at the optimal point a" for a range of c C [0,
As predicted by Theorem 3 we find that the solution is clearly divided into three regions. Equation 24 tells us that Ceh = 3/3 and Ymoo = 3, matching our observations in Fig. g In the first region when c f 3 the privacy sensitivity of the users is low, and the platform is able to capture most of the utility for itself, paying less of it out to the users. In this region, a" 2c, growing linearly with the privacy sensitivity. We also see that throughout this regime, the total utility is maximized, as predicted by the theory. In the region where E 13 I optimal a' is no longer growing linearly and now grows as a' 3c42 no longer have enough incentive to always choose the less private option, the total utility also begins to decrcase, mcaning less utility is available for incentives. These factors lead to a decrease in total utility in this region. As a* continues to increase towards 1. Once a' = 1 at c= 3 the platform is getting no utility, so may as well choose a² = O. Finally, for с 2 3: the platform no longer attempts to incentivize the users, and the total utility and payments fall to zero with a" =.
6c
For this particular example, it is possible to analytically solve the NE constraint in equation analytic expressions for the curves in Fig. S are given in Appendix B.4.1
21 exact
5.2 Considering Different Privacy Sensitivities
The computational burden in solving equation 21 is in characterizing the constraint, since the objective reduces to a one-dimensional optimization over E []. In the previous section, with the knowledge that the game is symmetric, we are able to easily characterize the equilibria as a function of a. If the q's are all different, for arbitrary utility functions, the problem essentially reduces to finding the equilibria in a general game. To make this tractable, we will need some assumptions. In Hu & Gong (2020), the specific choice of utility function and payments makes computation of the equilibrium tractable. If we have only two groups of users with different e; that act together, and finite privacy space, we can appeal to tools for enumerating equilibria in matrix games (Avs et al.] 2010). In this case if the privacy space is also binary, then the equilibria have an analytical solution, which we provide in Appendix b. Like the symmetric case, there are 3 cases for each of the two users as well as corresponding thresholds that depend on C1 and 02 respectively, resulting in 9 total cases. For example, in the case where payment is below the threshold of both users, neither participale al the low-privacy level, when the payment high enough both participate at the low privacy level, and for the remaining intermediate cases, either only one user chooses the low privacy option, or there is some asymmetric mixed strategy. Below, we numerically investigate this case:
This problem differs from equation 21 because the equilibrium is governed by asymmetric users. For example, if user 1 and user 2 have privacy sensitivity and 62 respectively, we have
in (pI. P2) = x (2)
p2 - [0 c1) [e]"Pp PI, u2 P2) = pf a (2) P2 - [0 oz) p2.
(25)
Consider a setting where there are only two users (these can be thought of as representing two groups of users) with utility function i1 and u2 listed above. Thus, when the platform is trying to optimize it's own utility, it must take into considcration that these two groups will play different stratogics.
maximize a
P UP - (1 -1))pppFu Up2
(26)
subject to (p1, E NE(a).
Fig. plots the results of simulating the solution of 26 It shows that there is one region when e1 and 02 are both small and close logether (< 1/3), the platform chooses a collect data from both users. If the difference is large, even in this region, the users may be asymmetrically engaged. When e > 02 1/3, the platform chooses a such that only user 2 chooses to participate, even if the difference is very small, and vice versa if 02 > Ci > 1/3, as before, when ci, C2 > 2/3 the sensitivily to too high and the platform can no longer offer enough payment to the users.
Broader Impact Statement One of the unique defining characteristics of data is that its generation pro- cess is inherently distributed, so single entity exists to advocate for data sellers. In the past, platforms
15

---

Published in Transactions on Machine Learning Research (02/2024)
02
0.1
01 06
0.
8.5
Figure 9: (Teft) The payments to user from the platform for range of c1 (Right) The platform's share of utility for the optimal a' payments for range of values Cı2 c2.
have been able to extract data from users, often with little to no compensation in return. As public con- sciousness around privacy changes, a muanced relationship around privacy between platforms and users must develop. Transparency and understanding the value of user data is an important step in empowering regu- lators, consumers, and platforms.
Users making strategic decisions about when they share their data stand gain from incentives.
For regulators, understanding the amount of value that flows through the interactions between platforms can enable better policies around data. Frameworks like those discussed in Theorem and can be starting point in understanding exactly how much this value is.
For platforms, understanding which data tasks are economically viable, and how they allocate in- centive important. Our discussion in Section and our three regimes help shed light on this.
6 Conclusion
This paper introduces two formal definitions of fair payments in the context of acquisition of private data. The first treats the users and the platform together and uses axioms like those of the Shapley value to determine unique fair distribution of utility. In the second, we define notion of fairness between the users only, leading to a definition of fairness that admits range of values, of which the platform is free to choose the most favorable. By formulating a federated mean estimation problem, we show that heterogeneous users can have significantly different contributions to the overall utility, and that a fair incentive, according to our second notion, must take into account the amount of data, privacy level as well as the degree of heterogeneity. We formulate and solve the problem, and also find that data heterogeneity and user properties play important role in the solution.
mochanism design problem in this federated mean estimation
While previous literature has investigated how platforms should design incentives for users in order to optimize its utility, the definitions of fairness we propose offers another important way to evaluate the fairness of these mechanisms. This is a critical step towards future research in ensuring that data acquisition mechanisms are both fair for users and efficient for platforms.
Though we provide a characterization of optimal fair mechanisms when privacy sensitivity is the same across users, designing mechanisms and developing theories that scale up these solutions to deal with platform that interact with large and diverse groups of users is critical. Additionally, users may come and go, their sensitivities may change over lime. Understanding how fluctuating users alter the model is of great practical significance. Furthermore, there is subjectivity in the choice of axioms, and other choices may lead to meaningful notions fairness worthy of study. We have also assumed a non-divisible and transferable utility, but many cases, users are paid for their data in the form of access to services. Investigating the impact of this will also be important for the practical application of comprehensive theory for fairness.
16

---

Published in Transactions on Machine Learning Research (02/2024)
References
Daron Acemoglu, Ali Makhdoumi, Azarakhsh Malekian, and Asuman Ozdaglar. Too much data: Prices and inefficiencies in data markets. Working Paper 26296, National Bureau of Economic Rescarch, September 2019. URL htttp://ww. nber. wttp:o////ppp//2226...6.6
Alessandro Acquisti, Curtis Taylor, and Liad Wagman. The economics of privacy. Journal of Economic Lit- eralure, 54(2):442 92, June 2016. doi: 10. /11257/je..5..2.44. URL https://wsrt wwtp://wwwweb..r/rriicccc.e..e.e id=10. 12.10..257//e1.5..22 442
Nasser Aldaghri, Hessam Mahdavifar, and Ahmad Beirami. Foderated learning with heterogencous differen- tial privacy, 2023.
David Avis, Gabriel D. Rosenberg, Rahul Savani, and Bernhard von Stengel. Enumeration of Nash equilibria for two-player games. Economic Theory, 42(1))9-37, 2010. doi: 10.1007/50009990009-0400 URL https: //doi.org/10 org/ 0000///001990000049------
Magdalena Balazinska, Bill Howe, and Dan Suciu. Data markets in the cloud: An opportunily for the database community. Proc. VLDB Endow. 4(12):1482 1485, aug 2011. ISSN 2150-8097. doi: 10.14778/ 3402755.3402801. URL https://doi. org/10. 44777/334025553402222
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Martin Hirt and Adam Smith (eds.), Theory of Cryptography, pp. 635-658, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg. ISBN 978-3-662-53641-4.
Syomantak Chaudhuri and Thomas A. Courtade. Mean estimation under heterogeneous privacy: Some privacy can be free, 2023.
Yiling Chen and Shuran Zheng. Prior-free data acquisition for accurate statistical estimation. In Proceedings of the 2019 ACM Conference on Economics and Computation, pp. 659 677, 2019.
Yiling Chen, Nicole Immorlica, Brendan Lucier, Vasilis Syrgkanis, and Juba Ziani. Optimal data acquisition for statistical estimation. In Proceedings of the 2018 ACM Conference on Economics and Computation, EC '1, pp. 27 44, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450358293. doi: 10. 01/5////111666211199
32191995
Fhih-Fen Cheng, Daniel M Reeves, Yevgeniy Vorobeychik, and Michael P Wellman. Notes on equilibria in symmetric games. In Proceedings of the 6th International Workshop On Game Theoretic And Decision Theoretic Agents GTDT, 2004.
R. Cummings, H. Elzayn, E. Pountourakis, V. Gkatzelis, and J. Ziani. Optimal data acquisition with privacy- aware agents. In 2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pp. 210- 224, Los Alamitos, CA, USA, feb 2023. IEEE Computer Socicty. doi: 10.1109 10.1109/SaTMI... M509///MMM55555522222222
URL http://h....eecooompeerrreeeeee/ http:///01.11100//5555555555555 2023. 000033
Kate Donahue and Jon Kleinberg. Model-sharing games: Analyzing federated learning under voluntary participation. In 2021 AAAI Conference on Artificol Intellegence, 2021. doi: 00.48550/ARXI 22100.00753.
URL https://arxivv org/ ab10 007553
Cynthia Dwork. Differential privacy: A survey of results. In Manindra Agrawal, Dingzhu Du, Zhenhua Duan, and Angsheng Li (eds.), Theory and Applications of Models of Compulation, pp. 1-19, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. ISBN 978-3-540-79228-4.
Alireza Fallah, Ali Makhdoumi, Azarakhsh Malekian, and Asuman Ozdaglar. Optimal and differentially private data acquisition: Central and local mechanisms, 2022. URL https://arxiv. .rgg 2201
03968
Amirata Ghorbani and James Zou. Data shapley: Equitable valuation of data for machine learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov (ods.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2242-2251. PMLR, 19-15 Jun 2019. URL https://proceedings mlr. wtw.s//ss/ http://vv///oobbbaiiaaam html
17

---

Published in Transactions on Machine Learning Research (02/2024)
Amirata Ghorbani, Michael Kim, and James Zou. A distributional framework for data valuation. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learn- ing, volume 119 of Proceedings of Mochine Learning Research, pp. 3535 3544. PMLR, 13 18 Jul 2020. URL https://proceeeding mml
http://wwwwa......ppp/////////ee wttp:///11//hooooa/a0000000 html
Arpita Ghosh and Katrina Ligett. Privacy as a coordination game. In 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1608-166 1615, 2013. doi: 10.1109/ 111099//lerton.2000
6736721.
Arpila Ghosh and Aaron Roth. Selling privacy at auction. In Proceedings of the 12th ACM Conference on Electronic Commerce, EC '11, pp. New York, NY, USA, 2011. Association for Computing Machinery. ISBN 9781450302616. doi: 10.1145/1993544.1900 19936605. URL https:///ot. http::://ao..og/11...o
1993574 1993605
Sergiu Hart and Andreu Mas-Colell Potential, value, and consistency. Econometrion, 57(3):589 614, 1989. ISSN 00129682, 14680262. URL
Rui Hu and Yanmin Gong. Trading data for learning: Incentive mochanism for on-device fedcrated learning. In GLOBECOM 2020 2020 IEEE Globol Communications Conference, pp. 1-6, 2020. doi: 10.1109/ GLOBECCOM2000.2200000 200.009222.22
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas J. Spanos. Towards efficient data valuation based on the shapley value. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of the Stenty-Seccon International Conference Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 1167- 1176. PMLR, 16 18 Apr 2019. URL https://proceedding mlr wtt.:prrrs///jjall/l/ll htmm
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Hu- bert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Koneený, Aleksan- dra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Praneeth Vepakomma,, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1-2):1 2):1-210,, 2021. ISSN 1935-8237. doi: 10. /22000000000 URL http: //dx dxx doi. org/ 10. (0.10220220000
John Kelly. new interpretation of information rate. the bell system technical
journal, joudrnal, 35()):117 926, 1956.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning, pp. 6357 6368. PMLR, 2021.
Scott M. Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS'17, pp. 4768 4777, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
Aaron Roth and Grant Schocnebeck. Conducting truthful surveys, cheaply. In Proceedings of the 13th ACM Conference on Electronic Commerce, EC '12, pp. 826 843, New York, NY, USA, 2012. Association for Computing Machinery. ISBN 9781450314152. doi: 11.14///229001222299766 URL
org/
10. 1 1111/1/2///1111 2229076
Lloyd S. Shapley. A Value for N-Person Games. RAND Corporation, Santa Monica, CA, 1952. doi: 10.7249/P0250
18

---

Published in Transactions on Machine Learning Research (02/2024)
Sarah Spiekermann, Alessandro Acquisti, Rainer Böhme, and Kai-Lung Hui. The challenges of personal data markets and privacy. Electronic Markets, 25(2):161-167, 2015a. doi: 10. 10.1007/11222555555111---9 URL
Sarah Spiekermann, Rainer Böhme, Alessandro Acquisti, and Kai-Lung Hui. Personal data markets. Elec-
tronic Markets, 25(2):91-93, 2015b. doi: 10.1007//12525-015-00113 URL
s1 612625-015-0190-1
Jiachen T. Wang and Ruoxi Jia. Data banzhaf: robust data valuation framework for machine learning. In Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent (eds.), Proceedings of The 26th International Conference Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Re- search, pp. 6388 6421. PMLR, 25 27 Apr 2023. URL https:://prceeddinnnn mlr pttppp///////aag////// html
Jaap Wieringa, P.K. Kannan, Xiao Ma, Thomas Reutterer, Hans Risselada, and Bernd Skiera. Data ana- lytics in privacy- world. Journal of Business Research, 122:915-922 2021. ISSN 0148-2963. doi:
2019..0.0000 URL http://wwwwwcieeeeeerrett..... articlee/h1/900445991339877
19

---

Published in Transactions on Machine Learning Research (02/2024)
A
Notation Table
Symbol
Definition
Relevance
E
privacy level space
N
Number of users
Pi
privacy level (generic) of user i privacy level (DP only) of user i platform utility function user i's utility function
E
U+)
m.())
All
40
privacy sensitivity function
NE()
Nash Equilibrium
4()
generic payment function
(.())
fair payment function for user i under Theorem &
2
0x(+)
fair payment for platform under Theorem
a(-)
fraction of utility used as payment in Theorem 2
user i'ss amount of data variance of user means mean of user variances relative user value in utility function best response function
s²
Section 4
a,
BR,())
p
prob. of playing more private option in mixed strategy expected relative payoff by changing strategy
Section 5
7(-)
Table 2: Table of Common Notations
B Missing Proofs
B.1 Proof of Equation 37
In this section, present the calculations required to arrive at the utility values in equation 37 First let's treat the trivial case of 6 0, 62 O. The optimal c-DP estimator is simply the optimal Bayes estimator with no data, i.e., the prior mean. Let us define this estimator as (uo,, = O. Its risk function is
R(p, (o.,)) = E [L(ro.,) 4) []] = n²,
(27)
The Bayes risk of fi)0,0) is the expectation of this quantity taken using our prior:
1
r r(00, 0)) = E [M²]]
(28)
12
Next, consider the case where user i chooses privacy level él = e' > 0, and the other user chooses = 0. In this case the estimator depends on X1, ( = w X1 + Z. Then the risk function is:
R(u,P(c.o)) = E [ww]X + 11) []]
( ( ( 1) (N (w- w1 3
2 + (-u+ 1/) (u+
w1
+
2
(29)
2
172
Now taking the expectation with respect to our prior over μe, have:
1
2
E [(((p,
(3w?
2w + 1) + 172'
(30)
12
20

---

Published in Transactions on Machine Learning Research (02/2024)
here 17 is the inverse scale parameter for Z. Note that equation 30 is minimized when oj is maximized. The
c. 6-DP condition enforces the constraint 1) S wr This constraint will be met with equality for the optimal
w1. The optimal w 34 52
Thus, we have:
e' 3r + 24
X1 + Z, P(e.0) 3 72
Z ~ Laplace
(31)
and the resulting Bayes risk is:
1 1
r((e', = r((o,e)))
(32)
3
+ 24
For the case with e1 62 e' we can repeat the same process by defining P(e',e") w X1 w2X2 + Z. By symmetry, must have u1 w2 we drop the index. Then the risk function and its expectation are:
(())) = (n+,)) ;) (-u+ )) x= + (ut 2) (w - -1²² 2 + (-ut 2) (u + w)² 2²
(33)
2
E [R(U, P(e)e
12 (8w² 4u + 1) + 172
(34)
By similar argument to the previous case, the Bayes optimal estimator and the corresponding Bayes risk is:
E' 4 + 12
P(cee) = 4+
(X
+ X2) + Z,
Laplace
(35)
12 22
1
r(<,c])=
(36)
12
2 + 2
Finally letting U(c) = +22()) Take U(0) =0 Simplifying gives us our desired result:
-12cg. And max, U(c) = 24(1-c2)
U((0,0F)) u((0)T9)] O(7 ((C,)11)
0
2(3 3 +
24
U =
=
(37)
2 3
21 (e))
(c')²
B.2 Proof of Theorem 1 and Theorem
which is standard and follows the typical proof of the Shapley We will begin with the proof of Theorem 2
value. We begin by proving di (p) as defined in equation 7 satisfies axioms (B.i-iii.. First assune U' ('psuta) U (psub))) AS [N]. then:
a(p)
U(psu(s)) - UU(s))
(:(p)
Σ
(38)
N
(1STT)
SCINIM
a(p)
U(psufi)) - Upss)
(U(psu()ura)= -U (psu()t)
Σ
Σ
(39)
N
(YE71)
(19171)
SCINTHAL)
SCINMMid
a(p)
U(PSU()) U(ps)
(U(PSU(OU()) - U (PsS()))
Σ
Σ
(40)
N
(N-1)
(151+1)
SCINTHES
SCINMAA
()(p),
(41)
21

---

Published in Transactions on Machine Learning Research (02/2024)
proving axiom (B.i) is satisfied. For the proof that axiom (B.ii) is satisfied, write:
a(p)
((ssuta)) (pss)
Σ
(42)
N
(15))
SCIN
a(p)
U(psura)
Ups))
Σ
Σ
Σ
E
(43)
N
(1s))
IN
SE(NTR()
SCIN)(()
[S|
a(p)U(p) a(p)
E U(psu(a)
Ups))
Σ
Σ
E
(44)
N
(15))
SENNM (1s)
SEIM]N() 18|
= a(p)U(p) + d(pp
U(ps)
(N - (SS)U(ps))))
Σ
Σ
Σ
(45)
N
(1-
(1s))
SCIN
SCIN]
iES
1SISN-1
|S|EN-1
ap))U(p) a(p) N
SSU(PS)
(N - (S)
Σ SCIN]
E SCIM
(46)
(181-1)
(18))
ISISN-1
N
(p))
(47)
thus proving axiom (B.ii) is satisfied. Finally, we note that (B.iif) is satisfied by lincarity. Next, we establish the uniqueness of equation 7 To prove uniqueness, we take approach that is standard in the literature where we define the unanimity game, show the uniqueness of the 6i (p) in that case, and then argue that uniqueness follows from additivity (B.iil..
Define the unanimity utility, indexed by some T S [N]]
{1
1 if T' C supp(p)
UT(P)
(o if else.
(48)
(UrbTCI form a lincar basis for utility function such that any utility U can be represented uniquely by set of values {br brgi)- In addition, by direct application of the axioms, it is easy to see that for the unanimity utility, the fair allocation of (p) is unique and is of the form:
(P)
a(p)
T
ifET
(49)
0
else.
Thus, for any utility U, the fair value is represented uniquely by bTo (p), (p), since this value is unique, it must be equivalent to equation
Now we consider the proof of Theorem By a similar argument to the above, we can establish that:
U(z, Ps) U(O.ps)
pp(2,p)
(50)
N
SCIN]
as well as:
(1(2,p) = N+1
1
Σ
N (su(a) - (181+1(+==))
1
(51)
SC(NM(
2'E(0.=)
(52)
22

---

Published in Transactions on Machine Learning Research (02/2024)
Applying the definition (0, p) = 0 have
U(2,
pp(2,p)
Σ
(53)
N+1
SE(N! (15)
(1(2.))
Σ
(U,z, PSu((t) U())ss).
(54)
(S|+1
completing the proof.
B.3 Error Computation for Section
In this section we prove Proposition and from which exact error expressions follow. Proposition 4. For the federated mean estimation problem described in Section the expected mean-squared error is given by:
08 0.) )
E
2
N2
N2
N2+-N,
N2
N2 N1
2
wi
+
2
w +
Σ
W3y +
(55)
n2
72
N
N
j= N
j= No++1 jtf
j
jft
-1
No No
where 7
Ni
+=
N
Proof. Consider an estimator of the form 0: =
Σ Ur where user j has n samples, and 02 is the local
model of user j. By Theorem 4.2 of Donahue & Kleinberg (2021] the error can be written as:
2
N
E
0 - 0.)²
=
+
s2
Σ j+z
2
+
Σ
(56)
Tij
jfi
For j = I,..., N....,N,, N2, we have Vij = Wij- For j = N2 + I,..., N₂ + Ni, we have Vig =
wio N1
Finally, for
> N1 + N2, we have Vij = 0. Thus the first term can written as:
N
N2
No+
2
=
2
W
WiD
(57)
T2j
T2j
T
N
1=1
j=N
N2
2
W0
+
w
(58)
N₂
n
Making these same substitutions to Ejsi uij and Σ ij Bi yields the desired result. Proposition 5. The error expression equation
55 is minimized if ps 0 with weights:
Ni
Vo/V2
Wij
(59)
N1
No
N + N
If = equation 55 is minimized by:
N
N₂
(60)
+
N2
N + N₂
Vo V
23

---

Published in Transactions on Machine Learning Research (02/2024)
V
$²
Wij N1
N2 Vo
N1
N2 Vo
Vj
(61)
Finally, P: = 2, equation 35 is minimized by:
N
N1
Win
Ni N2 2
Ve
N1 + N₂ Vo V.
(62)
A
Vo/V,
Vo/V,
32
wi
NJ + N2
Ni N₂ Vo
22 V
(63)
Vo/V WH NI N
Ni N Vo
V. 52
+
(64)
Vo
N + N2
Vo V V
Proof- First will consider the case where P 1. Considering the point where the derivative of equation with respect to Wik, k 2 1 is equal to zero gives:
55
2r²
2x²
N1 1
N₂
2
N2
))
Wis
Wif
+s²
2w0k
2
1
Σ
Wij
N1
1
wij
=0, (65)
Tkk
NNN
N?
N
==1
==1
2 Wikk
722 +
s²
+2
s2
W10
(66)
T4k
N1
N1
It. easily verified from the second derivative that solving this equation gives the unique minimum of
N2
-1
equation 55. For ease of notation, define V2 =
122 nx
+ 5²)
and Vo = +
Thus,
N₂
Vn
we have:
RiD Vo
Wik
N1
(67)
V/8
Noting that wio + E5=1 wiy 1, we have:
N2 VO
N2 2 N1 V
430 +
1,
(68)
N
V
N1
N₂
2
WAO
+ N
Ni + No
V
(69)
Vo/V,
$2
Wij =
N N₂
Vo
N1 + N₂ Vo V,
(70)
This completes the proof for those users such that P = 1. When Pj = 2, the gradient condition with respect to 1, k # is:
Vo Ni
Wi V4
W4o:
(71)
and similarly, the gradient condition when == is:
NoVo
2²
V.VV + WhO
+ = 1.
(72)
N, V
V.
Combining these together gives desired result. P:
7
24

---

Published in Transactions on Machine Learning Research (02/2024)
B.4
Proof of Theorem 3
The symmetric Nash equilibria of our game is characterized Cheng et al. (2004) by the minimizers of
min Σ (u(s.p) u(p.p)]²,
(73)
where u(s,p) is the utility a user when they choose privacy level Pi 8, and all other users play mixed strategy P. and p) = Es-p [u(s,p)]- Since our action space is binary, there are only two terms in this sum. Applying the definition of u and writing out both terms of this sum yields:
E(u(s: - u(p,p)]+ SEE
[u(pr.p) u(v, + (u(p2.P) p) - u p).
(74)
[c(1 p) a(p(p.)) 60n p))] + |e(1 p) - a(d(p,p) 6(22, p))] (75)
= [(1- ar(p) -1
(76)
where we define r(p) = x(p2,)) p) p) 7 is an important quantity in this problem that described the relative increase in payment user receives for choosing higher privacy level when the other users choose mixed strategy
In general, to say something about the equilibria, we must say something about y. We can now use Assumptions and 2 as well as the definition of d(:+) to establish properties of y. First we show 7()) 2 0 using monotonicity of U:
>() ((2.P) p) p),
(77)
Epprp pi=pls
Σ ()
(U(psutt) U(s)))
(N-1)
Epprp PEEP
(U (U( U(ps))
(78)
N
SCINTEEs (Ns))
Eppop SCINTV (s)) ##1
Σ
(UP - U U( 20.
(79)
In equation 78 we have used the definition of the fair value from Theorem 2 and in equation 79 we have simplified the expression, exchanged the sum and expectation, and used the fact that the expectation of a non-negative random variable is non-negative.
Next, will show that under Assumption 2 (and our assumption of equal marginal contribution) we also have ((p) 2 0. Assume p2 Pl: and let b(n,p) (1)((1 (1ppp11p1") N-i)
((22) - (P11) Σ
1
Enaopa jti
[U(pSt(a) UpP U(PSttD)
Enyops jfi
[U(pStta) U U(pS)t0)
(N-1)
SE(N](()
(80)
N
N Σ
Σ [S
b(n
s.t. Mprivate (p(n)) = -
(81)
(N-1) SCINTAE)
Now note that 6(n, P2) b(n, Pı) is zero-mean, and decreasing, furthermore, (UU(((n) is non-negative and non-increasing. Let n² represent the smallest value of n such that (2),P2) - is negative. Then we have:
A,U(p(n)) = Σ (b(n, - ((.p)))))(( + (b(n,p2) b(n, A(U(p)
(82)
n=
b(n, - p2). b(n.21)
(A.U(p(n" - 1)) - A,U((((")))
(83)
n=0
0.
(84)
25

---

Published in Transactions on Machine Learning Research (02/2024)
With the knowledge that 7(p) 2 0 and 7(p)) 2 0 compute p" for three distinct cases. Defining Ymaa == maxp 7(p) and Ymii == minp 7(p), we have:
Case
c 0'/ma > O:
Σ [u(s.p) - u(p p)l -
(11-)(cc p)(c-on(d))
(85)
Since this quantity is non-negative, it is clearly minimized when p' = 1, where it is exactly 0. Furthermore, since c - 0'/maa > O is satisfied with strict inequality, it is the unique minimizer.
Case c/a E Mmmsn Ymaz]:
Σ (u(s,p) u(p, p)p. [(1 p)(c ax())) (-p(c (-ple))
(86)
In the above case, this minimized when p" (c/o).
Case C O'minn <
Σ [u(s,p) - u(p,p)1 =
(87)
SCE
In the above case, the expression is minimized when p" = 0. To summarize, we have:
if a Tmux
p' = (c/a) if a E
(88)
a
Ymin
This establishes that the Nash equilibrium is cleanly separated into three regions. From this fact, we are able to show that the optimal strategy of the platform is also separated into three regions. We consider a platform that solves the following problem, where we define U(p) == Ep:~ (p))):
min(1 - ax)
(89)
Clearly, when privacy sensitivity is large, specifically, when c 2 Imas then a' 0 is the optimal solution, since (a(a) for all < 1, and for > 1 the objective becomes negative.
Alternatively, when e is very small, we determine the optimal value follows. We first note that Assumption implies that Up) is a decreasing function of p. Thus the condition for a* Tmmn is:
c/Timnn ((p Va < c/Tminn U(0)
(90)
1 --a
1 Since the left-hand side takes value T-a at c= O, while the right-hand hand side is 1, as well as the fact that both sides are continuous, by the Intermediate Value Theorem, (and our previous result, which implies that for large enough this condition does not hold), there is some minimum Cth, where this condition fails. Thus we conclude, there three regions:
(1) a region where S is small, and a" is the smallest such that p* 0, (2) intermediate region where a symmetric mixed strategy is played, and (3) a region where 2 Tmax and a 0.p" =
B.4.1 Exact Calculation for Example
In this section, work thought example in Section 5, showing that using Theorem and some basic caleulus, can determine valuable information about a The utility function is of the form:
2/3
U =
(91)
2/3
1
26

---

Published in Transactions on Machine Learning Research (02/2024)
$ (
0
2/3
$
a
0
(92)
1/2
2/3
1/2
When users play a mixed strategy p, the utility (p) can be written as
Up)) = p²
3 + 1.
(98)
The gamma function likewise can be computed as
1 + p
7p))
(94)
2
Thus, we find that Mmaa = 2 and Ymin 2. This allows us compute p" (a))
if < 3c
?
(a(a)
6
3
3e S a S 2c
(95)
2
if a 2c
From this and Theorem 3 we immediately know a² = 0 when
2 3. Next, we can determine Cth- First, we
compute U (a)):
if
U()'
8c
12ca
36 <
a S 2c.
(96)
?
if
The threshold is concerned only with a S 2c. We note that for c < the function (1 ())()*(a))) is monotone 0 S S 2e, and attains the value 1 2e a 2c. However, for e < 3. exceeds 1 2c it's maximum value at a 3c42
6e Thus, cth is z. To summarize, the optimal a* is:
2c
1 if
3
a"
6c 30+2
if 1
(97)
if 3
and making the neccessary substitutions generates the plots in Fig
C Monotonicity of Utility
When beginning this work, the dearth of algorithms that supported heterogeneous privacy constraints sur- prised us, given the increasing number of privacy options available to users. All of the algorithms that did cxist were provably sub-optimal Hu & Gong (2000), or placed constraints on privacy parameters to prove ap- proximate optimality Fallah et al. (202)). In both of these works, the pathology of the algorithm leads to er- ror that is not monotonically decreasing in p. For DP-based notions privacy, which both the aforemen- tioned works arc, one can prove that an optimal error must be monotonic. This observation inspired a recent work that studies saturation phenomenon Chaudhuri & Courtade (2023). Similar ideas can also be found in Cummings et al. (2023). The idea is that optimal algorithm will sometimes give users that choose large 6 more privacy than they asked for, to ensure that it still efficiently uses information from users j with E, << Ej.
D Solving the Federated Mean Estimation Mechanism Design Problem
In this section we discuss how we produce Fig 7 Algorithm D describes the process. In the first step, we exploit the symmetry of the utility function by exploiting the fact that the utility does not change when is exchanges between two users with the same ny, This greatly reduces the number payment functions that need to be calculated. Next, we compute the payment functions, again exploiting symmetry whenever possible reduce calculations. Finally, for each partition, we efficiently search through the partition see if there is a p that leads to NE.
27

---

end Published in Transactions on Machine Learning Research (02/2024)
Algorithm 1: Find optimal a
input n4, C N
output: a²
nArray(i) < Riy
N;
cArray(i) < C,, i
N:
partitions + GetValiiPartitions (n, == ,...,N).
/* all p that produce unique U */
for i= to len (partitions) do
p < partitions(i):
/* one representative p from the partition */
for j = N do
phi(j) Shapley j, nArray); end
/* Actual code skips repeated calculations
for E grid do neExists + TreeSearch (a x phi, cArray); /* Check if any in the partition is NE */
if neExists then
currUtil + (1 - a) xUtility (p, nArray):
if currUtil > maxUtil then
a² + a maxUtil currUtil;
/* Update a' if needed
end end
end
Comment on Fig 7 The observant reader will notice there is almost always one user with P; = 1. This is an artifact of our model, where only one user chooses p; = 1, essentially behaves the same from a utility perspective as has chosen A 2, but gets a roduced privacy scnsitivity. It possible show that this means that other than the all zeros NE, there will always be user with p =.
E Equilibria for Binary Privacy Level with Two Different Privacy Sensitivities
Let = lp (1 p)]² be the mixed strategy of user 1 and let q [q (1 g)}² be the mixed strategy of user 2. When they play these respective strategies, the utility of user is:
in ui(p. q) paob(p's (2) + p(1 - ()ve(p)) + (1 p) p + (1 pp - g)a0(p2 122 + -cr (1(11 p)
pam(p1, 9) + (1 100-pp)akk p) a1(1 pp)
a) a q) - c1.
By a symmetric argument, we also have that
u2(p.q) q (c2 (p))) ao(p).)) C2.
(98)
We interested in characterizing the best response maps:
BR, a:) arg max BR2(p: arg max wa (p
(99)
since their intersection characterize the set of NEs.
We begin with finding an analytic expression for BR, (q:a), which, we will break into three distinct cases:
Case 1:
Ci 0'moe
In this case, the constant factor in front of p always positive (invoking the monotonicity and non-negativity proved in the previous section under the assumptions), thus the best response is:
(q: [1 0f Va Ymaz
(100)
28

---

Published in Transactions on Machine Learning Research (02/2024)
Case 2: C1 0/min 0
In this case, by similar argument to before, the constant factor in front of p is always negative, thus the best response is:
(q = [0 1]" Yo Ci
(101)
Mmin
Case 3: a E
_
Tmars
In this case, the sign of the factor in front of p changes with q. We can write the best response piece-wise as: ci ar(1) > {la 61" 61"h a abb= if an(1) = 0 c (n < 0
O1
(q: =
(102)
10
This samne analysis can be applied to (p; The NE is characterized by the sets where these two maps intersect. The following table summarize the equilibria p", "", written as scalars for readability.
Tmar
Tmaa
Ymam
(1, 1)
(0,
(0, 1)
Omaz
(1 Tmax
(1,0)
(1,
(0,1)
Ymun
2g
(1,0)
(1,0)
(0,0)
7mii
When a is below the threshold for the two users (the top left entry), both ei and 02 are too small for it to be worthwhile for the users participate at the lower privacy option. Conversely, if is above the threshold for both users, then both users choose the less private option. When neither of these extremes occur the results are more nuanced.
29


Reviews:
[{"review_id": "42VPpl8Sjg", "reviewer": "Reviewer_RwJN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "See above", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Overview: The work studies the problem of a data aggregator attempting to learn from a collection of users who are heterogeneous in their privacy preferences. In this set-up, data subjects have multiple “privacy levels” at which they can choose to participate. For example, they may be able to participate with eps=1 or eps=2. The authors pose this as a mechanism design problem where the aggregator is required to come up with a payment function (monetary or otherwise) that incentivizes data subjects to participate with weaker privacy guarantees (e.g. a larger epsilon), while maximizing their profit (final utility - payments). The key contribution of the work is define what it means for such a payment structure to be “fair”. In the federated learning setting, a key component of the set of axioms for a “fair” payment structure set out by the authors is that two subjects should be compensated equally if their contribution to the utility is equal. A subject whose data does not impact the utility should not be compensated. \n\nGiven a utility function, the authors show at both a general level, and in specific examples, how to construct a “fair” payment structure. They give a specific, small scale example, to show how the optimal fair payment favors data subjects with highly influential (e.g. high quality) data, or who are willing to participate with lower levels of privacy. They also show how differential levels of heterogeneity in the data subjects can shift the relative payment between the subjects. \n\nComments:\nGiven the assumptions set forth in the paper, I think the formulation of the problem is nice. The axioms make sense. I thought the examples in Section 4 and Section 5.1 do a great job of illustrating how the optimal solutions behave. I found Figure 5 particularly interesting as it showed how heterogeneity in the user population plays a role in defining the optimal scheme.\n\nMy biggest concern with this work is the underlying assumption that a data subjects privacy preferences are a) a choice, and b) independent of their data. In practice, I think this is unlikely to be true. For example, data subjects with anomalous data (e.g. who are positive for a disease) are more likely to have a higher preference for privacy. Also, data subjects from historically discriminated against demographics are also more likely to place a higher value on privacy. I think this affects the work in a couple of distinct ways.\n1. Given that the complex societal factors that go into privacy preferences, it seems worth examining whether paying data subjects based on their willingness to provide data with lower privacy protections can ever be “fair”. It seems like these schemes will always pay less to marginalized communities who may be more wary of participating and hence have a higher cost for participating. \n2. Payment schemes like this bias the population whose data is collected. For example in Section 5.2, there are regimes where users with higher c (cost for participating) do not participate. If privacy preferences are correlated with data values, then this will create bias in the result. For example, entire populations may be missing from the sample because their data was too expensive to buy, exacerbating fairness concerns in the trained model.\n3. In all the examples given in the paper, in order to find an optimal fair payment scheme, the aggregator needed to know the privacy preferences of each data subject. If this is correlated with the data, then I think this choice needs justification. I would like to see either a motivating example where privacy preferences being public can be justified, or some indication of whether this assumption could be avoided in the future.\n\nThis work is first step towards defining fairness in this setting so I don’t expect it to have answers to all these concerns. I don’t know of a solution that takes these factors into account and appropriately incentivizes participation. However, since the key contribution of this work is to set up a fairness definition, I would like to see these points discussed and more motivation for the choices that the authors have made.\n\nI thought that the notation could be confused. Examples:\n-  it was sometimes not obvious when something was a function that varied with data subjects or was a fixed universal constant (e.g. s and t in section 4 are originally defined in a way that makes this unclear). \n- There is fluctuation in when p, \\bf{p} and \\bf{p}^* are used and I struggled to keep them straight. Why does Theorem 3 a used \\bf{p}^* but b uses just \\bf{p}? Should p be \\bf{p} in eqn 21? \n- \\bf{epsilon} is a vector but is used in inequalities, how is this defined?\n- In Figure 6, the labelling of platform profit by coloring in the region of the graph makes it seem like the profit is related to the area between the curves.\n- It was not clear to me how Figure 7 compared the payments to user 1 and user 2? It just shows user 2’s payment, no?\n\n\nMinor Comments:\n- I would like to see the authors be a bit more careful about what they refer to as “privacy”. For example, in the introduction, the authors describe FL and just sending data to the server as distinct privacy levels. These are certainly not clearly providing different levels of privacy (in fact, we know in some settings that FL does not provide much additional privacy protections). I also think this highlights an interesting question about communicating privacy level choices to users (that is outside the scope of this paper) since FL sounds more private than it is (in my opinion). \n- Typo: page 3 “but only places restriction only on relative”\n- Figure 3, introduce the objective function outside the caption.\n- Typo: Theorem 2 “Then for alpha(epsilon) satisfies”\n- Introduce notation used in eqn 13\n- After eqn 16, make it clear that Proposition 16 is in the appendix. \n- Figure 5b, is there a typo in the labelling of the second and 4th columns?", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Motivating example where privacy preferences can be public, or discussion of potential directions for eliminating this assumption.\n- Discussion of how the correlation between a user's data and their privacy preferences affects the fairness of the payment scheme. In relation to both lower payments for more protective data subjects, and potential bias in the final result.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "i7cJvge7f8", "reviewer": "Reviewer_EKtk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n- The interaction between fairness and privacy here is interesting \n- The design space, which tries to consider the economics of privacy in a more general sense than differential privacy by extending the meaning of $\\varepsilon$ is definitely a nice addition/novelty to the paper. \n\nWeaknesses: \n- A lot of the discussions of/connections with differential privacy are imprecise and/or erroneous. For example, it is known that sending the model directly to the platform without adding noise is not DP for any finite $\\epsilon$. Yet, on page 4, the authors claims their $\\epsilon = 2$ example is consistent to the standard definition of DP given in Definition 1. \n- The related work is missing a lot of references. There has been a lot of work on mechanism design for data acquisition where the motivation is that agents incur privacy costs to release their data, and a lot of work trying to address this adding a differential privacy dimension. The current discussion only has a small subset of these papers. The statement that an economic theory for the value is data is still nascent with cites from 2019 also misses a lot of references in the computer science/EC literature starting 2013-2015. \n- I worry about the novelty of Section 3. Theorems 1 and 2 seem to be standard Shapley value arguments/proofs. \n- I also worry about the novelty of Section 5. The setting here seems very simple with only two possible levels of privacy, when a lot of previous work have considered non-binary and even continuous privacy sensitivities (e.g. Ghosh-Ligett 2013, Hsu et al. 2014, Cummings et al. 2015, Chen et al. 2018, Fallah et al. 2022, Cummings et al. 2023, many of which are not cited). The current paper seems behind the state of the art when it comes to mechanism design with privacy considerations.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the problem of pricing data fairly in data acquisition and federated learning setting where data privacy is a major consideration.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "To see the paper accepted, I would like to see the following:\n1) Completely revamp the discussion of and connection with differential privacy in the paper to fix the issues mentioned above. \n2) Improve the related work to provide a more exhaustive view of the work on data acquisition/mechanism design with privacy costs and/or under differential privacy \n3) Clearly compare the results of this paper, especially Section 5, to previous work.", "broader_impact_concerns": "No broader impact concern; the goal here is privacy + fairness", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KOzQ4YCStJ", "reviewer": "Reviewer_LbcM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Modeling users and federated learning platforms using game theory is logical, and much of the knowledge from game theory can be applied to this type of problem, similar to the work presented.\n\nThe paper chose to frame the issue within the context of a coalition game. The primary coalition concerns the platform's decision on whether or not to join with users; without this, the coalition has no value. It might simplify the problem if rather than the platform acting as a player deciding to join a coalition, this decision became a component of each player's utility, based on the size of the coalitions. For example, they have set requirements on the number of users with specific privacy choices in each coalition.  This would shift the problem to be more like a mechanism design, primarily aiming to design a good payoff mechanism  for users. While this might not significantly alter the results, it could improve the paper's readability.\n\n\nThe paper models the problem at a very abstract level and it is not clear to me if we found any solution with this level of abstraction that would reflect how real world implementations will look like. For example, the current modeling is that users will decide between a few privacy choices and then the platform decides if he wants to join or not. In practice do the users complete information about the platform utility function ? Does it make any difference? \n\n\nThe reward functions in the paper have exponential complexity, making it challenging to see their practicality in scenarios with a large number of users.\n\n\nA minor comment that the paper uses epsilon in different parts of the paper to denote different meanings. In section 2.1 the authors use epsilon as in differential privacy epsilon but then later on they used epsilon to generally define privacy levels. The authors should try to use different notations or at least styles to improve readability.\n\n\nOne general comment: the interesting part of the paper is mechanism design and the game theory part of the work where it would be more appropriate in a game theory related venue.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper models users in a federated learning environment as a coalition game. Where users can choose different privacy levels to share their data and they will get paid based on their choices and the decision of the platform. Essentially if the platform decides to join the coalition then each client will get paid. This will allow platforms to simulate how different payment strategies can affect the decision making of the users and if that payment strategy will result in a stable coalition. Finally the authors evaluated a few simple settings to show effectiveness of their approach.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "- Make it clear why this problem is coalition game rather than any other mechanism\n- Complexity analysis of the solutions\n- Motivations on practicality of the work", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "URBDVAAGA8", "reviewer": "Reviewer_u8qr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* The problem is timely and interesting.\n* The mean estimation example can demonstrate how the utility changes when users have different privacy requirements.\n* Defining utility functions based on the Shapley value is meaningful.\n\nWeaknesses:\n\n* Presentation needs to be largely improved. Some terminology is not consistent with prior literature, and notations, equations, etc throughout the paper are not self-contained.\n\n-- The definition of \\epsilon-privacy algorithm is irrelevant to the \\epsilon-DP notion in the DP literature. I suggest to name it differently to void confusion.\n\n-- When epsilon=2, do the users send models or data? Regarding this, seems the text in Page 1-3 is inconsistent with Figure 2.\n\n-- The epsilons defined in Def 1-2 is based on DP, which is different from the implications of epsilons in {0,1,2} described before. Also, why do we need coordinate-wise DP (Definition 1)? What is the definition of coordinates? Does epsilon_i correspond to user i or the i-th gradient/model dimension? \n\n-- The sensitivity function is not defined. c_i is the sensitivity of what function defined over user data i? Why is it a function of epsilon_i? In my understanding, the sensitivity defined in privacy literature is not dependent on the privacy parameters, but rather, a property of the function and the data. As a result, I cannot parse the formulation of Eq. (2). When I read towards the very end of the paper, I realized (may be wrong) that c_i may refer to how much a user is sensitive to privacy protection, as opposed to the sensitivity where we usually need to bound to guarantee DP.\n\n-- Is Section 4.1 is plotting Eq (12) or (17), where (12) is the payment function and (17) is the utility function? The first sentence of Section 4.1.1 points out that it plots ‘how much each user’s utility differs from U(ε)/N’; however, the following text (and the y label) seems to infer that the y-axis is the payment each client receives. Eq. (12) is more expensive to compute, but more interesting. \n\n\n* The implications of the presented theorems are limited. Theorem 1 & 2 are listing the standard results of Shapley value. Example 1 gives a concrete example on a toy problem where we can calculate the utility values. What is the insight from this example on the coalition between the platform and all users? The fair payment depends on the (1) Shapley value calculation, and (2) the definition of the utility function. In the mean estimation case, (1) can be expensive and (2) can be defined and estimated in a straightforward way. The paper doesn’t discuss more general cases.\n\n* In Section 5, is the ‘identical statistical marginal distribution’ assumption reasonable? Why is the platform utility function in Eq (19) in this section different from the one discussed in (3)? Additional clarification is needed. Theorem 3 also assumes that all clients share the same privacy parameter c. While Section 5.2 studies the case where users have different privacy tolerance levels, it would be better to provide a similar theorem where each user i has a different c_i.\n\n* The mechanism design part formalizes the optimization problem (which is difficult to solve), characterizes some properties of the solutions under restrictive assumptions, and visualizes the solutions on a mean estimation problem; but doesn’t provide enough insights on meaningful algorithms to find the solution.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the fair payment allocation problem in federated learning based on Shapley values. It builds some game-theoretic framework, defines the utility functions for both the platform (server) and the users, and demonstrates some properties of the framework on a mean estimation problem.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Improve presentation\n\n* Dive deeper into the implications of the theorems.\n\n* Provide a formal theorem with different c_i's.\n\n* Discuss how do solve the fair allocation problem (19).", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a framework based on Shapley value in game theory to understand the incentive structure for users to balance their privacy and utility, where the platform gives incentives to the users to choose to be less private. The framework adopts from Shapley value three axioms (fairness, efficiency, additivity), based on which derives theoretical results that characterize the optimal incentives that a platform should pay users for their data. The rest of the paper is dedicated to further developing these ideas through several examples. 

The paper was reviewed by four expert reviewers on different aspects of the work with expertise ranging from federated learning, mechanism design, privacy, and fairness. The reviewers and authors engaged in a revision/response process and the reviewers have now submitted their recommendations on this paper. Overall, all reviewers and myself have found merit in the paper for publication. However, the reviewers have still identified several points that require another revision. In what follows, I describe the required revisions (based in part on the decision letter of the reviewers that was shared directly with the AE and EICs and in part on my own reading of the paper). The paper is recommended to be accepted subject to the authors incorporating the following revisions in their camera-ready version and providing a point-by-point response.

- The paper as it stands is hard to follow because the examples keep changing throughout the paper, and these examples are abstract at times. I suggest telling the story with a few recurring concrete examples, which also appear in the analyses of the paper. One such example would be mean estimation in federated learning with three levels of privacy. Another such example could be the setup with different users that have different privacy sensitivities, etc.

- The paper lacks a discussion on how to explicitly solve Eq (2) (or  Eq (22)) for the different examples that are proposed. At the very least, I suggest that (once the paper follows a few concrete examples) the authors discuss how to solve the problem for each setting. Also, please give some insight on how solving the problem might be easy/challenging for various types of utility functions, etc. 

- In Eq. (15) what does a_i encode? Please develop some intuition here by solving the problem for various a_i’s and exploring the role of a_i’s in the solution. In Eq. (15), please also change the notation of a_i that clashes with the previously introduced a. 

- Please make it clear how the theoretical results (theorems) are related to the existing literature. Specifically, please make it clear what the novelty of each theorem is with respect to the existing literature on Shapley values. In particular, if the theorem resembles a specific result, it would be best for the reader to be given this information explicitly right after the theorem statement.

- Please share some intuition for the specific type of utility function in (15). Is there an operational meaning for this logarithmic form? Does this have an implication in solving the problem in Eq (2)?

- As it stands, Section 4 ends abruptly. Please further develop the mean estimation example and explore the role of different parameters of the problem so that it is better understood what may incentivize different users to choose the three privacy levels. Please also further develop this example to understand the effect of number of users, the effect of task similarity, the effect of the number of datapoints each user has (which could be captured through the estimation variance of each user), etc. Currently, the choice of users for different privacy levels seems arbitrary. I was hoping to see how the “sensitivity” of the users to privacy leads them to choose different privacy levels. I was hoping to also see how the behavior of other users might affect the behavior of a given user to choose a different privacy level. As it stands, the example falls short to explain the game theoretic aspect of the developments of this paper. It would be best to relate the content of Section 5 back to the examples in Section 4.

- I was curious whether the mean estimation in FL was related to the simple theoretical setting that has been extensively used and analyzed in the FL literature, e.g., in [1-3]. I wonder if you may be able to adapt the privacy framework by incorporating varying levels of differential privacy as distinct sharing tiers in one of your examples.

[1] Li, Tian, et al. "Ditto: Fair and robust federated learning through personalization." International Conference on Machine Learning. PMLR, 2021.

[2] Cho, Yae Jee, et al. "Personalized federated learning for heterogeneous clients with clustered knowledge transfer." arXiv preprint arXiv:2109.08119 (2021).

[3] Aldaghri, Nasser, et al. "Federated learning with heterogeneous differential privacy." arXiv preprint arXiv:2110.15252 (2021).

- Right before (8), there is a reference to Eq. (33). Please make sure that the paper is self-contained for reading purposes.

- Please explain the axioms in words and make sure the reader intuitively understands what they entail and why they are sensible. I suggest giving the axioms one by one followed by a justification for each before moving to the next one.

- The statement regarding computational complexity at the beginning of page 8 seems out of place. Please expand on why that is important and how it is related.

- I was hoping to see an example where the platform is incentivized to pay different users differently because of the way the platform estimates the perceived value of each user’s data. Does such a setting fall within the realm of the proposed framework? If so, please capture it within (a modification to) one of the proposed examples?

- The example in Section 5.1 is quite nice. Please expand the analysis here to further understand the impact of many other parameters of the problem on the design of the mechanism to develop intuition for the reader.

- In the real world, the users are evolving. The privacy sensitivity of an existing user may change over time. Users with other privacy sensitivities might join the system over time, etc. It would be great if the paper can shed light on how to understand evolution of the incentives in such settings. To make the problem more manageable, let’s consider two settings: (a) One user changes their privacy sensitivity, and understand how the solution changes. (b) A new user is introduced into the system and analyze how the mechanism works given the sensitivity level of this user.

- Please clarify the differences between privacy level 2 and 3 first mentioned on Page 1, for example, what types of data statistics the server can query for, in what scenarios the query results will (and will not) allow the server to reconstruct raw data, and how many times the server can make such queries. Please define the exact privacy model somewhere in the paper. It mentions different levels of privacy conceptually throughout the paper, and also defines DP in Definition2; and it is not clear how we should reason about the actual privacy definition (e.g., how does DP fit into part of the story). It is also not clear if level 2 (rho=1) is defined with secure aggregation built in or not. If yes, then need to justify it; if sometimes, then need to define when. 

- Please consider adding a table of notations to make it easy for the reader to find the meaning of different parameters.
Decision: Accept (poster)