by ,
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), 2016
Bibtex Entry:
@inproceedings{frongillo-witkowski-aaai16,
	Author = {Frongillo, Rafael and Witkowski, Jens},
	Booktitle = {Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI'16)},
	Month = {February},
	Title = {A Geometric Method to Construct Minimal Peer Prediction Mechanisms},
	Year = 2016}