Maximum Selection and Ranking under Noisy Comparisons
This work addresses efficient algorithms for ranking and selection in noisy environments, with applications in areas like recommendation systems, but it is incremental as it builds on existing knockout tournament methods.
The paper tackles the problem of selecting the best item and ranking items under noisy comparisons, proposing a maximum-selection algorithm with O(n/ε² log(1/δ)) comparisons, which is tight up to a constant factor, and a ranking algorithm with O(n log n (log log n)³/ε²) comparisons, optimal up to a (log log n)³ factor.
We consider $(ε,δ)$-PAC maximum-selection and ranking for general probabilistic models whose comparisons probabilities satisfy strong stochastic transitivity and stochastic triangle inequality. Modifying the popular knockout tournament, we propose a maximum-selection algorithm that uses $\mathcal{O}\left(\frac{n}{ε^2}\log \frac{1}δ\right)$ comparisons, a number tight up to a constant factor. We then derive a general framework that improves the performance of many ranking algorithms, and combine it with merge sort and binary search to obtain a ranking algorithm that uses $\mathcal{O}\left(\frac{n\log n (\log \log n)^3}{ε^2}\right)$ comparisons for any $δ\ge\frac1n$, a number optimal up to a $(\log \log n)^3$ factor.