Answers are grounded in this paper and cite their sources.
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 <tex-math notation="LaTeX">m</tex-math> -sized subsets to accurately determine which items are the overall top- <tex-math notation="LaTeX">k</tex-math> items in a total of <tex-math notation="LaTeX">n</tex-math> 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 <tex-math notation="LaTeX">Δ ₖ</tex-math> between the <tex-math notation="LaTeX">k</tex-math> -th item and the <tex-math notation="LaTeX">$(k+1)$</tex-math> -th item. Specifically, we show that if <tex-math notation="LaTeX">Δ ₖ</tex-math> is greater than certain value, then the top- <tex-math notation="LaTeX">k</tex-math> items selected by the algorithm is asymptotically accurate almost surely; if <tex-math notation="LaTeX">Δ ₖ</tex-math> is below certain value, then the result will be inaccurate with a constant probability. In the special case of <tex-math notation="LaTeX">$m=2$</tex-math> , 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- <tex-math notation="LaTeX">k</tex-math> 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.
No takes yet. Share an insight, caveat, or question.
Chen et al. (2022) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: