1010. Kemeny median rankings: Necessary conditions for optimality and algorithmic advances
Invited abstract in session MC-8: Preference Learning 2, stream Multiple Criteria Decision Aiding.
Monday, 12:30-14:00Room: Clarendon SR 2.08
Authors (first author is the speaker)
| 1. | Nicola Morandi
|
| Joint Research Center, European Commission | |
| 2. | Ivano Azzini
|
| Joint Research Center, European Commission | |
| 3. | Giuseppe Munda
|
| Joint Research Center, European Commission |
Abstract
Let N and M be two integer numbers greater than or equal to 3. In a setting characterized by N alternatives and M rankings, i.e., permutations of (1, 2, ..., N), the Kemeny median ranking problem (KMRP) seeks to find all rankings that minimize the total Kemeny-Snell distance from the input set of rankings. This distance serves as a proxy for total disagreement with the input rankings, enabling applications in fields such as recommendation systems, genetics, air traffic control, defense decision support, and voting theory. Although approximable within a constant in polynomial time, the KMRP is NP-hard and challenging to solve, with current exact algorithms capable of consistently solving instances with N up to 14. We tackle the KMRP by reformulating it using antisymmetric matrices, and by identifying necessary conditions for optimal rankings. We then devise a branch-and-bound algorithm that incorporates these conditions as pruning rules. Our method solves instances with N up to 30 in one hour of computations and does not rely on commercial solvers, aligning with typical licensing and transparency requirement for institutional use.
Keywords
- Decision Theory
- Algorithms
Status: accepted
Back to the list of papers