Partial Truthfulness in Minimal Peer Prediction Mechanisms with Limited Knowledge
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.
Cite
Text
Radanovic and Faltings. "Partial Truthfulness in Minimal Peer Prediction Mechanisms with Limited Knowledge." AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/AAAI.V32I1.11511Markdown
[Radanovic and Faltings. "Partial Truthfulness in Minimal Peer Prediction Mechanisms with Limited Knowledge." AAAI Conference on Artificial Intelligence, 2018.](https://mlanthology.org/aaai/2018/radanovic2018aaai-partial/) doi:10.1609/AAAI.V32I1.11511BibTeX
@inproceedings{radanovic2018aaai-partial,
title = {{Partial Truthfulness in Minimal Peer Prediction Mechanisms with Limited Knowledge}},
author = {Radanovic, Goran and Faltings, Boi},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2018},
pages = {1595-1602},
doi = {10.1609/AAAI.V32I1.11511},
url = {https://mlanthology.org/aaai/2018/radanovic2018aaai-partial/}
}