Generalization of the Sultan's dowry problem

Solution 1:

This problem is also called (and may be better known as) the secretary problem.

The $k=2$ case was solved independently by Nikolaev ("On a generalisation of the best choice problem," Theory of Probability and Its Applications 22, 187-190, 1977) and Tamaki ("Recognizing both the maximum and the second maximum of a sequence," Journal of Applied Probability 16, 803-812, 1979). The optimal strategy is the following. Pass over the first $r^*_2-1$ candidates and then use the first choice to accept the next candidate that is the best seen thus far. After that, continue and use the second choice to accept the next candidate that is either 1) the best seen thus far, or 2) the second-best candidate that has been seen after $r^*_1-1$ candidates have been considered. Tamaki gives explicit values for $r^*_1$ and $r^*_2$ as well as the asymptotics $r^*_2/N \to d_2 \approx 0.2291$, where $x$ is the solution to $(1+x)e^{1/2} - \ln x = 7/2$, and $r^*_1/N \to d_1 = e^{-1/2} \approx 0.6065$. The asymptotic probability of selecting the best two is $d_2(2d_1-d_2) \approx 0.2254$.

The $k = 4$ case was apparently solved by Aarni Lehtinen in "Optimal Selection of the Four Best of a Sequence," Mathematical Methods of Operations Research 38, 309-315, 1993. I can't access the paper to see the optimal strategy, but I would assume the structure is similar to the $k=2$ case; one just needs to find the right values of the four $r^*$s. The abstract says the asymptotic probability of selecting the best four is approximately $0.12706$.

Lehtinen also appears to have solved the $k=5$ case and considered the general $k$ case in "Optimal Selection of the $k$ Best of a Sequence with $k$ Stops," Mathematical Methods of Operations Research 46, 251-261, 1997. Again, I can't access the paper, but the abstract says that the asymptotic probability of selecting the best five is approximately $0.104305$. The abstract also says about the case for general $k$, "Using [a] suboptimal solution, we find an approximation for the optimal probability values $P_k$ of the form $$P_k \approx \frac{1}{(e-1)k+1}."$$

It sounds like an exact solution for the general $k$ case is unknown. A search on "$k$-best secretary problem" seems to turn up some additional approximate solutions, although I haven't looked through them all.

Solution 2:

The asymptotic solution of getting one of the k best can be found in the paper "On an optimal stopping problem of Gusein-Zade"by A.Frank and S. Samuels in the journal Stochastic Processes and Applications, Vol. 10 (1980). Another highly recommended paper is T.P. Hill, "Knowing When to Stop: how to gamble if you must -the mathematics of optimal stopping", American Scientist, Vol. 97 (2009).