# Minimax-optimal Inference from Partial Rankings

arXiv: https://arxiv.org/abs/1406.5638 · HTML: https://mlsanity.com/paper/1406.5638/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jun 2014.

## Built on by (most cited first, 24 of 24)

- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Conformal prediction under ambiguous ground truth](https://mlsanity.com/paper/2307.09302/) (2023)
- [Uncertainty Quantification of MLE for Entity Ranking with Covariates](https://mlsanity.com/paper/2212.09961/) (2022)
- [FisherSFT: Data-Efficient Supervised Fine-Tuning of Language Models Using Information Gain](https://mlsanity.com/paper/2505.14826/) (2025)
- [Spectral Ranking Inferences based on General Multiway Comparisons](https://mlsanity.com/paper/2308.02918/) (2023)
- [ℓ∞-Bounds of the MLE in the BTL Model under General Comparison Graphs](https://mlsanity.com/paper/2110.10825/) (2021)
- [Learning Rich Rankings](https://mlsanity.com/paper/2312.15081/) (2023)
- [Dueling Convex Optimization with General Preferences](https://mlsanity.com/paper/2210.02562/) (2022)
- [Perfect Sampling from Pairwise Comparisons](https://mlsanity.com/paper/2211.12868/) (2022)
- [On Sinkhorn's Algorithm and Choice Modeling](https://mlsanity.com/paper/2310.00260/) (2023)
- [Efficient and Accurate Learning of Mixtures of Plackett-Luce Models](https://mlsanity.com/paper/2302.05343/) (2023)
- [Top-K ranking with a monotone adversary](https://mlsanity.com/paper/2402.07445/) (2024)
- [Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective](https://mlsanity.com/paper/2501.18282/) (2025)
- [What Does Preference Learning Recover from Pairwise Comparison Data?](https://mlsanity.com/paper/2602.10286/) (2026)
- [On the Sample Complexity of Rank Regression from Pairwise Comparisons](https://mlsanity.com/paper/2105.01463/) (2021)
- [On Top-k Selection from m-wise Partial Rankings via Borda Counting](https://mlsanity.com/paper/2204.05742/) (2022)
- [An Analysis of Elo Rating Systems via Markov Chains](https://mlsanity.com/paper/2406.05869/) (2024)
- [Learning Parametric Distributions from Samples and Preferences](https://mlsanity.com/paper/2505.23557/) (2025)
- [Path Planning using Reinforcement Learning: A Policy Iteration Approach](https://mlsanity.com/paper/2303.07535/) (2023)
- [Random pairing MLE for estimation of item parameters in Rasch model](https://mlsanity.com/paper/2406.13989/) (2024)
- [Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queries](https://mlsanity.com/paper/2606.08410/) (2026)
- [Optimal Top-k Identification from Pairwise Comparisons](https://mlsanity.com/paper/2607.08979/) (2026)
- [AI-Mediation in Retail Markets: Revenue Effects and Assortment Optimization](https://mlsanity.com/paper/2610.12917/) (2026)
- [Learning Distributions from Samples and Qualities](https://mlsanity.com/paper/2610.17956/) (2026)

## Abstract (arXiv)

This paper studies the problem of inferring a global preference based on the partial rankings provided by many users over different subsets of items according to the Plackett-Luce model. A question of particular interest is how to optimally assign items to users for ranking and how many item assignments are needed to achieve a target estimation error. For a given assignment of items to users, we first derive an oracle lower bound of the estimation error that holds even for the more general Thurstone models. Then we show that the Cram'er-Rao lower bound and our upper bounds inversely depend on the spectral gap of the Laplacian of an appropriately defined comparison graph. When the system is allowed to choose the item assignment, we propose a random assignment scheme. Our oracle lower bound and upper bounds imply that it is minimax-optimal up to a logarithmic factor among all assignment schemes and the lower bound can be achieved by the maximum likelihood estimator as well as popular rank-breaking schemes that decompose partial rankings into pairwise comparisons. The numerical experiments corroborate our theoretical findings.