AAAI Publications, Twenty-Second International Joint Conference on Artificial Intelligence

Font Size: 
A Maximum Likelihood Approach Towards Aggregating Partial Orders
Lirong Xia, Vincent Conitzer

Last modified: 2011-06-28


In many of the possible applications as well as the theoretical models of computational social choice,the agents’ preferences are represented as partialorders. In this paper, we extend the maximum likelihood approach for defining “optimal” voting rules to this setting. We consider distributions in which the pairwise comparisons / incomparabilities between alternatives are drawn i.i.d. We call suchmodels pairwise-independentmodels and show that they correspond to a class of voting rules that we call pairwise scoring rules. This generalizes rulessuch as Kemeny and Borda. Moreover, we show that Borda is the only pairwise scoring rule that satisfies neutrality, when the outcome space is the set of all alternatives. We then study which voting rules defined for linear orders can be extended to partial orders via our MLE model. We show that any weakly neutral outcome scoring rule (includingany ranking/candidate scoring rule) based onthe weighted majority graph can be represented as the MLE of a weakly neutral pairwise-independent model. Therefore, all such rules admit natural extensionsto profiles of partial orders. Finally, we propose a specific MLE model πk for generating a set of k winning alternatives, and study the computational complexity of winner determination for the MLE of πk.

Full Text: PDF