Efficient rank aggregation via Lehmer codes

Pan Li, Arya Mazumdar, Olgica Milenkovic

Research output: Contribution to conferencePaperpeer-review


We propose a novel rank aggregation method based on converting permutations into their corresponding Lehmer codes or other subdiagonal images. Lehmer codes, also known as inversion vectors, are vector representations of permutations in which each coordinate can take values not restricted by the values of other coordinates. This transformation allows for decoupling of the coordinates and for performing aggregation via simple scalar median or mode computations. We present simulation results illustrating the performance of this completely parallelizable approach and analytically prove that both the mode and median aggregation procedure recover the correct centroid aggregate with small sample complexity when the permutations are drawn according to the well-known Mallows models. The proposed Lehmer code approach may also be used on partial rankings, with similar performance guarantees.

Original languageEnglish (US)
StatePublished - 2017
Event20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017 - Fort Lauderdale, United States
Duration: Apr 20 2017Apr 22 2017


Conference20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017
Country/TerritoryUnited States
CityFort Lauderdale

ASJC Scopus subject areas

  • Artificial Intelligence
  • Statistics and Probability


Dive into the research topics of 'Efficient rank aggregation via Lehmer codes'. Together they form a unique fingerprint.

Cite this