Efficient Rank Aggregation via Lehmer Codes

Pan Li, Arya Mazumdar, Olgica Milenkovic
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:450-459, 2017.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v54-li17b, title = {{Efficient Rank Aggregation via Lehmer Codes}}, author = {Li, Pan and Mazumdar, Arya and Milenkovic, Olgica}, booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics}, pages = {450--459}, year = {2017}, editor = {Singh, Aarti and Zhu, Jerry}, volume = {54}, series = {Proceedings of Machine Learning Research}, month = {20--22 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v54/li17b/li17b.pdf}, url = {https://proceedings.mlr.press/v54/li17b.html}, 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. } }
Endnote
%0 Conference Paper %T Efficient Rank Aggregation via Lehmer Codes %A Pan Li %A Arya Mazumdar %A Olgica Milenkovic %B Proceedings of the 20th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2017 %E Aarti Singh %E Jerry Zhu %F pmlr-v54-li17b %I PMLR %P 450--459 %U https://proceedings.mlr.press/v54/li17b.html %V 54 %X 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.
APA
Li, P., Mazumdar, A. & Milenkovic, O.. (2017). Efficient Rank Aggregation via Lehmer Codes. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 54:450-459 Available from https://proceedings.mlr.press/v54/li17b.html.

Related Material