Budgeted Social Choice: From Consensus to Personalized Decision Making
Tyler Lu and Craig Boutilier
We develop a general framework for the analysis of 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 (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 prove the effectiveness of our algorithms.