The Secretary Problem

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

The manager of a firm wants to hire a good secretary. He has applicants to interview sequentially, in random order, and can rank the ones interviewed so far. The manager is able to make a decision immediately after each interview. If an applicant is rejected, that applicant cannot be recalled.

[more]

The manager applies the following strategy. He first interviews applicants but rejects them all. From among the rest of the applicants, he then chooses the first one that is better than any of the initial set of applicants. If such an applicant does not exist, the last applicant is automatically chosen. The problem is to choose the size of the initial sample optimally, that is, in such a way as to maximize the probability of getting the best applicant. The best applicant has rank 1 and the worst applicant rank .

This Demonstration shows examples of this optimal stopping problem. The green bars in the first plot are the applicants in the initial sample: they are all rejected. The blue bars are the rest of the applicants, and the red bar is the applicant that will be chosen. The second plot shows the probabilities that the best applicant will be chosen if the initial sample contains various numbers of applicants; the black bar is the number chosen. The thick magenta bar represents the best solution: it maximizes the probability of getting the best applicant.

[less]

Contributed by: Heikki Ruskeepää (February 2013)
Open content licensed under CC BY-NC-SA


Snapshots


Details

Snapshot 1: There are 10 applicants; three are interviewed but rejected (this is the optimal strategy; the probability of getting the best applicant is 0.3987). The manager chooses the sixth applicant because their rank is better than any of the first three. In this case, it happens that the manager gets the best applicant (for whom the rank is 1). Note that the initial sample contains the second-best applicant, so that the applicant chosen will necessarily be the best.

Snapshot 2: The fourth applicant is chosen, who happens to only be the sixth best. This illustrates one of two bad situations. Here, the initial sample of three applicants only contains applicants with poor ranks and the next-best applicant (the fourth) also happens to have a poor rank.

Snapshot 3: The tenth applicant is chosen, who happens to be the worst applicant. This illustrates another bad situation, where the initial sample contains the best applicant. No better applicants can be found, so that the last applicant must be chosen. Unfortunately, the last applicant has the worst rank.

Snapshot 4: Now we have 50 applicants. It is optimal first to interview 18 applicants but reject them all (the probability of getting the best applicant is then 0.3743). The 28th applicant happens to be better than any of the first 18 and is thus chosen; this applicant happens to be the second best of all 50 applicants.

Choosing an Applicant

The first of the two plots shows the situation as seen by an imaginary person who knows the ranks of all the applicants. Instead, the manager of the firm only knows the relative ranks of the applicants interviewed so far.

As an example, consider the first snapshot. After interviewing the first applicant, the manager cannot say anything about the rank of the applicant (we know that this applicant is the fifth best of all the applicants). After interviewing the second applicant, the manager can only say that they are better than the first applicant (we know the second applicant is the second best over all). After interviewing the third applicant, the manager can say that they are worse than the first and the second (we know that they are the ninth-best applicant). The process is continued this way until the sixth applicant has been interviewed. Now, the manager can say that the sixth applicant is better than the best of the first three and is thus chosen. The manager does not know that the sixth applicant happens here to be the best of all applicants; the manager is only able to say that the applicant chosen can have any of the ranks 1, 2, 3, 4, and 5.

The best situation is when the best applicant in the initial sample is the second-best applicant, because then the best applicant is necessarily chosen (Snapshot 1). One of the worst situations is when the best applicant in the initial sample has a poor rank, say , because the applicant chosen can then have as low a rank as (Snapshot 2). Another bad situation is when the initial sample contains the best applicant, because then the last applicant must be chosen, no matter their rank (Snapshot 3).

The Marriage Problem

The secretary problem is often also represented as the marriage problem, where a person wants to marry from a pool of suitors. Other names for the problem are the sultan's dowry problem, the fussy suitor problem, the googol game, and the best-choice problem.

In Lewis [1, p. 4–11], the problem is described as a marriage problem where and (this is not the optimal value of if we want to maximize the probability of getting the best possible result):

"You want the best spouse, but how can you maximize your [chances of finding him/her] under these rules? If you plunge too early in your dating career, there may be finer, undated fish in the sea, and you may go through life regretting a hasty marriage… Yet if you wait too long the best may have slipped through your fingers, and then it is too late.

"There are two ways you can lose badly… If the first ten just happen to be the worst of the lot—luck of the draw—and the next one just happens to be the eleventh from the bottom, you will end up with a pretty bad choice—not the worst, but pretty bad—without ever coming close to the best. You have picked the eleventh from the bottom because [he/she] is better than the first ten—that's your method—while the best is still out there… The other way you can lose is the opposite: by pure chance the best may have actually been in the first ten, leading you to set an impossibly high standard… You will then end up going through the remaining ninety candidates without ever seeing [his/her] equal, and will have to settle for the hundredth… The hundredth will be, on average, just average."

Optimal Sample Size

If the optimal size of the initial sample is used, the probability that we get the best applicant approaches the value , as the number of applicants grows. The optimal size of the initial sample approaches the value . For example, when , the probability of getting the best applicant is 0.3743, quite near to , and the optimal initial sample has size 18, quite near to .

Here, we have maximized the probability of getting the best applicant. We can also use other optimization criteria. For example, we can maximize the probability of getting the best, the second-best, or the third-best applicant, or we can minimize the probability of getting the worst applicant, or we can choose, say, the th candidate (a candidate is an applicant that is found better than all earlier applicants). The optimal stopping problem has also been considered in the case where we do not know in advance the number of applicants.

The Demonstration is based on problem 20 in [2]. See also Secretary problem in Wikipedia.

References

[1] H. W. Lewis, Why Flip a Coin? The Art and Science of Good Decisions, New York: Wiley, 1997.

[2] P. J. Nahin, Digital Dice: Computational Solutions to Practical Probability Problems, Princeton, NJ: Princeton University Press, 2008.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send