Partial Truthfulness in Minimal Peer Prediction Mechanisms With Limited Knowledge

Authors

  • Goran Radanovic Harvard University
  • Boi Faltings EPFL

Abstract

We study minimal single-task peer prediction mechanisms that have limited knowledge about agents' beliefs. Without knowing what agents' beliefs are or eliciting additional information, it is not possible to design a truthful mechanism in a Bayesian-Nash sense. We go beyond truthfulness and explore equilibrium strategy profiles that are only partially truthful. Using the results from the multi-armed bandit literature, we give a characterization of how inefficient these equilibria are comparing to truthful reporting. We measure the inefficiency of such strategies by counting the number of dishonest reports that any minimal knowledge-bounded mechanism must have. We show that the order of this number is θ(log n), where n is the number of agents, and we provide a peer prediction mechanism that achieves this bound in expectation.

Downloads

Published

2018-04-25

How to Cite

Radanovic, G., & Faltings, B. (2018). Partial Truthfulness in Minimal Peer Prediction Mechanisms With Limited Knowledge. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/11511

Issue

Section

AAAI Technical Track: Human-Computation and Crowd Sourcing