Document Open Access Logo

On the Welfare of Cardinal Voting Mechanisms

Authors Umang Bhaskar, Abheek Ghosh

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2018.27.pdf
  • Filesize: 0.5 MB
  • 22 pages

Document Identifiers

Author Details

Umang Bhaskar
  • Tata Institute of Fundamental Research, Mumbai, India
Abheek Ghosh
  • The University of Texas at Austin, TX, USA

Funding

  • Bhaskar, Umang: Research funded in part by a Ramanujan fellowship.

Cite As Get BibTex

Umang Bhaskar and Abheek Ghosh. On the Welfare of Cardinal Voting Mechanisms. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 27:1-27:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FSTTCS.2018.27

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
Keywords
  • computational social choice
  • voting rules
  • cardinal mechanisms
  • price of anarchy
  • distortion

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Salvador Barbera. Nice decision schemes. In Decision theory and social ethics, pages 101-117. Springer, 1978. Google Scholar
  2. Salvador Barbera. An introduction to strategy-proof social choice functions. Soc Choice Welfare 18, pages 619-653, 2001. Google Scholar
  3. Salvador Barbera, Anna Bogomolnaia, and Hans Van Der Stel. Strategy-proof probabilistic rules for expected utility maximizers. Mathematical Social Sciences, 35(2):89-103, 1998. Google Scholar
  4. Gerdus Benade, Swaprava Nath, Ariel D. Procaccia, and Nisarg Shah. Preference Elicitation For Participatory Budgeting. In Association for Advancement of Artificial Intelligence (AAAI), February 4 - 9, 2017, San Francisco, California, USA, 2017. Forthcoming. Google Scholar
  5. Umang Bhaskar, Varsha Dani, and Abheek Ghosh. Truthful and Near-Optimal Mechanisms for Welfare Maximization in Multi-Winner Elections. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, New Orleans, Louisiana, USA, February 2-7, 2018, 2018. Google Scholar
  6. Eleanor Birrell and Rafael Pass. Approximately strategy-proof voting. In IJCAI, pages 67-72, 2011. Google Scholar
  7. Craig Boutilier, Ioannis Caragiannis, Simi Haber, Tyler Lu, Ariel D. Procaccia, and Or Sheffet. Optimal social choice functions: A utilitarian view. Artif. Intell., 227:190-213, 2015. URL: http://dx.doi.org/10.1016/j.artint.2015.06.003.
  8. Felix Brandt, Vincent Conitzer, Ulle Endriss, Ariel D Procaccia, and Jérôme Lang. Handbook of computational social choice. Cambridge University Press, 2016. Google Scholar
  9. Simina Brânzei, Ioannis Caragiannis, Jamie Morgenstern, and Ariel D Procaccia. How bad is selfish voting? In AAAI, volume 13, pages 138-144, 2013. Google Scholar
  10. Bhaskar Dutta, Hans Peters, and Arunava Sen. Strategy-proof cardinal decision schemes. Social Choice Welfare, 28:163-179, 2007. Google Scholar
  11. Edith Elkind, Evangelos Markakis, Svetlana Obraztsova, and Piotr Skowron. Equilibria of plurality voting: Lazy and truth-biased voters. In International Symposium on Algorithmic Game Theory, pages 110-122. Springer, 2015. Google Scholar
  12. Uriel Feige and Moshe Tennenholtz. Responsive Lotteries. In Algorithmic Game Theory - Third International Symposium, SAGT 2010, Athens, Greece, October 18-20, 2010. Proceedings, pages 150-161, 2010. Google Scholar
  13. Aris Filos-Ratsikas and Peter Bro Miltersen. Truthful approximations to range voting. International Conference on Web and Internet Economics, pages 175-188, 2014. Google Scholar
  14. Sumit Ghosh, Manisha Mundhe, Karina Hernandez, and Sandip Sen. Voting for movies: the anatomy of a recommender system. In Proceedings of the third annual conference on Autonomous Agents, pages 434-435. ACM, 1999. Google Scholar
  15. Allan Gibbard. Manipulation of voting schemes: a general result. Econometrica: journal of the Econometric Society, pages 587-601, 1973. Google Scholar
  16. Allan Gibbard. Manipulation of schemes that mix voting with chance. Econometrica: Journal of the Econometric Society, pages 665-681, 1977. Google Scholar
  17. Claude Hillinger. The case for utilitarian voting. SSRN, 2005. URL: http://dx.doi.org/10.2139/ssrn.732285.
  18. Aanund Hylland. Strategy proofness of voting procedures with lotteries as outcomes and infinite sets of strategies. Unpublished paper, University of Oslo.[341, 349], 1980. Google Scholar
  19. Omer Lev and Jeffrey S Rosenschein. Convergence of iterative voting. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 2, pages 611-618. International Foundation for Autonomous Agents and Multiagent Systems, 2012. Google Scholar
  20. Reshef Meir, Maria Polukarov, Jeffrey S Rosenschein, and Nicholas R Jennings. Convergence to Equilibria in Plurality Voting. In AAAI, volume 10, pages 823-828, 2010. Google Scholar
  21. Shasikanta Nandeibam. An alternative proof of Gibbard’s random dictatorship result. Social Choice and Welfare, 15(4):509-519, 1998. Google Scholar
  22. Svetlana Obraztsova, Evangelos Markakis, Maria Polukarov, Zinovi Rabinovich, and Nicholas R. Jennings. On the Convergence of Iterative Voting: How Restrictive Should Restricted Dynamics Be? In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA., pages 993-999, 2015. Google Scholar
  23. Svetlana Obraztsova, Evangelos Markakis, and David RM Thompson. Plurality voting with truth-biased agents. In International Symposium on Algorithmic Game Theory, pages 26-37. Springer, 2013. Google Scholar
  24. Ariel D Procaccia and Jeffrey S Rosenschein. The distortion of cardinal preferences in voting. In International Workshop on Cooperative Information Agents, pages 317-331. Springer, 2006. Google Scholar
  25. Zinovi Rabinovich, Svetlana Obraztsova, Omer Lev, Evangelos Markakis, and Jeffrey S. Rosenschein. Analysis of Equilibria in Iterative Voting Schemes. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA., pages 1007-1013, 2015. Google Scholar
  26. Reyhaneh Reyhani and Mark Wilson. Best-reply dynamics for scoring rules. In 20th European Conference on Artificial Intelligence. IOS Press, 2012. Google Scholar
  27. Mark Allen Satterthwaite. Strategy-proofness and Arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of economic theory, 10(2):187-217, 1975. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact