A generalized secretary problem. Issue 2 (2nd April 2016) - Krieger, Abba; Samuel-Cahn, Ester
ABSTRACT: 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 a classical problem, 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.