  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 implementing an outcome whose
expected social welfare is at least an Omega(m^{-3/4}) fraction of the social
welfare of the socially optimal alternative. On the other hand, we show that
for sufficiently many agents and any truthful-in-expectation ordinal mechanism,
there is a valuation profile where the mechanism achieves at most an
O(m^{-{2/3}) fraction of the optimal social welfare in expectation. 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 for m = 3 and a sufficiently large number of
agents, the best mechanism that is ordinal as well as mixed-unilateral has an
approximation ratio between 0.610 and 0.611, the best ordinal mechanism has an
approximation ratio between 0.616 and 0.641, while the best mixed-unilateral
mechanism has an approximation ratio bigger than 0.660. In particular, the best
mixed-unilateral non-ordinal (i.e., cardinal) mechanism strictly outperforms
all ordinal ones, even the non-mixed-unilateral ordinal ones.
