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.

@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}