The fourth-best for the job

The subject of this post is a puzzle, a variant of the so-called secretary problem: suppose that you need to hire one of $n$ candidates for a job.  You must interview one candidate at a time in random order, and after each interview you must decide whether to accept the candidate and offer him or her the position, or to reject the candidate and move on to the next interview.  You cannot return to a previously rejected candidate.

Suppose that the candidates’ interview results are not quantifiable, but they are comparable, so that at any point in the process you can rank in strict preference order the candidates you have interviewed so far.  What should be your strategy for selecting the “best” candidate?

In the classical statement of the problem, the objective is to maximize the probability of selecting the overall best candidate.  The “popular” nice result is that the corresponding optimal strategy has a very simple form, and a nearly fixed success rate, no matter the total number $n$ of candidates: interview the first $n/e$ candidates (about 36.8% of them), rejecting them outright, then accept the first subsequent candidate that is the best so far.  The resulting probability of selecting the best overall candidate is approximately $1/e$, or about 0.368.

I remember first encountering this problem, and thinking that the goal was unrealistic: for example, consider the extreme situation where you have interviewed the 99th of 100 candidates, and he or she is the second-best so far.  The optimal strategy dictates rejecting the candidate– which is at worst third-best overall– and rolling the dice on the final candidate.

Problem: Instead, suppose that the objective is to minimize the expected overall rank of the selected candidate.  That is, if $X$ is the random variable indicating the final overall rank of the selected candidate, then instead of maximizing $P(X=1)$, we want to minimize $E(X)$.  What is the optimal strategy and resulting expected rank for, say, one hundred candidates?  One million candidates?

(Note that this seemingly natural variant of the problem is missing from the Wikipedia page, despite the inclusion of several other similar excursions.)

I think this is a great problem, particularly as a programming exercise.  It can be solved with a relatively simple recursive implementation in less than a dozen lines of code.  But with one million candidates, that simple implementation bogs down, and requires some re-factoring.  The resulting more efficient solution still involves less than a dozen lines of code… and I think the answer is just as interesting as the $1/e$ result in the original problem.

This entry was posted in Uncategorized. Bookmark the permalink.

1 Response to The fourth-best for the job

1. Michael Earnest says:

I think part of the reason this problem is not as well known is that the solution is not simple. The optimal expected rank, as you mentioned in your other post, approaches something like 3.8695 as $n \to \infty$, which is quite nice. However, the optimal strategy does not seem to admit a nice exact description. Still, the following heuristic seems to come reasonably close:

Reject the first 25% of the candidates. For each remaining candidate, if the number of unseen candidates is u, you should only accept them if their rank among the seen candidates is at most floor(n/u).

So, for candidates n/4 through n/2, you will only accept if they are the best you have seen so far. Then, for candidates n/2 through 2n/3, you loosen your restrictions and accept if they are in the top two so far, etc. This is interesting in comparison with the original secretary problem.

This site uses Akismet to reduce spam. Learn how your comment data is processed.