2017/11/17 by Goran Radanović, Radanovic, Goran, Boi Faltings +1
Decision Sciences · Social Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Experimental Behavioral Economics Studies #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1711.06614
openalex publication_date 2017/11/17 · openalex created_date 2022/12/22 · openalex updated_date 2026/07/28
We study minimal single-task peer prediction mechanisms that have limited\nknowledge about agents' beliefs. Without knowing what agents' beliefs are or\neliciting additional information, it is not possible to design a truthful\nmechanism in a Bayesian-Nash sense. We go beyond truthfulness and explore\nequilibrium strategy profiles that are only partially truthful. Using the\nresults from the multi-armed bandit literature, we give a characterization of\nhow inefficient these equilibria are comparing to truthful reporting. We\nmeasure the inefficiency of such strategies by counting the number of dishonest\nreports that any minimal knowledge-bounded mechanism must have. We show that\nthe order of this number is \Θ(\log n), where n is the number of\nagents, and we provide a peer prediction mechanism that achieves this bound in\nexpectation.\n