Stochastically Dominant Peer Prediction
Authors: Yichi Zhang
Shengwei Xu
Grant Schoenebeck
David Pennock
Venue: NeurIPS 2025 poster ()
Keywords: Information elicitation
mechanism design
crowdsourcing
Primary area: theory

Abstract: Eliciting reliable human feedback is essential for many machine learning tasks, such as learning from noisy labels and aligning AI systems with human preferences. Peer prediction mechanisms incentivize truthful reporting without ground truth verification by scoring agents based on correlations with peers. Traditional mechanisms, which ensure that truth-telling maximizes the \textbf{expected scores} in equilibrium, can elicit honest information while assuming agents' utilities are \textbf{linear functions} of their scores. However, in practice, non-linear payment rules are usually preferred, or agents' utilities are inherently non-linear.

We propose \emph{stochastically dominant truthfulness (SD-truthfulness)} as a stronger guarantee: the score distribution of truth-telling stochastically dominates all other strategies, incentivizing truthful reporting for a wide range of monotone utility functions. Our first observation is that no existing peer prediction mechanism naturally satisfies this criterion without strong assumptions. A simple solution - rounding scores into binary lotteries — can enforce SD-truthfulness, but often degrades \emph{sensitivity}, a key property related to fairness and statistical efficiency. We demonstrate how a more careful application of rounding can better preserve sensitivity. Furthermore, we introduce a new enforced agreement (EA) mechanism that is theoretically guaranteed to be SD-truthful in binary-signal settings and, under mild assumptions, empirically achieves the highest sensitivity among all known SD-truthful mechanisms.

Stochastically Dominant Peer Prediction
Yichi Zhang DIMACS, Rutgers University yz1 rutgeeee edu
Shengwei Xu University of Michigan, Ann Arbor shengwei @umi edu
David Pennock DIMACS, Rutgers University dpennockédimacs www.aaacc.ttttrre....mmmm edu
Grant Schoenebeck University of Michigan, Ann Arbor schoeneb@umich. edu
Abstract
Eliciting reliable human feedback is essential for many machine learning tasks, such as learning from noisy labels and aligning Al systems with human prefer- ences. Peer prediction mechanisms incentivize truthful reporting without ground truth verification by scoring agents hased on correlations with peers. Traditional mechanisms, which ensure that truth-telling maximizes the expected scores equilibrium, can elicit honest information while assuming agents' utilities are linear functions of their scores. However, in practice, non-linear payment rules are usually preferred, or agents' utilities are inherently non-linear.
We propose stochastically dominant truthfulness (SD-srutthullees)) stronger guarantee: the score distribution of truth-telling stochastically dominates all other strategies, incentivizing truthful reporting for wide range of monotone utility func- tions. Our first observation is that no existing peer prediction mechanism naturally satisfies this criterion without strong assumptions. simple roludion-rrunding scores into binary lotteries-cal enforce SD-truthfunness, but often degrades sensi- tivity, key property related fairness and statistical efficiency. We demonstrate how a more careful application of rounding can better preserve sensitivity. Further- more, we introduce new enforced agreement (EA) mechanism that is theoretically guaranteed to be SD-truthful in binary- settings and. under mild assump- tions, empirically achieves the highest sensitivity among all known SD-truthful mechanisms.
Introduction
Information elicitation studies how to design mechanisms that incentivize honest and high-effort human feedback. In this framework, a principal seeks reliable responses regarding a set tasks from strategic agents who motivated by the designed rewards. For example, Al companies collect human preferences to align language models via RLHF [Ouyang et al. 2022). J. and MOOCs use peer grading evaluate complex assignments at scale Piech al. [2013). A key challenge is designing scoring mechanisms that accurately assess the informativeness of agents' reports.
Peer prediction provides elegant solution for settings where ground truth is unavailable costly to obtain, such as in subjective tasks Miller et al., 20055. Instead of relying on external validation, peer prediction scores agents based on the correlation between their reports and those of their peers. The scoring mechanism is designed to be truthful so that everyone reporting truthfully forms a Bayesian Nash equilibrium, ensuring that truth-telling maximizes each agent's 's expected score.
key assumption underlying the effectiveness of existing peer prediction mechanisms is that agents' utility is linear function of their score. This assumption is reasonable in some cases, such as when agents are solely motivated by monetary payments, which can be straightforwardly designed
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

linear transformation of the peer prediction scores. However, in practice, non-linear payment rules such as threshold bonuses that reward workers only when performance exceeds cutoff are often preferred for their budget efficiency and flexibility (Zhang and Schoenebeck [023a] Moreover, agents' intrinsic utility functions are sometimes inherently non-linear. For instance, student graders care more about their final letter grades (e.g., A, B, C) than the real-valued numerical scores assigned by the mechanism. When agents' utilities are non-linear functions of their scores, truth-telling is no longer guaranteed to be an equilibrium strategy.
Motivated by this limitation, we introduce the concept of stochastic Cominance-truthffe (SD-trutde -ttrutffull peer prediction mechanisms. This stronger notion of truthfulness requires that an agent's score distri- bution, when everyone reports truthfully, first-order stochastically dominates the score distribution under any unilateral deviation. As a result, SD-truthful mechanisms incentivize truth-telling for agents with any utility function that monotone increasing with the score.
1.1 Our Results
Our first observation is that no existing peer prediction mechanism is naturally SD-truthful under general information structures, i.c., under arbitrary correlations between agents' signals. We examine three widely studied mechanisms that compute scores the average of multiple simple discrete scores, including Output Agreement (OA), Peer Truth Serum (PTS) [Faltings et al. 2017]. and Correlated Agreement (CA) [Shnayder et al.) 2016). Mechanisms with complex scoring rules such as those based on cartiuoou-vallueee estimates of mutual information Kong and Schoenebeck (2019). Kong 2020), , [ccheenebeck and Yu 2020]-are are unlikely to satisfy SDDtruthfulness. Yet even these simple mechanisms fail to guarantee SD-truthfulness without strong assumptions on the underlying information structure.
Our second observation is that achieving SD-truthfulness is easy in principle but challenging to do well in practice. Given any truthful mechanism M with bounded scores S.M [Smnt, Ssup],
can define probability by normalizing the score: A 5 - E [0, 1]. We then score agents Seup Suat
via a binary lottery: S. = 1 with probability X and 0 otherwise. Although this approach, called the direct rounding reduction, trivially satisfies SD-truthfulness, greatly reduces sensitivity an important property related to the efficiency and ex-post fairness of a mechanism. At high level, sensitivity measures how much a mechanism's 's score responds to changes in the information contained in an agent's 's reports, normalized by the standard deviation of the scores.
To overcome this limitation, we propose the partition rounding reduction, which helps partially recover the sensitivity of the original mechanism. The idea is to divide the questions into K disjoint subsets and apply the original mechanism separately within each subset to compute an individual score. The final score for an agent is then the average of K i.i.d. individual scores after applying direct rounding. Intuitively, this approach improves sensitivity by reducing variance through the aggregation of multiple independent scores.
However, the partition rounding process cannot fully recover the sensitivity of the original mech- anisms, implying additional room for more sensitive peer prediction mechanisms. We introduce novel mechanism called enforced agreement (EA) that is shown to be the most sensitive SD- truthful mechanism in the binary-signal setting. EA aims to replicate the key advantage of OA its high sensitivity-whie while relaxing the strong assumptions the information structure required for SD-truthfulness.
EA works by enforcing pre-determined empirical distribution of signals. In the binary setting, if Alice reports 0 on mg > nop questions (where no is the enforced count), the mechanism randomly flips mo no of them to 1. This trick removes agents' incentive to over-report majority signals. a strategy that undermines the truthful properties of OA. However, EA is only truthful but not SD-truthful when signals are non-binary, highlighting important future challenge in designing high-sensitivity SD-truthful mechanisms for more complex settings.
Lastly, our empirical results reinforce and complement our theoretical insights. In the binary- signal setting, we show that even a prior-free implementation of EA EA-simpll enforcing a uniform citribbttion-ouperffoo
other SD- mechanisms in most settings, including those that require prior knowledge. For non-binary-signe settings, the partition rounding reduction of PTS emerges as the most sensitive SD-truthful mechanism.
2

---

Table |I summarizes comparison of SD-truthful (implementations of) peer prediction mechanisms with respect to the assumptions they require and their sensitivities
Mechanisms
Requirements for SD-truthfulness
Output Agreement (OA)
delfnntmin signal
Enforced Agreement (EA) [This paper]
Binary and self self-predicting signal
Peer Truth Serum (PTS) [Faltings al. 2017
Self- Self-predicting signal
Correlated Agreement (CA) (hnayder ct al. 2016
Any signal
Matching Agreement (MA) Zhang and
Any signal
Schoenebeck 2023b
Table I: A Comparison of Discussed Peer Prediction Mechanisms ordered by sensitivity (from high to low), where PTS, CA, and MA require the partition rounding reduction achieve SD-truthfulness.
2 Related Work
The idea of peer prediction was proposed by MMlllr et al. [2005]. As the first discussion, their mechanism is not detail-free, i.e. the mechanism requires prior knowledge of the information structure (how agents' signals are correlated) to obtain truthfulness. There are two ideas to mitigate this limitation: (i) the single-task mechanism, which elicits the information structure directly from agents Prelece 2004]; and (ii) the multi-task mechanism, which assumes each agent responds to multiple 1..dd tasks but only requires eliciting signals rather than predictions (Dasgupta and Ghosh, 2013
Our study primarily relevant to the multi-task setting. We categorize multi-task peer prediction mechanisms into two types: peer agreement mechanisms Dasgupta and Ghosh| (2013). Faltings
et al. 2017), [Shnayder et al.] [016]] Zhang and Schoenebeck [023b], AAgawal et al. [011]] and mutual information mechanisms Kong and Schoenebeck [2019), Kong 2020). |Schoenebeck and Yu 2020 Schoenebeck et al. [2021] Kong [2024). In this paper, we primarily focus on peer agreement mechanisms, as SD-truthfulnest requires the mechanism's 's score to take a relatively simple form. Intuitively, this is because a complex scoring mechanism provides more opportunities for a cheating strategy to obtain one of the highest scores with larger probability than
which breaks SD-truthfulness. In Appendix[A] [A] we provide a more detailed discussion on why several classic mutual information mechanisms are not SD-truthful.
The score of a peer agreement mechanism can be viewed as an average of multiple individual scores, where each individual score takes values from small finite space, e.g. {0. 1}. For example, output agreement (OA) scores an agent based on the average number of questions that they agree with another agent. The first multi-task peer prediction mechanism lies in this category, which can achieve truthfulness in binary-signal setting (Dasgupta and Ghosh| 2013]. The correlated agreement (CA) mechanism generalizes their idea any tinite-signal setting [Shnayder et al., 2016). The peer truth serum (PTS) mechanism is a generalization of OA, which relaxes the self self-domin assumption to self- predictinn... In addition, two follow-up ups of CA aim to handle heterogencous agents (Agarwal ct al. 2017] and more general cheating strategics [Zhang and Schoenebeck 2023b].
Moreover, we note that the idea of rounding peer prediction scores into a binary lottery (see Section 5) was previously proposed by Miller et al.] [2005) to address risk-averse agents. What new in our work is the comparative analysis of various rounding reductions based on sensitivity, allowing to identify a more effective rounding approach. Furthermore, we formally prove that this idea extends beyond risk-averse agents and can be applied to any agents with increasing utility functions.
3 Model
We consider the multi-task peer prediction setting where two agents, Alice and Bob, answer the same n i.i.d. questions. For each question j. the agents receive discrete signals Xa,; Xo,5 Σ {O...., c- 1}, drawn from a fixed joint distribution Pr(X,, Xx.X,, X₁). In cases with more than two agents, we can reduce the case of two agents by, for any particular agent "Alice", choosing a random peer agent "Bob" for scoring.
MA is an extension of CA, and therefore shares similar requirements and properties.
3

---

