Truthful approximations to range voting

DOI10.1007/978-3-319-13129-0_13MaRDI QIDQ2936984zbMATH OpenOpenAlexFDO

Authors Aris Filos-Ratsikas, Peter Bro Miltersen

Publication date 7 January 2015

Published in Web and Internet Economics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.1766

zbMATH Keywords

mechanism designrange votingsocial welfare maximization

Mathematics Subject Classification ID

Other game-theoretic models (91A40) Voting theory (91B12)

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 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.

Recommendations

• Welfare maximization and truthfulness in mechanism design with ordinal preferences
• Social welfare in one-sided matchings: random priority and beyond
• Ordinal versus cardinal voting rules: a mechanism design approach
• scientific article; zbMATH DE number 6519655
• Truthful Mechanisms for Matching and Clustering in an Ordinal World

Cited in

(14)

• Strategy-proof voting on compact ranges
• Voting with evaluations: characterizations of evaluative voting and range voting
• Peeking behind the ordinal curtain: improving distortion via cardinal queries
• Welfare maximization and truthfulness in mechanism design with ordinal preferences
• Range convexity, continuity, and strategy-proofness of voting schemes
• On the welfare of cardinal voting mechanisms
• The distortion of distributed voting
• Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship
• Don’t Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond
• Truthful ownership transfer with expert advice
• Revisiting the distortion of distributed voting
• Approximating optimal social choice under metric preferences
• Improved metric distortion via threshold approvals
• Utilitarian distortion with predictions

This page was built for publication: Truthful approximations to range voting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2936984)