Reducing the time required to find the Kemeny ranking by exploiting a necessary condition for being a winner

Noelia Rico, Camino R. Vela and Irene Díaz

European Journal of Operational Research, 2023, vol. 305, issue 3, 1323-1336

Abstract: The ranking aggregation problem is gaining attention in different application fields due to its connection with decision making. One of the most famous ranking aggregation methods can be traced back to Kemeny in 1959. Unfortunately, the problem of determining the result of the aggregation proposed by Kemeny, known as Kemeny ranking as it minimizes the number of pairwise discrepancies from a set of rankings given by voters, has been proved to be NP-hard, which unfortunately prevents practitioners from using this method in most real-life problems. In this work, we introduce two exact algorithms for determining the Kemeny ranking. The best of these algorithms guarantees a reasonable search time up to 14 alternatives, showing an important reduction of the execution time in comparison to other algorithms found in the literature. Moreover, a dataset of profiles of rankings is provided and a study of additional aspects of the votes that may have impact on the execution time required to determine the winning ranking is also detailed.

Keywords: Group decisions and negotiations; Combinatorial optimization; Computational social choice; Ranking aggregation; Kemeny method (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722005847
Full text for ScienceDirect subscribers only

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:eee:ejores:v:305:y:2023:i:3:p:1323-1336

DOI: 10.1016/j.ejor.2022.07.031

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().