Radanovic, GoranFaltings, Boi2019-08-142019-08-142019-08-14201810.1609/aaai.v32i1.11511https://infoscience.epfl.ch/handle/20.500.14299/159854WOS:000485488901082We 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 Theta(log n), where n is the number of agents, and we provide a peer prediction mechanism that achieves this bound in expectation.text::conference output::conference proceedings::conference paper