Collaborative Mean Estimation Among Heterogeneous Strategic Agents: Individual Rationality, Fairness, and Truthful Contribution
Authors: Alex Clinton
Yiding Chen
Jerry Zhu
Kirthevasan Kandasamy
Venue: ICML 2025 poster (2025)
Keywords: Mechanism design
collaborative learning
mean estimation
Primary area: theory->game_theory
TL;DR: We design algorithms to incentivize data sharing in the presence of strategic agents.

Abstract: We study a collaborative learning problem where $m$ agents aim to estimate a vector $\mu =(\mu_1,\ldots,\mu_d)\in \mathbb{R}^d$ by sampling from associated univariate normal distributions $(\mathcal{N}(\mu_k, \sigma^2))\_{k\in[d]}$. Agent $i$ incurs a cost $c_{i,k}$ to sample from $\mathcal{N}(\mu_k, \sigma^2)$. Instead of working independently, agents can exchange data, collecting cheaper samples and sharing them in return for costly data, thereby reducing both costs and estimation error. We design a mechanism to facilitate such collaboration, while addressing two key challenges: ensuring *individually rational (IR) and fair outcomes* so all agents benefit, and *preventing strategic behavior* (e.g. non-collection, data fabrication) to avoid socially undesirable outcomes.
We design a mechanism and an associated Nash equilibrium (NE) which minimizes the social penalty-sum of agents' estimation errors and collection costs-while being IR for all agents. We achieve a $\mathcal{O}(\sqrt{m})$-approximation to the minimum social penalty in the worst case and an $\mathcal{O}(1)$-approximation under favorable conditions. Additionally, we establish three hardness results: no nontrivial mechanism guarantees *(i)* a dominant strategy equilibrium where agents report truthfully, *(ii)* is IR for every strategy profile of other agents, *(iii)* or avoids a worst-case $\Omega(\sqrt{m})$ price of stability in any NE. Finally, by integrating concepts from axiomatic bargaining, we demonstrate that our mechanism supports fairer outcomes than one which minimizes social penalty.

Collaborative Mean Estimation Among Heterogeneous Strategic Agents: Individual Rationality, Fairness, and Truthful Contribution
Alex Clinton Yiding Chen
Xiaojin Zhu
Kirthevasan Kandasamy
Abstract
often involves significant costs and resources, such as exper- iments, simulations, surveys, or market research. If agents share data, it can be mutually beneficial, particularly when they have complementary data collection capabilities, as agent can exchange cheap easily accessible data for costly or hard-to-obtant data. For example, hospital may be limited in the type of data it collects, due to local demo- graphic and disease patterns, but values diverse data from other hospitals to improve treatments for all patients. Today, data sharing platforms exist in many sectors, including busi- ness (goo; aws; azu; del). science (pub, a: 53 & 68, 2013; cit; pub, b), and public institutions (mad; sfo; nyc).
We study a collaborative learning problem where m agents aim to estimate a vector (H4......dd ) E Rd by sampling from associated univariate normal distributions ("(m),=")) Agent incurs cost Cs, sample from ((u,, o²). Instead of working independently, agents can exchange data, collecting cheaper sam- ples and sharing them in return for costly data, thereby reducing both costs and estimation er- ror. We design a mechanism to facilitate such collaboration, while addressing two key chal- lenges: ensuring individually rational (IR) and fair outcomes all agents benefit, and prevent- ing strategic behavior (e.g., non-collection, data fabrication) to avoid socially undesirable out- comes. We design mechanism and an associ- ated Nash equilibrium (NE) which minimizes the social penalty-sum sum of agents' estimation errors and collection costs-while being for all agents. We achieve O( -m)mmaapppoooaattti mum social penalty in the worst case and (()) approximation under favorable conditions. Addi- tionally. we establish three hardness results: no nontrivial mechanism guarantees (i) a dominant strategy equilibrium where agents report truth- fully, (ii) is IR for every strategy profile of other agents, (ii) or avoids a worst-case ( price of stability in any NE. Finally, by integrating con- demonstrate
Incentive-related challenges. However, data sharing raises two fundamental incentive-related challenges. (i) First, we must divide the data collection work and distribute the col- lected data in an individually rational (no agent loses by participating) and fair way. For example, while it would be most efficient have agents with the cheapest costs collect all of the data, this would not be fair to such agents and even discourage them from participating. (ūi Second, we must guard against strategic behavior, ensuring agents cannot manipulate mechanisms for personal gain at others' expense. For example, naive protocols like pooling and sharing all agents' data can lead to free-riding, where an agent may contribute little data if others are expected to contribute more. Moreover, simple checks to prevent free-riding, such counting the number of data submitted, can be easily bypassed by submitting fabricated (fake) data.
the mini-
cepts from axiomatic bargaining, that our mechanism supports fairer outcomes than one which minimizes social penalty.
These considerations make defining individual rationality (IR) and fairness nontrivial. While some prior work address free-riding behaviors like non-collection and data fabrica- tion, they assume homogeneous agents with identical collec- tion costs. Moreover, the interplay between IR/fairness and strategic behavior presents novel challenges. In this work, we investigate these challenges in Gaussian mean estimation problem.
1. Introduction
With the rise of machine learning, data has become a cru- cial resource for organizations. However, collecting data
'Department of Computer Sciences, University of Wisconsin- Madison, Madison, WI, USA 'Deparmmntt of Computer Science, Coreell University, Ithaca, New York, USA. Correspondence to: Alex Clinton <aclinton @ wisc.edu>.
1.1. Summary of Contributions
Model. There are m agents who seek to estimate an un- known vector μ E Rdd using samples from d associated univariate normal distributions. Agent incurs a cost Ci to draw one sample from the k distribution M(ug o²). An
Proceedings of the nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Collaborative Mcan Estimation Among Heterogeneous Strategic Agents
agent's penalty (negative utility) is the sum of her estimation ervor and data collection costs. By sharing data with others, she can improve her estimate while reducing costs, espe- cially by collecting data from distributions with low Ct and exchanging for those with high CLA-- We wish to design a mechanism (without money) to facilitate such sharing. In such a mechanism, agents will collect data from these distri- butions and submit it. The mechanism then returns, to each agent, an estimate for 14, or more generally, information about from which she can estimate J.
the social penalty in any NE of any mechanism can be as large factor Q( away from the baseline.
4. Fairness considerations. While minimizing social penalty subject to IR is our primary goal, it places most of the data collection burden onto agents with the lowest costs, leading to potential unfairness. In $6 we show that our mechanism can accommodate fairer divisions of work, which we formalize using concepts from axiomatic bargain- ing. To our knowledge, this integration of cooperative game theory for fair work allocation and noncooperative game theory for enforcement has not been explored in prior work.
1. Problem formalism. In $3, we formalize the three desiderata for a mechanism: (1) individual rationality (IR): every agent is no worse off than working on her own, (2) incentive- Compatibility (IC): agents are incentivized to col- lect sufficient data and report it truthfully, and (3) efficiency: the social penalty (sum of agent penalties) is minimized. A key challenge in formalizing this problem, novel to our setting, when agents have unequal costs, is that directly minimizing social penalty can violate IR as it demands the lowest-cost agents to collect most of the data, resulting in higher data collection costs for them compared to work- ing alone. Therefore, we propose baseline mechanism that achieves the smallest possible penalty among all IR mechanisms. However, this baseline is not IC. Our objec- tive is therefore to construct mechanism whose penalty approximates this baseline while ensuring both IR and IC.
1.2. Related Work
Collaborative learning and truthful reporting. Several prior work has studied free-riding issues in data sharing and collaborative learning (Blum et al., 2021; Karimireddy et al., 2022: Fraboni et al., 2021; Lin et al., 2019; Huang et al., 2023), but have assumed that agents contribute data truthfully. Dorner al. (2024) study collaborative mean es- timation among competitors and allow agents to alter their submissions, but their strategy space is restricted to two scalars that agents can use to modify the data they report. This is significantly simpler than our setting, where we al- low an agent's 's submission to be as general to the extent possible, even allowing it to depend on the data she has collected. (Hardt et al., 2016) consider strategic classifica- tion problem where participants may willingly incur cost to manipulate their submission to obtain better classifica- tion outcome. Others have explored mechanisms to enforce truthful reporting (Cai et al., 2015; Chen et al., 2020; Ghosh et al., 2014), employing methods akin to ours by compar- ing an agent's submission with those of others, but not for data sharing. They also do not formally study fabrication or falsification as part of the agent's strategy, as we do. Prior work has considered designing mechanisms to incentivize participation in collaborative learning (Donahue & Klein- berg, 2021; Capitaine et al., 2024; Tu et al., 2022) but do not address the issue of truthful reporting.
2. Mechanism. In $4, we present our mechanism. To ensure truthful data reporting, we rely, partly, on techniques from prior work, which evaluate an agents' submission by comparing it the submissions of others. While such evaluation is straightforward when all agents collect similar data amounts from the same distribution, it is challenging in our setting where agents collect varying amounts of data from different distributions. To effectively apply this tech- nique, we first modify the amount of data collected in the above baseline. Our modification ensures that, when pos- sible, a sufficient number of agents collect data from each distribution, so that mechanism has enough data from other agents when evaluating the submission of any given agent. However, this may require some high-cost agents to collect more data than in the baseline, increasing total costs. Hence, the modification must be carefully designed to pre- vent significant increase in social penalty. We prove that our mechanism has a Nash equilibrium (NE) which achieves ((vm) approximation to the baseline in the worst-case, and an ((1) approximatin under favorable conditions.
Our work is most closely related to Chen et al. (2023), who studied collaborative univariate normal mean estimation with strategic agents. There two (orthogonal) challenges to incentivizing truthful contributions while maintaining an efficient system. The first, addressed by Chen et al. (2023), is designing methods to validate an agent's 's submission us- ing others' data. The second, not addressed by Chen et al. (2023) and the focus of this paper, is ensuring that there is enough data from all agents so that each agent's 's submission can be sufficiently validated against the others, without com- promising on efficiency (social penalty). Chen et al. (2023) avoid the second issue by assuming a single distribution and equal costs across agents, allowing equal data contribution and ensuring sufficient data from all agents. However, this
3. Hardness results. In $5 we supplement the above result with three hardness results. The first two show, for any efficient mechanism, we cannot hope for a dominant strategy equilibrium nor a guarantee of IR at every strategy profile of other agents. The third result characterizes the difficulty of our problem, showing that in the worst case,
2

---

Collaborative Mcan Estimation Among Heterogeneous Strategic Agents
breaks down with heterogeneous collection costs. While we adopt a similar strategy to solve the first challenge, doing so requires overcoming technical hurdles. Consequently, our problem formulation in $3, mechanism and analysis in $4, and hardness results in $5 are novel and fundamental to the heterogeneous case.
an estimate for Jr. While our mechanism also uses I = Rd this general definition is necessary for our hardness results. Mechanism. A mechanism is a tuple (Z, b). where I is a chosen information space, and b maps the datasets received from the agents, to some information, i.e. an element in I. for each agent. Let D (Un2o R") be the space of datasets that can be submitted by a single agent-au an agent may submit a different number of points from each distribution. Then, the space of mechanisms is M = {M (I, b) D: + I
Cooperative game theory in data sharing. Some apply coalitional game concepts, like Shapley value, to value data contributions of many agents (Sim et al., 2020; Jia et al., 2019; Xu et al., 2021). But, they do not study strategic agents attempting to manipulate a mechanism.
Agent's strategy space. A pure strategy of an agent i consists of three components: (i) First, she will choose n; = {nt,ak.. where n4, indicates how many samples she will collect from distribution & [d]. She then collects her initial dataset X, {Xx,, ),, where X (ar,,e,m Ti refers to the ni, points collected from distribution k. (ii) She then submits f((X,) = Y, = {Yr, }., to the mechanism; the submission function f. maps the dataset collected by the agent to her submission. Here, V = (vr.k,.) In is ideally X but dishonest agent may choose to report untruthfully via fabrication, altering, or withholding data. Crucially, the agent's 'ss report can depend on the actual dataset X; she has collected, and when computing Y,,,, she may use data from other distributions & * k. (ii)) Once the mechanism returns the information 4, the agent will estimate using all the information she has, which is her initial dataset X;, her submission Y,, and her information I, returned by the mechanism, via an estimator h₂ (x,,, Y, Tt). A pure strategy of an agent is therefore the 3-tuple (na, fi, h:) E S, where the strategy space& S = Nod x F x H and
Data collection with money. Prior work has studied data collection protocols and data marketplaces where agents are incentivized to collect data via payments (Agarwal et al., 2019; 2024; Wang et al., 2020; Cai et al., 2015; Kong et al., 2020; Zhang et al., 2014). However, our focus is on mecha- nisms for data sharing without money.
2. Description of the Environment
We will begin with a description of the environment. For any v R", let ||ol|2 denote the ee-orrm. For any set S, let (S) denote all probability distributions over S.
Preliminaries.
The universe chooses a vector f E Rdd.
There are m agents who wish to estimate μ.. They do not possess any auxiliary information, such as prior, about J., but can collect samples from associated univariate normal distributions {NVu,,, o²) )xE(q. Agent i E [m]] incurs cost C. E (0, oo) to draw single sample from the ka distribu- tion N(uu, o If CLA = oo, it means that the agent cannot sample from the htth distribution'. Let e {cL. (m) [d] denote all costs. We will assume that for each distribution there is at least one agent who can sample from it with finite cost. Let C. defined below, be the set of such costs,
F (f: D + D). H. = (h: D + +R). (2)
A mixed (randomized) strategy 8; E ASS) is a distribu- tion over S. An agent using a mixed strategy samples a pure strategy (nz, fú, h,) 8; via external random seed independent of data randomness, and executes it. Going forward, {s:]s denotes the strategies of all agents and $4 = { denotes the strategies of all agents except i.
C= c= (ci, (cs.)ee(m) E (0, oc)
vk [d], Die [m] such that Ci < oo (1)
The variance x² and costs c are publicly known. While our results generalize different variances across agents or dis- tributions, we assume a common variance a for simplicity.
Truthful submissions and accepting an estimate. Let id e F denote the identity submission function, where an agent truthfully submits their collected data, i.e. id(X,) We wish to incentivize each agent to use fz = id so that others can benefit from the agent's submission. Next, in this work, we focus on the information set space I = Ied, where the mechanism returns an estimate for и based on all agents' data. Let ACC be the estimator which directly accepts the mechanism's 's estimate, i.e. 1, A, [+) = T, As we will see, naive mechanisms allow strategic agents to gain by misreporting data (ʃa # id) and/or altering the mechanism's 's estimate instead of accepting it (h, # h. ACC)
X,,
Mechanism. We now formally define a mechanism. The example in $3.2 will illustrate the ideas. Intuitively, a mech- anism accepts data from agents and returns information they can use to estimate μ. We first define "Information".
Information space. An information space I is set chosen by the mechanism designer. The information the mechanism returns to each agent is simply an element of I. The simplest information space is I = Rd, where the mechanism returns
'Orr model generalizes other models, where agents can either sample from a distribution or not (c.g., (Huang et al., 2023)), by setting G = 1 or G = oo, respectively.
Agent's penalty. An agent's penalty (negative utility) pa is the sum of her Tizkrikk and data collection costs. As this
3

---

Collaborative Mcan Estimation Among Heterogeneous Strategic Agents
depends on the mechanism M and strategies 8, we write
3.2. A Baseline for Efficiency:
Minimizing Social Penalty While Satisfying Individual Rationality
Pi(M, : :::::) sup TE K,, -m122 + Σ CL
Our goal in $3.2 is to establish baseline for minimizing social penalty (though, as we will see, this baseline will not be IC). We begin by introducing simple mechanism and a set of agent strategies that achieve low social penalty.
pERd
(3) Here, the expectation accounts for randomness in the data, the mechanism, and agents' mixed strategies. We take supre- mum over all f since y is unknown, and strategies should achieve a small penalty for any μ.. For instance, if μ - p', for a fixed/ p². the optimal strategy for an agent in any mech- anism is to forgo data collection and choose an estimator which always outputs pl, i.e. he(+.-.-) = p², incurring zero penalty. However, this assumes prior knowledge of u. The supremum ensures the problem is well-defined, and is similar to maximum risk in frequentist statistics (Wald, 1939).
The sample mean mechanism. A simple example of a mechanism is one which estimates μ via the sample means, i.e. it pools the data from all agents from each distribu- tion ((ux a d²), takes the average estimate each jkg, and then returns this estimate to all agents. For this mecha- nism, the information space is simply I = R Let Mgs denote this mechanism. Suppose, each agent reports Y = +Y,, where Yi,e = [Hi.k,n is agent i's sub- mission for distribution k. Let Y.,k- = Uselm Yi, be all the data for distribution & [d] received from all agents. The mechanism computes an estimate jü E R for fs, where D DY.,x Ever, , y is the sample mean of all data re- ceived for distribution k. Finally, it returns this estimate to all agents, so 6 b({Y))eimi) = (ei)e where L; = ğ for all E [m²] While this mechanism is simple, it achieves the smallest possible penalty for given data collection amounts when all agents submit their data truthfully (f+ = id) and accept the estimate (h; = h ACC), ), as demonstrated in the fact below. Its proof is given in $A.2.
The social penalty. The social penalty P(M,s) s) under a mechanism M and set of strategies s is the sum of agent penalties, i.c. P(M,s) s) = E sM).
3. Problem Definition
Goal. Our goal is to design a mechanism-strategy pair s*) E M x S that incentivizes agents to follow s* (incentive compatibility, IC), ensures agents are better off than acting independently (individual rationality, IR), and minimizes the social penalty P(M, s*) (efficiency). In $ 3.1 and 3.2, we establish baselines for IR and efficiency, and in 3.3, we formalize these three desiderata.
Fact 2. Fix the data collection amounts of each agent n [n.)eemm) Then, among all mechanisms. and all possible submission functions and estimators agents could use, the sample mean mechanism, along with truthful submission and accepting the estimate achieves the smallest possible social penalty. It can be expressed as follows,
3.1. A Baseline for Individual Rationality
Agent working individually. To establish a baseline for IR, consider an agent acting on her own, who will collect some amount of data and estimate js using this data. Let 8; be (mixed) strategy which chooses the number of data n. E Nd an agent will collect, and an estimator Ji D + IRd for y which uses her own data. The minimum penalty !ND agent can achieve is,
inf P(M, (ir)s))))) = P(Man, (n,, id, ACC))) M, (5thi)ss
mo²
Σ
(5)
71.k
A=1
Challenges in social penalty minimization. Before we proceed, we observe that naively minimizing social penalty, as is standard mechanism design, is problematic in our set- ting, where agents have different data collection costs. We will illustrate this with d = 1, where all agents wish to estimate a scalar quantity μr. For the purpose of this illus- tration, let us assume that C1,1 < .... < Cm,1 < co. Let us also assume, for now, that agents are compliant, i.e. will follow any set of strategies recommended by a mechanism designer (even if it is not the best strategy for them).
Σ cLA 1)
IND P:
== inf sup 4; MERR
[ls((..) - -l12 1112+
Here, the expectation is with respect to the data and any randomness in the agent's strategy. The following fact es- tablishes an expression for IND; the proof is given in $A.1.
Fact 1. We have
20
Veak
if FoaK < <:00 Vk.
Suppose that the mechanism designer wishes to minimize the social penalty. As agents are compliant, by Fact 2, for any given data collection amounts n = (ni)iemm) where n, E N, she can use Mgp and recommend agents to submit the data truthfully (f, = id) and accept the estimate (h, AACC). For convenience let s .CO
IND
(4)
k=1
otherwise.
When designing a mechanism and strategy profile (M, s*), individual rationality will require that p,(M, 8*) S p! IND
4

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
Data points collected
(a) Working alone
(b) Social penalty
(c) Social penalty (s.t. IR)
(a) Nash bargaining
[e) Egalitarian bargaining
Agent penalty
75
50-
25-
0 Agent Agent 2 A Ageent 1 Agent 2 Agent 3
Agent Agent
Agent Agent
Agent Agent 3 Agent Agent 2 Agent 3
Figure 1. An illustration of different allocations of the data collection work the sample mean mechanism. Here, = 1, C1,1 0.033, C,.1 = 0.066, Ca.1 = 0.1, and = 10. The blue and red columns represent the number of data collected and penalties incurred, respectively. The solid, dashed, and dotted gray lines indicate the penalties incurred by agents 1, 2, and when working alone. Agents can significantly reduce their penalties by sharing data. However, minimizing the social penalty without IR constraints (Fig. (b)) leaves agent I worse off than working alone (Fig. (a)). While our primary objective is reducing social penalty, in $6, we explore axiomatic bargaining concepts to achieve fairer work allocations (Fig. (d) and (c)).
{(n,, id, ) refer to the strategy profile where the agents follow the collection amounts n and comply with the recommendations Si = id and h; J,CCC, To mini- mize social penalty, the mechanism designer can optimize for n E Nmx1, From Fact 2 this is equivalent to minimizing
mo²
minimize
s.t
m -== ny,k
1=1
σ² Tiftk
+ Ci,A
Sm IND
[m] (7)
m
mo²
m G.I.I
Since the optimization problem above is convex, it can be solved using common optimization libraries. We have illustrated an example of the solution, n OPT, in Fig. (c).
P(Mgr n
(OM) = >11 11,1
From compliant to strategic agents. While (M CCOM is IR for all agents and minimizes the social penalty subject to IR constraints, it is not incentive-compatibe as some agents collect no data to avoid costs, and simply just receive the estimates from the mechanism. For instance, in Fig. 1 (c), even if agent 2 does not collect any data, her penalty will be small as agent is already collecting a sufficiently large amount of data (details provided in $C).
As agent has the smallest cost, the RHS is minimized by assigning all the work to agent I, i.. R1,1 = a //m/ca m//1.1 and 1 = 0 for all i o 1. However, as illustrated in Fig. (b), this allocation of work benefits all others at the expense of agent 1. In fact, it is not even IR for agent as she will be better off just working on her own Fig. (a): her penalty will be P, (Mai, s SCOM)-
o² /n1,1 11,1 (vm + 1//m) Ve1,1 > 20 /C1.1 pAND, It would be hopeless to aim for globally minimum penalty when agents are strategic, when it is not even IR when they are compliant.
Even a modification of Max which counts the amount of data an agents submits to verify |Yr,el noPT will not work as agents can simply fabricate data. Specifi- cally, instead of collecting (n.PTT> points, she can col- lect 0 points, submit as many fabricated (fake) points via {Yr, and appropriately discount the fabricated dataset from her estimator h4 = {hr,e That is by choosing h,, Y2, = (n.,A IL, - ()) - |Y,,,l), where ni,A = EEjz nj,k- While this behavior benefits agent i, it hurts others who may use this data.
IR mechanisms and strategies. A more attainable goal, and the one we take in this paper, is to minimize the social penalty subject to IR constraints. For this, let us define OR to be all mechanism and strategy tuples (M, s) that are individually rational for all agents. We have.
ORR = s(M EM (M 8) S IND
MNn.vie Vi [m]].
Hence, our goal (formalized in $3.3), is to design (M, s*) E OIR so that it is the best strategy for agents to follow 8* in M, and so that P(M, s*) approximates P(Mas, s cCOM )
Baseline for efficiency. We can now present our baseline for efficiency. To find a mechanism and strategy profile pair (M, s) which minimizes the social penalty in θIR, re- call from Fact 2, that (Mar, 8n .COM) minimizes the social penalty for any given n E Nuxxd Therefore, we should find Nmxd to minimize P(M s sCOM) subject to the IR constraints Pi (Mar. s COM) < IND Vi E [m]. Re- call that s COM : (nn id, kACC)) )eEmm and that pl IND is from (4). From writing this explicitly in terms of n and using Fact 2, if n OPT minimizes the optimization problem below, follows that (Mas, cCOM) = argmin s).
Fairness considerations. Before we proceed. is worth pointing out, that while (Mas, s (.0M is IR for all agents, the outcomes may not necessarily be fair. For instance, in Fig. (c), the penalty of agent is the same as when compared to working alone; while she is not worse off anymore, she has not befitted from collaboration, while the others have. Hence, we may consider other baselines which produce more fair outcomes, even at higher social penalty.
5

---

Collaborative Mcan Estimation Among Heterogeneous Strategic Agents
In $6, we use approaches from axiomatic bargaining to define fairer baselines, and show how our mechanism in $4 can be straightforwardly extended to such situations.
first modifies n (= n nPPT) using the Compute-n-Approx subroutine, as enable such evaluations when possible.
Compute-n-Approx consists of the following high level steps. 1) Initialize the approximation ñ to be n. 2) Continu- ally check if there is an agent: whose penalty for distribu- tion & when working alone " + +.,.n (ND is already within factor of 4 of their estimation error when all agents are compliant and follow n, then update ñ so that agent i only collects migkk have been updated via the sets Vg. 4) Update ñ to ensure that agents whose collection amount has not been modified are not collecting too small a fraction of the total data. 5) Return the approximation ñi (V)) and the total amount of data under ñi for each distribution, (Th) If i & Vi. then agent i is reliant others for data from distribution k. This will turn out to be key component of determining which agents we can incentivize to collect data according to Yi, If i E Vi then it means that agent can achieve good penalty on distribution At without much help from others. The point of calculating n is to find division of work which is enforceable (each agent is incentivized to follow it assuming the others do so).
3.3. Desiderata for Mechanism Design
Our goal is to design mechanism and strategy profile pair (M, E M x S, where agents are collecting sufficient amount of data and reporting it truthfully, so as to satisfy the following three requirements:
IND points. 3) Record which indices of
1. Nash incentive-compattiiii (NIC): (M, s*) is NIC if s* is a Nash equilibrium (NE) in the mechanism M.
That is, Vi E [ml, P,(M, (6), st,)) S PM, (8%, for all other 8; (S)).
2. Individual rationality (IR): (M, is IR if each agent's penalty at st is no worse than the smallest penalty p. pNND she could achieve independently (4).
That is, Vi E [im], P(( x*) S p!ND
3. Efficiency: We say that (M,s*) is p-efficient if it satis- fies P(M,s*) S p. inf (eee 8'M
DSIC, IR regardless of other agent behavior. Before we proceed, we note that in the first two requirements, other agents are assumed to follow the recommended strat- egy, 3- ب.ب One could consider incentive-compatbilii (DSIC) condition where following of is the best strategy for agent i regardless of others' strate- gies. Similarly, one could consider a stronger IR condition where p. (M, ('), S gies s'_4. However, in $5, we will establish hardness results which demonstrate that any mechanism satisfying either of these properties will be very inefficient.
comminant-stratee.
Algorithm Compute-n-Appror
1: Inputs: collection scheme n E N
2: ñ < n # 7 will be an approximation for which truthful reporting is enforceable.
IND, for all other agent strate-
3: Vi < Ø Vk E [d] # Agents who will receive no new data from others for distribution k.
IND 4: while 3(1, k) E [m]]/V x [d] such that AND + Ci
S
4 yE MiE + +C.AMo.)) do
4. Mechanism and Theoretical Results
5:
7id + IND
We will now describe our mechanism, Man (Corrupt Based on Leverage), outlined in Algorithm 2. As an argument, it takes a collection scheme n E Nqmxd Since our goal is to minimize social penalty, throughout this section we should think of and will take OPT (see (7)). For the purpose of generalizing our mechanism to fairer solutions in $6, we will continue to write n. Our mechanism sets I = Rdd to be the information space, as it returns an estimate of μ.
6:
V/ + Va {i}
7: Th + Em Ri tke E [d]
8: while k(i,k) E [m] x [d] such that n.. 0 and
n. Tie (n do
(n (n
!ND)
9: Ni +
10: Return n. (V (T+)
Computing an enforceable division of work. To ensure truthful data reporting, we adapt techniques from prior work, which evaluate an agents' submission by comparing it to the submissions of others (e.g (Chen et al., 2023; Cai et al., 2015)). This is straightforward when all agents collect sim- ilar data amounts from the same distribution, as there will be enough data from others to evaluate any given agent's 's submission. However, in n OPT, agents with the lowest costs for a distribution typically collect most of the data for that distribution (see Fig. ((c)). To address this, Algorithm 2
Algorithm 2 walk through. After computing the enforce- able approximation n. the mechanism designer publishes the mechanism and the recommended strategies s* (which we will define shortly). Each agent then chooses their strat- egy (not necessarily following s") before collecting and submitting their data to the mechanism. After receiving agent submissions, Algorithm 2 determines if based on the input, the following favorable condition holds for (c, n):
0²
Vi, k
+
IND
+ C.
(8)
IND
n i,k
== 72
6

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
Algorithm 2 Mea.
1: Inputs: collection scheme E Nmxd
# For minimizing social penalty, take n OPT (7)
2: Mechanism designer:
3: n², (V&) I +
Compute-n-Approx(())
4: Publish the information space R the mechanism (lines 9-29), and the recommended strategies s* in (9).
5: Each agent i:
6:
Choose strategy 9, ((S) and use it to select ((1r,)) y. fú, hi) 8s.
7:
Sample (Nt,s) points from the distributions to collect X; {Xt, where X1,e R Submit Y (Y......,, Yia) I...,,...... Xi,a) to the mechanism.
8:
9: Mechanism:
10:
Yi -U,+1 Ufti YEu k(i, E [m] [d]
11:
if the conditions in (8) are satisfied then
for (i, k) [m]] x [d] do
13:
if E V& then
14:
1 I ΣvEY, //
# Use sample mean of only the agent's data.
else
16:
if ni 0 then
17:
1 + |Y EveY,,
# Use sample mean of others' data.
18:
else
19:
Y + sample Ti- - - points from Y. without replacement
20:
Zi, sample min ( points from Yi, without replacement
2
21:
Ti. + oñ (Trr.el Everi T2. ExEZ, =)
# See (11) for a,,
4i,, - { Ez 2 E v Zikk Ex ~ N'O, ) N2,
22:
Lines 20 23 adapted from (Chen et al., 2023)
I,, " Ever + (o (021,, ) ExER(A"
23:
24:
else
25:
for (i, k) E [m]] x [d] do
26:
if E argmin, Cj then
27:
I + |ial Σ Ever
Use sample mean of only the agent's 's data.
28:
else
29:
1 + PY.. EvEY.,, y
# Use sample mean of others' data.
30:
Each agent it
31:
Post-prose Post-process the estimates via the estimator function h; (X,,Y, I.).
This condition checks if, for each distribution, only sharing data for that distribution according to n better for an agent than working on her own, when all agents are compliant. This condition favorable because, when (8) is satisfied, have enough data to validate the data of every agent that relies the mechanism to achieve good penalty, and hence we will be able to obtain good bound the efficiency.
if i E Vi then agent i receives the sample mean of only their data for distribution k: (which is fine as E V& implies that agent achieves a good penalty for distribution & working alone). Second, if n = 0 then there is no data to validate receives the sample mean using the data other agents submitted for distribution k. If neither of these conditions hold, the algorithm begins running corruption process sim- ilar to Chen et al. (2023) and returns the weighted average of the clean data agent submitted and corrupted data (created from the data the other agents) for 4, The corruption co- efficients used in this process, Oi,,,, are defined in $B. In our proof, we show that this choice for ai, ensures this penalty is minimized the value of ñi. returned by Algorithm 1.
(8) does not hold, for each distribution, we have the agent with the lowest collection cost, collect their individually rational amount of data for that distribution. The sample mean of this data, for each distribution, is then returned to all agents.
Recommended strategies. We now define the recom- mended strategies s*. Let (ñ,,)) denote the values re-
When (8) holds, Algorithm 2 checks two conditions. First

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
turned by Algorithm 1 when Compute-r-Approx(()) is ex- ecuted in Algorithm 2. In the following definition, the superscript L indicates leverage, as condition (8) implies that the mechanism has enough data from the other agents (when submitting truthfully) to incentivize sufficient data collection from the remaining agent. On the other hand, NL denotes no leverage. Define of == (m,, .2) where hACC, and
which is either ()) always IR: vi E [m], VoL E A(S)
Pi (M, (s.))) I p!ND, or (2) a dominant strategy
profile: Vi E [m], Vs! E A(S), Vs'i E A(S)m- Pi (M, (st, s'.)) ) S Ps (M, (st, The following two theorems answers these in the negative, showing that every agent will incur large penalty at every strategy profile.
Theorem 2. For any E C. if M is mechanism under which s is always IR then vi E [m]] V.'_ E
ff = id. h
n = (nix))=
di k=
if (c, n) satisfies (8)
A(S) . Pi (M, (5L, s':)) Pi
where, (9)
Theorem 3. For any C E C. if M is mechanism un- der which 8 is a dominant strategy profile then Vi IND
(n k==
otherwise
k=1
IND
i E argmin, Gj.k
[m], VoL E A(S)"-1, pi (M, (st,
niga == ni,k
NL Bi
mik
0
otherwise
Hence, no agent performs better than factor 1/2 com- pared to working alone, implying agent penalties remains large and do not decrease with the number of agents m. In contrast, agent penalties under (Mar, n TPT) and our mech- anism typically decreases with m. To illustrate this, sup- pose d = and C1, = d. The minimum social penalty is 20 2 with agents incurring a penalty of 20ye'' For strategic agents, as (8) is satisfied, our mechanism achieves social penalty of 160 c'm and agent penalty of 16ave" ymm In contrast, the lower bound from Theorems and 3 gives social penalty of at least 20m and an agent penalty of 2o ve, both of which are O(ym) larger than those in our mechanism.
We now state the first theoretical result of this paper, which gives the properties of Algorithm 2 and the recommended strategies s* in (9). In $5, we show that the worst-case ()mm) bound on the price of stability is unavoidable.
Theorem 1. Let e E C and Algorithm 2 be executed with and n = n OPT (see (1), (7)). Then, (Mezs. s*) is NIC, IR, and /m-efficient. Moreover if; n (c, OPT) satisfies (8), then (Mas, 5*) is 8- efficient.
vmn
On condition (8). Condition (8) can be interpreted as follows: it is true if, for each distribution, we separately allowed agents to share data for that distribution according to n (= n2 OPT), would agents be better than working on their own For example, this is easily satisfied if all agents have the same or similar costs for each distribution. More generally, any problem instance where agents 1) collect no more data for each distribution than they would individually and 2) receive least as much data for each distribution as they would collect individually, also satisfies (8).
Our fourth theorem establishes that an (2(m)) price of sta- bility is unavoidable in the worst case. While Theorems 2 and also apply to homogeneous settings, this result is fundamental to the heterogeneous setting with multiple dis- tributions and varying agent data collection costs.
Theorem 4. There exists a set of costs e E C such that the following true. Let OIR be as defined in (6) for these costs c. For any mechanism M E M and any Nash equilibrium st E A(S) of this mechanism, we have
Proof challenges. Beyond the design challenges high- lighted above, we mention some of the technical challenges in our proof. First, we show that (8) and & V& form a suffi- cient condition to guarantee the existence of ag, (as defined previously), and then lower bound a by / /n,,u- This en- sures that for each agent it is exactly optimal collect ni,k points and contribute them truthfully. Next, we need to show that collecting ni,x points is also efficient for the agents. In particular, penalizing agents too severely via large O, may be necessary to incentivize truthful contribution but result in poor efficiency.
P(M,**) 2 22 2(Vm)) inf (M)
P(M'
6. Fairness
Thus far we have focused on designing (M, sM) E OIR to minimize social penalty. While this ensures IR, it is still unfair for agents with small data collection costs, as they will collect most, if not all the data. For example, in Fig. I (c), Agent I is doing only as well as working on her own, while others reap all the benefits. However, one can lever- age ideas from axiomatic bargaining, to choose fairer divi- sions of work. Some common bargaining solutions include Nash bargaining (Nash et al., 1950), egalitarian bargain- ing MMas-Colell et al., 1995), and the Kalai-Smordinn solution (Kalai & Smorodinsky, 1975). We have reviewed
5. Hardness Results
Theorem 1 shows that si is NE and that at this NE, each agent is better off than working on her own. As discussed in $3.3, we may consider stronger IR and IC conditions, which hold regardless of other agents' strategies. In par- ticular, is there an efficient eechanism-strategy pair (M,s)
8

---

Collaborative Mcan Estimation Among Heterogeneous Strategic Agents
these solutions in detail in SC. Both of these solutions cor- respond to solving simple optimization problems. In Fig. (d) and (e), we give examples of these solutions. In both cases, all agents benefit more fairly even though the social penalty is worse (by definition).
Impact Statement
The paper focuses on providing algorithms to enable mul- tiple parties to benefit from data sharing. As the paper is primarily theoretical in nature we do not feel the need to highlight particular societal and ethical consequences be- yond the standard considerations, concerns, and practices that accompany sharing data.
Specifying bargaining solution. Fortunately, our mech- anism can also accommodate such fair divisions of work, while still enforcing truthful reporting. To formalize this, re- call the sample mean mechanism Max ($3.2), the compliant strategy profile cCOM where agents collect data according to Nmxd ($3.2), and an agent's penalty when working alone p. IND (Fact 1). Now define,
References
http://wwaaaaaaa.aaaaaaaaa AWS Data Hub. https: /awps amazon. com/blogs /big- data/taggdatahbb// Accessed: 2024-05- 11.
Azure Data Share. https: mwt.eee.ccroooffoo com
N=
{n Nmxxd (PiMa COM) S
Pi IND vi [m]
/enn-ss/products/tttee share. Accessed: 2024- 05-10.
(10)
We refer any nº E N as bargaining solution. It speci- fies an individually rational division of work, i.e. how much data each agent should collect from each distribution, when all agents comply in the sample mean mechanism. In fact, N precisely the utility possibility set bargaining (Mas- Colell et al., 1995). By definition OPT A (see (7)), but mechanism designer may prefer fairer bargaining solution.
Citrine 10. https://citrine..ee Accessed: 2024- 05-11.
Delta Sharing. https://dtss.sss.eeeee dwt.bricks....oooo bbatarsharinng/iddeehhmm Accessed: 2024- 05-11.
c com/ en
Ads Data Hub. httpps:/deeveloperss.ggg/////// com / hacd--attta-hutuuude//ttttooo Accessed: 2022- 05-10.
Bareii approximations. If the goal is to im- plement a bargaining solution nº other than n OPT in place of efficiency, we should consider a new notion measuring how effectively the mechanism implements nB in terms of agent penalties. We say that (M, s²) p-approximates BB E N, if Vi [m], we have (M,, S p (MM sCOM), ) i.e. all agents are within factor p of the penalty they would incur if they collected data according to B and complied in the sample mean mechanism. The following theorem states that when n = n satisfies the same favorable condition in (8), we can guarantee efficient data sharing.
Madison Open Data. http::::/daaaaacttyooooote son
opendata.arcgis... com/. Accessed: 2024-05-11,
New https://ppenaate..ittffeeeeeee Accessed: 2024-05-11.
York
City
Data. Open
PubChem. https: http:///ubcchmm.cc ncbi nlm, nih.gihoov, a. Accessed: 2022-05-10.
PubMed. ht
ncbi nlmm wim..iih.ggo... gov, b.
Theorem 5. Let E C and B E N (see (1), (10)). Suppose Algorithmm& 2 is executed with n nB Then, (Maz, s*) is NIC and IR. Moreover, if (c,nB) satisfies the condition in (8), then (M ez s*) ) is an 8-approximation n
Accessed: 2024-05-10.
San
Francisco
Open
Data.
https: pttps::/dataar /ataaf..aafff.aaaaaaa..aaa.....a ort.taaaa..gg/ppenaaaaaa.. 2024-05-11.
Accessed:
53, D. J. 68. S. D. A. The cancer genome atlas pan-cancer analysis project. Nature genetics, 11100):113-11133 2013.
A. K.T.P.P..... W. Y. and
7. Conclusion
We study collaborative mean estimation where strategic agents estimate vector μ E IRd by sampling from distri- butions with different costs. We design an IR, NIC. and efficient mechanism, supported by matching hardness sults, and show that it accommodates fairer divisions of work without additional modifications.
Agarwal, A., Dahleh, M., and Sarkar, T. A marketplace for data: An algorithmic solution. In Proceedings of the 2019 ACM Conference on Economics and Computation, pp. 701-726, 2019.
Acknowledgements
Agarwal, A., Dahleh, M., Horel, T., and Rui, M. Towards data auctions with externalities. Games and Economic Behavior, 148:323-356, 2024.
This work was partially supported by NSF grant 2441796.

