Research map / Learning theory and algorithms / Submodular and game algorithms
Stochastically Dominant Peer Prediction
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces SD-truthfulness for peer prediction (score distribution under truth-telling first-order stochastically dominates any deviation), shows rounding reductions enforce it, and proposes the enforced agreement mechanism, which is SD-truthful for binary self-predicting signals and has highest sensitivity among known SD-truthful mechanisms.
Problem
Classic peer prediction mechanisms guarantee truthfulness only for expected scores, which assumes agents have linear utility in score; non-linear payments and non-linear agent utilities break truthfulness, and existing mechanisms are not stochastically dominant truthful without strong assumptions.
Approach
Define SD-truthfulness (score distribution under truth-telling first-order stochastically dominates any deviation), so truth-telling is optimal for any increasing utility. Achieve it via direct and partition rounding of truthful mechanisms into binary lotteries, and propose enforced agreement, which forces a pre-set marginal distribution of reports before applying output agreement to retain high s
Key results
- EA is SD-truthful for binary self-predicting signals for any enforcement, and in the binary setting it achieves the highest sensitivity among known SD-truthful mechanisms except when the prior is nearly uniform.
- Partition rounding multiplies sensitivity by sqrt(K) relative to direct rounding, while direct rounding loses about sqrt(n) in sensitivity for OA.
- Even EA-uniform (prior-free) outperforms PTS-partition-round in most settings; in budget experiments, SD-truthful mechanisms with threshold payments beat truthful mechanisms with linear payments at higher target effort.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace direct rounding with partition rounding (ablation) | truthful bounded-score mechanisms · multi-task peer prediction | sensitivity: exactly $\sqrt{K}$ times | Helped |
| apply direct rounding instead of retaining the original averaged scores (ablation) | Output Agreement (OA) · multi-task peer prediction | sensitivity: $\sqrt{n}$ | Hurt |
| enforce the signal prior (ablation) | Enforced Agreement (EA) · J1, binary signals | sensitivity | Helped |
| use uniform enforcement rather than requiring prior knowledge (ablation) | Enforced Agreement (EA) · J1, binary signals | sensitivity | Helped |
| use EA-uniform instead of PTS-partition-round | SD-truthful mechanisms · J1, binary signals with a biased prior | sensitivity | Helped |
| use PTS-partition-round when the signal prior is nearly uniform | Peer Truth Serum (PTS) · binary signals with prior near 0.5 | sensitivity | Helped |
| use EA rather than other SD-truthful mechanisms | SD-truthful mechanisms · binary signals, except when the signal prior is nearly uniform | sensitivity | Helped |
| use CA-partition-round or MA-partition-round rather than higher-sensitivity alternatives | Correlated Agreement (CA) and Matching Agreement (MA) · general signal settings | sensitivity | Hurt |
| pair an SD-truthful mechanism with threshold payments instead of using a truthful mechanism with linear payments | peer prediction mechanisms · J1 effort elicitation | budgetary efficiency | Helped |
| use EA with signal-prior enforcement | SD-truthful mechanisms with threshold payments · J1 effort elicitation | total payment | Helped |
| use EA with a non-binary signal space | Enforced Agreement (EA) · non-binary signals | stochastic-dominance truthfulness | Hurt |
Surprising findings
- EA is not SD-truthful for signal spaces larger than two, even when signals are self-predicting; SD-truthfulness requires uniformly self-predicting signals for three signals.
- CA with the original implementation is not SD-truthful, even though it is truthful when the joint distribution is known.
Limitations
- EA is only SD-truthful for binary signals; for larger signal spaces it is only truthful when the information structure is known.
- Partition rounding and direct rounding substantially reduce sensitivity compared with the original mechanisms.
- SD-truthfulness does not guarantee truthfulness under tournament (rank-order) rewards.
Experimental setup
Datasets: compound appropriateness crowdsourced labels (Dawid-Skene estimated information structure, J1) tweet sentiment annotations with 300 tweets, 4 signals (J2)
Benchmarks: sensitivity under varying prior and number of tasks on J1 and J2 budgetary efficiency under threshold and linear payments
Metrics: sensitivity total payment (budgetary efficiency)
Baselines: Output Agreement Peer Truth Serum Correlated Agreement Matching Agreement linear payment truthful mechanisms
Builds on: output agreement peer truth serum correlated agreement matching agreement
Closest papers by meaning
- Carrot and Stick: Eliciting Comparison Data and Beyond (NeurIPS 2024 · similarity 0.89)
- A Cramér–von Mises Approach to Incentivizing Truthful Data Sharing (NeurIPS 2025 · similarity 0.86)
- Truthful High Dimensional Sparse Linear Regression (NeurIPS 2024 · similarity 0.86)
- Incentivizing Truthful Language Models via Peer Elicitation Games (NeurIPS 2025 · similarity 0.85)
- Plant-and-Steal: Truthful Fair Allocations via Predictions (NeurIPS 2024 · similarity 0.85)
- Peer Neighborhood Mechanisms: A Framework for Mechanism Generalization (AAAI 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.