On Top-$k$ Selection From $m$-Wise Partial Rankings via Borda Counting
Wenjing Chen, Ruida Zhou, Chao Tian, Cong Shen · IEEE Transactions on Signal Processing · 2022
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 Shahet al.using probabilistic pairwise comparison data. The performance of the Borda counting algorithm critically depends on the associated score separation$\Delta _{k}$between the$k$-th item and the$(k+1)$-th item. Specifically, we show that if$\Delta _{k}$is greater than certain value, then the top-$k$items selected by the algorithm is asymptotically accurate almost surely; if$\Delta _{k}$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 Shahet 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.