Additive Approximation Guarantees for Impartial Sample Mechanisms

30^th January 2019, 13:00
Nicos Protopapas
University of Liverpool

Abstract

A group of peers must decide, one of them to receive a valuable, indivisible prize. All of them care to win the prize, and might be strategic to get it, but no one will try to cheat to help someone else win. The peers will do this by reporting their preferred winner from the rest of the peers. This situation describes the problem of impartial selection and an impartial mechanism is a mechanism that awards the prize and does not allow the peers to benefit by misreporting their preferences. We know from the literature that only approximate solutions are possible. We define a new approximation metric giving a different point of view on the limitations of the problem. Using this metric, we investigate the performance of a natural class of impartial mechanisms: mechanisms that select a sample of the peers and ask them to decide the winner.

This is joint work with Ioannis Caragiannis and Giorgos Christodoulou.