Sample Complexity of Peer Prediction
2026-08-17 • Information Theory
Information TheoryComputer Science and Game Theory
AI summaryⓘ
The authors study how to reward people for honestly sharing information without knowing the true answer, using something called mutual information. They focus on figuring out which types of mutual information can be correctly estimated from a limited number of examples. They find that with very few samples, only trivial or one special type of mutual information (called DMI) works well, but with more samples, other types appear. They also improve the way to estimate DMI and explore new methods that use a flexible number of samples to reduce uncertainty in the rewards.
peer predictionmutual informationunbiased estimatorDeterminant Mutual Information (DMI)information theorysample complexitybinary report spacevariance reductionscoring rule
Authors
Abdellah Aznag, Robin Bowers, Rachel Cummings, Jason Hartline, Matthew vonAllmen, Bo Waggoner
Abstract
Peer prediction seeks to incentivize agents to truthfully report an observed signal by rewarding joint sets of reports without observing a ground truth. Following the generalization of information-theoretic mutual information introduced in Kong and Schoenebeck (2019), we call a function of a joint distribution over signals a mutual information when it is non-negative and disincentivizes garbling reports for all information structures. An unbiased estimator for a mutual information takes some number of samples from the distribution and returns rewards for both agents, such that the expected reward is equal to the mutual information. We seek to characterize the set of mutual informations with unbiased estimators for a given number of samples. We show that for three or fewer sampled report pairs, the only mutual information with an unbiased estimator is trivially zero, and for four or five samples with a binary report space, the Determinant Mutual Information (DMI) of Kong (2024) is the unique mutual information (up to a scalar multiple). We further show that DMI ceases to be unique at six samples. We provide an improved estimator of DMI for any given number of samples and characterize its convergence rate. We also examine mutual information estimators that accept a randomized number of samples. First, we show that mutual information estimators on an ex-ante bounded number of samples (termed "stop-short estimators") can achieve a lower variance than an equivalent fixed-sample estimator (for DMI). Second, we introduce the class of scoring-rule-based mutual informations and identify in this family a mutual information that can be estimated with under three samples in expectation.