A new approach for identifying the Kemeny median ranking

Condorcet consistent rules were originally developed for preference aggregation in the theory of social choice. Nowadays these rules are applied in a variety of fields such as discrete multi-criteria analysis, defence and security decision support, composite indicators, machine learning, artificial intelligence, queries in databases or internet multiple search engines and theoretical computer science. The cycle issue, known also as Condorcet's paradox, is the most serious problem inherent in this type of rules. Solutions for dealing with the cycle issue properly already exist in the literature; the most important one being the identification of the median ranking, often called the Kemeny ranking. Unfortunately its identification is a NP-hard problem. This article has three main objectives: (1) to clarify that the Kemeny median order has to be framed in the context of Condorcet consistent rules; this is important since in the current practice sometimes even the Borda count is used as a proxy for the Kemeny ranking. (2) To present a new exact algorithm, this identifies the Kemeny median ranking by providing a searching time guarantee. (3) To present a new heuristic algorithm identifying the Kemeny median ranking with an optimal trade-off between convergence and approximation.

AZZINI Ivano;  MUNDA Giuseppe; 

2020-01-10

ELSEVIER SCIENCE BV

JRC116021

0377-2217 (online),   

https://doi.org/10.1016/j.ejor.2019.08.033,    https://publications.jrc.ec.europa.eu/repository/handle/JRC116021,   

10.1016/j.ejor.2019.08.033 (online),