Data-driven Rank Breaking for Efficient Rank Aggregation

Abstract

Rank aggregation systems collect ordinal preferences from individuals to produce a global ranking that represents the social preference. Rank-breaking is a common practice to reduce the computational complexity of learning the global ranking. The individual preferences are broken into pairwise comparisons and applied to efficient algorithms tailored for independent paired comparisons. However, due to the ignored dependencies in the data, naive rank-breaking approaches can result in inconsistent estimates. The key idea to produce accurate and consistent estimates is to treat the pairwise comparisons unequally, depending on the topology of the collected data. In this paper, we provide the optimal rank-breaking estimator, which not only achieves consistency but also achieves the best error bound. This allows us to characterize the fundamental tradeoff between accuracy and complexity. Further, the analysis identifies how the accuracy depends on the spectral gap of a corresponding comparison graph.

46 pages, 12 figures

References in corpus (4)

• Simple, Robust and Optimal Ranking from Pairwise Comparisons
• Minimax-optimal Inference from Partial Rankings
• Collaboratively Learning Preferences from Ordinal Data
• Learning Mixed Membership Mallows Models from Pairwise Comparisons

Cited by in corpus (6)

• The Smoothed Possibility of Social Choice
• Fast and Robust Rank Aggregation against Model Misspecification
• From PAC to Instance-Optimal Sample Complexity in the Plackett-Luce Model
• Best-item Learning in Random Utility Models with Subset Choices
• Aggregating Incomplete and Noisy Rankings
• Accelerated MM Algorithms for Ranking Scores Inference from Comparison Data