2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | L.11.2 | ||
| Paper Title | On Top-k Selection from m-wise Partial Rankings via Borda Counting | ||
| Authors | Wenjing Chen, Ruida Zhou, Chao Tian, Texas A&M University, United States; Cong Shen, University of Virginia, United States | ||
| Session | L.11: Learning Theory II | ||
| Presentation | Lecture | ||
| Track | Statistics and Learning Theory | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | We analyze the performance of Borda counting algorithm on noisy $m$-wise ranking data to accurately select the top-$k$ items from a total of $n$ items. This generalizes a previous result of a similar nature reported by Shah et al. on the noisy pairwise comparison data. We show that the associated score separation $\Delta_k$ between the $k$-th item and the $(k+1)$-th item plays an important role: if $\Delta_k$ is greater than a threshold depending on $(n,k)$ and the scoring system in Borda counting, then the top-$k$ selection is accurate asymptotically almost surely; if $\Delta_k$ is below a threshold, then the top-$k$ selection will not be accurate with at least a constant probability. This separation between the two thresholds depends on $m$ and the scoring systems in the Borda counting procedure. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
