Proceedings

Budgeted Social Choice: From Consensus to Personalized Decision Making

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 280-285.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-057

© 2011 International Joint Conferences on Artificial Intelligence

Abstract

We develop a general framework for social choice problems in which a limited number of alternatives can be recommended to an agent population. In our budgeted social choice model, this limit is determined by a budget, capturing problems that arise naturally in a variety of contexts, and spanning the continuum from pure consensus decision making (i.e., standard social choice) to fully personalized recommendation. Our approach applies a form of segmentation to social choice problems— requiring the selection of diverse options tailored to different agent types—and generalizes certain multi-winner election schemes. We show that standard rank aggregation methods perform poorly, and that optimization in our model is NP-complete; but we develop fast greedy algorithms with some theoretical guarantees. Experiments on real-world datasets demonstrate the effectiveness of our algorithms.

  1. M. R. Ackermann, J. Blömer, and C. Sohler. Clustering for metric and non-metric distance measures. SODA-08, pp.799- 808, Philadelphia, 2008.
  2. K. J. Arrow. A difficulty in the concept of social welfare. J. Political Economy 58:328-346, 1950.
  3. S. Barberà, W. Bossert, and P. K. Pattanaik. Ranking sets of objects. In P.J. Hammond and C. Seidl (eds.), Handbook of Utility Theory, Ch. 17, pp.893-977. Kluwer, 2004.
  4. J. Bartholdi III, C. Tovey, and M. Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare 6:157-165, 1989.
  5. J. Chamberlin and P. Courant. Representative deliberations and representative decisions: Proportional representation and the Borda rule. Amer. Poli. Sci. Rev., 77(3):718-733, 1983.
  6. Y. Chevaleyre, U. Endriss, J. Lang and Nicolas Maudet. A short introduction to computational social choice. SOFSEM- 07, pp.51-69, Harrachov, CZ, 2007.
  7. R. Cohen and L. Katzir. The generalized maximum coverage problem. Inf. Process. Lett., 108(1):15-22, 2008.
  8. W. W. Cohen, R. E. Schapire, and Y. Singer. Learning to order things. JAIR, 10:243-270, 1998.
  9. V. Conitzer and T. Sandholm. Common voting rules as max- imum likelihood estimators. UAI-05, Montreal, pp.145-152, 2005.
  10. P. Diaconis. A generalization of spectral analysis with appli- cation to ranked data. Annals of Stat., 17(3):949-979, 1989.
  11. C. Dwork, R. Kumar, M. Naor, and D. Sivakumar. Rank ag- gregation methods for the web. WWW-01, pp.613-622, 2001.
  12. W. Gaertner. A Primer in Social Choice Theory. Oxford, 2006.
  13. M. T. Hajiaghayi, M. Mahdian, and V. S. Mirrokni. The fa- cility location problem with general cost functions. Networks, 42(1):42-47, 2003.
  14. E. Hüllermeier, J. Fürnkranz, W. Cheng, and K. Brinker. La- bel ranking by learning pairwise preferences. Art. Intel., 172:1897-1916, 2008.
  15. T. Kamishima, H. Kazawa, and S. Akaho. Supervised order- ing: An empirical survey. IEEE ICDM-05, pp.673-676, 2005.
  16. J. G. Kemeny. Mathematics without numbers. Daedalus, 88(4):577-591, 1959.
  17. S. Khuller, A. Moss, and J. Naor. The budgeted maximum coverage problem. Inf. Process. Lett., 70(1):39-45, 1999.
  18. J. Kleinberg, C. Papadimitriou, and P. Raghavan. Segmenta- tion problems. JACM, 51:263-280, 2004.
  19. T. Lu and C. Boutilier. Budgeted social choice: A framework for multiple recommendations in consensus decision making. COMSOC-2010, pp.55-66, D usseldorf, 2010.
  20. T. Lu and C. Boutilier. Robust approximation and incremental elicitation in voting protocols. IJCAI-11, Barcelona, 2011. To appear. IJCAI
  21. G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of ap- proximations for maximizing submodular set functions Math. Prog., 14:265-294, 1978.
  22. R. F. Potthoff and S. J. Brams. Proportional representation: Broadening the options. J. Theor. Politics, 10:147-178, 1998.
  23. A. D. Procaccia, J. S. Rosenschein, and A. Zohar. On the com- plexity of achieving proportional representation. Social Choice and Welfare, 30:353-362, 2008.

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

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