Mechanism Design for Collaborative Normal Mean Estimation
Authors: Yiding Chen
Jerry Zhu
Kirthevasan Kandasamy
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Mechanism design
statistical minimax estimation
federated learning
TL;DR: We study collaborative normal mean estimation with strategic agents.

Abstract: We study collaborative normal mean estimation, where $m$ strategic agents collect i.i.d samples from a normal distribution $\mathcal{N}(\mu, \sigma^2)$ at a cost. They all wish to estimate the mean $\mu$. By sharing data with each other, agents can obtain better estimates while keeping the cost of data collection small. To facilitate this collaboration, we wish to design mechanisms that encourage agents to collect a sufficient amount of data and share it truthfully, so that they are all better off than working alone. In naive mechanisms, such as simply pooling and sharing all the data, an individual agent might find it beneficial to under-collect and/or fabricate data, which can lead to poor social outcomes. We design a novel mechanism that overcomes these challenges via two key techniques: first, when sharing the others' data with an agent, the mechanism corrupts this dataset proportional to how much the data reported by the agent differs from the others; second, we design minimax optimal estimators for the corrupted dataset. Our mechanism, which is Nash incentive compatible and individually rational, achieves a social penalty (sum of all agents' estimation errors and data collection costs) that is at most a factor 2 of the global minimum. When applied to high dimensional (non-Gaussian) distributions with bounded variance, this mechanism retains these three properties, but with slightly weaker results. Finally, in two special cases where we restrict the strategy space of the agents, we design mechanisms that essentially achieve the global minimum.

Mechanism Design for Collaborative Normal Mean Estimation
Yiding Chen
Xiaojin Zhu UW-Madison jerryzhudcs wisc.
Kirthevasan Kandasamy UW-Madison kandasamy@cs. wisc. edu
UW-Madison ychen695@wisc.edu
Abstract
We study collaborative normal mean estimation, where m strategic agents collect i.idd samples from a normal distribution o²) at cost. They all wish to estimate the mean μ.. By sharing data with each other, agents can obtain better estimates while keeping the cost of data collection small. To facilitate this collabo- ration, we wish to design mechanisms that encourage agents to collect sufficient amount of data and share it truthfully, so that they are all better off than working alone. In naive mechanisms, such as simply pooling and sharing all the data, an in- dividual agent might find it beneficial to under-collect and/or fabricate data, which can lead to poor social outcomes. We design a novel mechanism that overcomes these challenges via two key techniques: first, when sharing the others' data with an agent, the mechanism corrupts this dataset proportional to how much the data reported by the agent differs from the others; second, we design minimax optimal estimators for the corrupted dataset. Our mechanism, which is Nash incentive compatible and individually rational, achieves social penalty (sum of all agents' estimation errors and data collection costs) that is at most a factor 2 of the global minimum. When applied to high dimensional mnon-Gaussian distributions with bounded variance, this mechanism retains these three properties, but with slightly weaker results. Finally, in two special cases where restrict the strategy space of the agents, we design mechanisms that essentially achieve the global minimum.
Introduction
With the rise in popularity of machine learning, data is becoming an increasingly valuable resource for businesses, scientific organizations, and government institutions. However, data collection is often costly. For instance, to collect data, businesses may need to carry out market research, scientists may need conduct experiments, and govemment institutions may need to perform surveys on public services. However, once data has been generated, it can be freely replicated and used by many organizations [20]. Hence, instead simply collecting and learning from their own data, by sharing data with each other, organizations can mutually reduce their own data collection costs and improve the utility they derive from data [21]. In fact, there are already several platforms to facilitate data sharing among businesses [1, 40], scientific organizations [2, 3], and public institutions [16, 34].
However, simply pooling everyone's 's data and sharing with each other can lead free-riding [23, 35]. For instance, if an agent (e.g an organization) sees that other agents are already contributing large amount of data, then, the cost she incurs to collect her own dataset may not offset the marginal improvement in her own learned model due to diminishing returns of increasing dataset sizes (we describe this rigorously in $2). Hence, while she benefits from others' data, she has no incentive to collect and contribute data to the pool. A seemingly simple fix to this free-riding problem is to only return the datasets of the others if an agent submits large enough dataset herself. However, this can be easily manipulated by strategic agent who submits a large fabricated (fake) dataset without incurring any cost, receives the others' data, and then discards her fabricated dataset when learning. While the agent has benefited by this bad behavior, other agents who may use this fabricated dataset
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

are worse off. Moreover, a naive test by the mechanism to check if the agent has fabricated data can be sidestepped by agents who collect only small dataset and fabricate a larger dataset using this small dataset (e.g by fitting a model to the small dataset and then sampling from this fitted model).
In this work, we study these challenges in data sharing in of the most foundational statistical problems, normal mean estimation, where the goal is to estimate the mean of normal distribution N(u, o²) with known variance o². We wish to design mechanisms for data sharing that satisfy the three fundamental desiderata of mechanism design; Nash incentive compatibility (NIC); agents have incentive to collect sufficiently large amount of data and share it truthfully provided that all other agents are doing so; individual rationality (IR): agents are better off participating in the mechanism than working on their own; and efficiency: the mechanism leads to outcomes with small estimation error and data collection costs for all agents.
Contributions: (i) In $2, we formalize collaborative normal mean estimation in the presence of strategic agents. (ūi) In $3, we design an NIC and IR mechanism for this problem to prevent free-riding and data fabrication and show that its social penalty, i. sum of all agents' estimation errors and data collection costs, is at most twice that of the global minimum. fiii) In Appendix E, we study the same mechanism in high dimensional settings and relax the Gaussian assumption to distributions with bounded variance. We show that the mechanism retains its properties, with only a slight weakening of the NIC and efficiency guarantees. (iv) In $4, we consider two special cases where we impose natural restrictions on the agents' strategy space. We show that it is possible to design mechanisms which essentially achieve the global minimum social penalty in both settings. Next, we will summarize our primary mechanism and the associated theorem in $3.
1.1 Summary of main results
We assume that all agents have a fixed cost for collecting one sample, and define an agent's penalty (negative utility) as the sum of her estimation error and the cost she incurred to collect data. To make the problem well-defined, for the estimation error, we find it necessary to consider the maximum risk, i. maximum expected error over all μ E R. A mechanism asks agents collect data, and then shares the data among the agents in an appropriate manner to achieve the three desiderata. An agent's strategy space consists of three components: how much data she wishes to collect, what she chooses to submit after collecting the data, and how she estimates the mcan μ using the dataset she collected, the dataset she submitted, and the information she received from the mechanism.
Formalism:
Mechanism and theoretical result: In our mechanism, which we call C3D (Cross-Check and Corrupt based on Difference), each agent i collects dataset X, and submits possibly fabricated altered version Y; to the mechanism. The mechanism then determines agent i's allocation in the following manner. It pools the data from the other agents and splits them into two subsets Z,, Z4. Then, Z, is returned as is, while Z is corrupted by adding noise that is proportional to the difference between Y; and Zz. If an agent collects less or fabricates, she risks looking different to the others, and will receive a dataset Z of poorer quality. We show that this mechanism has Nash equilibrium where all agents collect sufficiently large amount of data, submit it truthfully, and use a carefully weighted average of the three datasets X,, Z,, and Z as their estimate for p. The weighting uses some additional side information that the mechanism provides to each agent. Below, we state an informal version of the main theoretical result of this paper, which summarizes the properties of our mechanism.
Theorem I (informal): The above mechanism is Nash incentive compatible, individually rational, and achieves a social penalty that is al most twice the globally minimum social penally.
Corruption is the first of two ingredients to achieving NIC. The second is the design of the weighted average estimator which is (minimax) optimal after corruption. To illustrate why this is important, say that the mechanism had assumed that the agents will use any other sub-optimal estimator (c.g simple average). Then it will need to lower the amount of corruption to ensure IR and efficiency. However, a strategic agent will realize that she can achieve a lower maximum risk with better estimator (instead of collecting more data herself and/or receiving less corrupt data from the mechanism). She can leverage this insight to collect less data and lower her overall penalty.
Proof techniques: The most challenging part of our analysis is to show NIC, First, to show minimax optimality of our estimator, we construct a sequence of normal priors for y and show that the minimum Bayes' risk converges to the maximum risk of the weighted average estimator. However, when compared to typical minimax proofs, we face more significant challenges. The first of these
2

---

is that the combined dataset X2 U Z; U Z; is neither independent nor identically distributed as the corruption data-dependent. The second that the agent's submission Y, also determines the degree of corruption, so we cannot look at the estimator in isolation when computing the minimum Bayes' risk; we should also consider the space of functions an agent may use to determine Y, from X;- The third is that the expressions for the minimum Bayes' risk do not have closed form solutions and require non-trivial algebraic manipulations. To complete the NIC proof, we show that due to the carefully chosen amount of corruption, the agent should collect sufficient amount of data to avoid excessive corruption, but not too much so as to increase her data collection costs.
1.2 Related Work
Mechanism design is one of the core areas of research in game theory [13, 18, 36). Our work here is more related to mechanism design without payments, which has seen applications in fair division [31], matching markets [32], and kidney exchange [33] to name a few. There a long history of work in the intersection of machine learning and mechanism design, although the overwhelming majority apply learning techniques when there is incomplete information about the mechanism or agent preferences, (e.g [6, 8, 22, 28, 30)). On the flip side, some work have designed data marketplaces, where customers may purchase data from contributors [4, 5, 19, 38J. These differ from our focus where we wish to incentivize agents to collaborate without payments.
Due to the popularity of shared data platforms [1. 2. 16, 34] and federated learning [21], there has been a recent interest in designing mechanisms for data sharing. Sim et al. [35] and Xu et al. [39] study fairness in collaborative data sharing, where the goal to reward agents according to the amount of data they contribute. However, their mechanisms do not apply when strategic agents may try to manipulate mechanism. Blum et al. [9] and Karimireddy et al. [23] study collaboration in federated learning. However, the strategy space of an agent is restricted to how much data they collect and their mechanism rewards each agent according to the quantity of the data she submitted. The above four works recognize that free-riding can be detrimental to data sharing, but assume that agents will not fabricate data. As discussed above, this assumption is not true, agents can easily manipulate such mechanisms. Fraboni et al. [17] and Lin et al. [25] study federated learning settings where free-riders may send in fabricated gradients without incurring the computational cost of computing the gradients. However, their focus is designing gradient descent algorithms that are robust to such attacks and not on incentivizing agents to perform the gradient computations. Some work have designed mechanisms for federated learning so to elicit private information (such as data collection costs), but their focus is not on preventing free-riding or fabrication [15, 26]. Miller et al. [29] uses scoring systems to develop mechanisms that prevent signal fabrication. However, the agents in their settings can only choose to report either their true signal or something else but can not freely choose how much data to collect. Cai al. [11] study mechanism design where learner incentivizes agents to collect data via payments. Their mechanism, which also cross-checks the data submitted by the agents, has connections our setting in $4.2 where we consider a restricted strategy space for the agents.
Our approach of using corruption to engender good behaviour draws inspiration from the robust estimation literature, which design estimators that are robust to data from malicious agents [12, 14, 27]. However, to the best of our knowledge, the specific form of corruption and the subsequent design of the minimax optimal estimator are new in this work, and require novel analysis techniques.
2 Problem Setup
We will now formally define our problem. We have m agents, who are each able to collect i.i.d samples from a normal distribution N N(H,a²) where 8² is known. They wish to estimate the mean μ of this distribution. To collect one sample, the agent has to incur cost c. We will assume that o². c, and m are public information. However, μ E R is unknown, and no agent has auxiliary information, such as a prior, about μ.. An agent wishes to minimize her estimation error, while simultaneously keeping the cost of data collection low. While an agent may collect data on her own to manage this trade-off, by sharing data with other agents, she can reduce costs while simultaneously improving her estimate. We wish to design mechanisms to facilitate such sharing of data.
3

---

Mechanism: A mechanism receives a dataset from each agent, and in turn returns an allocation A each agent. An agent will use her allocation to estimate j.. This allocation could be, for instance, a larger dataset obtained with other agents' datasets. The mechanism designer is free to choose a space of allocations to achieve the desired goals. Formally, we define a mechanism as a tuple M = (A. b) where A denotes the space of allocations, and b is procedure to map the datasets collected from the m agents to m allocations. Denoting the universal set by U, we write the space of mechanisms M as M = (M- = (A. b): A U, b: (Un20 R" + AT).
(1)
As is customary, we will assume that the mechanism designer will publish the space of allocations A and the mapping b (the procedure used obtain the allocations) ahead of time, that agents can determine their strategies. However, specific values computed/realized during the execution of the mechanism are not revealed, unless the mechanism chooses to do so via the allocation A₁.
Agents' strategy space: Once the mechanism is published, the agent will choose strategy. In our setting, this will be the tuple (n:, fs. h4), which determines how much data she wishes to collect, what she chooses to submit, and how she wishes to estimate the mean μr. First, the agent samples n; points to collect her initial dataset X, = { [==. where Ti.j ~ N (Js, a²), incurring en, cost. She then submits Y, = b = fx(),) to the mechanism. Here fü is a function which maps the collected dataset to possibly fabricated or falsified dataset of potentially different size. In particular, this fabrication can depend on the data she has collected. For instance, the agent could collect only a small dataset, fit a Gaussian, and then sample from it.
Finally, the mechanism returns the agent's allocation A,, and the agent computes an estimate (X,, Y., A.) for μ using her initial dataset X,, the dataset she submitted Y,, and the allocation she received A, We include Y, as part of the estimate since an agent's 's submission may affect the allocation she receives. Consequently, agents could try to elicit additional information about via a carefully chosen Y, We can write the strategy space of an agent as S N x F H. where is the space of functions mapping the dataset collected to the dataset submitted, and H. is the space of all estimators using all the information she has. We have:
F == {f
Un2o R" + Un2o
=- {h: Un R x Unzo R" x R (2)
One element of interest in F is the identity which maps a dataset to itself. A mechanism designer would like agent to use fa I, i.e to submit the data that she collected is, so that other agents can benefit from her data.
Going forward, when } E STM denotes the strategies of all agents, we will use s-, = {s; hiti to denote the strategies of all agents except i. Without loss of generality, we will assume that agent strategies are deterministic. If they are stochastic, our results will carry through for every realization of any external source of randomness that the agent uses to determine (n Jt,
The agent's penalty P: (i.e negative utility) is the sum of her squared estimation error and the cost en, incurred to collect her dataset X; of n, points. The agent's 'ss penalty depends on the mechanism M and the strategies s = {sy} of all the agents. Making this explicit, pt is defined as:
Agent penalty:
Ps M. s) = sup F. (X, Y, A,) n1)
+ CT
(3)
MER
The term inside the expectation is the squared difference between the agent's 's estimate and the true mean (conditioned on the true mean n)) The expectation with respect to the randomness of all agents' data and possibly any randomness in the mechanism. We consider the maximun risk, i.e supremum over j E R. since the true mean μ is unknown to the agent a priori, and their strategy should yield good estimates, and hence small penalty, over all possible values μ. To illustrate this further, note that when the value of true mean ja is yí, the optimal strategy for an agent will always be to not collect any data and choose the estimator hu(.:...) strategy can be meaningfully realized by an agent only if she knew that μ = p² a priori which renders
...) jí' leading to 0 penalty. However, this
the problem meaningless' Considering the maximum risk accounts for the fact that μ is unknown and makes the problem well-defined.
1 'This is akin to the reason why it is customary study the maximum risk in frequentist statistics [24, 37J. An alternative approach to take a Bayesian view, considering a prior on a and using the Bayes' risk E,, (h, Y,, Ax) - م) [+]]] instead of the maximum risk in p:. While we have adopted a frequentist formalism here, our main proof ideas can be ported over to the Bayesian setting as well (See Appendix F for more details)

