Abstract: We present a comprehensive understanding of three important problemsin PAC preference learning: maximum selection (maxing), ranking, andestimating \emph{all} pairwise preference probabilities, in theadaptive setting. With just Weak Stochastic Transitivity, we show thatmaxing requires $\Omega(n^2)$ comparisons and with slightly morerestrictive Medium Stochastic Transitivity, we present a linearcomplexity maxing algorithm. With Strong Stochastic Transitivity andStochastic Triangle Inequality, we derive a ranking algorithm withoptimal $\mathcal{O}(n\log n)$ complexity and an optimal algorithmthat estimates all pairwise preference probabilities.