Efficient and Thrifty Voting by Any Means Necessary
Debmalya Mandal, Ariel D Procaccia, Nisarg Shah, David Woodruff
Abstract
We take an unorthodox view of voting by expanding the design space to include both the elicitation rule, whereby voters map their (cardinal) preferences to votes, and the aggregation rule, which transforms the reported votes into collective decisions. Intuitively, there is a tradeoff between the communication requirements of the elicitation rule (i.e., the number of bits of information that voters need to provide about their preferences) and the efficiency of the outcome of the aggregation rule, which we measure through distortion (i.e., how well the utilitarian social welfare of the outcome approximates the maximum social welfare in the worst case). Our results chart the Pareto frontier of the communication-distortion tradeoff.
BibTeX
@inproceedings{NEURIPS2019_c09f9caf,
author = {Mandal, Debmalya and Procaccia, Ariel D and Shah, Nisarg and Woodruff, David},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d\textquotesingle Alch\'{e}-Buc and E. Fox and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Efficient and Thrifty Voting by Any Means Necessary},
url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/c09f9caf5e08836d4673ccdd69bb041e-Paper.pdf},
volume = {32},
year = {2019}
}