by R. Frongillo, J. Witkowski

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.

Reference:

A Geometric Method to Construct Minimal Peer Prediction Mechanisms R. Frongillo, J. WitkowskiIn Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI'16), 2016Superceded by the TEAC paper above.

Bibtex Entry:

@inproceedings{frongillo-witkowski:2016, Author = {Frongillo, Rafael and Witkowski, Jens}, Booktitle = {Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI'16)}, Month = {February}, Note = {Superceded by the TEAC paper above.}, Title = {A Geometric Method to Construct Minimal Peer Prediction Mechanisms}, Year = 2016}