On Sample Complexity Upper and Lower Bounds for Exact Ranking from Noisy Comparisons

Wenbo Ren, Jia Liu, Ness B. Shroff

This paper studies the problem of finding the exact ranking from noisy comparisons. A comparison over a set of $m$ items produces a noisy outcome about the most preferred item, and…