# The Secretary Problem

## An algorithm for deciding who to marry, and other tough choices.

*Excerpted from* **Things to Make and Do in the Fourth Dimension: A Mathematician’s Journey Through Narcissistic Numbers, Optimal Dating Algorithms, at Least Two Kinds of Infinity, and More** *by Matt Parker. Out now from Farrar, Straus and Giroux.*

Finding a life partner is a delicate balance. When you first start dating people, you don’t know, on average, how romantically well matched other people could be to you, and without that baseline you cannot ascertain if someone is an above average catch and someone you should settle down with. This makes permanently partnering up with the first person you date a bit of a gamble: You should date a few people to get the lay of the land. That said, if you take too long dating people, you run the risk of missing your ideal partner and being forced to make do with whoever is available at the end. It’s a tricky one. The ideal thing to do would be to date just the right number of people to gain the best sense of your options while leaving the highest probability of not missing your ideal partner.

Luckily, math has made it easy for us: That right number of people is the square root of the total number of people you could date in your life. How you estimate the size of your possible dating population is entirely up to your statistical skills and the level of your self-confidence, as is how you then collect your sample. A “voluntary response sample” is generally regarded as socially acceptable, whereas a “stratified random sample” can land you in jail.

Putting that aside, here is the recipe for finding optimal love:

Step 1: Estimate how many people you could date in your life, *n*.

Step 2: Calculate the square root of that number, √*n*.

Step 3: Date and reject the first √*n *people; the best of them will set your benchmark.

Step 4: Continue dating people and settle down with the first person to exceed the benchmark set by the initial √*n *dates.

Who knew it could be so easy? Problems like deciding who to settle down with have the mildly disturbing math name of “optimal stopping problems.” The original optimal stopping problem was known as the secretary problem, and here it is as originally framed.

You’re hiring a new personal assistant and the company’s human resources department has put out an advertisement following the guidelines laid down in its official diversity policies. There is now a queue of potential candidates outside your office, spanning a wide range of genders and ethnicities, all ready to be interviewed for the job. Each of the 10 candidates will come into your office individually for you to assess their qualifications for the role. After you have interviewed each candidate you need to decide on the spot if you want to hire them for the job or move on to the next interview. If you dismiss someone without a job offer, they’ll be snapped up by a rival company: You cannot go back to them later and offer them the job.

You’re in an interesting position. Logic suggests that you shouldn’t offer the job to the first person you interview, because you have no idea what the general caliber of the candidates is. Nor do you want to wait until the 10^{th} person, because if they’re the only one left you’re going to be forced to offer them the job regardless of how well suited to it they are. Somewhere in the middle there must be an ideal place to stop interviewing more candidates just to see what they’re like, and hurry up and choose a good one. This is the optimal place to stop. It’s exactly the same constraint as dating to find a life partner; if you break up with someone you later realize was an ideal candidate, you can rarely go back to re-interview them.

The secretary problem was tossed back and forth between mathematicians in the U.S. during the 1950s, and we don’t know who was first to solve it (though people suspect it was the American mathematician Merrill Flood). The first official solution to appear in print was by the British statistician Dennis Lindley, in 1961. Solving this problem involves realizing that all 10 candidates could be ranked from best to worst and then shuffled up in some random order. There’s a 1 in 10 chance the first candidate through the door is the best one, but the thing is, you just don’t know.

By analyzing the possible distribution of talent, it was calculated that if you interview the first 37 percent of any queue then pick the next one who is better than all the people you’ve interviewed so far, you have a 37 percent chance of getting the best candidate. So, his algorithm is the same as our dating one, but with 0.37 × *n *instead of √*n*. The figure of 37 percent keeps appearing because it is the ratio 1⁄*e*, where *e *is the exponential number 2.718281828 ... (discovered by Jacob Bernoulli). The short story of why the number *e *crashes the party is that it is linked to estimating where the best candidate could be in the queue. Using this method gives you a better than one in three chance of choosing the most suitable candidate overall.

However, the original secretary problem assumes that you have an all-or-nothing attitude. Lindley proved mathematically that his 37 percent method algorithm is the best approach, but that is only if you’ll be completely happy with the best person and completely unhappy with anyone else. In reality, getting something that is slightly below the best option will leave you only slightly less happy. A better solution would be one that will give you someone as high up the ranking of candidates as possible, even if they aren’t necessarily the best. In 2006, psychologist Neil Bearden calculated the best strategy for selecting the highest ranking candidate compared to the theoretically best candidate possible, and it was he who discovered the √*n *method. Out of a choice of 10 people, the √*n *method will, on average, get you someone about 75 percent perfect; in a queue of 100 candidates, the figure is around 90 percent.

You can use this algorithm when faced with any life choice, from choosing life partners to making purchase decisions. I used it when I bought my second-hand car, making sure I saw at least √*n *of the number of cars I had time to check out before I definitely needed to buy one. I think the biggest advantage is that it makes people wait and not impulse-accept their first option. When examples of real decision-making processes have been analyzed, the consistent result is that people choose too soon, and without looking at enough options (with the exception of online dating, where some people become so spoiled for choice they cannot make themselves settle down when there may be better options). An optimal stopping algorithm takes all that indecision away.

This may all sound very impersonal as a way to find a partner, but math has been used to locate love. When Kepler (of the Kepler conjecture) lost his first wife to cholera, he decided to make finding his next wife a mathematical process. In a letter written in 1613 he described how he planned to dedicate two years of his life to interviewing and ranking 11 possible candidates and then making a calculated choice. We don’t know what his “wife appropriateness function” to rank them was, but we do know that he felt the constraints of the secretary problem. He tried to go back and propose to the fourth person he interviewed, but she had already moved on, and refused him. He eventually ended up happily married to candidate five of eleven. Now that’s some rigorous loving.

*Excerpted from* **Things to Make and Do in the Fourth Dimension: A Mathematician's Journey Through Narcissistic Numbers, Optimal Dating Algorithms, at Least Two Kinds of Infinity, and More** *by Matt Parker, published in December 2014 by Farrar, Straus and Giroux, LLC. Copyright © 2014 by Matt Parker. All rights reserved.*