10 February 2017, Computational Social Choice Seminar, Mathijs de Weerdt

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.

The talk will start with a brief introduction into rank aggregation, discussing basic concepts such as the Mallows model for ranking a number of alternatives, and the use of the Kemeny rule for rank aggregation to maximise the likelihood of an aggregate ranking. Then we define the objective of 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.

This is work is done jointly with Enrico Gerding and Sebastian Stein, University of Southampton, UK.