How the secretary problem works, and where the 37% rule comes from

What exactly is the secretary problem?

The puzzle imagines an administrator hiring for one position. There are n applicants, and the number n is known in advance. They are interviewed one at a time in a random order, with every ordering equally likely. After each interview the administrator must say yes or no straight away, and a rejected applicant is gone for good.

During the process the administrator can rank each new applicant against everyone met so far, but knows nothing about those still waiting. The goal is narrow: maximise the chance of ending up with the single best applicant of the whole group. Picking the second best counts as a loss.

The puzzle has many nicknames, among them the best choice problem, the googol game, the fussy suitor problem and the marriage problem. Its answer is often called the 37% rule. If every decision could wait until the end, there would be no puzzle at all: you would simply remember the best so far and pick it. The whole difficulty comes from having to decide in the moment.

How does the optimal stopping rule work, step by step?

The winning strategy has two phases. In the first, you look but do not leap: you reject a fixed number of early applicants no matter how good they seem, and simply note the best among them. In the second, you accept the first applicant who is better than everyone you have seen. If nobody ever beats that benchmark, you end up with the last applicant.

Only applicants who beat everyone before them are worth considering, since anyone else cannot be the overall best. Mathematicians call such an applicant a candidate. The question then becomes how long the looking phase should last.

Too short a look, and the benchmark is weak, so you may grab an early candidate who is merely decent. Too long a look, and the best applicant may already have been rejected during the looking phase. Working through the probabilities and letting n grow large shows the ideal cutoff is a fraction 1/e of the applicants, with e being the constant at the base of natural logarithms. That is about 37%. With this cutoff, the chance of selecting the very best applicant also approaches 1/e, about 0.368.

What does a worked example look like?

Imagine you are choosing a flat and will see ten in random order, with no chance to go back to one you turned down. The rule says to view roughly the first three or four without signing anything, while keeping a mental note of the best of them.

Suppose the third flat was the strongest of that opening group. From the fourth flat onward, you sign for the first one that is better than that third flat. If the seventh flat clears the bar, you take it and stop looking. If none of the remaining flats beats it, you are left with the tenth.

This will not always land the best flat. Sometimes the best one sits in the opening group and is passed over; sometimes a good but not best flat beats the benchmark first. But no other rule based only on relative ranks does better on average. For small numbers like ten, the exact best cutoff can be found by dynamic programming rather than the 1/e approximation.

Why is the 37% figure so striking?

One reason the problem draws so much attention is that the rule is simple and its success rate barely depends on scale. It selects the single best option about 37% of the time whether the pool holds 100 or 100 million. Choosing the best out of a huge crowd by pure chance would be nearly hopeless, yet a plain look-then-leap rule keeps the odds above one in three.

The shortest rigorous proof known comes from the odds algorithm, which also shows the win probability is always at least 1/e. The same algorithm handles several variations, such as applicants who are only available some of the time, group interviews and certain cases where the number of applicants is random.

The problem belongs to a wider field called optimal stopping, which studies when to take an action to maximise an expected reward. Economists working on similar questions, such as a worker hunting for a well-paid job or a shopper looking for a low price, call it search theory. Choosing a parking space on the way to a theatre, without turning back, is another classic example.

Where does the 37% rule break down?

The clean answer depends on assumptions that rarely hold in full. The biggest is that you know n, the total number of options, in advance. When the number of applicants is itself random, the best achievable odds are usually lower than 1/e, and for some distributions they can fall towards zero. Not knowing the size of the pool has a real price.

A later result, the 1/e-law of best choice proved by F. Thomas Bruss in 1984, offers a way around this. Instead of counting applicants, you fix a time window and wait until a point in time by which 1/e of arrivals would be expected, then take the first applicant who beats all earlier ones. That strategy still wins with probability at least 1/e. It is sometimes confused with the classic solution because the same number appears, but it rests on different and weaker assumptions.

The rule also assumes applicants do not know the strategy. If early arrivals knew they had no chance, they might not show up at all. And the goal of only the very best is strict: in real choices a near-best option is usually still valuable, which leads to different variants with different answers.

What does it teach about making decisions?

The secretary problem is an exploration versus exploitation dilemma in miniature. Some time spent purely exploring is not wasted; it is what makes a later decision informed. But exploring too long has its own cost, because the best option may slip away while you are still gathering information.

It also shows how much the answer depends on framing. Change the goal from the best to a good one, or let the number of options be uncertain, and the right amount of looking changes. The 37% rule is a precise answer to a precise question, and its value lies as much in making the trade-off visible as in the number itself.

Questions people ask

The thinking behind it

• opportunity cost
• choice overload
• expected value
• local vs global optimum

More algorithms, explained

• How Bayesian inference works
• How binary search works
• How collaborative filtering works: recommendations from people like you
• How PageRank works: the algorithm that ranked the web by its links