OPTIMAL SELECTION OF THE k-TH BEST CANDIDATE
Yi-Shen Lin, Shoou-Ren Hsiau, Yi‐Ching Yao · Probability in the Engineering and Informational Sciences · 2019
In the subject of optimal stopping, the classical secretary problem is concerned with optimally selecting the best of n candidates when their relative ranks are observed sequentially. This problem has been extended to optimally selecting the kth best candidate for k ≥ 2. While the optimal stopping rule for k=1,2 (and all n ≥ 2) is known to be of threshold type (involving one threshold), we solve the case k=3 (and all n ≥ 3) by deriving an explicit optimal stopping rule that involves two thresholds. We also prove several inequalities for p(k, n), the maximum probability of selecting the k-th best of n candidates. It is shown that (i) p(1, n) = p(n, n) > p(k, n) for 1<k