Truthful Approximations To Range Voting

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.