Optimal full ranking from pairwise comparisons
By Pinhan Chen, Chao Gao, Anderson Y. Zhang. 2021
25 citations recorded by the source corpus.
We consider the problem of ranking n players from partial pairwise comparison data under the Bradley-Terry-Luce model. For the first time in the literature, the minimax rate of this ranking problem is derived with respect to the Kendall’s tau distance that measures the difference between two rank vectors by counting the number of inversions. The minimax rate of ranking exhibits a transition between an exponential rate and a polynomial rate depending on the magnitude of the signal-to-noise ratio of the problem. To the best of our knowledge, this phenomenon is unique to full ranking and has not been seen in any other statistical estimation problem. To achieve the minimax rate, we propose a divide-and-conquer ranking algorithm that first divides the n players into groups of similar skills and then computes local MLE within each group. The optimality of the proposed algorithm is established by a careful approximate independence argument between the two steps.
Subfields: Economics and Econometrics, Statistics and Probability, Information Retrieval & Search
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Economics and Econometrics
In Statistics and Probability
In Information Retrieval & Search
Citations in the corpus
- Generalized Results for the Existence and Consistency of the MLE in the Bradley-Terry-Luce Model (2021, methodology): “Recently, the minimax bound under the Erd¨os-R´enyi comparison graph was established by Chen et al. (2020a; 2019), and a decision-theroetic recovery of full ranking was suggested by Chen et al. (2020b).”