Stochastically Dominant Peer Prediction

We apologize for several conceptual confusions and will update our paper accordingly for clarification. Below, we provide responses to each of your questions. Please follow up for further clarification if there is any misunderstanding of your questions.

Bayesian Nash Equilibrium

The score of a peer prediction mechanism depends not only on the agent being scored (Alice) but also on her peer (Bob). Therefore, our considered truthful guarantee is based on the equilibrium concept. By the definition of an equilibrium, we must show that if everyone else is reporting truthfully, Alice is better off reporting truthfully as well. This leads to the assumption that Bob is always reporting truthfully, which applies to every peer prediction mechanism discussed in the paper. This is a common assumption in peer prediction literature.

EA for the motivating example

The example we introduced in lines 37-40 is primarily used to motivate the concept of SD-truthfulness, i.e, we want mechanisms whose score distribution under truth-telling FOSD that under any untruthful strategy. The mechanism (EA) introduced in Section 5 is a new way to obtain SD-truthfulness, and thus is a new solution to the grading example in lines 37-40.

To apply EA, suppose a grader scores "+" on 8 out of the 10 assigned submissions, but the instructor knows that only the top 30% of submissions should be "+" and 70% should be "-". Then, by EA, the instructor randomly flips 5 submissions graded "+" by the grader to "-". The grader will be scored based on the probability that her grades agree with another grader on the same 10 submissions (after flipping). To incentivize graders, we then map this score into the letter grades using any step function or any rank-order function. For example, assign A to the 30% students with the highest score; assign B to the top 80%; assign C to the remaining students. EA guarantees truth-telling as long as graders prefer A over B over C, and it does not require partition rounding.

Section 2 introduces the general model for how agents’ signals are correlated, how they can manipulate, and the input/output of a peer prediction mechanism. The general model also applies to section 5.

Budget efficiency and measurement integrity

These two concepts are indeed only used to motivate why sensitivity is a good metric to look at. We will clarify this.

EA under partition rounding

Please clarify if we misunderstood. In addition to sensitivity, in Figures 3 and 4, we show that EA can indeed incentivize a desired effort level at a lower cost of payment compared with other lower-sensitivity mechanisms. EA does not require partition rounding to be SD-truthful.

Other questions

• $\Phi$ is a unique concept for EA, which is the distribution of reports that EA enforces before computing the score. However, this does not violate the general model introduced in Section 2. To clarify, suppose $\Phi$ enforces a distribution of reporting 50 “yes” and 50 “no” on 100 questions. If Alice reports 40 “yes” and 60 “no”, EA will randomly flip 10 “no” answers to “yes” so as to enforce $\Phi$.
• Information structure refers to the joint distribution of agents’ signals. We will try to use the latter more in the paper.
• The joint distribution does not affect the truthful guarantees, but it affects the sensitivity of mechanisms. The sensitivity is higher when agents’ signals are more correlated.
• Colored variables: We do not see any regulations about colored text on NeurIPS website. We will remove color edits for the potential camera-ready.
• Line 78: See our response to “Motivating example”.
• Line 88: We consider the budgetary efficiency as a robustness check because it is shown in the previous paper [Zhang and Schoenebeck 2023] that when the score distribution is approximately Gaussian, a mechanism with a higher sensitivity has higher budgetary efficiency for rank-order utility functions. We replicate the experiments here to show that EA, which has the highest sensitivity, indeed has the highest budgetary efficiency (lowest cost of payments) in our setting.
• Line 130: Yes, when $e=1$, the model reduces to the general model in Section 2. To further clarify the effort model, when both agents exert effort, their signals are drawn from the joint distribution $\Pr(X_a, X_b)$; if either agent does not exert effort, the signals are drawn independently from the marginals $\Pr(X_a)*\Pr(X_b)$. Thus, a higher effort level $e$ corresponds to a stronger correlation between the agents’ signals.
• One citation for Proposition 3.2 is [Faltings et al., 2017] (Theorem 1). The necessary condition—OA is not truthful for self-predicting signals is presented in Proposition 3 of [Faltings et al., 2017]. We will include this necessary condition in our paper.
• Line 198: The original implementation of CA is not SD-truthful, because of the bolded text in line 210. We bold this sentence as this is an interesting insight and an important note for future research. The partition rounding implementation of CA is SD-truthful. The captain of the table clarifies that the table is referring to the rounded version of certain mechanisms.
• The technical importance of sensitivity has been highlighted in several prior works [Zhang and Schoenebeck (2023); Xu et al. (2024); Burrell and Schoenebeck (2023)]. At a high level, these works suggest that peer prediction mechanisms with high sensitivity are better able to produce scores that reflect high effort and high-quality responses. We will include more details about the conditions and technical meanings for these results in a new supplementary section.
  • In addition to this technical importance, we provide an alternative way to interpret sensitivity. To ensure truthfulness, many peer prediction mechanisms—such as PTS—reweight scores, or—like CA and EA—inject noise. These modifications inevitably reduce the mechanism’s ability to capture and reward the informational content in agents’ responses. In contrast, a high-sensitivity mechanism requires less distortion to ensure truthfulness, preserving more signal and thus providing scores that better reflect the quality of input.
