Skip to main content
Open Access Publications from the University of California

UC San Diego

UC San Diego Electronic Theses and Dissertations bannerUC San Diego

Maxing, Ranking and Preference Learning


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. We consider $(\epsilon,\delta)$-PAC

maxing and ranking using pairwise comparisons for \nobreak{general}

probabilistic models. We present a comprehensive understanding of

three important problems in PAC preference learning: maxing, ranking,

and estimating \emph{all} pairwise preference probabilities, in the

adaptive setting.

{\bf SST + STI:} We consider $(\epsilon,\delta)$-PAC maximum-selection

and ranking using pairwise comparisons for \nobreak{general}

probabilistic models whose comparison probabilities satisfy

\emph{strong stochastic transitivity (SST)} and \emph{stochastic

triangle inequality (STI)}. Modifying the popular knockout

tournament, we propose a simple maximum-selection algorithm that uses

$\mathcal{O}\left(\frac{n}{\epsilon^2} \log

\frac1{\delta}\right)$ comparisons, optimal up to a constant

factor. We then derive a general framework that uses noisy binary

search to speed up many ranking algorithms, and combine it with merge

sort to obtain a ranking algorithm that uses $\mathcal{O}\left(\frac

n{\epsilon^2}\log n(\log \log n)^3\right)$ comparisons for

$\delta=\frac1n$, optimal up to a $(\log \log n)^3$ factor.

{\bf SST +/- STI and Borda:} With just one simple natural assumption:

\emph{strong stochastic transitivity (SST)}, 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 $\cO(n\log n)$


{\bf General Transitive Models} With just \emph{Weak Stochastic

Transitivity (WST)}, we show that maxing requires $\Omega(n^2)$

comparisons and with slightly more restrictive \emph{Medium Stochastic

Transitivity (MST)}, we present a linear complexity maxing

algorithm. With \emph{Strong Stochastic Transitivity (SST)} and

\emph{Stochastic Triangle Inequality (STI)}, we derive a ranking

algorithm with optimal $\mathcal{O}(n\log n)$ complexity and an

optimal algorithm that estimates all pairwise preference


{\bf Sequential and Competitive} We extend the well-known

\emph{secretary problem} to a probabilistic setting, and apply the

intuition gained to derive the first query-optimal sequential

algorithm for probabilistic-maxing. Furthermore, departing from

previous assumptions, the algorithm and performance guarantees apply

even for infinitely many items, hence in particular do not require

a-priori knowledge of the number of items. The algorithm has linear

complexity, and is optimal also in the streaming setting and for both

traditional- and dueling-bandits. In a non-streaming setting, a

modification of the algorithm is \emph{competitive} in that it

requires essentially the lowest number of queries not just in the

worst case, but for every underlying distribution.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View