Bridging Central and Local Differential Privacy in Data Acquisition Mechanisms
Authors: Alireza Fallah
Ali Makhdoumi
Azarakhsh Malekian
Asuman E. Ozdaglar
Venue: NeurIPS 2022 Accept (2022)
Keywords: Mechanism design
algorithmic game theory
optimal data acquisition
differential privacy

Abstract: We study the design of optimal Bayesian data acquisition mechanisms for a platform interested in estimating the mean of a distribution by collecting data from privacy-conscious users. In our setting, users have heterogeneous sensitivities for two types of privacy losses corresponding to local and central differential privacy measures. The local privacy loss is due to the leakage of a user's information when she shares her data with the platform, and the central privacy loss is due to the released estimate by the platform to the public. The users share their data in exchange for a payment (e.g., through monetary transfers or services) that compensates for their privacy losses. The platform does not know the privacy sensitivity of users and must design a mechanism to solicit their preferences and then deliver both local and central privacy guarantees while minimizing the estimation error plus the expected payment to users. We first establish minimax lower bounds for the estimation error, given a vector of privacy guarantees, and show that a linear estimator is (near) optimal. We then turn to our main goal: designing an optimal data acquisition mechanism. We establish that the design of such mechanisms in a Bayesian setting (where the platform knows the distribution of users' sensitivities and not their realizations) can be cast as a nonconvex optimization problem. Additionally, for the class of linear estimators, we prove that finding the optimal mechanism admits a Polynomial Time Approximation Scheme.

Bridging Central and Local Differential Privacy in Data Acquisition Mechanisms
Alireza Fallah
Ali Makhdoumi
EECS Department
Fuqua School of Business
Massachusetts Institute of Technology afallah@mit.. edu
Duke University
ali m.i.mmauommmi @duke. edu
Azarakhsh Malekian
Asuman Ozdaglar
Rotman School of Management University of Toronto
EECS Department
Massachusetts Institute of Technology asuman@mit t. edu
azarakhsh, mwl.mallaaaaaam anciiotaratat utoronto.com ca.
Abstract
We study the design of optimal Bayesian data acquisition mechanisms for plat- form interested in estimating the mean of distribution by collecting data from privacy-conscious users. In our setting, users have heterogeneous sensitivities for two types of privacy losses corresponding to local and central differential privacy measures. The local privacy loss is due the leakage of user's information when she shares her data with the platform, and the central privacy loss is due to the re- leased estimate by the platform to the public. The users share their data in exchange for payment (c.g., through monetary transfers services) that compensates for their privacy losses. The platform knows the distribution of privacy sensitivities but not their realizations, and must design mechanism to solicit their preferences and then deliver both local and central privacy guarantees while minimizing the estimation error plus the expected payment to users. We first establish minimax lower bounds for the estimation error, given a vector of privacy guarantees, and show that linear estimator is (near) optimal. We then turn to our main goal: designing an optimal data acquisition mechanism. We establish that the design such mechanisms in Bayesian setting (where the platform knows the distribu- tion of users' sensitivities and not their realizations) can be cast as a nonconvex optimization problem. Additionally, for the class of linear estimators, we prove that finding the optimal mechanism admits a Polynomial Time Approximation Scheme.
Introduction
Users' personal data are currently being utilized for personalized advertising, medical trials, targeted advertising, and recommendation systems, among others. The transaction of individual data is set to grow exponentially in the coming years, with widespread applications of artificial intelligence (AI) and machine learning techniques. Even though it is widely accepted that users need to own their data (see, e.g., Posner and Weyl [2019] Kushmaro 102 and WILL.IAM 22199), the impact of different market architectures on the design and operation of data markets are not clear: some users prefer protect their own raw data while others expect companies to protect their data proactively (see, e.g., GDMA 2018)). ). In this paper, we consider the design of data acquisition mechanisms when users have heterogeneous privacy concerns and ask the following question:
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