• Line 334: Feel free to further clarify the question? In the current version, we are already doing what you asked: have one sentence describing the idea and defer details to the appendix. However we will make this clearer.

Partition round with replacement

As highlighted in line 210, repeatedly using the same question to compute multiple scores will distort the incentive for truth-telling. Although we don’t have a counterexample for every peer prediction mechanism, the intuition from Example 3.1 strongly warns against reusing questions.

Utility function

Lines 122-124 are sufficient to show the equivalence between SD-truthfulness (in scores) and truthfulness for any monotone utilities. This follows directly from the definition of first-order stochastic dominance. A utility function maps from a score to a real-value utility, which is a numerical representation of an individual's preferences over a set of outcomes. It is assumed that agents’ objective is to maximize their utilities.

Single-task mechanisms

Single-task mechanisms require agents to report both their own answers and probabilistic predictions of their peers' responses. These mechanisms are typically suited for settings where such predictive information is accessible and the questions exhibit a thinking hierarchy—that is, agents who know the correct answers can better anticipate the mistakes of others, but not vice versa. As a result, their use cases and scoring methods differ fundamentally from those of multi-task mechanisms and fall outside the scope of this paper.

Self-prediction

Intuitively, self-prediction is a mild assumption in practice. If Alice observes “A”, self-prediction only requires her to believe that Bob is more likely to have also observed “A” than if she had observed a different signal. This excludes only cases when agents' beliefs are very different, such as when they are negatively correlated.

More formally, in Footnote 2, we note that self-prediction is equivalent to positive correlation of agents’ signals in the binary setting—a reasonably weak assumption. Importantly, it is strictly weaker than self-dominance.

We adopt the self-prediction assumption from Faltings et al. (2017), where it is shown to be technically reasonable. Specifically, they demonstrate that Bayesian updating under a Dirichlet prior—a widely used prior over categorical distributions—satisfies the self-prediction condition.

In contrast, self-dominance is much stronger. It requires that upon observing “A”, Alice believes Bob is more likely to observe “A” than any other signal. This can easily be violated in practice. For instance, if “A” is a majority signal with high prior probability and Alice observes a minority signal “B”, she may believe Bob is still more likely to observe “A” than “B”, thereby violating self-dominance.

Dear reviewer BNRF,

Thank you for your review. We look forward to updating the paper according to your suggestions. Please feel free to follow up with any questions (if any). We'd love to keep the discussion going.

Best,

Authors of Submission23815

We appreciate your acknowledgment of our key contributions and the valuable feedback! We provide our responses below and wish to update our paper for clarification based on your comments.

Binary setting

While the Enforced Agreement (EA) mechanism is SD-truthful only in the binary-signal setting, we believe it remains valuable for two main reasons.

• First, the binary-signal setting is a practical and important setting. Many real-world tasks in crowdsourcing naturally take binary form—for example, selecting the better of two responses in RLHF, or determining whether a news article is real or fake in verification tasks. In theory, it is also a widely considered setting. Many peer prediction mechanisms are particularly designed for binary settings, e.g., [Dasgupta and Ghosh (2013)] and [Chen et al. (2024)].
• Second, EA is exceptionally simple to implement. Unlike PTS, it does not require reweighting scores based on prior probabilities, and unlike CA and related mechanisms, it does not require distinguishing between bonus and penalty questions. Its simplicity is on par with Output Agreement (OA), making it easy to communicate and apply in practice, such as in labeling tasks or educational settings.

