Partial Truthfulness in Minimal Peer Prediction Mechanisms With Limited Knowledge
Authors: Goran Radanovic, Boi Faltings
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | Goran Radanovic Harvard University Cambridge, USA gradanovic@g.harvard.edu Boi Faltings EPFL Lausanne, Switzerland boi.faltings@epfl.ch |
| Pseudocode | Yes | Algorithm 1 depicts the pseudocode of Ada PTS based on the UCB1 algorithm (Auer, Cesa-Bianchi, and Fischer 2002). |
| Open Source Code | No | The paper does not provide any statement about releasing source code or a link to a code repository. |
| Open Datasets | No | The paper is theoretical and does not describe experiments using datasets. Therefore, it does not mention public datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments with data. Therefore, it does not provide training/test/validation splits. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments or mention any hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe experiments requiring specific software dependencies with version numbers. It mentions algorithms and mechanisms as theoretical constructs. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or specific training settings. |