Proceedings

Randomized Social Choice Functions under Metric Preferences

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 46-58.

© 2016 International Joint Conferences on Artificial Intelligence

Abstract

We determine the quality of randomized social choice mechanisms in a setting in which the agents have metric preferences: every agent has a cost for each alternative, and these costs form a metric. We assume that these costs are unknown to the mechanisms (and possibly even to the agents themselves), which means we cannot simply select the optimal alternative, i.e. the alternative that minimizes the total agent cost (or median agent cost). However, we do assume that the agents know their ordinal preferences that are induced by the metric space. We examine randomized social choice functions that require only this ordinal information and select an alternative that is good in expectation with respect to the costs from the metric. To quantify how good a randomized social choice function is, we bound the distortion, which is the worst-case ratio between expected cost of the alternative selected and the cost of the optimal alternative. We provide new distortion bounds for a variety of randomized mechanisms, for both general metrics and for important special cases. Our results show a sizable improvement in distortion over deterministic mechanisms.

  1. [Anshelevich and Postl, 2015] Elliot Anshelevich and John Postl. Randomized social choice functions under metric pref- erences. CoRR, abs/1512.07590, 2015.
  2. [Anshelevich et al., 2015] Elliot Anshelevich, Onkar Bhard- waj, and John Postl. Approximating optimal social choice under metric preferences. In Proc. 29th AAAI Conf. Artificial Intell., pages 777-783. AAAI Press, 2015.
  3. [Aziz and Stursberg, 2014] Haris Aziz and Paul Stursberg. A generalization of probabilistic serial to randomized social choice. In Proc. 28th AAAI Conf. Artificial Intell., pages 559- 565. AAAI Press, 2014.
  4. [Aziz et al., 2013] Haris Aziz, Felix Brandt, and Markus Brill. On the tradeoff between economic efficiency and strate- gyproofness in randomized social choice. In Proc. 2013 Int. Conf. Autonomous Agents and Multi-agent Syst., pages 455- 462, 2013.
  5. [Bogomolnaia and Moulin, 2001] Anna Bogomolnaia and Hervé Moulin. A new solution to the random assignment problem. J. Econ. Theory, 100(2):295 -328, 2001.
  6. [Boutilier et al., 2012] Craig Boutilier, Ioannis Caragiannis, Simi Haber, Tyler Lu, Ariel D. Procaccia, and Or Sheffet. Optimal social choice functions: A utilitarian view. In Pro- ceedings of the 13th ACM Conference on Electronic Com- merce, pages 197-214. ACM, 2012.
  7. [Campos Rodríguez and Moreno Pérez, 2008] Clara M. Cam- pos Rodríguez and José A. Moreno Pérez. Multiple voting location problems. Eur. J. Oper. Res., 191(2):437-453, De- cember 2008.
  8. [Caragiannis and Procaccia, 2011] Ioannis Caragiannis and Ariel D. Procaccia. Voting almost maximizes social welfare despite limited communication. Artificial Intell., 175(9):1655-1671, June 2011.
  9. [Chakrabarty and Swamy, 2014] Deeparnab Chakrabarty and Chaitanya Swamy. Welfare maximization and truthfulness in mechanism design with ordinal preferences. In Proc. 5th Conf. Innovations in Theoretical Comput. Sci., pages 105- 120. ACM, 2014.
  10. [Chatterji et al., 2014] Shurojit Chatterji, Arunava Sen, and Huaxia Zeng. Random dictatorship domains. Games and Econ. Behavior, 86:212-236, July 2014.
  11. [Christodoulou et al., 2016] George Christodoulou, Aris Filos- Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Gold- berg, Jie Zhang, and Jinshan Zhang. Social welfare in one- sided matching mechanisms. CoRR, abs/1502.03849, Febru- ary 2016.
  12. [Elkind and Faliszewski, 2014] Edith Elkind and Piotr Fal- iszewski. Recognizing 1-euclidean preferences: An alter- native approach. In Proc. 7th Int. Symp. Algorithmic Game Theory, pages 146-157. Springer, 2014.
  13. [Enelow and Hinich, 1984] James M. Enelow and Melvin J. Hinich. The Spatial Theory of Voting: An Introduction. Cam- bridge University Press, New York, NY, 1984.
  14. [Escoffier et al., 2011] Bruno Escoffier, Laurent Gourves, Nguyen Kim Thang, Fanny Pascual, and Olivier Spanjaard. Strategy-proof mechanisms for facility location games with many facilities. In Proc. 2nd Int. Conf. Algorithmic Decision Theory, pages 67-81. Springer, 2011.
  15. [Feldman et al., 2015] Michal Feldman, Amos Fiat, and Id- dan Golomb. On voting and facility location. CoRR, abs/1512.05868, December 2015.
  16. [Filos-Ratsikas et al., 2014] Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, and Jie Zhang. Social welfare in one-sided matchings: Random priority and beyond. In Proc. 7th Int. Symp. Algorithmic Game Theory, pages 1-12. Springer, 2014.
  17. [Fishburn and Gehrlein, 1977] Peter C. Fishburn and William V. Gehrlein. Towards a theory of elections with probabilistic preferences. Econometrica, 45(8):1907-1924, 1977.
  18. [Fishburn, 1972] Peter C. Fishburn. Lotteries and social choices. J. Econ. Theory, 5(2):189 -207, 1972.
  19. [Gans and Smart, 1996] Joshua S. Gans and Michael Smart. Majority voting with single-crossing preferences. J. Public Econ., 59(2):219-237, February 1996.
  20. [Goel and Lee, 2012] Ashish Goel and David Lee. Triadic con- sensus. In Proc. 8th Workshop Internet and Network Econ., pages 434-447. Springer, 2012.
  21. [Harsanyi, 1976] John C. Harsanyi. Cardinal welfare, indi- vidualistic ethics, and interpersonal comparisons of utility. Springer, 1976.
  22. [Intriligator, 1973] Michael D. Intriligator. A probabilistic model of social choice. Rev. Econ. Stud., 40(4):553-560, October 1973.
  23. [Merrill and Grofman, 1999] Samuel Merrill and Bernard Grofman. A unified theory of voting: Directional and proximity spatial models. Cambridge University Press, 1999.
  24. [Oren and Lucier, 2014] Joel Oren and Brendan Lucier. Online (budgeted) social choice. In Proc. 28th AAAI Conf. Artificial Intell., pages 1456-1462. AAAI Press, 2014.
  25. [Procaccia and Rosenschein, 2006] Ariel D. Procaccia and Jef- frey S. Rosenschein. The distortion of cardinal preferences in voting. In Proc. 10th Int. Workshop Cooperative Inform. Agents X, pages 317-331. Springer, 2006.
  26. [Procaccia and Tennenholtz, 2009] Ariel D. Procaccia and Moshe Tennenholtz. Approximate mechanism design with- out money. In Proc. 10th ACM Conf. Electron. Commerce, pages 177-186. ACM, 2009.
  27. [Sui et al., 2013] Xin Sui, Alex Francois-Nienaber, and Craig Boutilier. Multi-dimensional single-peaked consistency and its approximations. In Proc. 23rd Int. Joint Conf. Artificial Intell., pages 375-382. AAAI Press, 2013. IJCAI
  28. [Zeckhauser, 1969] Richard Zeckhauser. Majority rule with lotteries on alternatives. Quart. J. Econ., 83(4):696-703, 1969.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards