Efficient Rank Aggregation via Lehmer Codes
This work addresses rank aggregation for applications like voting or recommendation systems, offering an efficient and parallelizable method, though it appears incremental as it builds on existing Lehmer code concepts.
The paper tackles the problem of rank aggregation by proposing a method that converts permutations into Lehmer codes, enabling decoupled coordinate aggregation via scalar median or mode computations. It proves that this approach recovers the correct centroid aggregate with small sample complexity under Mallows models and shows applicability to partial rankings.
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.