Maxing and Ranking with Few Assumptions
Abstract
PAC maximum selection (maxing) and ranking of $n$ elements via random pairwise comparisons have diverse applications and have been studied under many models and assumptions. With just one simple natural assumption: strong stochastic transitivity, we show that maxing can be performed with linearly many comparisons yet ranking requires quadratically many. With no assumptions at all, we show that for the Borda-score metric, maximum selection can be performed with linearly many comparisons and ranking can be performed with $\mathcal{O}(n\log n)$ comparisons.
Cite
Text
Falahatgar et al. "Maxing and Ranking with Few Assumptions." Neural Information Processing Systems, 2017.Markdown
[Falahatgar et al. "Maxing and Ranking with Few Assumptions." Neural Information Processing Systems, 2017.](https://mlanthology.org/neurips/2017/falahatgar2017neurips-maxing/)BibTeX
@inproceedings{falahatgar2017neurips-maxing,
title = {{Maxing and Ranking with Few Assumptions}},
author = {Falahatgar, Moein and Hao, Yi and Orlitsky, Alon and Pichapati, Venkatadheeraj and Ravindrakumar, Vaishakh},
booktitle = {Neural Information Processing Systems},
year = {2017},
pages = {7060-7070},
url = {https://mlanthology.org/neurips/2017/falahatgar2017neurips-maxing/}
}