AAAI Publications, Thirtieth AAAI Conference on Artificial Intelligence

Font Size: 
A Geometric Method to Construct Minimal Peer Prediction Mechanisms
Rafael Frongillo, Jens Witkowski

Last modified: 2016-02-21

Abstract


Minimal peer prediction mechanisms truthfully elicit private information (e.g., opinions or experiences) from rational agents without the requirement that ground truth is eventually revealed. In this paper, we use a geometric perspective to prove that minimal peer prediction mechanisms are equivalent to power diagrams, a type of weighted Voronoi diagram. Using this characterization and results from computational geometry, we show that many of the mechanisms in the literature are unique up to affine transformations, and introduce a general method to construct new truthful mechanisms.

Keywords


Mechanism Design; Peer Prediction; Incentive Schemes; Computational Geometry; Power Diagram; Robustness

Full Text: PDF