You interview candidates for a job, one by one and in random order. You can only choose one, and once you reject a candidate you can't go back. You want to maximize the probability of choosing the best of all. What is the optimal strategy?
Home > Riddles > The choice optimal
The choice optimal
It is not a problem of guessing the best, but of deciding when it stops paying to continue looking. Its beauty is that the optimal strategy comes from accepting a calculated renunciation.
Hints
Show hints
- Before choosing you need a reference: deciding blindly from the beginning is usually a bad idea.
- The optimal strategy has two phases: first observe without choosing; then choose by comparison.
- The optimal cut-off point is close to 37% of the total, that is, around \(N/e\).
Solution
Show full solution
Answer: If there are \(N\) candidates, the optimal strategy is to at first discard approximately \(N/e\) candidates without choosing any and, from there, hire the first one who is better than all the previous ones. Explanation: This is the classic optimal stopping problem. If you choose too early, you lack a reliable reference. If you wait too long, perhaps the best candidate has already passed. The correct strategy therefore has two phases: 1. Observation phase. You reject the first candidates and use them only to calibrate the level.
- Decision phase. From that point on, you choose the first one that surpasses all those seen until then. The mathematical result is that the optimal cut-off point is very close to \[
\frac{N}{e}\approx 0{,}368\,N.
\] That is, it is advisable to look at approximately the initial 37% and then accept the first candidate who beats that bar. For example, if there were 100 candidates, the strategy would be to observe without choosing the first 37 and, from the 38th, choose the first one who is better than all the previous ones. This rule does not guarantee always getting it right, but it does maximize the probability of choosing the best one. And that maximum probability approaches \[
\frac{1}{e}\approx 36{,}8\%.
\] The elegance of the problem is that the best strategy does not need to know who will be the best: it only needs to decide when to start being willing to choose.
Related riddles
Keep practicing
If you enjoyed this one, try more pure-logic riddles, explore this theme, browse the full archive, or read the riddle-solving guide.