A Cramér–von Mises Approach to Incentivizing Truthful Data Sharing

Thank you for your response and questions.

Strengths And Weaknesses:

• Novelty of techniques: We would like to emphasize that although comparing agents' submissions is a common idea in fields like peer prediction, there is a substantial gap between existing methods, which are limited to simple data distributions (e.g. Bernoulli, Gaussian, etc), and our approach, which supports unrestricted data distributions. In fact, we believe prior work has focused on simple distributions precisely because achieving a general result has proven to be challenging. Bridging this gap requires novel insights and connections to two-sample testing that are technically nontrivial.

• Privacy/communication in federated learning: We agree that there are many practical considerations such as privacy and communication overhead that go into building real world data sharing systems. However, our focus is on the incentives at play and these challenges are beyond the scope of our paper.

• Choice of feature maps: We wish to point out, as noted in lines 219-220, that truthfulness does not depend on the feature maps used. Our mechanism is truthful for any choice of feature maps chosen by the mechanism designer. However, we allow the flexibility of choosing feature maps because (i) the choice of feature maps determines how much an untruthful agent gets punished, and (ii) different types of data may be suited to different representations. For low dimensional data the coordinate projections are reasonable choices for features maps, whereas for high dimensional image data, embeddings given by a deep learning model are a more reasonable representation. The success of modern machine learning and pretrained models relies on using feature maps so our approach is not atypical. In our experiments, we used feature maps from existing models with no additional tweaking and found our methods work well.

• Approximate truthfulness: Theorem 3 shows that Algorithm 3 is $\frac{1}{4} \left( \frac{1}{ |X_i|+|W_i| } + \frac{1}{ |Z_i| }\right)$-approximately truthful in both the Bayesian and frequentist settings. Therefore, the more data that is being shared the more negligible $\omega$ is.

• Comparisons with advanced baselines: We first wish to point out that, to the best of our knowledge, we are the first theoretical work on truthful data sharing to provide experiments. Prior methods either do not work because their methods are not applicable for general data distrbutions and/or are computationally prohibitive. For instance, the method from [1] only applies to a single binary data point that is (untruthfully) reported without any fabrication. The approaches given by [2, 3] assume data is drawn from a Gaussian distribution and [4] requires that the data distribution belongs to the Exponential family or has finite support. The only method that is applicable in all of our settings is the mean difference mechanism (for which theoretical guarantees are available for Gaussian problems). We chose to include comparisons to KS, CvM, etc since comparisons with prior methods were not feasible.

  Can you please clarify what you mean by "adversarial reward mechanisms"?

  [1] Ghosh et al. (2014). Buying private data without verification.

  [2] Chen et al. (2023). Mechanism Design for Collaborative Normal Mean Estimation.

  [3] Clinton et al. (2025). Collaborative Mean Estimation Among Heterogeneous Strategic Agents: Individual Rationality, Fairness, and Truthful Contribution.

  [4] Chen et al. (2020). Truthful data acquisition via peer prediction.

• Simulation of marketplaces: As each of these applications is its own line of work we defer in depth simulations to future work.

Questions:

• Selecting feature maps: Please see the "choice of feature maps" section above.

• Empirically estimating approximate truthfulness: At the moment we do not have a way to empirically estimate how close approximate truthfulness is to exact truthfulness due to the complexity of the unrestricted agent strategy space. However, we conjecture that in the frequentist setting, if the class of data distributions over which the supremum is being taken is sufficiently rich, then our mechanism is exactly truthful. We leave this as a question for future work.

• Privacy and decentralization: We imagine that techniques used to address problems of privacy and decentralization could be incorperated into our mechanism but leave this as a direction for future work.

• Malicious agents: Data sharing with colluding agents is a direction that we are currently studying. Because our mechanism is not sensitive to ourliers in data (through its use of CDFs) we believe that there is an amount of robustness already present although this is not quantified in the results we present. We believe that techniques from robust statistics will be useful in proving results about data sharing under collusion although it is common in game theory not to consider adversarial agents.

• Relation to information theoretic methods: To the best of our knowledge, information theoretic methods that rely on concepts such as mututal information suffer from either strong data distributional assumptions or are not analytically and computationally tractable. Our techniques alleviate these concerns.

Thank you for your response and questions.

Strengths And Weaknesses:

• Quantifying the loss for more data: We do in fact have exact quantative relationships between the feature maps, data distribution, and an agent's expected loss for both Algorithms 2 and 3. Because these relationships are complex, we also provide simple upper bounds for an agent's expected loss as a function of the amount of data. We'll now go into more detail on this for both algorithms.

  1. For Algorithm 2: Proposition 9 (stated in the appendix) gives an explicit relationship for how the expected loss changes when agent $i$ submits an additional data point, depending on the prior and feature maps. This exactly quantifies how much higher of a "payoff" an agent receives for reporting more data. Proposition 10 (stated in the appendix) gives a simple upper bound for the expected loss as a function of the amount of data: $\frac{1}{4} \left( \frac{1}{ |X_i| } + \frac{1}{ |Z_i| } \right)$ in general and $\frac{1}{6} \left( \frac{1}{ |X_i| } + \frac{1}{ |Z_i| } \right)$ when the selected feature maps applied to the data are continuously distributed.

  2. For Algorithm 3: Proposition 11 (stated in the appendix) gives an analogous simple upper bound of $\frac{1}{4} \left( \frac{1}{ |X_i|+|W_i| } + \frac{1}{ |Z_i| } \right)$ for the expected loss. However, when the selected feature maps applied to the data are continuously distributed, this proposition provides an exact expression for the expected loss in both the Bayesian and frequentist settings: $\frac{1}{6} \left( \frac{1}{ |X_i|+|W_i| } + \frac{1}{ |Z_i| } \right)$.

  We will make sure to better highlight these quantitative relationships between the prior, feature maps, amount of data, and an agent's expected loss in the revision.

• Minor typos: We will fix these in the revision.

Questions:

• Quantitative dependence between loss, feature maps, and prior: Yes, please see above.

• Evaluating feature maps: Could you please clarify what you mean by "diversity and marginal payoff for data"?

Thanks for pointing out these quantitative results! I think they make the main message of the paper stronger, so it could be nice to include some mention of them in the main body.

Thank you for your response and questions.

Strengths And Weaknesses:

• Novelty compared to existing literature: We have acknowledged in the paper that the idea of comparing data submitted by agents appears in prior work. However, there is a substantial gap between existing methods, which are limited to simple data distributions (e.g. Bernoulli, Gaussian, restricted class of exponential families etc), and our approach, which supports any data distribution. Bridging this gap requires novel insights that are technically nontrivial. In fact, we believe prior work has focused on simple distributions precisely because achieving a general result has proven to be challenging.

  1. Chen et al. incentivize agents to report data truthfully using information theoretic ideas from peer prediction. However, these techniques require strong data distributional assumptions to gaurantee their mechanism satisfies basic properties such as individual rationality or tractability. Our techniques, inspired by two-sample testing, are novel (as pointed out by reviewer Ap5u) and alleviate these restrictive assumptions.

  2. The model studied by Karimireddy et al. differs significantly from ours because it does not allow for misreporting data. The primary aim of our paper is to develop a mechanism which incentivizes agents to report their data truthfully when a priori they may attempt to fabricate or misreport their data.

  3. Cai et al. also do not allow for misreporting data and instead adpot a model where agents can exert higher effort to decrease the noise in the data they sample. They also require the effort-noise tradeoff function to be known. Therefore, their methods are not applicable to our problem of incentivizing agents to report truthfully when dealing with data from general distributions.

• Truthfulness and feature maps: We wish to point out, as noted in lines 219-220, that truthfulness does not depend on the feature maps used. Our mechanism is truthful for any choice of feature maps chosen by the mechanism designer. However, we allow the flexibility of choosing feature maps because (i) the choice of feature maps determines how much an untruthful agent gets punished, and (ii) different types of data may be suited to different representations. For low dimensional data the coordinate projections are reasonable choices for features maps, whereas for high dimensional image data, embeddings given by a deep learning model are a more reasonable representation. The success of modern machine learning and pretrained models relies on using feature maps so our approach is not atypical. In our experiments, we used feature maps from existing models with no additional tweaking and found our methods work well.

• Experiment settings: As noted by Reviewer jWHw, we do provide experiments using real world image and text data. While we agree that experiments involving market dynamics would be useful, we also wish to point out that, to the best of our knowledge, we are the first theoretical work on truthful data sharing to provide experiments. In fact, some prior methods are not even practical to implement due to expensive Bayesian posterior computations, or information theoretic quantities, such as mutual information, being analytically intractable for complex data distributions.

Questions:

• Novelty compared to existing literature: Please see above.

• Implementation guidelines: Can you please clarify what you mean by "guidance on implementing the method"? Are you asking about how to select feature maps?

Thank you for your response and questions.

Strengths And Weaknesses:

• Feature maps: It is true that the mechanism designer will choose reasonable feature maps based on the problem specification; however, this is to be expected given that there are no restrictions on the data distributions supported by our mechanism. Moreover, the success of modern machine learning and pretrained models relies on using feature maps so our approach is not atypical.

• Approximate truthfulness: We do have an exactly truthful mechanism in the Bayesian setting, but it can be computationally expensive (much like other methods in this space). Approximate truthfulness is a trade-off for designing a prior-agnostic mechanism that is both simple and tractable across diverse data distributions.

Questions:

• Adversarial feature maps: Because feature maps are selected by the mechanism designer we do not consider the possibility that they are adversarially selected. We do note however, that the that the mechanism is still truthful regardless of the feature maps selected. The choice of feature maps determines how much an untruthful agent gets punished.

• Collusion among agents: Collusion and coordinated fabrication introduce new challenges that we are investigating in future work. We believe that techniques from robust statistics can be leveraged to form data sharing mechanisms that are provably robust to a small fraction of strategic colluding agents. Because our mechanism is not sensitive to ourliers in data (through its use of CDFs) we believe that there is an amount of robustness already present in our mechanism although this is not a result we have provided.