Each agent E {a, by applies a strategy 8, O which maps from signals to distributions over the same space Ag. The report question j is denoted as Xi, 0, (X..,). We highlight two types of strategies: the truth-tellingg strategy т, which always reports the received signal, and the uninformative strategy μ., where reports are independent of the input. Examples of uninformative strategies include always reporting the same signal or randomly reporting signals according to the prior.
peer prediction mechanism M maps vectors of reports X, and X5 a score for Alice. Given an information structure (i.e., the joint distribution over signals) and a mechanism, the score is random function of strategies, denoted as (0a, 06). The randomness arises from the signals, strategies, and the mechanism itself. When it is clear from context, we omit the superseript M.
3.1 Truthful Guarantees
Existing peer prediction mechanisms focus on expected scores, guaranteeing that any deviation from truth-telling will only reduce the expected score. In this sense, truth-telling forms Bayesian Nash Equilibrium. Since our analysis centers on equilibrium behavior, we assume Bob always tells the truth. Under this assumption, the score assigned by the mechanism reduces to function of Alice's strategy 0, written as S (0).
Definition 3.1. peer prediction mechanism is truthful E[S(r) 2 E[S(0) for any 0 E e.
truthful mechanism guarantees that if agents have linear utility in their scores, truth-telling is Bayesian Nash Equilibrium-any deviation yields lower expected utility. However, as we argued earlier, assuming linear utility is often undesirable and, in some cases, unrealistic. Instead, we aim to design truthful mechanisms for a broader and more reasonable class of utility functions- those that are simply increasing in score. This motivation naturally leads to the concept of stochastic dominance.
Definition 3.2. A peer prediciton mechanism is stochastic dominance-truthful (SD-truthful) if the distribution of S(r) first-order stochastic dominates (FOSD) the distribution of S(0) for any 0 O i.c. Pr(S(T) 2 t) 2 Pr(S(0)= 2 t) for any E R.
standard result microeconomic theory suggests that S(r) FOSD S(0) and only if ([((((())) Elu(S(0)) for every increasing utility function u [Hadar and Russell 1969]. Since linear utility functions are also increasing, every SD-truthful mechanism is also truthful.
3.2 Sensitivity
In practice, effective scoring mechanism should meaningfully evaluate the information contained in agents' reports and reward more informative reports with higher scores. This motivates an additional design criterion, orthogonal to truthfulness, known as sensirivity [Zhang and Schoenebeck 2023a
To motivate the concept of sensitivity, we extend the model to incorporate agents' effort levels. This extension captures how the mechanism responds to marginal changes in information at equilibrium, iee. how the score varies when all other agents exert full effort while one agent adjusts her effort. In particular, on each question, we assume Alice exerts effort with probability always exerts effort and reports truthfully. When Alice exerts effort, the signal pair (Xa, X,) is drawn from the joint distribution Pr(X,, X,); in the extreme case where Alice exerts effort, the signals are independently drawn from the marginals Pr(X,) Pr(X,). That is, exerting effort produces a signal X₂ that is correlated with X, according to the joint distribution, while shirking yields an uninformative guess drawn from the prior Pr Pr(Xa). After observing the signal, Alice will report truthfully. Then, Alice's s score under mechanism M becomes a function of e, denoted as (M).)..
[0, 1), while Bob
Definition 3.3. The sensitivity of a peer prediction mechanism M at effort level is 8-M(e) = vels where V denotes the derivative operator and std denotes the standard deviation. sdd sd(SM((
Sensitivity measures how well mechanism's 's expected score responds to changes in effort- and thus, changes in information. Consequently, a trivial mechanism that always assigns a score of 1, though truthful, has zero sensitivity, its output is unaffected by effort.
Prior work /Zhng and Schoenebeck 2023a shows that when the score is normally distributed and agents rewarded based on the ranking of scores, sensitivity is sufficient statistic for budgetary

---

efficieeny:: mechanisms with higher sensitivity can elicit the same equilibrium effort level at lower budgetary cost. Moreover, Xu al. [2024] establish a one-to-one correspondence between sensitivity and measurement integrity [Burrell and Schoeneheck 2023]. implying that mechanisms with higher sensitivity generate scores more closely aligned with the true quality of responses. Together, these findings highlight sensitivity as practically meaningful and theoretically grounded property of peer prediction mechanisms, motivating our choice to use it as an additional dimension for comparison.
Our goal is to design SD-truthful mechanisms that also achieve high sensitivity.
Prior Mechanisms
To the best of our knowledge, no existing peer prediction mechanism naturally achieves SD- truthfulness without imposing strong assumptions on the information structure. In this section, we introduce three exemplary multi-task peer prediction mechanisms and explain why they are not naturally SD-truthful motivate methods.
4.1 Output Agreement (OA)
The oulput agreement (OA) mechanism scores Alice based on the fraction of questions on which both agents agree. The final score of OA is the average of n independent binary individual scores, ie. SOA 1 Eie(n) SOA where S 1 if both agents' reports agree on question i and otherwise. However, OA encourages over-reporting of the majority signal, which is truthful only under strong assumption.
Definition 4.1. Agents' signals are self-dominating if Pr(X, o|X, oo) > Pr(X, d'Ixa o) for any o' # o E Σ. Proposition 4.2. OA is truthful if agents' signals are self- reff-dominating.
In fact, OA is also SD-truthful when signals are self-dominating. This is because each individual score SOA takes only two values, meaning that S0 FOSD SPA((B) if and only if Pr(Sp (7) 1) 2 Pr(S(A(0)) =). Furthermore, the average of multiple i.i.d. scores that each SD-truthful remains SD-ttruhful (see Section 5.2). Consequently, for OA, SD-truuhfulness reduces to truthfulness.
4.2 Peer Truth Serum (PTS)
Self-dominance is usually considered strong assumption. [Radanovic et al. 2016 propose the Peer Truth Serum (PTS) which incentivizes truth-telling under a weaker assumption
Definition 4.3. Agents' signals are self-predicting if Pr(X, = o|X, = =0) > Pr(X, = o|X2 = o') for any o' E Σ.
PTS assumes symmetric, publicly known prior R(o)= Pr(X, =) = Pr(X, о). It repeatedly samples questions without replacement, and assigns an individual score S!TS 1/R(o) ) to Alice Xa, Xt, a, and 0 otherwise. The final score of PTS is the average of all S!T'S.
Proposition 4.4 [Faltings et al. 2017). PTS is truthful if agents' signals self-predicting.
Is PTS SD-truthful? The short answer is no. Each individual score SPTS takes at most |Σ| + 1 values, with the maximum being Smax 1/ (//(m.,)). where mmin is the least likely signal un- der the prior. A necessary condition for PTS to be SD-truthful is that truth-telling maximizes Pr (T) = Smaz), which the probability of Alice agreeing with Bob on signal m While truth-telling, this probability is the joint distribution Pr(X, Jmin Xa Omin). However, if Alice uses an uninformative strategy that always reports Tmin, this probability increases to Pr(X, = 0. Therefore, although μ decreases the expected score, its distribution is not stochasti- cally dominated by truth-telling, meaning that there exists an increasing utility function under which Alice strictly prefers p to r.
II the binary signal setting, self- predicreditionn is equivalent to positive correlation, which is a strictly weaker condition than eef-nnomin.c.e
5

---

4.3 Correlated Agreement (CA)
The correlated agreement (CA) mechanism (Shnayder et al., 2016 takes two questions to compute an individual score which has three possible values: -1, 0. and I. Suppose the joint distribution Pr(X.. is known. The CA mechanism first computes the delta matrix Ao.or Pr(X, a, Xb = o²) Pr(Xa a σ) Pr(X, o'), which is the difference between the joint distribution and the product of marginal distributions. Let TA (a, d') Sign( (a, be the agreement function where Sign(z) 1 if >> O and 0 otherwise. Intuitively, Ta (a, o²) = if the pair of signals (") appears more often on the same question than on distinct questions.
Then, CA repeatedly samples bonus question j and a penalty question k. For an individual score SCA, Alice gets 1 if both agents agree on j and gets -1 if her response on j agrees with Bob's response on k. i.e. SCA TA (Xa.j, X - (X x,,x). Since each bonus question can be paired with
penalties, the final score is the average over nnn - 1) individual scores.
Intuitively, the CA mechanism works by encouraging correlations on the same question and penalizing correlations on distinct questions. Consequently. if Alice always reports the majority signal, the frequency of agreements on the bonus question will be identical the frequency of agreements on the penalty questions, which results in a score of O. Prior work shows that when Pr(X... X,) is known (or accurately estimated), CA is truthful-and in fact, informed truthful (Shnayder et al. 2016].
Is CA SD-truthful? that the original implementation of CA described above is not SD-truthful.
The answer depends on the implementation. The following example illustrates
Example 4.1. Suppose n 2, so that Alice knows each of the two questions she answers will be used once as the bonus question and once as the penalty question. Her final score is the average of two individual scores, each with SCA E (-1, 0, 13. Thus, the final score has five possible values: SCa (-1, 0,5,,, 1}. A necessary condition for SD- SD-rruthfulness is that Pr(SCA(T) -1) < Pr(SCAA(A) (0) -1) for any strategy 0. However, we show that this does not hold in general.
Suppose the signals are positively correlated, i.e. Ta is a diagonal matrix. Alice receives -1 and only if she reports different signals on the two questions and Bob disagrees on both. Under truth-telling, this happens with probability (T)
of
0, X, Pr 1, X, 0). However, if Alice always reports the same signal (e.g.. ul(r) = 0 for any σ), she can avoid this outcome entirely. Therefore, μ is not stochastically dominated by т.
-) = 2 Pr(X,
This warns that repeatedly using the same question as the bonus the penalty question will sabotage the SD-truthfulness of CA.
5 A Rounding Reduction For Stochastically
-raiinan-Truthhllneess
We introduce a straightforward rounding reduction that maps any truthful mechanism to an SD- truthful one. However, this approach often comes at a huge cost of sensitivity. To address this, we propose a more refined rounding method that partially restores the original mechanism's sensitivity.
5.1 Direct Rounding
Consider a peer prediction mechanism M that assigns Alice a score S.M with bounded support S. < oc and S.M > -co. In direct rounding, normalize the score probability: XM
5MM - E [0, 1]. Alice's final score S.M is then determined by a binary lottery: receiving I with probability M and otherwise.
S:M-
Proposition 5.1. The direct rounding reduction of a truthful mechanism with bounded scores is SD-truthful.
Intuitively, because direct rounding always outputs a Bernoulli score. SD-truthfulness simply implies that truth-telling should maximize the expected success probability. But the expected success probability is just the success probability. By our design of M the success probability is a linear function of the final score S.M, which proves equivalence between SD-truthfulness and truthfulness.
However, scoring agents via a single binary score is clearly not practical. The following proposition suggests that direct rounding usually destroys the sensitivity of the original mechanism. Let (M)

---

and (e) be the sensitivity of M and its direct rounding reduction. Additionally, let m (=) and std (e) be the expected score and the standard deviation.
Proposition 5.2. The sensitivity ratio between a mechanism and its direct rounding is:
V(SM mM)c)) (mM(c) - (M)
(M)))
(ed
This ratio is typically large. For example, the final score of OA is averaged Binomial Bin(n, m (e)), whose standard deviation is /m m Thus, the sensitivity ratio between OA and its direct rounding is vn. This illustrates key drawback of direct rounding: it greatly reduces the sensitivity by climinating the benefit of averaging over multiple questions.
5.2 Partition Rounding
To reduce variance of and improve sensitivity, we aim to better leverage the information from all questions. In particular, if the final score of S.M is the average of K independent individual scores S.M. we can apply direct rounding to each S:M and take the average. This motivates the idea of partition rounding. We first partition the n questions into K disjoint subsets, using each to compute an individual score. Each score then directly rounded as Section 5.1 and the final score S. is the average of the K rounded scores. The following lemma proves the feasibility of this idea.
Lemma 5.3. Let S = K EiEKK: Sü, where the individual scores S; are i..d.. Then, S(T) first-order stochastically dominates S(0) if and only if each individual score St(T) first- stochastically dominates (!).
Proposition 5.4. The partition rounding reduction of a truthful mechanism with bounded scores is SD-truthful.
We defer the proof of Lemma 5.3 which follows from a straightforward coupling argument, to Appendix F3 Proposition 5.4 then follows directly from this lemma and the SD-truthfulness of direct rounding.
We now show that the partition rounding reduction can partially recover the sensitivity of the original mechanism. The key observation is that the final score under partition rounding is the average of
n.M-st with m-M being binomial variable, i.e. (e) * Bin(K, (e)), where XM( SM St
the expectation of the individual score. Putting this into Definition 3.3 gives us the sensitivity of the partition rounding reduction
(m) VK
8M (M)))= V (mm((e) S.M) (SMMp me))
(I)
The sensitivity of the partition rounding reduction is exactly VK times that of the direct rounding reduction. This means that by using partition rounding, we can recover substantial portion of the original mechanism's 's sensitivity.
In Appendix B
present the sensitivities of the partition- versions of the three mechanisms discussed. We summarize the limitations of these mechanisms below which motivates the design of a new SD-truthful mechanism introduced in the next section.
OA is already SD-truthful without rounding and thus has high sensitivity. However, OA is SD-truthful only for eeff-dominatin signals.
PTS requires rounding to ensure SD-truthfulness. Therefore, when the prior of signals is biased, PPS becomes large, which turn leads to a low sensitivity.
sup
CA uses two questions to compute an individual score, so K = n/2. Furthermore, only bonus questions contribute to sensitivity, while penalty questions are used to enforce truth- fulness. This dilutes the sensitivity by half again. Therefore, only 1/4 of the questions count for the sensitivity of the partition-rouna of the partition-rounded CA is only half of that of the original implementation.
CA. Hence, even without rounding, the sensitivity
7

---

6 The Enforced Agreement Mechanism
This section aims to present a novel mechanism with high sensitivity, which does not require the above rounding reduction. To motivate our idca, we begin by summarizing the key lessons learned from the previous discussions.
First, Example 4. shows a particular type of strategy that prevents previous mechanisms from being SD-truthful: reducing/changing the variance of scores, e.g. by always reporting the same signal. This inspires our enforced agreement (EA) mechanism, where the idea is to control a randomness level within agents' reports so that strategic manipulations cannot arbitrarily alter the variance of the scores.
Second, our analysis of sensitivity in Section 5.2 suggests that a high-sensitivity mechanism requires a larger number of partitions K and a smaller score range Soup Sint. This insight guides to use just one question to compute an individual score (so K n) and avoid the need for rounding. We show that EA meets these criteria.
We first prove the SD-truthfulnness of EA in the Eimary-signal setting, and then establish a negative result explaining why it fails ensure SD-truthfulness when signals non-binary. Nonetheless, we show that EA remains truthful in non-binary settings when the signal structure is known or can be accurately learned.
6.1 EA in the Binary-signal Setting
We introduce EA in the binary-signal setting and defer the discussion for general settings to the appendix. The idea of EA is to control the marginal distribution of Alice's reports. In the binary setting, the mechanism commits to target empirical distribution $- = (ng, n1) where Bg + n2 = n. The mechanism expects Alice to report signal i on exactly n, out of n questions. If Alice's actual distribution & xx.-- = (ma, mi) and suppose W.L.O.G. that mo > no. the mechanism randomly selects mn no of her O-reports and flips them to 1, After enforcing 4 Alice is scored using the output agreement mechanism (OA).
Compared with OA, the enforcement process in EA prevents Alice from benefiting by over-reporting the majority signal. However, this enforcement introduces dependencies across questions, so the binary agreement scores are no longer i.i.d., and Lemma 5.3 does not apply. Our main result shows that EA is SD-truthful when signals are self seff-prediction (Definition)
Theorem 6.1. If Σ = 2 and signals are self- predictrd,,,, the enforced agreement mechanism is SD SD-truthful for any 4
We defer the detailed proof to the appendix and present the main ideas below. Note that the final score of the enforced agreement mechanism is the average of n Bernoulli variables, each with a potentially different success probability. In the binary binary-signal setting, there are four possible success probabilities in total total-P;; P.j = Pr(X, = X, = i) for i.j E {0. repressnnnn the probubility of Bob observing (and reporting) j question conditioned with success probability Pij corresponds to a question on which Alice observes but is flipped to j either by the mechanism or by Alice herself. Suppose W.L.O.G. that mp no. meaning that the mechanism will randomly flip mo - no reports of Alice from 0 to 1 under truth-telling. In this case, the final score of Alice is the average of three binomials:
Alice observing i. A Bernoulli variable
n (r) ~ Bin(noo, + Bin Pm)) + Bin no: Po1)
We show that for any untruthful strategy, the resulting final score can be written n SEA (0)~ Bin(no - k, Poo) + Bin(m; - k, + Bin no + ki po1) + where 0 < k < min(no, m1). Under the self-prediction condition, Poo > P10 and Pı1 > P01- Therefore, any untruthful strategy can only reallocate & samples from two binomial distributions with higher success probabilities to those with smaller success probabilities. Via a simple coupling argument, we can see that S(Ø) is first-ordered stochastically dominated by S(r).
Additional results are provided in Appendix C First, we show that EA is not generally SD-truthful in the non-binary setting. Strategic signal permutations can produce score distributions that are not stochastically dominated by truth-telling. However, EA remains truthful when the information structure is known or well estimated. Moreover, we derive closed-form expression for the sensitivity- maximizing 4 enabling computation of the optimal enforcement from the information structure.
8

---

7 Empirical Evaluations of SD-Truthful Mechanisms
In this section, we empirically compare the sensitivity of the proposed mechanisms across various settings. The results support theoretical findings: EA consistently exhibits the highest sensitivity among SD-truthful mechanisms in the binary-signal setting (except when the signal prior nearly uniform).
7.1 Datasets and Experiment Setup
We use two real-world datasets to estimate the information structure between two agents. The first dataset contains binary labels classifying whether compound is appropriate or inappropriate to be synthesized [Baba et al. 2018). The second dataset collects the annotations of the sentiment 300 tweets, where the size of the signal space is [Venanzi et al.) 2013). We denote these information structures as JI and J2 respectively, and defer the details to Appendix E.
In the main body of the paper, we focus SD-truthful mechanisms, which include:
OA (Section 4.1). which SD-truthful only when signals are self-dominating.
PTS-partition-ronnd the partition rounding reduction of PTS (Section 4.2), where we re-weight
every individual score using signal prior and take the average.
CA-partition-round the partition rounding reduction of CA (Section 4.3 where we create
= n/2 partitions of questions and score agents the average of the individual CA score for each partitionn after rounding.
MA--parittoon-roudd-- partition rounding reduction of the matching agreement mechanism (Appendix(D) D).
EA-prior EA with enforcement + Pr(X.).
EA-uniform EA with 4; 1/121, Vi E.
EA-optimal EA with the
4 computed according to Appendix C.3
For information structures with binary-signal settings, sensitivities can be computed analytically shown in Appendix B For general cases, estimate sensitivity using Monte Carlo approach. In particular, we simulate reports to each the n questions with both agents exerting full effort and run M compute the scores. Repeating this process for T = 20,000 times yields T i..d. samples of (c)).. We then compute the score of Alice when she deviates to a lower effort level at Ac 0.8, and obtain T samples of 5 Ae). The sensitivity of at effort is then estimated as 3|s (e)) ((sM))eeeeeee)) s(d(sM(e)))
Ae
7.2 The Sensitivity of SD- Mechanisms
We now compare the sensitivity of the discussed SD-truthful mechanisms. In Figure la show the sensitivity when the prior of the binary signal is varied, i.e. Pr[Xa = 0] E [0.1, 0.9). and the number of questions 100.
Figure lb and Ic present sensitivity as the number of questions n e {10, 20..... ......... 100} increases,
under information structures J1 and J2, respectively. In J2. where [ 2, EA is no longer SD-truthful; however, we still include its sensitivity for comparison.
Baprer
EApier
15
Whoerismmee
ITSpankssoocad
Ok potkoneee
1.5
1.8
0A
03
02
15
100
10
32
70
Niedic
Ages
54
A.e
(a) Varying prior Pr[X.-
(b) Varying #tasks under J1
(c) Varying #tasks under
Figure 1: A Comparison of the Sensitivity of Different Mechanisms.

---

We make the following observations. First, although the partition reductions of CA and MA are SD-truthful for general settings, their sensitivities are dominated by other SD-truthful mechanisms. This is due to their requirements of the penalty questions, which do not contribute to the sensitivity, and the fact that they require two questions to compute an individual score.
Second, PTS performs well when the signal prior is nearly uniform, i.c. Pr(X,, = 0) ~ 0.5. Intuitively, this is because the rounding factor that enlarges the gap S inf shrinks when the prior is close uniform. However, even slight bias, i.e. Pr((X, 0) 0.5| 0.03 causes PTS-partition-rrunnd to be outperformed by EA.
Third, observe that enforcing the signal prior in EA closely approximates the optimal enforcement. Remarkably, even EA-uniform, a detail-frre free version that doesn' require knowledge of the prior, con- sistently outperforms PTS partition-rous
which does rely on prior knowledge for SD-rruthfulness.
Additionally, we note that the partition-rounde roundinn reduction of MA coincides with that of CA when signals are binary (see Appendix D). Consequently, the blue and red overlap in Figure Ta and 1b
Due to space constraints. defer the comparison between partition-rounding reductions and their original implementations to Appendix E.2 These results further show that high-sensitivity mecha- nisms perform strongly in practical, incentive-aligned environments, underscoring the importance of EA.
Conclusion and Future Work
This paper initiates the discussions of stochastically dominant-truthful (SD-truthful) peer prediction mechanisms, which ensure that in equilibrium, the score distribution under truth-telling first-order stochastically dominates any other strategy. Unlike traditional peer prediction mechanisms, which rely on linear utility assumptions, SD-truthful mechanisms can preserve truthfulness for any increasing utility function. We show that existing mechanisms fail to naturally achieve SD-truthfulness and propose rounding method to enforce it. However, this process often reduces the sensitivity of the original mechanism, making it less efficient in practice. Additionally, we introduce the Enforcement Agreement (EA) mechanism, which empirically shown to have the highest sensitivity among all SD-truthful mechanisms in the binary-signal setting except when the signal prior is nearly uniform.
Future work is needed investigate more sensitive SD-truthful mechanisms beyond the binary-signal setting. A promising next step is to explore approximate SD-truthfulness, which allows truth-telling lose small utility for some utility functions. This relaxation could lead mechanisms with better sensitivity. Furthermore, SD AD-truthfullness alone does not ensure that truth-telling maximizes expected rewards a tournament (rank-order rewards). Because agents' scores are correlated, a manipulation strategy with dominated score distribution may still raise an agent's 's chance of ranking above others by altering these correlations. An important direction for future work is therefore the design of peer prediction mechanisms that provide incentive guarantees under tournaments.
Broader Impact
On the positive side, our method enhances the reliability and efficiency of crowdsourced data collection, which supports more trustworthy machine learning systems and reduces reliance on expert annotation. However, mechanisms that incentivize effort may unintentionally disadvantage contributors with limited time, resources, or familiarity with the task, raising fairness concerns. We aim to mitigate these risks by designing robust, broadly applicable mechanisms and promoting transparency in their deployment.
Acknowledgment
This work was partly carried out the DIMACS Center Rutgers University and supported by NSF #2313137.
10

---

References
Arpit Agarwal, Debmalya Mandal, David Parkes, and Nisarg Shah. Peer prediction with heteroge- neous users. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 81-98. ACM, June 2017.
Yukino Baba, Tetsu Isomura, and Hisashi Kashima. Wisdom of crowds for synthetic accessibility evaluation. Jourmal of Molecular Graphics and Modelling, 80:217-223, 2018.
Noah Burrell and Grant Schoenebeck. Measurement integrity in peer prediction: A peer assessment case study. In Proceedings of the 24th ACM Conference on Economics and Computation, EC '23, page 369-389, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701047. doi: 10.1 10.11455388050733577444 URL (tRp::tps:///ae http:://ioi..oo///.//// 11111/001114//50550 3597744
Anirban Dasgupta and Arpita Ghosh. Crowdsourced judgement elicitation with endogenous profi- ciency. In Proceedings of the 22nd international conference on World Wide Web, pages 319-330. ACM, 2013.
Alexander Philip Dawid and Allan M Skene. Maximum likelihood estimation of observer error-rates using the em algorithm. Journal of the Royal Statistical Sociery: Series (Applied Statistics), 28 (1):20-28, 1979.
Boi Faltings, Radu Jurca, and Goran Radanovic. Peer truth serum: Incentives for crowdsourcing measurements and opinions, 2017.
http://as/117..000
Josef Hadar and William R. Russell. Rules for ordering uncertain prospects. The American Economic Review, (9(1)25 34, 1969. ISSN 00028282. Utt/tttp://ww. wtg/stable//111099
Yuqing Kong. Dominantly truthful multi-task peer prediction with constant number of tasks. In Proceedings of the fourteenth annual acm-siam symposium on discrete algorithms, pages 2398-244 2411. SIAM, 2020.
Yuqing Kong. Dominantly truthful peer prediction mechanisms with a finite number of tasks. J. ACM, 71(2), apr 2024. ISSN 0004-5411. doi: 10.1145/3638239, URL 1145/3638239
Yuqing Kong and Grant Schoenebeck. An information theoretic framework for designing information elicitation mechanisms that reward truth-telling. ACM Transactions on Economics and Computation (TEAC), 7(1):1-33, 2019.
Nolan Miller, Paul Resnick, and Richard Zeckhauser. Eliciting informative feedback: The peer- prediction method. Management Science, (1(9))1359-133 2005.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730- 27744, 2022.
Chris Piech, Jonathan Huang, Zhenghao Chen, Chuong Do, Andrew Ng, and Daphne Koller. Tuned models of peer assessment in mooes. arXiv preprint arXiv:/30..2579, 2013.
Drazen Prelec. A bayesian truth serum for subjective data. science, 306(5695):462 466, 2004.
Goran Radanovic, Boi Faltings, and Radu Jurca. Incentives for effort in crowdsoureing using the peer truth serum. ACM Trans, Intell. Syst. Technol. 7(4), March 2016. ISSN 2157-6904. doi: 10.1145/2856102
Grant Schoeneheck and Fang-Yi Yi Yu. Learning and strongly truthful multi-task peer prediction: A variational approach. arXiv preprint arXiv:2009. 14730, 2020.
Grant Schoenebeck, Fang-Yi Yi Yu, and Yichi Zhang. Information elicitation from rowdy crowds. In
Proceedings of the Web Conference 2021, WWW '21, page 3974-3986, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383127. doi: 10.1 1455/444238111 2.44494994... 33449400.
URL https: /doi. wooo/oo.11. 10. 1145/344238 3449840

---

Victor Shnayder. Arpit Agarwal. Rafael Frongillo. and David C. Parkes. Informed truthfulness in multi-task peer prediction, 2016. URL https://arxiv, org hts//bs//16000 03151
Matteo Venanzi, William Teacy, Alexander Rogers, and Nicholas Jennings. Weather sentiment amazon mechanical turk dataset, 2015. URL httph:://eprintss.stttoe wwt.:stttto....../.....
Shengwei Xu, Yichi Zhang. Paul Resnick, and Grant Schoenebeck. Spot check equivalence: interpretable metric for information elicitation mechanisms. arXiv preprint arXiv:2402.13567, 2024.
Yichi Zhang and Grant Schoenebeck. High-effort crowds: Limited liability via tournaments. In Proceedings of the ACM Web Conference 2023, WWWW '23, page 3467-3477, New York, NY, USA, 2023a. Association for Computing Machinery. ISBN 9781 150034466.. 3583334. URL https:://oi..org org/ 10. 1145/3543507 3583334
doi: 10.1145/3543507.
Yichi Zhang and Grant Schoenebeck. Multitask peer prediction with task-dependent strategies. In Proceedings of the ACM Web Conference 2023, WWW '23, page 3436-3446, New York, NY, USA, 2023b. Association for Computing Machinery. ISBN 9781450394161. doi: 10.1145/3543577. 3583292. URL https: //doi. org /00 1145/3543077 3583292
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Please abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: As mentioned several times in the paper, our solution requires a binary-signal assumption achieve the strong truthful guarantee proposed in the paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Iiaification:Pleasss see Section for detailed assumptions and theory. Proofs are left in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
The datasets and parameters of our experiments presented in Section
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

reproducible, they Answer: [Yes]
Justification:
We provide the code for our experiments in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.c cc/
Polccyy)l for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ https/ccccbbccccgcccccce htte:/guuide//oeeSuuunn
sesiiisssiiiyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Our experiments do not require training. Details of set-up and parameters shown in Section 7 and Appendix
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Our figures are visualizations of analytical results where there is error, or averaged using a large number of independent trials so that the error bars are all very close to zero.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: Our experiments do not involve dense computing, and can be conducted on laptops.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:p////aurrpp..cc//p/b///aaas
Answer: [Yes]
Justification: There is violation of the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We provide broader impacts section right after the conclusion section.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This work does not release any models or datasets with a high risk of misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We believe all datasets and LLMs used in this paper are properly cited.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, papprswiiiiiie theode com datastts has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: This paper releases code used for running the experiments. The code is documented and provided alongside the submission to ensure reproducibility. No new datasets or models are introduced; all experiments are based on public simulated data.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooell as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The paper does not involve data collection from human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve data collection from human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMS if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs were not used in the development of the methods, experiments, analysis in this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMMs as any important, original, non-standard components.
Please refer to our LLM policy http://p///errrroooooooooooooooa for what should or should not be described.
A Continued Related Work: Mutual Information Mechanisms
We review several classic peer prediction mechanisms that evaluate agents by estimating mutual information, and illustrate why these mechanisms fail to achieve -D-truthfulness. First, proposed by Kong and Schoenebeck [2019]. we can estimate the empirical point-wise joint distribution between Xa. and X6., using pairs of reports from two agents, (Xa.j- Xa.))E(()) Note that because questions are i.i.d.,
reports from all questions to estimate the same distribution. Then, plugging the learned empirical joint distribution into an f-divergence operator returns (biased) estimate of the f point-wise mutual information. The following the score for the f-mutual information mechanism Kong and Schoenebeck] 2019]
SÉMI - (Pr (Xar, Pr (Xa.) Pr (Xv:))
However, because the estimation is biased, the f-mutual information mechanism is only asymptoti- cally truthful, meaning that it requires an infinite number of i.i.d. questions to satisfy Definition 3.1 When the number of tasks is small, there is non-zero probability that truth-telling is not the best response. For example, if Alice observes "yes" on all her questions, which happens with a positive probability, then she knows that truth-telling will always result in score of regardless Bob's responses. This is because the estimated point-wise joint distribution is the same as the product of marginal distributions. However, by misreporting "no" on some questions. she has a non-zero probability of receiving positive score. In comparison, such deviations are discouraged under the enforced agreement (EA) mechanism because the mechanism will randomly flip the responses on behalf of the agent (see Section 6).
Several follow-up works, such as the Determinant Mutual Information (DMI) mechanism by Kong (2000 and the pairing mechanism by [Schoenebeck and Yu [2020), propose different ideas to estimate the mutual information. However, they still not SD-truthful. Consider the strategy from Example where Alice always reports "yes." Under both DMI and the pairing mechanism, this strategy always yields score of zero. In contrast, similar to the CA mechanism, there is positive probability that truth-telling may result in negative score. Thus, this constant- constant-reporting strategy is dominated by truth-telling under these mutual information- based mechanisms whose score can take negative values.
B Sensitivity of Prior Mechanisms Under Partition Rounding
We now map the exemplary mechanisms discussed in Section into the partition rounding framework. In particular, we specify the key parameters K, Smnf Saup- and me;e) for each mechanism. Consider an information structure with joint distribution J, and the marginal distribution of Alice and Bob being M and Mb, respectively. Furthermore, Ma = Mr M denote the product of marginal distributions.
19

---

Output Agreement An individual score of OA, S is if both agents agree on question and 0 otherwise. Therefore, OA is the partition rounding reduction of itself with K n, Sint 0, and Soup 1. By definition, when Alice exerts effort, agents' signals on the same question is sampled from the joint distribution J; while if Alice does not exert effort, she will sample a signal from the prior, meaning that agents' signals on the same question is sampled from M. The expectation of an individual score at the effort level e is thus
m Pr(Xa: X1.s) (1 -e- Pr(m(Xa..)) (x = tr(J) + (1 e) tr tr(M).
This means that the derivative of the expected score w.r.t. effort is
Vm.
tr(J M) tr(A),
where A is the difference between the joint distribution and the product of marginal distributions, and tr(.) represents the trace of matrix, i.e. the sum of the diagonal entries.
Peer Truth Serum Similar to OA, each partition of PTS is composed of a single question so that K n, Sint O, and Saup prior. The expected individual score is
where min is the signal occurs with the smallest probability in
Mr min
Ja Mg
A M
A M
PTS (c) m
Σe- OES
+ (1- M2 l
Σ DEE
PTS Vm
(e)
Σ OCE
e.
Correlated Agreement The CA mechanism reguires two questions to compute individual score, meaning that K = n/22. By Proposition F.I and Lemma 5.3 when the signal space is binary, scoring Alice using SCA -ocA=Ei >x S without rounding is SD-truthful. However, when
[>] > 2. we have to use the partition rounding reduction of CA to obtain SD-truthful where Sinf = -1 and Saup 1. On the bonus question, the probability of receiving a score of 1 is given by Eoo'r (e Jo + +1- -Moor)) (o, o'). On the penalty question, the probability of penalizing a score of is given by En (e. MM + (1 ee) -M, Ta(a, Combining these,
m.A (A)(e) = Σ A To(o,o)) =
(m)
Σ ( 0,''E
O,T'EE
where (x)+ = - if > 0 and O otherwise. Putting these parameters into Equation returns the sensitivity of the partition rounding reduction for CA. However, note that by Proposition F. do not need to round the individual CA scores when |=|= = 2. This motivates variant of an SD-truthful implementation of CA that may have a slightly larger sensitivity in the binary- signal setting. We will
introduce and test this implementation in Section 7
We summarize the limitations of the above three SD-truthful mechanisms.
OA does require the partition rounding reduction to achieve SD-truthfulness and thus is likely to have high sensitivity. However, OA is SD-truthful only when signals are self-dominating.
PTS requires rounding to ensure SD- 3D-truthfullnes. The normalizing factor Me implies
that PTS will be less sensitive when the prior distribution of signals is biased.
For the CA mechanism, only bonus questions contribute to the sensitivity of the mechanism, while penalty questions are used to enforce truthfulness. However, CA requires two questions to compute single individual score, which means K n n/2 Therefore, even without rounding, e.g. when ΣΣ| 2, the number of effective questions is only one half of the available questions. Moreover, the rounding process divides each score by factor of 2, which further harms the sensitivity of the mechanism.
C The Enforced Agreement Mechanism (Continued)
C.1 Arbitrary Signal Space
Unfortunately, we show that the above idea does not generalize beyond the binary-signal setting. For general setting with Σ c, the enforced agreement mechanism can be characterized by an
We emphasize that increasing K by rerunning partitions is not SD-truthful (Example 4.1
20

---

enforced marginal distribution & = (mo..... ,c-,,) and an enforcement rule that ensures an agent's reports follow 4.
Let Alice's report vector Xa have an empirical marginal distribution & xx (rio. ................................ ma-1) 1). The enforcement rule can be characterized as a c x c matrix
(xa) (or simply if there is no confusion), such that Pi.j denotes the number of randomly selected questions on which Alice reports i and is flipped to j by the mechanism. By construction, Pi.j E Z20 for any i, E E. Furthermore, >; Pigj ny for any j E Σ and Σ, Pi.j fh for any E Σ.
Suppose Alice's signal vector Xa has marginal distribution 4, (mo......)) mc-1). 1). Under the enforcement rule, while reasoning the distribution the EA score, every (randomized) strategy can be characterized by mixture of) manipulation matrix. The entry Ui of a manipulation matrix denotes the number of randomly selected questions where Alice observes but is flipped to j either by the mechanism or by herself. Similarly, Di,5 Z2o for any i, E Σ, >; Di.j = n2 for any j E Σ, and E, 0z,5 m, for any i E Σ. In particular, let (p( denote the manipulation matrix corresponding to truth-telling under the enforcement rule p.
Given manipulation matrix 9 the final score of Alice is thus the average of c² binomials:
S
(0)
Σ Bin(drs:Pit),
IJEE
where Pıj = Pr(X, = Xa = 1) is the conditioned probability of agents' signals.
To obtain SD-truthfulness, we have to construct an enforcement rule such that for any (under some assumptions), any Xa, and any feasible 0, the random variable SEA is first-order stochastically dominated by (T)( This is particularly challenging when is large because i has e² 2c + degrees of freedom, yet we must identify a p such that o (p) dominates any other 0.
Three signals We show that even for the three-signal setting, EA SD-truthful only under very special type of information structure.
Definition C.1. Agents' signals are uniformly self-predicting if Pr(X, = i X, = =1) Pr(X, = i X, j) Pr(X, il X,- k) for any and k + i.
Consider the following enforcement rule:
Alice over-reports one signal. mh 2 n, while m, S ny for any j * i, the enforcement rule will randomly select n; m, questions which Alice reports i and flip them j for j E E and j *
Alice over-reports two signals. If my < ny while mn 2 n; for any + j. the enforcement rule will randomly select m. n, questions on which Alice reports i and flip them to j for
i E Σ and i +j. j.
This enforcement rule flips the minimum number of reports enforce & and thus named the minimal enforcement rule, denoted as p"
Proposition C.2. If Σ 3 and signals are relf-predicting the enforcement agreement mechanism is SD-truthful for any if and only if applies the minimal enforcement rule and signals are uniformly self-predicting.
We defer the proof to Appendix F.5 Our results imply that achieving SD-truthfulness using the EA mechanism is infeasible for arbitrary information structures beyond the binary-signal setting. Investigating alternative approaches, such as mechanism designs that leverage additional structure in the information space or stronger assumptions on agent strategies, remains interesting direction for future work.
C.2 Truthfulness of EA
Although the EA mechanism is not SD-truthful when |X]] > 2, we show that is still possible to obtain truthfulness long the information structure is known.
21

---

Given a report vector of Alice Xa with an empirical distribution & = (mo. mc-1), 1),, EA will apply the /P enforcement rule by solving the following integer programming.
max 1
Σ
01.5 Pij
KE
Σ Dis5 = njj VjE
s.t.
iEN:
Σ Dis = mi, ViE jEz
01.j E Z20.
Vi,jE
Suppose the optimal solution is 8* (X.)). The mechanism will then randomly select & (Xa) aid questions on which X. = i and flip them to j. for any i,j E E. After the enforcement step, Alice will be scored based on the output agreement mechanism.
Proposition C.3. For any enforcement & and information structure, if Xa) is known, the enforcement agreement mechanism with the IP enforcement rule is truthful.
The proof is straightforward. Note that to prove truthfulness, it is sufficient to show that truth-telling maximizes the expected score which is Σijes Vi, Pij. Because the mechanism will manipulate agents' reports in an optimal way by solving the above integer programming, no strategy can achieve higher expected score than truth-telling.
Note that when |>]] = 2 and signals self- self-predicting, the optimal solution to the above IP does not depend on the information structure Pij. In particular, the IP enforcement rule always flips the over-reported signal to enforce no zeros and no ones and does not flip any of the under-reported signal. This echos Theorem 6. which suggests the EA mechanism is 3D-truthful in the binary-signal setting without the knowledge of p.
Remark C.4 (Connection to Peer Truth Serum Faltings al. (017)) As illustrated in Section 4.2
PTS can be viewed as an output agreement mechanism (Section 4.1 where the score for agreement weighted inversely by each signal's 's prior. This weighigt shifts the probability of agreement from the joint distribution X.). which demands eeff-domnatting signals to ensure truthful reporting, to the conditional distribution Pr(X, Xa), which requires self-predicting signals.
In contrast, EA avoids using the prior Pr(Xa) by controlling the marginal distribution of Alice's reports. This approach similarly transforms the probability of agreement from the joint to the conditional distribution. However, the enforcement process creates additional incentive issues when the signal space large which requires complete knowledge of the underlying information structure. Consequently, if |>]] 2 and signals are self- ooff-rredictin, EA can obtain a stronger truthful guarantee (SD-truthfulness) without any prior knowledge; but for |>]] 2, requires more extensive structural information to guarantee truthfulness.
C.3 The Optimal Enforcement
We have established that when signals are binary and self- seff-predicting, EA with any enforcement & SD-truthful. In this subsection, we examine how the choice of enforcement, = (no, n no). influences the sensitivity of EA, and in particular, what is the sensitivity maximiizigi enforcement.
Fixing an information structure, the expected score given by EA, SEA ( e), can be viewed as function of the number of questions where the answers are enforced to zero, and Alice's s effort level, e. We first present an intermediate result suggesting that the standard deviation of S is independent of ng. This implies that the enforcement affects the sensitivity of EA only through VE,SEA(e)) (e)).
Lemma C.5. For fixed information structure, std (SEA(no, e)) is independent of na- i.e. std (SEA(no,e)) std (SEA(T) e)) for any no.n/ E 1...,...,,1
We next analyze how the derivative of the expected score depends on the choice enforcement. enforcement no is determined by a quantile of a binomial
We find that the distribution with success probability Pr(Xa = 0), where the quantile depends on the information structure.
22

---

Proposition C.6. ! = 2 and signals are self predicting, the sensitiiity enforcement of the EA mechanism (no. n no) satisfies that
......... max { lo (0.1.....n) F(K) <
V0o V61
160 %o1 + 7/11 Voo
where F(k) Ei Pr(X, Pr(
0) Pr(Xa 0))²~ is the c.d.f. of binomial random variable with success probability Pr(X. 0), and 1/65 Pr(X = Xa = Pr(Xp- =))
We defer the proofs of Lemma C.5 and Proposition
C.6 to Appendix F.6
D The Matching Agreement Mechanism
The matching agreement mechanism a follow-up of the correlated agreement mechanism aiming to address more complex cheating strategies Zhang and Schoenebeck [2023b]. Similar to CA, which determines "agreement" using the delta matrix (see Section 4.3) MA determines "agreement" using different method depending the information structure.
Definition D.1. Let P be |>] x Σ x |X] tensor where
T Taliaaaa = (r σT X = -2) - Pr(Xa -0 Xa = -a).
The agreement function is thus Tr- Sign(T),, i.e. Tr (01, 1 if F1.02.00 and otherwise.
Next, the mechanism randomly samples bonus question j and a penalty question & uniformly at ran- dom. An individual score computed using these two questions thus S. Tr In words, the matching agreement mechanism awards Alice a score of 1 if, when predicting her response on question b, the posterior conditioned on Bob's response to the same question provides a better prediction than the posterior conditioned on Bob's response different question g. Similar to CA, each bonus question can be paired with n - penalty questions. Therefore, the final score of MA is the average of n (n 1) individual scores.
Tr [Nas Xb.j N.
The Sensitivity of MA Under the Partition Rounding Reduction We further investigate the sensitivity of the MA mechanism under the partition reduction. The MA mechanism requires two individual score, implying that K n/2.. Clearly, Sint and S by definition. By Equation (T). to compute the sensitivity, we only need to compute the expected individual score m,(e) and its derivative. When Alice exerts full effort, the probability of obtaining score can be computed as follows:
questions to compute
m (1)= = Σ Pr(Xa, No, 02, Xo,A 03) Tr (01, 02 03)
01,09,03
Σ
oo
My Tr (01,02,00)
01
Σ
Mo
Tr 0z) + Σ Mo T (0),0,)00)))
01.02:03
1
Σ
(Jo Mo Tr (01,
2 01:72:033
(Note that Tr (a), 02, 03) (01,003000))
1
+
Σ
Mb Mà T Tonouos Tr (r1,),22,3))
2
2
01,02.05
Σ
M Mè (Tonooos)
2
01.02.03
where (x)+ if x
0 and 0 otherwise.
23

