Abstract

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 - Jan 1 2017
Event20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017 - Fort Lauderdale, United States
Duration: Apr 20 2017Apr 22 2017

Conference

Conference20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017
CountryUnited States
CityFort Lauderdale
Period4/20/174/22/17

Fingerprint

Rank Aggregation
Permutation
Agglomeration
Aggregation
Performance Guarantee
Centroid
Decoupling
Small Sample
Ranking
Inversion
Scalar
Partial
Simulation
Model

ASJC Scopus subject areas

  • Artificial Intelligence
  • Statistics and Probability

Cite this

Li, P., Mazumdar, A., & Milenkovic, O. (2017). Efficient rank aggregation via Lehmer codes. Paper presented at 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, Fort Lauderdale, United States.

Efficient rank aggregation via Lehmer codes. / Li, Pan; Mazumdar, Arya; Milenkovic, Olgica.

2017. Paper presented at 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, Fort Lauderdale, United States.

Research output: Contribution to conferencePaper

Li, P, Mazumdar, A & Milenkovic, O 2017, 'Efficient rank aggregation via Lehmer codes' Paper presented at 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, Fort Lauderdale, United States, 4/20/17 - 4/22/17, .
Li P, Mazumdar A, Milenkovic O. Efficient rank aggregation via Lehmer codes. 2017. Paper presented at 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, Fort Lauderdale, United States.
Li, Pan ; Mazumdar, Arya ; Milenkovic, Olgica. / Efficient rank aggregation via Lehmer codes. Paper presented at 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, Fort Lauderdale, United States.
@conference{06a28723ef854299bd078b24d32c5207,
title = "Efficient rank aggregation via Lehmer codes",
abstract = "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.",
author = "Pan Li and Arya Mazumdar and Olgica Milenkovic",
year = "2017",
month = "1",
day = "1",
language = "English (US)",
note = "20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017 ; Conference date: 20-04-2017 Through 22-04-2017",

}

TY - CONF

T1 - Efficient rank aggregation via Lehmer codes

AU - Li, Pan

AU - Mazumdar, Arya

AU - Milenkovic, Olgica

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85067584619&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85067584619&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:85067584619

ER -