When every rejection is irreversible, choosing well begins with knowing when not to choose. An initial sample can become the standard used for every later decision.
The optimal choice
Riddle statement
You will interview a known number \(N\) of candidates for a job. They arrive one at a time in a uniformly random order, and you can rank them without ties.
After each interview, you must decide immediately: hire that candidate and stop, or reject them permanently. If you reach the final candidate without hiring anyone, you must hire that candidate.
You want to maximize the probability of selecting the best candidate overall.
What is the optimal strategy, and what success probability does it achieve?
Show solution
Solution
Strategy: reject the first \(r\) candidates and use them only as a sample. Then hire the first candidate who is better than everyone seen previously. If no candidate meets that condition, hire the last one.
Success probability. Suppose the best candidate appears in position \(k>r\). The strategy selects that candidate exactly when the best of the preceding \(k-1\) candidates lies among the first \(r\). Otherwise, a later candidate would have triggered the rule earlier.
Among the first \(k-1\) positions, the location of their best candidate is uniform. Hence this condition has probability
The overall best candidate is equally likely to occupy any of the \(N\) positions, so
For a given \(N\), choose the integer \(r\) that maximizes this expression.
For large \(N\), write \(x=r/N\). The harmonic sum is approximately
and therefore
This is maximized at \(x=1/e\).
The practical rule is to reject approximately the first 37% of candidates and then hire the first candidate who beats everyone seen before.
For \(N=100\), the optimal cutoff is \(r=37\), with success probability approximately 37.10%. As \(N\) grows, the probability approaches \(1/e\approx36.8\%\).