Secretary problem

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---an applicant 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.

Deriving the optimal policy

The optimal policy for the problem is a stopping rule. Under it, the interviewer should skip the first $r-1$ applicants, and then take the next applicant who is a candidate (i.e., who has the best relative ranking of those interviewed up to that point). For an arbitrary cutoff $r$, the probability that the best applicant is selected is

:$P(r)=sum\_\{j=r\}^\{n\}left(frac\{1\}\{n\}\; ight)left(frac\{r-1\}\{j-1\}\; ight)=left(frac\{r-1\}\{n\}\; ight)sum\_\{j=r\}^\{n\}left(frac\{1\}\{j-1\}\; ight).$

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

:$P(r)=x\; int\_\{x\}^\{1\}frac\{1\}\{t\},dt\; =\; -x\; log(x).$

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$.

For small values of $n$, the optimal $r$ can also be obtained by standard dynamic programming methods. The optimal thresholds $r$ and probability of selecting the best alternative $P$ for several values of $n$ are shown in the following table.

Note that the probability of selecting the best alternative converges quite rapidly toward $1/eapprox\; 0.368$.

Alternative solution

The secretary problem and several modifications of this problem can be solved in a straightforward manner by the Odds algorithm.

Heuristic performance

Stein, Seale, and Rapoport (2003) derived the expected success probabilities for several psychologically plausible heuristics that might be employed in the secretary problem. The heuristics they examined were:

* The Cutoff Rule (CR): Do not accept any of the first $y$ applicants; thereafter, select the first encountered candidate (i.e., an applicant with relative rank 1). This rule has as a special case the optimal policy for the CSP for which $y=r$.
* Candidate Count Rule (CCR): Select the $y$ encountered candidate. Note, that this rule does not necessarily skip any applicants; it only considers how many candidates have been observed, not how deep the decision maker is in the applicant sequence.
* Successive Non-Candidate Rule (SNCR): Select the first encountered candidate after observing $y$ non-candidates (i.e., applicants with relative rank > 1).

Note that each heuristic has a single parameter $y$. The figure (shown on right) displays the expected success probabilities for each heuristic as a function of $y$ for problems with $n=80$.

Cardinal payoff variant

Finding the single best applicant might seem like a rather strict objective. One can imagine that the interviewer would rather hire a higher-valued applicant than a lower-valued one, and not only be concerned with getting the best. That is, she will derive some value from selecting an applicant that is not necessarily the best, and the value she derives is increasing in the value of the one she selects.

To model this problem, suppose that the $n$ applicants have "true" values that are random variables $X$ drawn i.i.d. from a uniform distribution on $[0,1]$. Similar to the classical problem described above, the interviewer only observes whether each applicant is the best so far (a candidate), must accept or reject each on the spot, and "must" accept the last one if he is reached. (To be clear, the interviewer does not learn the actual relative rank of "each" applicant. She learns only whether the applicant has relative rank 1.) However, in this version her "payoff" is given by the true value of the selected applicant. For example, if she selects an applicant whose true value is 0.8, then she will earn 0.8. The interviewer's objective is to maximize the expected value of the selected applicant.

Since the applicant's values are i.i.d. draws from a uniform distribution on $[0,1]$, the expected value of the $t$th applicant given that $x\_\{t\}=maxleft\{x\_\{1\},x\_\{2\},ldots,x\_\{t\}\; ight\}$ isgiven by

:$E\_\{t\}=Eleft(X\_\{t\}|I\_\{t\}=1\; ight)=frac\{t\}\{t+1\}.$

