Optimal Full Ranking from Pairwise Comparisons

摘要: We consider the problem of ranking $n$ players from partial pairwise comparison data under Bradley-Terry-Luce model. For first time in literature, minimax rate this is derived with respect to Kendall's tau distance that measures difference between two rank vectors by counting number inversions. The exhibits a transition an exponential and polynomial depending on magnitude signal-to-noise ratio problem. To best our knowledge, phenomenon unique full has not been seen any other statistical estimation achieve rate, we propose divide-and-conquer algorithm divides into groups similar skills then computes local MLE within each group. optimality proposed established careful approximate independence argument steps.