Competitive analysis of the top-K ranking problem
This work addresses a fundamental ranking problem with applications in recommender systems, web search, and crowdsourcing, offering a significant algorithmic improvement over prior methods.
The paper tackles the problem of identifying the top-K items from noisy pairwise comparisons under a general noise model, presenting a linear-time algorithm with a competitive ratio of Õ(√n), which is shown to be tight and improves upon previous algorithms with ratios of Ω̃(n) or worse.
Motivated by applications in recommender systems, web search, social choice and crowdsourcing, we consider the problem of identifying the set of top $K$ items from noisy pairwise comparisons. In our setting, we are non-actively given $r$ pairwise comparisons between each pair of $n$ items, where each comparison has noise constrained by a very general noise model called the strong stochastic transitivity (SST) model. We analyze the competitive ratio of algorithms for the top-$K$ problem. In particular, we present a linear time algorithm for the top-$K$ problem which has a competitive ratio of $\tilde{O}(\sqrt{n})$; i.e. to solve any instance of top-$K$, our algorithm needs at most $\tilde{O}(\sqrt{n})$ times as many samples needed as the best possible algorithm for that instance (in contrast, all previous known algorithms for the top-$K$ problem have competitive ratios of $\tildeΩ(n)$ or worse). We further show that this is tight: any algorithm for the top-$K$ problem has competitive ratio at least $\tildeΩ(\sqrt{n})$.