  We study a twist on the classic secretary problem, which we term the
secretary ranking problem: elements from an ordered set arrive in random order
and instead of picking the maximum element, the algorithm is asked to assign a
rank, or position, to each of the elements. The rank assigned is irrevocable
and is given knowing only the pairwise comparisons with elements previously
arrived. The goal is to minimize the distance of the rank produced to the true
rank of the elements measured by the Kendall-Tau distance, which corresponds to
the number of pairs that are inverted with respect to the true order.
  Our main result is a matching upper and lower bound for the secretary ranking
problem. We present an algorithm that ranks $n$ elements with only $O(n^{3/2})$
inversions in expectation, and show that any algorithm necessarily suffers
$\Omega(n^{3/2})$ inversions when there are $n$ available positions. In terms
of techniques, the analysis of our algorithm draws connections to linear
probing in the hashing literature, while our lower bound result relies on a
general anti-concentration bound for a generic balls and bins sampling process.
We also consider the case where the number of positions $m$ can be larger than
the number of secretaries $n$ and provide an improved bound by showing a
connection of this problem with random binary trees.
