AAAI Publications, Thirtieth AAAI Conference on Artificial Intelligence

Font Size: 
Optimal Aggregation of Uncertain Preferences
Ariel D. Procaccia, Nisarg Shah

Last modified: 2016-02-21


A paradigmatic problem in social choice theory deals with the aggregation of subjective preferences of individuals --- represented as rankings of alternatives --- into a social ranking. We are interested in settings where individuals are uncertain about their own preferences, and represent their uncertainty as distributions over rankings. Under the classic objective of minimizing the (expected) sum of Kendall tau distances between the input rankings and the output ranking, we establish that preference elicitation is surprisingly straightforward and near-optimal solutions can be obtained in polynomial time. We show, both in theory and using real data, that ignoring uncertainty altogether can lead to suboptimal outcomes.


Uncertainty; Voting; Preference elicitation

Full Text: PDF