Kemeny-Young - Optimal rank aggregation minimising Kendall τ disagreement

Overview

Kemeny-Young finds the ranking σ* minimising total Kendall τ distance from all individual rankings (equivalently maximising the Kemeny score). It always elects the Condorcet winner if one exists. Computing the exact solution is NP-hard for large m - use branch-and-bound or genetic algorithm heuristics for m > 8.

Output

rank position, lower is better

Data

Crisp, complete rank

Size

2+ alternatives, 3-12 criteria works best

Used for

Rank aggregation, social choice, preference fusion

How it works

1. 1

   Collect K expert rankings R_k.

   $$\mathcal{R}=\{R_1,\dots ,R_K\}$$

   Kemeny 1959, p.585

2. 2

   Pairwise disagreement count d(σ,R_k) for each candidate consensus σ.

   $$d(\sigma ,R_k)=\#\{(i,l):{\sigma }_i<{\sigma }_l\text{but}{R}_{k,i}>R_{k,l}\}$$

   Kemeny 1959, p.586

3. 3

   Find σ* minimising total Kemeny distance Σ_k d(σ,R_k).

   $${\sigma }^{\ast }=\arg \underset{\sigma \in S_m}{\min }\sum _{k=1}^{K}d(\sigma ,R_k)$$

   Kemeny 1959, p.587 Eq.(2)

4. 4

   Kemeny consensus σ* is the final ranking.

   $$\text{ranking}={\sigma }^{\ast }$$

   Young-Levenglick 1978, p.288 Theorem 1

Fits when / Look elsewhere when

Assumptions to verify

• Input is a rank matrix (1=best, m=worst per voter)
• Each voter ranks all alternatives

Edge cases and pitfalls

• Kemeny-Young is NP-hard: exact computation feasible only for m ≤ 8 alternatives (8! = 40320 permutations). For larger m use heuristics (genetic algorithms, simulated annealing).

How to cite