Truthful approximations to range voting

14^th October 2014, 13:00 Ashton Lecture Theater
Aris Filos-Ratsikas

Abstract

We consider the fundamental mechanism design problem of
approximate social welfare maximization under general cardinal
preferences on a finite number of alternatives and without
money. The well-known range voting scheme can be thought of as
a non-truthful mechanism for exact social welfare maximization in this
setting. With m being the number of alternatives, we exhibit a
randomized truthful-in-expectation ordinal mechanism with
approximation ratio \Omega(m^{-3/4}). On the other hand, we show
that for sufficiently many agents, the approximation ratio of any
truthful-in-expectation ordinal mechanism is O(m^{-2/3}). We supplement
our results with an upper bound for any truthful mechanism. We get tighter
bounds for the natural special case of $m = 3$, and in that case furthermore
obtain separation results concerning the approximation ratios achievable by
natural restricted classes of truthful-in-expectation mechanisms. In particular,
we show that the best cardinal truthful mechanism strictly outperforms all ordinal ones.