Minimising the Rank Aggregation Error
(Extended Abstract)
M.M. de Weerdt (TU Delft - Algorithmics)
Enrico Gerding (University of Southampton)
Sebastian Stein (University of Southampton)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Rank aggregation is the problem of generating an overall ranking from a set of individual votes which is as close as possible to the (unknown) correct ranking. The challenge is that votes are often both noisy and incomplete. Existing work focuses on the most likely ranking for a particular noise model. Instead, we focus on minimising the error, i.e., the expected distance between the aggregated ranking and the correct one. We show that this results in different rankings, and we show how to compute local improvements of rankings to reduce the error. Extensive experiments on both synthetic data based on Mallows' model and real data show that Copeland has a smaller error than the Kemeny rule, while the latter is the maximum likelihood estimator.