Budgeted Social Choice: From Consensus to Personalized Decision Making

Lu, Tyler; Boutilier, Craig

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

Budgeted Social Choice: From Consensus to Personalized Decision Making

Tyler Lu, Craig Boutilier

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

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.

Tyler Lu, and Craig Boutilier. 2011. Budgeted Social Choice: From Consensus to Personalized Decision Making. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 280–285. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-057

@inproceedings{ijcai2011p57,
  title     = {Budgeted Social Choice: From Consensus to Personalized Decision Making},
  author    = {Lu, Tyler and Boutilier, Craig},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {280--285},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-057},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-057},
}

TY  - CPAPER
TI  - Budgeted Social Choice: From Consensus to Personalized Decision Making
AU  - Lu, Tyler
AU  - Boutilier, Craig
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 280
EP  - 285
DO  - 10.5591/978-1-57735-516-8/IJCAI11-057
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-057
ER  -