Maxing and Ranking with Few Assumptions
Moein Falahatgar, Yi Hao, Alon Orlitsky, Venkatadheeraj Pichapati, Vaishakh Ravindrakumar
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.
BibTeX
@inproceedings{NIPS2017_db98dc0d,
author = {Falahatgar, Moein and Hao, Yi and Orlitsky, Alon and Pichapati, Venkatadheeraj and Ravindrakumar, Vaishakh},
booktitle = {Advances in Neural Information Processing Systems},
editor = {I. Guyon and U. Von Luxburg and S. Bengio and H. Wallach and R. Fergus and S. Vishwanathan and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Maxing and Ranking with Few Assumptions},
url = {https://proceedings.neurips.cc/paper_files/paper/2017/file/db98dc0dbafde48e8f74c0de001d35e4-Paper.pdf},
volume = {30},
year = {2017}
}