The secretary problem is an optimal stopping problem that has been studied extensively in the fields of applied probability, statistics, and decision theory. It is also known as the marriage problem, the sultan's dowry problem, the fussy suitor problem, and the best choice problem. The problem can be stated as follows:
- There is a single secretarial position to fill.
- There are n applicants for the position, and the value of n is known.
- The applicants can be ranked from best to worst with no ties.
- The applicants are interviewed sequentially in a random order, with each order being equally likely.
- After each interview, the applicant is accepted or rejected.
- The decision to accept or reject an applicant can be based only on the relative ranks of the applicants interviewed so far.
- Rejected applicants cannot be recalled.
- The object is to select the best applicant. The payoff is 1 for the best applicant and zero otherwise.
Let us say that an applicant is a candidate only if it is better than all the applicants viewed previously. Clearly, since the objective in the problem is to select the single best applicant, only candidates will be considered for acceptance. One reason why the secretary problem has received so much attention is that the optimal policy for the problem (the stopping rule) has a surprising feature. Specifically, for large n the optimal policy is to skip the first n / e applicants (where e is the base of the natural logarithm) and then to accept the next candidate that is better than all those previously interviewed. As n gets larger, the probability of selecting the best applicant from the pool goes to 1 / e, which is around 37%. Whether one is searching through 100 or 100,000,000 applicants, the optimal policy will select the single best one about 37% of the time.
For an arbitrary cutoff r, the probability that the best applicant is selected is
Letting n tend to infinity, writing x as the limit of r / n, using t for j / n and dt for 1 / n, the sum can be approximated by the integral
Taking the derivative of P(r) with respect to x, 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.
In summary:
Psychologists and experimental economists have studied the decision behavior of actual people in secretary problems . In large part, this work has shown that people tend to stop searching too soon. This may be explained, at least in part, by the cost of evaluating candidates. Extrapolating to real world settings, this might suggest that people do not search enough whenever they are faced with problems where the decision alternatives are encountered sequentially. For example, when trying to decide at which gas station to stop for gas, people might not search enough before stopping. If true, then they would tend to pay more for gas than they might had they searched longer. The same may be true when people search online for airline tickets, say. Experimental research on problems such as the secretary problem is sometimes referred to as behavioral operations research.