Truthful approximations to range voting - Filos-Ratsikas, A; Miltersen, P (Springer Verlag, 2014)
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 Ω(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-in-expectation 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.