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. We also show that classical peer prediction is ``complete'' in that every minimal mechanism can be written as a classical peer prediction mechanism for some scoring rule. Finally, we use our geometric characterization to develop a general method for constructing new truthful mechanisms, and we show how to optimize for the mechanisms' effort incentives and robustness.
Reference:
A Geometric Perspective on Minimal Peer Prediction R. Frongillo, J. WitkowskiIn ACM Transactions on Economics and Computation (TEAC), 2017Forthcoming. Supercedes the AAAI'16 paper below.
Bibtex Entry:
@article{frongillo-witkowski:2017,
	Author = {Frongillo, Rafael and Witkowski, Jens},
        Journal = {ACM Transactions on Economics and Computation (TEAC)},
        Note = {Forthcoming. Supercedes the AAAI'16 paper below.},
 	Title = {A Geometric Perspective on Minimal Peer Prediction},
	Year = 2017}