10
$\begingroup$

We know the solution of the Sultan's dowry problem: To reject the first $n/e$ candidates and then to select the first who exceeds the best of the sample. How to find the best strategy if we want select the 2, or 3, or $k$ best instead of only one?

  • 0
    Oh, but down there in the actual solution, Wikipedia then passes from the solution to an approximation thereof. And Mathworld seems sound here. If this understanding is correct, that feels dirty and I feel cheated that Wiki initially advertised theirs as exact. I've got to track down Masteller's book now; I'm dying (a little) (to know) (on the) inside.2016-05-11

3 Answers 3

10

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.

  • 0
    @Jean-Pierre: You're welcome. You asked an interesting question that I wanted to know the answers to as well, so I did some digging. :)2011-04-08
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).

0

For the general case, have a look at this article of Bruss and Paindaveine (2000)