Vote Elicitation with Probabilistic Preference Models: Empirical Estimation and Cost Tradeoffs
A variety of preference aggregation schemes and voting rules have been developed in social choice to support group decision making. However, the requirement that participants provide full preference information in the form of a complete ranking of alterna
- PDF / 459,052 Bytes
- 15 Pages / 429.442 x 659.895 pts Page_size
- 61 Downloads / 141 Views
Abstract. A variety of preference aggregation schemes and voting rules have been developed in social choice to support group decision making. However, the requirement that participants provide full preference information in the form of a complete ranking of alternatives is a severe impediment to their practical deployment. Only recently have incremental elicitation schemes been proposed that allow winners to be determined with partial preferences; however, while minimizing the amount of information provided, these tend to require repeated rounds of interaction from participants. We propose a probabilistic analysis of vote elicitation that combines the advantages of incremental elicitation schemes—namely, minimizing the amount of information revealed—with those of full information schemes—single (or few) rounds of elicitation. We exploit distributional models of preferences to derive the ideal ranking threshold k, or number of top candidates each voter should provide, to ensure that either a winning or a high quality candidate (as measured by max regret) can be found with high probability. Our main contribution is a general empirical methodology, which uses preference profile samples to determine the ideal ranking threshold for many common voting rules. We develop probably approximately correct (PAC) sample complexity results for one-round protocols with any voting rule and demonstrate the efficacy of our approach empirically on one-round protocols with Borda scoring. Keywords: social choice, voting, preference elicitation, probabilistic rankings.
1 Introduction Researchers in computer science have increasingly adopted preference aggregation methods from social choice, typically in the form of voting rules, for problems where a consensus decision or recommendation must be made for a group of users. The availability of abundant preference data afforded by search engines, recommender systems, and related artifacts, has accelerated the need for good computational approaches to social choice. One problem that has received little attention, however, is that of effective preference elicitation in social choice. Many voting schemes require users or voters to express their preferences over the entire space of options or alternatives, something that is not only onerous, but often extracts more information than is strictly necessary to determine a good consensus option, or winner. Reducing the amount of preference information elicited is critical to easing cognitive and communication demands on users and mitigating privacy concerns. R.I. Brafman, F. Roberts, and A. Tsouki`as (Eds.): ADT 2011, LNAI 6992, pp. 135–149, 2011. c Springer-Verlag Berlin Heidelberg 2011
136
T. Lu and C. Boutilier
Winners can’t be determined in many voting schemes without a large amount of information in the worst case [2,3]. Nonetheless, the development of elicitation schemes that work well in practice has been addressed very recently. Lu and Boutilier [10] use the notion of minimax regret for vote elicitation: this measure not only allows one
Data Loading...
