The Postdoc Problem under the Mallows Model

The well-known secretary problem in sequential analysis and optimal stopping theory asks one to maximize the probability of finding the optimal candidate in a sequentially examined list under the constraint that accept/reject decisions are made in real-time. The problem is related to practical questions arising in online search, data streaming, daily purchase modeling and multi-arm bandit mechanisms. An extension is the postdoc problem, for which one aims to identify the second-best candidate with highest possible probability of success. We solve the postdoc problem for the nontraditional setting where the candidates are not presented uniformly at random but rather according to permutations drawn from the Mallows distribution. The optimal stopping criteria depend on the choice of the Mallows model parameter \theta: For \theta > 1 , we reject the first k^{\prime}(\theta) candidates and then accept the next left-to-right second-best candidate (second-best ranked when comparing with all appeared candidates). This coincides with the optimal strategy for the classical postdoc problem, where the rankings being drawn uniformly at random (\boldsymbol{i}.\boldsymbol{e}. \theta=1). For 0 < \theta\leqslant 1/2, we reject the first k^{\prime \prime}(\theta) candidates and then accept the next left-to-right best candidate; if no selection is made before the last candidate, then the last candidate is accepted. For 1/2 < \theta < 1 , we reject the first k_{1}(\theta) candidates and then accept the next left-to-right maximum, or reject the first k_{2}(\theta)\geqslant k_{1}(\theta) candidates and then accept the next left-to-right second-maximum, whichever comes first.