Accurate algorithms for identifying the median ranking when dealing with weak and partial rankings under the Kemeny axiomatic approach

• DOI: 10.1016/j.ejor.2015.08.048
• Publication Date: 2015-09-08T20:46:58Z
• Authors: S. Amodio; A. D’Ambrosio; R. Siciliano
• Keywords: Aggregation problem

Preference rankings virtually appear in all field of science (political sciences, behavioral sciences, machine learning, decision making and so on). The well-know social choice problem consists in trying to find a reasonable procedure to use the aggregate preferences expressed by subjects (usually called judges) to reach a collective decision. This problem turns out to be equivalent to the problem of estimating the consensus (central) ranking from data that is known to be a NP-hard Problem. Emond and Mason in 2002 proposed a branch and bound algorithm to calculate the consensus ranking given $n$ rankings expressed on $m$ objects. Depending on the complexity of the problem, there can be multiple solutions and then the consensus ranking may be not unique. We propose a new algorithm to find the consensus ranking that is equivalent to Emond and Mason's algorithm in terms of at least one of the solutions reached, but permits a really remarkable saving in computational time.