Secretary problem

In statistics , game theory, and decision theory , the secretary's problem (also known as the marriage problem , but not to be confused with the problem on which the marriage rate is based) describes the task of choosing the best candidate from a number of individually examined applicants one after the other. A rejection is irrevocable. Because of the random elements it contains, the problem is usually formulated in such a way that the greatest probability of selecting the best offer can be determined. A solution algorithm for this problem is given by the odds strategy .

The solution to the problem is known as the 37 percent rule (or rule). It was described by Geoffrey Miller in his book The Mating Mind . It says that you look at the first 37 percent (more precisely: percent) of the applicants and then accept the first applicant who is better than all previous ones (i.e. the optimum found so far). This simple rule should not be confused with the 1 / e law of best choice (see below), which applies in an extended model with an unknown number of candidates. ${\ displaystyle 1 / e}$ ${\ displaystyle \ textstyle 1 / e \ cdot 100}$ ${\ displaystyle 1 / e}$

Failure of the procedure

The probability of finding the best applicant is 37%, which means that in almost 2/3 of the cases you will not find the best applicant. This happens when the best applicant was already in the top 37%. In this case, the last candidate, which happens to be the last, is taken. If the applicants are sorted in descending order of quality, the procedure means that the absolutely worst applicant has to be taken. The process is also not very successful if the first 37% of applicants were the worst. In this case, the next best is accepted.

problem

In a variant often cited as an example, an organization wants to hire a secretary . The applicants speak one after the other; A ranking can be established in the assessment and the qualities of each applicant can be recorded. However, a rejected applicant is finally eliminated and is no longer available in the further course, a premise that contradicts the actual reality of staffing.

Another formulation of the problem assumes the choice of a spouse from among a number of candidates . The problem also implies that the probability of selecting the best candidate in each case should be maximized. If instead the expected value is to be maximized in relation to all possible candidates, a different strategy would be necessary.

example

There are three applicants who apply in random order. For their observed qualities 1, 2, 3 (where 1 is the worst applicant and 3 is the best) there is then 6 = 3! equally probable possibilities: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1) . If the first applicant were to simply get the job, the probability of hiring the best one would be the same , namely in cases (3,1,2) and (3,2,1). ${\ displaystyle {\ tfrac {2} {6}} = {\ tfrac {1} {3}}}$

The following strategy is more clever: the first applicant is rejected. If the second is better than the first, the second is discontinued, otherwise the third. With this strategy you get the best applicant in cases (1,3,2), (2,3,1) and (2,1,3), i.e. in 3 out of 6 cases. The probability is thus . ${\ displaystyle {\ tfrac {3} {6}} = {\ tfrac {1} {2}}}$

In general, it can also be shown that the best strategy is to first reject a certain number of applicants and then hire the first one who is better than the rejected one. It is to be optimized depending on so that the probability of hiring the best applicant in this way is maximized. ${\ displaystyle r}$ ${\ displaystyle n}$ ${\ displaystyle r}$ ${\ displaystyle r}$ ${\ displaystyle n}$

strategy

The problem has a very simple strategy that is also optimal :

Consider the first of the candidates (with ) - and reject them. ${\ displaystyle r}$ ${\ displaystyle n}$ ${\ displaystyle 1 \ leq r <n}$

From the remaining applicants, choose the first one who is better than any of the first . ${\ displaystyle no}$ ${\ displaystyle r}$

