Skip to yearly menu bar Skip to main content


Poster

Maxing and Ranking with Few Assumptions

Moein Falahatgar · Yi Hao · Alon Orlitsky · Venkatadheeraj Pichapati · Vaishakh Ravindrakumar

Pacific Ballroom #40

Keywords: [ Online Learning ] [ Ranking and Preference Learning ]


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.

Live content is unavailable. Log in and register to view live content