A Decision-theoretic Model of Rank Aggregation

Modern social choice theory has spurred considerable recent work in computa-tional rank aggregation, the problem of aggregating rankings into a consensus ranking. However, in the social choice context where rankings represent prefer-ences of agents, or “voters, ” over outcomes, or “candidates, ” there is scant jus-tification in the literature for producing rankings as an output of the aggregation process. We introduce a novel model which offers one possible decision-theoretic motivation for constructing a consensus ranking rather than an outcome. Roughly speaking, we view rankings as a compact, easily communicable decision policy in the face of uncertainty about candidate availability. This gives rise to a princi-pled approach, based on minimizing expected dissatisfaction with the candidate choice, for optimization functions on rankings. We provide exact and approxi-mation algorithms for computing optimal rankings in our model that exploit the properties of our objective function. We also describe interesting connections to popular voting protocols such as the plurality rule and the Kemeny consensus.