It can be shown that for large the optimal value for results from , where the base is the natural logarithm ( Euler's number ). With this strategy, the probability of choosing the best candidate is around 37%. ${\ displaystyle n}$ ${\ displaystyle r}$ ${\ displaystyle r \ approx n / e}$ ${\ displaystyle e}$ ${\ displaystyle 1 / e}$

proof

Probabilities P in the case of n = 12 applicants. The optimal number of initially rejected applicants is r = 4 with P ≈ 0.3955

The best candidate can only win the election if he is not among the first test candidates. If he is placed immediately afterwards , he wins. The probability that he is in this place is . If he is one place further on place - again with the probability - he wins exactly when the best of the previous candidates is among the first trial candidates. That is the case with the probability , put together it gives the probability . ${\ displaystyle r}$ ${\ displaystyle r + 1}$ ${\ displaystyle {\ frac {1} {n}}}$ ${\ displaystyle r + 2}$ ${\ displaystyle {\ frac {1} {n}}}$ ${\ displaystyle r}$ ${\ displaystyle {\ frac {r} {r + 1}}}$ ${\ displaystyle {\ frac {1} {n}} \ cdot {\ frac {r} {r + 1}}}$

If one goes through the cases accordingly up to the last position for the best, the probability for this position and for the probability that the best predecessor was one of the first test candidates is obtained again , that is , together . ${\ displaystyle {\ frac {1} {n}}}$ ${\ displaystyle r}$ ${\ displaystyle {\ frac {r} {r + nr-1}} = {\ frac {r} {n-1}}}$ ${\ displaystyle {\ frac {1} {n}} \ cdot {\ frac {r} {n-1}}}$

Overall, the probability of the strategy being successful is: ${\ displaystyle P}$

{\ displaystyle P = \ sum _ {a = r + 1} ^ {n} {\ frac {1} {n}} \ cdot {\ frac {r} {a-1}} = {\ frac {r} {n}} \ sum _ {a = r} ^ {n-1} {\ frac {1} {a}}}

The integral approximation , which gets better and better with increasing, is used for the sum : ${\ displaystyle n}$

{\ displaystyle P \ approx {\ frac {r} {n}} \ int _ {r} ^ {n} {\ frac {1} {a}} da = - {\ frac {r} {n}} \ ln {\ frac {r} {n}}}

This approximate expression assumes the maximum where its derivative is equal to 0, namely at the point ; it amounts to . The maximum is not very high: for the wide range is in fact consistently never reached. A more accurate analysis based on the odds strategy (Bruss 2003) shows more, namely that the probability of success is always strictly greater than 1 / e = 0.3678 ..., i.e. always strictly greater than the asymptotic probability of success if the number of Applicants striving towards infinity. ${\ displaystyle r = {\ tfrac {n} {e}}}$ ${\ displaystyle {\ tfrac {1} {e}} \ approx 0 {,} 368}$ ${\ displaystyle {\ tfrac {n} {4}} \ leq r \ leq {\ tfrac {n} {2}}}$ ${\ displaystyle {\ tfrac {\ ln 2} {2}} \ approx 0 {,} 346}$

If the second-best is included in the above strategy, the probability that this will be selected approaches the value for large . Overall, the probability that this strategy will result in the best or second-best candidate is slightly greater than 50% for large ones. ${\ displaystyle n}$ ${\ displaystyle 1 / e ^ {2}}$ ${\ displaystyle n}$

Generalizations and Variants

Unknown number N of options

The main disadvantage of the classic secretary problem for possible applications is the fact that the number of options (candidates) is assumed to be known in advance. One way to get around this is to assume that the distribution of this number is known (Presman and Sonin, 1972). However, in this model it is generally more difficult to determine the optimal solution. In addition, the optimum probability of winning is often much smaller. It is intuitively clear that ignorance of the number N of options should come at a price, but this price is often very high. In fact, in some cases, the optimal winning probability becomes practically zero. A clever reformulation of this model solves this problem. ${\ displaystyle N}$ ${\ displaystyle P (N = k) _ {k = 1,2, \ cdots}}$

1 / e law of best choice

The essence of the reformulated model (the so-called generalized approach in continuous time) is based on the idea that it is easier to estimate when candidates are more or less likely to come (under the hypothesis that they will come) than to estimate the distribution of the number itself.

The generalized model: A candidate is to be selected from an unknown number of candidates in the time interval . The aim is to maximize the likelihood of choosing the best candidate if the arrival orders of different ranks are equally likely. It is believed that all ranks are independently the same arrival time density to have. Let be the corresponding arrival time distribution, i.e. H. ${\ displaystyle [0, T]}$ ${\ displaystyle N}$ ${\ displaystyle f}$ ${\ displaystyle [0, T]}$ ${\ displaystyle F}$

{\ displaystyle F (t) = \ int _ {0} ^ {t} f (s) \, \ mathrm {d} s}

, .

{\ displaystyle \, 0 \ leq t \ leq T}

The 1 / e law (Bruss 1984) then says: Let the solution of the equation be. Furthermore, let S be the strategy of waiting for all candidates until the time and then, if possible, to select the first candidate who is better than all predecessors before the time . ${\ displaystyle \ tau}$ ${\ displaystyle F (\ tau) = 1 / e.}$ ${\ displaystyle \ tau}$ ${\ displaystyle \ tau}$

This so-called 1 / e strategy S has the following properties:

If there is at least one candidate, then

(i) S achieves a winning probability of at least 1 / e for all ;

{\ displaystyle N}

(ii) S is the only strategy that can achieve this lower bound 1 / e, and this lower bound is sharp;

(iii) S does not choose a candidate with probability 1 / e (exactly).

The 1 / e law was received with surprise (see Math. Reviews 85: m), because a winning probability of 1 / e did not seem to be feasible for an unknown number of candidates , whereas this value is now the lower bound, and even so in a model with recognized weaker hypotheses. The 1 / e law is often confused with the solution to the secretary's problem, because 1 / e also plays an important role there. Note, however, that the 1 / e law goes much further, as it applies to an unknown number of candidates on the one hand and also arises from a user-friendly model in continuous time. ${\ displaystyle N}$

Further variants of the classic model

The problem has been studied in many different ways, including:

Two candidates may be chosen (instead of just one).
The number of applicants is unknown.
Equal candidates matter.
Rejected applicants have not been permanently eliminated.
The second best applicant can also be chosen.

literature

Eugene Dynkin : Optimal Choice of the Stopping Time of a Markov Process . In: Sov. Math. Dokl. No. 02 , 1963, p. 238-240 .

Franz Thomas Bruss : Sum the Odds to One and Stop . In: Annals of Probability . tape 28 , no. 03 , 2000, p. 1384-1391 .

Franz Thomas Bruss : A Note on Bounds for the Odds Theorem of Optimal Stopping . In: Annals of Probability . tape 31 , no. 04 , 2003, p. 1859-1861 .

Franz Thomas Bruss : A Unified Approach to a Class of Best Choice Problems with an Unknown Number of Options . In: Annals of Probability . tape 12 , no. 3 , 1984, pp. 882-889 .

Franz Thomas Bruss : Strategies of the best choice . In: Spectrum of Science . No. 05 , 2004, p. 102-104 ( Spektrum.de ).

Stephen M. Samuels: A Best-Choice Problem with Linear Travel Cost . In: Journal of the American Statistical Association . tape 80 , no. 390 , 1985, pp. 461-464 , doi : 10.1080 / 01621459.1985.10478141 .

Eric W. Weisstein: Sultan's Dowry Problem . In: MathWorld . Wolfram, 2004 ( mathworld.wolfram.com [accessed February 24, 2007]).

Web links

Mathematics online: secretary problem
Read admirers or the "secretary problem" (PDF; 120 kB)