Maxing and Ranking with Few Assumptions
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 O(n log n) comparisons.
Thanks for the rebuttal, which was quite helpful and clarified most of the issues raised in the review. 
The authors study the problem of PAC maximum selection (maxing) and ranking of n elements via random pairwise comparisons. Problems of that kind have recently attracted attention in the ML literature, especially in the setting of dueling bandidts. In this paper, the only assumption made is strong stochastic transitivity of the pairwise winning probabilisties. Under this assumption, the authors show that maxing can be performed with linearly many comparisons while ranking has a quadratic sample complexity. Further, for the so-called Borda ranking, maximum selection and ranking can be performed with O(n) and O(n log n) comparisons, respectively. 
The paper addresses an interesting topic and is well written. That being said, I'm not convinced that is offers significant new results. It's true that I haven't seen the first two results in exactly this form before, but there are very similar ones, and besides, the results are not very surprising. Further, the argument for the result regarding the non-existence of a PAC ranking algorithm with O(n log n) comparisons in the SST setting is not totally clear. 
More importantly, the last two results are already known. Theorem 8 this known as Borda reduction, see e.g., Sparse Dueling Bandits, Generic exploration and k-armed voting bandits, Relative upper confidence bound for the k-armed duelling bandit problem. Likewise, Theorem 9 is already known, see e.g., Crowdsourcing for Participatory Democracies, Efficient elicitation of social choice functions.
Consequently, the only result that remains, being both novel and relevant, is the PAC maxing algorithm and its analysis. Nevertheless, a study of its performance on real data is missing, as well as a comparison with other algorithms.              
Indeed, the experiments are not very convincing, especially because only a simple synthetic setting is considered, and no experiments for (Borda) ranking are included. SEQ-ELIMINATE is a subroutine of OPT-MAXIMIZE, so does it really makes sense to compare the two? It would be rather more meaningful to compare one of the two with other maxing algorithms in the main paper and move their comparison, if necessary, to the appendix. Lines 189-299: models with other parameters should be considered. In all maxing experiments, it should be tested whether the found element is the actual maxima. 
			  
Minor issues:
- 51: an \epsilon-ranking (and not \epsilon-rankings)
- 100: comparisons (and not comparison)
- 117-118: Please reconsider the statement: "the number of comparisons used by SEQ-ELIMINATE is optimal up to a constant factor when \delta <= 1/n".  \delta <= 1/n => n <= 1/\delta => O(n/\epsilon^2 \log(n/\delta)) = O(n/\epsilon^2 \log(1/\delta^2)) != \Omega(n/\epsilon^2 \log(1/\delta)) 
- 117-118: Please reconsider the statement: "but can be \log n times the lower bound for constant \delta", since n/\epsilon^2 \log(1/\delta) \times \log(n) != n/\epsilon^2 \log(n/\delta).
- 120-122: It is not clear how should such a reduction together with the usage of SEQ-ELIMINATE lead to an optimal sample complexity up to constants. PLease elaborate.
- 130-131: "replacing or retaining r doesn’t affect the performance of SEQ-ELIMINATE". The performance in terms of what? And why there is no effect?
- 165: same comment as for 117-118
- 167: in 120 it was stated that S' should have a size of O(n/\log n), and here It's O(\sqrt(n\log n))
- 165-169: The procedure described here (the reduction + usage of SEQ-ELIMINATE) is different from the one described in 120-122. And again, it's not clear how should such a procedure results in an order-wise optimal algorithm.
- 204: Lemma 12 does not exist.
- 207: Lemma 11 does not exist.
- 210: at least (and not atleast)  
- 215: \delta is missing in the arguments list of PRUNE
- 221-222: same comment as for 165 and 117-118
- 238-239: The sample complexity is not apparent in both cases (distinguished in algorithm 2)