In statistics and game theory, the secretary problem (also known as the marriage problem, the optimal stopping problem, the sultan's dowry problem or the fussy suitor problem) is a puzzle involving being presented sequentially with a known number of items of varying quality. The puzzle is to select the best one from the items on offer; but rejecting an item is irrevocable. Because of the random element, the problem is often phrased in terms of maximizing the probability of choosing the best on offer.

The canonical example is an organization wishing to hire a secretary. Applicants present themselves sequentially; the interviewers may rank the applicants, and can remember the quality of everyone whom they have interviewed. The interviewers must accept or reject each applicant immediately after the interview, however. If an applicant is rejected, that person will find another job and become unavailable for hire. Other light-hearted instantiations include choosing a spouse from a series of suitors.

The problem stated above has a very simple optimal strategy: for some integer $r$ with

The problem as stated above has many variants, including:

1. The chooser may be allowed to choose two items rather than one
2. The number of applicants may be unknown
3. Ties in applicants may be significant
4. Rejectees may be recalled
5. The chooser may be satisfied with second best

Optimal $r$ derivation

There are two suitors which are relevant to the optimal strategy, one being the best suitor, which we shall label as a. The other one is the second best suitor in the interval ^*.

Given a: If , you would reject the best suitor and fail. If $a\; >\; r$, the strategy divides the suitors into three groups, (r,a and (a,n]. For the strategy to succeed, the second best suitor in the interval has to be in [1,r. The probability of that is $\backslash frac\{r\}\{a\}$. Therefore, the overall chance of success is $\backslash frac\{r\}\{a\}$ given that $a\; >\; r$.

In the large n limit, this becomes the integral over possible $a$ positions

$P(\backslash textrm\{success\})\; =\; \backslash frac\{1\}\{n\}\backslash sum\_\{a=r\}^n\; \backslash frac\{r\}\{a\}\; \backslash approx\; \backslash frac\{1\}\{n\}\backslash int\_r^n\; \backslash frac\{r\}\{a\}da\; =\; -\backslash frac\{r\}\{n\}\backslash log\backslash left(\backslash frac\{r\}\{n\}\backslash right)$

Take the derivative of the above expression to be zero and you'd find the optimum value of $\backslash frac\{r\}\{n\}\; =\; \backslash frac\{1\}\{e\}$.

References

• T. S. Ferguson. "Who solved the secretary problem?" Statistical science, volume 4, pp.282-296. 1989.

External links

Game theory

Sekretärinnenproblem | בעיית המזכירה | Problem sekretarki | 秘書問題