Using extension sets to aggregate partial rankings in a flexible setting

摘要

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.