What is the optimal data acquisition mechanism when users have heterogeneous privacy concerns regarding access to their raw data and the outcome of the platform's 's processing?
We use differential privacy to measure the two types of privacy losses. Informally, an estimator is called differentially private if its distribution over outputs is insensitive to the changes a user's data.
In particular, we consider a platform whose goal is to estimate an underlying parameter of interest who own a noisy version of the underlying
by collecting data from set of users .V = (1, .I,...,? n) parameter. For instance, consider medical trial in which a hospital wants to collect users' data to estimate the efficacy of a drug. Each user has two types of privacy concerns: (i) local privacy concern that captures how much information their shared data reveal about their raw data, and (ii) central privacy concern that captures how much information the platform's output reveal about their raw data. We adopt local and central Rényi differential privacy to measure these two types of privacy losses. The reason for choosing Rényi differential privacy is twofold. First, our framework can cover a wide range of information measures by varying the Rényi divergence parameter. Second, it can be achieved by a Gaussian mechanism, which simplifies our analysis while capturing the main tradeoffs in the design of two-part data acquisition mechanisms.
Before formulating the platform's data acquisition problem, we derive optimal estimators for a given vector of heterogeneous local privacy loss levels. In particular, we establish a minimax lower bound for the estimation error and prove that first privatizing users' data by adding a properly designed Gaussian noise to them and then using a properly designed weighted average of these privatized data points achieves this lower bound. This result motivates us to consider the design of the optimal data acquisition mechanism for the class of linear estimators.
We then turn our mechanism design problem. Each user has heterogeneous preference regarding the importance of the above two privacy concerns. For instance, if a user fully trusts the platform, then the first type of concern lessens, and the main concern would be about the information revealed from the platform's 's estimate. On the other hand, if a user does not trust the platform at all, the first type of concern would be more than the second one. We model such a setting by assuming each user i has a privacy sensitivity Q E [0, 1] that determines the relative weight she puts on the local privacy concern (1 G is the weight she puts on the central privacy concern). The utility of user is the payment she receives from the platform (in exchange for sharing her data), minus times her local privacy loss, and again, minus e2 times her central privacy loss. The platform does not know the value of c; and (knowing its distribution) must design a (Bayesian) data acquisition mechanism to elicit the true privacy sensitivities (that guide the optimal choice of local and central privacy losses delivered to each user) and optimize its objective.
In particular, the platform designs two-part data acquisition mechanism that comprises a payment scheme, a local privacy guarantee, and a central privacy guarantec as a function of the reported privacy sensitivity of users. The platform's goal is minimize the sum of the mean estimation error and the expected total payment to users while satisfying the incentive compatibility and individual rationality constraints. Incentive compatibility ensures that users have no incentive to misreport their privacy sensitivity, and individual rationality ensures that the payment to users (and the delivered privacy guarantees) are such that users are willing to share their data with the platform.
The platform's problem is a functional optimization over three functions of the reported privacy sensitivities: payments, local privacy guarantees, and central privacy guarantees. We first find the payment function in terms of the local and central privacy guarantees by using the incentive compatibility and individual rationality constraints. This reduces the space of the platform's 's decision variables. We then focus on the Gaussian mechanisms and linear estimators (motivated by our minimax optimality result) and show that the platform's problem can be cast as an optimization problem that minimizes a non-convex objective (which depends on the virtual cost of users) for any reported vector of privacy sensitivities. This reformulation significantly reduces the space of decision variables that the platform needs to optimize. However, it still involves solving non-convex optimization problem. We further use the structural properties of this non-convex optimization and use duality theory to develop a polynomial time algorithm to approximate the platform's 's problem. More preeisely, we prove that the design of the optimal two-part data acquisition mechanism admits a Polynomial Time Approximation Scheme (PTAS).

---

The contribution of our work is threefold. First, we develop minimax lower bound when users have heterogeneous local privacy losses and establish that a linear estimator (approximately) achieves this bound. Second, we develop a modeling framework for data acquisition mechanisms when users have heterogeneous concerns for both local and central privacy losses. Third, for any estimator and mechanism to deliver privacy guarantees, we characterize the design of the optimal two-part data acquisition mechanism as the solution to a point-wise optimization problem. Additionally, for the class of Gaussian mechanisms to deliver privacy guarantees and linear estimators, we develop an algorithm to approximately find the optimal data acquisition mechanism (despite the fact that the corresponding optimization is non-convex).
Related literature: Our paper relates to the literature on optimal data acquisition from privacy concerned users. There a large body of work that use differential privacy to measure the privacy loss of users Ghosh and Roth [2011]. Nissim et al. [2012). Nissim et al. [2014). One of the earliest papers in the literature Ghosh and Roth [20T]. which study the design mechanisms for collecting users' data when users incur some privacy cost from sharing their data. More specifically, Ghosh and Roth (201T) consider binary data (bit) with the platform's 's goal being to estimate the sum of user's s data by using a differentially private and dominant strategy truthful mechanism. They study both the case when the user data and privacy parameter are independent (similar to our paper) and when they are correlated. In the independent case, they propose a mechanism that delivers a single privacy level to all users (as opposed to our setting that delivers heterogeneous privacy levels). For the correlated case, they prove an impossibility result for the existence of a truthful and individually rational mechanism.
Several works build on Ghosh and Roth 2011], extending it take it or leave it offers Ligett and Roth [2012), strengthening the impossibility results Nissim et al. [0014) and studying the open question posed by Ghosh and Roth [2011] on whether model with distributional assumption on users' costs and Bayesian mechanism design approach could be used to develop the optimal mechanism for
collecting data with privacy guarantees (see, c.g., Liao et al. [202T) and Fallah et al.] (2022)) ). In
particular, Roth and Schoenebeck [2012). Chen et al. [2018]. and Chen and Zheng (209) tackle this problem by developing a randomized mechanism in which user's data is randomly included in the final estimator where the inclusion probability depends on the reported privacy costs of the users (as opposed to our setting in which the payments and privacy guarantees depend on the reported privacy sensitivity of all users). These papers do not use differential privacy to model privacy costs and instead use a menu of probability-prie
pairs to tune the privacy loss and the payment to each user (see also Pai and Roth [2013) for survey). Similar to the above paper, we consider a setting in which the platform can verify the data of users. For instance, in the context of medical trials, this means that the users decide whether to participate in the medical trial and cannot change the samples they share. A different stream of the literature explores settings in which users can misreport their information Perote and Perote-Penal [2003]. Dekel et al. [2010) Meir et al. 2012 Ghosh al. (2014). Cai et al. 2015), Liu and Chen 2016 2017].
Our paper differs from these works in three main ways. First, we assume prior information on user privacy sensitivities and focus on characterizing the optimal Bayesian incentive compatible mechanism. Second, we model a setting in which users have both local and central privacy concerns and explore the different privacy guarantees of these two types delivered by an optimal mechanism. Third, assume that user data are drawn from the same underlying distribution that allows the platform to put differing weights on the data of users depending on their privacy sensitivity, leading to different privacy levels for participating users.
Finally, our paper relates to the literature on differential privacy. Pioneered by the seminal work of Dwork et al. (2006a]b) b). differential privacy has emerged as a prevalent framework for characterizing the privacy leakage of data oriented algorithms. More specifically, our paper is related to the private mean estimation considered by Duchi et al. [2013]. Barber and Duchi [2014), Karwa and Vadhan [2017), Asoodeh et al. [2021), Kamath et al. [2019 2020), Cummings et al. [2021), and AAcharya et al. 2021]. Additionally, our paper relates to the stream of differential privacy literature that studies
Rényi differential privacy (RDP) introduced by Bun and Steinke (2016) and Mironov] 2017
2 Problem Formulation
We consider a platform interested in estimating a parameter E IR by collecting data of n users, indexed by N = {1. .n). For any i E N, we denote user i's data by X; E X' and we assume X;
3

