What Is the Secretary Problem?

Imagine you are looking for a flat in a busy city. You can view ten flats, one after the other. After each viewing you must say yes or no at once, because someone else will take the flat the same day. If you say yes too early, a better flat may come later. If you wait too long, the best one may already be gone. When should you stop looking and choose?

What is the secretary problem?

The secretary problem is the name mathematicians give to this kind of decision. You see options one at a time, you must decide on each one at once, and you cannot go back. The problem has a clear answer. Look at the first 37 percent of the options without choosing any of them. After that, take the first option that is better than everything you have seen so far.

The name comes from an old example in which a manager interviews applicants for a secretary job. Other names are the marriage problem and the best-choice problem. In its classic form, the problem has strict rules.

1. You want only the very best option. Second best counts as a failure.
2. You know how many options there will be.
3. The options come in random order.
4. You can only compare an option with the ones you have already seen. You do not know how good it is on any absolute scale.
5. An option you turn down is gone for good.

Under these rules, no strategy can do better than the 37 percent rule. The next section shows why.

How does the 37 percent rule work with ten flats?

We start with the smallest interesting case, three flats, and then go up to ten.

Call the three flats A, B and C, where A is the best and C is the worst. They can come in six different orders, and each order is equally likely. Our rule is this: look at the first flat without taking it, then take the first flat that is better than it. If no flat is better, you are left with the last one.

The rule finds the best flat in 3 of the 6 orders, so it succeeds half the time. Taking the first flat would succeed in only 2 of 6 orders, one time in three. Looking first helps, even with three flats.

Now we go to ten flats. You view a few flats only to learn what is normal in this city. Then you take the first flat that is better than all of them. How many should you skip? The table shows the chance of getting the best flat for each choice.

The best choice is to skip three flats. Then you get the very best flat about 40 percent of the time. If you picked a flat at random, your chance would be 10 percent.

Why is there a best point in the middle? The look phase sets your standard. If it is too short, your standard is weak, and an average flat can beat it. If it is too long, the best flat has often already passed during the look phase. Then nothing later can beat your standard, and you end with the last flat.

Mathematicians can write this chance as a formula. Suppose there are n options and you skip the first k. Your chance of success is (k/n) × (1/k + 1/(k+1) + … + 1/(n−1)). When n becomes large, the best share k/n gets closer and closer to 1/e. The number e, about 2.718, is a constant that appears wherever growth and chance are studied. So 1/e is about 0.368, or 37 percent.

The surprising part is that the chance of success also approaches 37 percent. With 100 flats or with a million, the rule still finds the very best about 37 percent of the time.

What the secretary problem teaches you

When options come one at a time and you cannot go back, spend a fixed part of your search only learning what is normal. Then commit to the first option that beats everything you have seen. The question to ask yourself is: “Have I seen enough to know what good looks like?”

• Searching with a time limit. You often do not know how many options there will be, but you know how much time you have. Then the rule applies to time. If you have one month to find a flat, use the first 11 days to look and learn.
• Hiring and job hunting. A small business that interviews applicants one by one faces the same choice. So does a person who applies for jobs and must answer each offer within days.
• A famous search for a wife. The astronomer Johannes Kepler looked for a second wife after his first wife died in 1611. He considered eleven women over almost two years and chose the fifth. As the statistician Thomas Ferguson noted, the rule for eleven options is to skip four and then choose. Kepler’s choice fits it exactly, though he could not have known the rule.

In economics and psychology, the secretary problem is a standard test of how people search. In experiments, most people stop searching too soon. One reason may be that every extra look costs time and effort in real life. When researchers add a small cost for each look, the best rule moves earlier, closer to what people actually do.

Does the rule mean you will usually get the best?

Many people think the 37 percent rule almost always finds the best option. In fact, it misses the best option in about 63 percent of cases. The rule is the best possible strategy under the conditions, but those conditions make success hard for any strategy.

A second mistake is to think that the rule at least gives you a good option. It does not. If the best flat happened to be among the first three, nothing later can beat it. You then end with the last flat, which may be poor. The rule aims for the very best and accepts this risk. If you would be happy with a good flat, the problem changes. Mathematicians have solved that version too, and its best rule is different.

Where do the assumptions break?

Real searches rarely follow the strict rules, and each broken rule changes the answer.

• You can sometimes go back. A landlord may still have the flat next week. If going back is possible, you can look longer.
• Options can say no. In dating and in job markets, the other side also chooses. The classic problem ignores this completely.
• You often know real values. If you know the actual quality of each flat, and how quality is spread in the market, you can do better than 37 percent. In this version, studied by the statisticians Gilbert and Mosteller in 1966, the best chance is about 58 percent.
• Looking has a cost. Each viewing costs time and energy. With a cost per look, you should stop earlier.

So treat the 37 percent as a guide for one clear situation, not as a law for every search.

Learn more

The secretary problem has no single inventor, and its early history is unclear. It first appeared in print in February 1960, in Martin Gardner’s mathematics column in Scientific American. Gardner called it the game of googol and credited it to two men named Fox and Marnie. But many people knew it earlier. The mathematician Merrill Flood said he presented a version, which he called the fiancée problem, at a conference in January 1950.

The statistician Lindley published the first solution in a scientific journal in 1961, and the mathematician Dynkin followed in 1963. In 1989 Ferguson asked who had really solved it. His answer was “Nobody”, because Gardner’s game was harder than the version everyone had solved.

Ferguson’s paper “Who Solved the Secretary Problem?” is the best next step. It is witty and readable, and it explains both versions. For the wider idea of when to stop searching, read Algorithms to Live By (Affiliate Link) by Brian Christian and Tom Griffiths. It starts with this problem and applies ideas from computer science to everyday decisions. When both sides choose, as in dating or school places, the problem becomes a matching problem. That is the subject of “Who Gets What and Why” by Alvin E. Roth: Summary and Review.