As in the classical problem, the optimal policy is given by a threshold, which for this problem we will denote by $c$, at which the interviewer should begin accepting candidates. [http://dx.doi.org/10.1016/j.jmp.2005.11.003 Bearden (2006)] showed that $c$ is either $lfloor\; sqrt\; n\; floor$ or $lceil\; sqrt\; n\; ceil$. This follows from the fact that given a problem with $n$ applicants, the expected payoff for some arbitrary threshold $1leq\; c\; leq\; n$ is

:$V\_\{n\}(c)=sum\_\{t=c\}^\{n-1\}left\; [prod\_\{s=c\}^\{t-1\}left(frac\{s-1\}\{s\}\; ight)\; ight]\; left(frac\{1\}\{t+1\}\; ight)+left\; [prod\_\{s=c\}^\{n-1\}left(frac\{s-1\}\{s\}\; ight)\; ight]\; frac\{1\}\{2\}=\{frac\; \{2cn-\{c\}^\{2\}+c-n\}\{2cn.$

Differentiating $V\_\{n\}(c)$ with respect to $c$, one gets $partial\; V\; /\; partialc=left(-\{c\}^\{,2\}+n\; ight)/\; left(2\{c\}^\{,2\}n\; ight)$. Since for all permissiblevalues of $c$, we find that $V$ is maximized at $c=sqrt\; n$. Since $V$ is convex in $c$, the optimal integer-valued threshold must be either $lfloor\; sqrt\; n\; floor$ or $lceil\; sqrt\; n\; ceil$. Thus, for most values of $n$ the interviewer will begin accepting applicants sooner in the cardinal payoff version than in the classical version where the objective is to select the single best applicant. Note that this is not an asymptotic result: It holds for all $n$.

Other variants

A number of other variations of the classical secretary problem have been proposed. [ Many of these are reviewed in Freeman (1983).]

Experimental studies

Psychologists and experimental economists have studied the decision behavior of actual people in secretary problems [ Bearden, Murphy, and Rapoport, 2006; Bearden, Rapoport, and Murphy, 2006; Seale and Rapoport, 1997] . 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.

ee also

* Optimal stopping
* Odds algorithm
* Search theory

References

* [http://dx.doi.org/10.1016/j.jmp.2005.11.003 J. N. Bearden. "A new secretary problem with rank-based selection and cardinal payoffs." "Journal of Mathematical Psychology", volume 50, pp.58-59. 2006.]
* [http://dx.doi.org/10.1016/j.jmp.2005.08.002 J. N. Bearden, R. O. Murphy, Rapoport, A. "A multi-attribute extension of the secretary problem: Theory and experiments." "Journal of Mathematical Psychology", volume 49, pp.410-425. 2005.]
* [http://dx.doi.org/10.1287/mnsc.1060.0535 J. N. Bearden, A. Rapoport, R. O. Murphy. "Sequential observation and selection with rank-dependent payoffs: An experimental test." "Management Science", volume 52, pp. 1437-1449. 2006.]
* F. Thomas Bruss "Sum the odds to one and stop," Annals of Probability, Vol. 28. 1384-1391. (2000)
* T. S. Ferguson. [A mathematics professor at UCLA and the father of Chris "Jesus" Ferguson, the professional poker player] "Who solved the secretary problem?" "Statistical science", volume 4, pp.282-296. 1989.
* P. R. Freeman. "The secretary problem and its extensions: A review." International Statistical Review / Revue Internationale de Statistique, volume 51, pp. 189-206. 1983.
* [http://dx.doi.org/10.1006/obhd.1997.2683 D. A. Seale, A. Rapoport. "Sequential decision making with relative ranks: An experimental investigation of the 'secretary problem.'" Organizational Behavior and Human Decision Processes, volume 69, pp.221-236. 1997.]
* [http://dx.doi.org/10.1016/S0377-2217(02)00601-X W. E. Stein, D. A. Seale, A. Rapoport. "Analysis of heuristic solutions to the best choice problem." European Journal of Operational Research, volume 151, pp.140-152.]

Notes

External links

* [http://www.utilitymill.com/utility/Secretary_Problem_Optimizer Online Utility to Calculate Optimal r]
*
* [http://www.behavioral-or.org behavioral-or.org J. Neil Bearden's Home Page]
* [http://www.math.ucla.edu/~tom/Stopping/Contents.html Optimal Stopping and Applications book by Thomas S. Ferguson]
* [http://www.mathpages.com/home/kmath018.htm Optimizing Your Wife] at MathPages