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:

1. There is a single secretarial position to fill.
2. There are $n$ applicants for the position, and this is known.
3. The applicants are interviewed sequentially in a random order, with each order being equally likely.
4. The applicants can be ranked from best to worst with no ties.
5. The decision to accept or reject an applicant can be based only on the relative ranks of the applicants interviewed so far.
6. Rejected applicants cannot be recalled.
7. You will only be happy if you select the single best applicant. You get a payoff of 1 if you do so, and nothing 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 and then to accept the next encountered candidate, where $e$ is the base of the natural logarithm. 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 for the Secretary Problem

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 interview 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}}\right)\left({\frac {r-1}{j-1}}\right)=\left({\frac {r-1}{n}}\right)\sum _{j=r}^{n}\left({\frac {1}{j-1}}\right).$

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}\left({\frac {1}{t}}\right)dt=-x{\text{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.

$n$	1	2	3	4	5	6	7	8	9
$r$	1	1	2	2	3	3	3	4	4
$P$	1.000	0.500	0.500	0.458	0.433	0.428	0.414	0.410	0.406

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

Heuristic Performance in the Secretary Problem

File:SecretaryProblemHeuristicPlot.jpg

Expected success rates.

Stein, Seale, and Rapoport (2003) derived the expected success rates 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.
• Sucessive 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 rate for each heuristic as a function of $y$ for problems with $n=80$.

A Secretary Problem with Rank-Based Selection and Cardinal Payoffs

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 it 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}=\max \left\{x_{1},x_{2},\ldots ,x_{t}\right\}$ is given by

$E_{t}=E\left(X_{t}|I_{t}=1\right)={\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. Bearden (2006) showed that $c$ is either $\lfloor {\sqrt {n}}\rfloor$ or $\lceil {\sqrt {n}}\rceil$. This follows from the fact that given a problem with $n$ applicants, the expected payoff for some arbitrary threshold $1\leq c\leq n$ is

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

Differentiating the last line of $V_{n}(c)$ with respect to $c$, one gets $\partial V/\partial c=\left(-{c}^{\,2}+n\right)/\left(2{c}^{\,2}n\right)$. Since $\partial ^{\,2}V/\partial c^{\,2}<0$ for all permissible values 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}}\rfloor$ or $\lceil {\sqrt {n}}\rceil$. 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 of the Secretary Problem

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

Experimental Studies of Decision Behavior in Secretary Problems

Psychologists and experimental economists have studied the decision behavior of actual people in secretary problems (e.g., 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. 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.

Trivia

One of the most highly cited papers on the secretary problem ("Who solved the secretary problem?") was written by Thomas S. Ferguson, a mathematics professor at UCLA, who is the father of Chris "Jesus" Ferguson, the professional poker player.

References

• J. N. Bearden. "A new secretary problem with rank-based selection and cardinal payoffs." Journal of Mathematical Psychology, volume 50, pp.58-59. 2006.
• 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.
• 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.
• T. S. Ferguson. "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.
• 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.
• 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.

External links

• Weisstein, Eric W. "Sultan's Dowry Problem". MathWorld.
• behavioral-or.org J. Neil Bearden's Home Page