A generalized secretary problem

摘要

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.