---

When Alice exerts no effort,
(A) = Σ
Pr(Xas Xaj = -1, Xn, = 02, X1, = 0z) Tr (01,
m
01,02
Σ
M M M -Tr 001,02)3))
01
Σ
M M M Tr 021,022)333
+ 2
Σ Mc, Ma, Ir (31,033)2)))
2
01.02.03
01.02.03
1
(Me, M M2, Ma, M M²x)
Tí (01,
2
2
01,02.03
(Note that Tp (01, = 11- -T 03))
The expected score while exerting effort e a convex combination of m. mMA(1I) and m (0). i.e. m. (c)
2 2 Ea M M (To,,o,,))* and Vm, M.MA (())
E...o o2.03 M Ma Mè, (To..
When signals are binary, we find that MA reduces to CA. Lemma D.2. When signals are binary, Eonor M M (T (To1,00,0) = Eo
Proof. First note that by definition, 1' = when 03. Therefore, when signals are binary,
Σ Ma (ToL
Σ
Ma. Mi-oz (T 0201))).-022*
Σ
Mo (To))200))
01.02.03
Σ
of Jon.l-o Ma.
01.02
Σ (Jo (1 (1-Ma,) ((Ma) Ja)n)) Ma.)" 01,02
(Signals are binary.)
Σ
(Jonoo Ma, -Ma
01,02
(A01
01.02
An immediate consequence of Lemma D.2 is that the expected score under MA is a linear transfor- mation the expected score under CA. This further implies that the partition rounding reductions of MA and CA has the same sensitivity under the binary-signal setting.
Proposition D.3. When signals are binary, (M)(e) = -CA(c) under the partition rounding reduc- tion.
Proof. By Lemma D.2 know that
m. AAAA(e)
1
Σ
Ma M³ (To 1
Σ
(Ao -= 1 +11 m, (()))))
01.09.03
01.02
MA
VmfA(e)
24

---

which is By Equation
1
(m) vn/2
(M)
((mmM (e) " (SAMA - m (e)
1. vm (c) vn/2
V MA() 2) ( m MA (e))
Vm. vn22
(mm + 1) (1 m (c((
= (c)
E Experiments (Continue)
All codes for our experiments are provided in httpss//gttaaal.ccm/arriiiagggg
E.1 Information Structure
For Section 7.2 we consider two real-world crowdsourcing datasets, each having signal space of size [Σn] = 2 and Σg] = 4. The information structure between pair of agents can be characterized by a Dawid-Skene model Dawid and Skene [9779] In particular. each task has an underlying ground truth w that is i.i.d. sampled from a prior distribution W. Conditioning on each agent receives a signal a according conditioned distribution where ri Pr(a = = =].
In the first dataset [Baba et al. 2018 18 agents each labels whether a compound is appropriate or inappropriate be synthesized. The prior of the ground truth and the conditioned signal distribution
are
0..955
0.095
W1 [0.613
0.387].
r1
0.283
0.717
In the second dataset Venanzi et al. 2015), 110 agents provide the annotations of the sentiment of 300 tweets. There are four ground truth labels and four possible signals where the information structure
0..770
0.122
0.084
0.0247
0.091
0.735
0.130
0.044
W/ = [0.196 0.241 0.247 0.316].
I2 =
0.033
0.062
0.866
0.039
0.068
0.164
0.099
0.669
E.2
The Sensitivity of Original Implementations
How much does the partition rounding reduction harm the sensitiviry? We compare the partition rounding reduction implementations of CA, MA, and PTS with their original implementations in Figure 2 To be clear, other than the implementations considered Section we consider the following implementation of the mechanisms.
PTS corresponds to the peer truth serum mechanism introduced Section 4.2 truthful but not SD-truthful.
CA corresponds the original implementation of the Correlated Agreement mechanism described in Section 4.3 which is truthful but not SD-truthful.
CA-partition represents the implementation where we get = n1/2 partitions of ques- tions and score agents the average of the individual CA score for each partition (without normalization). By Proposition F.I] CA-partition is SD-truthful when signals are binary.
MA corresponds to the original implementation the Matching Agreement mechanism described in Appendix D. which is truthful but not SD-truthful.
25

---

EAgour
EAsnnfom
optnnal
3,0
MAguttilion-mun
CAprrtiion-nnd
3.6
CA-petiion
2.5
2.5
2.0
2,0
1.5
1.5
1.0-
1.0-
0.5
0.5
Namber TTake pat Agent
Number Tanke pat Agent
(a) Mechanisms shown in Scction under J1
(b) Other Mechanisms under J1
EA-rrirr
MA
EAvunifom
PTS
Elinsisd Seuntsstt
MAA-patiiin--mun
Exinceed Sennitiitty
FTS partilon round
OA
10
20
40
50
70
80
90
100
10
20
40
50
70
80
50
100
Number of Tasks Agent
Number of Taaks Agent
Mcchanisms shown Scction 7 under
Other Mechanisms under
Figure 2: A Comparison of the Sensitivity of Different Mechanisms.
We observe that, relative to the original implementations (solid lines), the partition-roundingg reduc- tions (dashed lines) consistently exhibit lower sensitivity. This observation further demonstrates the superior sensitivity of EA mechanisms, as it has the property of SD-truthfulness in the binary setting with need for partition rounding reduction.
Additional Proofs
F1 The CA Mechanism
We first show that a single draw of the CA score is SD-truthful when =
Proposition F.1. When | 2, instead of taking the average, the mechanism that scores agents using an individual CA score SCA is SD-truthful
Proof of Proposition F.1 We first show that the agreement function TA is an identity matrix if and only if signals are self self-predicting. For simplicity. let Ja Pr(X, o, X, o') be the joint distribution, and let M Pr(X, o) and M Pr(X, a) be the marginal distribution of Alice and Bob respectively. The delta matrix can be written as
D Jo M M¹
Ja M (Ja,a + Jo
Ja Mg. Ja M
M M. (Pr(X, a x)= Pr(X, = X. = =0)).
'When |Σ] 2 3, counter-example exist showing that scoring agents with SCAAA is no longer SD SD-truthful for general information structure.
26

---

Do,o' = Jo M Ma
Ja M (Ja Jo' ,
= Jo Ma. -o' M
= -M² Ma. (Pr(X, = o' = -0) = Xx = =d)).
Next, we reason about the distribution of scores under different strategies. Note that a single draw of the CA score can be -1, 0, 1. Therefore, to prove SD-truthfulness for single draw of the CA score, it is sufficient to show that Pr (T) = 1) 2 (s5 = and Pr (SCA(T) = =-1 s Pr (S) = -1) for any strategy 0. When signals are binary. there are only three types of untruthful strategy: always reporting 0, always reporting 1, and 3) always flipping to I and to 0. Any other strategy is a mixture of truth-te tellinellngg and these strategies. Now, we show that all of these strategies are stochastically dominated by truth-telling by discussing two cases.
When signals are self-predicting, i.e. Pr(X6 = a Xa = o) - Pr(X, = a Xa = =0) > 0, the distribution of S is
Pr (S(A(T)) = 1) = Jo.0 M + J1.1 Mp.
Pr (r) =- = Jo Md + J1, Mc
Because Bob's signal is self seff-predicting. Pr (5) = > Pr (r(SA((T) =1). Let Oy be the strategy where Alice always flips the signals.
Pr (s (0,r =1) Jo,1 Mg J1,0 M Pr Pr = -1),
Pr (S())((0)) (0))= = --) = -ooo M + J1 M = Pr (5.A(T) = =1)-
This means that (g)) is dominated by (T)(T). Let u be the strategy where Alice always reports the same signal.
Pr Pr(s. (n) =1) Pr (S (1) = -1) = Mg Mr.
Therefore,
Pr (S (T) 1) Pr (S = =)) Jo,0 M J1,1 M M M
Ju,o M J1,1 Mg
M (Jo.1 J1,1)
Ju,0 M Jo,1 Mg
MD M (Pr(X. =0 0 X, 0) - -Pr(X = xx = 1)
Similarly, can observe that Pr (T) 1) < Pr (5F -1).
The analysis for the case when signals are not self predictin,,,, i.e. TA (a, o') = if and only if + a'. analogous.
Next, we show that when Σ = 3, counterexamples exist showing that auth-telling does not FOSD every untruthful strategy.
Example F.1. Consider the following joint distribution:
0.02
0.01
0.02
J
0.2
0.4
0.25
0.00
0.05
0.05
The marginal distribution of Alice and Bob are
M (0.05, 0.85, 0.1) and M (0.22,
0.46, 0.32).
27

---

The product of marginal distribution and the corresponding agreement function are
0.009
-0.013
0.004
1 0
0.013
0.009
-0.022
= TA
1 0
00.022
0.004
0.018
1
When Alice reports truthfully, the probability of obtaining score of 1, i.e. obtaining score of the bonus question and obtaining score of 0 on the penalty question, is given by
Pr(S (T) =) = (Jo.0 Jo.2) MP + (J1,0 + J1,1) M (J2,1 + J2.2) M 0.2324.
Alice reports
Alice reports
Alice reports
However, when Alice plays a strategy μa that always reports O, the probability of obtaining a score of 1 is given by
Pr(Sf 1) (M) + MD) My 0.2474 Pr(SPA(T) 1).
Therefore, is not first-order stochastically dominated by т.
F2
The Direct Rounding Reduction
Proof of Proposition 5.2 By definition, the sensitivity of mechanism with score S(e) at effort level
is
(c)
8 (e)
(c)
The direct rounding of (M), denoted as (eM,)), is a Bernoulli variable with success probability E[AM] m.M(e)) S.
Therefore,
Supp
VE g. (c)
SM S.M. Ve)(()
std
(s)(e))
-[B[M (1-
S.M V (m) -;ih)
(S.y
(e)
S.M.
sup
(m)
= (M) v (m)((e) - S.M) (SM
(3)
m(e))
F.3 The Partition Rounding Reduction
Proof of Lemma 5.3 Let Si(T) and Si(0) be the random variable of each individual score under truth-telling and strategy 0, respectively. S,(r) (and (t))) is i..dd. because questions are assumed to be i.i.d. and strategies are task-independent. We want to show
(,(T)
FOSD
S₂(0)
S(T)
FOSD
S(0).
Forward Direction. Suppose (T( FOSD S:) for any 0, By definition, this means for each individual score, can find coupling such that whenever S, st, S,(T) = $ 2 si. Applying this coupling for every individual score and taking the average gives us coupling for S(T) and S(0): whenever S() ΣiE(K 8;, S(T) ΣiEKK s Z ΣiEKK 8; the coupling. Therefore, in this coupling, (r( < t) Pr(S(() < t) for any t E [K Sint, K Samp where S and Soup are the infimun and supremum of each St, respectively. This completes the proof for the sufficiency.
Reverse Direction. We prove the contrapositive of statement: if ST(T) does not first-order stochastic dominates 5,(0), then S(r) does not first-order stochastic dominates S(0). By the failure of FOSD for the individuals, there exists some threshold 4 and (by the i.i.d. assumption) every such that F, (tz) Fo (t1), where F, and F& denote that c. for S,(T) and (,) respectively. Let
28

---

F and F be the c.d.f. of the sum of k i..dd individual scores, i.e. ΣXEM S((T) and ΣiER S: respectively. We want to find k such that FK (tx) F/ (tx). Then, because a linear scaling (by 1/K) of the sum, the inequality transfers directly to the averages.
We prove this via an inductive argument:
Base case (K 1): by assumption, there exists i such that F,((1) > Fo(ti).
Inductive step: suppose that for K 11 there exists threshold fK-1 such that
F (IK-1) Fg (Lx-
Now, consider the K-fold convolution. Note that the convolution of discrete distributions a weighted sum of the individual c.d.f..
(xx) = =
Σ ST(T) =s iE|K-1]
(l(k--s)
and similarly for F (Ix). By the base case and the induction assumption, we can set t.k tK-1 1 + t so that FK(tt) (tx) > FK (tk). This means that there exists threshold
t = t K so that
Pr(((r) <) Pr(S(() s
This completes the proof of the necessity.
E44
EA in the Binary-signal Setting
Proof of Theorem 6.7 Suppose Alice observes mo zeros and my ones on n questions while the enforced empirical distribution is & (no, n1). Alice's strategy and & thus determines the number of i..dd samples from each of the four binomials.
To prove SDT, we have to show that truth-telling results in a score distribution that first-order stochastic dominates the score distribution under any other strategy. Suppose W.L.O.G. that my > no and the mechanism will randomly flip Alice's ' reports on mh no questions from 0 to 1. If Alice reports truthfully, there are rig questions where Alice reports and will be scored if Bob also reports O; there are mi questions where Alice reports and will be scored 1 if Bob also reports 1; and there are me - no questions where Alice observes 0 but her reports are flipped to which means that she will be scored if Bob reports 1 on those questions. Therefore, the final score of Alice can be expressed as
n S(T Bin Poo) + (in(m11P11) Bin - noo Po1
To show that S(7) dominates S(0) for any strategy it is sufficient to focus on deterministic strategies. Suppose Fi is the number of questions that Alice observes but reports j for i,j E {0, 1}. First note that 20,0 Fo, my and 11,0 + 11,1 m.. Then,
argue that it sufficient focus on strategies that satisfy F0.0 + 21.0 = ng and Zo,1 + ø1,1 ni. Otherwise, the mechanism will enforce & on behalf of Alice which is identical for Alice to flip her signals by herself. Fixing any and x the above four constraints suggest that there is only one free variable in x, meaning that there is only one possible way to cheat aatarrinteingggg 20,0 (O....,no).
Now, we show that reporting Fo.0 = no is the best strategy-repeaae distribution dominated by reporting 20,0 no- Also, note that truth-telling is one of the strategies that has 20,0 An. Let F0.0 no - k where & 2 O. Then, the final score of Alice and be expressed
any Fo.0 results in a score
5(A)~ Bin k. Poo) + Bin(m, P11) + Bin -o + k. Po1) Bin P1o). (5)
Compared with the truth-telling score distribution in Equation (2). any untruthful reporting can be viewed as subtracting l samples from Bin(ni, Poo) and draw le more samples from Bin(k, Pio): subtracting & samples from Bin(m1, P11) and draw l more samples from Bin(mo no + H. Po1).
any
29

---

When signals are self pelfipredi,,ing,, Puo P1o and P11 > Pui- We can construct a coupling to show that S()) dominated by S(T). In particular, for the & questions whose scores are sampled from Bin Pio), we couple them with & out of the no samples from S(0)~ Bin - k. poo); for the no k questions whose scores are sampled from Bin k, Pon), we couple them with the
remaining no - k samples from ~ Bin(no k. Poo); we do the same for the other two Binomial distributions. Under this coupling, clear that making 20,0 as large as possible will have the dominating score distribution, which happens while truth-telling.
F.5
EA in the Three-signal Setting
Proof of Proposition C.2
Sufficiency. We prove the sufficiency by discussing two cases. First, suppose W.L.O.G. that 2 no. mi I n1, and ma I R2. Under the minimal enforcement rule, the manipulation matrix corresponds to truth-telling
710
71
m1
112 - 17/
07 (p'p))
0
7711
0
0
m2
When we score an arbitrary report vector Xa. it sufficient to consider its manipulation matrix 0. Therefore, want to show that H will result in score distribution that first-order stochastically dominates the score distribution of any other feasible 9. Note that there are 9 variables in a 3 x matrix and 5 constraints: the sum of variables in n, while only 5 of these 6 constraints are independent. This means that any manipulation matrix be characterized by independent variables denoted as t1.... 2
is m, and the sum of variables in column is
1Ap 11 - l2
n1
m1
+ 1 + 14
13
112
m2 + 12 + 13 444
1
t t4
14
f2
f3
m2 22 - t3
The variables (,, 4 must satisfy the constraints ensuring that every entry in remains non-negative.
The final score of truth-telling is given by the average of n Bernoulli variables where 87 (p").. of these variables are sampled from Bernouli((p..). Similarly, the final score corresponding to the manipulation matrix the average of Bernoulli variables where &9 of them are sampled from Bernoulli(p..).
Our goal is to construct coupling of these Bernoulli variables such that, for any given ox., + and f1,....ta f4. each variable under truth-telling with manipulation matrix 8 (p(p") has a weakly higher probability of success than its coupled counterpart under 1. We denote this coupling by
Zf,, 4 Z to indicate that we pair & Bernoulii variables associated with H (p")-each drawn from Bernoulli(pij)- Our coupling is:
Bernoulli variables associated with e-ch drawn from Bernoullippzy))
76,0
no 1 12,
78.0
Zf,1 1itty 76,1
latty, 76,2 Z
41
Z9,0
ZT, mi
29,1
2J.2 44 Zi,2
12
Z2.
2J,1 13 22
ZT.2
ma to -1
Z
Under this coupling, every diagonal variable ZP, is coupled with 2T,, which is drawn from the same Bernoulli distribution. Furthermore, every non diagonal variable 2", is either coupled with 27, which has a larger success probability because of self- pred-rredition, or coupled with Z which has the same success probability because signals are uniformly celf-predicting.
The proof of the second case is analogous. suppose W.L.O.G. that mp > my >> n1, and m2 < n2z Under the minimal enforcement rule, the manipulation matrix corresponds truth-telling is
740
mo
R30
rr
0
R1
Mi
12
(6)
0
722
30

---

Any feasible manipulation matrix can be written as
710
11
1
mo
Ro
+ 1 22 4
8
t1
n1
t3 t1
m1 - n1 + 13 + t1 t
t
m2
t2
We construct the following coupling. If f 2 t.2 we apply the term red; while if ( < 14, we apply the term in blue.
2
no 10-11-12,
28.0
Zi. 14 Z
2 " Z0.2
Zi.
41 b 14 Z9,2
Z
0 , 79.0
Zi,1
11
11-18-14,
Z9,1
Z , Z
Z
06,0
1
Z2
ZT,1
1/
Z
2
m2 122
Z2
Under the same argument, larger success probability. This completes the proof of sufficiency.
observe that every 2 is coupled with Z3. with weakly
Necessity. We first show that if the mechanism's 's enforcement rule is not minimal, it is not SD-truthful. For a non-minimal enforcement rule, there must exist a report vector Xa and an enforced histogram & such that if Alice reports Xa truthfully, there exists a diagonal value in the corresponding manipulation matrix that can be increased without breaking the constraints. In other words, there exists a strategy 0 whose corresponding manipulation matrix is 8 and column, such that 00 > 07.3 Then, the strategy 0 is not dominated by truth-telling even when signals are uniformly self-predicting. This because by playing 0, Alice can move 0 J samples from Bernoull((p:) or Bernoullipps)) to Bernoulli(p;;) where i, + j. For self-predictinn signals, Páj is the largest column value.
Next, we show that if signals are uniformly self-predicting. the enforced agreement mechanism is not SD 3D-truthful even when the enforcement rule is minimal. We can easily find a counterexample by comparing Equation 6 with Equation 7 Suppose W.L.O.G. that 0h < oī.2. then Alice can set t t2 f3 0 and t4 max(11, mo no) in which case she can move 44 samples from Bernoulli (P..2) 2) to (ernoulli(pI.)) resulting a score distribution that dominates truth-telling. This completes the proof of necessity.
F.6 The Optimal Enforcement
Proof of Lemma C.5 Suppose Alice observes 0 on mg out of the n questions and observes 1 on the remaining mo questions. There cases.
First, when my S no, the final score of Alice is the average of the following three type of questions:
mg questions where Alice observes and receives a score of Bob also reports 0.
π2 no questions where Alice observes and receives a score of Bob also reports 1.
110 mig questions where Alice observes but receives a score of if Bob reports 0.
When Alice exerts full effort (e = 1), Bob's reports (which match his signals) follow the conditional
probability distribution Pij Pr(Xx, j X. =i). In contrast, when Alice exerts effort (e 0), her signals are uninformative about Bob's signals, and thus her belief about Bob's reports follows the marginal distribution M = Pr(X, i). Therefore, conditioned on Alice observing 0 in mo questions, the score defined by EA follows the sum of three binomials:
n SEA e 1 ma < n²) Bin(mo, (oo) Bin(n no. (h.P111)> + Bin(ng mo. P1o), n S.SAA 0 mg < nn) ~ Bin(mo. Mt) + Bin(n - no. M + Bin(no mo. M1)).
Note that for any question, the probability of Alice observing 0 while exerting effort is the marginal distribution Pr(X. 0), which is identical to the probability of observing 0 while exerting effort. This implies that under our definition of effort, the probability of Alice observing 0 on mp questions does not depend on the effort. Let Pa Ejejn (1 Xa,;) ) be the number of questions where Alice observes O. The probability that Alice observes 0 on mno questions is
Pr (po = mo) =
(Mg) (1 - -g)r~mo
mm
31

---

Consequently, when mo I Alice's score, conditioned on observing 0 in mo S no questions
(which occurs with probability Pr (Po mo)). follows the distribution:
n (no. mo S no) ~Bin (mo, e Poo + (1 - e) MM) + Bin (n nu. e P11 + (1 -1-08 e) Mf}
+ Bin (no ma, Pio + (1 e)
Mc)
In the second case, where mg > rln, the final score of Alice is the average of the following three type of questions:
no questions where Alice observes and receives a score of Bob also reports O.
7t me questions where Alice observes and receives a score of Bob also reports 1.
m0 no questions where Alice observes but receives a score of if Bob reports 1.
By the analogous arguments, we know that Alice's score, conditioned on observing in mg > no
questions, follows the distribution:
SEA(no, e mo > no) ~Bn (no, e Puo + (1 - c) Mg) + Bin (n mu, e P11 + (1 - e) Mt) Bin (mo no, Poi + (1 -e) e) Mf).
Putting everything together,
S SFA(no, e) ~ Pr (po = mo)-s ( mo S no)+
Pr (po = mo). (no, e mo > no)
mp=0
mo=R0-
(8)
Now, we show that the standard deviation of S (no, e) is independent of no. For simplicity, let
Miy = Ptj + -1- Mý. Note that 1200 + 7/1 = e (pro + Pa)) + (1 e) (M) + Mf) = 1.
Furthermore, the variance of a binomial with parameters n. is np(1 - p). When mo I no, the variance of the final score
var (n SEA (no. e my I no)) = my Too (1 1700) + (n - no) mh (1 m/1) + (no - ma) the (1 - m72))
= mg Tooo (1 1100) + (n (1a-ma) mo) 7/1 (1 - -.)).
Similarly, when mo > 110 var (n- SEA ( e mg > no)) = no Too (1 700) + (n mo) Th1 (1 mm1 + (mo no) Mon (1 - M01)
= mg Too (1 (Joo) + (n - mo) 7h1 (1 711)
Therefore, conditioned on observing 0
me questions, the standard deviation mg TJeo (1 - (o0) + (n mo) 7/11 (1- m1) is independent of
std (SEA (no. e ma)) no. Consequently, the standard deviation of the final score, averaging over mo. is also independent of
ng.
Proof of Proposition C.6 By Lemma C.5 the standard deviation of the EA mechanism is indepen- dent of the enforcement Φ. Therefore, the enforcement that maximizes the sensitivity is the one that maximizes the derivative of the expected score w.r.t. effort e. By Equation (8), the score given by EA can be expressed as the average of many binomial variables. Note that the expectation of binomial variable with parameter (n,, p) is n p. We thus have
IE [[EEA (no.e mo I no)] = mo7o0 + (n - no) 711 + (no mo) T110
IE [SSAA mo > no)) 1o07000 + (n mo) 711 + (mo no) 7701
where Mij e Pig (1 e) MD. The derivative of Mıj w.r.t. is thus n/ Pij M3.
We aim to find the no that maximizes
JE (EEA(no. e)]
Pr (pu = mo) (mo Tho + (n - -no) v/n + (no - mo) %/0)
de
m0=0
Σ
(pu = mo) (nu noo + (n - mp) 7/1 + (mo - no) 762)
my m1=
32

---

Let no increase by 1:
dE S RA (no + 1,,e)
2o+1
Pr (po = mo) (mo too + (n no 1001 1) 1/1 + (no 11 - -mo) 1/10)
de
mg=0
Pr ma) ((no + 1) 1/o0 + (n mo) 1/1 + (mo 1o 1) vo2))
Therefore, the marginal return of increasing no is given by
OE
[SEA (mo + 1,,]] OE [nn, c)
dVSBA
de
de
no Σ m==0
Pr (po mo) (1/o 1/i)
Σ
Pr mo) (160 1%61)
=o=ng+1
Note that
To 1/11 = P1o MD P11 M
2(111 - M³)
(pu1 = 1 - Pm1 and MD 1 MM.))
2(P11 (Mğ Pol + Mí Pı))
= 2((11 (1 - (f) - -po Mi)
= 2 MD (P11 Po1)
<0 0
(By self-prediction.
Similarly, we can show that V/10 1/1 0.
Therefore, when no = 0. dV 5FA (0) > O, and when no = n, dVVEA(()) < O. Furthermore, AV (no) decreases in no- The dV > Let F(k) E (po = mo).
no is thus the largest integer such that
dVSEA(no)
F(no) (vio 1/1) (1 F(nu)) (N6o vot 0
Tho 1/1
F(no) < 16o 7o1 1/1 7/10''
33


Reviews:
[{"review_id": "y7XGcXk1j1", "reviewer": "Reviewer_AWMx", "summary": "The authors study mechanism design for peer prediction. Whereas theoretically scoring rules that guarantee truthfulness in expectation is sufficient, in practice non-linear payment rules are preferred for incentivizing truthful behavior. To address this discrepancy, the authors introduce a new stronger notion of truthfulness namely stochastically dominant (SD) truthfulness where the truth-telling reward distribution must first-order dominate the reward distributions of all other strategies.\n\nThe authors observe that SD-truthfulness does not hold for many mechanisms but can be trivially be attained by rounding all rewards to two extreme values so that the expectation is preserved. This directly yields SD-truthful mechanisms but introduces significantly higher variance in rewards. To address this, they seek to optimize an additional objective, namely sensitivity. They propose an optimized SD-truthful mechanism called Enforced Agreement (EA) that reduces sensitivity and empirically show that its levels of sensitivity closely follow that of other peer-prediction mechanisms while also being SD-truthful.", "questions": "- Is it possible to theoretically establish optimal mechanisms that satisfy SD-truthfulness for any domain. Is EA optimal in any regard?\n- Is there a characterization for SD-truthful mechanisms?", "limitations": "The authors clearly state the limitations of their proposed mechanism.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe paper clearly motivates why expected utility truthfulness is insufficient in practice. It introduces SD-truthfulness as a more robust guarantee for arbitrary monotonic preferences. It proves that classical mechanisms (Output Agreement, PTS, Correlated Agreement) do not meet this stronger criterion and designs EA, a novel and creative mechanism to achieve SD-truthfulness in binary domains.\n\nWeaknesses\nAn important weakness with the proposed mechanism is the lack of theoretical exploration. The paper mainly proposes the EA mechanism as a novel alternative but does not establish its theoretical performance or optimality in some domain. There could be other mechanisms that are better and even not-restricted to give binary outputs.\nMoreover, while the proposed mechanism aims to be more practically relevant, its limitation to binary-signals feels substantial in practice.\n\nFinally, the main body of the paper seems very imbalanced. It spends many pages describing the limitations of other mechanisms and spends less than a page to the description of the proposed alternative which very dense, hard to parse and only focused on the SD-truthfulness of EA without motivation.", "was_revised": true, "final_justification": "Based on the rebuttal, the authors give more motivation for the setting considered that they plan to integrate in the paper.", "rebuttal": "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.\n\n### **The Space and Optimization of SD-truthful Mechanisms**\n\nYou 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.\n* 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.\n* 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.\n\nTo 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).\n\n### **Binary setting**\n\nWhile the Enforced Agreement (EA) mechanism is SD-truthful only in the binary-signal setting, we believe it remains valuable for two main reasons.\n* 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)].\n* 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.\n\nWe 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.\n\n### **Addressing the Imbalanced Main Body**\n\nWe 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.\n\nThe 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."}, {"review_id": "JLkosUETkC", "reviewer": "Reviewer_X4e2", "summary": "The paper considers peer prediction mechanisms for eliciting truthful behavior.\n\nIt proposes a new type of truthfulness guarantee, stochastic dominance-truthful (SD-truthful), in which the probability that the mechanism assigns a score above some threshold $t$ to the truth-telling strategy is greater than the probability that it assigns a score above that threshold for any other strategy, for any threshold $t \\in \\mathbb{R}$.\n\nIt also discusses mechanism sensitivity, a measure of the extent to which the mechanism gives higher scores to more informative reports. The goal of the paper is \"to design SD-truthful mechanisms that also achieve high sensitivity.\"\n\nThe paper makes the following claims:\n\n1. No existing peer prediction mechanism is naturally SD-truthful under general information structures.\n2. Achieving SD-truthfulness is easy in principle but challenging in practice.\n3. The proposed _enforcement agreement_ mechanism is more sensitive than the _direct rounding_ or _partition rounding_ reductions, and requires weaker assumptions (signals are self-predicting) for SD-truthfulness than _output agreement_ (signals are self-dominating).", "questions": "1. In Figure 1, the paper provides a comparison of the sensitivity of different mechanisms. Is there a way to also evaluate and visualize truthfulness?\n\n2. The legend for Figure 1 (a) and (b) includes CA-partition-round, but I don't see the red line. Is it missing from the plots?", "limitations": "See weaknesses above.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n- The new SD-truthfulness property is presented clearly.\n- The paper does a good job of motivating both SD-truthfulness and sensitivity.\n- The paper reviews several prior mechanisms and well situates the new SD-truthfulness property within that context.\n    - It shows that SD-truthfulness is only achieved (by output agreement) under the strong assumption of self-dominating signals. \n    - It also shows that peer truth serum (PTS) is truthful, but not SD-truthful, under the weaker assumption of self-predicting signals. The justification feels right, although I did not check the details of the proof carefully.\n- The new mechanism, enforced agreement (EA) is clearly presented. It is also SD-truthful for binary, self-predicting signals (which is a weaker assumption than OA requires), while being more sensitive under the partition rounding reduction than correlated agreement (CA), matching agreement (MA), and (usually) PTS.\n\nOverall, this feels like a valuable contribution that future work can build on, both for the SD-truthfulness property and for the novel EA mechanism.\n\n### Weaknesses\n\nThe proposed mechanism, enforced agreement (EA), is not generally SD-truthful in the non-binary setting. The paper does a good job of pointing out this limitation in the main text, and discusses it in depth in Appendix C. It also points out that EA is still truthful as long as the information structure is known. I am not an expert, so I am not sure what this information structure assumption means or whether it is reasonable.\n\nThe explanation of \"effort\" in the definition of sensitivity was hard for me to follow. I get it at an intuitive level, but the clarity of this section could definitely be improved.", "was_revised": true, "final_justification": "My rating is unchanged. I still think the paper should be accepted, but I also feel it could be written better, to cater to a broader audience. For example, the definition of \"effort\" still does not make sense to me.", "rebuttal": "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.\n\n### **Binary setting**\n\nWhile the Enforced Agreement (EA) mechanism is SD-truthful only in the binary-signal setting, we believe it remains valuable for two main reasons.\n* 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)].\n* 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.\n\nWe 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.\n\n### **Information structure assumption**\n\nAt 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.\n\n### **Effort model**\nWe 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.\n\n\n### **Visualize truthfulness**\nTruthfulness 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. \n\nThe 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. \n\n### **CA-partition-round**\n\nAs 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."}, {"review_id": "uiFyJr1JSW", "reviewer": "Reviewer_WpLs", "summary": "The paper introduces a new notion of truthfulness for peer prediction mechanisms called stochastically dominant truthfulness (SD-truthfulness). They then provide several contributions connected to this definition:\n(1) They propose a modification of the (known) rounding/normalization strategy that converts an existing peer-prediction mechanism into one that is SD-truthful, such that the resulting modified peer prediction mechanism additionally has higher sensitivity compared to vanilla rounding.\n(2) They then propose a novel peer prediction mechanism, called Enforced Agreement (EA), that instead of performing using a rounding strategy proceeds via a different method on top of Output Agreement --- this method provably achieves SD-truthfulness in the binary setting (though not generally/necessarily SD-truthful beyond that), and establish several further properties of EA.\n(3) They perform experiments establishing the favorable performance of the SD-truthful methods they have developed, as compared to prior methods with that property --- establishing that SD-truthfulness via their constructions (EA and the \"bucketed rounding\") leads to better sensitivity curves (i.e. to better sensitivity across various levels of effort).", "questions": "See more details in the Weaknesses section, but the following are distilled important questions to resolve:\n\n(1) Please concretely discuss why/how SD-truthfulness would get violated (or not) in complex mechanisms (such as mutual information-based).\n\n(2) Please concretely discuss in substantially more detail why sensitivity is an important metric (currently it's a few lines in the middle of the paper, which is not enough for a key notion), and why one shouldn't worry about defining sensitivity with respect to the utility functions in this case.\n\n(3) Please make general clarity-inducing improvements targeting less experienced readers in terms of extra terminology, context from the elicitation literature, etc.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "As the Strengths of this paper, the following stand out:\n\n++ The idea of defining SD-truthfulness is quite simple and neat: due to the canonical link between stochastic dominance and monotonic transformations of random variables, it implies strictly stronger truthfulness guarantees than the linear-utility ones explored before, and thus naturally cover a variety of natural settings where handling a generic monotonic transform of the scores is necessary (such as the given example of students targeting grades A, B, C, and many other conceivable structured settings).\n\n++ The constructions for both the new rounding scheme and for EA are pleasantly simple --- almost to the point of being elegant (being based in particular on clever constructions that permit the use of stochastic coupling to enable meaningful stochastic dominance comparisons), and in that sense are in my opinion a perfect starting point for further, more sophisticated studies/follow-ups that would further explore SD-truthfulness.\n\n++ The empirics do a fairly good job exposing the benefits afforded by the proposed methods, from directly providing sensitivity plots to (in the Appendix) exploring positive consequences on budgeting.\n\nAs far as the weaknesses:\n\n-- Why is the sensitivity notion, as defined, the important/the right one to consider? First off, budgeting and fairness that are mentioned existing applications, are a fair point, but they are not elaborated on sufficiently in the main part for a first-time reader's benefit (nor, unfortunately, in the appendix modulo the extra experiments). More fundamentally, I like the sensitivity definition as-is in the standard context of linear utilities (that are modulo offset proportional to scores) --- but since you are considering general monotonic utilities here as your main contribution, a sensitivity notion that would strike me as far more natural would measure e.g. the worst-case (or average case, etc) sensitivity with respect to the utility functions in a certain class of monotonic utilities. In other words, why should I care more about how sensitive the scores themselves are, rather than the utilities generated from those scores? The moment things become nonlinear these are two different notions.\n\n-- One important technical point got swiped under the rug (despite being mentioned twice: in the intro and in the appendix): For a multitude of mechanisms that are more \"complex\" than the ones discussed in this manuscript, in particular ones based on mutual information etc., it is claimed without further elaboration that due to this complexity, such mechanisms would be \"unlikely\" to be SD-truthful due to the strategic manipulations that are permitted through these complexities. For the readers' benefit, I believe it would be quite critical to get more concrete on this point. If you believe that a general and simple to state class of manipulations would prevent SD-truthfulness from holding, I'd like to request that you please give such a construction in your response/in the paper. On my end, while I completely agree that exact SD-truthfulness is elusive, in my opinion just citing the complexity of scoring rules as a major reason sounds a bit peculiar/non-fundamental. Moreover, when it comes to looking at approximate rather than exact SD-truthfulness, the logic of saying \"the scoring is way too complex, clearly can be exploited\" would seem to not be robust to that (as such complexity could perfectly well hide inside the approximation parameter in that case, and possibly in a pretty inconspicuous way).\n\n-- The paper may not be 100% clearly written from the perspective of a general ML/GT reader at times, which is because the paper was written with a specific audience in mind (more so for a generic EC attendee than a generic NeurIPS attendee); in particular, some notions --- like Bayes Nash equilibrium --- get thrown around quite causally throughout the text, and while it's helpful for the seasoned expert reader, I would have like to see further effort on the accessibility front (i.e. either explain such terms at least informally at least in footnotes, or try to avoid them unless necessary). Moreover, even from the experienced reader's perspective there is some lack of clarity in places, see the above Weaknesses.", "was_revised": true, "final_justification": "My conceptual and concrete questions about the setup (the significance of the metric, truthfulness issues in related mechanisms, etc.) were sufficiently clarified and addressed in the response by the authors. Furthermore, I have also studied the other reviews and the authors' rebuttals to those, and believe that the authors have also clarified other reviewers' points to a sufficient extent. The core contributions of the paper are simple and insightful --- however the issue of readability and supporting discussions in the paper will be important but not fully trivial to fix, which is why I kept my (positive) score rather than increase it.", "rebuttal": "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.\n\n### **SD-truthfulness for Mutual Information Mechanisms**\n\nThank 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.\n\n* 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.\n\n* 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.\n\nIn 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.\n\n### **Sensitivity Definition and Motivation**\n\nWe 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.\n* 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.\n\n* 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.\n \n* 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.\n\n### **Clarity and Accessibility Improvements**\n\nWe 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.\n\nWe 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."}, {"review_id": "6r5ttAlgfS", "reviewer": "Reviewer_BNRF", "summary": "This paper proposes Enforcement Agreement, a new mechanism for the peer prediction problem that satisfies the novel SD-truthfulness criteria. Whereas other mechanisms rely on linear utility functions in order to satisfy Truthfulness, SD-truthful mecahnisms incentivize truth-telling for general increasing utility functions. It is shown that partition rounding can translate any truthful mechanism with bounded scores into a SD-truthful one (Prop 4.4). Furthermore, EA is shown to be SD-truthful for the binary setting when signals are self-predicting (Thm 5.1), and demonstrated to have high sensitivity. Empirical results compare EA to other mechanisms, including OA, PTS, CA, and MA.", "questions": "- The K partitions seems to be analogous to Bootstrapping. Do you need the partition assumption in order to get your results -- instead of, i.i.d sampling with replacement?\n- Is line 122-124 the only explanation for why your mechanism can handle monotonic but non-linear utility functions? Also, it's not clear what a utility function is, relative to what is discussed in Section 2.\n- Why are single task mechanisms different than multi-task mechanisms? Line 443 in Appendix A refers to Prelec (2004) but doesn't suggest why ideas from that literature doesn't seem to translate to the problem addressed in this paper.", "limitations": "The main result (Thm 5.1) is limited to binary and self-predicating signals. The authors demonstrate that SD-truthfulness does not hold for 3+ elements. I would really like a better understanding in this paper why self-predicting (Def 3.3) is a useful or important concept with respect to either PTS (in Sec 3.2) or in the proof of Thm 5.1. This is introduced as a sufficient condition, but no context is provided for why this condition is important, or in what types of real-world decision problems this condition holds.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper does a good job at introducing the peer prediction problem, explaining how the new proposed concepts (SD-truthfulness, partial rounding, and EA) compare to prior literature (OA, PTS, and CA), and demonstrating why EA satisfies the SD-truthful criteria. The authors do well explaining how and why EA (which incorporates OA with partial rounding) achieves a much better sensitivity ratio than OA with direct rounding. An empirical study compares the results. Overall I found the paper clear and convincing. While I did not check the proofs in the appendix thoroughly, they appear generally correct.\n\nStill, peer prediction is a complicated concept and the paper could use several edits to clean up the presentation. Here are some major comments:\n- Can you explain the assumption about Bob's reports being truthful on Line 109? You introduce this relationship with Bayes Nash Equilibrium, which makes sense, but don't refer back to it throughout the paper. It's not clear why this assumption, or being in equilibrium, makes sense across these mechanisms.\n- The paper could really make use of a running example to demonstrate these concepts. I think your discussion of Direct and Parititon rounding is clear. But the discussion breaks down when you introduce $\\Phi$ on line 278. It seems like the discussion in Section 5 is significiantly detached from the model introduced in Section 2, and it's immediately clear to the reader how to build this relationship. The paper loses its relationship to the applications in lines 37-40 very quickly, so I struggle to understand how it could be directly applied.\n- Lines 139-143: You introduce two new concepts here -- budget efficiency and measurement integrity. BE is only used in Appendix E.3; MI is not used at all in the paper. I would recommend reframing this paragraph to suggest that these are \"useful to know\" concepts related to sensitivity, as opposed to highlighting them as important for the reader to remember later on.\n- Although you demonstrate EA has better sensitivity, due to partial rounding, you don't explain this in context. It's not clear how good EA is on this measure dimension. \n- The discussion on Lines 304-308 could use significant elaboration in the main text, since they appear to be significant parts of your paper's contribution.\n- It's not clear: (1) what $\\Phi$ is relative to the model introduced in Section 2, (2) what \"information structure\" means, and (3) how the joint distribution $Pr(X_a, X_b)$ affects your results -- or if this is just a modeling necessity.\n\n\nOthers:\n- Fix \\citet -> \\citep citation format on lines 26, 38, 54; also in Appendix A\n- Line 29: fix to \"subjective assessment tasks.\" Otherwise subjectivity is in contrast with \"ground truth\"\n- Not sure if colored variables in Line 298-299 are acceptable for NeurIPS. Please double check.\n- Lines 62-64 high-level description of \"sensitivity\" could be improved.\n- Line 78 -- please explain \"enforced count\" for readers not familiar with the peer prediction literature\n- Line 88 -- why is assessing budget efficiency a \"robustness check\"?\n- Line 130: is $X_a$ the random variable over $\\Sigma$? So that if $e=1$ then this reduces to the model discussed in Sec 2.1?\n- Citation for Prop 3.2? Is there a corresponding necessary condition for OA to be truthful?\n- Line 198 - clarify \"depends on implementation\": either say \"not necessarily\" or also mention which implementation would be SD-truthful. Does this contradict Table 1? Are lines 210-211 important enough to be bolded?\n- Line 227 - how is sensitivity related to practicality? Since this concept is important throughout the paper, it may be worthwhile on elaborating some of the intuitive findings from [Zhang and Schoenebeck, 2023a] on lines 136-138 (not just the technical relationships).\n- Line 334: please include a one sentence description of EA-optimal, and then point to the appendix for the full description\n- Inconsistent reference style in bibliography", "was_revised": true, "final_justification": "The authors sufficiently addressed my concerns in their rebuttal. I will therefore keep my score.", "rebuttal": "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. \n\n### **Bayesian Nash Equilibrium**\nThe 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.\n\n### **EA for the motivating example**\n\nThe 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. \n\nTo 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.\n\nSection 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.\n\n### **Budget efficiency and measurement integrity**\n\nThese two concepts are indeed only used to motivate why sensitivity is a good metric to look at. We will clarify this.\n\n### **EA under partition rounding**\nPlease 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.\n\n### **Other questions**\n* **$\\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$.\n* **Information structure** refers to the joint distribution of agents’ signals. We will try to use the latter more in the paper.\n* 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.\n* **Colored variables**: We do not see any regulations about colored text on NeurIPS website. We will remove color edits for the potential camera-ready.\n* Line 78: See our response to “Motivating example”.\n* 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.\n* 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.\n* 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.\n* 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.\n* 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.\n  * 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.\n* 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.\n\n### **Partition round with replacement**\n\nAs 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.\n\n### **Utility function**\nLines 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. \n\n### **Single-task mechanisms**\nSingle-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.\n\n### **Self-prediction**\nIntuitively, 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. \n\nMore 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.\n\nWe 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.\n\nIn 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."}]

Author rebuttal:

Meta-review: Traditional peer prediction mechanisms incentivize truthfulness with respect to expected rewards.  In practice, agents may be risk averse or otherwise care about things in a non-linear way.  This paper introduces the idea of ensuring truthfulness stochastically dominates other strategies, which inherently incentivizes a range of utility functions.  An existing rounding approach can achieve this, but makes the scores less sensitive.  A more sophisticated rounding scheme and a new mechanism achieve better sensitivity.

All reviewers are positive about the paper, appreciating the novel, well-motivated definitions, the elegant mechanism designs, and the empirical evaluation.  The main remaining concerns that some reviewers had after the discussion are concerns that the current accessibility of the exposition for readers outside the EC community could be improved (some specific improvements in this regard have been identified and the authors have committed to making them) and that the SD-truthfulness, although not the standard truthfulness, are limited to the binary setting (this limitation receives significant discussion in the paper).
Decision: Accept (poster)