Rank aggregation basics: Local Kemeny optimisation

rank-aggregationvotingkemenysocial-choicealgorithms

Abstraction: Local Kemeny optimisation as tractable rank aggregation via adjacent swaps

Key points:

Condorcet's paradox: with >2 items majority voting can cycle (A<B, B<C, C<A), making global majority ordering impossible
Kemeny score K(r) counts pairwise disagreements between aggregate ranking r and all voter rankings; minimising it is NP-hard even with 4 votes
Locally Kemeny optimal: no adjacent swap decreases K; still satisfies the generalised Condorcet criterion
Local Kemenization computed via insertion sort in O(n²); can reach O(n log n) via Hamiltonian path on majority-vote directed graph
The unique locally optimal solution is consistent with its starting point, enabling heuristic-guided initialisation
Based on Dwork, Kumar, Naor, Sivakumar "Rank Aggregation Methods for the Web" (WWW 2001)

Connections: David Maciver · Rank Aggregation · Kemeny Optimisation · Social Choice Theory · Condorcet Paradox