We view EA as a simple yet effective step toward addressing the challenge of designing SD-truthful mechanisms. As some reviewers have noted, it opens the door to a promising line of research with substantial opportunities for extension and improvement.

Information structure assumption

At a high level, the information structure refers to how agents' signals are jointly distributed. To extend EA to multiple signals, we aim to estimate the joint distribution $\Pr(X_a, X_b)$ between agents’ signals. This is not a desired assumption, but also not an unrealistic one. A common approach in peer prediction—used in works such as Dasgupta & Ghosh (2013), Shnayder et al. (2016), and Zhang & Schoenebeck (2023)—is to have each agent answer multiple i.i.d. questions, which allows this joint distribution to be learned empirically. They show that agents are better off helping the designer learn this joint distribution accurately. Therefore, the truthfulness property still holds. This same approach can be readily applied to EA extend to non-binary settings.

Effort model

We apologize for the confusion and will clarify this in the paper. Effort is modeled as the probability that an agent chooses to work diligently on a question. When Alice exerts effort (to show that truth-telling is an equilibrium we can assume Bob will always exert effort and report truthfully), the pair of signals from two agents for that question is drawn from the joint distribution $\Pr(X_a, X_b)$; if Alice does not exert effort, the pair of signals is drawn from the marginals $\Pr(X_a)\cdot\Pr(X_b)$. Thus, a higher effort level $e$ corresponds to a stronger correlation between the agents’ signals.

Visualize truthfulness

Truthfulness is a binary property—a mechanism either satisfies it or it does not. We have formally proven that all mechanisms shown in the visualizations are (SD-)truthful.

The space of all deviations is quite complex, and it is not known how to measure how "close to" truthfulness a mechanism is in a theoretical way. While [Burrell and Schoenebeck], cited in the paper, create an innovative way to measure truthfulness, it is very empirical and less rigorous. First, they need to select prior, then they need to select possible deviation strategies. Then they measure whether the agents benefit when the deviating strategies are employed. Our analysis is much stronger than this because we prove that agents cannot benefit from any strategy while other agents are expending effort and telling the truth.

CA-partition-round

As shown in Proposition D.3, CA and MA have the same sensitivity under the partition rounding reduction in the binary setting. This results in the red lines in the figure being fully overlapped. We apologize for the confusion caused by the removal of several minor results for space considerations and will add a pointer to this clarification in the main body.

Thank you for the thoughtful follow-up. We’d like to clarify that the main contribution of our paper is theoretical. While we believe our proposed mechanism offers practical advantages—particularly its simplicity and stronger incentive properties—empirical validation would require additional human-subject experiments, which we view as beyond the scope of the current work and deserving of a separate study.

That said, there is a growing body of empirical research demonstrating the effectiveness of peer prediction mechanisms, even if the exact mechanism we propose has not yet been tested. For instance, Brown et al. (2025), "Incentive Mechanisms for AI: Theory and Evidence," show that a variant of the peer agreement mechanism can successfully incentivize effort while lowering the need for costly auditing. Similarly, Radanovic et al. (2016), "Incentives for Effort in Crowdsourcing Using the Peer Truth Serum," demonstrate that a version of the Peer Truth Serum (PTS) outperforms simpler agreement-based mechanisms in encouraging careful grading.

We sincerely thank Reviewer WpLs for their thoughtful and constructive feedback. Your questions highlight important aspects of our work that deserve deeper clarification. We address each of your main concerns below.

SD-truthfulness for Mutual Information Mechanisms

Thank you for raising this excellent point. We will add a supplementary section in the appendix to provide a more detailed explanation of why mutual information (MI)-based mechanisms are not SD-truthful. Below, we briefly summarize the key ideas.

• First, a straightforward way to implementing MI-based mechanisms is to estimate the empirical joint distribution and score agents using an $f$-divergence between the joint and the product of marginals, i.e. $S^{fMI} = D_f(\Pr(X_a, X_b) || \Pr(X_a)\Pr(X_b))$, as proposed by Kong and Schoenebeck (2017). However, this implementation is only asymptotically truthful. When the number of tasks is small, there is a non-trivial probability that truth-telling is not the best response. For example, if Alice observes "yes" on all her questions, she knows that truth-telling will always result in a score of 0, regardless of Bob's responses (because the estimated joint distribution is the same as the product of marginals). By misreporting "no" on some questions, she introduces variation and has a chance of receiving a positive score. In comparison, such deviations are discouraged under EA because the mechanism will randomly flip the responses on behalf of the agent.

