The Secretary Problem

---------------------------------------------------------------------------------------------------------------------------

I started a new book this week about applying algorithms in our daily lives. One of the examples cited is about "optimal stopping problems." The theory of optimal stopping (or early stopping) is concerned with the problem of choosing a time to take a particular action, in order to maximize an expected reward or minimize an expected cost. Optimal stopping problems can be found in statistics, economics, and finance - and in everyday life.

Here's a fun example - known as "the dating problem" or "the secretary problem" from Slate magazine in December 2014.

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.

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?

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 10th 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 during the 1950s. 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, Lindley calculated that if you interview the first 37 percent (the ratio 1⁄e, where e is the exponential number 2.718281828 (otherwise known as the base of the natural logarithm)) 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.

Wait! Is it 0.37 × n instead of √n? Which one is right?

The original secretary problem assumes that you have an all-or-nothing attitude. Lindley proved 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; the result -- 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. 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.

As with all techniques like this, it is important to remember the key assumptions. In this case, I think one of the ket assumptions is once you pass on a person, you can't go back. Certainly this is not usually the case when you are interviewing someone for a job. Most firms take weeks to decide on whether someone is the right choice! But it is still an interesting analysis.