Reducing the Computational Time for the Kemeny Method by Exploiting Condorcet Properties

Noelia Rico, Camino R. Vela, Raúl Pérez-Fernández and Irene Díaz
Additional contact information
Noelia Rico: Department of Computer Science, University of Oviedo, 33203 Gijón, Spain
Camino R. Vela: Department of Computer Science, University of Oviedo, 33203 Gijón, Spain
Raúl Pérez-Fernández: Department of Statistics and O.R. and Mathematics Didactics, University of Oviedo, 33007 Oviedo, Spain
Irene Díaz: Department of Computer Science, University of Oviedo, 33203 Gijón, Spain

Mathematics, 2021, vol. 9, issue 12, 1-12

Abstract: Preference aggregation and in particular ranking aggregation are mainly studied by the field of social choice theory but extensively applied in a variety of contexts. Among the most prominent methods for ranking aggregation, the Kemeny method has been proved to be the only one that satisfies some desirable properties such as neutrality, consistency and the Condorcet condition at the same time. Unfortunately, the problem of finding a Kemeny ranking is NP-hard, which prevents practitioners from using it in real-life problems. The state of the art of exact algorithms for the computation of the Kemeny ranking experienced a major boost last year with the presentation of an algorithm that provides searching time guarantee up to 13 alternatives. In this work, we propose an enhanced version of this algorithm based on pruning the search space when some Condorcet properties hold. This enhanced version greatly improves the performance in terms of runtime consumption.

Keywords: ranking aggregation; Condorcet; Kemeny method; exact algorithm; recursive method (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/12/1380/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/12/1380/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:12:p:1380-:d:574921

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().