of the submission. * originality: I enjoyed reading this paper. It introduces a new and interesting twist on the secretary problem, thereby providing a stylized theoretical version capturing the main essence of the task of ranking in many online settings. Some part of the analysis also provides some novel techniques that may be independently useful for other purpose (e.g. the new anti-concentration inequality). The proposed randomized algorithm is natural and somewhat unsurprising, but its analysis building upon connections to linear probing is interesting. * quality: By in-large the paper seems to be technically sound. I have gone through most proofs in detail, and although some would benefit with added clarity (see some examples below), I haven't found any main flaws. * clarity: The paper is in general well written, although there is room for some improvement. I list some examples below. * significance: In terms of significance, I believe that this work would be of interest to a small fraction of researchers within NIPS. In fact, in terms of fit, this looks like more a submission to be found within SODA. * other details/comments: - p.2, line 42: the optimal => an optimal \- p.4, line 155 to 159: this is a bit of a repeat, and somewhat ill-placed. Should appear before line 148 \- p.4, measure of sortedness: perhaps indicate whether there are other interesting measures one could consider (besides Kendall' tau and Spearman's footrule) \- p.5, line 192,1: $R$ should be defined (set of available rank); $r_1$ should be defined as 0 \- p.5, line 192,5: how are ties within the argmin dealt with? \- p.5, line 203: this equation is not numbered, but seems to be referred to as Eq. (3.2) later on; so it should be numbered. Same elsewhere where you have an equation which you want to refer to later on ... \- p.5, proof of Proposition 3.3: in the introduction of the event ${\cal O}_\sigma$ 5 lines above, it was for a permutation $\sigma$ on $t$ elements. Now in the proof, $\sigma$ is a permutation over $t-1$ elements. Which conditional event do we have in the conditional probability. By the way that formula indicates that the relative rank $r_t$ is {\em conditionally} uniformly distributed ... \- p.5, line 227: $t$-the should be $t^{th}$. Also what bound do you refer to at the end of the sentence? \- p.7, line 247: shouldn't we say: is popular at time $t$ w.p. at most $e^{-\Omega(\alpha)}$, that would help in the proof of Lemma 3.5, otherwise I don't see how the last equality in 263 can be true as the integral could be infinite? \- p.8, line 277: should $O(n\sqrt{n})$ be $\Omega(n\sqrt{n})$?
* significance: In terms of significance, I believe that this work would be of interest to a small fraction of researchers within NIPS. In fact, in terms of fit, this looks like more a submission to be found within SODA.