The secretary problem is a famous problem that uses the optimal stopping theory. The problem 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, the googol game, and the best choice problem.
Contents
- Formulation
- Deriving the optimal policy
- Alternative solution
- Unknown number of applicants
- 1e law of best choice
- The game of googol
- Heuristic performance
- Cardinal payoff variant
- Other modifications
- Experimental studies
- Neural correlates
- History
- Combinatorial generalization
- References
The basic form of the problem is the following: imagine an administrator who wants to hire the best secretary out of
The problem has an elegant solution. The optimal stopping rule prescribes always rejecting the first
Formulation
Although there are many variations, the basic problem can be stated as follows:
Terminology: 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".
Clearly, 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. 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 it is easy to see that 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
Taking the derivative of P(x) with respect to
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.
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 (2000), 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. None of these modifications are treated in this article.
Unknown number of applicants
A major drawback for applications of the solution of the classical secretary problem is that the number of applicants
1/e-law of best choice
The essence of the model is based on the idea that real-world problems pose themselves in real time and that it is easier to estimate times in which specific events (arrivals of applicants) should occur more likely (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: An applicant must be selected on some time interval
1/e-law: Let
The 1/e-strategy
(i) yields for allThe 1/e-law, proved in 1984 by F. Thomas Bruss, came as a surprise. The reason was that a value of about 1/e had been considered before as being out of reach in a model for unknown
The 1/e-law is sometimes confused with the solution for the secretary problem because of the similar role of the number 1/e. Note however, that in the 1/e-law, this role is more general. The result is also stronger, since it holds for an unknown number of applicants and since the model is more tractable for applications.
The game of googol
According to Ferguson 1989, the secretary problem appeared for the first time in print in Martin Gardner's column of Scientific American in 1960. Here is how Martin Gardner formulated the problem: "Ask someone to take as many slips of paper as he pleases, and on each slip write a different positive number. The numbers may range from small fractions of 1 to a number the size of a googol (1 followed by a hundred 0s) or even larger. These slips are turned face down and shuffled over the top of a table. One at a time you turn the slips face up. The aim is to stop turning when you come to the number that you guess to be the largest of the series. You cannot go back and pick a previously turned slip. If you turn over all the slips, then of course you must pick the last one turned."
In the article "Who solved the Secretary problem?" Ferguson 1989 pointed out that the secretary problem remained unsolved as it was stated by M. Gardner, that is as a two-person zero-sum game with two antagonistic players. In this game Alice, the informed player, writes secretly distinct numbers on
Bob wants to guess the maximal number with the highest possible probability, while Alice's goal is to keep this probability as low as possible. It is not optimal for Alice to sample the numbers independently from some fixed distribution, and she can play better by choosing random numbers in some dependent way. For
Heuristic performance
The remainder of the article deals again with the secretary problem for a known number of applicants.
Stein, Seale & 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:
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, the interviewer will derive some value from selecting an applicant that is not necessarily the best, and the derived value increases with the value of the one selected.
To model this problem, suppose that the
Since the applicant's values are i.i.d. draws from a uniform distribution on [0, 1], the expected value of the tth applicant given that
As in the classical problem, the optimal policy is given by a threshold, which for this problem we will denote by
Differentiating
Since
Other modifications
There are at least three variants of the secretary problem that also have simple and elegant solutions.
One variant replaces the desire to pick the best with the desire to pick the second-best. Robert J. Vanderbei calls this the "postdoc" problem arguing that the "best" will go to Harvard. For this problem, the probability of success for an even number of applicants is exactly
For a second variant, the number of selections is specified to be greater than one. In other words, the interviewer is not hiring just one secretary but rather is, say, admitting a class of students from an applicant pool. Under the assumption that success is achieved if and only if all the selected candidates are superior to all of the not-selected candidates, it is again a problem that can be solved. It was shown in Vanderbei 1980 that when n is even and the desire is to select exactly half the candidates, the optimal strategy yields a success probability of
Another variant is that of selecting the best
Experimental studies
Experimental psychologists and economists have studied the decision behavior of actual people in secretary problem situations. 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. In 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 along a highway to stop for gas, people might not search enough before stopping. If true, then they would tend to pay more for gas than if they had searched longer. The same may be true when people search online for airline tickets. Experimental research on problems such as the secretary problem is sometimes referred to as behavioral operations research.
Neural correlates
While there is a substantial body of neuroscience research on information integration, or the representation of belief, in perceptual decision-making tasks using both animal and human subjects, there is relatively little known about how the decision to stop gathering information is arrived at.
Researchers have studied the neural bases of solving the secretary problem in healthy volunteers using functional MRI. A Markov decision process (MDP) was used to quantify the value of continuing to search versus committing to the current option. Decisions to take versus decline an option engaged parietal and dorsolateral prefrontal cortices, as well ventral striatum, anterior insula, and anterior cingulate. Therefore, brain regions previously implicated in evidence integration and reward representation encode threshold crossings that trigger decisions to commit to a choice.
History
The secretary problem was apparently introduced in 1949 by Merrill M. Flood, who called it the fiancée problem in a lecture he gave that year. He referred to it several times during the 1950s, for example, in a conference talk at Purdue on 9 May 1958, and it eventually became widely known in the folklore although nothing was published at the time. In 1958 he sent a letter to Leonard Gillman, with copies to a dozen friends including Samuel Karlin and J. Robbins, outlining a proof of the optimum strategy, with an appendix by R. Palermo who proved that all strategies are dominated by a strategy of the form "reject the first p unconditionally, then accept the next candidate who is better". (See Flood (1958).)
The first publication was apparently by Martin Gardner in Scientific American, February 1960. He had heard about it from John H. Fox, Jr., and L. Gerald Marnie, who had independently come up with an equivalent problem in 1958; they called it the "game of googol". Fox and Marnie did not know the optimum solution; Gardner asked for advice from Leo Moser, who (together with J. R. Pounder) provided a correct analysis for publication in the magazine. Soon afterwards, several mathematicians wrote to Gardner to tell him about the equivalent problem they had heard via the grapevine, all of which can most likely be traced to Flood's original work.
The 1/e-law of best choice is due to F. Thomas Bruss (1984).
Ferguson (1989) has an extensive bibliography and points out that a similar (but different) problem had been considered by Arthur Cayley in 1875 and even by Johannes Kepler long before that.
Combinatorial generalization
The secretary problem gets a combinatorial flavor when there is not only a single job available but multiple different jobs. Again there are
By a generalization of the classic algorithm for the secretary problem, it is possible to obtain an assignment where the expected sum of qualifications is only a factor of