Candidates arrive one at a time, and you must decide on the spot: hire now or turn them away for good. It seems you could pick the best of 100 with about a 1% chance. A simple optimal stopping rule gives 37%: let the first 37 go, then take the first one who beats everyone before. Check it with a game, a simulation and five explanations.
This is the classic optimal stopping problem. It is known as the secretary problem, the marriage problem or the game of googol. The core is the same: options appear one by one, you can't go back to one you turned down, and you must decide when to stop.
There are n candidates for one job. You know how many there are, but they come to the interview in random order.
After each interview you know only one thing: how this candidate compares with the ones you have already seen. You know nothing about those still to come.
You can hire the candidate, and the search is over. Or you can reject them, and they are gone for good. If you reach the last one, you have to take them.
There is only one way to win: hire the best of all n. The second best counts as a loss. Which strategy gives the highest chance, and how high is it with 100 candidates?
"The best is one in a hundred, so the chance is about 1%. It's a lottery"
In fact the 37% rule finds the best 37% of the time, and that chance barely depends on how many candidates there are. Even with a million candidates it stays at 36.8%.
Round 5 shows what happens when these rules change.
Imagine the smartest strategy anyone could come up with. How often would it find the best of 100 candidates? Lock in your answer before reading on.
Your answer will be compared with the right one here.
Candidates arrive one at a time. The height of a bar shows how a candidate compares with those seen so far, and orange means "best so far". You see the true scores only at the end. Play a few times: the panel on the right shows how the 37% rule would have done on the same lineups.
With 20 candidates the best rule is to skip 7, then take the first one who beats everyone before. It finds the best in 38.4% of lineups. Picking at random would give 5%.
A strategy with cutoff r: skip the first r candidates, then hire the first one who beats everyone before. The computer plays thousands of lineups for each r. The line is the exact formula; the dots are the simulation. For 100 candidates the peak is at r = 37.
The first part of the candidates is not for choosing. It is for learning what counts as good. The only question is how long to spend on it.
With no information you can't tell whether a candidate is good. So you only assess the first 37 and remember the best of them. That person becomes the bar. After that you take the first candidate who clears it.
The skipped candidates are not wasted: they are what tells you the level. The price of that knowledge is that the best might be among them.
Stop looking too early and the bar is weak, so an average candidate clears it. Look for too long and the best was probably among those you skipped, so nobody later beats the bar. A cutoff of 37 balances the two risks.
The number is the candidate's true place: 1 is the best. Faded means skipped; dark means hired.
With a cutoff of 37 there are three outcomes. In 37.1% of lineups you hire the best. In another 37% the best was among those skipped: nobody clears that bar, and you reach the end. In the remaining 25.9% someone other than the best clears the bar first.
Say the best stands at place i, with i greater than r. That happens with probability 1/n. You hire them if nobody cleared the bar before, that is, if the best of the first i−1 candidates was among the first r. The chance of that is r/(i−1). Add it up over all i:
The sum of reciprocals from r to n−1 is about ln(n/r). So the chance depends only on the share x = r/n, not on n itself. The function −x · ln x peaks at x = 1/e, and its value there is also 1/e. That gives both numbers: skip 37% and win 37% of the time.
The 37% figure doesn't care how many candidates there are, but it does care about the goal. If anyone from the top three will do, or you can go back to someone you rejected, the share to skip is quite different.
The n axis is logarithmic, from 3 to 10,000. The dashed line is 1/e ≈ 36.8%. For small n the chance is even higher: 50% with three candidates.
Suppose that at the end, if you hired nobody, you may call back the best person you saw. They say yes with probability q. 100 candidates.
Same rule everywhere: skip the first r, then take the first one who beats everyone before, and if nobody does, take the last. The best cutoffs were found by computer. Press "Check" to rerun 10,000 simulated lineups.
| Goal (100 candidates) | Best cutoff | Result |
|---|
The last row is about a search with a time limit, when you don't know how many candidates will come. Then you count time instead of people: you only look during the first 37% of the period. The chance stays at least 1/e for any number of candidates.
After his first wife died in 1611, the astronomer Johannes Kepler considered 11 possible brides. In the end he married the fifth, Susanna Reuttinger. The story is often told as an example of the secretary problem, including in the book Algorithms to Live By.
Martin Gardner brought the problem to a wide audience in his Mathematical Games column in Scientific American in 1960. In his version, people write any numbers on slips of paper, as large as a googol, and you have to stop at the largest.
Pick one of 100 candidates at random and the chance of the best is 1%. The 37% rule gives 37.1%. With 1,000 candidates a random pick gives 0.1%, and the rule still gives 36.8%.
Algorithms to Live By (2016) by Brian Christian and Tom Griffiths opens with the 37% rule and applies it to flat hunting and dating. If you search from age 18 to 40, the first 37% of that span ends at about 26.
The number 1/e ≈ 36.8% also turns up in the Secret Santa problem: when many people draw names at random, the chance that nobody draws their own name also tends to 1/e.
If the goal is not "the best or nothing" but the best average rank, there is a cleverer strategy with several thresholds. Even for a huge number of candidates it gives an average rank of about 3.87. The result was published in 1964.
Share your own explanation, an objection or a variant of the puzzle. Commenting needs a GitHub account.
I keep adding new puzzles, new ways to explain them and write-ups of the discussions they start. Leave your email and I'll write when something new is out. No spam, one-click unsubscribe.
The sign-up form will appear here soon.