A Robust Bayesian Truth Serum for Non-Binary Signals

Goran Radanovic, Boi Faltings

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:

  1. Information Report ($x_i$): The agent's actual observation (e.g., a rating from 0 to 2).
  2. Prediction Report ($y_i$): The agent's belief about the distribution of signals reported by their peers.
The interaction flow between agents and the center in the RBTS mechanism.

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.

Example probability distribution and conditional beliefs for a three-signal scenario.

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

Abstract

Several mechanisms have been proposed for incentivizing truthful reports of a private signals owned by rational agents, among them the peer prediction method and the Bayesian truth serum. The robust Bayesian truth serum (RBTS) for small populations and binary signals is particularly interesting since it does not require a common prior to be known to the mechanism. We further analyze the problem of the common prior not known to the mechanism and give several results regarding the restrictions that need to be placed in order to have an incentive-compatible mechanism. Moreover, we construct a Bayes-Nash incentive-compatible scheme called multi-valued RBTS that generalizes RBTS to operate on both small populations and non-binary signals.
BibTeX
@inproceedings{radanovic2013robust,
  author = {Goran Radanovic and Boi Faltings},
  title = {{A Robust Bayesian Truth Serum for Non-Binary Signals}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8677},
}
Figure