A Geometric Perspective on Minimal Peer Prediction

Rafael M. Frongillo, Jens WitkowskiACM Trans. Economics and Comput 2017 · DOI · OpenReview

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 article, 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.
BibTeX
@article{frongillo2017geometric,
  author = {Rafael M. Frongillo and Jens Witkowski},
  title = {{A Geometric Perspective on Minimal Peer Prediction}},
  journal = {ACM Trans. Economics and Comput.},
  year = {2017},
  doi = {10.1145/3070903},
}

Loading related content...

Figure