• Several follow-up ideas, such as the Determinant Mutual Information (DMI) mechanism by Kong (2020) and the pairing mechanism by Yu and Schoenebeck (2020), propose various ways to estimate the mutual information. These mechanisms aim to reduce the required number of questions to achieve truthfulness. However, they are still not SD-truthful. Consider the strategy from Example 3.1, where Alice always reports "yes." Under both DMI and the pairing mechanism, this strategy always yields a score of zero, while truth-telling may result in a negative score (we have new empirical results that verified this). Thus, this constant-reporting strategy is not dominated by truth-telling under these mutual information-based mechanisms with negative scores.

In summary, mechanisms with complex score distributions tend to introduce opportunities for strategic manipulations not dominated by truth-telling. We hope these new discussions and results could further reinforce the intuition that SD-truthful mechanisms tend to prefer simple design.

Sensitivity Definition and Motivation

We appreciate your insightful question about why sensitivity, as defined, is the appropriate metric to consider. Our motivation for considering sensitivity was mainly justified in the previous works, and we acknowledge that we should provide a more detailed discussion in the paper.

• First, Zhang and Schoenebeck (2023) show that, when the score is normally distributed (which it is when the number of questions is large), sensitivity is a sufficient statistic for budgetary efficiency when agents' utilities depend on the ranking of scores — a mechanism with a higher sensitivity can incentivize the same effort level in equilibrium at a lower cost of payment. Second, Xu et al. (2024) show that there is a one-to-one mapping between sensitivity and measurement integrity [Burrell and Schoenebeck (2023)], meaning that a mechanism with a higher sensitivity can produce scores that are better correlated with the quality of responses.

• A key feature of sensitivity is that it depends only on the mechanism itself, not on the agent's utility function or how scores are translated into rewards. Comparing mechanisms under a fixed utility function is challenging because their score scales differ: for instance, fMI mechanisms produce non-negative scores, DMI scores can be unbounded, while most mechanisms in this paper yield scores between 0 and 1. As a result, each mechanism would require a different (non-linear) transformation of scores to determine rewards, making direct comparison of worst- or average-case sensitivity potentially misleading. A more meaningful comparison can be made under rank-order utility functions, where an agent’s utility depends only on their score ranking. In this setting, Zhang and Schoenebeck (2023) show that sensitivity is the appropriate metric for evaluating mechanisms.

• If we focus on non-linear utilities that are not ranking-based, e.g., a threshold utility function, we should then compare the mechanisms under the mechanism-dependent thresholds optimized for an objective that the principal cares about. For example, suppose the principal aims to elicit a desired effort $e$ at a lower cost, where the marginal cost of effort is $dc$. To incentivize such an effort, the principal must guarantee that agents’ marginal utility of exerting a higher effort overcomes the $dc$, i.e., $r\cdot dp\ge dc$ with $r$ being the payment and $dp$ being the marginal probability of receiving a score that is higher than the threshold. Because $dc$ is fixed, the threshold that minimizes $r$ is the one that maximizes $dp$. Suppose the score is normally distributed, the $dp$-maximizing threshold is precisely the expected score. This means that the original sensitivity is again a sufficient statistic for the performance of peer prediction mechanisms under threshold utilities.

Clarity and Accessibility Improvements

We greatly appreciate your feedback regarding clarity for a broader audience. From your questions and comments, we can see that you understood the main points and contributions of our work. However, we also recognize that the manuscript could be further improved—for example, by providing a crisp explanation of concepts like Bayes Nash Equilibrium and better contextualizing terminology from the elicitation literature.

We believe that the same improvements that would benefit a larger audience will benefit all readers. You can certainly expect to see changes in the potential camera-ready version that enhance accessibility while maintaining technical rigor. We spent considerable time on the current draft and believe it is suitable for acceptance, but we are committed to making the work more accessible to the broader NeurIPS community.

Dear reviewer WpLs,

Thank you for your appreciation and your thoughtful comments — they've certainly helped sharpen our paper! We're excited to incorporate these clarifications in the next revision. If any other ideas or questions come to mind, please feel free to bring them up. We’d love to keep the conversation going.

