Source-linked AI summary
Informed Truthfulness in Multi-Task Peer Prediction
Victor Shnayder, Arpit Agarwal, Rafael Frongillo, David C. Parkes
TL;DR
Peer prediction must elicit informative, truthful reports without objective ground truth, while avoiding equilibria that reward uninformed behavior. The paper analyzes multi-task mechanisms for non-binary signals, introduces Correlated Agreement, and develops a detail-free variant. It establishes informed truthfulness in general multi-signal domains, characterizes when strong truthfulness holds, and retains epsilon-informed truthfulness when statistics are learned from many tasks.
Problem
Peer prediction seeks truthful information without external verification, but uninformative equilibria can pay as well as or better than truthful reporting.
Method
The paper extends the Dasgupta-Ghosh multi-task mechanism to multi-signal settings, introduces Correlated Agreement, and estimates correlation statistics in a detail-free variant.
Results
Correlated Agreement is informed truthful in general multi-signal domains, while MSDG is strongly truthful under categorical signal distributions; the paper also establishes maximal strong truthfulness within a broad mechanism class.
Takeaways & Limitations
The mechanisms make truthful reporting strictly preferable to uninformed strategies, including settings with non-binary signals and few agents and tasks.
Takeaways & Limitations
Correlated Agreement is not always strictly proper, and MSDG’s categorical condition is unlikely to hold for naturally ordered or closely related signals.
Abstract
from arXiv · showhide
The problem of peer prediction is to elicit information from agents in settings without any objective ground truth against which to score reports. Peer prediction mechanisms seek to exploit correlations between signals to align incentives with truthful reports. A long-standing concern has been the possibility of uninformative equilibria. For binary signals, a multi-task mechanism [Dasgupta-Ghosh '13] achieves strong truthfulness, so that the truthful equilibrium strictly maximizes payoff. We characterize conditions on the signal distribution for which this mechanism remains strongly-truthful with non-binary signals, also providing a greatly simplified proof. We introduce the Correlated Agreement (CA) mechanism, which handles multiple signals and provides informed truthfulness: no strategy profile provides more payoff in equilibrium than truthful reporting, and the truthful equilibrium is strictly better than any uninformed strategy (where an agent avoids the effort of obtaining a signal). The CA mechanism is maximally strongly truthful, in that no mechanism in a broad class of mechanisms is strongly truthful on a larger family of signal distributions. We also give a detail-free version of the mechanism that removes any knowledge requirements on the part of the designer, using reports on many tasks to learn statistics while retaining epsilon-informed truthfulness.
1. INTRODUCTION
Peer prediction elicits information without external verification by rewarding reports that correlate with peers’ reports, but uninformative equilibria can undermine truthful behavior. The paper extends multi-task peer prediction to non-binary signals and introduces informed-truthful mechanisms that reward effort and truthful reporting.
- Motivation: Peer prediction uses correlations among participant reports to elicit information when no external ground truth is available.Applications include surveys, restaurant feedback, emotional responses to videos, and MOOC peer assessment.
- Motivation: Uninformative equilibria can payoff-dominate truthful behavior, causing agents to misreport strategically rather than reveal useful information.An uninformative equilibrium uses reports independent of received signals.
- Prior work: The binary-signal multi-task mechanism of Dasgupta and Ghosh is strongly truthful, so truthful reporting yields higher expected payment than any other strategy except signal permutations.The mechanism relies on multiple independent tasks with overlap between assignments.
- Contribution: Informed truthfulness requires truthful reporting to weakly maximize payoff and to strictly outperform every uninformed, signal-independent strategy.This property targets both incentives to acquire informative signals and incentives not to misreport them.
- Contribution: The paper studies MSDG for multi-signal domains, generalizes it to the Correlated Agreement mechanism, and develops a detail-free version that learns correlation statistics from reports.The detail-free mechanism is informed truthful in the large-task limit and has a convergence-rate analysis for epsilon-informed truthfulness with high probability.
- Contribution: The mechanisms provide strong or informed truthfulness for non-binary signals without requiring a large population, with robust incentives holding for as few as two agents and three tasks.The analysis also simplifies techniques used in the earlier binary-signal work.
2. MODEL
The model specifies multi-task peer prediction with finite, correlated signals, effort-dependent information, and strategies mapping observed signals to reports. It formalizes informed versus uninformed behavior and uses the Delta matrix to encode signal correlations and analyze linear mechanisms.
- Agents receive signals only after investing effort, while no effort yields no informed signal.
- The signal model assumes ex ante identical tasks, exchangeability, stochastic relevance, and common knowledge of the joint distribution.
- The Delta matrix records correlation between signal values through joint probabilities minus products of marginal probabilities.
- Strategies may be mixed mappings from observed signals to reports, with permutation strategies relabeling signals and uninformed strategies using the same report distribution for every signal.
- Tasks are divided into shared bonus tasks and separate penalty tasks, with task identities and designations hidden to preserve anonymity and prevent coordination.
- For linear mechanisms, averaging a strategy vector preserves expected score, allowing analysis to focus on a single per-task strategy and deterministic optimal strategies.
3. MULTI-TASK PEER-PREDICTION MECHANISMS
The paper defines multi-task mechanisms using score matrices and bonus-task payments adjusted by reports on penalty tasks. Linearity supports a simplified deterministic analysis of truthful, informed, and equilibrium strategies.
- The mechanism class extends Dasgupta-Ghosh by mapping report pairs to a common score through a score matrix.
- Each agent must receive at least two tasks, agents must overlap on one task, and at least three tasks are used overall.
- Bonus-task payment equals the score for reports on that task minus a score computed from reports on two randomly selected penalty tasks.
- Expected bonus-task payment is tr(F^T Delta G S^T), combining signal correlations with strategy-induced expected scores.
- A deterministic optimal joint strategy exists for any world model and score matrix.
- Consequently, deterministic strategies suffice when checking strong truthfulness, informed truthfulness, equilibria, and truthful deviations.
4. THE DASGUPTA-GHOSH MECHANISM
The MSDG mechanism rewards matching reports and is strongly truthful exactly under the categorical condition for symmetric Delta matrices. Its limitation is practical: ordinal or otherwise non-categorical domains can make signal merging profitable.
- MSDG uses an identity score matrix that pays 1 for agreement and 0 for disagreement.
- If the world is categorical, MSDG is strongly truthful and strictly proper; if symmetric Delta is non-categorical, it is not strongly truthful.
- Under categorical models, truthful reporting achieves the maximum payment because Delta has positive diagonal and negative off-diagonal entries.
- Positive off-diagonal correlations let agents increase payment by merging two signals into one report.
- For binary signals, positive diagonal correlations imply categorical models, yielding a simpler proof of the binary Dasgupta-Ghosh result.
- 4.1. Discussion: Applicability of the MSDG mechanism: MOOC evidence shows categorical structure in about one third of three-signal models and none of the larger models, which instead display ordinal correlations.
5. HANDLING THE GENERAL CASE
The Correlated Agreement mechanism uses the sign structure of signal correlations to achieve informed truthfulness across general domains, while strong truthfulness depends on the absence of clustered signals and paired permutations. It is maximally strong truthful within its correlation-based class, and a detail-free implementation preserves approximate informed truthfulness.
- The CA mechanism sets its score matrix to Sign(∆) and is informed-truthful and proper for all worlds.
- Truthful reporting strictly beats uninformed strategies because truthful score is positive while signal-independent reporting scores zero.
- Strong truthfulness: Clustered signals permit non-permutation strategies to match truthful payoff, so CA is not strongly truthful in those distributions.
- Strong truthfulness: Without clustered signals or paired permutations, every strategy except symmetric permutations earns less than truthful reporting, making CA strongly truthful.
- Maximality: CA is maximally strongly truthful among multi-task mechanisms using correlation signs and signal-pair indices; clustered signals or paired permutations preclude stronger truthfulness in that class.
- Detail-free implementation: The detail-free CA mechanism estimates correlations from reports and, with enough tasks, remains informed-truthful despite reports influencing the estimated score matrix.
6. CONCLUSION
The paper introduces the Correlated Agreement mechanism for informed truthfulness in multi-signal peer prediction and establishes strong-truthfulness and detail-free variants.
- The CA mechanism makes truthful reporting highest-payoff across joint strategies and strictly better than uninformed strategies.Uninformed strategies do not depend on signals or require effort.
- CA is informed-truthful in general multi-signal domains and reduces to the Dasgupta–Ghosh mechanism for binary signals.
- CA is strongly truthful in categorical domains and maximally strongly truthful among a broad class of multi-task mechanisms.
- A detail-free CA version works without knowledge of the signal distribution while retaining ϵ-informed truthfulness.