  Given partially observed pairwise comparison data generated by the
Bradley-Terry-Luce (BTL) model, we study the problem of top-$k$ ranking. That
is, to optimally identify the set of top-$k$ players. We derive the minimax
rate with respect to a normalized Hamming loss. This provides the first result
in the literature that characterizes the partial recovery error in terms of the
proportion of mistakes for top-$k$ ranking. We also derive the optimal signal
to noise ratio condition for the exact recovery of the top-$k$ set. The maximum
likelihood estimator (MLE) is shown to achieve both optimal partial recovery
and optimal exact recovery. On the other hand, we show another popular
algorithm, the spectral method, is in general sub-optimal. Our results
complement the recent work by Chen et al. (2019) that shows both the MLE and
the spectral method achieve the optimal sample complexity for exact recovery.
It turns out the leading constants of the sample complexity are different for
the two algorithms. Another contribution that may be of independent interest is
the analysis of the MLE without any penalty or regularization for the BTL
model. This closes an important gap between theory and practice in the
literature of ranking.