---

is given by X; = + Z, where Zi, Zn are independent and identically distributed zero-mean random variables with variance VAR. To simplify the exposition, we further assume |Z, < 1/2 for any E WMD (Thoughout, we use lower case letters to denote the realization of random variables. The platform's s goal is to minimize the estimate's error by collecting data from privacy-concerned users. Therefore, the platform needs to incentivize them to share their data.
2.1 Local and central privacy losses
Before formalizing the utilities/objectives of the platform and the users, define the notions of privacy losses that we adopt in this paper. In particular, we consider two different types of privacy losses that users suffer from. The first one is the privacy loss of user when she shares her data (only) with the platform, and the second one is the privacy loss through the released estimate (to the public) by the platform. Depending on how different users trust the platform, they might care differently about these two privacy losses. For instance, if user fully trusts the platform, then her main privacy concern would be the second one, while user who does not trust the platform at all would more concerned with the first one as the public only observes the aggregated estimate, as opposed to the platform which observes each user's (shared) data separately.
We use the differential privacy framework to quantify these privacy losses. Since differential privacy was introduced by Dwork et al., several variants of it have been also proposed. In particular, popular one in the machine learning literature is Rényi differential privacy (RDP), introduced by MMronov [0177] which we also adopt in this paper. Let us first recall the definition of Rényi divergence. Definition 1. Let P and Q be two distributions over R with densities p and q. For any E (1, the Rényi o-divergence between P and Q is denoted by Da (Pl(2) and is given by
p((z) a g(z)dr. (((z))
Da(PIIQ) a- log
For two random variables X and Y, (x(X denotes the a-divergence between their distributions.
We next define two notions of differential privacy, known central and local, to capture the two aforementioned types of privacy losses. Local differential privacy corresponds to the privacy loss of a user when she shares her data with the platform through randomized mapping, known channel.
Definition 2. Let & 2 O and a E (1, oc]. A randomized channel C: X' - IR is locally (e, -r)-éényi (differentially) private if for any x, x' E X,
Da(C(=))((<))) SE.
Central differential privacy corresponds to the other privacy loss mentioned above. It bounds the change in the distribution of the platform's output, i.e., the released estimate, by changing one user's data. We next provide the formal definition.
Definition 3. Let (e:) E R2 and E (1, 20). randomized algorithm A X + R is (e, Rényi (differentially) private for any two datasets Dim, Ti.n E X" that only differ in i-th coordinate (data of user i),
Da(A(zim)llAtt E
The customary approach guarantee RDP is Gaussian mechanism in which a properly tuned zero- mean Gaussian noise is added to fulfill the required condition. The following lemma, adapted from Mironov [2017), allows to characterize the Gaussian noise's variance for privacy loss level.
Lemma 1. For a function f X + IR, we define its sensitivity with respect to i-th coordinate as
L.( : sup (I(())))) (((1,)) for all Tia and 2'. differing only at i-th coordinate).
For any a E (1, oc], A( = (I1m)) + W with W ~ N((002) is ((att(l 20²
. RDP..
For given vector of local privacy losses (e en natural way to privately estimate the mean is by using a linear estimator with Gaussian mechanism which is given by
0 Fn) = Σ w where Σ wi = and a. I. +NO0 a
for all i E W. (1)
2c
i=1

---

=x + 100
2c
Platform
2, =2 1.0
20
Σ wrg,
2,= = xx+ (0
2
Figure 1: The interaction between the users and the platform in the two-part private data acquisition.
Figure depicts this estimator. In particular, using Lemma the local privacy delivered to user i E E is et and the central privacy delivered to user i E N e = w Σÿ= w / In the next section, we focus on linear estimators in designing the optimal private data acquisition mechanism. We motivate such specification by showing that, for given vector of local privacy losses (e(")== a linear estimator is optimal with respect to mean square error. To formalize this statement, we first need to define the minimax estimation error as the notion of optimality. Let P be class of distributions over X. For any P P, we denote its mean by ((P). (e(")) "===--ooatl RDP estimator can be cast as (x;
where Cz(-) is the randomized channel corresponding to user i. Let > -locally RDP estimators. The minimax estimation error
(( ( be the class of such (e, (4) )==1)
C(P, (e m )=))==
sup E " (.1C,,,,0((("))
inf
(2)
where the expectation is taken over both randomness of data and estimator (including private channels). In other words, the optimal estimator is the that has the lowest worst case error among all estimators that satisfy the privacy requirements. We next state the optimality result.
Theorem 1. Assume a 2 2 and e!!) < for all i. Let P1 be the family of distributions over [- 1 21 and C,, ... Cn be independent channels. Then, there exists a universal constant such that
C(P, 2, (e.")) 2 emin
1
(1) 1).
Ei=
Furthermore, there exists linear estimator with Gaussian mechanism such that
E (L(((())))))(((((X)))))))))))))) -(P))
Σ
We prove the lower bound by using the Le Cam's method Yu finding lower bounds hypothesis testing problem and requires bounding the total variation distance between the estimates when the input data points change. We then find it more convenient to bound the total variation in terms of Hellinger distance and use a series of inequalities to bound it.
1997 that reduces the problem of
2.2 Data acquisition mechanism with two-part privacy guarantees
We next describe the utility functions of the users and the platform and then formulate the platform's optimal data acquisition mechanism. As described earlier, each user suffers from two privacy losses when sharing her data. The first one is a central privacy loss because of the leakage of her information through the platform's output. The second is local privacy loss because of the leakage of her information through the raw data that she shares with the platform. Each user has heterogeneous privacy sensitivity for these two types of privacy losses. To model such heterogeneity, for each e N, we let E [0, 1] be her relative local privacy sensitivity, representing the relative weight that user i assigns the (per unit cost of) local privacy loss. We also let c, be her relative central privacy sensitivity, representing the relative weight that user i assigns to the (per unit cost of) central privacy loss. Therefore, e; z implies that user suffers a higher loss of privacy by sharing her raw data with the platform (local privacy loss) compared to her loss from the platform's output
This assumption does not have any fundamental impact on the results and is made to simplify the notations.
5

---

(central privacy loss). Differently, Q; = 0 implies that the user suffers a smaller loss of privacy by sharing her raw data with the platform compared her loss from the platform's 's output. In what follows, we use the term privacy sensitivity instead of relative local privacy sensitivity.
For each i N, the privacy sensitivity c, is independently drawn from a publicly known distribution whose support is [0, 1] with cumulative distribution and probability density functions F.(-) and f((-). We also let user is her private information, i.e., the platform does not know it. This is because individuals have different views regarding how trustworthy the platform is in protecting their raw data.
(cI, (C1,...,Cy, Cx.) be the vector of privacy sensitivities. The privacy sensitivity of each
The platform's 's objective is to design a mechanism to collect users' data by paying them to compensate for their privacy losses without knowing the privacy sensitivity of users. To introduce the platform's 's' objective formally, we adopt the formalism of Bayesian mechanism design pioneered by Myerson [98T]_ More specifically, the platform designs and announces a payment function, local privacy loss function, and a central privacy loss function that are mappings from the reported privacy sensitivities of users. The users then report their privacy sensitivities (which may or may not be truthful). Based on the payment function, the platform compensates the users (the compensation could be monetary or some free discounted service provided the user). Based on the local and central privacy functions, the platform designs randomized channels and randomized estimation algorithms that deliver the guaranteed local and central privacy losses while minimizing the sum of the mean squared error and the total expected payments. Given this interaction, we next formally introduce a data acquisition mechanism with two-part data privacy guarantees.
Definition 4 (two-part private data acquisition mechanism). We call the tuple (0, e())) two-part private data acquisition mechanism where
1. For all i WWW e R + + is a function that maps the vector of privacy sensitivities c to a local privacy loss for user i, e (c). with e e.) = (e!" ())).
2. For all i E EN, e, :T + R4 is a function that maps the vector of privacy sensitivities c a central privacy loss for user i, e(' (c), with (.) (e( (+))
3. 0: Xx x RT x RY + Ris (c()) a) Rényi differentially private estimator that maps acquired locally (e. (c), a)-Rén differentially private data of user i for i E > to an estimate 0(x, e (C(cc, ec) (c)..
4. For all i E. 4 R + R4 is function that maps the vector of privacy sensitivities to a payment for user i, tc(c), with t(.) = (+))-
Notice that have not specified the estimator and the mechanisms that delivers (local and central) Rényi differential privacy. In the rest of this subsection, we introduce the utilities and the platform's 's problem for general estimators and mechanisms deliver differential privacy. Later, we focus on linear estimator and Gaussian mechanisms and explicitly solve the platform's 's problem.
Each user that participates in a two-part private data acquisition mechanism suffers from both the local and central privacy losses and need to be compensated by the platform. In particular, the utility of user from participation when her privacy sensitivity is c, and she reports of is given by
ui(e c... el c),, 0) E._, [t 4)) (e - (1 c.) (c cMI,
( (c_ 6) is the relative lo- where the term 4(c_,,))) ()) is the payment from the platform, the term og;; cal privacy sensitivity of the user multiplied by her local privacy loss, and the term (1 (1-c)ee (c_ d) is her relative central privacy sensitivity multiplied by her central privacy loss. A user i N that does not participate in the mechanism neither compromises her privacy nor gets a compensation. Therefore, the utility of user who does not participate in the mechanism becomes 0.
The goal of the platform is to minimize the sum of the mean squared error and the overall payment to users. We let y R, represents the relative weight of the mean estimation error and the payments in

---

the platform's 's objective Therefore, the platform's 's objective is
Ee (e) + Σ 4(c)),
where the first term the mean square error of estimator & given reported vector of privacy sensitivity and resulting local and central privacy losses e(I) and e(c), i.e.,
MSE(e(((c) (c), e (c), 0) = [x e _e(o) - -
Also, each summand of the second term is the compensation that the platform gives to user to incentivize her to participate and report her privacy sensitivity truthfully.
In Appendix we prove that, similar the classical mechanism design setting, revelation principle holds. This means that there is no loss of generality in focusing on the class of direct incentive compatible mechanisms, meaning the platform's 's optimization problem be written
min (0.))))))
(c))MSE(e"(c))) (c), 0) +
[x(c]]
(3)
==1
e() t. (c,)), (c. c,,),
(4)
(c). t. 20 for all EN,G.
(5)
where the constraints in (4) represent the incentive compatibility. These constraints guarantee that that each has no incentive misrepresent her privacy sensitivity when others report truthfully
(reporting truthfully is an equilibrium of the game among the users). Also, the constraints in (5)
represent individual rationality, which ensures that each user receives non-negative utility from participating in the platform's 's mechanism and sharing her data.
From the mechanism design problem to an optimization problem
For a given estimator 0, the platform's 's decision comprises the local and central privacy loss functions (.) and (.)) together with the payment functions t(-). We next show that this problem can be equivalently formulated privacy losses (as opposed to functions). In the rest of the paper, we impose the following assumption which is well-known in the mechanism design literature and simplifies the analysis
optimization problem over the vector of local privacy losses and central
Assumption 1. For any user E N, the virtual cost defined as ()((c) c fi(e]
Fi(e) is increasing c,
where f((-) and F:(-) are probability density and cumulative distribution functions of cs respectively.
The above assumption holds for a wide class of distributions such as the ones with log-concave density functions (c.g., uniform).
Theorem 2. Suppose Assumption holds. For given estimator 0 8" x R. x X - R. in the optimal two-part data acquisition mechanism, for given vector of reported privacy sensitivities the local and central privacy losses are the solution of
min
M
(())
(e(c)))) + Σ 6 00 (1-vc(()))
(6)
Proof Sketch of Theorem 2
We introduce the following interim functions
=Ic [t(c,, e-),, (()(c.) Ec_, (E(") (c., c-)), and E (c:) = =c (c,, c-))].
We first establish a payment identity that determines the optimal payment terms of the optimal local and central privacy losses. In particular, by evaluating the first order condition corresponding to the incentive compatibility constraint (4), we establish that this constraint holds and only if
((c)) (. + + (c) - (0) + ci(ef((())))) s( -(0) 1 (c) 9 (z) - (c) (z))dz,
2 Notice that changing parameter 7 enables us to study a wide range of platform's objectives with differing relative weights hetween estimation error and the total payments. Without this assumption, extending the results requires ironing technique of Myerson [98]]
7

---

and (2) -e( is weakly decreasing in We then plug in this payment identity back to the platform's 's objective, use the individual rationality constraint, and rewrite the platform's 's expected utility in terms of the privacy loss functions and the virtual cost of users. This is still functional optimization problem in terms of (.) and (.). However, we establish that, under Assumption we can solve this functional optimization point-wise (i.e., for any given c).
Theorem 2 highlights the tradeoff in the platform's problem: by decreasing the local privacy loss, the second term of the objective decreases (this term corresponds the payment to users) while the first term (i.e,, the mean squared eτror) increases. The role of the central privacy loss is more nuanced, and there are two cases. If the coefficient central privacy loss, the third term of the objective decreases while the first term increases. If the coefficient (((( is negative, increasing the central privacy loss decreases both the third term and the first term. However, we cannot increase the central privacy loss level without limits because the central privacy loss level is always below the local privacy loss level. Therefore, the platform's optimal mechanism should find the "right" balance between these terms.
(cx) non-negative. by decreasing the
4
Optimal mechanism with two-part privacy guarantees for linear estimators
For the rest of the paper, we focus on linear estimators with Gaussian mechanism described in Section The following is a direct corollary of Theorem
2.1
Suppose Assumption 7 holds. For any reported vector of privacy sensitivities c, the optimal local privacy loss levels are El (c) yi and the optimal central privacy loss levels are
Corollary 1.
(c)
w,²
where (wi,.... ...... wx and (vi ....... Vin the optimal solution of
min VAR
w
70
W
(1
vbr(c))
(i(c))y
(7)
w.y
2
Vi
Σド=1 M/
n
s.t. Ws y 2 0, for all i E N and
Σ
wi = 1.
Let us highlight the difference between our characterization and that of classic mechanism design (e.g.. Myerson (181]). In classic mechanism design. the designer's 's problem becomes linear optimization. However, in our setting, the designer's ' problem is a non-linear and non-convex optimization. This makes the problem of finding the optimal two-part data acquisition mechanism challenging. Before addressing this computational challenge, let us revisit the form of the Gaussian mechanism that we have adopted: the platform adds Gaussian noise locally and then outputs a convex combination of the privatized users' data without adding any noise centrally. More specifically, one may guess that the platform may benefit by having central noise added the final output in addition to the local noises. In the following subsection, we establish that there is another Gaussian mechanism for any Gaussian mechanism that only adds local noises and achieves weakly lower cost.
4.1 Optimality of having only local noises in the Gaussian mechanism
The platform has the opportunity of adding Gaussian noise to both the raw data of each user and the final estimator and ex-ante one may guess that it is optimal to use both of these instruments. However, as we establish next, interestingly, in the optimal two-part data acquisition mechanism. it is always optimal to only add noises locally.
For given vector of local privacy losses (e Gaussian mechanism with both local and central noises is of the form
en and central privacy losses (e(²) 1..., (0)
(1)
( Inn)
Σ wpdr + (O, ( where Σ m and à; NO Vi ViE.
23
Proposition the optimal two-part data acquisition mechanism that adopts a Gaussian mecha- nism with both local and central noises, have
8

---

Algorithm 1: Computing the optimal two-part private data acquisition mechanism Input: The vector of privacy sensitivities (ci,...,Cr) for S Grid S).6) do
Let
Vi &1 =
Eusly [5(()) -
14
VVAR (1 (a(c)))/S' Si
23
j=l
2
Σi=1 Sive S-Σ:-1 V Vileete
Let
Let
ws w;((S) + E, Us Vslc))
-n/ossc)), v=(S) w())
P
(e(())))
and OBJ(S) be the objective of Problem evaluated for this solution.
end
Output: (U*) (.(") where (S*) mig (i) (SJ(S).
Proposition 1 has an important implication in terms of the design of data market architecture when users have both central and local privacy costs: optimal add noise locally! Adding a noise centrally to the final estimator has an advantage because the weights in the final estimator give the platform a lever to deliver heterogeneous central privacy guarantees to users. Despite this advantage, we establish that adding noise centrally is never optimal. This is because the platform prefers to add the noise locally to contribute to both central and local privacy guarantees delivered to users.
4.2 Computing the optimal privacy loss function
The implementation of the optimal two-part private data acquisition mechanism requires solving Problem (7). which a non-convex program. However, we use the structure of the problem to develop polynomial time algorithm to solve it approximately. To do so, we first replace Σ w //: by an auxiliary variable S. Next, we consider the corresponding lagrangian problem. Using Kuhun Tucker (KKT) conditions, p, the lagrangian coefficient corresponding to S = Σi= w / y,. Furthermore, we develop upper and lower bounds for S. Finally, we do grid search to find the approximate optimal solution.
establish number of relations between problems' parameters, S, and
Theorem 3.
For any vector of reported privacy sensitivities and O, Algorithm finds local privacy loss levels and the differentially private linear estimator of the two-purt data acquisition mechanism whose cost (i.e., platform's objective) is at most + 8 of the optimal cost in time poly(n, }).
Notice that the approximation factor in Theorem 3 depends on the underlying parameters. Therefore, have Polynomial Time Approximation Scheme (PTAS) for finding the optimal two-part data acquisition mechanism in the class of linear estimators.
In the Appendix, provide case study with two users to illustrate the performance of the optimal two-part data acquisition mechanism in terms of the guaranteed privacy levels and payments as functions of the reported privacy sensitivities.
5 Conclusion
In this paper we develop unified framework to study the design of data acquisition mechanisms when users have both local and central privacy concerns and are heterogeneous in how they value these two privacy concerns. We use Rényi differential privacy to measure the privacy loss of users and first establish a minimax lower bound that motivates us to focus on linear estimators. We then establish a wisnt-wise optimization problem whose solution fully characterizes the optimal data acquisition mechanism that constitute payment scheme to compensate users for their privacy losses, local privacy guarantee, and central privacy guarantee all as function of users' preferences for

---

local and central privacy concerns. We then focus on linear estimators, motivated by our optimality results, and establish that, even though the corresponding optimization problem non-convex, the platform's problem admits Polynomial Time Approximation Scheme. Finally, we focused on data acquisition to estimate mean population. However, our framework more general and allows for considering other (potentially vector) estimates. In particular, our Theorem 2 converts the data acquisition mechanism design problem into a (potentially) non-convex optimization problem.
Acknowledgement
Alireza Fallah acknowledges support from the Apple Scholars in Ai/ML PhD fellowship.
References
Acharya, Z. Sun, and H. Zhang. Differentially private assouad, fano, and le cam. Algorithmic Learning Theory, pages 48-78. PMLR, 2021.
Asoodeh, M. Aliakbarpour, and F. Calmon. Local differential privacy equivalent to contraction of an f-divergence. In 2021 IEEE International Symposium on Information Theory (ISIT), pages 545-550, 2021.
R. F. Barber and J. C. Duchi. Privacy and statistical risk: Formalisms and minimax bounds. arXiv preprint 1rXiv:1412.4451, 2014.
M. Bun and T. Steinke, Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635-658. Springer, 2016.
Y. Cai, C. Daskalakis, and C. Papadimitriou. Optimum statistical estimation with strategic data sources. In Conference on Learning Theory, pages 280-296. PMLR, 2015.
Y. Chen and S. Zheng. Prior-free data acquisition for accurate statistical estimation. In Proceedings of the 2019 ACM Conference Economics and Computation, pages 659-677, 2019.
Y. Chen, N. Immorlica, B. Lucier, V. Syrgkanis, and J. Ziani. Optimal data acquisition for statistical estimation. In Proceedings of the 2018 ACM Conference Economics and Computation, pages 27-44, 2018.
R. Cummings, V. Feldman, A. McMillan, and K. Talwar. Mean estimation with user-level privacy under data heterogeneity. NeurIPS 2021 Workshop Privacy Machine Learning, 2021.
O. Dekel, F. Fischer, and A. D. Procaccia. Incentive compatible regression learning. Journal of Computer and System Sciences, 7688)775-7777 2010.
J. C. Duchi, M. I. Jordan, and M. J. Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 429-438. IEEE, 2013.
C. Dwork. K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 486-503. Springer, 2006a.
C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006h.
A. Fallah, A. Makhdoumi, A. Malekian, and A. Ozdaglar. Optimal and differentially private data acquisition: Central and local mechanisms. arXiv preprint arXiv:2201.0::: 103968, 2022.
GDMA. Global data privacy: What the consumer really thinks. 2018. URL https: dma
org uk/ http/////oa//mmmm/////////////// http:22211122211111----1----- aloballddtta dataall-dd-----iiaaaaa privacc-report-....... - final-2 2_ 5b0522b11396e pdf
A. Ghosh and A. Roth. Selling privacy at auction. Proceedings of the 12th ACM conference on Electronic commerce, pages 199-208, 2011.
10

---

A. Ghosh, K. Ligett, A. Roth, and G. Schoenebeck. Buying private data without verification. In Proceedings of the fifteenth ACM conference on Economics and computation, pages 931-948. 2014.
G. Kamath, Li, Singhal, and Ullman. Privately learning high-dimensional distributions. In Conference on Learning Theory, pages 1853-1902. PMLR, 2019.
G. Kamath, V. Singhal, and J. Ullman. Private mean estimation heavy-tailed distributions. In Conference on Learning Theory, pages 2204-2235 PMLR, 2020.
V. Karwa and Vadhan. Finite sample differentially private confidence intervals. arXiv preprint arXiv: 1.10000 2017.
Kushmaro. Why data privacy human right (and what businesses should do about it). 2021. URL https://wwe forbes. com tes/ http:////wt.....att...tt..tt/tt/ why pay-dataa-rivacc--- a- a-human right- and what www.bussiinsss...e should-do -oo--es--se--------------------- about- it/ Psh=c2a9684ec3aa
G. Liao, Y. Su, Ziani, A. Wierman, and Huang. The privacy paradox and optimal bias variance trade-offs in data acquisition. In Proceedings of the 22nd ACM Conference Economics and Computation, pages 689-689, 2021.
K. Ligett and A. Roth. Take it leave it: Running survey when privacy comes at cost. In International workshop on internet and network economics, pages 378-391. Springer, 2012.
Y. Liu and Y. Chen. Learning to incentivize: Eliciting effort via output agreement. arXiv preprint 1rXiv:1604.04922 2016.
Y. Liu and Y. Chen. Sequential peer prediction: Learning to elicit effort using posted prices. In Thirty- AAAI Conference on Artificial Intelligence, 2017. 2017.
R. Meir, A. D. Procaccia, and J. S. Rosenschein. Algorithms for strategyproof classification. Artificial Intelligence, 186: 12-11223,6,, 2012.
I. Mironov. Rényi differential privacy. In IEEE 30th computer security foundations symposium (CSF), pages 263-275. IEEE, 2017.
R. B. Myerson. Optimal auction design. Mathematics of operations research, 6(1):58-73, 1981.
K. Nissim, C. Orlandi, and R. Smorodinsky. Privacy-aware mechanism design. In Proceedings of the 13th ACM Conference Electronic Commerce, pages 774-789, 2012.
K. Nissim, S. Vadhan, and D. Xiao. Redrawing the boundaries on purchasing data from privacy- sensitive individuals. In Proceedings of the 5th conference Innovations in theoretical computer science, pages 41 411-422 12-2 2014.
M. M. Pai and A. Roth. Privacy and mechanism design. ACM SIGecom Exchanges, 12(1):8-29, 2013.
J. Perote and J. Perote-Pena. The impossibility of strategy-proof clustering. Economics Bulletin, (23):1-9, 2003.
E. A. Posner and F. G. Weyl. Radical Markets. Princeton University Press, 2019.
A. Roth and G. Schoenebeck. Conducting truthful surveys, cheaply. In Proceedings of the 13th ACM Conference Electronic Commerce, pages 826 843, 2012.
LAL..LAM. We need to own our data as a human right-and be compensated 2019. URI. htttps:/wwet www.omist..c.................... cwm/ htwp:/owws....oooopaooeoottetea/
for it.
we ne-need- to- own- our tar--dat--e as- a human right and be compenstedd--oo--iiiii
B. Yu. Assouad, fano, and le cam. In Festschrifi for Lucien Le Cam, pages 423-435. Springer, 1997.

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Please check the conclusion
section.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Please check Sections 2.3, and 4.
(b) Did you include complete proofs of all theoretical results? [Yes] Please check appendix
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "niM1sBmyVGl", "reviewer": "Reviewer_Buzh", "summary": "This paper studies the mean estimation problem in the case that the users have heterogeneous sensitivities for local and central differential privacy. By sharing their data, the users receive payments, but lose both local and central privacy. A user’s goal is to maximize her total utility, while the platform’s goal is to minimize the sum of the mean squared error plus the total payments to all users with two constraints: incentive compatibility and individual rationality. The privacy loss is quantified by local Renyi DP and a generalized version of central Renyi DP, in which n different epsilons are given, one for each user. Each user’s “privacy sensitivity” is represented by a scalar $c_i$ in [0,1], which means that the weight of local DP loss for user i is $c_i$, and the weight of central DP loss is (1-$c_i$). The authors analyze the minimax lower bounds for the estimation error and propose a linear estimator that is order optimal. Then, they propose a data acquisition mechanism with the assumption that the server knows the agents’ privacy sensitivity distribution, and has both local and central privacy guarantees, and model it as a nonconvex optimization problem. Finally, they show that there is an approximately optimal polynomial time algorithm for the linear estimators. ", "questions": "* Are there previous publications about users having different sensitivities for local and central DP, or different users having different central DP epsilons?\n* There are some clarification questions about the setting / notations in “Strengths And Weaknesses” - “Quality”.\n* Page 8, Proposition 1, it is claimed that it’s always optimal to add local noise. This is very counterintuitive, because usually local DP is much more expensive than central DP. What if every user only cares about central DP, but not local DP (all $c_i$ are 0). Does the conclusion still hold?\n", "limitations": "I don’t think the setting proposed in this paper is practical. See my comments in “Strengths And Weaknesses” - “Significance”.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Originality: This paper is related to central / local differential privacy and Bayesian data acquisition mechanisms. The authors propose a new privacy model, that each user has a privacy sensitivity, which determines whether they care more about central DP loss or local DP loss. Also, the users are allowed to have different epsilon values in both the local and central model. The problem is modeled by a nonconvex optimization problem, and approximate optimal polynomial time solutions are discussed. Based on the introduction and related work, the setting and solutions are novel. I do wonder if there are previous publications about users having different sensitivities for local and central DP, or different users having different central DP epsilons?\n\n* Quality: The setting / notations are mostly ok. Some clarification questions:\n  * Page 3, line 138, Is each $x_i$ a scalar? Or could it be a vector?\n  * Page 3, line 141, Is $Z_i$ defined?\n  * Page 3, line 142, “minimize the estimate’s error” What kind of estimate do you consider in this paper? Could it be arbitrary? From Page 4, line 173, seems you only consider estimating a scalar from user data?\n  * Page 4, line 184, Is $\\varepsilon_1^{(l)}$ defined before you use it?\n  * Page 6, line 241 and 243, why is $\\varepsilon_i^{(l)}: \\mathcal{X} \\rightarrow \\hat{\\mathcal{X}}$, but $\\varepsilon_i^{(c)}: \\mathbb{R_+^n} \\rightarrow \\mathbb{R_+}$? Shouldn’t both functions have the same input and output value range?\n\n* Clarity: The writing and organization is mostly clear. Some comments:\n  * Page 1, line 9, “The platform does not know the privacy sensitivity of users”. This might be misleading, because you do assume that the platform knows the distribution of users’ sensitivities (as stated in line 16). I suggest making the assumption clear in line 9.\n  * Page 2, line 56, “be the more the second one” -> be more than the second one\n  * Page 2, line 66, “The platform’s problem is to…” I suggest changing “problem” to “goal” or “target”. The same comment for other occurrences of this phrase.\n  * Page 3, line 97, “in this literature” -> in the literature\n  * Page 8, line 295-296, “This problem is still a functional optimization in terms …” -> This is still a functional optimization problem in terms …\n  * Page 9, line 362, “a point-wise optimization problem hose…”, “hose” -> “whose”\n\n* Significance: While the setting this paper proposes is new and kind of interesting, I wonder how practical it is to model privacy in a way that each user only has a “privacy sensitivity” in [0, 1] to determine the weight between central and local DP, and the platform got to determine every user’s epsilon value in both central and local DP. The idea is that a user is fine with arbitrarily large privacy loss, as long as they are paid according to some payment rule, which is hard to justify. If every user can have an upper bound epsilon, then the setting would be more meaningful.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "gShCitoJx0m", "reviewer": "Reviewer_5KYG", "summary": "This paper considers a heterogeneous population of users with respect\n to their privacy preferences. They consider the 'change'\n neighjbourhood for DP, which is natural for local DP. It first shows\n a lower bound on the linear estimation for the Gaussian-mechanism,\n and a matching upper bound.  linear estimator for individuals with\n $\\epsilon_i$ preferences.  In the main paper, however, they consider\n relative privacy sensitivity to local and central mechanisms instead.\n\nThey then cast the case of MSE in parameter estimation, with incentive\ncompatibility and individual rationality constraints.\nIn some sense the result that it's optimal to only add local noise is\nnot extremely surprising, given the results about anonymity and local\nDP.", "questions": "What can you say about generalisation to other estimators or non-MSE loss?\n\nIt is a bit strange that you initially look at the case of heterogenous overall losses, and then only tradeoff between local and central losses. Why is that?\n\nThe obvious question here is elicitation: How can users be sufficiently informed as to be able to truthfully report in the first place? I realise that this is a general question in mechanism design, but it is typically easier to price a tangible item than relative privacy losses...\n", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "It is a well written and interesting combination of a number of areas that have not been studied very much so far, even though the design of optimal mechanisms for privacy is important.\n\n Under the assumption of a monotonic increasing 'virtual cost' (it's ok if you\ndon't explain it, but it is not actually fully defined: what are $f_i,\nF_i$?)\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JeZ2s-ELvnL", "reviewer": "Reviewer_vRJn", "summary": "This paper addresses an important problem in the field that is to eliminate local and central differential privacy (DP) concerns with one unified framework. It also considers the heterogeneous differential privacy where different users have different privacy needs. The approach is relatively simple compared to state-of-the-art solutions. They use Renyi DP and find a minimax lower bound first. Then they establish a point-wise optimization problem to characterize the optimal data acquisition mechanism.", "questions": "As far as I know, local DP is stronger and when it is guaranteed, central DP is also guaranteed. Is that correct?  If that's the case why you add noise twice in the framework? ", "limitations": "Authors discusses the limitations in conclusion section. They mention that it is still an open problem to study the optimality of linear estimators. I don't have any other concern.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: This paper addresses an important problem for real-world applications and I found the simplicity of the approach very practical for those applications. It is well written and theoretically sounds. Although I am not an expert in the field, I found many parts of the paper easy to follow and understand.\n\nWeaknesses: This approach is quite applicable to real-world problems. I'd like to see some empirical evaluation of the proposed approach to understand how useful it could be for real applications. Minor but I've noticed a few typos, e.g. hose in page 9, line 362, We (capital W) in  page 2 line 87.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Dox5V9jpD23", "reviewer": "Reviewer_BCdV", "summary": "The authors study the design of optimal Bayesian data acquisition mechanisms for a platform interested in estimating the mean of distribution by collecting data from privacy-conscious users. The authors assume users have heterogeneous sensitivities for local and central differential privacy measures and the users share their data in exchange for a payment that compensates for their privacy losses. The authors establish minimax lower bounds for the estimation error and show that a linear estimator is (near) optimal. A Bayesian setting is considered to turn the design of an optimal data acquisition mechanism into a nonconvex optimization problem. ", "questions": "1. From my point of view, the assumption that the distribution of users’ sensitivities is known may be a strict condition. Can the authors give some examples to show that the assumption may be satisfied in some cases?\n\n2. I am a little confused about the privacy sensitivities (c_1, …, c_n). The authors mentioned that it should be unknown to the platform, however, in line 256, it is assumed that “the privacy sensitivity is c_i and she reports c’_i”, also, in algorithm 1, the privacy sensitivities are also assumed to be given. Have the sensitivities been reported by the users? If not, how to estimate the privacy sensitivities when optimization?\n\n3. In line 330, a Gaussian mechanism is given. What is the sensitivity L_i for the linear estimation of the sample mean?\n", "limitations": "The authors have adequately addressed the limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The manuscript is well organized and includes enough information needed to support the claims it makes. The proposed method is novel in the sense that the authors consider the heterogeneous sensitivities of users, and use a Bayesian setting to cast the mechanism designing problem as an optimization problem.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept