Abstract
This paper introduces a multi-valued Robust Bayesian Truth Serum (RBTS), an incentive mechanism designed to elicit truthful reports of private, non-binary information when ground truth is unavailable. By requiring agents to provide both an observation and a prediction of peer reports, the mechanism achieves incentive compatibility under a "self-predicting" assumption, even with small populations and unknown priors.
Introduction
In domains such as crowdsourcing, sensor networks, and opinion polling, researchers often collect data that cannot be immediately verified against a ground truth. Ensuring that agents report their private information truthfully is a significant challenge. Existing peer prediction methods often rely on two restrictive assumptions: that the data collector (the "center") knows the statistical likelihood of different answers (the common prior problem), and that signals are binary (e.g., Yes/No). This paper addresses these limitations by extending the Robust Bayesian Truth Serum to handle complex, multi-valued data.
The Multi-valued RBTS Mechanism
The authors propose the Multi-valued Robust Bayesian Truth Serum (RBTS), which requires each agent $i$ to submit two distinct reports to the center:
- Information Report ($x_i$): The agent's actual observation (e.g., a rating from 0 to 2).
- Prediction Report ($y_i$): The agent's belief about the distribution of signals reported by their peers.
The mechanism calculates a score for each agent based on a decomposable payment scheme. The Information Score rewards agents whose reports match a peer's report, scaled by the inverse of the peer's prediction to incentivize "surprisingly common" answers. The Prediction Score uses a strictly proper scoring rule to reward the accuracy of the agent's prediction relative to the peer's actual report.
Theoretical Foundations
The core of the mechanism's success lies in the self-predicting assumption. This assumption posits that an agent believes a specific signal is more likely to be observed by others if they observed it themselves. This is a significantly weaker and more realistic requirement than the "self-dominant" assumption used in previous literature. The authors prove that under this condition, truth-telling constitutes a Bayes-Nash equilibrium.
Numerical Illustration
To demonstrate the mechanism's efficacy, the authors provide a numerical example involving three possible signal values (0, 1, 2). The table below illustrates a sample prior distribution and the resulting conditional beliefs an agent might hold.
In this scenario, an agent who observes signal $S_i = 1$ updates their belief about a peer's signal $S_j$ according to the middle column. The RBTS ensures that reporting $x_i = 1$ and the corresponding belief $y_i$ maximizes the agent's expected payoff.
Key Results and Generalization
The paper establishes several critical results:
- Impossibility Results: Theorems 1 and 2 show that without restrictions on belief updates, no mechanism can universally guarantee incentive compatibility for non-binary signals using only one or two reports.
- Incentive Compatibility: Theorem 3 proves that the multi-valued RBTS is incentive-compatible under the self-predicting assumption.
- Broad Applicability: The method generalizes the original binary RBTS to any number of signal values ($m \ge 2$) and supports populations as small as two agents, a significant improvement over the original Bayesian Truth Serum (BTS).
Conclusion
The Multi-valued RBTS provides a robust framework for eliciting truthful non-binary data without requiring a known prior. While it relies on the self-predicting assumption and assumes no collusion among agents, it represents a major step forward in peer prediction. Future research may explore even weaker conditions for incentive compatibility and the impact of coordinated strategic behavior.
Summary updated