---

Recommended strategies: In addition to publishing the mechanism, the mechanism designer will recommend strategies { E S for the agents so as to incentivize collaboration and induce optimal social outcomes.
Desiderata: We can now define the three desiderata for a mechanism:
1. Nash Incentive compatibility (NIC): mechanism M = (A, b) is said to be NIC at the recom- mended strategy profile s* if, for each agent i, and for every other alternative strategy S for that agent, we have p.( (M,, , s*) Σ (M, (8,, s s",)). That is, s* is a Nash equilibrium so no agent has incentive to deviate if all other agents are following s*
2. Individual rationality (IR): We say that mechanism M is IR at s* if no agent suffers from a higher penalty by participating in the mechanism than the lowest possible penalty she could achieve on her own when all other agents are following s* If an agent does not participate, she does not submit nor receive any data from the mechanism; she will simply choose how much data to collect and design the best possible estimator. Formally, say that mechanism M is IR if the following is true for each agent é:
inf sup E LHER
Ps Pr(M,
- [1 + en2y
(4)
MIEN
3. Efficiency: The social penalty P(M,s) of a mechanism M when agents follow strategies s, is the sum of agent penalties (defined below). We define PR(M, (, s*) to be the ratio between the social penalty of mechanism at the recommended strategies s and the lowest possible social penalty among all possible mechanisms and strategies (without NIC or IR constraints). We have:
P(M,s*) inf
s(
Σ (c(M [m(m)
PR(M,s))
(5)
P(M', ,8)
M'EM,sES"
Note that PR 2 1. We say that a mechanism efficient if PR(M,s*) = 1 and that it is approximately efficient if PR(M, s*) is bounded by some constant that does not depend on m. If 8* is a Nash equilibrium, then PR(M, 8*) can be viewed as an upper bound on the price of stability [7].
For what follows, we will discuss optimal strategies for agents working on her own and present a simple mechanism which minimizes the social penalty, but has poor Nash equilibrium.
Optimal strategies for an agent working on her own: Recall that, given n samples {=:}]_ from (H, o²), the sample mean minimax optimal estimator [24]: i. among all possible estimators the sample mean minimizes the maximum risk suPnER [[ - (ff==)/ Ø, )² [4] (note that the agent only has the dataset she collected). Moreover, its mean squared error is o² /n for all μ R. Hence, an agent acting on her own will choose the sample mean and collect n. = a vē samples so as to minimize their penalty; as long as the amount of data is less than a VC. agent has incentive to collect more data since the cost of collecting one more point is offset by the marginal decrease in estimation error. This can be seen via the following simple calculation:
o22 + cns) = 20
inf (sup (1,((X.,0000) - 11)² [ + en:) min n:ER
A Pmin
(6)
R.ER
Let JR Vo denote the lowest achievable penalty by an agent working on her own. If all m agents work independently, then the total social penalty is mp 2amm/c. Next, we will look at simple mechanism and an associated set of strategies which achieve the global minimum penalty. This will show that it is possible for all agents to achieve significantly lower penalty via collaboration.
A globally optimal mechanism without strategic considerations: The following simple mecha- nism Mp pools all the data from the other agents and gives it back to an agent. Precisely, it chooses the space of allocation A = Un2o RR" to be datasets of arbitrary length, and sets agent i's allocation U j Y, The recommended strategies gooel {(n f000l hr asks each agent
be A,
to collect nopoo = a/ Vem points?, submit it as is foool = I, and use the sample mean of all points
To avoid rounding effects, henceforth will treat a /em, and a/ve ć integers.
5

---

Algorithm McR
1:
Mechanism designer publishes:
2:
The allocation space A Un2o R
Un2o I x RR,, and the procedure in lines 6-15.
3: Each agent i:
4:
See (8) for recommended strategies. Sample n, points X; [ )= and submit Y, fx;))) to the mechanism.
Choose strategy 8; = (m,, h1)))-
5:
6: Mechanism:
7:
For each agent i E [m]]
# can be done simulannously for all agents
8:
Y- < Uff$ Y,
9:
If' m S 4:
# Simply pool and return all of the other agents' data agent i. A - (Y- Ø, 0). Return A, to agent i.
10:
11:
Else:
12:
2, - sample min 0/ /cm] points in Y-; without replacement.
13:
n/ x- a² [ Σ yvv y- 1 ΣzEz,
# See (7) for a.
14:
7 {= 62,1; for all = Y-i\Z where 62 (O(0,
15:
A, + (Z,, Z, n²). Return A, to agent
16:
Each agent i:
17:
Compute estimate h, (X,, Y,,
# See (8) for recommended estimator.
as her estimate (X, X,, A.) X.UAA. Exex,UA, 2. It is straightforward show that this minimizes the social penalty all agents follow s After each agent has collected their datasets {Xi)i, the social penalty is minimized if all agents have access to each other's datasets and they all use a minimax optimal estimator: this justifies using Mpoc with /! and setting h2 to be the
sample mean. The following simple calculation justifies the choice of En 2001
m inf Σ sup (ha(X A.) - -1)² 1 + cn. +en)) 8ES
((supB
E. + Σ nz = 20 20/mmm.. mc.
mo²
min {n
i=1
However, g8002 is not a Nash equilibrium of this mechanism, as an agent will find beneficial to free-ride. If all other agents are submitting o //mmm points, by collecting no points, an agent's is penalty o o/me/
1). as she does not incur any data collection cost. This strictly smaller than 20 /c/e when m 2 3. In fact, it not hard to show that Mςoc1 at a Nash equilibrium only when the total amount of data is o/ /c: for additional points, the marginal reduction the estimation error for individual agent does not offset her data collection costs. The social penalty at these equilibria o /c(m + which is significantly larger than the global minimum when there are many agents.
A seemingly simple way to fix this mechanism is to only return the datasets of the other agents if an agent submits at least a/ /cm points. However, as we will see in $4.1, such mechanism can also be manipulated by an agent who submits a fabricated dataset of a /cmm points without actually collecting any data and incurring any cost and then discarding the fabricated dataset when estimating. Any naive test check for the quality of the data can also be sidestepped by agents who sample only a few points, and use that to fabricate a larger dataset (e.g by sampling a large number points from Gaussian fitted to the small sample). Next, we will present our mechanism for this problem which satisfies all three desiderata.
Method and Results
We have outlined our mechanism Mon- and its interaction with the agents in Algorithm 1 in the natural order of events. We will first describe it procedurally, and then motivate our design choices. Our mechanism uses the following allocation space, A Un IR" Un2o R R,. An allocation
A, = (Z,, Zg, n/?) E A consists of an uncorrupted dataset Z, a corrupted dataset Z/, and the variance 7/ of the noise added to Z for corruption. Once the mechanism and the allocation space are published, agent i chooses her strategy = (M;; fi, h₂). She collects a dataset X, = {xi 1= where rigj ~ NN o²), and submits Y; f((X)) the mechanism.
Our mechanism determines agent i's allocation as follows. Let Y-+ be the union of all datasets submitted by the other agents. If there are at most four agents, we simply return all of the other

---

agents" data without corruption by setting A, + first chooses a random subset of size min([Y-il. a/ /em) from Y-;: denote this Z, In line 13, the mechanism individually adds Gaussian noise to the remaining points Y-i 7z to obtain Z (line 14). The variance of of the noise depends on the difference between the sample means of the subset Z and the agent's submission Y, It is modulated by a value a, which is a function of m, and o². Precisely, a is the smallest number larger than va(em)-1/ which satisfies G(a) = 0, where:
If there are more agents, the mechanism
G(v))
2
4c va(m/e)
4(mm + 1)
a²
VZn exp
sym/c Sa?
Erfe
(7)
a/vem
2v2a
Finally, the mechanism returns the allocation A, = (Z,, Zí, n2) to agent and the agent estimates ja.
Recommended strategies: The recommended strategy s; : hi)) for agent is given in (8). The agent should collect n a/ (m) samples if there are at most four agents, and n = a/ /em samples otherwise. She should submit without fabrication or alteration f; I, and then use weighted average of the datasets (X;, Zi, Z to estimate μ. The weighting is proportional to the inverse variance of the data. For X, and Z, this is simply o², but for Zí. the variance is o² + nf. since the mechanism adds Gaussian noise with variance 17. We have:
if m < 4
mye Vem
==
m 4
1: Yi, (Zi, ()) / EmEx, u + 024% Euez; u
(8)
X + 024n [27
Design choices: Next, we will describe our design choices and highlight some key challenges. When m & 4, it is straightforward to show that the mechanism satisfies all our desired properties (see beginning of $3.1), so we will focus on the case m 4. First, recall that the mechanism needs to incentivize agents to collect a sufficient amount of samples. However, simply counting the number of samples can be easily manipulated by an agent who simply submits a fabricated dataset of a large number of points. Instead, Algorithm 1 attempts to infer the quality of the data submitted by the agents using how well an agent's 's submission Y; approximates μ.. Ideally, we would set the variance vi of this corruption to be proportional to the difference (TĀ. Epev, V - 14)², so that the more data she submits, the less the variance of Z/, which in turn yields a more accurate estimate for μ.. However, since is unknown, we use a subset Z: obtained from other agents' data as a proxy for μ. and set 7i proportional to (प7) Σver,
[2 Σxez, 2)² If all agents are following s*. then |Y] = |z,| /cm = nı; it is sufficient to use only nł points for validating Y; since both [V. Evey; and 2. Σxez, Z will have the same order of eтror in approximating μr.
The second main challenge is the design of the recommended estimator h;. In $3.1 we show how splitting Y- into a clean and corrupted parts Z,, Z allows us to design minimax optimal estimator. A minimax optimal estimator is crucial to achieving NIC. To explain this, say that the mechanism assumes that agents will use sub-optimal estimator, e.g sample mean of X, U Z, U Z/. Then, to account for the larger estimation error, it will need to choose a lower level of corruption of to minímize the social penalty. However, a smart agent will realize that she can achieve a lower maximum risk by using better estimator, such as the weighted average, instead of collecting more data in order to reduce the amount of corruption used by the mechanism. She can leverage this insight to collect less data and reduce her overall penalty.
This concludes the description of our mechanism. The following theorem, which is the main theoretical result of this paper, states that Maw achieves the three desiderata outlined in $2.
Let m > 1, a be as defined in (7), and st be as defined in (8). Then, the following statements are true about the mechanism Meso in Algorithm 1. (i) The strategy profile s* is a Nash equilibrium. (ii) The mechanism is individually rational at s*. (ii) The mechanism is upproximately efficient, with PR(Mes;: 8*) 2
Theorem 1.
The mechanism NIC as, provided that others are following sf, there is no reason for any one agent to deviate. Moreover, we achieve low social penalty at s;. Other than s*, there is also a set of similar Nash equilibria with the same social penalty: the agents can each add a same constant to the data points they collect and subtract the same value from the final estimate. Before we proceed,
7

---

the expression for a in (7) warrants explanation. If we treat a is a variable, we find that different choices of a can lead other Nash equilibria with corresponding bounds on PR. This specific choice of a leads to a Nash equilibrium where agents collect a //v //mmm points, and small bound on PR. Throughout this manuscript, we will treat a as the specific value obtained by solving (7), and not as a variable.
High dimensional Gau-Gausiian distributions: In Appendix E, we study Mex when applied to d d-dimensional distributions. In Theorem 7, we show that under bounded variance assumptions, s* is an 5m -pproximmtt Nash equilibrium and that PR(Mess, s*) S + Em where Em E (1/mm.
3.1 Proof sketch of Theorem 1
When m I First, consider the (easy) case m S 4. At s;, the total amount of data collected is a/ o/ve (see n in (8)), and as there is no corrupted dataset, hद simply reduces to the sample mean of X,YY,,. The mechanism is IR since an agent's penalty will be /ve[[+ pul (6). It is approximately efficient since the social penalty is v 1) which is at most twice the global minimum 20 /mc when m S 4. Finally, NIC is guaranteed by the same argument used in (6); as long as the total amount of data is less than a /C. the cost of collecting one more point is offset by the marginal decrease in the estimation error; hence, the agent is incentivized to collect more data. Moreover, as A, does not depend ft under these conditions, there is incentive to fabricate or falsify data.
which is smaller than
When > 4: We will divide this proof into four parts. We first show that G(a)) = 0 in line (6) has solution larger than vn (a(c)) This will also be useful when analyzing the efficiency.
1. Equation (7) has a solution. We derive asymptotic expansion of Erfo(-) using integration by 8/ /m)) For m large enough such that the residual in the asymptotic expansion is negligible, we show Omm (Vn,, n n1 + log m/ /m) via an identical technique.
parts analyze the solution (7). When 2 show that G( G mz/ ((
By continuity of G. there exists Om E (Vnt, (1 (1 mm)) s.t. G(um)
The strategies s in (8) is Nash equilibrium: We show this via the following two steps. First (2.1), We show that fixing any ni, the maximum risk and thus the penalty is minimized when agent i submits the raw data and uses the weighted average as specified in (8), i. for all n4.
Pi (Mass ((ns fi, (T), s)))) S p: (MMes, ((rs, fú, h.), si)), V(n,, h4) ENx H.
(9)
Second (2.2), we show that p3 is minimized when agent collects nę samples under (fi ht), i.e.
Ps(Mazn; ((nt, ft, (T), S PrMMeso ((n,, ff, fT, (t),
Vn,NN.
(10)
2.1: Proof of (9). As the data collection cost does not change for fixed n;, is sufficient show that (ft kt) minimizes the maximum risk. Our proof is inspired by the following well-known recipe for proving minimax optimality of estimator [24]: design sequence of priors {Ae)e, compute the minimum Bayes' risk {Re Je for any estimator, and then show that R& converges to the maximum risk of the proposed estimator as l oc.
To apply this recipe, we use a sequence of normal priors Ae = NV E for μ. Howeiver, before proceed, need to handle two issues. The first of these concerns the posterior for μ when conditioned on (X,, Z, Z().. Since the corruption terms c,,s added to Z depend on X, and Z,, this dataset is not independent. Moreover, as the variance vf the difference berween two normal random variables, Z is not normal. Despite these, is normal. The second challenge is that the submission f. also affects the estimation error as determines the amount of noise v/" We handle this by viewing F x H as rich class of estimators and derive the optimal Bayes' estimator (f, h.ee) F x H under the prior Aç- We then show that the minimum Bayes' risk converges to the maximum risk when using (f: h²))
are able to show that the posterior pu((X,, Z,, Z,)
8

---

Next, under the prior Ae = NN f), we can minimize the Bayes' risk with respect to h2 H by setting n e to be the posterior mean. Then, the minimum Bayes' risk Re can be written as,
Re inf E fEF
[/] 0² +
a
a²
[X]
Σ VEY.
V
1 2.
1, + 0²
|
1 P
ZEZ
inequality [10], we can show that the above quantity is minimized when S.. is chosen be shrunk version of the agent's initial
Note that Y; = J((X;) depends on fi. Via the
dataset X,, ie (X.) {(1 ou++o2/10 (()x(())) I, Vx E X.). This gives us an expression for the minimum Bayes' risk Re under prior Aç. To conclude the proof, we note that the minimum Bayes' risk under any prior is lower bound on the maximum risk, and show that Re approaches the maximum risk of (fr ht) from below. Hence, (ft ( is minimax optimal for any n4. (Above, it is In the Appendix, we also find that h. + h.
worth noting that f.t f I as l
2.2: Proof of (10), We can now write (MsM... ((ng, fr M),s" st,)) = R. + en,, where Ro is the maximum risk of (f7, hī) (and equivalently, the limit of the minimum Bayes' risk):
Re := 1 ( 2)n
(im--2)n(( (o² a (o2 0² /
(n4 + +2)
The term inside the expectation convex n, for each fixed æ. As expectation preserves convexity, we can conclude that pN is a convex function of ny. The choice of a in (7) ensures that the derivative at n² which implies that n² is a minimum of this function.
3. Meso is individually rational at s": This is direct consequence of step 2 as we show that an agent 'working on her own' is a valid strategy in Mow-
4. McD is approximately efficient at s*: By observing that the global minimum penalty is 20 /em, we use a series of nontrivial algebraic manipulations to show PR(Mes0, s*) 10n² 10n2/n/-1
(m+1)a=2(mm27) + +1) As > Vn,, some simple algebra leads to PR(Mexo 5*) < 2.
4 Special Cases: Restricting the Agents' Strategy Space
In this section, we study two special cases motivated by some natural use cases, where we restrict the agents' strategy space. In addition to providing better guarantees on the efficiency, this will also help us better illustrate the challenges in our original setting.
4.1 Agents cannot fabricate or falsify data
First, we study a setting where agents are not allowed to fabricate data or falsify data. Specifically, in (2), F is restricted to functions which map dataset to any subset. This is applicable when there are regulations preventing such behavior (e.g government institutions, hospitals)
Mechanism: The discussion the end of $2 motivates the following modification to the pooling mechanism. We set the allocation space to be A = Un R", ie the space of all datasets. If an agent i submits at least a// cm points, then give her all the other agents' datasets, i. A; = Yj otherwise, set A; Ø. The recommended strategy s (m ft h of each agent is to collect a //mem points, submit it as is fi = I, and then use the sample mean of Z; U A; to estimate μ. The theorem below, whose proof is straightforward, states the main properties of this mechanism.
Theorem 2.
The following statements about the mechanism and strategy profile s* in the paragraph above are true when F is restricted to functions which map dataset to any subset: (i) s* is a Nash equilibrium. (ii) The mechanism is individually rational at s" (ii)) At s*, the mechanism is efficient.
not hard to see that this mechanism can be easily manipulated by the agent there are no restrictions on F. As the mechanism only checks for the amount of data submitted, the agent can submit a fabricated dataset of a /em points, and then discard this dataset when computing the estimate, which results in detrimental free-riding.

---

4.2
Agents accept an estimated value from the mechanism
Our next setting is motivated by use cases where the mechanism may directly deploy the estimated value for μ in some downstream application for the agent, i.e the agents are forced to use this value. This is motivated by federated learning, where agents collect and send data to server (mechanism), which deploys a model (estimate) directly on the agent's 's device [9, 23]. This requires modifying the agent's 's strategy space to S N x F. Now, agent can only choose (n,, fi), how much data she wishes to collect, and how to fabricate or falsify the dataset. A mechanism is defined as a procedure b: (Un20 R²" + RR, which maps m datasets to m estimated mean values.
Algorithm 3 (see Appendix D) outlines a family of mechanisms parametrized by E for this setting. As we will see shortly, with parameter e, the mechanism can achieve PR of (1++). This mechanism computes agent i's estimate for μ as follows. First, let Y-, be the union of all datasets submitted by the other agents. Similar to Algorithm I, the algorithm individually adds Gaussian to each Y-, to obtain Z, (line 10). Unlike before, this noise is added the entire dataset and the variance ny of this noise depends on the difference between the sample means of the agent's 's submission Y; and all of the other agents' submissions Y-,. It also depends on two e-dependent parameters defined in line Finally, the mechanism deploys the sample mean of Y; U Z; as the estimate for The recommended strategies s = (n; f;') for the agents is simply collect nł a/ a/ven /cm points and submit it as is fi I. The following theorem states the main properties of the mechanism.
Theorem 3. Let 0. The following statements about Algorithm 3 and the strategy profile s* given in the paragraph above are true: (i) s* is a Nash equilibrium. (ii) The mechanism is individually rational at s*. -iii) At s*, the mechanism is approximately efficient with PR(M, s*) S 1
The above theorem states that it is possible obtain social penalty that is arbitrarily close the global minimum under the given restriction of the strategy space. However, this mechanism is not NIC if agents allowed to design their own estimator. For instance, if the mechanism returns = (line 10), then using a weighted average of the data in X; and Z, yields lower estimation error than simple average used by the mechanism (see Appendix D). An agent can leverage this insight to collect and submit less data and obtain a lower overall penalty at the expense of other agents. Cai al. [11] study a setting where agents are incentivized to collect data and submit truthfully via payments. Interestingly, their corruption method can be viewed as special case of Algorithm 3 with k = and only achieves 1.5x factor of the global minimum social penalty. Moreover, when applied to the more general strategy space, it shares the same shortcomings as the mechanism in Theorem 3.
5 Conclusion
We studied collaborative normal mean estimation the presence of strategic agents. Naive mecha- nisms which only look at the quantity of the dataset submitted, can be manipulated by agents who under-collect and/or fabricate data, leaving all agents worse off. To address this issue, when sharing the others' data with agent, mechanism Mcn corrupts this dataset proportional to how much the data reported by the agent differs from the other agents. We design minimax optimal estimators for this corrupted dataset achieve socially desirable Nash equilibrium.
Future directions: We believe that designing mechanisms for other collaborative learning settings may require relaxing the exact NIC guarantees to make the analysis tractable. For many learning problems, difficult to design exactly optimal estimators, and it is common to settle for rate- optimal (i.e up to constants) estimators [24]. For instance, even simply relaxing to high dimensional distributions with bounded variance, Mes can only provide an approximate NIC guarantee.
Acknowledgment
This project is supported in part by NSF grants 1545481, 1704117, 1836978, 2023239, 2041428, 2202457, ARO MURI 2011112110317, and AF CoE 119550-18-1-0166.
References
[1] Ads Data Hub. https://developers. wow.ollopppr..ggggeee.oooooooooe wwwggl..oom//eee.eeooooooooooo.o cessed: 2022-05-10.
Ac-
10

---

[2] PubChem. https://pubblti ncbi nlm. nih. wwo..ni......o. gov/. Accessed: 2022-05-10.
[3] Data Coordinating Center Burton Robert 67 Jensen Mark A 53 Kahn Ari 53 Pihl Todd 53 Pot David 53 Wan Yunhu 53 and Tissue Source Site Levine Douglas A 68. The cancer genome atlas pan-cancer analysis project. Nature genetics, 45(10): ((10)):113-11200 2013.
[4] Anish Agarwal, Munther Dahleh, and Tuhin Sarkar. A marketplace for data: An algorithmic solution. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 701-726, 2019.
[5] Anish Agarwal, Munther Dahleh, Thibaut Horel, and Maryann Rui. Towards data auctions with externalities. arXiv preprint arXiv:2003.0833 2020.
[6] Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Learning Prices for Repeated Auctions with Strategic Buyers. In Advances in Neural Information Processing Systems, pages 1 1169-1177, 2013.
[7] Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Éva Tardos, Tom Wexler, and Tim Roughgarden. The price of stability for network design with fair cost allocation. SIAM Journal on Computing, 3804))1602-1163, 2008.
[8] Susan Athey and Hya Segal. An Efficient Dynamic Mechanism. Econometrica, 81(6):2463- 2485, 2013.
[9] Avrim Blum, Nika Haghtalab, Richard Lanas Phillips, and Han Shao. One for one, or all for all: Equilibria and optimality of collaboration in federated learning. In International Conference on Machine Learning, pages 1005-1014. PMLR, 2021.
[10] Almut Burchard. A short course rearrangement inequalities. Lecture notes, IMDEA Winter School, Madrid, 2009.
[11] Yang Cai, Constantinos Daskalakis, and Christos Papadimitriou. Optimum statistical estimation with strategic data sources. In Conference on Learning Theory, pages 280-296. PMLR, 2015.
[12] Yiding Chen, Xuezhou Zhang, Kaiqing Zhang, Mengdi Wang, and Xiaojin Zhu. Byzantine- robust online and offline distributed reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 3230-3269. PMLR, 2023.
[13] Edward Clarke. Multipart Pricing of Public Goods. Public Choice, 1971.
[14] Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions without the computational intractability. In 2016 IEEE 57th Anmual Symposium on Foundations of Computer Science (FOCS).
[15] Ningning Ding, Zhixuan Fang, and Jianwei Huang. Incentive mechanism design for federated learning with multi-dimensional private information. In 2020 18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT), pages 1 8. IEEE, 2020.
[16] Mona Flores, Ittai Dayan, Holger Roth, Aoxiao Zhong, Ahmed Harouni, Amilcare Gentili, Anas Abidin, Andrew Liu, Anthony Costa, Bradford Wood, et al. Federated learning used for predicting outcomes in sars-cov-2 patients. Research Square, 2021.
[17] Yann Fraboni, Richard Vidal, and Marco Lorenzi. Free-rider attacks on model aggregation in federated learning. In International Conference Artificial Intelligence and Statisties, pages 1846-1854. PMLR, 2021.
[18] Theodore Groves. Efficient Collective Choice when Compensation is Possible. The Review of Economic Studies, 1979.
[19] 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 The 22nd International Conference on Artificial Intelligence and Statistics, pages 1167-1176. PMLR, 2019.

---

[20] Charles I Jones and Christopher Tonetti. Nonrivalry and the economics of data. American Economic Review, 110(9))281--58 2020.
[21] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1-2):1-2 1-000 2021.
[22] Sham M Kakade, Ilan Lobel, and Hamid Nazerzadeh. An Optimal Dynamic Mechanism for Multi-armed Bandit Processes. arXiv preprint 1001,40900 2010.
[23] Sai Praneeth Karimireddy, Wenshuo Guo, and Michael Jordan. Mechanisms that incentivize data sharing in federated learning. arXiv preprint arXiv:2207.04557, 040007000557 2022.
[24] Erich I. Lehmann and George Casella. Theory point estimation. Springer Science & Business Media, 2006.
[25] Jierui Lin, Min Du, and Jian Liu. Free-riders in federated learning: Attacks and defenses. arXiv preprint 191.:::911..25550 2019.
[26] Yuan Liu, Mengmeng Tian, Yuxin Chen, Zehui Xiong, Cyril Leung, and Chunyan Miao. A contract theory based incentive mechanism for federated learning. In Federated and Transfer Learning, pages 1 117-137. Springer, 2022.
[27] Gabor Lugosi and Shahar Mendelson. Robust multivariate mean estimation: the optimality of trimmed mean. 2021.
[28] Yishay Mansour, Alcksandrs Slivkins, and Vasilis Syrgkanis. Bayesian compatil Bandit Exploration. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 565-582, 2015.
[29] Nolan Miller, Paul Resnick, and Richard Zeckhauser. Eliciting informative feedback: The peer-prediction method. Management Science, 5 5199::135-11373 2005.
[30] Hamid Nazerzadeh, Amin Saberi, and Rakesh Vohra. Dynamic Cost-per-action Mechanisms and Applications to Online Advertising. In Proceedings of the 17th International Conference on World Wide Web, pages 179-188, 2008.
[31] Ariel D Procaccia. Cake Cutting: Not Child's Play. Communications of the ACM, 56(7): 78-87, 2013.
[32] Alvin E Roth. On the Allocation of Residents Rural Hospitals: A General Property of Two- sided Matching Markets. Econometrica: Journal of the Econometric Sociery, pages 425-427, 1986.
[33] Alvin Roth, Tayfun Sönmez, and M Utku Ünver. Kidney Exchange. The Quarterly journal of economics, 119(2):457-48 488, 2004.
[34] Micah Sheller, G Anthony Reina, Brandon Edwards, Jason Martin, and Spyridon Bakas. Multi-institutionn deep learning modeling without sharing patient data: A feasibility study on brain tumor segmentation. In Brainlesion: Glioma, Multiple Sclerosis, Stroke and Traumatic Brain Injuries: 4th International Workshop, BrainLes 2018, Held in Conjunction with MICCAI 2018, Granada, Spain, September 16, 2018, Revised Selected Papers, Part I 4, pages 92-104. Springer, 2019.
[35] Rachael Hwee Ling Sim, Yehong Zhang, Mun Choon Chan, and Bryan Kian Hsiang Low. Collaborative machine learning with incentive-aware model rewards. In International conference on machine learning, pages 8927-8936. PMLR, 2020.
[36] William Vickrey. Counterspeculation, Auctions, and Competitive Sealed Tenders. The Journal of Finance, 1961.
[37] Abraham Wald. Contributions to the theory of statistical estimation and testing hypotheses. The Annals of Mathematical Statistics, 10(4):299-326, 1939.
12

---

[38] Tianhao Wang, Johannes Rausch, Ce Zhang, Ruoxi Jia, and Dawn Song, A principled approach data valuation for federated learning. Federated Learning: Privacy and Incentive, pages 153-167, 2020.
[39] Xinyi Xu, Lingjuan Lyu, Xingjun Ma, Chenglin Miao, Chuan Sheng Foo, and Bryan Kian Hsiang Low. Gradient driven rewards to guarantee faireess in collaborative machine learning. Advances in Neural Information Processing Systems, 34:16104-16117 2021.
[40] Wenting Zheng, Raluca Ada Popa, Joseph E Gonzalez, and lon Stoica. Helen: Maliciously secure coopetitive learning for linear models, In 2079 IEEE symposium on security and privacy (SP), pages 724-738. IEEE, 2019.
13

---

A Proof of Theorem 1
In this section, we prove Theorem This section is organized follows. First, in $A.1, we consider the case where m < 4. In the remainder of this section, we will assume m 2 5. First, in $A.2, we will show that (7) can be solved for a and state some properties about the solution. Then, in $A.3, will prove the Nash incentive compatibility result, in $A.4 we will prove individual rationality, and we will prove the result on efficiency.
$A.5,
A.1
When m
First, consider the (easy) case m S 4. s;, the total amount of data collected is a/ / as each agent will be collecting n myF (see (8)). As there is no corrupted dataset, hद simply reduces to the sample mean of U_YY_, The individual rationality property follows from the following simple calculation:
P.MMon: x*) (1 Voa < 2 IR
Pmin
Similarly, the bound on the ratio between the penalties can also be obtained via the following calculation:
PR (11+H) < <vm 20
Finally, to show NIC, consider agent and assume that all other agents have followed the rec- ommended strategies, i. collected a (m). Then, the agent will have an uncorrupted dataset Y-; Uj Xj of ni, = (m 1)o/ (m/ points with no corruption. Regardless of what she chooses to submit, the best estimator she could use with the union of this dataset Y-i and the data she collects X; and will be the sample mean as is minimax optimal. The number of points that minimizes her penalty is.
argmin 24
( (sup E (.. 11)2 -1) [n]
cns)
argmin n.ER
(_o²
o² my n';
+ oni)
mv
Finally, as A; does not depend on fi under these conditions, there is no incentive to fabricate or falsify data, i.e choosing anything other than f* I does not lower her utility.
In the remainder of this section, will study the harder case, m 2 4.
A.2 Existence of solution to (7) and some of its properties
In this section, show that G( ///2
(em)r/7 0 and G((1+ Cm 2/2
0, where C. 20
(em)r77
when m < 20 and Cm 5 when 20. This means equation G(a) 0 has solution in g//2
[emja77 (1 + C. 1/2
[cm))14
First, in Lemma 12, derive asymptotic expansion of the Gaussian complementary error function, and construct lower and upper bounds for G(a)) that are easier to work with. We have restated these lower (Erfe,,n) and upper (Erfcup) bounds below.
exp( x2
exp( x2)
3 3expl-
ErfcuB(x) = V
+
(11)
2x
5x
1 cxp( xx))
exp(-2 -x2)
ErfeLB (z)
(12)
Vi
2x
We can now use this to derive the following lower (GLB) and upper (GUB) bounds on G. Here, we have used the fact that 4(m + avm/c - > 0 when a 2 (a/ /em)
a²
1/2 We have:
GLB(a) = m - 20/ 22/v/mm Vcm cm
2
4a
V/(m//c1/44
-(4(m +
a²
a (oym/o mmcc
\/((m/c)1/4)
-1]
-1
v 2T V2Teexp exp
ErfcuB
0 /m/c
8a?
2/2x
14

---

10a
((1 Cm/mm) vn")
10a
m=
10-2
10-4
m= m-5
100
200
300
400
500
Figure 1: Plot for G (1
Cuu
1//2
See G_ 10_emmppooee plot. py. The discontinuity m 20 is due
m
(cm))77
to the different values for Cm when m S 20 and when m > 20.
4a²
4a Vo(m/cc114
Gun(a) = - 20/ /erv/en
/em
-(41m mmmc
a²
σ @Vmcc
s/cc
(o(m/c)3/4
+
2T V
exp
ErfeLE
8
2/2a
By first, substituting a/ //vem for a in the expressions for GUB and ErfCUB, and then via sequence of algebraic manipulations, we can verify that
o 1/2
1/2
I GUB
(cm)
(em)
4(m-4) 4)
- (1)(
1/2
2
1/2
8
3/2
m-2
Vem
V2
4
+ 1)
-1)
Vam
vo(w m 1/1
m cm
(o(=)
1/4
3/2
3/1
128
(m 2/m3/2 < 0.
Next, we will show that G( [5, 500],
C. g//
> 0 by studying the lower bound GLB. For
[em))z/4
verify individually that G (1 + Cm 0//2
(am)i/a
O (See Figure 1). For 500,
we have:
Cm
1/2
= -G =c((1
5
a 1/2
2 GLB ((++)
1/2
1 +
(cm) 1/4
(cm) 1/4
(cm)
m
m
1 1 +1) (m-4)
1/2
4
5 + 1)
2
Vem
(m(m)
m 1/4
1/2
3/2
4 (5 + 1)² (m + 1)
2v2 (5
1)
8
(5 + +1)²
V2
-1)
m
Vem
m
Vom
Vom
vō( m) 1/4
3/2
3/4
96 + 1)
Vem
/5/2 m
5/1
64(m= + 5)3 (m 191m 5 1566m 3920m3 + 2100m + 19500m + 15000)
(m
21/2
When m > 500.
m 6
191m 5 1566m 3920m3 mm 191m² 1566m 3920)
15

---

(m200 + + 100)m² 191m² - 1566m 3920)
>m (200m² + 10 2.5 10? 191m 1566m
-3920) > 0.
Combining the results from the two previous displays, we have, G(11 completes the proof for this section.
Cm 01/2 m [em)1/8
which
A.3 Algorithm is Nash incentive compatible
In this section, will prove the following lemma which states that st, defined in (8) Nash equilibrium Mcss-
Lemma (NIC). The recommended strategies {(nt St, hg)bs i as defined in (8) in mechanism Mew (Algorithm 1) satisfies:
(MMMu s*) S P:MMew (st, s²))
for all E [m]] and 8; FN H.
The Proof of Lemma 4 relies on the following two lemmas:
Lemma 5 (Optimal Estimation and Submission). For all E [m] and (m,, h.) EN x H.H. (MMo, ((14, fi.
S (:Mas ((1s, fi, hz),
See the Proof of Lemma in $A.3.1
Lemma 6 (Optimal Sample Size). For all [m] and n, N. (MMcn ((1) fr ("), S (MMo ((r4, fo ht),
See the Proof of Lemma in $A.3.2
Proof of Lemma 4. By Lemma 5 and 6, have, for all [m]] and s (n4, Se, fe, E Ps (Maa 8*) Pe( (Ma ((n), f7, MT), st,)) I PMMMa ((14, fi, h7), st;)) S (Mss, ((ns, fú, h.). = p:pPpMaMM. (Mas, s7,))
A.3.1 Proof of Lemma 5
In this section, will prove Lemma 5, which, intuitively states that, regardless of the amount of data collected, agent i should submit the data as is (f: = 1) and use the weighted average estimator in (8) estimate μ. We will do so the following three step procedure, inspired by well-known techniques for proving minimax optimality of estimators (e.g see Theorem 1.12, Chapter of Lehmann and Casella [24]).
First, we construct sequence of prior distributions {Achez for and calculate the sequence of Bayesian risks under the prior distributions:
E (1;((,, f(Xx), A,) 11) ul]: 1 1.
Rs
inf J.E.A,
T AA
2. Then, will show that limg- R₁ = sup,, E. [(h; (X (X, (X;),, Av) 11)2 u1.
3. Finally, as the Bayesian risk is lower bound on maximum risk, we will conclude that (ft h is minimax optimal.
Without loss of generality, we focus only on the deterministic f; and h₃- If either of them are stochastic, we can condition the external source of randomness and treat them as deterministic functions. Our proof holds for any realization of this external source of randomness, and hence it will hold in expectation well. Similarly, Z; is randomly chosen in Algorithm 1, In the following, condition on this randomness and the entire proof will carry through.
Note that Y: f((x)). We will use both of them interchangeably in the subsequent proof.
16

---

Step (Bounding the Bayes' risk under the sequence of priors): We will use a sequence of normal priors A, N00 (2) for all f To bound the Bayes' risk under these priors, we will first note that for fixed Si E F.F
Blp ~ N(), Ve E X;UZ;
(13)
zlu, m. ~ NN,, +
Vx E Z
(14)
Here, recall that uz is a function of Y, and Z, Because both Y; = (X4) and nī are deterministic
functions of x;; Z; when ft is fixed, the posterior distribution for μ conditioned on (X,, Yú, A,) can be calculated follows:
X, Y,, A.) = p(u|X; X, Y,, Z4 72) = p(ux,, Z,
α p(1, X3, Zi, 7.) = p(Z X, Zz 1)D( Zelu))(u)) p(Z Zi,
112
Σ (r - 11) zEZi
Σ
(x (m-m)² 1)2
x exp
2( + +1/)
exp
20
cxp
202
zEX;UZ;
1
Z
X
Zz
1
Σ CEEZ
EmEx II
x exp
+ (2
12
exp
2
0²
+ 1/
2
02 + 17
exp
3 11 - 2 ue
x exp
(μ
pe)
2
0i
20
where
Excy x d'+1p + Excxuzz x
H4
2 +
|x,1+12,1 + 12
and o0
2
|x.|+1211
(15)
+
+
0²
o²
We can therefore conclude that (despite the non i.. nature of the data), the posterior for μ is Gaussian with mean and variance as shown above. We have:
pu) X, Yi, ~ N(ue, až).
Next, following standard steps (See Corollary 1.2 in Chapter 4 of [24]). we know that En (X,, A,) -x)² |,, A; is minimized when (x, Y, A,) = Eplu|X,, Y,, A,] = pe. This shows that for any fi E h,, the optimal h, is simply the posterior mean of μ under the prior Ae conditioned on (X,, (X,),, A.). We can rewrite the minimum averaged risk over H. by switching the order of expectation:
inf Eunode Me
E (hr Yo, Ad) - -0)-4)))) [x]
inf Ex Ex.Z..z Ep (hx Yr At) 11) Xx, Zr, z
HEH
[E (wee I/xi Zi, 2: = Ex 1x,2,22007
Ex,,2.
=x,,z
(16)
| o++??
|X. a²
+
+ 82
the expectation in the last step involves only X,, 7 because of depends only X,, 7, and |7/], but not the instantiation of Z
Next, we will show that (16) is minimized for the following choice of fa which shrinks each points in X; by an amount that depends on the prior Ae's variance t²
|xal / f.(X,) = 1 /02 + 1/02 x, for each x E X,
(17)
Remark 1. An interesting observation (albeit not critical to the proof) here is that J' in (17) converges pointwise to Jt, i.e. I, as l co. This shows that the optimal submission function under the prior converges to Jt. We can make a similar observation about the posterior mean in (15), where pe converges to h as e +
17

---

To prove (17), we first define the following quantities.
M(X))
2, ((O) = Σ
AZZ = Z
Σ
X zEX;
SEY;
SEZ;
We will also find it useful express of as follows. Here is as defined in (7). We have:
b a (M(() - (T(z)))²
The following calculations show that, conditioned on X,, (iZz) μ and μ |x.1/=+11/Ea (XX;) are independent Gaussian random variables?:
1X.1/02
p()) μ. pl),) & (()) p. p,
=p( - X; ())()) p(p((z) - -ll)p(((
x exp
1 7
(ī(Z.) - -1)² exp
Σ
(x
11)
exp
262 u2
1
2 o2
2
xEX;
1 |z
Xil
1Xil/02
exp
(T((Z.) 22)² exp
/02 + 1/ 1/22
2 0²
02
82
|xxil
(x(((()))a(x.)
oxp
|x,1/02
Thus conditioning on X,, we can write
1 ((X)) ~N ((())
fiZz)) 1 1x
1,1
à²
0
X x
+1/B
which leads us
Xxi/ /x + 1/22 M(xi)
0²
1
((
Xe N
0,
(18)
7
Xi
/ 1/82
Next, we will rewrite the squared difference in ny. follows:
n
(A(Y)) - T((2)))
a
Xx P(Z.)= Xil /02 + 1/e2 (X,)
1x/1/02 X1 /02 + 1/F 1X, (XX.) ((Y))
=ā,
Here, we observe that the first part of the RHS above is equal to oÿ. where is normal noise e|X, NO0 1) and oy is defined in (18). For brevity, we will denote the second part of the RHS as (,,, fi), which intuitively characterizes the difference between X; and Y. Importantly, o(X,, fi) when fa chosen be (17).
Using and o, we can rewrite (16) using conditional expectation:
xx
Ex:
E
z
X.
12
2
X
2,
1
= Ex, Ex|X.
2'
X.I+I2.1
0²
This is akin to the observation that given u, (0 1). then and u independent.
18

---

000
1
e²
Ex,
exp
de
(19)
1x,++ 2il (eto0 +
2
2
o² +
=:Pa(e)
where we use the fact that e|X; ((.,) 1) in the last step. To proceed, we will consider the inner expectation the RHS above. For any fixed X;, (.).) (as marked the RHS) is that monotonically increases on [0, oo) bounded by [x,|+IZ]] and F-(-) (as marked on the RHS) is an even function that monotonically decreases [0, 00). That means, for any E R,
function
Fi(e - a F2))
Z (2(e)de=
< 000
X;
By corollary of the Hardy-Littlewood inequality in Lemma have
Fi(e+ + (Xle)
Fi(e)Fa(e)de,
(20)
the equality achieved when (X,, fi)/ In particular, the equality holds when f. chosen as specified in (17).
Now, complete Step 1, combine (16), (19) and (20) obtain
Ex, [ File+ ((.,
inf 18 WiEH Be
(hs( A.) (A)
Ex [ (2)) - - (((c)
(21)
where the last step is because conditioning on each realization of X,, the term inside the expectation is constant. Using (21), can write the Bayes risk RG under any prior Aş as:
Re:=
inf fEEAA,,
Bands E (hr Y, A.) 1) I
Fi(e)F2(e)))
=FeeN((011)
2 02
1xI+1Z.1
Because the term inside the expectation is bounded by xx can use dominated convergence theorem to show that:
and lime o/ g²
[2,1
+ 18,1 we
Roc == lim Eo-N(0.1)
(22)
8-000
z
[x, +12
2 a
22
+7 [x
22
Step 2: Maximum risk of (ff. ht): Next, will compute the maximum risk of the (ft. h3)
(see (8)) and show that it is equal to the RHS of (22). First note that we can write,
P
N
(0)
X
jo (a(z)
Z.)
0
22.1
By linear transformation of this Gaussian vector, we obtain
[x (π((,) 41 + |Z ( 1)
((X,)
(XX,)
((Z))
=
(((z))
- p
~ (0)
1X.1-221
0
X
14.
19

---

1X.++1211 which means | ( (A(X,) + لبكاا (ā(Z,) p1) and 2i = -)((,,)) -x,)) are independent Gaussian
random variables. Therefore, the the maximum risk of (5: h;)) is:
Ex a tt
[x o
(Xx)) +
1241
oF (Z.)))
2
sup (X, A.) 1) sup Esys
E
1
|x:1+1211
( 11)
X.l 0²
(zt X;)
11)
22 (Ti 2x) (4)
sup Eny. 1
E
77
|
+
0²+m
o²
E2
(a-1)
1xc.l
(π();) 14) + 24 (T(Z.)) (1)
2
o²
sup Eng #
[
[x1+
[02 + 7/?) (a² + n??)
| + Z
= -sup Eays 14
[3
|x. |x,1+12,1 o²
r²
+
1
Em
EE
2 +
|x,1+/211
2
0²
a2 2 (p( ((X.)))
0²
Because f((;)) - (((x;) ~ NN(1,
we can further write the maximum risk as:
|X,7
[74
sup E (h; Y,, A.) - 1)7 = (e..((
|x,++ 2,1 Roo
2
0²
+o?
[2:1
Here, we have observed that the final expression in the above equation is exactly the same as the Bayes' risk in the limit in (22) from Step 1.
Minimax optimality of (fi ht]): As the maximum is larger than the average, we can write, for any prior Ae. and any (fi,h)) E F x H.
Step 3:
sup E [ha (x, fi(X),, As) - 1m) 2 EA, [B[ A.) 1n) 2 Rr.
As this is true for all E, by taking the limit we have, for all (fi, h.) E F x H.
sup sup E( (X,,, A,) |)] 2 Rxc = sup E (h) (X,, (Xi), - p)]]pp]
That is, the recommended (fi htt) has smaller maximum risk than all other (fi, hi) E H. This establishes that for any ni.
P:(Man ((n,, fi h;), s"a)) = inf inf (M ((ns, Fc, hs). s),)).
J.EA b.
A.3.2 Proof of Lemma 6
In the previous section, we showed that for any nh, the optimal (fi, h2) were (fi hz) as given in (8). Now, we show that for the given (ff h2), the optimal number of samples is n; = a/ /cm. For this, we will show that pa a convex function of n, and then show that its gradient 0 at n?.
First, noting that
((x,) L((1,
0²
+
X
[2
20

---

we can rewrite the penalty term as:
1
p(n.) :=p; (Meso, ((r6, Si fi, 11
EE
+
2
21
(1,) -xX))))
=BenN(0.1)
+ cn
Z
X. +1/+1/211 12.1
+
22
x2
0²
[x,1
=B.-N(0.1)
+ CT4
(23)
[m- 2)
nut
22
a2 22
22
Convexity of penalty function: To show that p(n:) is convex in ni, let us consider I(n,, a.) Fixing and v, we have
(m-2))
2²
1
1
0
1+a2
x2
n++o?
1+ m2
x2
I(nn,, a) -0² On;
0
(m 22mn
(m (m-2))a
x² + M4 + m
+ ni + m
Ita?
1+a²
x²
m
(24)
As Un, [m,, xx; ai) an increasing function nis we have that I(n,, x;; a) a convex function in n.-
As expectation preserves convexity (see Lemma 10), p(n:) is a convex function.
Penalty is minimized when n Lemma 13 provides expression for the derivative of p(n:)
(obtained purely via algebraic manipulations). Using this, we have
4a
4a²m m
-1)
p'(n;)- = 64 m
mn
/nmm
(m - 2)m
mm
mmn
4ex2
(m + 1) -1) 2 Erfc
-exp
8a
mm
2/2//
a²
mans
c
(By Lemma 13)
d²
4a
/4a² 4) -1)
64 a²
mn
/mm;
(m-
- 2)m1
/ mm
mm
2
(m + 1) -1) 22T Erfe
exp
8a.
mm?
2V2
a²
mmn
=G(a) = 0.
- Finally, we have observed that the expression is Here, the second step uses the fact that n Vem equal G(a) as defined in (7) which is by our choice of a. Since p' (m;) = 0 and p(-) is convex, we can conclude that p(n:) is minimized when n, n². Therefore,
(MMe ((n) h,) sz.) - Pa (MMo, ((r,, ft h2), sz))).
21

---

A.4 Algorithm is individually rational
As outlined in the main text, the NIC property implies IR since 'working on her own' is valid strategy in the mechanism. Precisely, if an agent collects any number of points chooses not to submit anything fi(+) = 2, and then uses the sample average of the points she collected (X,,, Ø, A.) [X; - 2xex, then (m,, Si, h;) E S.
Below, will prove this when participating. For any fixed n,, without participating in the mechanism, the smallest penalty the agent can achieve is by using empirical mean estimation and the penalty is:
formally and also show that the agent's penalty is strictly smaller
T4
When participating, the agent gets additional nł number of clean data along with some noisy data, provided that all other agents are following s" By using the empirical mean over the clean data, the penalty is:
cn2
+ cn, n2
n1, + n
Now, since the weighted average estimator in Sf is minimax optimal, the agent gets even smaller maximum risk and hence smaller penalty. In other words, for any ni,
pa (Mean )*) S ps (Memm, ((n,, fi, 1(), s²))) S
+ CT cn;
+ nz
By minimizing the RHS with respect to n,, we get Pa (MM s*) < Pmm.
Thus Algorithm is IR.
A.5 Algorithm is approximately efficient
In this section, we will bound the penalty ratio PR for Mew at the strategy profiles st First, noting that G(a) 0 (see (7)), we can rearrange the terms the equation obtain:
4ac
4m² 4) (m==2)n
-
mn Sa
man""
exp
Erfc
2/2
a² mnn
2m
1a2 mn;
(m + 1) -
(25)
Next, will use the expression for p(n:) equation in (25) to simplify p(nt) as follows:
Pe MM (8 (n4,, ft ht))) in Lemma 13 and the
a² mn?
2mv 2T,,
a² mnn
exp
mnn 8n
(m- 2) Erfe
2/2
p(n))-
en
2
(By Lemma 13)
Au (m 27
a mn?
2m 2n
a² mn;
- (m - 2)T 42m
mny
(m+1)-1
+ on
(By (25))
4v 2
(m-d)
g²
m
(m
2)
And (m 1)-1
(m 2yn?
+ cn!
2mm
0²
Aa²
(m + 1)
1a n.
(m - 4) + (m - 2)
n
+ on.
2mn
4n m
22
20a² n
2
2
10a²
n
cn
+ cn
2mn
1a2
m+11
mn
1a m++1
22

---

Algorithm 2 Moes
1:
Mechanism designer publishes:
2:
The allocation space A Un2o R", and the procedure in lines 6-11.
3: Each agent i:
4:
Choose strategy 8; = (m,, h.)))-
5:
Sample n, points X; ( and submit Y; fx(X;) to the mechanism.
6: Mechanism:
7:
For each agent E [m]]
# can be done simultaneosly for all agents A, + U- Y, if Yil v/m A t otherwise. Return A; to each agent.
8:
9:
10: Each agent i:
11:
Compute estimate h (X,, Yi, A,).
10a 1
+1
2n2 m++1
From our conclusion in $A.2, we have a² > 0a
= 11, i.e.
a² > 1. Therefore, we have:
Vem
10a²
mp(n1)
(R 5*
n
+
20 / /cm
2
la m+11
ni
m
10a²
+
10e"
1 +
20 m+1
m
+ +1 = 2.
2
2n
12
m
B Proof of Theorem 2
We will use Maes to denote the mechanism in $4.1, as it pools the datsets, but checks for the size of the dataset submitted by each agent. For clarity, we have stated Mycs algorithmically in Algorithm We will also re-state the recommended strategies s {(n] ft h ) below:
12
=I
(X,
Σ
(26)
V
cm
X
DEX;UA;
Throughout this section, 8f will refer (26) (and not (8)).
We will first prove that s a Nash equilibrium. Because the sample mean achieves minimax error for Normal mean estimation [24], immediately have, for all (n,, fi, hi) E S.
p:( (Mrss, ((n:, fi, (()))))))))))))))))))))))))))))) S (MMss ((n4, Jú, be), s-.))
Because the agent can only submit the dataset subset, and the agent's 's allocation only depends on the size of the dataset, the size of the dataset she receives can always be maximized by submittin the whole data set she collects, i.e. chooses f. = I. Therefore, we have for all (ni, fú, huj) E S,
Pa(M (Mrss, ((ni, ft h;), s))) S PM ((n,, fi, h+),, s"1)) S ps (MMMs ((ni, fú, hs), s()))
Finally, we can use the fact that the maximum risk of the sample mean estimator using points is o² /n to show that the penalty is minimized when n, = n = o/ cm. In particular, we have that if n, af /em.
σ²
Pi (11,, (7).
cn, 20
ni
And if n; 2 /em
g²
PMMMss (1n, s
+ en, 2 20
ni + (m 1)0/ /om
23

---

Because 20 2 20 Pi(Mscs. ((ns, ft, ("),st)))))) is minimized when n4 0/ /mm. We thus conclude that s* Nash equilibrium. That is, for all (n,, h,) E N x F
H
Pi s*) S (Mess ((ra, Ses he),
Next, the IR and efficiency properties follow trivially from the fact that pi (Mass 8*) 20r cc/m for each agent i. In particular, (MMMsc 8*) V and P(Mpes 8*) 20 /om.
C Proof of Theorem 3
We will use Maw to denote our mechanism in $4.2, as it corrupts the deployed estimate based on the difference. We have stated this mechanism formally in Algorithm 3. We will also re-state the recommended strategies st ( below:
=
(27)
cm
Throughout this section, sf will refer to (27) (and not (8) or (26)).
We will present the proof of Theorem 3. First, in $C.1, show that s is Nash equilibrium of MEDEr as the Nash incentive compatibility result. Then, in $C.2, we show individual rationality at st. In SC.3, conclude by showing that Ma is approximately efficient by showing that its social penalty at most (1 + factor of the global minimum.
C.1 Algorithm is Nash incentive compatible
Step 1. We will first show that fixing any nee the best strategy is to submit the raw data, i.e. for all (T4, fi) E F.F
(M ((n,, f(), S (MMEDD ((n,, s":)).
(28)
Let c2,i= = E2,i/Tk where Th, and Es are as given in lines 9 and 10 respectively, We have that e 's are i.i.d. standard Normal samples. Because the cost term en, is fixed when is fixed, we only need to consider the risk term. We will first define,
(XX,)
Σ FEX;
((Y)) =
Σ x
M(Y
Σ zEY-1
R.
(29)
X
Y
Y
YEY,
Via some algebraic manipulations, we can express the maximum risk as:
+ e2,t -1) 11) )m)) "
supE. E
1
-v-
1)+
Σ
Yi + (m
1)m
WEY.
sEY
2 +
2
1
supl
Σ DEY;
ly -1-1
Σ
(2+ C2 - ())
(IY)) (m 1)m?)²
sEY-.
2
1
sup E
(IY (M(Y)) 11)) +
Σ (z (2-11) 14) 12)
Σ ez
$1
(IY) + (mn 1)m²) )²
IEY
>EY
(IY-) (m 1)m;) ) sup (IYI) - -2)) (m 1)m 1) (T())) - ()YY.))
Hg]
(m 1)m;a 0²
(IY, + (m-11 )
Recall that 3, also involves [8s]. Note that we have fixed n; and 8-; 8" the maximum risk depends only on |У,] and (Y,), that is, the agent's maximum risk hence penalty only depends on the number of points she submitted, and their average value. Hence, find the optimal submission
24

---

Algorithm 3 Moxi
Require: Approximation parameter > 0
# to obtain a 1 + bound on PR.
1: Mechanism designer publishes: The procedure in lines --11.
2: Each agent i:
3: Choose strategy 8; (nt, fs).
4: Sample n4 points X; = و and submit Y; = f((X,) to the mechanism.
5: Mechanism:
(2 (x.)) (m-1)At-1
6:
Ke -
1
B. +
Re Rel2ke - 1yllotee kx m3h./2
7:
For each agent i E [m]:
# can done simultaneuusly for all agents
8:
Y- Uزf1 1 Y
1 nh 3 [ EyE 9 IV-1 Ever_ 2h
9:
Zi {2 Es.i, for all Y-i where Eett NN(0. n/i)} |,UZZ Everiuz, u for agent i.
11:
Deploy estimate
Yi, we will first fix the size of the agent's submission |Y;| and optimize for the sample mean ((()) (step 1.1), and then we will optimize for |Y| (step 1.2).
Step 1.1. Since the other agents have each collected a h/vemm = nı points and submitted it truthfully,
we have p(Y-s) ~ NV (m-11nn
Via a binomial expansion, we can write,
E (M(S)) 2))
= ((T())) 14) --a(Y=)) 1))
24.
(-1)²
(2ke
(e(((())) [ -1) -1)ahc-11
1=0
2k:
LE [M(())
{ -2)2a -25
2j
j=0
Thus the maximum risk can be written
Re
sup E
Σ
- P
(30)
where Ao, As. is sequence of positive coefficients.
Similar to the proof of Theorem 1, we construct a lower bound on the maximum risk using sequence of Bayesian risks. Let At := NO (2), 1, 2.2.... be sequence of prior for μ. For fixed t, the posterior distribution is:
p(n(X)) (p((.l1)p(m) x exp
1
Σ
(x
12)
exp
2
20
# TEX.
exp (- 14
12
-
Σ
x 28
22 11
This means the posterior of given X, Gaussian with:
x|X; x ~ /
=:N(u,
n4/02 + 1/ ns/a² + 1/62
Therefore, the posterior risk is:
RC Ax(P((.)) - 2 X, =E
k.
A,((((Y,) - pc) (1 25 Xi
j=0
25

---

k2 A5(e - (7(()) - ne))
6²
cxp
de
20
=
=:Fa(e)
Because:
(-)- is even function and increases on [0, oo);
F-(+) is even function and decreases on [0, oc, and Sg P2(e)de 00
For any E IR, J& Fi F2)ede < co.
By the corollary of Hardy-Littlewood inequality in Lemma 9,
/ a()-a))a(e)dd / (i(e)F2(c)de
which means the posterior risk is minimized when (i(Y;) Me In Lemma 11, have stated expressions for the expected value of the power normal random variable. Using this, we can write the Bayes risk
h Σ 1=0
R
E
A,
(u --)-2e xi]
A2( 1)!!b
1=0
and the limit of Bayesian risk as + 00 is
A2(2j 1)!! 1)!! 22
Roo = lim
14
1=0
When ((Y,)) = (i);), the maximum risk is:
ha
sup E
A, (7(Y)) - 2))2 μ
-suple E
(x()(x)) 2
/
1=0
1
j=0
A2 1)!!(?2 Roo-
This means, fixing n; and Yil. agent achieves minimax risk when choosing (YY)) = (x(X)); as the maximum is larger than the average, this follows using similar argument to Step 3 in $A.3.
Step 1.2. Next, will show that the best size of the submission is Y X, T4g. assuming
(((Y)) = (x)). For this, we will first use nt to rewrite 32 as
8² n (m 1) (1 (m 1)m9)²
1: (2ke - 1) !!!lm 22
Because
((X)) ((Y.)) N (
(m (m- 1)ng o2 )
the risk term in the penalty can be rewritten and lower bounded as follows:
1
[r. o2/n// + (m 1)m; 1)!!
+
o2h.
((Y + (m - 1)mt)²
(m 1)m2
(m - 1)
+
(|Y/ + (m 1)m;)²
|Y o² + +(m 1)nã0²
h. (m 1)ke
he
+
o²
([Y)) + (m - (m=1))m))
km +1
(m
l)m
26

---

o²
(m 1)6,
1
1
he
o².
B4 + (m 1)ng
k +1
n4
(m 1)mz
Here, the last step follows from the fact that |Y|| a² ny + (m - 1)nço²
|Y:| o² + (m - 1)nç0²
((ia + (m - 1)m;)²
IE + 2| (m - 1)m; + (m - 1)2n;²
74 n
|
o²
+ +(m 1)m
|ri| o²
ni + (m 1)mç0²
ny
| T4 n;
+
n4 +
1
(m 1)n; + +(m 11)nn?
(ng + (m 1)m;){
[KG
n; + +mm 1-mm
my
0²
14 + (m 1)m
Equality holds in this inequality if and only if [| = n,,
In conclusion, fixing n4, the agent can minimize her penalty by submitting n, points with the same sample mean as the dataset X; she collected. One way to achieve this is set f: This completes the proof of (28).
Step 2:
Our next step is to show that the agent's best strategy is collect nę data points. That is, we will show for all n E N.
(Meuu ((n) st),, S P:Mow ((r4, f1'), s";)). In the following, we will use p(n:) as a shorthand for (MMMODD ((n,, fi), s" :)). The penalty can be rewritten as:
(31)
o²
n kh 1
(m - 1)4r (1
1
p(n.)= = 14 (m 1)n;
+
+
0² + cn,
kambet1
T2
(m- - 1)m;
We need to show that (n,) achieves minimum at ni; = nz.. The derivative of pi(-) is:
o²
n R.
(m 1)ke (1
k.-1
1
pm(..) = (n; + (m- - 1)m3)²
+ (m 1)m3
0²
+ c
m
12
n
Because p'(n;) increase in n, p(n;) is convex. Moreover, because
o²
n tk 1 (m - 1)a,,
(1
h--1
pl(n)) = m n a²
+
+ c
mh+tl
(m - 1)m
n
2
(m - 1)02
a²
-
+ 0,
m m²n:²
m²n;²
mnn²
we know p(n.) reaches minimum at n, = n.. This concludes the proof for (31),
C.2 Algorithm is individually rational
The penalty of an agent at the recommended strategies can be expressed as:
+ n
(m - 1)
1
An
PMMau ,i) = p(n;) =
+
0² + +nn
mn
kembt+1
m
(m
1)m
o²
n h -1 (m
-1)²
m
0² + cn.
mn
k.+1
ntte (m - 1)k.
2
o²
(2 2 k
ove
+ cn =
(32)
mn
hg mn;
m
We have that Mover is IR when m 2 2, via the following simple calculation:
1 ooe
(2 2 2 V2
oe
2 +
<
< 20 pmn
k
m
27

---

C.3 Algorithm& 3 is approximately efficient
Using the expression for Ps (MEDED: s7) in (32), the penalty ratio can be bounded by:
2 + k. vemm
1
PR(MeuE, 5*)
$ te.
20 /em
2h
D Additional Materials for Section 4.2
D.1 Mechanism detail
See Algorithm 3.
D.2
Using a weighted average under the original strategy space from $2
In this section, we will consider variation of Monen when applied to our original strategy space x F x H. For this, we will assume that Mesen will return A; Z, as the agent's allocation, and then an agent can use X;, Y,, Zi to estimate In this situation, below we show that the agent can achieve a smaller penalty using a weighted average over X; U Z, instead of the sample mean used by the mechanism. Here, the weights are proportional to the inverse of the variance of each data point. (Our mechanism purposefully uses the sub-optimal sample mean in the restricted strategy space N x IF way to shape the agent's penalty and incentivize good behavior.)
This shows that MaTED (with the above modification) is not NIC in this more general strategy space. The agent can obtain lower penalty using better estimator (such as the weighted average we show over here) and achieve a lower penalty. More importantly, as the agent knows that she can achieve a lower estimation error via a better estimator instead of more data, she can leverage this insight to collect less data and reduce her penalty even further.
We should emphasize that it is unclear if this weighted average is minimax optimal. It is also unclear if there exists a Nash equilibrium for Mon (or any straightforward modification of Mano) in the expanded strategy space.
The weighted average estimator: We will now present the weighted average estimator that achieves a lower maximum risk. To show this, first note that for all x E X, V[x]] = a²; when (n4, f1) (f). for all Z,.
V [ =E (z + Ez, 1)) 0² + 8.B (p(X.)) ()(Y:))) 26
ni 22 2
(mn;
he
(2ke - 1)!!
+ (m- - 1)m²
ke (2ke 1) 1) 22h
n1 kr (m 1)k--1 n
2
k k.m.a- (m- - 1) o
o²
hig ma
Consider the following weighted-average estimator:
1 Σxex x, x +
Exez, x
h,(X,, (Zi, n²))
0
m 0
(m 1)m
22
The maximum risk of h; is
E (hi(Xi, Yi, (Zi, (Z),n))) 1n)
1
m
0
n²
33 +
σ2 1
(m- 1)n 1m-1)n
m m-1 o²
1+ N. M-1
n
m
7
11
1
+ Ke
Re m
0²
(1
1
σ²
(33)
+
n
mn
Rc m
28

---

Note that the RHS of (33) is the risk of the sample average deployed by MaDEr- This means, suppose all other agents choose s", then agent can choose weighted average to reduce her penalty without collecting more data.
E High dimensional mean estimation with bounded variance
In this section, we will study estimating a d-dimensional mean (0)) E IR for distributions 0 with bounded variance. We will focus on our original setting in $2, but will outline the modifications to the formalism to accommodate the generality. For E Rd let 2:()) denote the 1 dimension.
Modifications to the setting in $2: First, we should change the definitions of F, H and M in equations 1 and (2) to account for the fact that the data is d dimensional. For instance, the space of functions mapping the dataset collected to the dataset submitted should be defined as F = (f
U Un20 Rdx= + Un2o [d Next, let θ {0: supp (0) C. R., EE-e [(x()) (())()))) < a², ViE E [d] be the class of all d' dimensional distributions where the variance along each dimension is bounded by o². Here, the maximum variance o² is known and is public information. Note that we not assume that the individual dimensions are independent. An agent's penalty Pt is defined
similar to (3) but considers the maximum risk over θ i.e
Pr 8) sup E (X,,, Y,, A:) (0)11 []
cng.
(34)
#e
Finally, the social penalty and ratio PR are as defined in (5), but with the above definition for pi.
Mechanism:
Our mechanism for this problem the same as the one outlined in Algorithm 1, with
the following cosmetic modifications. First, the allocation space should now be A = Un2o dg x Un2o pd x R4. The noise modulating parameter a is determined by similar equation as in (7). but with e replaced with c/d. In line 12 of Algorithm 1, we should set the size of the dataset Z; to be min |Y_l), a a /. Finally, the operations in lines 13 and 14 should be interpreted as d- dimensional operations that performed elementwise. The recommended strategy s (n,, ft hT) for agent is as follows:
if S 4,
n
m
fi =I
(35)
if 2
cm
Σuez; u 1 Euex,uZ, u ,ー
1
2a²0²
(X,,, Yi, (Zi, Z x1)
where, T.
E R..
X U ZiI + नमं Z1
n2
Above, one difference worth highlighting is the change in the recommended estimator h Previously, the weighting used the nτ. term returned by the mechanism, which is a function of Y; and Z, This data-dependent weighting
necessary to obtain exactly (i.e including constants) minimax optimal estimator for the corrupted dataset, which in turn was necessary to achieve an exact Nash equilibrium. However, bounding the risk when using a data-dependent weighting is challenging when the Gaussian assumption does not hold. Instead, here we use a deterministic weighting via the quantity 7²- While this is not exactly minimax optimal, we can show that its maximum risk is very close to a lower bound, which helps us obtain an approximate Nash equilibrium. It is worth pointing out that designing exactly minimax optimal estimators, even under i.id assumptions, challenging for general classes of distributions [24].
The following theorem states the main properties of this mechanism.
Theorem 7. The following statements are true about the mechanism Meso in Algorithm with the above modifications.
(i) The strategy profile s* as defined in (35) is an approximate Nash equilibrium, ie if all agents except i are following s", then for any alternative strategy 8; for agent i, we have ps Mea, 8*) S p&( (Mas, (s".,, + 5/m) (ū) The mechanism is individually rational at s*. (ii) The mechanism is approximately efficient s with PR TReMM, s*) ) < + 10/m.
We see that even under this more general setting, our mechanism retains its main properties with only a slight weakening of the results. We now have approximate, instead of exact, NIC, with the benefit of deviation diminishing as there are more agents. Similarly, the bound on the efficiency only slightly weaker than the one in Theorem 1.
29

---

E.1 Proof of Theorem 7
When m I 4, the claims follow using the exact steps in $A.1. Therefore, we focus on the case m Moreover, some of the key steps of this proof follows along similar lines to Theorem 1, so we will provide an outline and focus on the differences.
Approximate Nash incentive compatibility. We will first prove the statement (i) of Theorem 7, which states that 8i as defined in (35), is approximate Nash equilibrium for Man. That is, we will show that the maximum possible reduction in penalty for an agent i when deviating from of is small, provided that all other agents are following s'-..
For this, we will first lower bound the penalty p; (34) using the family of independent Gaussian distri- butions. Let Ox {N(H, Ia) l Rd denote the space of d d-dimensional normal distributions with identity covariance matrix. For any mechanism M and strategy profile s E S we define the penalty of agent restricted to θ2 as:
P (M,
sup [XI,, Y,, - m(0)1l 0]] + enj.
#eθx
Since 0. C O, it straightforward see that for all M E M and s E S
14 (M, S (M)
(36)
We will now use this result lower bound the penalty of an agent for any other alternative strategy. First note that, by independence, the mean estimation problem on θN can be viewed as independent copies of the univariate normal mean estimation problem considered in Theorem 1 but with replaced with c/d. Let hn be the weighted average that applies the estimator in (8) along each dimension. And let : = (nt, ht). We can now lower bound the penalty agent when following any (alternative) strategy 8; E S, provided that other agents are following s We have:
Pi (s,, s² = ps (MozD. (si, (nI.: ht,)))
2 vf (Mesns (sis (n=s; (1
(By (36))
= P.N (Messs 86s (n fi f h2s
(As agent i's penalty will not be affected by other agents' estimators)
2 p. (Mans (( ht). (nt... ht:)))
(By adapting the analysis in SA.3. )
= = "MMoss (Me )*)
(37)
Above, the second step uses (36) and the third step uses the fact that other agent's estimator will not affect agent i's penalty. The fourth step uses the fact that for estimation problems in θ,,, the strategy profile 5* {n1), fr h5]} is Nash equilibrium; in $A.3, showed this for the one dimensional case, but this proof can be easily adapted to d dimensions since we are assuming an identity covariance matrix in θx. Finally, by adapting the analysis in $A.5, we can obtain the following expression for agent i's penalty P. (Mes, 8*) in ON!
10e2
c/d
F (Mex, 3*) = do
+
(38)
4 mtl
m
n m
To state the approximate NIC result, we will now upper bound the penalty of the agent when following s Using the bounded variance assumption, we have:
oz Evex,uz, +
Ā+TT EMEZ!
u
2
(M,,,* = sup oE
(1()
0
+ en
+X 2
न.! 2í1
d sup
Euex,uz (uit) (u(t)
(8) + :ーサ7 EvEZ (u(k)
2 m((O)(a)) (ul))m((0yan)
)
E
+ cn
1 U 2i1 + কィ! 14/
0E0
k=1
30

---

10"
5/m
E(m)
10
10
m=5
100
200
300
400
500
Figure 2: (mm) plot. See G_ em emmelltttttooo py.
Emex,uZ, -
1 Ene 21
LE [[(((A) [((()))((0)(00) [(0)(=))]
sup 8E6
03
+ cn (39)
|x U 211
0= Zi
k=1
d
d²
d
= 0// cd
m
en:
+ cn
+1
(40)
2n
[m 2|n
2
2-
2+
m-2
6² 7. 2n
14
2
14 2
where (39) is because: for all k E [d] Vz (K) (1()) 21 (() (k), ((h) - (K) are uncorrelated pairwise. The final inequality due to the bounded variance assumption.
12
E EX
V2
(1)
22
(k)
Z
(k)
(0)
22
Next, for brevity, let us write Am == Vnz $A.2, we can show that
where defined in (7). By adapting the analysis in
Cm
20 Cm
if m S 20
Am
1,
where,
(41)
m
5,
if m
By combining the results in (37), (40), and (41), we obtain the following bound:
Pe 8*)
Ps Mazo s*)
inf,, (Mss (st, s²
F (MaD, 8*)
m
+ 1
+1
2+ 1+243
2n
do V
old
142 muml
10.42
+1)
402 m+11
+1
4.22 ((A2, 1)m + 4.1, m
=: E(m).
(42)
(4.4. + ((7A7, - 1)m + 2.7.)
Let E(m) denote the final upper bound obtained above. Next, we will prove E(m) 5/m. When m E [5, 500], this can be individually verified for each value of E(m) (see Figure 2). When m 2 500, we have Am < 1.01 (see (41)). From this we can conclude,
4 1.01 x (2.01 m 3)m
E(m)
(43)
6m
m
Combining the results in (42) and (43), obtain the following approximate NIC result:
ViE [m], S, (M s*) S PeMMs (s., s²,))
1
7
Individual rationality: This proof very similar to the proof in $A.4. particular, using calcula- tions similar to (40), can show that regardless of the choice of n,, the agent's penalty is strictly
31

---

smaller when using the uncorrupted (Z₂) and corrupted (Zz) datasets along with the weighted average in (35).
Approximate efficiency: To bound the penalty ratio, first note that by (38) and using the same reasoning as $A.5, we have that
E (Meso, 8*) inf MEM. E.P. (M, inf. E.r,' (M, 20 cove
mp, (Meso, 8*)
mp (Mesn 3*)
2 (44)
Next, ON C O, and noting that P(M,s) = Ei for all M, 8, also write,
inf MEM.EES"
DX inf P(M,s). MEM.sES"
(45)
We can combine the above results to obtain the following upper bound on PR:
P(Meso; 8*)
(Mss, 8*)
PR(Meax s*) inf ME..SS P(M.s) S
(By (45))
inf MeM.Es" Σ, (M, (M, Pi s*)
(Maza 8*)
inf MEM. E, (M, P. (Meso, 8*)
Pi (Mess: 8*)
< 2 P4 8*)
(By (44))
2(1 + E(m)))
(By definition of E(m), see (42))
10
2 + m
(By (43))
This establishes approximate efficiency for Men for the high dimensional setting.
F
Application to Bayesian Settings
While our results study the Normal mean estimation in frequentist statistics, the main ideas can also be applied to the Bayesian setting. When the Normal mean admits zero-mean normal prior, the major proof steps remain the same. Specifically, our current analysis constructs a sequence of Gaussian priors and takes the limit prove the minimax optimality. In the Bayesian setting, one can simply skip the step in (22), which takes the limit w.r.t. the prior sequence. The other steps remain the same.
G Useful Results
In this section, we will state some useful results that we have used throughout this proof. Lemma (Hardy-Littlewes Littlewood inequality, Lemma 1.6 in Burchard [10]). Let and be non-negative measurable functions that vanish at infinity Let J and of to denote the symmetric decreasing rearrangement of f and g. If f"g" g" cc, then,
[g |
Next, we will use the above result to derive corollary that will be useful in our proofs. Lemma 9 (A corollary of Hardy-Liitlewood), Let J, g be nonnegative even functions such that,
f is monotonically increasing on [0, oo).
g monotonically decreasing on [0, oo), and has a finite integral Jg. ga)dd oc.
Va. Jra f(x - a)g(x)dz < <0.
Then for all
/ f(z)g(z)d < f(x - a)g(x)dr
R
32

---

Proof. We will break this proof into two cases. The first is when sup f < oo and the second is when sup f cc. First consider the case sup f < co. Let
M lim f(z).
2000
By using Lemma 8, Va.
J (M 2 / (M f(x (d))g())))
The result follows after rearrangement.
If sup f = co, let (x) :- min(f(x), n.. For all n and by Lemma 8,
[( (n (n- fn(x)))(())d 2 | (n-fn(e ())d(r)dr
thus
1 (n(t))(a)de & / fa(x a)g(x)dx.
Note that (fx f())g(z), the result follows by letting + both sides and using dominated convergence theorem.
Below, we provide brief example on using Lemma calculate the Bayes risk in normal mean estimation problem with i.i.d data. While it is not necessary to use Hardy-Litlewood for this problem, this example will illustrate how have used our proofs.
Example 1. Consider the Normal mean estimation problem given samples X[n] ~ (w, where admits prior distribution (0, The goal is to minimize the average risk:
E Ep-N((,.3) [x [ -1)lu]]
where the loss function, I(.), is even function that increases [0, oo). By a standard argument, one can show that the posterior distribution of μ. conditioned on Xjn] Gaussian with data- detandeeenddnt purameters p., 22:
p|X[n| ~ ~N(T,T))
The posterior risk is:
z²
exp
Ey [T( [T --]]= -E [T(( - (3)) + ( B))
L(x (
dx
== (T- pi)
=ig(x)
By applying Lemma with f and g, the posterior risk above is minimized when = p. So the average risk.
The next Lemma shows that convexity is preserved under expectation under certain conditions. Lemma 10. Let y random variable and f (x, 3) be a function s.t.
fax u) is convex in x;;
Eyllf(a (x. y)ll < oc for all x.
Then [,,f( v)] is also convex in x.
Proof. For any 21, 22, have
Eylf(xr w)1 + Bf = Eyy
((11,) + f(x2,11) v)
21 +
Ey
f
2
Lemma 11 (Centered moments of normal random variable). Let X NN, 02) be normal random variable and E Z., then
ip is odd if p is even
B((X
oP
1)!!
33

---

G.1 Some technical results
Next, we will state some technical results that were obtained purely using algebraic manipulations and are not central to the main proof ideas. The first result states upper and lower bounds on the Gaussian complementary error function using an asymptotic expansion.
Lemma 12 (Eric bound). For all 0,
x² exp(
exp(-
(pp(-x²)
3exp(-x")
Erfo(x)= _ VT
(46)
x
2x.3
4r
1
exp( exp(-x²))
exp(- -2x
Erfo(x) 2
(47)
x
2x
Proof. By integration by parts:
VT
// cxp( (xp(-tt)dt
exp(-
(1t2
10
000
exp(-
(-t²)
Erfc(z)
dt
2
212
exp( (mp(->))
exp(-1x
(t))
exp(
2x
413
41
exp( (mx2)
exp(
00
exp(
dt
(48)
2x
4x3
4/
20
exp( (xx²)
exp(
exp(-x" (-x²)
3 eeppppet (-(2)
15 1xpp(
eexp(-(3
+
dt
2r
3r
8t5
816
exp(-x²)
exp(-
exp
(-2²
3 Sexp(-x"
10
15 exp( (-t?)
dt
(49)
2x
4x
8x
8
The results follow by (48) and (49).
Our next result, states an expression for the function p(n:) and its derivative defined in (23).
Lemma 13 (Value and derivative of penalty function at s*). Let p(n:) = P. PMMos ((n,, ft ht), st,))
(see (23)) and s ft ht be specified in (8). The penalty of agent in Algorithm I satisfies:
mn!
2m 2m
mu!
a
exp
8a
(m 2) Erfc
2/2
a2 min
p(n?)
+ en (50)
4 2
0²
4a
4a²m
p'(n?)
64
a²
mn
V //mm
(m (m22))m
m-2
Vmn
mmn 8a?
4a2
(m 1) -1 1 V2n Erfc
exp
(51)
mmn
2/2
man
This proof involves several algebraic manipulations, so we will provide an outline of our proof strategy. First, we will rearrange the denominator inside the expectation in (23), write the LHS of (50) J KE
L++2 and the LHS of (51) J' K'E L+za + K"E (1+=))² where the expectation is with respect to standard normal (0, 1) variable, J, K. K', K" are quantities that depend on n,, m, c, o², a², and importantly, L is strictly larger than Using properties of the normal distribution, in Lemma 14, prove the following result:
π
E
cxp
Erfc
(52)
L + x2
2L
2
34

---

V 2/213/2
(1 L) exp (
E
Erfe
(53)
(L + x²
2L
By plugging these expressions and then substituting ni ni. we obtain (50) and (51).
Proof of Lemma 13. We will rewrite p(n;) and p' p((n)) the Gaussian integral of rational functions and use (52) to calculate their values. By (23),
p(n?)= =R =BeN)((.1)
+ en
(m 22n
22 22
o2
x2
=B.n)((01)
+ en
E N(0.))
+ cm!
2)m
2nd
m- +2
2n
+
14 2n
x
0²
2
E
(0,11
+ en
n
2
2
400 1² + m
2²
m
n2
(0.1)
+ cn
2m
n
2
2
x.2 +
man 2a²
0²
m
2
exp
mn Sa²
Erfc
mmn Sa
+ cn
2m
2
mnn 2n
In (52), let T.
mn; 4a
=HHS of (50).
To prove the second statement of Lemma 13, by (24) and the dominated convergence theorem, have:
1 +
(m 22
1+a2
n2
n,"
p((m)) B2
-0²
+
(m (m=2))n
+ n nt.
1+a
x2
(By (24) and dominated convergence theorem)
(m 2 a n!
1
2u 1+
o PR ((0.11)))))
"
(m (m-2)nn; + 2n
1422 202 Ry
(m (m=2)n 2 2
1+
22) (n)
E V(,,1)
+
n
(m 2)m
4'+20=22 22 + 2
4(n) 2a²
+ +4m 2) 2222
N22111
+
An
((m 2)m + +2( + 2a 2))²
(m n22 4(m 2)m; (n: + 22²x²) + 4(m 2)m;
Eg-N10.11
+
4n
(mm 2)n; 2(m; + 22222))²
35

---

a²
-mm 2)m 1(n + 2a²x²)
+ x
B N(011)
(m -2)n;
+c
4ng
(4a2x² + mmn))
o²
(m 2)m; 4a²
Ex ((211
1 (m -2)m
Amg
(4a2x² + mmn)²
g²
o²
(4a2x² + mmn)) ) + 2n
+
(m
22)n
+
4n
4n
(4a2x² + mnn) )
0²
1 4a2x² + mnn
2n
+
(m
22)n; En~N((.1)
+
4n²
4n
(4a2x² mmn))²
0²
d²
2n
+
(m
t
4ng
4n
4a x²2 +
mn!
40
16a
(x22 +
mn. da
2
4n 2
02
4n;
(m 2)m
2a²
16a
2n;
mnn
mon
4ex
exp
mmn 8a
Erfc
mmn Sa?
mana 2a
2a
0²
(m 2) 2m,
+ 4n
16a4
mn!
20d
In (52) and (53) and let L
man
1a
0²
1 (m 2)m
4n ??
4a2m
1
1
n
mn, Sa
mmn 8a?
+
(m
2)m
4a² +
exp
Erfc
V
4n??
4ma?
16a4
man 2
0²
(m 2)mz
1
4m
2
4rx2 m
+
0²
(m 2)n
av2n 2t
n
2
(m
+ 1) -1)
exp
mn Sa
Erfo
V
mnj
An²²
/mng 16
mn,
80
=RHS of (51)
We will now prove the statements in (52) and (53). Both statements follow from the Lemma below by substituting t = 1/2. Lemma 14. For all 2 0 and some L, > 0,
1
I(t) =
exp(
-tx ) dr exp(Lt) Erfe( v Lt),
L
+
x2
2T
2L
1
π 1
Vi
J(t) =
exp( -txrt
2L -t) cxp(Lt) Erfo( v Lt) +
[ 22)2
22
2L
V2L
Proof. We derive T(I) and J(() as the solutions to two ODEs and solve the ODEs to obtain the results. Firstly, by caleulation:
000 +
-1((+ +T())
exp (xp(-1x²)dd
I x2 V2T
221
and
T(0)
dx
L+ 22 2m
2L
36

---

This means [tt satisfies the following ODE:
-I((t) + LI(t)= 22 ((0) V2r.
(54)
We solve (54) by multiplying integrating factor exp( (t)::
exp(-Li)\'(t) (exp)((())-e(((()))(((())
exp(-
21
Note that the LHS is the derivative of exp(-ITt)T(C) the ODE becomes:
(exx(_L())(()
1
exp(-Lt)
V2f
Integrating both sides over t, we get:
exp(-Li)1(() = - - exp(-Lt)dt = --j exp(-Li)dv = Erfe(VLL)
x 2L
+
22t
V2L
where we use integration by substitution for the last two equalities and C' is some constant that does depend on This means [tt) satisfies the following form:
+0)
((t) exp(Lt) [Erfc(V Lt)
2L
Using the initial condition I(0) V 21. Thus
x and the fact that Erfc(0) O, we conclude that
[(]) exp(L() Brfo( Brfo(VL.) 2T.
We can similarly derive an ODE for [t). By calculation:
2.2 +
- + =
exp( tx tt=)dx==>>>> dr = I(t)
(L + x2)²
22T
1
J(0)
dx 21,3/2 2
(L + x22²2
2n
Thus J(t) satisfies the following ODE:
{ -'((t + LJ) (((0) 21 T
(55)
We similarly multiply integrating factor -xxp( Lt) and integrate both sides:
7 dr /' [(x) exp( (xxp(-Lx)dz S( Erfo( v (oooVoz))))))) Lx) 2L
d dexp (exp(=La)J(x)==
=
+ 1' expl- Lxx)
x FrFfcoVVaa
π
dx
2I 0
V2x
(Integration by parts)
2
VLa
= - & (EEfo(LLt)))))))
222 exp(-1)2)dy
2L
13/2
Change of variable: y VLx
22
Vta
VTi
= =- V Lt)
π
exep( -eeppp-p' -22)
/
exp(-yy² -22 y22) Jdy
expl
2L
13/2
2
2
10
(Integration by parts)
2
V2
VLL
= - - (arfo(VLt)) Lt)
v Lt expl Siop(-IAn Lt)
-It)
2L
13/2 2
3//2
2
37

---

- --EecoVVL))
π
VL
exp(
V 2/
Erl (VLL)
2L
V2L
(By definition of Erl)
Vi
V
EErfc( SeriovLL)) Lt)
π
exp( Lt)
-
(1 - Erfo (vit)
2L
V21.
2 2T/123/2
(By definition of Erfc)
1 2T.
1)
Br
π
+
Vt
exp(-L()) J(0)
2T.
V2
(By (55))
This means:
- cxp((L) (J, dcsp(-La)J(x)++ + ((0)
((1)
Vł
exp(Ltt)
22 -t) Lt) V
exp(-Lt)
2L
VēL
Vt
-V21 2T. 2T. -1) exp( Erlol Erlc(v
V2L
38


Reviews:
[{"review_id": "OzrQAA07Sw", "reviewer": "Reviewer_LHqC", "summary": "The authors study a collaborative normal mean estimation problem, where m strategic agents are trying to estimate the mean \\mu of an unknown normal distribution with given variance. The agents can acquire samples drawn from the distribution at a cost of c per sample. In addition, each agent can share their samples with a mechanism, which will reward them by providing some of the samples other agents have submitted. Given that the agents are strategic, they can also omit or alter their samples prior to sharing, or even fabricate additional samples at no extra cost.\n\nThe strategy of each player therefore is how many samples to obtain, what to report and how to estimate \\mu given the response of the mechanism. The cost of the agent has a worst case flavour: it is the cost of the samples plus the maximum expected quadratic estimation error (with the supremum taken over all possible true values of \\mu and the expectation over the samples received directly or by the mechanism, which further depends on the strategies of other agents). The solution concept used is the Nash equilibrium. The mechanism needs to satisfy Incentive Compatibility (IC) and Individual rationality (IR). IC is about the players following the 'honest' strategy, which in this case is suggested by the mechanism and includes taking a certain number of samples and honestly sharing all of them. If IC holds (more on that in the questions), then following this honest strategy is the best option for any agent, as long as every other agent is also honest. IR dictates that for the honest strategy, every player should have lower cost than if playing in isolation.\n\nThe mechanism also needs to efficient, which means that the expected sum of costs (given the recommended IC strategy) should be a close approximation of the 'optimal' cost, which is the minimum that can be achieved by any mechanism and agent strategy (ignoring IC and IR constraints). In this case, it is shown that the optimal non-strategic mechanism simply collects samples are forwards them to all agents, who use a minimax estimator.\n\nThe designed mechanism called C3D collects samples from agents and then for each agent i: it splits all collected samples into two sets Z_i and Z_i', where Z_i contains min(|Y_i|, \\sigma / \\sqrt{c m}) samples where Y_i are the samples submitted by agent i. The samples Z_i' are then perturbed by adding random noise, increasing in the difference between Y_i and Z_i. This mechanism is both IC and IR (which is implied since submitting no samples is a valid strategy) and has an approximation ratio of 2.\n\nThe authors also consider extensions where the agents have to submit their true samples or where the mechanism itself calculates \\mu (thus the agents cannot misreport and then ignore their input from their estimation). In the first case, a simpler mechanism is completely efficient, while in the second a 1+ \\epsilon mechanism can be designed for all \\epsilon > 0.", "questions": "None.", "limitations": "Yes.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The setting of collaborative mean estimation is very interesting and particular care has been taken to establish a nuanced model where this question can be meaningfully posed and answered. The presentation of the paper is excellent, with all ideas communicated clearly and in the right order. Before any rigorous proof, an appropriate amount of intuition is provided. \n\nThe mechanism itself is very natural and seems robust, while achieving a good approximation.", "weaknesses": "No lower bound is provided for the 2-approximation.\n\nUsually, Incentive Compatibility refers to a strategy being optimal no matter what the other players are doing, whereas here the definition given is essentially the same as the Nash equilibrium. \n\nIn any sensible mechanism IC would imply IR in this setting. Given that the paper is very well presented this is a minor point, but a bit of content could be cut and simplify the notation by restricting mechanisms wlog.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comments and suggestions. Yes, we agree it would be interesting to establish the lower bound for the 2-approximation, and leave it to future work.\n\n*Definiton of IC:* We agree with you on this. There are two common notions of IC  that are used in the literature, dominant strategy (DSIC) and Bayes-Nash (BNIC). We don't have a DSIC and while we have a Nash equilibrium, we are clearly non-Bayesian so we couldn't use BNIC either. However, we agree that IC might be taken to mean DSIC, so we will switch to \"Nash Incentive Compatibility\" as a compromise."}, {"review_id": "Obbme7vP71", "reviewer": "Reviewer_Sj1t", "summary": "This paper studies collaborative normal mean estimation, where strategic agents collect i.i.d samples from a normal distribution at a cost. This paper designs a \"truthful\" mechanism such that the strategic players will try to collect data instead of doing some \"random\" thing that harms the system and benefits themselves for federated learning systems.", "questions": "See the weakness section.", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem it studies is very interesting, and has the potential impact for further directions and research. The theory is solid. I think this kind of research that consider the robustness of the system / robust statistics will gain much attention for federated learning (and related) community.", "weaknesses": "I am not very familiar with AGT, and thus will not point out the weakness on the theory part. However I do have some minor concerns with respect to the model and motivation.\n\n+ In this paper, the author only considers estimating the mean of Gaussian distribution from samples, which is a one-round scenario. The clients can communicate with each other and send the raw data. While in real applications, it is always not good to directly send the data because of the privacy issue. Thus the optimization problem may include several round of interactions. Is it possible to extend the current single-round results to a multi-round protocol?\n+ In federated learning or collaborated data-sharing applications, different clients may have different data-distribution (in the current paper, different clients may have different mean $\\mu_i$). Thus, some clients may also untruthfully report the data to take advantages for their own sake. The current model may be too easy (all clients consider the same data distribution). Is it possible to extend the current results / mechanism to the non-IID setting where different clients may care about different distribution?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comments and ideas. \n\n*Multi-round mechanisms and privacy:* We are actually looking at multi-round mechanisms now :) While we can build on our current paper, there is still more work needed to solve this problem. As for privacy, we believe the rigorous way to study this would be to include it as part of the agent's penalty (or utility) in the formulation. We think this is an interesting avenue for future work.\n\n*Heterogenous agents:* Studying heterogeneity will be interesting, both in terms of what the agent can collect and also in terms of what each agent wishes to estimate. We believe a 'complete' mechanism will use something similar to our mechanism when there is overlap between the agents, and some other protocol when there is no overlap. Our focus on this paper was to isolate and study the free-riding issue which is quite challenging as is."}, {"review_id": "Zy3nFDh2Lz", "reviewer": "Reviewer_ipny", "summary": "The paper designs a mechanism that collects data from n agents to estimate the mean of a Gaussian distribution. The agents incur costs to collect data, they can misreport data, and they strategically choose the level of effort and the data to report. They propose a mechanism that corrupts the returned datasets according to the difference between an agent's reported data and others' data. They prove that their mechanism is IC, IR, and achieves a 2-approximation of the optimal social welfare.", "questions": "Is it possible to use the VCG-like mechanism from (Cai et al., 2015) in your problem?", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper studies an interesting problem and the presentation is clear.", "weaknesses": "The result may be overshadowed by the results in (Cai et al., 2015), which is not cited in the current paper. Although the problem is formulated without payments, it is pretty much a mechanism design problem with payments, because the designer knows the agents' utility function exactly and can add arbitrary noise to adjust an agent's utility freely. This is very similar to adding a numerical payment to the allocation function, which makes the problem very close to (Cai et al., 2015). However, (Cai et al., 2015) achieves a much stronger result: they are able to achieve optimal social welfare at a dominant strategy equilibrium. In addition, when their mechanism is used, the agents do not have the incentive to misreport data, which means that truthfully reporting data will be a weak BNE. In this paper, only 2-approximation is achieved at a BNE, which is pretty far from the potential optimal. It may not be straightforward to apply (Cai et al., 2015) because adding noise can only give negative payments, but it is also not clear whether (Cai et al., 2015) can yield a better result than 2-approximation.\n\nCai et al., 2015, \"Optimum Statistical Estimation with Strategic Data Sources\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for mentioning the paper by (Cai et al., 2015). This is a nice and relevant paper that we were not aware of, but will be sure to include it in the revision. While Cai et al., 2015 study a general supervised learning problem, when applied to mean estimation, their setting is more restrictive than ours.\n\nThe **primary** difference is that the agents' strategy spaces are different. In the main part of our paper (Section 2 and 3), the agents can choose how much data to collect, what to submit, and most importantly how to estimate the mean from the information received from the mechanism. In (Cai et al., 2015), the agents can only choose how much effort to exert (where the effort is similar in spirit to the number of data points in our paper). This means that the mechanism design problem is significantly more challenging in our setting. Based on this, we will highlight the key differences below, while also offering rebuttals to the reviewer's claims.\n\n\n1. *the setting is similar to payments in Cai et al, since the designer knows the utility and can add noise freely:* There are two key components to designing a mechanism under our strategy space. First, the mechanism should decide 'how much' to give away (which is similar to payments), and second 'how to give away', since the agents can use the information they receive to decide how to estimate the mean. While several prior work have studied the former component (e.g Cai et al, Karimireddy et al, Blum et al), the latter component (which we believe is significantly more challenging), has not been studied to our knowledge.\nTo illustrate this further, suppose the mechanism decides on a 'payment' and returns a mean estimate that corresponds to this payment. However, there is no guarantee that the agent will simply accept this mean. The agent may post process this estimate, for instance based on the original data it collected, and aim to achieve a higher 'payment' than the mechanism intended. Agents can in fact be even more strategic; they can only submit part of the data they collected, and use the remaining hidden data to refine their estimate. The mechanism should account for this strategic behavior - this explains why we had to design careful allocation spaces, corruption mechanisms, and minimax optimal estimators for the corrupted datasets.\n\n2. *In Cai et al, the agents do not have the incentive to misreport data:* We would like to respectfully point out that this was not proved in their paper. As we pointed out above, they limit the strategy space to the amount of effort. We are looking at a 17-page COLT 2015 paper; please let us know if there is an updated version.\n(We do however believe that it is possible to prove this result for a modified version of their mechanism in a simpler setting using techniques from our paper; more on this below)\n\n3. *Cai et al are able to achieve optimal social welfare [penalty]:* First of all, we would like to point out that their definition of social penalty is different from ours.\nMoreover, there is no way to reduce one to the other as we are summing over all agents' errors, and each agent could have a different error since they may use different estimators and may have different allocations.\n\n   * However, it is worth observing that when we were first studying the problem in Section 4.2 (a simpler strategy space than Section 2 and 3 where the agents have to accept a mean estimate from the mechanism), we started with exactly the same corruption method to the one in Cai et al. We were able to prove that it was truthful; however, it was able to achieve, at best, a $1.5\\times$ factor of the global minimum according to our definition of the social penalty. We were able to improve the mechanism with a different corruption strategy to get $(1+\\epsilon)\\times$ factor for arbitrarily small $\\epsilon$ while still ensuring truthful reporting. This is the mechanism presented in Section 4.2.\n   * To summarize, when restricted to mean estimation, our results in 4.2 are already stronger than Cai et al: it achieves a lower social penalty according to *our* definition, and we prove that agents should submit the data truthfully (they did not). We wish to emphasize that our main contributions in Section 2 and 3 are **significantly** more challenging than in 4.2.\n\n\n4. *Cai et al achieve a dominant strategy equilibrium:* while it is possible to prove a DSE under a restrictive strategy space, it is easy to see that there may be multiple (infinite) Nash equilibria in any nontrivial mechanism if we allow agents to alter the data they submit and then estimate/post-process the information they receive. For instance, all agents can add some constant $a$ to each sample they collect, and then subtract $a$ from the final estimate. Each value of $a$ would correspond to a different Nash equilibrium.\n\n\nHopefully, these points alleviate your concerns that the results of Cai et al. \"overshadow\" this work. We will make sure to cite that paper and clarify the differences."}, {"review_id": "cFiU78B0Jb", "reviewer": "Reviewer_jdRd", "summary": "The author consider the problem of designing a data-sharing mechanism that encourages a group of $m$ agents to share their iid collected samples truthfully and further uses the shared data to refine their estimations of the normal mean. To ensure truthful reporting, the mechanism introduces additional noise into the shared data.  The amount of noise is determined based on the discrepancy between the mean of an agent's reported data and the mean reported by other agents, with the noise variance increasing proportionally. The authors demonstrate that this mechanism achieves both individual rationality and incentive compatibility. In addition, the mechanism is also efficient compared to the minimum social penalty. The authors further extend the result to estimation of the mean in high-dimensional settings with a bounded variance.", "questions": "What if there exists a common prior of $\\mu$? Does the result still hold in general?\n", "limitations": "No concerns here.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The problem of data sharing is well motivated by real world applications and has gained great attention in recent years. The difficulties associated with this type of problem often involve determining the appropriate pricing strategy for data to incentivize genuine data collection while discouraging data fabrication. This paper addresses the problem in an elegant way in the language of normal mean estimation. \n\nThe authors explore the methods of inserting noise into the reallocated data whose variance depends on the quality of an agent’s report. The idea has occurred in many previous work, but the authors show that by carefully designing the noise level, the mechanism can be at the same time IC, IR and efficient. Moreover, the results hold for any number of agents and can also be extended to non-normal distribution. I believe that this work may be of interest to the community.\n\nThe paper is well-written and the results are sound. ", "weaknesses": "It seems that the current result is quite limited to the specific form of the social/individual penalty. The proof of the IC also seems to heavily rely on this specific structure. Can the results be extended to more general penalty functions?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comments and suggestions. \n\n*Specific form of penalty:* Yes, you are correct. We do believe that these results can be extended to other penalty forms and supervised learning problems, but we may need to relax from an exact to an approximate Nash equilibrium. This is because for other penalty forms, it is hard to design exactly minimax-optimal estimators and it is customary to settle for rate(order)-optimal estimators. See 2nd para of Section 5. We are working on extending the ideas in this work to more general settings.\n\n*When there is a common prior $\\mu$:* Yes, our results can be adapted when there is a common prior -- see footnote 1. In fact, our analysis constructs a sequence of Normal priors to analyze the maximum risk, so if this prior is Normal, you can directly use the calculations in our proofs to obtain a Bayesian result which depends on the priors. The techniques can also be applied to non-normal priors; however, the results will be prior-dependent, and if the prior is complex, the results may be hard to interpret."}, {"review_id": "Pg1MJeJLSX", "reviewer": "Reviewer_T2ys", "summary": "The paper considers a collaborative mean estimation\nsetting where a set of agents can all collect\ni.i.d samples from an underlying Gaussian distribution,\nand their goal is to share data with each other in order\nto estimate the mean of the distribution. \nEach agent has a fixed cost for collecting each sample\nand its negative utility equals the sum of the estimation error and\nthe sampling cost.\nNaturally, each agent has an incentive to free-ride\nand under-collect, reporting false data to\nthe data collecter and using other agents' data instead.\nThe goal is to design a mechanism that can incentivize\nthe agents to share their data more truthfully, in order\nto ensure successfull mean estimation.\n\nThe authors propose an\nincentive compatible and individually rational mechanism based on the idea\nof \"punishing\" agents whose estimates deviate too much\nfrom the true mean by sharing false data with them,\nand use a minimax estimator on the collected\ndataset to estimate the mean.\nThe authors show that the mechanism's social\npenalty is at most twice the global optimum.\n", "questions": "Can the authors point to a reference for their definition of IC and IR? \nSpecifically, the definitions I'm familiar with (e.g., see [1]) require the mentioned properties\nto hold in any point, not just at the equilibrium.\nIn any case, it would be better to emphasize that the mentioend claims only hold\nat the equilibrium early on. As is, the abstract and introduction suggest\nto me that the properties hold globally, which is a much stronger claim.\n\nCan the authors provide a formal proof of the footnote in Section 4? While the claim is not central to their paper,\nI think it should be either be proved formally, or the authors should adjust the language of the footnote\nso it is clear that they do not have a proof.\n\nAlso, regarding the appendix, is there any reason the authors have chosen to put appendix F in the end, rather than the beginning?", "limitations": " ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors propose an interesting problem, and provide a nice solution to it.\nThe paper is well-written.\nThe result is somewhat surprising and I believe may be important for future research.", "weaknesses": "The presentation of the result suggests that the mechanism is incentive\ncompatible globally and not just in the equilibrium point. This\nshould be clarified earlier in the paper.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comments and suggestions. \n\n*Definition of IC and IR:* We agree with you on this. There are two common notions of IC that are used in the literature, dominant strategy (DSIC) and Bayes-Nash (BNIC). We don't have a DSIC and while we have a Nash equilibrium, we are clearly non-Bayesian so we couldn't use BNIC either. However, we agree that IC might be taken to mean DSIC, so we will switch to \"Nash Incentive Compatibility\" as a compromise.\nAs for IR, we will also clarify that it only holds at the Nash equilibrium. (We do wish to point out that it may be difficult to design an IR mechanism regardless of the strategies of the other agents. For instance, if all agents except one agent are malicious and submit false data, then the lone agent will lose out.)\n\n*Proof of footnote*: Are you implying the footnote on page 4 (and not footnote 4)? Yes, we will include proof sketch. In fact, our current analysis uses a sequence of Normal priors and Bayesian estimators to analyze the maximum (frequentist) risk. We believe these calculations can be used as is, to prove a result for Normal priors.  The techniques can also be applied to non-normal priors; however, the results will be prior-dependent, and if the prior is complex, the results may be hard to interpret.\n\n*Order in the appendix:* Appendix F consists of technical (algebraic) lemmas that are important but not central to most of the proofs. For a more coherent presentation, we decide to defer them to the end. "}, {"review_id": "XuW0noJ5g5", "reviewer": "Reviewer_8RFX", "summary": "- The authors study normal mean estimation in a collaborative setting. N agents each aim to obtain a good estimate for the unknown mean while incurring as little cost for data acquisition as possible. \n- The authors show that a naive data aggregation mechanism leads to freeriding. Then, they propose a novel mechanism in which a central entity collects all data and only sends players noisy information about other players' samples, with the magnitude of the noise depending on the deviation from a player's sample to others' samples. \n- The authors show that their mechanism fulfills desirable properties (Incentive compatibility, Individual rationality and Efficiency) in the single-dimensional Gaussian case and retains approximate versions of these properties more generally. \n**I am keeping my positive score after reading other's reviews and the rebuttal.**", "questions": "- Is it necessary for the affordance to contain $\\eta$, when the players can compute that from $Y$ and $Z$?\n- Should $2\\sigma \\sqrt{c/m}$ in line 221 use $cm$ instead of the fraction?\n- Why is Algorithm 1 using $m\\geq 4$ as the cutoff, while 221 suggests a phase transition for $m\\geq 3$?\n- Is the general form of the allowances necessary? Since the goal is mean estimation I would imagine that allowances that only use the mean (like in section 5) could simplify the exposition and analysis.", "limitations": "- The scope of the paper is firmly limited to the (fundamental) problem of mean estimation. \n- All players are assumed to be perfectly homogeneous in the sense that they have the exact same data acquisition costs and their samples have the same conditional means and variances. However, I do expect the proof intuitions to extend beyond that case.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is generally well written and offers a relevant new take on data-sharing incentives in federated learning.\n- The proposed mechanism does not rely on side payments and is therefore quite flexible. \n- The authors consider a very general class of player strategies and still manage to prove strong theorems.", "weaknesses": "- The placement of \"recommended strategies\" within the formalism is a bit confusing, as there does not appear to be any difference in the analysis of recommended vs non-recommended strategies. \n- As the recommended, desirable strategy profiles are only shown to be Nash equilbria but not dominant strategies, some discussion of other equilbria would be nice (in particular, are all equilbria essentially equivalent to the recommended strategies modulo some simple transformation, or are there very different equilbria?)  \n- Some very relevant citations seem to be missing from the related work section. In particular, the proposed mechanism is very similar to the idea of [peer prediction](https://pubsonline.informs.org/doi/abs/10.1287/mnsc.1050.0379) and connections to that strain of work could be highlighted better.\n- Minor comments: \n    - 256-258 contains \"simply\" twice in the same sentence\n\n    - 352 seems to contain a grammar error/typo (\"given her\")", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comments and suggestions. \n\n*Recommended vs non-recommended strategies:* We have shown that the recommended strategies are a Nash equilibrium, which means that when all other agents are following the recommended strategies, then the best response for an agent is to also follow the recommended strategy. Moreover, if all agents follow the recommended strategies, the social penalty is small.\n\n*Regarding other equilibria:* This is an interesting question. Due to the complexity of the space of estimators, it's not clear to us what other optimal estimators could lead to other Nash equilibria. You are correct though, that there are multiple Nash equilibria that could be similar to each other. For instance, all agents can add some constant $a$ to each sample they collect, and then subtract $a$ from the final estimate. Each value of $a$ would correspond to different Nash equilibria.\n\n*References on peer prediction:* Thank you for mentioning the references on peer prediction. We will add these to our related work section.\n\n*Inclusion of $\\eta$:* We chose to present it this way for clarity. We thought it would be clearer if all numerical quantities in Algorithm 1 were hidden (it is crucial that the random values in line 14 be hidden), and the mechanism reveal what is necessary. See lines 142--143. However, you are correct that if $\\alpha$ was also published as part of the mechanism, then revealing $\\eta$ would not be necessary.\n\n*Line 221:* The current formula in line 221 is accurate.\n\n*$m\\ge3$ vs $m\\ge4$:*\n$m\\ge3$ is the threshold at which the agent achieves the smallest penalty by collecting no data points when other agents are submitting $\\sigma/\\sqrt{cm}$ points in the mechanism described in line 209. \nWhile $m\\ge4$ is the threshold at which the equilibrium in the mechanism described in line 209 is approximately efficient with $PR \\le 2$.\n\n*Is the general form of allowance [allocations] necessary? Why not use something similar to Section 4.2?* We study general allocation spaces for three reasons:\n\n- First, we do wish to point out that even if the mechanism returns a mean, the agent need not simply accept it (like in Section 4.2). The agents could very well post-process this estimate to obtain a more accurate estimate. In fact, in Appendix 4.2, we show that under the more general strategy space, it is possible for agents to use a convex combination of the mean returned by the mechanism and the mean of their original dataset to reduce their MSE. They can then leverage this insight to collect less data and obtain a lower overall penalty.\n- Second, you are correct that a mechanism that simply returns the estimate in (8) instead of the 3-tuple, will have a similar guarantee to our current mechanism (agents will submit truthfully and accept this estimate). However, this will at best marginally simplify the presentation of the mechanism, while the analysis would be exactly the same.\n- Third, this form demonstrates that we have studied the problem in its fullest generality and better elucidates our contributions. For instance, if we had only studied mechanisms which return an estimate (i.e a scalar value), it could lead to other questions such as, \"Can you return something else instead of a simple estimate and get better guarantees?\".\n\n"}]

Author rebuttal:

Meta-review: This paper studies a collaborative normal mean estimation problem, where m strategic agents are trying to estimate the mean of an unknown normal distribution with given variance. As main contribution, the paper proposes a mechanism that can prevent free-riding and data fabrication among dishonest agents. It is proven that the proposed mechanism is incentive compatible, individual rational, and a bound on the efficiency is provided.

The reviewers found the paper to be relevant for the Neurips community, well-written, and recommend acceptance. The results presented in this paper could inspire more practical multi-round protocols for mean estimation, such as e.g. needed in many Federated Learning algorithms.

Some reviewers noted that relation to prior work should be discussed a bit more carefully (especially the reference Cai et al. 2015, "Optimum Statistical Estimation with Strategic Data Sources"). We would like to urge the authors to include this comparison (see discussion below) in the final version of the paper, and also to expand the discussion of prior work---not only comparing the different settings considered in the respective works, but also commenting on how the results of these work would compare to the proposed method if they are applied in the same (a bit less general) setting.
Decision: Accept (spotlight)