A generalized secretary problem

Abba M. Krieger
Ester Samuel-Cahn

A new Secretary Problem is considered, where for fixed k and m one wins if at some time i = m(j .. 1) + 1 up to jm one
selects one of the j best items among the first jm items, j = 1,...,k. Selection is based on relative ranks only.
Interest lies in small k values, such as k = 2 or 3. This is compared with the classical rule, where one wins if one of
the k best among the n = km items is chosen. We prove that the win probability in the new formulation is always larger
than in the classical one. We also show, for k = 2 and 3 that one stops sooner in the new formulation. Numerical
comparisons are included.

July, 2014