2013/07/06 by Aris Filos-Ratsikas, Filos-Ratsikas, Aris, Peter Bro Miltersen +1
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #91A40 #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Voting Systems #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.1307.1766
openalex publication_date 2013/07/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.