Using extension sets to aggregate partial rankings in a flexible setting

作者:

Highlights:

摘要

This paper deals with the rank aggregation problem in a general setting; in particular, we approach the problem for any kind of ranking: complete or incomplete and with or without ties. The underlying idea behind our approach is to take into account the so-called extension set of a ranking, that is, the set of permutations that are compatible with the given ranking. In this way we aim to manage the uncertainty inherent to this problem, when not all the items are ranked and/or when some items are equally preferred. We develop two approaches: a general one based on this idea, and a constrained version in which the extension set is limited by not allowing non-ranked items to be placed in an existent bucket of tied items. We test our proposal by coupling it with two different algorithms. We formalize our approaches mathematically and also carry out an extensive experimental evaluation by using 22 datasets. The results show that the use of our extension sets-based approaches to compute the precedence matrix, clearly outperforms the standard way of computing the preference matrix by only using the information explicitly provided by the rankings in the sample.

论文关键词:Rank aggregation problem,Kemeny ranking problem,Borda method,Extension set,Partial ranking,Ranking with ties

论文评审过程:Received 20 November 2014, Revised 5 April 2016, Accepted 1 June 2016, Available online 20 July 2016, Version of Record 20 July 2016.

论文官网地址:https://doi.org/10.1016/j.amc.2016.06.005