# On Top-k Selection from m-wise Partial Rankings via Borda Counting

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 25 references that are in the map.
- First posted on arXiv 11 Apr 2022.

## Builds on (most cited first, 4 of 4)

- [Simple, Robust and Optimal Ranking from Pairwise Comparisons](https://mlsanity.com/paper/1512.08949/) (2015)
- [Spectral MLE: Top-K Rank Aggregation from Pairwise Comparisons](https://mlsanity.com/paper/1504.07218/) (2015)
- [Minimax-optimal Inference from Partial Rankings](https://mlsanity.com/paper/1406.5638/) (2014)
- [Lower Bounds on the Bayes Risk of the Bayesian BTL Model with Applications to Comparison Graphs](https://mlsanity.com/paper/1709.09676/) (2017)

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

- [Efficient and Accurate Top-K Recovery from Choice Data](https://mlsanity.com/paper/2206.11995/) (2022)

## Abstract (arXiv)

We analyze the performance of the Borda counting algorithm in a non-parametric model. The algorithm needs to utilize probabilistic rankings of the items within m-sized subsets to accurately determine which items are the overall top-k items in a total of n items. The Borda counting algorithm simply counts the cumulative scores for each item from these partial ranking observations. This generalizes a previous work of a similar nature by Shah et al. using probabilistic pairwise comparison data. The performance of the Borda counting algorithm critically depends on the associated score separation Deltak between the k-th item and the (k+1)-th item. Specifically, we show that if Deltak is greater than certain value, then the top-k items selected by the algorithm is asymptotically accurate almost surely; if Deltak is below certain value, then the result will be inaccurate with a constant probability. In the special case of m=2, i.e., pairwise comparison, the resultant bound is tighter than that given by Shah et al., leading to a reduced gap between the error probability upper and lower bounds. These results are further extended to the approximate top-k selection setting. Numerical experiments demonstrate the effectiveness and accuracy of the Borda counting algorithm, compared with the spectral MLE-based algorithm, particularly when the data does not necessarily follow an assumed parametric model.