Technical Program

Paper Detail

Paper IDL.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

Visit Website!