Name
Abstract | ||
|---|---|---|
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 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 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. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1109/TSP.2022.3167159 | IEEE TRANSACTIONS ON SIGNAL PROCESSING |
Keywords | DocType | Volume |
Borda count, M-wise comparison, ranking | Journal | 70 |
ISSN | Citations | PageRank |
1053-587X | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wenjing Chen | 1 | 0 | 0.68 |
| Ruida Zhou | 2 | 3 | 3.44 |
| Chao Tian | 3 | 39 | 4.46 |
| Shen Cong | 4 | 196 | 27.27 |