Collaborative Mean Estimation Among Heterogeneous Strategic Agents: Individual Rationality, Fairness, and Truthful Contribution

Thank you for your response and questions.

Experimental Designs Or Analyses:

• 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.

Essential References Not Discussed:

• 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.

Other Strengths And Weaknesses:

• 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.

• 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.

• 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 sets $(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.

• 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.

Other Comments Or Suggestions:

• 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.

Questions For Authors:

• 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.

• 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.

• 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.

• Creation of Figure 1: Please see "Experimental Designs Or Analyses" section of the rebuttal.

• Tightness of the efficiency bound: Yes, Theorem 4 implies the efficiency bound is tight up to constants.

Thank you for your response and questions.

Relation To Broader Scientific Literature:

• 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.

Essential References Not Discussed:

• 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.

Other Strengths And Weaknesses:

• Novelty of the setup: Please see "comparisons with Chen et al. 2023" in the response to reviewer MzVR.

Other Comments Or Suggestions:

• 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.

  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.

Questions For Authors:

• Novel challenges introduced by heterogeneity: Please see "comparisons with Chen et al. 2023" in the response to reviewer MzVR.

• 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.

Thank you for your response and questions.

Other Strengths And Weaknesses:

• 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.

• 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.

• 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.

Thank you for your response and questions.

Essential References Not Discussed: Thank you for the suggestions. We will update the paper to include this reference.

Other Strengths And Weaknesses:

• Comparisons with Chen et al. 2023: We would like to emphasize the two (orthogonal) challenges that need to be tackled to incentivize truthful contributions while maintaining an efficient system. (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. (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).

  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.

  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.

  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.

  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.

  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).

• 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.

Other Comments Or Suggestions:

• 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.

Questions For Authors:

• 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.