License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2018.27
URN: urn:nbn:de:0030-drops-99260
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9926/
Bhaskar, Umang ;
Ghosh, Abheek
On the Welfare of Cardinal Voting Mechanisms
Abstract
A voting mechanism is a method for preference aggregation that takes as input preferences over alternatives from voters, and selects an alternative, or a distribution over alternatives. While preferences of voters are generally assumed to be cardinal utility functions that map each alternative to a real value, mechanisms typically studied assume coarser inputs, such as rankings of the alternatives (called ordinal mechanisms). We study cardinal mechanisms, that take as input the cardinal utilities of the voters, with the objective of minimizing the distortion - the worst-case ratio of the best social welfare to that obtained by the mechanism.
For truthful cardinal mechanisms with m alternatives and n voters, we show bounds of Theta(mn), Omega(m), and Omega(sqrt{m}) for deterministic, unanimous, and randomized mechanisms respectively. This shows, somewhat surprisingly, that even mechanisms that allow cardinal inputs have large distortion. There exist ordinal (and hence, cardinal) mechanisms with distortion O(sqrt{m log m}), and hence our lower bound for randomized mechanisms is nearly tight. In an effort to close this gap, we give a class of truthful cardinal mechanisms that we call randomized hyperspherical mechanisms that have O(sqrt{m log m}) distortion. These are interesting because they violate two properties - localization and non-perversity - that characterize truthful ordinal mechanisms, demonstrating non-trivial mechanisms that differ significantly from ordinal mechanisms.
Given the strong lower bounds for truthful mechanisms, we then consider approximately truthful mechanisms. We give a mechanism that is delta-truthful given delta in (0,1), and has distortion close to 1. Finally, we consider the simple mechanism that selects the alternative that maximizes social welfare. This mechanism is not truthful, and we study the distortion at equilibria for the voters (equivalent to the Price of Anarchy, or PoA). While in general, the PoA is unbounded, we show that for equilibria obtained from natural dynamics, the PoA is close to 1. Thus relaxing the notion of truthfulness in both cases allows us to obtain near-optimal distortion.
BibTeX - Entry
@InProceedings{bhaskar_et_al:LIPIcs:2018:9926,
author = {Umang Bhaskar and Abheek Ghosh},
title = {{On the Welfare of Cardinal Voting Mechanisms}},
booktitle = {38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
pages = {27:1--27:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-093-4},
ISSN = {1868-8969},
year = {2018},
volume = {122},
editor = {Sumit Ganguly and Paritosh Pandya},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9926},
URN = {urn:nbn:de:0030-drops-99260},
doi = {10.4230/LIPIcs.FSTTCS.2018.27},
annote = {Keywords: computational social choice, voting rules, cardinal mechanisms, price of anarchy, distortion}
}
|
Keywords: |
|
computational social choice, voting rules, cardinal mechanisms, price of anarchy, distortion |
|
Collection: |
|
38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
05.12.2018 |