---

Collaborative Mcan Estimation Among Heterogeneous Strategic Agents
Blum, A., Haghtalab, N., Phillips, R. L.,, and Shao, H. One for one, all for all: Equilibria and optimality of collabo- ration in federated learning. In International Conference on Machine Learning, pp. 1014- PMLR, 2021.
Kalai, E. and Smorodinsky, M. Other solutions to nash's bargaining problem. Econometrica: Journal of the Econo- metric Society, pp. 513-518, 1975.
Karimireddy, P., Guo, W., and Jordan, M. Mechanisms that incentivize data sharing in federated learning. arXiv preprint arXiv:2207.0455 2022.
Cai, Y., Daskalakis, C., and Papadimitriou, C. Optimum statistical estimation with strategic data sources, In Con- ference on Learning Theory, pp. 280-296. PMLR, 2015.
Kong, Y., Schoenebeck, G., Tao, B., and Yu, F.-Y. Informa- tion elicitation mechanisms for statistical estimation. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 34, pp. 2095-2102, 2020.
Capitaine, A., Boursier, E., Scheid, A., Moulines, E., Jordan, M., El-Mhamdi, E.-M., and Durmus, A. Unravelling in collaborative learning. Advances in Neural Information Processing Systems, 37:97231-9726) 2024.
Lehmann, E. L. and Casella, G. Theory of point estimation. Springer Science & Business Media, 2006.
Chen, Y., Shen, Y., and Zheng, S. Truthful data acquisition via peer prediction. Advances in Neural Information Processing Systems, 33:18194-18200 2020.
Lin, J., Du, M., and Liu, J. Free-riders in federated learning:
Attacks and defenses. arXiv preprint arXiv:1911.12566 2019.
Chen, Y., Zhu, J., and Kandasamy, K. Mechanism Design for Collaborative Normal Mean Estimation. Advances in Neural Information Processing Systems, 36, 2023.
Mas-Colell, A., Whinston, M. D., Green, J. R., et al. Mi- croeconomic theory, volume 1. Oxford university press New York, 1995.
Donahue, K. and Kleinberg, J. Model-sharing games: Ana- lyzing federated learning under voluntary participation. In Proceedings of the AAAI Conference on Artificial In- felligence, volume 35, pp. 5303-5311, 2021.
Nash, J. et al. The bargaining problem. Econometrica. 18(2):155-12,, 1950.
Sim, R. H. L., Zhang, Y., Chan, M. C., and Low, B. H. Collaborative machine learning with incentive- aware model rewards. In International conference on machine learning, pp. 9927-8936 PMLR, 2020.
Domnrr, F. E.,, Konstantinov, N., Pashaliev, G., and Vechev, M. Incentivizing honesty among competitors in collab- orative learning and optimization. Advances in Neural Information Processing Systems, 36, 2024.
Tu, X., Zhu, K., Luong, N. C., Niyato, D., Zhang, Y., and Li, J. Incentive mechanisms for federated learning: From economic and game theoretic perspective. IEEE transac- tions cognitive communications and networking, 8(3): 1566-1593, 2022.
Fraboni, Y., Vidal, R., and Lorenzi, M. Free-rider attacks on model aggregation in federated learning. In International Conference on Artificial Intelligence and Statistics, pp- 1854. PMLR, 2021.
Wald, A. Contributions to the theory of statistical estimation and testing hypotheses. The Annals of Mathematical Statistics, 10(4):299-33) 03-62999926,. 1939.
Ghosh, A., Ligett, K., Roth, A., and Schoenebeck, G. Buy- ing private data without verification. In Proceedings of the fifteenth ACM conference on Economics and compu- tation, pp. 931-948, 2014.
Wang, T., Rausch, J., Zhang, C., Jia, R., and Song, D. A prin- cipled approach to data valuation for federated learning. Federated Learning: Privacy and Incentive, pp. 153-167, 2020.
Hardt, M., Megiddo, N., Papadimitriou, C., and Wootters, M. Strategic classification. In Proceedings of the 2016 ACM conference innovations in theoretical computer science, pp. 111-122, 2016.
Xu, X., Lyu, I.,, Ma, X., Miao, C., Foo, C. S., and Low, B. K. H. Gradient driven rewards to guarantee fairness in collaborative machine learning. Advances in Neural Information Processing Systems, 34:16104-16111 2021.
Huang, B., Karimireddy, S. P., and Jordan, M. I. Evaluating and incentivizing diverse data contributions in collabora- tive learning, arXiv preprint arXiv:2306.0550
2023. Jia, R., Dao, D., Wang, B., Hubis, F. A., Hynes, N., Gürel, N. M., Li, B., Zhang, C., Song, D., and Spanos, C. J. Towards efficient data valuation based on the shapley value. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1167-1176. PMLR, 2019.
Zhang, X., Yang, Z., Zhou, Z., Cai, H., Chen, L., and Li, X. Free market of crowdsourcing: Incentive mechanism design for mobile sensing. IEEE transactions on parallel and distributed systems, 25(12):3190-320 2014.
10

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
A. Proofs of referenced facts
A.1. Proof of Fact
Let us first consider agents who can sample from all distributions, i.c Ci < 0o for all k [d]. Suppose this agent collects X, via n, (ne,) samples from each distribution, incurring cost >x Ci,k It can be shown using standard arguments (Lehmann & Casella, 2006), that for any such R4,k- the deterministic sample mean WSy (1x2) jk. where hi (X,) |x E 2;, which simply takes the average of all points from distribution ht is minimax optimal. (M
o² /nG,k. Consequently, ElllSSM (X,) - μll Σx= o² /ni,k. rational agent will choose n, {ns,k l& to minimize her penalty Ek=1 o² /ns,k + C, As this decomposes, straightforward calculation shows that her penalty is minimized by deterministically choosing Ri,k a/ Vei samples from each distribution k. For convenience, let n: n!ND denote these choices for n4,k- Next, consider agents for whom C, for some k' E [d]. As this agent cannot obtain any samples from distribution k' on her own, her maximum risk in estimating P& is infinite, and consequently sup,, B[]],, 2) 2l = oo for any estimator h4- Therefore, their penalty will also be infinite. Putting these together yields the claim.
Moreover, for any R2,, the expected squared estimation error for each k: is (
A.2. Proof of Fact 2
By definition
m Σ
P(M (nj, h ),
sup
E
| (x,,id,)) - 1-112
Ci ne,k
HERd
sup E |CC (X,, id, ( HERd
-113
Since are taking n (ns) to be fixed, minimizing the social penalty is equivalent minimizing the first term in the second line. It can be shown using standard arguments (Lehmann & Casella, 2006), that for any n, the deterministic sample mean of the collected points ASM optimal. Therefore,
}
[x,.al ΣxEX,, 3), (where X Xeemm]-X,xi a) is the is minimax
m Σ MER'
sup E [1 ACC (X,,id, ()) 11 N sup
[1 SM HER
But notice that when agents submit truthfully, the sample mean of the collected points is the same as the sample mean of the submitted so ACC (X,, id, A = SSM Therefore the lower bound above is achieved using Max when agents submit truthfully and accept the estimate so we conclude
PMM (ny, id, (,AC)))== inf (fyh))semm)
P(M, (nj,Jz,h)) hz)))
Using that the data dimensions are independent, we find
d
PMM (nj, id, h ((AC)))) =
sup E [[lI.
-112] +
WRRd
1=1 k=1
27
d
sup E WERd
Σ
Σ
Xi, zeX,,k
km
27
d
sup
2 1k
+
C n4.k
X. ZEX..k
REBd
1=1
k=1
sup
RE km
X.
1=1 Rm

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
mo²
i= 1
k=
mo²
m
E
7i
B. Definition of (.,((ank))
The corruption coefficients used in Algorithm 2, Oi,k,, are each defined to be the smallest number larger than n such that Gi,x(au,)) = O where Gi is defined as
Gi, = 4a VTh
40 TR
Ci,k
Di,E
0² Di,k
Th
44
Tk
+1) - -1)
+1)--))
Ts 880,,
exp
80
Tk
n
22Frrf
(V
(11)
and D1, T3- - 22
C. Examples of different bargaining solutions
This section gives the bargaining solutions and associated computations shown in Fig. (i.e. when d = 1, C1.1 = 0.033,
C, 0.066, C3 = 0.1, and a 10). Each bargaining solution corresponds to simple optimization problem. The following computations were obtained by feeding the respective optimization problems into Mathematica with the aforementioned problem parameters.
Working alone. Recall from $A.1 that when agents work alone they will collect
C points to minimize their penalty,
This results in a penalty of 2a /4,1 Therefore,
111 = 55
IND
IND = 39, 2,2
12311
IND 32,
IND 3.63,
IND 5.13,
IND z 6.23. P3
P2
Social penalty minimization without IR constraints. Without IR constraints, the agent with the cheapest collection cost for each distribution will be responsible for collecting all of the data for that distribution. Because agents can have the same collection costs, there are multiple agents which could have the cheapest collection cost resulting different bargaining solutions with the same social penalties. this case, for the sake of convenience, assume that = argmin; G1 chooses one of the agents with the cheapest cost for distribution & in which case the following bargaining solution is one of potentially many which minimizes the social penalty
argmin
+ C.,TT..))) (mRAA
o²_
if i = argmin, Ci
n
(n.,)
where
SP ni.k
0
otherwise
2a Vincik if argmin, G.R
0
otherwise
In our example this results in
SP 95, COM Pi (Mer. n ~ 4.19,
SP =
SP 0,
P2 (Man 5,
.CM pa (Man, S,00P COM) se 1.05.
Social penalty minimization with respect to IR constraints. Recall that minimizing social penalty subject to IR constraints given by the optimization problem in (7). Although the cheapest agent for a particular distribution can no longer collect all of the data (as this would not IR), it turns out that the solution (7) still has the cheapest agents
12

---

Collaborative Mcan Estimation Among Heterogeneous Strategic Agents
collecting most of the data. More specifically, the cheapest agents collect slightly more data than they would on their own and receive small amount of data from the other agents which offsets this increase in penalty. It can be shown that under the solution to (7) there is set of cheap agents whose penalty is exactly their penalty when working alone. If it were the case that this penalty was lower than when working alone, more of the work of data collection could be shifted to this agent which would result in a decreased social penalty. Solving (7) in our example we find that
OPT 71,
OPT 7, n2.1
OPT 0,
R1,1
3311
pi (Man, 8 RPPT) R 3.63, p2 (Man
.OM SOOPT)
R 1.72, pa (Man, 8 S0PTT 1.28.
COM)
Nash bargaining. Nash bargaining typically refers to the bargaining solution which maximizes the product of each agents utility minus the utility they can achieve when working alone (Mas-Colell et al., 1995). In our setting we can think of penalty as negative utility. Thus, while there are multiple ways to define the Nash bargaining solution in our problem, reasonable to define it as
NB argiaxx II (P!ND- Ps (Mss. sn )OM)).
Le. the bargaining solution which maximizes product of the differences between an agents penalty when working alone and when collaborating with others. In our example we get that
71,1 = 35,
2,
23,
T0,,1
16,
COM) Pi (Mar, Nn ~ 2.50, P2 (Mar, COM)
RJ 2.89, P3 (Mas, COM) Ro 2.92.
Egalitarian bargaining. Egalitarian bargaining is typically defined as the bargaining solution under which all agents achieve the same utility and for which this utility is maximized (Mas-Colell et al., 1995). In our problem penalty can be viewed as negative utility. While there are many ways in which egalitarian bargaining can be defined, it is reasonable to define the egalitarian bargaining solution to be
EB
argmin max pj (Mau, Sn COM).
n
In our example we get that
72 1,1 41
EB
7221
EB
21
T2,,
EB
14
P1 ( (Man, .OMM 7
= -2 (Max, $ ,,
COM)
= Pa (Mar, s 7, = 2.69.
COM)
D. Proof of Theorem 1
The proof of the theorem can be divided into two cases based on whether or not (c, satisfies the condition given in (8). Proving the theorem when (8) does not hold is given in SD.1. When (8) holds the proof is given in $D.2.
D.1. Proof when condition (8) is not satistied
Incentive Compatibility and Individual Rationality. If (c,ne) n.) does not satisfy (8), the mechanism employs the following simple procedure for each agent and distribution. If an agent does not have the lowest collection cost for a distribution, they receive the sample mean of all of the data for that distribution. Otherwise, the agent only receives the sample mean of the data they submitted for that distribution.
IND Note that when an agent has the lowest collection cost, it is best for her collection ni,k points and use the sample mean. Moreover, she is worse off submitting this data truthfully, and accepting the estimate from the mechanism. Also, when an agent doesn't 't have the lowest collection cost for particular distribution, she will receive all the data from agents that do have the cheapest collection cost. Because their collection cost is cheaper, the best strategy for the agent receiving the data is to not collect any data (as the cost of data collection outweighs the marginal decrease in estimation error). Therefore, assuming the other agents follow s",, the best strategy for agent is st i.c. s* is a Nash equilibrium under Man when (8) isn't satisfied. Finally NIC implies IR since an agent working on their own a valid strategy.
13

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
Efficiency. Recall that the social penalty is minimized by, for each distribution & E [d], having of the agent with the cheapest cost to sample that distribution, collect mini yei,t points from distribution k and freely share them with the other agents after which each agent will take the sample mean of the data for each distribution. Therefore have that
dym
PiMMas, on
COM
o²
+ 1
argmin Ojub min Cj. minj vijk
ovm
mym minj Vey.
minj Cijk
+1 i argmin CjA o ov min Vo,a
Here the inequality is used in case there multiple agents with the same cheapest collection cost in which only one of them collects the data. Using the definition of the mechanism we also have that
o²
Ps (Mem, s*)
i argmin CjA min CiA min; Vork
argming Gj miny voLk
Therefore,
Σ k=
d²
+ 1 [i argminy Gja] min; Ci min; ver.
(Max, s*) Pi (MMg sn (OM)
argming G.A min; Fick
miny ver. Vm
l E argmin, CjKl o o vorh)
d
argmin, Gy.k min; VELA
miny VeyAA vm
k==
mn.
Therefore, (Man, 5*) /m approximasss B. When n = OPT it follows from summing the penalties of all the agents that 8*) ef-efiicient.
D.2. Proof when condition (8) satisfied
When (8) satisfied the proof becomes just an instance of Theorem by taking n = n OPT.
E. Proof of Theorem 5
We will first show in $E.1 that the constants used in Algorithm are well defined. We then prove Nash incentive compatibility, individual rationality, and efficiency in $E.2, $E.3, and $E.4 respectively.
E.1. Proving ai, is well defined when & Vk and nT,AA
We have discussed how it may not be the case that for all (i, k:) E [m]] x [d] solution to Gj,kk (,, exists. However, can show that i & VR, ni, > 0 is sufficient condition for the existence of such ds, We can also show that o4, 2 /nc The following lemma proves these two claims. Thus a as used in Algorithm 2 is well defined.
Lemma Let Ga,,( be defined as in (11). For any agent i o Vv such that n > O. Ear. 2 Vni, such that Gr,((on,)== =0
Proof. We will show that lim +o G..(aa,)) and Gi (VTT,)) 0. Since G.,k (vTT.) is continuous, will conclude that Bos 2 n such that (.
14

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
By the definition of (aa,() have
lim
40j,k
16a Thmi
000
lim
VTh
- Ci.k
0² Di,
Tk
4a
Tk +1
Tk
exp
8a
Th
ni,
-1
2TErre
V
8a ks
40
4a Tk
160 T.mii
Tk
-11 -1)
2 lim
- - Ci,k
100
+ +1
VTk
d²Di,k
ni,K
40
40 Tho²
16 T (n(,2,))
40
Tk
lim
100
+
-11
02.--200
VTx
ni,
4as,k
Aa
Th
lim
(4Thaa, - 4cix(1 Dinni
100
+1
, VT
Ta.
Notice that 0² 4er (n,,a) i & Ve. Therefore, since the first term is positive for sufficiently large i and has oi while the second term has of Lima,,t-oc G.,,(Di,k)) xC.
7i which is implied by Lemma 10 since
Recall the definition of Gi,,(an,)) Notice that Oi, > following lower bound on the Gaussian complementary error function
T = -1 -1 (+a + 1 o 2 0. Lemma 8 gives us the mink
1 xx²
exp(-2>
ErfCLB(0)
V
x
2x.3
Therefore, for 04 2 V have the following upper bound Gi,k (oi,k)
Goaa()))) == 400, (-1+
4T n7, (Th
+
-2m(
(Tu (7n-2n 2n
VTr
4
1 +
Te
e saf
22TT
-1+
Tī.
mi
ErfoIE
(v
88
Th
(12)
Using Lemma 14, we can write Gi,k (vTi,
as
UB
64( (4(2) /3/2 (Tx)3 - (2(n)xx)² -TT)))
Gi (vnt.))
=
(TT)3/2(Tr - 2n k02
Now observe that
50 64(n),))322 (cLAn)
0 ( - S
Gi
mi,k
(Tx) kn;,))or
UB
But, since i & Va. we have Tw 2 (n (ND)) (TE)) + (2(n(,)) (T²))) 0.
result of the second while loop Algorithm 1. Thus, - ))x
C + (2(n),))² (Tx)2)0² 2 c.u(nn IND (TT)) + (2(m1,))
= + 2(nn )0² (Tx))
2((ni,)) 20² 20.
Therefore, Gi,K( ( I which gives us that G. (v I 0. Since Gi,a(ar,)) is continuous, together with
too Ci.ll//))))) & and lim lim +oo Gr = co, we conclude that 3ork 2 VnL such that G (av,k)
15

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
E.2. Mani is Nash incentive compatible
We will follow the proof structure of Nash incentive compatibility in Chen al. (2023). Like Chen al. (2023), we will decompose the proof into two lemmas. The first lemma shows that for any distribution over n4, the optimal strategy is to fi fr and h4 h,. The second lemma shows that the optimal strategy is to set R4 nţ. Together, these lemmas imply that = (m) f At) is the optimal strategy. Although the proof structure will be the same, we will need to make changes to handle our more general problem setting.
Lemma 2. For all i [m] and 8; E A(S) we have that
Pi (Mon, (87, (4)) S (Man, (8i, 8i4)
where 8* is the pure strategy defined in (9).
We decompose the proof into the following lemmas:
Lemma 3. For all E. [m]] and E A(S), define the randomized strategy 8, E A(S) by sampling (1,,fi, ~ and selecting (ns, St h2). Then, we have that
Pe (Mau, (ix, S Pe (M (8,, st1))
Proof. See H.I.
Lemma 4. For all i [m]] and 8t E A(S) such that Sa = 1 dii lig (Maa, (ii) S Pi (Mes, (8i, sti)):
Proof. See H.2.
Proof of Lemma 2. For any strategy E (SS) we can construct the strategy of which samples (ni, Sis h4) ~ 8; and selects
(n4, fr, h2). Applying Lemmas and we get
Pi (Mau, (8), s4)) pi (Mau. (5/,, (4)) pi (Mom, (si, sz,))
E.3. Mon. is individually rational
If an agent works their own they, by definition, achieve their individually rational penalty. Furthermore, agent may choose to work on their own this is an option contained within their strategy space. Therefore, because we have shown that Man is incentive compatible, any agent has no incentive to deviate from their recommended strategy, hence they must achieve a penalty no worse than their individually rational penalty. Therefore, Mas individually rational.
E.4. (Mau, ) is an a-approximation to n
Let Pi, denote the penalty agent incurs as a result of trying to estimation pa, i.e. the sum of her estimation error for distribution plus the cost she incurs collecting ni,k points from distribution k. We will show in Lemma 5 that for all (i,k) k) E [m] [d]
Pi.k (Mes,, s*)
<8
Pi,k Man ((n id, hACC)},)
Using this, we will get
(Mee,, s*)
Σd_ Pi,k (Mau. s*)
Pi Man. [nn id, h A
d k=1 Pi,k MMrx {(n id, hACC))]
Σ - Spi, (Mas { ( id, AACC)
Σd Pi,k (Mer, (nn id, }ACO)),
8
16

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
This also tells that we can bound the price of stability on the social penalty by writing
- Sp: (Man: { (n= ,i,, /1ACC)))) )1;)) =8
E Pi (MEEL: s*)
Ei= Ps MMn, ((n, id, hACC)};)
2i=1 Pi (Mas, {(n id, )((C));)
Lemma 5. For all ki, E [mm] x [d] we have
Pi.k (Maz 5*)
88
Pi,k Mar [n id, )(CC)),)
Proof. We break the proof into two cases depending on whether or nor i Vj. When i E V2 we further subdivide into the following three sub cases: (a) n 0, (b) n n 0, and (c) ni, * ni
Case 1. (i E ViJ) In this case we know that ni = n IND as a result of the first while loop in Algorithm 1. Furthermore, we know from Algorithm 2 that 1 VoA EyEr. Therefore, because agent reports truthfully under s*, we have that
a² + t. = IND Ri,
a² + C.
Pi,k 8")
ni,
Since i Ve, we also know that
2
o²
+
IND CL
<4
+
IND
E n/
i.k
where n' is the value of n on the iteration when i was added to Ve, Furthermore, we know that 7
>
1 2 as result of
Lemma 11. But this implies that د n'
1/2 mm n.k. Therefore,
20
+ G. <
+ C.
m
==
m
n
J.k
202
+ C.
Σ j=l 1
B
J.k
0²
<
+
B C
1= 2
Combining these two inequalities, we get
Pi,k (Mea, 8*) Pi,k MMnn (n id, /AAC))),) Therefore, in this case can conclude that
IND
0²
+ C.
IND
8
mm n
nit + c.nngh)
m nn + Ci
g2
Ex nig + cin
Pikk (Mes, s*)
58
Pi,k Mans (n id, hAC0)),
Case 2. (a) (i & V&, n. 0) In this case simply receives the sample mean of all of the other agents' uncorrupted data for distribution A: In this case can apply Lemma 13 to get
a²
Pi.k (MOL. 5*)
Ens RjA
Ejet Ti Σ Satt ni,u
<
Pi,k Mas (nB id, (ACC))))
Ejer n
Therefore, in this case we can conclude that
Pi.k (Mesi, 5*))
-2
Pi.k MMn, (nB id, NACC)),)
17

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
Case 2. (b) (i E V&+ ni, = = 0) In this case i instead receives weighted average of clean and uncorrupted data for distribution & from the other agents. Using Lemma 12 and that ni B. we have
Pi,k (Meal, 8*) Pi, (Mas {(n id, )AAC));
Pi.k (Maas, 8*)) + C.A.
o²
EES PiA
Pi.k (Meu,, 8*)
El PiK + C.A
Pi.k (Mez, 8*)
2E Ri + C.
Let Tx = = n i.e. how it is specified in Algorithm 1. Lemma 17 gives explicit expression for Pi,k (Mau, 8*). Substituting this in, we get
Pi,k (MaL; 8*)
0² 11 Mi + C.
200 +02+ + ai,t (16G,,(m7,, 2 TTaa, + ( - 2m - -4Txa2,)00
Th n n 1, Tx + 02)
n2 n Thois + +(n + -T,)
(2 6cs i + o2) (ni, + (2c,,,n, To 02)
(ni,)
2( TTx00 mi )
(13)
(nt (7)(-nn,, & ,,
+
Here the second equality is direct result of Lemma 18. Because know 02 2 m the denominator of the second term is positive. Additionally the numerator of the second term is also positive. To see this observe that
(n,, - 2( ni (Tx)
(mt,) 2(m Tx0² + c.,
2
3 (T&)) n
30,n(1 2(mit))) TTo0² ci,,n, Th 0²
-
(14)
02
2(n (2 TT,0²
2 30.u(1
4
-2(n TT2
(15)
Ci
10(n
TT x2
0
IND) x² Line (14) uses that Th Th 2 (n a. and line (15) uses that Tg > IND = Ver Both of these statements make use of the fact that i & Vv. This means that the penalty ratio bound is decreasing as ag,i increases. Therefore, taking 0s,k / gives upper bound this entire expression. Therefore, by Lemma 20, substituting ai,A = = into (13) yields:
a which is result of Lemma 9.
Ta (20,, (ni + 60t,nn + + (ni, + (2) Th 0²)
(cc,e(nt 2(n TTo0² ni (22)
(ni (T)((nn(e)))) 44
02)
2Tx (Cann (4ni + 11Th) + +02)
(16)
(nnt + 3Tkx
(20, + 02)
IND
Since @ Ve, Lemmas and 10 tell us that Tk 2n
IND and n
> ni Therefore, Tg 4n We can use this fact to 2
i.k
18

---

Collaborative Mcan Estimation Among Heterogeneous Strategic Agents
bound (16) as follows
27k (Cr,enfu (An1,+ + 117k) + 0²)
(Anix + 33t) (20rmmt,e 022
21k (Iee, Th +02)
(Ani, + +3Tx) (20,,m Th + 02)
(4ni,e +3t) (2ouent To + 02)
(c),(mi,,)) II
37h (Illerent + 3002
(n,,)) 2TT + un T + 4m + 3Tx0²
(nni, + +3Tx) (20 + to²)
80, (Th
(4 + 3Tx)
(g Tx + {022
$ (n) 12T,. + 24 (n (n
2T + An 0² + 31,02
4n + 3Tx)
n2 T. + 0²)
1l (20 + 0²)
80, (m
3
(2 TTkk
(20,n Th + 02)
54
Therefore, in this case we can conclude that
Pi.k (Mos,, 5*)
24
Pi,k MMas, (nB, id, hACC)),)
Case 2. (c) (i & Vk, nT,a # n > 0) Similar to the previous case, i receives a weighted average of clean and uncorrected
IND
data for distribution & from the other agents. However, the difference is that in Algorithm 1, 74, was changed to n2,
by
T2
(1
the second while loop. Thus, ni, we have that
We again know from Lemma 12 that Σ i S E n Therefore,
Tv
Pi,k (MoEL: 5*)
Pik (Max: s*) o² Ei ni + Ci i,ke
Man. [nn id, hA0O)),)
Pi.k
Pi,k (Men,
Pi,k (Men,
2 "Σ a/.6
The only difference so far from the previous case is that we dropped the Ci,AM 3,k term in the denominator. It turns out that we
get away with doing this, knowing that ni,x for pi,k (Man, s*). Substituting this in, we get
Let T2 Em nh. Lemma 17 gives us explicit expression
Th
Ps,k (Man, s*)
2 2E n/
20 (02.) +02 ai,k (160L,(17, ( TTaaf, + (nT
- 2n,, 4TTa2
Ts
02
ni, Tealik + +(nn, +Tx)a
Th (m + Gei, + 0²)
(ct,(m (ni + Tk)( ( Ta + an, + 4T
22)'0 - - (2))
+
(17)
(nt + Tx)o2
19

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
Here, the second equality is direct result of Lemma 19. For oi. / the denominator of the second term is positive. Also notice that the numerator of the second term is the same the Therefore, we can again conclude that the penalty ratio is decreasing as ai, increases and so taking 0i,k Vni, gives an upper bound on the entire expression. Therefore, by Lemma 21, substituting in 0 V into (17) yields:
showed positive in the previous case.
Th (2 )2 60,,an Th + 02)
+ (, (Txa) 2( Tx (Tk)))))))) (1T, + (-)(- Ta + 4m 0 + 4T )
(ni, + Tx)
2Tx (Cann (Ani, + +11Tk) +02)
(18)
Am + 3Tk) 0²
(ntND)² Tk
Using the fact that n
o² c. (18) becomes
0²
(1TT++
4o2
(ounti (4nt, + 11Tk) + 02)
2T
0²
5.
2
An + 31k) 02
+
1
2Tμ
11T; +
CLATE
4d
+2
3T,
+
40
3T, +
5,47
117
$
3
3T
8
Therefore, in this case we can conclude that
Pi.k (Meas, 5*)
Pi,k Man; (n id, )ACC)),
In all of the cases we have considered the penalty ratio is bounded by 8. Thus concludes the proof.
F. Hardness results
F1. Proof of Theorem 2
Proof. We claim that each agent collects their IR amount of data for each distribution { IND ii,k }
} Suppose that this were not the case, and consider s'_, E A(S)"-1 such that Ejpi, n',R = 0 (i.e. when the other agents collect no data). In this case agent i working alone as they are the only one collecting data and we know from Fact that when working alone the best penalty an agent can achieve is y IND which implies that ps (M, (8s, s'-:) < <pp IND unless n4, = mis =
IND Now since we
IND IND
know that 74, = ni
IND we get pa (M, (st, s',)) 2 Σx CI
F.2. Proof of Theorem 3
Proof. We claim that each agent collects their IR amount of data for each distribution not the case, and consider s'_, A(S)"-1 such that Σjzi,e dd, (i.e. when the other agents collect data). In this situation agent i could improve their penalty by collecting their IR amount of data and using the sample mean (see $A.1). IND
IND 1
Suppose that this were
IND and so ps (M, s(,)) 2 En C.,.n But this would contradict that is a dominant strategy. Thus, ng, n, IND
F33. Proof of Theorem 4
We will now prove the hardness result given in Theorem 4.
20

---

Collaborative Mcan Estimation Among Heterogeneous Strategic Agents
Construction. We will begin by constructing a difficult problem instance. Suppose there are m agents and d 2 distributions. Let y (0, 00), and let the costs (0, oo) mo)mm> be:
C1,1 = 7, C1,2 o0,
c11 = 00, C12 FY Vi m...
(19)
Next, let us compute the minimizer of the social penalty in O. Recall that for given n E Nmxx, we have that (Man: (ng, id, ),)) simultaneously minimizes the individual penalties of all the agents, and hence the social penalty (see (5)). Moreover, as no agent can sample both distributions, we have D! = oc for all agents E [m]] Hence, we can simply minimize the social penalty without any constraints to obtain in (M P(M', ,') (see (5), (7), and (10)).
To do so, let write the social penalty P(M on COM) as follows,
m
m
2
a²
+ ca,eneee ))
P(Mss; Sp
COM)
Σ
Ds (Ma (1nj, id, ((A0))))
=
2==1 Di,k
i=1
k=
2
Σ
mo²
+
m i=1
==1
As C122 = 2o, we can set 21.2 O: otherwise the social penalty would be infinite. Similarly, we can set n1,1 = 0 for all
i E (2.....m) m). This gives us,
ma²
ma²
m
PMM {(n,, id, )ACC))))
+ 70,1
+
+
?
n2
R1.1
Σ
j=2
Therefore, the RHS can be minimized by choosing any n which satisfies
m
11, = 0
m
n1,2 O,
n4,1 0,
>
n4.2
m
(20)
1=2
Therefore the optimum social penalty is,
inf (Mi', ee)
P(M' 8') = P(M sn (OM) = 40 /myy
(21)
Proof intuition and challenges. We will first intuitively describe the plan of attack and the associated challenges. In our construction above, to minimize the social penalty, we need to collect a /m/r points from both distributions. Since agent 1 is the only agent collecting data from the first distribution (M1,, o²), ). she is responsible for collecting all of that data. Though costly, this is still IR for agent as she would have penalty of oc working alone. However, mechanism can validate agent 1 submission because she is the only one with access to distribution 1. Therefore, agent 1 will only collect an amount of data to minimize her own penalty, leaving the others with significantly less data than they would have in n leading to our hardness result.
In particular, suppose a mechanism explicitly penalizes agent I for submitting only a small amount of data, say, by adding large noise to the estimate for μ2, or even not returning any information about μl at all. Then, agent can fabricate a large amount of data by sampling from some normal distribution M( a2) at no cost, and submit this fabricated dataset instead. Intuitively, we should not expect mechanism to be able to determine if the agent is submitting data from the true distribution N N(H; o²)) or the fabricated one N(ū,, o²) as only agent has access to distribution 1. Hence, the best that a mechanism could hope for is to simply ask agent I to collect an amount of data to minimize her own penalty and submit it truthfully.
Formalizing this intuition however is technically challenging. In particular, our proof cannot arbitrarily choose ش4 when fabricating data for agent 1. For instance, if she arbitrarily chose म1 1.729, this would work poorly against mechanism which explicitly penalizes agent for submitting data whose mean is close to 1.729. The key challenge is in showing that for any mechanism, there is always fabricated data which agent can submit to the mechanism so that the information she receives about #22 is not compromised. We will now formally prove Theorem 4 using this intuition.
Notation.
Unless explicitly stated otherwise, throughout this proof, we will treat 1, 1,,2, fI, and h = (h h1,2) as random quantities sampled from a mixed strategy for agent 1. For instance, if we write Ps, (ni,1 = 5), we are referring to the probability that, when agent I follows mixed strategy 81, she collects 5 samples from the first distribution.
21

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
Proof of Theorem 4. Let M M be mechanism and let 8* (.i sm) E A(S) be (possibly mixed) Nash equilibrium of M. First observe that if if (M.2 > 0) > 0, i. if agent were to collect samples from the second distribution with nonzero probability, then Pı (M, 8*) = oo which implies P(M, s*) oo, and we are done. Hence, going forward, we
will assume Pot (71.2 2 0) 1. Similarly, we can assume Ps; (m.,1 0) 1. Note that we can also write any estimator h1 : D x D x > R² for agent as h1 = (1,2) where h1. D x D x I + R is her estimate for jak-
The key technical ingredient of this proof Lemma 6, stated below. states that instead following the recommended Nash strategy si. agent can follow an alternative strategy 31 in which she submits fabricated dataset and not be worse off. In particular, even if sj pure, 31 may be a mixed (randomized) strategy where the randomness comes from sampling (fabricating) data. She then use the legitimate data she collected to estimate ll and the information set she receives from submitting the fabricated data to estimate pg. In $1, her submission function and estimator h1 for pa may be random quantities which are determined by the fabricated data and do not depend the data X1 (X1,,, Ø) she collects. We have proved Lemma 6 in Appendix F.3.1.
Lemma 6. Let M E M and s* be Nash equilibrium in M. Then, there exists a strategy 81 E ASS) for agent I, such that
Pi (M, pı (M, (2))
o²
(D. -12)) -12)
+ m1,1
+ sup E (Z1.0t))
11,1
X M
for any D E D. Additionally, ler (0111. 0), Fi, (61,,,,12)) be drawn from i and let (Ir (hi,1 h2,2)) be drawn from s1. The following statements about these random variables are true
1. N1,1 -mi,a i.e. the amount of data the agent collects in both strategies is the same.
2. (X1,)));;)) M (X1). Le. agent I uses the sample mean of the data she collected from the first distribution estimate f1, regardless of what she submits and the information set she receives from the mechanism.
3. h1,2 is constant with respect to (i.e does not depend on) μr and X1 (X1,1: Ø), i.e. the agent's 's estimator for μlz does not use the data she collects from the first distribution.
We will organize the remainder of the proof into two steps:
Step 1.
Using Lemma 6, we will show that in any Nash equilibrium st, agent 1 always collects a/ /7 points which is factor vmm less than the amount in nB (see (20)), that is P.; (M1,, # a/ /T) = 0.
Step 2. Consequently, we show that all other agents will incur large penalty, resulting in large social penalty.
IND Step 1. Let ni,1 == o/ o/v7. 7. In this step we will show that Paa; (R1,1 * (NP)) = 0.
Suppose for contradiction that Pa. (M1,1 # IND) > O. Let &j be the strategy that Lemma 6 claims exists. Now define the strategy of be the same as except that agent always collects !u points from distribution 1. Concretely, in s1, the
agent first samples ((11,1, 0), fi, (h1,1, h122)) ~ 31 and then executes ((n),) .0) fi. (t..1,1122)) Let s' := (s st)) be the strategy profile where all other agents are following the recommended Nash strategies while agent 1 is following s1 Using the fact that in of the agent always collects n1,1 points and uses the sample mean for h1, (Lemma 6), we can write
Pi (M,s)= = sup E P1:02
E Xm Nf
Σ AE(1.2)
(X))) - =2x)2
+ m1,
sup E
E X1..XXm
(XI. -22)²
+ TND n1,1
+ +yn
IND
Next, Lemma 6 also tells us that $1, and hence in 8/. neither fi nor h1.2 depends on the actual dataset X1 = (X1,1. 2) agent has collected. Hence, we can replace X, with any D D and drop the dependence on X, and consequently /4 in
22

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
the third term of the RHS above. This leads us to,
o²
P1 (M,s') sup P2
E E X
(112 (D,,)()) A1) - -12)²]
+ +,1111"
T2 IND
Next, by property of $1 in Lemma 6, and our assumption (for the contradiction), we have P;, (n1,2 1 # n1,1 IND) P.- (m1,1 +
(ND) O. Noting that e" + y is strictly convex in and is minimized by x n1,11 a/ v. we have
0²
Pı (M, (6,,
IND
IND
sup Ma
(D, A1) -22)²
1,1
(0/112))
Xm Xm id
0²
[1/122 (D. -12)9
+ 11,
+ sup
E
E
11,1
(sl.08))
X2...X
M
0²
(112 (D) -22)²
E 81
+
71111
+ sup
E X M
11,11
(3L.0%)
Above, the final step simply observes that s' (s). and that fi and h122 are almost surely equal in both s and &1. By Lemma 6, the last expression above is equal to pi (M, 8*), which gives us pı (M, (1,,)) < pi (M,s*) which contradicts the fact that s* is Nash equilibrium, as agent can improve their penalty by switching to s1. Therefore, we conclude Pot (11,1 1 # IND) O.
Step 2. We will now show that agents 2 .... m will have a large penalty, which in turn results in large social penalty. Consider the penalty (:M,, s*) for any agent i E (2....,,, , under s*. Recall that Pay (ni,1 = 0) = 1 for all such agents (otherwise their individual penalties, and hence the social penalty would be infinite). We can write.
Pi (M,8*) sup 1122 5"
Σ (E(1).)
(bi,a (xx,) 1:) 14))2
72,
X M
[hha. ((X.,, -mi)
sup
E X1..X Xm M
.22
22
0/7
IND
Above have dropped some non-negative terms in the second step and then in the third step used the fact that cannot do better than the (minimax optimal) sample mean of agent I's submission Xi,1 to estimate jln Similarly, agent I's penalty will be at least R as she collects o/ / points.
Therefore, the social penalty Pr(M, s*) is at least movv. On the other hand, from (21), we have, P(Mas, ((n ),A0));) = 40 /my. This gives us
2 Vm P(M Ung id, (ACC)])
P
4
for any mechanism M and Nash equilibrium s* of M.
It is worth mentioning that our anlaysis in step 2 to bound the social penalty at (M, s²) is quite loose in the constants we have dropped the penalty due to the estimation error and data collections of the second distribution.
F. PROOF OF LEMMA
At a high level, Lemma says that we can decompose agent I's penalty into two parts, one for each distribution. The first term is the sum of the estimation cost for distribution plus to cost to collect the data from distribution 1. The second term
23

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
the estimation for the second distribution based the information provided by the mechanism. Notice that the the data drawn from distribution 2 as opposed to
second term only involves a supremum over [A2 and an expectation supremum over both of Mi, A2 and an expectation over all of the data. This is because the submission and estimation functions sampled from s will be constant with respect to μl and the data drawn from distribution 1.
Proof of Lemma 6. We will break this proof down into four steps:
Step 1. Using sequence of priors on f4, {Ar will construct sequence of lower bounds pi (M, s*). Furthermore, the limit - oc of these lower bounds will also be a lower bound on P1
Step 2. We will show that this lower bound is achieved for careful choice of ($1 stn) which satisfies the properties listed in Lemma 6.
Step 3. Using the fact that o1 is the optimal strategy for agent (assuming the other agents follow 821), ) we can upper bound (MM,,S, s*) by Pı (M, sT))
Step 4. We will show that our upper bound for p1 PMMM,s* s*) matches our lower bound for Pı (M, s*). Therefore, Pi (M, equals our upper/lower bound.
Step 1. For the sake of convenience, let A = (s A(S) n1,1 = n By the definition of p1 (M, and the fact that s* is a Nash equilibrium, we have
Pı (M,,' sup E
E XI..X M
Σ (xxx) -m=)? +1m1,1
kE(112}
inf sup SSY Pide2
E X Xm M
Σ kE(L2)
- -um? + +
(22)
(s1-2))
If the second equality did not hold, then agent could deviate from si by choosing strategy with a different distribution over the set of submission/estimation functions and achieve lower penalty (which would contradict that s* is a Nash equilibrium).
We will now construct a sequence of priors parameterized by 2 and use them to lower bound (22) and thus pi (M,s*) s*).
Let A, = _N(,0²)) Since the supremum is larger than the average we have
inf sup #1 ES) M1P2 (s1:et)
Σ
((x)()), mm)?
+ +1m111
X1 Xi..Xm M
kE(1,2}
inf sup E EESSS pi7A,
Σ kE(1,2)
=2x)
+ 111
(23)
(51,85)
XI......
A3
We can switch the order of the expectation for μl and X, by rewriting (4 conditioned on the marginal distribution of X For convenience, let D(7) denote the marginal distribution for X₁. Changing the order, (23) becomes
inf sup E SEYASS H2 (SL.8%)
E X2...X
E XinD(r)
E
Σ (E
(X),(X),, mx0 X
+
721.1
(24)
Pl
It is well known (Lehmann & Casella, 2006) that for a normal distribution, the Bayes' risk minimized by the Bayes estimator and and that the Bayes' risk under this estimator is simply the posterior variance, i.c.
Consider the term Eu, ( (())) - 2
{x
E (X,, I)) - -1))² -)
x
11.1
24

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
Following this observation, rewrite (24)
inf sup E #1EAss 12 (o1,0t)
E m
E Xir)((r)
E
+ (M1,)(x, - -m2)² X1
+ ,
o²
Xa
1111
o²
inf sup 6:EA(S) Na ($1:55)
(1 -12))
X1
+
71
(25)
Xm
D(T)((T) Mi
11.1
+
o²
7x
We now observe that when we condition on the data from distribution 1, (h,, (X)),, (X))), 11) 112) with respect to Pi. This allows drop the expectation over fur which let rewrite (25)
X2
constant
σ²
inf sup S1) p2 (e1.0h)
E
E (xrDD(r)
71,1
(26)
Xm
11,1
If we take the limit - oc of (26), using monotone convergence and that E E((S), we obtain the following lower bound on equation P1
0²
PI s*)
E
11
M1,1
(b),((X), - x2)
lim
inf
sup
E pa (#1,eh)
E Xm
E (xnD((r)
(27)
7-000
Step 2. Lemma shows that the right hand term in (27) is constant in r which allows us to drop the limit. Additionally, Lemma and the remarks that precede its proof, describe and show how sampling X₃ from D(T) can incorporated into the strategy 81 because D(r) probability distribution that does not depend on μl; (22 or X2,-..; Xm. Therefore, the submission/estimatonn functions used in estimating distribution 2 do not depend on the data collected from distribution 1. Thus, without loss of generality
write the lower bound in (27)
a²
E
inf sup E eEEASS na (s1ia))
E Xa... M
m2)² -M2))
(28)
n11
where D E D is any dataset. Therefore, we have
0² + n1
PI 2
+ +
(29)
12,1
However, priori, do know that there exists a single strategy 81 E A(SY which actually achieves estimation error of L distribution 2 (i.c. the eπrо corresponding to plugging the strategy into the right hand term of (28)). Suppose for contradiction that this is not the case. We know that for all E > 0, we can find strategy whose estimation error for distribution 2 comes within of L. Furthermore, for each of these strategies, the distribution over f1,1 does not affect the estimation error of distribution 2 since the right hand term does not involve h111- Therefore, we can suppose that these
strategies all select hi,1 = h SM (X1). More concretely, Vs O, 3sf E A(SY such that hi = SM (X,) and
sup (ff.5))
E X X2...X.. X... M
(1n.2(D.A
p2)²] -
<L+
we plug the strategy (sf, s into equation (22) we obtain the following upper bound on pr ( (M,**
PM < sup
E (
E X
Σ
(LLA(X,, )2x)
+ E [mm.1]]
M
(E(12)
25

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
+ sup IE a2
E Xm
(n)) - m=)² -12)²
+ E (,m,1))
11,1
(1D))) - -22)²
+ 711,1
+ sup
E
E
161,1
#2
(ofiet))
X2...
M
711,1
+ LEE.
(30)
11,1
As supposing that the lower bound in inequality (29) is not actually achieved for any 81 E A(SY, the inequality is strict. Combining inequalities (29) and (30), we get
o²
o² 11,1
+L+E>p((Ms)) E
+ 7011 +L.
11,1
However, this yields contradiction since these inequalities hold > Therefore, we conclude that 3 Ji, T.) 3i (SS) such that
( - -p2)² =
sup
F2
(31.4%)
Xa...
Furthermore, for this strategy, the distribution over hı, does not affect the above term (the estimation error of distribution 2) since h1,1 doesn't appear in the expression. Therefore, we can suppose that $1 always selects h1 = h h5M (X2). Also observe that since we were able to replace X1 with D in step 2, we have that f1. h1,2 are constant with respect to μr and X1. Additionally, since 8j E A(SY we know that 71,1 = ni.1- Therefore, 8j satisfies our three desired properties which are listed below.
(X))).)). Let be defined == (81, 8.
1. M1,1 ni.1-
3. 21.2 constant with respect to jn and X1.
We can now write the lower bound in equation (29) as
Pi PM 2
+ ym
+ sup
E
E [(LL)(D, (1) - n2)
(31)
111
N2 X2...
Step We can now take 5. plug into equation (22), and use properties two and three of s to get the following upper bound on Pı (M, s*)
Pi (M, < sup
E X1 X1...
Σ
(HxM(XX,,A())),) 11) - -m+)²
+E hm1p1
11 i2a
RE(1.2)
2²
+ 7m1,
+ sup E
(MIa((), u2)
(32)
11111
X M
Step
But notice that (31) and (32) provide matching lower and upper bounds for pı (M, We can therefore conclude
that
Pi (M, 8*)
E
71.
+ sup E #2
E X M
(DD))
222
11
3
This completes the proof.
26

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
Lemma 7. The expression introduced in Step I. of Lemma 6 and given below constant in
(T) := inf sup E #LEA(SY H2 (61.85)
E Xm M
[b1,2(X,, -22)
[22
22 (7
Remark 1. For convenience, we have defined the quantities 2² (T) and 2² 81) above. We can think of 2 (T) as the best possible estimation error agent can achieve on distribution 2 for particular T and any choice 81 81 E (SSy. (T,
can be thought of as the estimation error agent 1 achieves on distribution 2 for a particular T and choice of strategy $1 &SSY..
Remark 2. Here is an intuitive justification for why we should believe Lemma 7 is true. For any choice of (()) is just some probability distribution that does not depend on μ1, 22 or the data drawn from these distributions. If (Ta) < 2 (T,) for two different values of of lau, means that we were able to achieve a lower estimation error by using X1 D(Ta) than using X1 ((T)). However, because agent can use randomized strategy, they could draw and use data from (TTa) while ignoring any data drawn from (TT)). Therefore, the error achieve should not be subject the value of T. We now this idea prove Lemma 7.
Proof of Lemma 7. Suppose for contradiction that 3r, # To such that 2T(a) < (T)). A priori we do not know that
2² (Ta) is achieved by single choice of 8 E A(S)' so let (89:") nnn be a sequence such that limm- z² (Tas (T ") 2² (T.). 6.n But using this sequence, we can construct a different sequence (s""" "nE defined via (n fb.n fi si
such that
(m1 bm pm M11))
11 a.n S (XT*),
[1, 112 (XT+ S1 (XI"), Ai))
where
(nl n.n
a. and X D(Ta)
This construction samples strategy from stth and then uses data sampled from (TTa) in place of the data sampled from D(T.). But notice that via this construction
22
(Ta,
sup bang
E D(TD(TT)
(X1, A1) n22)²]
X
M
(01 (XI" " f1XT A1) n2)²
sup
Xg Xm... M
(09 .02))
D(T.)
(XiD((rr)
(XT FI - 112)
= sup
E
E (*9 ,et)
Pa
Xg Xg..Xm
x(Ta
(11 (X,, -
-12
= sup E
E
E (xnD((T.)
Na X2...m
x (Ta; 81m1))
This implies that 1im (Tb, 81 81n)) contradiction. Therefore, 21 constant in r.
) = lim 2 (Ta We can therefore say that 2 (Ta) 2 21 (Tt) which is a
G. Technical Results
This section is comprised of technical results that are not relevant to the ideas of the proofs they are used in.
Lemma 8. For all 0
eepp expp(xx²)
exp( xx
Erfe(w) 2
3r
27

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
Proof. First set
((x) Erfe(x) 1
[eppp= x²)
exp( x2)
V
2x
We find that gxxx)
3 3exp( xxx)
Furthermore, since
12
1 eep((=
exp( (xp(-x2)
))
lim
Erfe(x)
V
2x
we conclude that g(x) 2 O.
Lemma 9. Let n be the value of mie after the first while loop but before the second in Algorithm 1. Also let
Th = Ei=1 a then
o²
IND > 4 Ci
= Th > 2
IND
- 1
Proof. We will prove the contrapositive. Since ni,k
0²
+
=4
+ t.nnkin
mm 1==
n
j,k
0²
+ C
i,k
o²
IND i,k
σ²
IND
IND
C.,.
n 1,k
Therefore T3 IND
IND Ri
Lemma 10. Suppose that B satisfies (8). if & V& then n
Proof. Let n. be the corresponding vector returned in Algorithm 1, and let n denote the value of after the first while loop
IND but before the second while loop in Algorithm 1. Since g Vk, we know that WRn + C.
>
1= 2 + (1
We now consider two cases:
IND n = Ni.k: Since n
we have that
i,k
VeLz
IND
2n
C.
IND
+
IND C.
>
m f= n'J
+
> 40,,nn
2
If TrLL # n4.6: We know that N4,4 was changed in loop two, otherwise nh, and 7, would equal since they are equal after
loop one by definition. Because K. was updated in the second loop, know that 72
(n
IND,
where T
> nhe
2
IND 2 IND Therefore 7 (n n
by the definition of Algorithm 1. Lemma 9 tells us that Tk IND
IND Th
In both cases
>
ni. Therefore
nT,5R. as n² is defined in Algorithm 2 to be the value of ñ returned by Algorithm >
2
28

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
Lemma 11. Suppose that ne satisfies (8). Then
Proof. Let ni, the maximum amount data that is individually rational for agent i collect assuming that & the only distribution that is trying estimate. By this definition we have
o²
o²
+
+
IND Ca
= 20 Ve,E
Tii + Σ jos Jik
n s
IND
Therefore C, < Ci,k = Tiikk <
2x
We can now write
voLi
IND L
n
VeLk
1
Thi
2a
2
Ve5,k
IND 12
IND Tist
By definition n 2 B and so
>
which proves the claim.
Lemma 12. Suppose that nB satisfies (8). Let n' be the value of in Algorithm I after the first while loop but before the second while loop. Then
n
Proof. Initially N B B nh = i and so
but may be modified by the first while loop. If n4 is unchanged by the first loop then IND But since n satisfies (8), we > 1.2 nH, is changed by the first loop then 75 becomes ii
ni,
"i n
know by Lemma 11 that
n,
IND
B and
mie In both cases the desired inequality holds.
B 2"
Lemma 13. Suppose that n satisfies (8). Let n* be the value returned by Algorithm 1. Then nig n..
Proof. The final value of ñ will be the value returned for n² in Algorithm 1. Initially na.k ni and is modified (if at all)
in either the first the second while loop. The second while loop only increase 74, from n. to (n!ND)²
so if ñ4
modified by the second while loop we know that
ni
B and so 2. If ñi, is unchanged by either loop then 7i = f,
mie > 1. If R is changed by the first loop then n becomes IND But since n satisfies (8), we know by Lemma 11
IND 1 and
that
ti I In every case the desired inequality holds.
Lemma 14. Let Gi ( be as defined in (12). Then have that
64(n), )3 (CLAM (2h)3 - (2(n - ()²)
G.
(VTia)) )
UB
(T& (T2 - 2n;
Proof. The exponential terms in Gi,k (VTT,N)
cancel giving
UB
(n)
Gi, (Vni.))
4 /
4Tp
160g, Th
- 1 +
VTk
Ti. 2n
(Ih 2n
Tk
mi
881
1/2
1
8m
3/2
-V
-1 +
1+
n
Tk
Tk
2
Tk
(b)
29

---

Collaborative Mcan Estimation Among Heterogeneous Strategic Agents
Now notice that
(a) 4(1 (TT)))
+
(Tx)5/2(T) - 2n 20)
(TT) - 2m, 102
16( (I2 )
(
+ (Ta)5/2(T2: )
(Ta)o/2(TT> 2n, )
Amk.k]
88
1/2
8 3/2)
(6) = -V2
34
Tk
Ts
Ts
1/2
8
3/2
8v 8v2(n )3/2
32v/(m;, )5/2
V2
Tr
2
T
(Tx)3/2
(Tx)5/2
(T)2 - 2m )o
48(m),)) (3/2 3//
2)
(TT) - - 202
(Tx)5/2(1)) - x)2
132TT km
(IT)5/2(1> - 2n, 200 )02
(Ix)5/2(T> 2
24(m),))
(22
(TT) 2n 200
(TT)5/2(T,
20²
(12))
96(m),,) 3//2T
(Tx) 202
(Tx)5/2(Tk k02
16(n),)) 16(m2,))3/2T(( (T)))
32( )/2
(TT) 2n,
(Tk) (T2 2n, )o2
35/2T/00
(2
(Tx) 2
(Tz)5/2(Tk> 2n
The result now follows from
(/((tt (Tu)3 + (2(m (TT)))0²)
(a) + (b)
2)) (Tx)5/2(Tx
Lemma 15. In the context of $H.2 we have that
Opi (ni,))== ==
0² D
40i,k
160 T T.nk
Ci,b
0ng
64a VTnNA
VTk
D2D
4a
To.
+1 -1)
(1
22TErfc
eexp
80
Tk
mi,k
Proof. By the dominated convergence theorem we have
1+
D.
ai N
(m
8ps (nt,k)
+
22
-02
Oni,
Ci.k
(0.10
D..
+ n2,n
ni.k
1-02,
22
30

---

Collaborative Mcan Estimation Among Heterogeneous Strategic Agents
+
207, x²
(ni
1+ "ink
E
+ Ci,E
(0.1)
D
+ 2n
2 x2
"2,4
Di,ea,,
1
+200,
E
+ C2
(mi,) )2
(0.1)
Di.k
2a L + 2)
2
1 + 2a 2,2
4D ( a x,
0²
E
+ Gith
4(
20.1)
Dii + (nt. + +22
0²
14 (Di,K) 4D,,ATT + 2x² + aD
E
+ Ci
4( 2
N(011
(iix + 2 (N + 20
0² 4( 2
DoR 1(77,N 22² + 1a N2
E
1 + DiA
ci
x~N(0.1)
(40 x22 + Th
Tk
2n 402,102
E
1 + Di.
+ +
4( 2
(0,1)
(4a7 + Tx
2
2n
Din
E
+
+
1( 10 )2
1(n 12
N(.1)
40 Aa2 + +Tk)
(4a3, x² + Ths
0²
2n
1
E
+ Cifb
4(1
A(n 12
N 1)
4a (22 +
Tg 1a
16a
(a2 +
Ty.
2
Batt
0²
0²
2n
1
CiK
4(1
)2
A(ni
Di.k
16a
To.
202,
+
4(
d2
Dit
4a,
1
+
16a
2n
Jn
exp
Tk 80
Erfo
(v
8a
Tk
π T
20
20
A(1;,k) )2
d2
ni.k
nēc
Th
Di.k 80 k
4
DiAk
40
4a, Th.
16a
exp
Erfe
(v
20
0²
Da
1
A(n;,)) J2
4at Th
Os 0s. 2T
[4axx
Tk. +1 +1/ - -11
Tx
Te
4
DiAk
TTe
1602,
Th
ni.x
exp
88
Erfe
(V
o²
4avik VTk
16a, ThTTi
- 1 Ci.b
Da,an
σ Di.k
31

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
4
Tk 888
exp
80
Biik
+
-1)
V
(1
Lemma 16. Suppose that (8) is satisfied. Let Tk be as defined in Algorithm I and Di, = Ts 2n If i & Ve and ni >> O then
Du.k R2,
o²
σ²
Tk 8a k
Pi,k (Maz, s*)
exp
Erfc
+ C.M.i
2n
4a
T 2
Proof. By the expression for agent i's penalty for distribution &t given in the proof of Lemma and the result of Lemma 24, have that
Pi.k (Mea., 8*)
1
E
+ Ci
(0,1)
2
1 )22 +
|x,,e++ Z,,x|
o2 ( (1xt,a)
+ C
(0,1)
D,
Ni +m? 0²
634 1,6
22
22
2²
"i
+ C.,ni
(0.1)
D.,k
2n 1.
2=2
o²
0²
E
Ci
1 (0,1)
Dew/ni
+ 20 =d
1 "i,k
0²
E
+ C.
De /// + 2a?
n (0,1)
"i,k
20 22 14
"i
20?
0²
E
+ c,
ni (0.1)
Di.k/ni 2
4a x
Dia 1i
o²
E
ni (0,1)
2
D + 2 +
4a 2² ni,a
0²
o²
E
+ Capafi
2n
2
(0.1)
Di.e/mfi +
tay x² n²
32

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
0²
o²
Dix/nije
+ Ci
2n
2
1 ni
2m11101)
D +2 1.. "i,
+ x
o²
+ Ci
2n
0²
Dijk/ +2
Di.k/n +
4
2
exp
Erfc
2
2
Daufni +2 4u 1.
2
0²
0²
Dia/nix exp
Tk 80
Tk
π
2m
Aa
2
Erfe
(V
Sa
T2
CLA
200
Lemma 17. Suppose that (8) satisfied. Let Tk be as defined in Algorithm 1. if E Vx and ni > 0 then
Pi.k (Mas, 8*) 2ca,((1 + a,,(160, P a (m (-2n + 4T. ) - Thas 4(m +T
2n
Proof. Let Di,k Tk 2m We have already shown that G..((an))) = 0 has solution. Therefore
Tk 8a7,
Th 8
2
2 (1
x 0i
T2kaf D.amnj
16c, e Di.o
exp
Erfe
(V
T2 "ink
T
-1
Substituting this expression into Lemma 16 gives us
Pi,k (Meas s*)
of Di.e
(-1+
4Tr02
16 Thak
02
a²
Th
Di.nni
Di,202
= -i,nni, +
2n
1+
Tv
2m Thack
-1
Th
1
a D V
Th
-1
Di,en
4Tra2
180,,nnf, Te
De.022
02
o²
2n1
1 n
Thang
-1
Th
(a)
where we have the following expression for (*)
/
DDi + Maatuo" - 160; No Tha
TI
1(1 (1+ n
-Thar
NTc
33

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
L Ta
-DiiNo²+ + Too 16
Pia
vT (-Traa,nii + +d(nix + +
(DDaROPnG + +ITra],00
Teoi + 4(1,, + TT))a
(16eL)(n,,) ( Thaa (D - 4T
ai,
-mi Thoik + A(mi, + +Ta)a
ai, (16e))(M),)) T + (nt,x (-2ni, Tis) 2
-n TROik + 4(1,,, + +Tz)aa,,
Substituting in this expression for (+) gives the desired result.
Lemma 18. The following two expressions are equal
20, (1i,)) o² + ank ( + (n] 2n%,k) - 2
Th "i, (20, k Tk + 02)
-i,n Th + 4(m + T2)
(1(2 6c,, 6c,,KoT +02)
(ccK(n ( 2( 2(1 (11) 02
(nfix + Th (2) To 02)
(ni, m Th 4 4T n1 Tk 02)
Proof. Via a sequence of algebraic manipulations, we have that
20 (ni,( 02+ aik (16c2A(nh ) Tha + (Mi - 2m 4TRRZx)0*
T₁ n n Th + 0²)
0²
- - Thaki + 4(n + +Ti))aa
+ Ts )2
Th (16)) TTaaf + (nt (Tx 2m ATT 022)
+
(2c Th + 02)
ni (20 To +
(-n 4 (nt. + Tx)) a3,1k
Th
(2 +22
fi + Tk)
(20LAM Tk 0
nixxTh
(160), ( Thaa + (ni,e (Th- -2n(x) ATTaaR 0²
Tk
(NE + Thk)
+Th)
(-mi Th + 4mixaa, + 4Tka3, (20 Th + 02)
Tk (20xx (ni.,)) o22
Te (2cs (n 12+2)+++ +
+
ni, + Ts)
223,,nn i The + 02)
ni,x + Tsk) Ai R Tk + 02
Ti
(1+ mixx)
To
(16CL. ( PRaRZ + (niw (Ih - 2n - 4lha? 02)
ni + Th.)
(-n, + an + +4TRa?,
(20 + 022 (2c, +02) nin
Th (0,, + 6ei Ta +0²2
Th - -6C, TB
(33)
nt, + +Th (2c,,nt To +
niN +Tx) (2c Th +
Tk
[ +1+ mix
Jk
(16C1, (n (Mt + (nix (Th 1 -2n1,K) - 4Tku? 0²)
(34)
ni + Tis) (-nt, Ts
4TRaG,)
(20HAnt + 022
34

---

Collaborative Mcan Estimation Among Heterogeneous Strategic Agents
Notice that can rewrite line (34) as
Tk + mi,x/
Tk.
) ( (16L + (ni, (Th. -2miik - 4Tka2,t) 02)
n + Tis
-nn Th + +4 + +4Tha2i, (20, To + 02)
(1+ ni,y
I
(m " - -TF
ni, + Tkk
(-nt Ti Th + An aN, + 4TKal;)) (2c,amt Tk + 02)
( +
Te
(Tenie (Th -1m( 02)
mi
+
n + Tx)
(-ni,e + Of + +4Th03, (,k)
(20, Tk + 02)
(1+
( - 42fa
m7,2
n/. + Th)
-i + 4m ol + 4Tr02;) (20 Th 02)
ni,TTo" 2(m Tho 2= + T3 TTs (2--21(,)) 0²
+ 7i + +Tx)
(-mi, 4n a + 4Taa3,) (2ci To + 0?)
(1+
Te mi,a
(16CL (m TT 17Z07,000)
n + Tkk)
TT + 4m 1,k + (Taa (2cr,m, Ta + t02)
4G.u(1I 22 - 2(m x 22k0²² - -ni Tho?
+
n7,x + Tx))
(- Tk + An 0Z, + +4Tha7,)
(20r Th + 02)
- -4 x) 1 + T2202
7i, + Ts)
(-mi, Ta + 4n a + 4Ta03,
(203.m7 Th + 02)
Substituting in this expression, we have that lines (33) and (34) become
To (2 )2 + 6c,, + o²)
ni,N + +bb) (2c,, The + o²)
Ac,,A(n/,, PTT 2( 2(1Ete) Tho2
1N + TTx)
(-n, nT + 4n 4lhaa, (2cr Th + 02)
GeLuni +
TE nitu
(20))(
+
(35)
mi,K + Th)
(2cummt 02)
(1+
Th mite))
(160a,(m1, ( 4TTa2
+
(36)
"T,x + Th))
(- + 4n un,, 0r 44Traf,)) (20,.mn To + +02)
(n,, 2T + ON202
+
(37)
"T,x + +Tx)
(-nt, Th + 4n 0 + 4TRa33, ) (20,,en Tk + +02)
Now notice that we can show lines (35), (36), and (37) sum to 0 then we are done with the proof. We can rewrite the sum of these three lines as
(- Acc.nn TRo²) (- (-nt,Th + a2, + 4Tkaa,))
ni,e + Ts) (-nt Te + 4n 4TrO33 (2cr.mn,e Th + 02)
35

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
(I+ I mi,x
(n 4TZa
ni + Ikk
(-n Th + 4m ai + 4Tka3,
( + 0²2
Ae x 2T + TØO0²
ni,x + Tik
( + 4m a. + 4Tka,,2
i + t²2
(nT,k + T()
(-n Th + a + 4Tr,02 (201,n + o2)
TRo2
Ac,,,,,, T
(-ni,Th + an + 4Tnaa,)
(38)
ki
Tk 1
( 4TZal,007) - (ni,k) 2 + Too²
(39)
We will conclude by showing that lines (38) and (39) sum to 0 which will complete the proof.
1202
Aec.,mn +
(-ni + An + 4Thaa,
mi,k
Tk:
+
1
(10c) (m
(Tak) TEa
4Tz - -4,,,((1,,)) + +TO00
mi,k/
= (m,,)) 16G, (1 RRR
4TR020
- -200² + 4T200a², +
m
+ +100g,(m 2
4T x2
+ 16c Tx T2a
ni.
(ni TT + TRO0
= 0
Lemma 19. The The following expressions are equal
aik (1T,) + (n, (Tx - -2m - -DTTTKaai 4Traa
Tk
(n1,( + +0²
n2
-ni Thaik 4(1i, Tx.
Th (2cs,A (ni, +2 66, 7 66,, +02)
4c,a ) (TT)) x2 -
-n - 202
(ni, + T2)
(nt + Tx)( n To + a + 4T 202
Proof. Via a sequence algebraic manipulations, we have that
ait (160,, ? + (n - -2 k) - 4T 42
Tk n 0²2002
20( 02
-n Thaai 1(17,a +Tx)a
Tk (20, (20,, 02)
Th (16CL PRROZ (ntx (Th 221;,2 mi,k (-nt + ni, + Ts a² 02
-ATRaZ 0²)
+
0²
36

---

Collaborative Mcan Estimation Among Heterogeneous Strategic Agents
Th T
(20 00²
Min + Tis 0²
(( nile
(160))(M7, ( TRO + (mix (Th -m ) - 4TRaZ 02) )22)
Th
Ni,K + Tb)
-n + an + 4Tk03,1 0²
Tk
20 (
x²2)
T2
(2 +02)
n Tss 0²
ni + Tb) 02
Th 1 + miKk)
(1602,(1 (n,,, Tha., +
(ni. (Te-2n1)) 4Tha2 00)
+
ni + +Tk) (-n7, Tk
An a -4TR03H) 02
Tk (20,,(((, )2 + Ge,,MM Th 022
+ -6 + I2
(2cr 02²)
mie
(40)
ni, + TT))0r 0²
(nix Th) 0²
To 1 +
Tx
(1601, 2 + (nix (Ts 2m1
44Traz,) 0²)
Rikk
(41)
"i,x + Tx)
(-n3, To + u + (ThaZ, 0²
Notice that we can rewrite line (41) as
The 1 +
Th. 7T,k)
166,,,nn ( + (ni (Th. 2n1,a)
4TruZtt 022
TT + Tx)
(-nt Th + 4n oi. k:
+ +4Txa 4TTa03, 0²
1 + m
Tz
(16)). () 22Raa, - aTz0a,
(1+
Tz. m,,
(Tanī (T (Th- 2n -2 02)
+
n + Ty
(n -4n + x4TraZ,
02
FiA + Ts)
ni + 4 + +4Txa1
0²
+ mi,x/
Tv
(16G) ( PTaa - aT
ThoT -
2 2 + T TT - 2n
0²
1 + Tis
-- 4n 0.. + 44TraZ
02
1h, + Tss)
(ni + Ant +4T 4Txxa, 2
2,
0²
+ wi.u
Tr)
(16cL.(mt, )) PTaCI - 4TT22,002)
4 40 2( ) T - TRo2
+
# + The
(-mi, Th An, + 44TraG,
02
11, + Ts)
(-mi, To + 4n 4TRo2,, 02
(c,, TT + Tgo²
+
ni + Th
(-ni Th + 4m aZ + 4Tra?, 0²
Substituting in this expression, we have that lines (40) and (41) become
Tk (m),)) )2 + 6eg,En Tk + x²)
4ct.(ni -2(m5,,) T2r n Tx
+
mi + Th) (2)))-nn). (-mq + an + 4T<00 02
ni Th. 02
T2 (2cc,(nt,)) +z2)
mia
(42)
ni, +TTx) 02
[1 + miax
I2)
(16c),(0t TTxa 4T ATRaZ
+
(43)
ni,s + To)
(-nt Ts + un, + ATRUZ 02
37

---

Collaborative Mcan Estimation Among Heterogeneous Strategic Agents
(n 2
2 + TR
(44)
niA + Ts) (- (-mi, Th + A a2 + 4Tra 0²
Now notice that if we can show lines (42), (43), and (44) sum to 0 then we are done with the proof. We can rewrite the sum of these three lines as
TRo2 miK
(- (-n + o + (TTaa;
1. +
ni, + Thx)
(-ni,eTh + Ami 00, 4Tk00 (.k 02
1
Te
(66,,((7, ( TTTh,, - a 02
+
ni, + Tx)
Th + 4m aZ + 4Tkaa i,k)
02
Ac,u(mi 2 TRO²
+
n1,5 + Tik
Th + 4n aZ + 4lka,,, 02
(nT + Te)
(- Tk + Amj + +4TkO(() 0²
((-AA 12 +
TEo"
x
(-niAeTh + an, + (T
(45)
Tk 1+
(1t,) - 4TZaZ0007 - 40 2 + T/o²
(46)
n
We will conclude by showing that lines (45) and (46) sum to O which will complete the proof.
T20²
Ac +
(-nigThh + an + (TTaa
Tk. + 1
(1665, ( TTO
47 o7 - -4c2
(n TT + +TR02
ni,k/
-c,((n 2T 16c,, (n,,)) "
2
n6,
- -ngo² + -1120 + 4T
+ +10r, 02 - 2T
+ T2 a
n
40,x TT + Tg
0
Lemma 20. Let ai.k / V Then
Th (2c,,, + 60, 6ct, Th + 02)
(nt,) - -2
TToo² 2
n2, (T2)
(ni, + (2)) To + 02)
(ni + Tw)(-nt, Ta + +4ni, + + +22
2Tx (cLAnG. (Ani + 11Th)) + + (20s,nn, Ts + 02)
-(ant, + +3Tx)
38

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
Proof. Via a sequence of algebraic manipulations, we have
Th (22 + 6G, 6ci,nn 02)
40,, (c 2(m - m (TE)
(nt, + +k)
20 Th + 022) (nt + Th)( (-n,- a + 4n, 03 + 4T,a? i + 0²)
(4m3, +33% Tx (20,, + 60, Th + +
(TI,)
40, (T - 2( " - n (Tx)202
(4mj, + +37x) (25, To 0²)
(ni, + Ta)m (4n + 37x) [20,,011 Th + +
(+37,)+
Th (2, 6o,,n 02)
FIE (4c. (Tbb) - 2 )2x0²² - n (Tx)²
(An + +37k) (20, d²)
(An 3T(e) 2 Tx 02²)
(TT,+
(Ami, + 3Tk) T (20r &
(4m + +3%))
20 Tk + 02)
+ Tc - Tno - TR002
1
(Te,
(m),)(1 Th + 30c (1 + 2 + 220 + 2TT02)
(4n k + 3Tk)
n2 02)
(T7,+
(2TH (nt, + Tk) (cr,ntu (Ant, + 11Tx) + +0²))
(4mi, + +3Tx
2,, Ths 02)
2Tk (CLuntt
(Ant + +11Tx) + 0²
(Am + +T3x
(20 Tk o2)
Lemma 21. Let ai,k V Then
Ty (2C )2 + 6c,,ant, + 02)
(e 2(n 2 n2 P02 (n7,e + Tx)(-n Th Th + 4n NZ, 4TkaG )²
(ntx T2)o²
2Tx ( (Ami, + 11Th)) + +02)
Ang, + +3T% 02
Proof. Via a sequence of algebraic manipulations, we have
Th (2 ) Ge, Ta + o2)
(n ((Tk)3 2(n 22 T2x0² (T&) 222
(nt, Tx)o22
(mi, + +T)( + 4n 07, + 47 ( )000
(4nj,
Ta (20r, (mi,))) Gei,nn Th +02) [n],+TTe]
4ca (n (2(Th)² 2( ) 2 1
+
(4m1, + 3Tk)02
(ni, + Tw)mi (41 + +3Tx
(337,) (TT,
Th (20r, (n5,,)) 2² + Gei,nn 0z)
+ tT, (4ccu(nt,)) ((T)) - -2(n (4m + 322
( TTo0² -n ni, (Tx)222)
(4n/, + 3Tx)02
(Th (4m;, + +3
(Ani + 3TT) T (20x,(1(,,)) Ges To + o²) + To 2n - TEoo2
39

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
(T))
(An + +T2 (Sera Th + 30cs, (m),)) T3 x + 22 TØ + 2T
(T))
( + +73 (2Th (ni, + Th) (ca,ente (An), 11Th) + +o²))
2T% (cruni, (4nT, + 11Th) + +
(4ni, + 3Tx)o²
H. Results based on other work
This section presents the proof of lemmas related to creenive-oompatibiiity.. As we use a similar corruption strategy to Chen al. (2023), the high-level proof ideas are similar to theirs. However, adapting specific techniques to unequal costs requires nontrivial algebraic adaptations.
H.1. Proof of Lemma 3
In Algorithm we have specified the information set space for Mear. to be Rd, which corresponds to d estimates of the distributions. We could have defined an equivalent mechanism where the information set space is D D x Rd and 7, (7,,,---- (.a) where T [z, Z', n²²). In this setup Z is clean data, Z' is corrupted data, and r/2 is the amount of define the following sets characterize the types of information
noise added to obtain Z'. For the sake of convenience, sets i receives for each distribution. We also specify the information sets provided under this alternative information set space.
A = {k: : E Vi
if E then L1, = (0,0,
B = [k:n, = 0 and g V
if E B then Ti,k = (Yi,,, 8,0)
C = { : ni 0 and i V
if k C' then Lip (Zi Zi,,, me,k)
Under this change, we would now recommend agent to use the estimator
EVEX, V (o=+n ( )i1
Σ=Ezi
he (X,, Y,, 1))
/ 1 Z4,1| U.
o²4ni 77/a1
instead of directly accepting estimates directly from the mechanism. In fact, Chen et al. (2023) use the single variable version of this exact information set space. Notice that in this setup agents receive more information since, in each case, the estimate recommended by Mas. is function of (Z, Z', .7²). In the proof of this lemma, we will show that if agent i has access to I = (z, 2', ,)²)) then it is optimal to submit data truthfully and compute the same estimates that are returned by Mau. Therefore, when I d and the agent only receives recommended estimates in place of (Z,Z', 2',2,,n")) n?"). the agent will achieve the same penalty by submitting truthfully and accepting the estimates of the mechanism, even when they now receive less information. This will imply that submitting truthfully and accepting estimates from the mechanism is the optimal strategy in the information set space I = pdd. We now present an argument of this claim, adapting the proof of Lemma 5 from Chen al. (2023).
Step 1. First, we construct a sequence of multivariable prior distributions (Achezi for μ E Rd and calculate the sequence of Bayesian risks under the prior distributions
inf E ESASSY
E (s(.ee))
E Me..
hhs
Yi, Y. 13) -m12
e21
arde
Here A(SY is the set of strategies where i collects the same amount of data as in i.e. A(SY = ((k = of E ASS) nl n, J.
40

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
Step 2. Next, we define to be the randomized strategy given by (14, Vi, (Q). We then show that
lim R2 8030
sup
E
[lle (X,, Vi, 1,) pa
(aLvet))
Step 3. Finally, using that the Bayesian risk a lower bound on the maximum risk, we conclude that amongst the strategies in A(S), 8; is minimax optimal. Thus, an agent will suffer no worse of an error when using fi =f and h4 = hi regardless of the distribution
ni.
Step 1. (Bounding the Bayes' risk under the sequence of priors) We will use sequence of multivariable normal priors
Ag := :> (0, eT) for 2 1. Notice that for an agent i, the mechanism returns an uncorrupted estimate for distribution & i E V/2 or _ = and a corrupted estimate otherwise. More specifically, if i Va an uncorrupted estimate using only Yú,: returned whereas if n
uncorrupted estimate using Y-,, returned.
Fix some F. We now analyze the optimal choice for ha,k depending whether is is in A, B, or C.
Suppose that A: E A. Recall that æ 14h ~ (pu, o²), Va E Xi Since k E A, Ie,A is just function of Xi,k no other data from the other agents is given. Therefore, the posterior distribution for μa conditioned on Xi,k Yi,es Li, can be written as MM xi Ye Ii = P4 Xi Furthermore, it is well known (See Example 1.14 in Chapter of (Lehmann Casella, 2006)) that ju Xi,k ~ N (MA.AA.O...
where
F (Xi,s)
1 [xyal +
PARK = N. o
14
[x
+
+
Therefore, 14 Xi,k, Vi,, li ~ N (NA.EK. )AA...)
If k B then agent receives Y regardless of what they submit. Again, know from (Lehmann & Casella, 2006) that 14 Xi,k, Ye,e, li,k N (KB.CK, BB..)) where
PBILk =
XeALY 02
Mk +
SM (Xi, UY
B. = X1,
+
+ 1
0²
E: we have that
x I us ~ N -N 0?) Vo E Xi,k U Zi,k x. Mk. nh N (wz, 0² nhx)) Va E Zi,k
Recall that n is function of Yr, and Zr Assume for now that Xt, is fixed. Under this assumption, and having fixed fir both Y and v² are deterministic functions of X5,k and Zi Therefore, the posterior distribution for b conditioned on (Xi,, Ye,o, T,,)) can be calculated as follows:
P (Junl Xa.k Yo, Te,x) = (nx YL,, Zi,k 21 p.xx) = Ki.ks Zede Z, (MA,, Xi,k, Zi,k, Zi,x) I Zik (b) (XiL, Zi.k (14e) p(1n))
(Z [X Zi,ki (44) (X ) (Z p(14)
o exp
2222 + nH
1
Σ
(x - 2
exp
20
1
Σ
(x (x)²
exp
282
1
2
=EX;,UUZi,
7
Xi,kl + Z
1
Σ 2
ExEx,,
exp
2
exp
2
+
22
o²
02 1

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
)) x exp
exp
0 C,e,k
xxx
20
(us M.C.E)))
where
ExERt, EOExIUULLE
0244%
and cee.k =
P.C.kk =
[.
IX +
X
2
We can therefore conclude that (despite the non i..d nature of the data), the posterior distribution of μa conditioned on Xi,k, Yi,k Li,k, assuming Xi,-k is fixed, is Gaussian with mean and variance as given above, i.e.
Pk Xi,ss Yi,,, Li ~ N (pc,e, C.,..)
Next, following standard steps (See Corollary 1.2 in Chapter 4 of (Lehmann Casella, 2006)), we know that Exs (be, (X,, Yi,4,) 2x)2 Ki, Yik. 4.,0 is minimized when
h (X Yo, T.) = E [et PR
X Ye Te.e]
When Xi assumed be fixed, Exs juk Xi, Y,, 4.,ll P.C.A. This shows that for any fi F and fixed X1 the optimal h is simply the posterior mean of μa under the prior A₃ conditioned on (Xi,s, Yi,k,
We have now derived our optimal choices for hi, (either M.A.A (,B.,k, (.C..)) depending on whether & E A, k E B, or k E C. Going forward, we will also use f. and h2 to denote probability distributions over F and H. respectively. For some fixed ft E A(F), we can rewrite the minimum average risk over h2 E ((H)) by switching the order of expectation:
inf NEEA(H) prdrr ((onn.)dhe))et)
[l (X,, Y., (1,44) 44) -vll?
Man
inf hEA((1) wañe
E
E (ines
E McMe
(bi.k (X,, Yi, I2) - m1m
in
E
(he (X,, 14) -1m2 2 X,, Z, 2/
hNEA(H)))))
k=1 (Reifeshe)
X
inf h.E)(H))
E Ne
(47)
(me.fe.tee)
IE [(hs, (X,, mmm? X1,,, Ze,ko Mi,k]
Xi Zo Zz Hab
(48)
Pkk
Substituting the appropriate posterior depending on whether A, B, or tell us that equation in lines (47) and (48) is bounded below by
Σ K
E (Nt..f))
E Kin
E
E (pA.e-
px)2
X Zak. Zi,al
Xirks Zt Zy |عا
Σ
E
B
E
E (uBBe ma) Xi,k Ze,ks 71,1] Xi,k, Zo, 7z P
KEB (ne.fe)
X Zrinki R th
Xe, 2e n mi
E
E Ri itii
E Zu
E
- ) Xa,i Ze, 2.al
Xi, Zr 2e
REC
42

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
EE E
E
E
E
E
E
REA (me.fe)
X ii Sa
2,,
[x a2
(na.ff)
X1,k. 2,
82
KEB
0²
82
(49)
Σ E (neife)
E
(50)
N1 Ze Zi Z
[x, 11.11122.11
kEC
Now notice that if k E A or k E B then li does not depend on Yi,6 so lines (49) and (50) become
E Ri,k
E
(51)
X.ck
B R5.6
+
Σ E
E
(52)
AEC (na.d))
X
[
+
o--1i
0²
Since n depends on pik: Xi,ki Xy,ke Ze Xil, Lo, and
Zi but not Zi nor Di we can write (51) and (52) as
Σ
E
(53)
Xi,k
ke
72
ke B
+
E M.r.X..kk
(54)
(m..fi)
Xi,
3 o"+"i,
The second to last step follows from the fact that if k E A or E B then Lis does not depend on Yı,- Notice that the terms in (53) do not depend on fo whereas the terms in (54) do. We will now show that (54) (and thus the entire equation) is minimized for the following choice of which shrinks each point in X, by an amount that depends on the prior Ag:
fx,(X,))
Va E XIR
(55)
X o²
22
To prove this, first define the following quantities:
M(X.,)
Σ x
((Yi.)
Σ "
((Za,))
Σ
Y
zEX.
yEY.,
sEZi,k
We will also find it useful express nh as follows (here as is as defined in (11)):
The = - (f((s,)) x)
The following calculations show that, conditioned on XI,., T7 Z((z.)) fa and μa Gaussian random variables:
[X.u//o ((x.,)) are independent
IX.ul/o²
( Pk Ma X x (P((z,)) - Mk: Pk. Xi,k)
P (i..) Mk,, Xi p(ux) (M( pa (ul))) (Xexllu) p(ux)
(-1 1 1|
exp
(-2 o²
(0((z.,)) -4a))
exp
Σ
(a- uu)²
exp
202 M
20"
xEXi
43

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
&2 x exp (- (-2 o² (T(Zz,k) 14k))
[
1x /02 [ + 1/ 1/22 ((xx))
21
exp
σ²
+
82
14k
xxsue 1o2
( ((X.))))
ocp
10241/121
Thus, conditioning on X, we can write
(ZZa, Pb
~N ((0)
o²
7ic
0
X /221/22
which leads us to
/o2 /x + 1/2 M (i,k)
x²
(ZZi,)
Kit
Xix
N
0,
+
[ o02 1/12
=.0..
Next, we rewrite the squared difference in v as follows:
Th.
(T((..)) - -T()))((()))) {)()),)))
|x,x//0* /02
|xxAl/O22 Xoul//² + 1/E2 (X2,k) -V(V..)
((ZZ,)) Xi,u//O + 1/22 (x,x)++
(56)
=0,,00
=x((Xe,.fi)
Here we observe that the first part of the RHS above is equal to de. where e is noise e X ~ NO, 1) where θg.u defined in (56). For brevity, we denote the second part of the RHS as ((X,,,s, h,,k) which intuitively characterizes the difference between Xr, and Y.,. Importantly, ((Xx,,, hi, 0 when fa is chosen be (55). Using e and é, we can rewrite each term in (54) using conditional expectation.
E fc)
E
E X.
p.k
X
12
1Zenl
o2+1
= E (m:
E
E
E
M.k k
X:
Ze.u N
2
+
o=
22
= E (i)
E
E
E
M.b X
x,x
2
1x Zo.kl
x2 20
(o (0 ( (X
0²
exp
2
de
2
E (m:.f)
E
(57)
Xx
1 o a 32 (e+ oix
Xx,
/2
000
::Pa(e)
where we use the fact that e Xs,* ~ N0, 1) in the last step. To proceed, we will consider the inner expectation in the RHS above. For any fixed X.R. Fi.6 (.) (as marked on the RHS) an even function that monotonically increases on [0, oo)
44

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
bounded by Zi,l and F2(+) (as marked the RHS) is even function that monotonically decreases [0, x)). That means, for any a IR,
(la(e-o)Fale - [ [1i + Zs
Fe(e)de= [1, + 11,zl
< <000
By Lemma 23, we have
Fia(e + O fu) / F1x)())F((edde
(58)
the equality is achieved when o(Xik f In particular, the equality holds when fú, is chosen specified in (55).
Now, to complete Step 1, we combine (53)/554), (57), and (58) to obtain
inf (.E
JE pords
E
[1], (X,, Yz, 4.) =1112
MoB
1
[xc o7
Ri.k
+
Pick
+
B2
((Xi, li,ts)
E
E (U.kiX.,
E
Fi,
c
F Fe(e)de
(mi.ft)
Xi.k
Tek
kEC
E
E na.k
Fi,e (e) Pa(e)de
(59)
X 5²
XENUY
REA
KEB
7
REC
Here the inner most expectations the last summation are dropped as Fi,s only depends on [. Zi,kl, and [Z but their instantiations. Using (59), we can rewrite the Bayes risk under any prior Aę as:
R4 = inf inf
E
E
[llke (Xi, Y,, 12) - m16]]
5, of <EEASS Ar
(th)et))
ManL
1
E
E
E
Fi, (e) F2(e)de
X
kEA
Diuk
2
ke B
nlckk
22
kec
-00
1
E
E
X
X.,EU o²
KEA
KEB
ni.k
22
E
KEC
Rick
(0.1
Xexl+12un1
o²
Because all the terms inside the expectations are bounded and lime convergence to show that
02
[X,,el
12 we can use dominated
g²
0²
R = lim R
=
E mi.k
E
E00
REA
KE
mi.k
X1,a
U
Σ
(60)
1x, H Zi,e|
REC
+
o²
o2+a
c2
x
2..0
45

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
Step 2. (Maximum risk of 8,) Define 8 be the randomized strategy given by (n4 fi, h2)) Recall that ny is the randomized distribution over how much data is collected. Thus, 8 is the strategy always submits data truthfully and uses the suggested estimator while following the same data collection strategy as 8;.
We will now compute the maximum risk of & and show that it is equal to the RHS of (60). First note that we can write,
((,),,)) pi
(()
M
0
By a linear transformation of this Gaussian vector, we obtain
(
1k) (f(X2,))
+
T7(
12,,o
0²
(Ti (. (46)
=
[x
72
1
12,al
-1
r²
(p(Xi,,) -
(TZi,k) p4l
146
0
0²
0
a²
+
12
o²
which means o²h random variables. Therefore, the maximum risk of 8 is:
|Neal (f((*,A))
7.
(T Zi,x) (xx)
and
Bi.k O..k
((xx))))))))))))))))))()))))(( -T(Z(s)) are independent Gaussian
sup E PERd
E MOBL
[11k (X,, Xi, - 1=]2]] -1111
(#i,e")
sup J
J M.ME
E(e (X,, 1,, pxx22 2
(hii (X,,Y,,1) -MN)²
Σ
E(hi
(hi, (X4, L., -ma)
nER Rd R.
KEA
KEB
REC
sup
TE McBL
Σ (f(X,,k) - pp))2
Σ
(A(XEA UY..)) pkx)+ 2 Σ
(hi, (Xi, 12) )mm)?
WERd
REA
REC
a²
o²
sup WERA
E
E Mest
Σ REA
Σ KEB
+ REC
Σ Chin (X,, 2
XI, UYLl
ΣΣ REA
+
Σ
E
sup E E WER" Di McBL
(ha. (X,, Y,,,Y, V,, Ii) mx)²
(61)
X
KEB
LEE
Now notice that we can rewrite the last summation, given (61), as:
E
E
Σ
(hi. (X,, Y..Y, =2x)
HERd R. P. MEBL
LEEO
sup
E.
[(heR (X,, 1, mx)
pERd KEC
as
MoBt.
((Z
(Z.. 0²
X
sup
E
E
E
12
HER
Wh.k
(a(Z) x) -14 |
(8(2..))))) -
(D(X..)
+
02
sup
E
E
IE
Th.kk
PERd
KEC
Ai.k
Ziuu
[Z.AUXEN 0²
o2+
2
) + pe))
E
o²
17.
Σ
sup
E
E
PER
KEC
7
Z
46

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
Zau (02 + nīxs)
[iidl +
[Zz,A
Σ REC
= sup
E Rock
E
PER
77,
(o2 n2.10)
x²
Σ E
E
KEC
0 +-
0²
Σ E
24 xu 6²
REC
0 2 N (1) X. x.x) ((2
Σ E
E
(0,(0,11)
REC
+
0²
2240
o2
o2
k.
Here the last line follows from the fact that (x(x,,)) line (61) we get
-T(ZZi,)) ~ N (0,
d²
o² (2,e)
Substituting this expression into
[x,
0² [iik
o²
sup E
E MeBL
[14, (X,, Y,, 1))
+
E
(62)
pERd
(B..8t,)
REA
k
Ri,h
X1, UYK
Σ keC
E
(63)
Ai.k
(oN(
+
o²
o2+a
x2
o2
2,,
X..k
Roo
Here, we have observed that the final expression in the above equation is exactly the same as the Bayes risk in the limit (60) from Step
Step 3. (Minimax optimality of 8,) As the maximum is larger than the average, we can write, for any prior Ae and any
of E (S))
sup E HERd (s/,et)
[1 (X.,Y,
ml]2]] >
E. La.
[1 (X,, Yr, 4.) -11
z R
Mest
w~rr
As this is true for all L, taking the limit, we have that Vs! E A(S)'
sup I HERd (s1.42)
[1 (X,, Y., 1.) 1 ml
Rro
sup E HERd (3..2t)
[1]bs (X,, 1.) -=1la]
that is, 3; = (ni, fC, (T) has smaller maximum risk than any other s E A(S).
H.2. Proof of Lemma 4
Since we are assuming that Ji = fi, by h2. we have that
Pi = Pi (Meas ((ns, fi, h()) s())
47

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
sup nERd
I (Neaete)
E M.MMaoL
[llk; (X,, Y2, 14)
Ci
k=
E
+ sup E PERE (s..5.)
E MesMe
[1
(Xi, V1, 1.) - 1112
(ol.e%)
Since - penalty as
h we can use the expression we calculated for the maximum risk in lines (62) and (63) to rewrite the
o²
Pr
+
E Ri,k
Σ
E
[Xi,
kE
A
REB
Mi,k
Σ REC
E
E
Ri.
12.
o2+a,
22
22
Xi.N
o²
σ²
Σ
Σ
E
C2,
DiRk
ke
Ri.k
[Ki,
Y
Σ
Ci
(o.1)
kEC
o2+a?e
2²
a2
σ²
σ²
2 Σ
min mit
+
+
min mik
+ G...likkk
Xi
REA
REB
+ Σ nikk
min
E c.A110.1)
+ C
Lu.uX o²
KEC
0 +
x2
x2 [x,0|
21
To minimize this entire quantity, we minimize each of the terms, making use of the fact that these terms are all separable and each only depend on one of n,,1...., Aj,d- We do this by cases, depending on whether l is in A, B, C.
If l E A, then know that by definition
argmin PA.
+ C.EMi, = argmin
IND + G. = n
Xi,k
74.
Furthermore, since A, n
n,k by the definition given in (9).
If E B, then n O. We know that Y Tk by the definition of Algorithm 1. Since & Ve, Lemma 9 tells that IND and Y4,x > n Therefore, the cost for agent to collect more data is not offset by the marginal Tr > 2n > n decrease estimation error due this extra data. This means that
argmin Ri
argmin R..
G.ARiA 0
X.AUY.
nik + |
Furthermore, since B, n by the definition given in (9).
48

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
If k E C, then more work required to show that
1
argmim 74,
+ C.
ni
e0,1)
o
o²
+
o2
Let D = Tk - 2n
Now notice that
1
min Ra,k
E (o,1)
1
|1,1++12..1
0
x2
5²
12
min A,,
Ri,k
(64)
(0,11
DiA
0²
22
"1.
1.k
We will now show that / convex in ni,
Di,
0 2.
Di
+
Pi,k
1
+
"1
n1
14
Rick mith
Inikk, 02,k) -
Ōmi,k
2
2
Di.
D,,t
+ TTikk + 1i
+ Riik
n
Itaf,
I+a
"1,k +
We have that on., (ni,k, x;; ((.kk) is an increasing function and thus I (ni,k, I;; (ii,k) ) convex. Because taking expectation preserves convexity (see Lemma 22), the penalty term as a whole is convex. By Lemma 15 we have that
0p: (ni,k) Onik
D²
4ai, VTr
64a
Ven
DEANG
1
Ci.
r2 o2Di,k
Tk
[aa
Tk ni
+ 1 -1)
(V
Th. V88,,
exp
80
Tk
Now notice that the right hand term has a factor of (u,,( This means that (64) is minimized when nic = ni Thus, by combining our analyses for when &s E A, B C, conclude that pt is minimized when ni, n
Known results
In this section, we will state known results that are either used directly or with minimal modifications.
Lemma 22. Let Y be random variable and f IR² + R be a function for which f(z, Y) is convex in a and Vr E R, E[f(z, Y)ll < oc. Then E [f Y) is also convex in x.
Proof. For all 31, 22 and E [0, 1] we have
f (znt + ==(1-1), < ((t,,)) (1) Y)] ())(1
Elf (1
t),
49

---

Collaborative Mean Estimation Among Heterogeneous Strategic Agents
Lemma 23 (Chen al. (2023) (A corollary of Hardy--inllewool).. Let f. g be nonnegative even functions such that,
f is monotonically increasing on [0, oo).
g monotonically decreasing on [0, so), and has a finite integral Jg g(x)dr
Va, f( - a)g(2)do (z)))) oc.
Then for all
J [())(())d / J( a)g(d)d
Lemma 24 (Chen et al. (2023)). For all 2 and some I. > 0, define
1
I(t)
exp (-tx²) de
-00 + x² 2
J(I)
exp (-tx²) dr.
(T. + x²
2T
Then we have
π
((t) exp(Lt)Erfc( Lt),
2L
1
-1) exp(Ld)Erfe(( LVI
Ll) + Vt V2L'
J(I)= V 2T.
2T.
50


Reviews:
[{"review_id": "AJjwaGZc7i", "reviewer": "Reviewer_MzVR", "summary": "This paper studies collaborative learning among multiple heterogeneous strategic agents.  There is a $d$ dimensional isotropic Gaussian with an unknown mean.  Each agent has a cost to derive a sample for each coordinate of the Gaussian, but also wants to reduce the square error of mean estimation.  The paper wants to design a mechanism that recommends the number of samples for each agent and returns some information for each agent.  An ideal mechanism should minimize the social cost, be individually rational (willing to participate), and be incentive compatible (e.g., truthful reporting).  The paper provides a mechanism that has a Nash equilibrium that minimizes social cost under IR constraint and further $O(\\sqrt{m})$ approximation ratio to the minimum social cost without IR constraint.  The paper further shows that their mechanism can enforce different recommended numbers of samples to tailor objectives other than social cost.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your response and questions.\n\n**Essential References Not Discussed:**\nThank you for the suggestions. We will update the paper to include this reference.\n\n**Other Strengths And Weaknesses:**\n- *Comparisons with Chen et al. 2023:* \nWe would like to emphasize the two (orthogonal) challenges that need to be tackled to incentivize truthful contributions while maintaining an efficient system.\n    (1) The first (addressed by Chen et al.), is to design methods to validate an agent's submission using others' data. Their approach compares an agent's data to others' submissions and ensures a Nash equilibrium (NE) where everyone submits truthfully.\n    (2) The second, **not addressed by Chen et al.** and the focus of this paper, is to ensure that there is enough data from *all* agents so that *each* agent's submission can be sufficiently validated against the others, without compromising on efficiency (social penalty).\n\n  Chen et al. avoid the second issue by assuming a single distribution and equal costs across agents (i.e., homogeneous agents), allowing equal data contribution and ensuring sufficient data from all agents. However, this breaks down with heterogeneous data collection costs. Our paper focuses on this second challenge. As noted in lines 307–309, we adopt their method (Algorithm 2, lines 20–23) to address challenge 1, though we must overcome some technical hurdles to do so.\n\n  The following example illustrates why challenge 2 is non-trivial. Even with $d=1$, unequal costs make it most efficient for the cheapest agent (say, agent 1) to collect all the data. However, this raises two issues: (i) As discussed in Section 3.2, this may violate IR for agent 1. (ii) As covered in Section 4, applying Chen et al.’s solution to challenge 1 requires sufficient data from other agents. Without their contributions, agent 1 could fabricate data, making truthful reporting hard to enforce. The same intuition applies even in the social penalty minimizing allocation of work where the cheapest agent collects most but not all of the data. Again, the mechanism may not have enough data from the other agents to cross validate the submission and incentivize truthful reporting. These considerations do not arise in Chen et al., as agents have the same collection cost so the work of data collection can be equally divided which eliminates these challenges.\n\n  These challenges worsen with multiple distributions ($d > 1$). For example, suppose there are $m$ agents and two distributions: agent 1 faces high cost for the second distribution, while agents $2,\\dots,m$ face high cost for the first. Then, agents $2,\\dots,m$ depend on agent 1 for data from the first distribution, but the mechanism cannot validate agent 1’s data, as no one else can sample distribution 1. This intuition underlies the $\\Omega(\\sqrt{m})$ hardness result in Theorem 4, unique to the heterogeneous case - in contrast, Chen et al. always achieve an $O(1)$ approximation.\n\n  The main algorithmic challenge is dividing the work to (a) maintain a large enough group for data verification, and (b) keep data collection costs low to minimize social penalty. These goals conflict, as (a) may require costly agents to collect more, increasing the social penalty. While we rely on Chen et al. for challenge 1 (lines 19–23 of Algorithm 2), the rest of Algorithm 2 and all of Algorithm 1 are novel. As reviewer ZK8A noted, this paper builds significantly on Chen et al.\n\n  In addition to solving the aforementioned challenges, we provide supplementary hardness results in Theorems 2 and 3. These results also apply to the setting studied by Chen et al. (but are not presented in their work).\n\n- *Generalizing to new distributions and losses:* We study the problem of normal mean estimation because Chen et al. have solved challenge 1 for this problem and our focus is on challenge 2. To the best of our knowledge, Chen et al. provide the only solution to challenge 1 under general strategy spaces where agents can submit untruthful data and post-process the information returned by the mechanism. If methods for solving challenge 1 were developed for different distributions or losses, we believe our techniques to solve challenge 2 could be applied in this new setting.\n\n**Other Comments Or Suggestions:**\n- *IC and IR:* Apologies for the confusion, we meant to say that defining IR in our setting is nontrivial. We will update the writing to make this more clear.\n\n**Questions For Authors:**\n- *Non-isotropic Gaussians:* Our setting assumes that $m$ different agents wish to learn $d$ unrelated normal distributions which we represent as learning an isotropic gaussian. A non-isotropic gaussian would correspond to the agents learning the means of correlated distributions so the mechanism would need to be adapted for this new problem setting.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I did not formally check the proof.", "experimental_designs_or_analyses": "No", "relation_to_broader_scientific_literature": "At high level, this work can be viewed as information elicitation without money.  The main techniques are closely related to Chen et al. 2023.", "essential_references_not_discussed": "Nothing critical.  \n\nOne related work can be Kong, Yuqing, et al. \"Information elicitation mechanisms for statistical estimation.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 02. 2020, which considers eliciting truthful Gaussian signal.  However, agents do not have cost and need monetary reward.", "other_strengths_and_weaknesses": "Strength:\n- The observation of fair issue when agents have heterogeneous cost is interesting.\n- The paper further shows that the mechanism can enforce any bargaining solution is interesting.\n- Bounding the social cost gap with and without IR is nice.\n\nWeakness:\n- The main technique of the paper seems to mostly follows Chen et al. 2023, which solve for one dimensional homogeneous setting.  I feel this is a miss opportunity, as considering general Gaussian setting may inspire new technique. \n- The technique heavily depends on the Gaussian assumption and square error setting.  It would be good if the paper discusses how to generalize the results to other setting, e.g., exponential family.", "other_comments_or_suggestions": "It seems IC generalizes IR in this paper.  The discussion about prior work overlooking IR before section 1.1 confuses me.", "questions_for_authors": "Does the mechanism work for non-isotropic Gaussian?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RlmPw7jWOq", "reviewer": "Reviewer_7Eg1", "summary": "This paper proposes a novel collaborative learning mechanism to solve the problem of individual rationality, fairness, and strategic behavior among heterogeneous strategic agents. Its contributions include mechanism design, approximate ratio analysis, hardness results, and fairness comparison.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your response and questions.\n\n**Other Strengths And Weaknesses:** \n\n- *Unknown costs, privacy, communication costs:* These are important considerations in real-world systems but because our current model is already technically challenging, we leave these for future work.\n\n- *Fairness and efficiency tradeoff:* The tradeoff between fairness and efficiency is a natural question in many multi-agent systems. Axiomatic bargaining solutions are designed specifically to handle such trade-offs. In Section 6, we allow the mechanism designer to specify their favorite bargaining solution (which leaves it to them to determine how to trade-off fairness and efficiency). Our focus instead is on incentivizing truthful reporting while approximating this bargaining solution. To summarize, while we do not explicitly consider fairness vs efficiency, our framework allows a mechanism designer to handle this trade-off by choosing a bargaining solution.\n\n- *Communication overhead of data exchange:* Because our mechanism is a one time algorithm for data sharing we do not anticipate communication overhead being a practical issue and leave this consideration for future work.", "claims_and_evidence": "The claims are convincing and have sufficient theoretical support.", "methods_and_evaluation_criteria": "The proposed methods are technically sound and have sufficient theoretical proofs as the support.", "theoretical_claims": "I only checked part of the theoretical proofs, and they are correct. I didn't check all the theoretical proofs.", "experimental_designs_or_analyses": "No experimental designs since it is a purely theoretical work.", "relation_to_broader_scientific_literature": "Ensure individually rational and fair outcomes so all agents benefit and prevent socially undesirable outcomes in a multi-agent collaboration system.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strength:\n\n1. This paper addressed an important problem that is ensuring individually rational and fair outcomes so all agents benefit and preventing socially undesirable outcomes in a multi-agent collaboration system.\n\n2. The proposed collaboration mechanism with social penalty is technically sound.\n\n3. Sufficient theoretical proofs are provided.\n\nWeakness:\n\n1. The model assumes that the collection cost of the agent is a known constant and that data sharing is frictionless. However, there may be dynamic costs, privacy constraints, or transmission delays in real-world scenarios. Failure to discuss the impact of these limitations on the conclusions, such as robustness analysis, may undermine the model's usefulness.\n\n2. The trade-off between fairness and performance / efficiency sacrifice remained unknown.\n\n3. The communication overhead of data exchange among agents has not yet been discussed, which is problematic in real-time collaboration.", "other_comments_or_suggestions": "Please refer to weakness.", "questions_for_authors": "Please refer to the weakness.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NuZK3sNvBF", "reviewer": "Reviewer_3gvh", "summary": "This paper studies a scenario of data sharing among players interested in estimating the mean of a vector $\\mu \\in \\mathbb{R}^d$ through samples from a gaussians with mean $\\mu_k, k \\in [d]$. The fact that the players can exchange data (which could happen in practice if some players have specific advantages to collect specific kinds of data) requires several conditions to ensure favorable outcomes. The mechanism needs to ensure Individual Rationality (i.e. the players are better off by joining the process), Incentive Compatibility (i.e., the players are better off by being trustful) and producing \"nice/fair\" outcomes. Typically, the mechanism needs to prevent strategic behaviours (players misbehaving in order to improve their own personal utility).\n\nA mechanism (designed by a principal who coordinates the players) is a tuple given by an information set $\\mathcal{I}$ and a map from the datasets given by the agents to some information released to the agents. On the players' side, the strategy consists of a number of samples collected, a map that transforms the collected samples before submitting them to the mechanism designer and finally an estimator that also takes into account the information released by the principal to the agent. Of course, the agents have costs depending on the coordinate of the vector they sample and can strategically choose the components of their strategy.\n\nThe goal of the mechanism is to minimize the global penalty (kind of a non-decreasing function of the individual costs) under the Individual Rationality constraint.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your response and questions.\n\n**Relation To Broader Scientific Literature:**\n\n- *New challenges from heterogeneity:* We apologize for not highlighting the new challenges that heterogeneity introduces well enough due to space constraints. Please see \"comparisons with Chen et al. 2023\" in the response to reviewer MzVR. We will ensure this is better highlighted in the revision. \n\n**Essential References Not Discussed:**\n\n- *Capitaine et al. and Donaheu et al.:* Thank you for bringing these to our attention. We will add them to the related work section in the revision. However, we wish to emphasize that neither Capitaine et al. nor Donaheu et al. address the problem of truthful reporting and both assume a more restrictive strategy space than the one we consider. Additionally, in Donahue et al. agents are drawing their data from different distributions and do not share the data itself whereas we utilize the fact that agents are drawing data from the same distributions and share data drawn from those distributions. \n\n**Other Strengths And Weaknesses:**\n\n- *Novelty of the setup:* Please see \"comparisons with Chen et al. 2023\" in the response to reviewer MzVR.\n\n**Other Comments Or Suggestions:**\n\n- *Real world applications of our model:* Data sharing consortia exist among research labs, hospitals, and freight/wireless spectrum monitoring/tech companies. Examples include PubMed, PubChem, CLARiTi, FLOW, BigSpec, and DeltaSharing. In particular,  BigSpec for wireless spectrum monitoring shares average power usage across different wireless spectrum bands, and is akin to our mean estimation problem.\n\n  To our knowledge, these systems and the references in line 20 rely on trust, assuming agents will always report truthfully. Mechanisms that rely on trust are susceptible to free-riding wherein participants may forgo the work of data collection and instead rely on the data collected by other participants. This can discourage agents from participating in data sharing. On the other hand our mechanism discourages agents from free-riding and incentivizes them to collect and contribute a sufficient amount of data truthfully.\n\n**Questions For Authors:**\n\n- *Novel challenges introduced by heterogeneity:* Please see \"comparisons with Chen et al. 2023\" in the response to reviewer MzVR.\n\n- *Current mechanisms for data sharing (more than line 20):* Current platforms fall into one of two categories. First, in some, agents contribute data and others can use this data (e.g PubChem, PubMed). In other examples, participants all submit data to a centralized planner who reallocates the data received (eg. BigSpec, CLARiTi). To our knowledge, none consider truthful reporting, nor do they consider the costs involved with data collection.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "No evaluation criteria, the only example is an illustrative graph in dimension 1 but I do not feel like intensive experiments are needed to support the paper.", "theoretical_claims": "I checked as I could the theoretical proofs of the paper's theorems but I must admit that I did not go through all the details of the proofs in the supplementary. From what I checked, things seemed correct.", "experimental_designs_or_analyses": "NA.", "relation_to_broader_scientific_literature": "The problem tackled in this paper is interesting but not new and has already been studied in the literature. I appreciate the fact that the reference Chen et al., Mechanism Design for Collaborative Normal Mean Estimation has its own paragraph discussion in the related works. The paper claims that considering heterogeneous costs between the agents for the data collection raises \"new IR and fairness challenges\" but I would enjoy a more thorough discussion about the fundamental differences that are implied by the heterogeneous costs (while the appendix \"Extended related works\" mostly rephrase the paragraph from the main).", "essential_references_not_discussed": "Yes, essentially these two references seem crucial to me:\n\n- Capitaine et al., Unravelling in collaborative learning: this paper studies a mechanism so that rational and strategic agents can share data to the principal and receive a trained model. The best the data they provide is, the best is the model they receive. Similar questions about what happens at the Nash Equilibrium are studied and both setups seem close to me.\n\n- Donahue et al., Model-sharing Games: Analyzing Federated Learning Under Voluntary Participation is a classic reference that studies collaborative inference under constraints on the participants' behaviors.", "other_strengths_and_weaknesses": "To me, the major weakness of the paper is the lack of novelty of the setup since designing mechanisms for trustful sharing of data among [potentially] strategic agents has already been introduced an studied before.\n\nOne the other side, the paper provides a good understanding of how it relates to the existing literature, acknowledges the differences between the previous setups and provides thorough theoretical foundations for the claims.\n\nI also have to say that the paper is very correctly written.", "other_comments_or_suggestions": "I do not believe that experiments are necessary for the paper. However, providing setups where this data sharing situation could happen would be absolutely great and how the proposed mechanism would experimentally compare to what exists would be a real plus.", "questions_for_authors": "Could you explain more precisely how the heterogeneous costs among the agents make a fundamental difference with the work of Chen et al., Mechanism Design for Collaborative Normal Mean Estimation?\n\nCould you discuss the current mechanisms that are implemented for data sharing in practice nowadays (in more details than the statement line 20)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cc977ADixp", "reviewer": "Reviewer_ZK8A", "summary": "The paper studies a mechanism design problem for agents gathering and sharing data. The authors formalize a model for agents that collect data, with some cost, and distribute it to others, potentially in a strategic manner. They demonstrate a mechanism with satisfies Nash incentive-compatibility, individual rationality, and $\\sqrt{m}$-efficiency (Theorem 1, Algorithm 2). The authors go on to discuss hardness results for mechanisms with stricter properties, as well as fair solutions determined by bargaining.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your response and questions.\n\n**Experimental Designs Or Analyses:**\n\n- *Creation of Figure 1:* The plot was created using a small amount of Mathematica code to solve each of the 5 optimization problems and a minimal amount of Python code to plot the results. We will update the paper to include this in the final version.\n\n**Essential References Not Discussed:**\n\n- *Discussion of federated learning, strategic classification, and data sharing:* These are all valid practical considerations in data sharing but for the sake of simplicity, given that our model is already technically challenging, we leave these for future work. We will make sure to discuss how our mechanism relates to the federated learning, strategic classification, and data sharing references you have provided in the updated version of the paper.\n\n**Other Strengths And Weaknesses:**\n\n- *Technical notation and notion of leverage:* We describe the mechanism as having \"leverage\" when condition (8) is satisfied for $(c,n)$. At a high level this means there is enough data from each agent to cross validate all the submissions. The notation mentioned is to try and emphasize the process by which the recommended strategies are determined (see bullet point 3). We will more clearly motivate and clarify these terms and notation in the revision.\n\n- *Solving for $n^{OPT}$:* The scale of $n^{OPT}$ is determined by the problem parameters (e.g. $c,\\sigma,m$, etc). For example, lower costs lead to increases in $n^{OPT}$ as it is now worth it to collect more data. Solving for $n^{OPT}$ is a convex optimization problem and thus can be handled by tools like Mathematica (which we did for Fig. 1). We will highlight this practical consideration in the revision.\n\n- *Clarifying Algorithm 1:* Our mechanism can handle different bargaining solutions to suite the mechanism designer's preference. However, not every bargaining solution is feasible. For example, having the cheapest agent collect all the data maximizes social welfare but leaves the mechanism with no way to validate their submission. Thus, having the cheapest agent submit this quantity of data truthfully is not IC. Given a bargaining solution $n$, the purpose of Algorithm 1 is to compute an approximation, $\\widetilde{n}$, where agents collecting data according to $\\widetilde{n}$ and submitting it truthfully is IC. Along with $\\widetilde{n}$, Algorithm 1 returns two\nsets $(V_k)_{k=1}^d$, $(T_k)_{k=1}^d$ which record information about $\\widetilde{n}$ for technical convenience to be used in Algorithm 2.\n\n- *Enforceability:* By saying $n$ is enforceable, we mean that agents collecting data according to $n$, submitting it truthfully, and accepting the estimate from the mechanism forms a Nash equilibrium. Some bargaining solutions such as having the cheapest agent collect all the data do not result in a Nash equilibria so we would say that bargaining solution is not enforceable by the mechanism. We will elaborate on and clarify this in the revision.\n\n**Other Comments Or Suggestions:**\n\n- *Minor comments:* We will address the minor comments as recommended in the revision. We assume that in the third bullet point you are referring to the first few lines at the start of page 8? Here we mean to say that a large value of $\\alpha_{i,k}$ may be needed to ensure IC but result in poor efficiency. We will make this clearer in the revision.\n\n**Questions For Authors:**\n\n- *The constraint of money:* Using money may simplify some of the calculations as payment is now replacing the estimation error. However, there is still the problem of incentivizing truthful data collection. For example, paying the cheapest agent to collect all of the data leaves the mechanism with no way to validate their submission. Therefore, the tradeoff between efficiency and a mechanism's ability to validate submissions as a result of heterogeneity remains.\n\n- *Independent dimensions:* Yes, the problem model is that agents wish to learn the means of $d$ unrelated distributions. We use a multivariable gaussian with identity covariance to represent this. You are correct that figure is limited to $d=1$ because we wanted to provide a simple example of how different bargaining solutions can lead to asymmetric divisions of work and penalties.\n\n- *Currency of collection costs:* We are assuming that the costs are normalized relative to the error so that it makes sense to add them when defining the penalty.\n\n- *Creation of Figure 1:* Please see \"Experimental Designs Or Analyses\" section of the rebuttal.\n\n- *Tightness of the efficiency bound:* Yes, Theorem 4 implies the efficiency bound is tight up to constants.", "claims_and_evidence": "The authors prove five theorems:\n\n* (Thm 1) Alg 2 is NIC, IR, and $\\sqrt{m}$-efficient.\n\n* (Thms 2-3) Any mechanism M for the setting that is either --  always IR or dominant strategy -- has each agent's individual pentality of at least $\\frac{p_i^{IND}}{2}$.\n\n* (Thm 4): Price of stability lower-bound.\n\n* (Thm 5): 8-approximation on efficiency for bargaining-like solutions.\n\nThese results seem thorough for this type of paper.", "methods_and_evaluation_criteria": "The authors provide sufficient benchmarks with respect to (1) the number of samples and individual penalties that agents would draw by working alone, and (2) comparisons against the sample mean mechanism. Baselines are used to establish bounds on individual rationality.", "theoretical_claims": "The proofs appear correct as I skimmed them, though I did not check the appendix too closely for possible errors.", "experimental_designs_or_analyses": "Experiments do appear thorough in visually demonstrated 5 different solution concepts pertaining to this work, including (a) working along, (b) minimizing social penalty without caring for IR, (c) minimizing social penalty subject to IR constraints, and (d--e) bargaining solutions. However, there is no \"experiments\" section which discusses how the data for Figure 1 was generated (except perhaps Appendix D, though this should be described further in the main text).", "relation_to_broader_scientific_literature": "The papers focus is on free-riding problems in data sharing settings, so they provide some background (in Sec 2 and Appendix A) about free-riding, cooperative game theory approaches to data contributions, and data sharing with monetary incentives. There are not too many references, but it seems thorough enough for this type of work. This paper significantly builds on Chen et al. (2023).", "essential_references_not_discussed": "Since your paper discusses data learned across independent parties, this seems like a federated learning task where agents share raw data rather than summary parameter vectors. In general, FL is studied because of the high communication overhead for sharing so much data and in order to conserve privacy of the underlying data. How is this addressed in your current study? I'd like to see some discussion on how your work builds upon other mechanism design literature in federated learning [1], strategic classification [2], or data sharing [3, 4].\n\n[1] Zhan, Y., Zhang, J., et al. (2021). A Survey of Incentive Mechanism Design for Federated Learning.\n\n[2] Hardt, M., Megiddo, N., et al. (2016). Strategic classification.\n\n[3] Zhang, X., Yang, Z., et al. (2014). Free market of crowdsourcing: Incentive mechanism design for mobile sensing.\n\n[4] Tu, X., Zhu, K., et al. (2022). Incentive mechanisms for federated learning: From economic and game theoretic perspective.", "other_strengths_and_weaknesses": "Strengths:\n- The paper presents mechanisms to address problems of free-riding and data manipulation in the setting of data sharing. The authors conduct a through review of several problems in this area, including (1) dishonesty of the agents, (2) ability for agents to change their estimator functions $h_i(\\cdot)$, (3) equitability of agents sampling the data.\n- Contributions appear novel, significant, and technically rigorous.\n- The paper is well-organized with its headings. Notation is clear and well-defined.\n\nWeaknesses:\n- The latter portion of Section 4, through Section 5, is harder to read than the rest of the paper, especially with a lot of technical notation. The authors employ high-level concepts, such as \"leverage,\" without describing the intuition. Several notation for numbers of samples are introduced, such as \n  * $\\tilde{n}_{i,k}$,\n  * $n_i^*$, and \n  * $n^{L}_{i,k}$\n\nwithout clearly distinguishing why these are necessary.\n- How large is $n^{OPT}$, or how complicated is solving Eq (7)? This seems significant through Sections 4 and 5, though isn't properly discussed.\n- Can you clarify the purpose of Algorithm 1 and what it returns?\n- What does \"enforceable\" mean?\n\n[1] Anshelevich et al. (2004). The price of stability for network design with fair cost allocation.", "other_comments_or_suggestions": "Minor:\n- Is the sub-title on each page supposed to be different than the main title?\n- Why is some text blue in Section 2?\n- Is the text following $n_i^*$ on page 8 correct?\n- In \"Agent's penalty\" section, clarify that $\\mu'$ is a fixed and commonly known distribution.\n- In \"Truthful submissions\" paragraph, clarify that $s^*$ denotes the truthful submission and estimate, corresponding with $id$ and $h^{ACC}$.\n- Please be consistent with \"Fig. 1\" and \"Fig 1\".\n- In \"Algorithm 2 walk through\" paragraph, if you are including $G_{i,k}$ (defined in Appendix C), please at least mention what it represents. However, since this variable does not appear to be used in the main text, only in the proof (Appendix F), I would not recommend mentioning it in the main text.\n- Paragraphs \"Baseline for efficiency,\" \"From compliant to strategic agents,\" and \"Fairness considerations\" are somewhat redundant to other material presented earlier in the paper. This content can be condensed if you are running out of space elsewhere.\n- Please define \"price of stability\" and cite [1]\n- Section 6: please replace \"fairness\" with \"equitable.\" These terms are not synonymous.", "questions_for_authors": "- How does your constraint that the mechanism cannot use money change the setting? In \"Problem formalism,\" you suggest that lowest-cost agent $i^*$ could collect the most data. It seems that, if this data were valuable to other agents, they would pay $i^*$. This makes sense from a labor specialization perspective: it satisfies each agent's needs in an IR manner with the minimal social cost.\n- It seems that the objective vector $\\mu$ has no covariance by assumption -- i..e, the d dimensions are independent of each other. In this case, it would seems that your setting is really d independent settings, though with possibly different costs across the agents for each dimension. Is this addressed in your theory, or am I mistaken? It seems that your experiments focus on the d=1 dimension case.\n- In Agent's penalty, why are we suggesting that the cost $c_{i,k}$ is of the same currency as the L2 gain that agents get by being correct? Is this a good assumption, or just a mathematical convenience as a regularization variable?\n- How are the allocations of Figure 1 produced? This seems to correspond to Appendix D, but this isn't described in the main text.\n- Does Theorem 4 imply that the efficiency bound found by Theorem 1 (and Algorithm 2) is tight?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies a data sharing problem in collaborative learning where each agents can get some normally distributed estimates of a mean (in multi-dimension), with a cost that is heterogeneous across agents. The paper proposes an approximate mechanism for social cost minimization, proves hardness results, and analyzes variants that are more "fair" (in the repartition of cost amongst agents, formalized with the concept of axiomatic bargaining). 

All reviewers found that the paper tackles an important problem and has strong theoretical results on it. The fairness part was particularly appreciated as the most novel. On the downside, it was noted that the methods heavily rely on Chen et al. 2023, so that the novelty in the proofs is somewhat incremental. Nevertheless, the consensus was that the results are worth acceptance.
Decision: Accept (poster)