![secretary_problem_graphs](https://upload.wikimedia.org/wikipedia/commons/c/c4/Secretary_problem_graphs.svg)
The secretary problem demonstrates a scenario involving
optimal stopping
In mathematics, the theory of optimal stopping or early stopping
: (For French translation, secover storyin the July issue of ''Pour la Science'' (2009).) is concerned with the problem of choosing a time to take a particular action, in order to ...
theory
[ For French translation, se]
cover story
in the July issue of ''Pour la Science'' (2009). that is studied extensively in the fields of
applied probability
Applied probability is the application of probability theory to statistical problems and other scientific and engineering domains.
Scope
Much research involving probability is done under the auspices of applied probability. However, while such res ...
,
statistics
Statistics (from German language, German: ''wikt:Statistik#German, Statistik'', "description of a State (polity), state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of ...
, and
decision theory
Decision theory (or the theory of choice; not to be confused with choice theory) is a branch of applied probability theory concerned with the theory of making decisions based on assigning probabilities to various factors and assigning numerical ...
. It is also known as the marriage problem, the sultan's dowry problem, the fussy suitor problem, the googol game, and the best choice problem.
The basic form of the problem is the following: imagine an administrator who wants to hire the best secretary out of
rankable applicants for a position. The applicants are interviewed one by one in random order. A decision about each particular applicant is to be made immediately after the interview. Once rejected, an applicant cannot be recalled. During the interview, the administrator gains information sufficient to rank the applicant among all applicants interviewed so far, but is unaware of the quality of yet unseen applicants. The question is about the optimal strategy (
stopping rule) to maximize the probability of selecting the best applicant. If the decision can be deferred to the end, this can be solved by the simple maximum
selection algorithm
In computer science, a selection algorithm is an algorithm for finding the ''k''th smallest number in a list or array; such a number is called the ''k''th ''order statistic''. This includes the cases of finding the minimum, maximum, and median e ...
of tracking the running maximum (and who achieved it), and selecting the overall maximum at the end. The difficulty is that the decision must be made immediately.
The shortest rigorous proof known so far is provided by the
odds algorithm The odds algorithm (or Bruss algorithm) is a mathematical method for computing optimal strategies for a class of problems that belong to the domain of optimal stopping problems. Their solution follows from the ''odds strategy'', and the importance ...
. It implies that the optimal win probability is always at least
(where ''
e'' is the base of the
natural logarithm
The natural logarithm of a number is its logarithm to the base of the mathematical constant , which is an irrational and transcendental number approximately equal to . The natural logarithm of is generally written as , , or sometimes, if ...
), and that the latter holds even in a much greater generality. The optimal stopping rule prescribes always rejecting the first
applicants that are interviewed and then stopping at the first applicant who is better than every applicant interviewed so far (or continuing to the last applicant if this never occurs). Sometimes this strategy is called the
stopping rule, because the probability of stopping at the best applicant with this strategy is about
already for moderate values of
. One reason why the secretary problem has received so much attention is that the optimal policy for the problem (the stopping rule) is simple and selects the single best candidate about 37% of the time, irrespective of whether there are 100 or 100 million applicants.
Formulation
Although there are many variations, the basic problem can be stated as follows:
* There is a single position to fill.
* There are ''n'' applicants for the position, and the value of ''n'' is known.
* The applicants, if seen altogether, can be ranked from best to worst unambiguously.
* The applicants are interviewed sequentially in random order, with each order being equally likely.
* Immediately after an interview, the interviewed applicant is either accepted or rejected, and the decision is irrevocable.
* The decision to accept or reject an applicant can be based only on the relative ranks of the applicants interviewed so far.
* The objective of the general solution is to have the highest probability of selecting the best applicant of the whole group. This is the same as maximizing the expected payoff, with payoff defined to be one for the best applicant and zero otherwise.
A ''candidate'' is defined as an applicant who, when interviewed, is better than all the applicants interviewed previously. ''Skip'' is used to mean "reject immediately after the interview". Since the objective in the problem is to select the single best applicant, only candidates will be considered for acceptance. The "candidate" in this context corresponds to the concept of record in permutation.
Deriving the optimal policy
The optimal policy for the problem is a
stopping rule. Under it, the interviewer rejects the first ''r'' − 1 applicants (let applicant ''M'' be the best applicant among these ''r'' − 1 applicants), and then selects the first subsequent applicant that is better than applicant ''M''. It can be shown that the optimal strategy lies in this class of strategies. (Note that we should never choose an applicant who is not the best we have seen so far, since they cannot be the best overall applicant.) For an arbitrary cutoff ''r'', the probability that the best applicant is selected is
:
The sum is not defined for ''r'' = 1, but in this case the only feasible policy is to select the first applicant, and hence ''P''(1) = 1/''n''. This sum is obtained by noting that if applicant ''i'' is the best applicant, then it is selected if and only if the best applicant among the first ''i'' − 1 applicants is among the first ''r'' − 1 applicants that were rejected. Letting ''n'' tend to infinity, writing
as the limit of ''(r−1)''/''n'', using ''t'' for ''(i−1)''/''n'' and ''dt'' for 1/''n'', the sum can be approximated by the integral
:
Taking the derivative of ''P''(''x'') with respect to
, setting it to 0, and solving for ''x'', we find that the optimal ''x'' is equal to 1/''e''. Thus, the optimal cutoff tends to ''n''/''e'' as ''n'' increases, and the best applicant is selected with probability 1/''e''.
For small values of ''n'', the optimal ''r'' can also be obtained by standard
dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
I ...
methods. The optimal thresholds ''r'' and probability of selecting the best alternative ''P'' for several values of ''n'' are shown in the following table.
The probability of selecting the best applicant in the classical secretary problem converges toward
.
Alternative solution
This problem and several modifications can be solved (including the proof of optimality) in a straightforward manner by the
odds algorithm The odds algorithm (or Bruss algorithm) is a mathematical method for computing optimal strategies for a class of problems that belong to the domain of optimal stopping problems. Their solution follows from the ''odds strategy'', and the importance ...
, which also has other applications. Modifications for the secretary problem that can be solved by this algorithm include random availabilities of applicants, more general hypotheses for applicants to be of interest to the decision maker, group interviews for applicants, as well as certain models for a random number of applicants.
Limitations
The solution of the secretary problem is only meaningful if it is justified to assume that the applicants have no knowledge of the decision strategy employed, because early applicants have no chance at all and may not show up otherwise.
One important drawback for applications of the solution of the classical secretary problem is that the number of applicants
must be known in advance, which is rarely the case. One way to overcome this problem is to suppose that the number of applicants is a random variable
with a known distribution of
(Presman and Sonin, 1972). For this model, the optimal solution is in general much harder, however. Moreover, the optimal success probability is now no longer around 1/''e'' but typically lower. This can be understood in the context of having a "price" to pay for not knowing the number of applicants. However, in this model the price is high. Depending on the choice of the distribution of
, the optimal win probability can approach zero. Looking for ways to cope with this new problem led to a new model yielding the so-called 1/e-law of best choice.
1/e-law of best choice
The essence of the model is based on the idea that life is sequential and that real-world problems pose themselves in real time. Also, it is easier to estimate times in which specific events (arrivals of applicants) should occur more frequently (if they do) than to estimate the distribution of the number of specific events which will occur. This idea led to the following approach, the so-called ''unified approach'' (1984):
The model is defined as follows: An applicant must be selected on some time interval