Best,

Authors of Submission23815

We sincerely thank Reviewer AWMx for their thoughtful review and constructive feedback. We appreciate your recognition of our paper's clear motivation for SD-truthfulness and the novel EA mechanism design. Your feedback helps us identify important areas for improvement and clarification. Below, we clarify several questions and concerns raised in your review.

The Space and Optimization of SD-truthful Mechanisms

You raise an excellent theoretical question about the possibility of finding optimal SD-truthful mechanisms. Previous efforts to carve out the space of peer prediction mechanisms for optimization have led to limited interest (and success) primarily for two reasons.

• First, it is too hard to constrain the space of mechanisms conditioned on truth-telling being a BNE. A large issue is that it must work for all prior distributions, but the space of distributions is large. One might overcome this if the joint distribution of agents' signals is known (so that it needs only to work for one prior distribution). However, this is a very strong and limiting assumption. Although this distribution could, in principle, be learned from reported data, doing so introduces two issues: 1) the learned model is often inaccurate and prone to overfitting; 2) since the learned joint distribution depends on reports themselves, agents may have incentives to misreport so as to mislead the optimizer. Previous attempts in this direction have only led to optimization in a very limited space of mechanisms.
• Second, optimized mechanisms tend to be complex and difficult to interpret. They require the designer to specify, in advance, the scoring or payment rule for every possible signal pair $(X_a, X_b)$. Such a mechanism can hardly be implemented or justified in real-world settings where simplicity and transparency are critical. This may explain why simple mechanisms like Output Agreement (OA), despite their limited theoretical guarantees, remain popular in practice.

To answer your questions, it is theoretically possible to find an SD-mechanism that is more sensitive than EA. However, we doubt it will come from any sort of explicit optimization. Furthermore, even if a more sensitive mechanism were arrived at, it would take a huge advance to show that it was optimal in any meaningful way (or to show EA is optimal for that matter).

Binary setting

While the Enforced Agreement (EA) mechanism is SD-truthful only in the binary-signal setting, we believe it remains valuable for two main reasons.

• First, the binary-signal setting is a practical and important setting. Many real-world tasks in crowdsourcing naturally take binary form—for example, selecting the better of two responses in RLHF, or determining whether a news article is real or fake in verification tasks. In theory, it is also a widely considered setting. Many peer prediction mechanisms are particularly designed for binary settings, e.g. [Dasgupta and Ghosh (2013)] and [Chen et al., (2024)].
• Second, EA is exceptionally simple to implement. Unlike PTS, it does not require reweighting scores based on prior probabilities, and unlike CA and related mechanisms, it does not require distinguishing between bonus and penalty questions. Its simplicity is on par with Output Agreement (OA), making it easy to communicate and apply in practice, such as in labeling tasks or educational settings.

We view EA as a simple yet effective step toward addressing the challenge of designing SD-truthful mechanisms. As some reviewers have noted, it opens the door to a promising line of research with substantial opportunities for extension and improvement.

Addressing the Imbalanced Main Body

We apologize for not motivating EA clearly enough. We aim to motivate EA throughout Sections 3-4, where we systematically demonstrate why existing mechanisms fail to achieve SD-truthfulness. In particular, Example 3.1 shows that "always reporting the same signal" is a strategy that thwarts the SD-truthfulness of CA. This is because agents can strategically adjust (reduce) the variance of their scores by misreporting, resulting in a score distribution not dominated by truth-telling. Therefore, EA prevents this. It effectively controls the prior distribution of reports so that misreporting cannot change the variance of scores. If an agent's reports do not match the preset distribution, it flips the reports so that it does. Because of this, an agent cannot artificially increase or decrease variance by submitting more or fewer reports of a particular signal.

The current paper structure deliberately builds this motivation: Section 3 establishes that existing mechanisms fail SD-truthfulness, Section 4 shows that simple rounding approaches have limitations, and Section 5 introduces EA as a principled solution. However, we recognize that this connection could be made more explicit. In the potential camera-ready version, we will enhance the presentation to make the logical flow from the limitations of existing approaches to EA's design more transparent to readers.

Dear Reviewer AWMx,

Thank you for your review. We appreciate your recognition that the concerns have been addressed. Your review has been very helpful in refining our work.