A Geometric Method to Construct Minimal Peer Prediction Mechanisms
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.
Cite
Text
Frongillo and Witkowski. "A Geometric Method to Construct Minimal Peer Prediction Mechanisms." AAAI Conference on Artificial Intelligence, 2016. doi:10.1609/AAAI.V30I1.10050Markdown
[Frongillo and Witkowski. "A Geometric Method to Construct Minimal Peer Prediction Mechanisms." AAAI Conference on Artificial Intelligence, 2016.](https://mlanthology.org/aaai/2016/frongillo2016aaai-geometric/) doi:10.1609/AAAI.V30I1.10050BibTeX
@inproceedings{frongillo2016aaai-geometric,
title = {{A Geometric Method to Construct Minimal Peer Prediction Mechanisms}},
author = {Frongillo, Rafael M. and Witkowski, Jens},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2016},
pages = {502-508},
doi = {10.1609/AAAI.V30I1.10050},
url = {https://mlanthology.org/aaai/2016/frongillo2016aaai-geometric/}
}