In his fascinating book, A Man For All Markets, Edward Thorp trots out a problem called the “secretary problem” and breezily gives us the solution (pp.263-4).
“Assume that you will interview a series of people, from which you will choose one. Further, you must consider them one at a time, and having once rejected someone, you cannot reconsider. The optimal strategy [the one that maximizes the probability of picking the best one] is to wait until you have seen about 37 percent of the prospects, then choose the next one you see who is better than anybody among this first 37 percent that you passed over. If no one is better you are stuck with the last person on the list.”
But why should this be? What’s so special about looking at but not selecting the first 37% of applicants and then leaping to select the next candidate who comes along who’s better than any of the first 37%? You can look up the mathematical solution to the problem. But is there a simpler way to get this result, a more intuitive way to understand why 37%?
There is. It’s through simulation. Let’s set it up.
The Look-Then-Leap Algorithm
Suppose we have n elements that are rank ordered from 1, 2, …, n. The elements are jumbled up so the rank ordering is messed up. For instance they are jumbled up as 4, 56, 73, 1, …, n, 32. We can only see the elements one at a time. The only choice we can make is to either select or reject an element when it is presented to us.
If the objective of the game is to maximize our chances of selecting the best element (which we’ll designate as element 1, second best as element 2, and so on), what strategy should we adopt? That is the secretary problem. It might seem like there’s no good strategy. But as Thorp pointed out, there is.
The winning strategy is to adopt the Look-Then-Leap algorithm where you switch from look to leap once you’ve looked at 37% of the total number of items.
Here are the steps of the look-then-leap algorithm:
- Look at and reject the first k items where k < n
- Go to the next item in the list – if this is the last item, choose it and STOP
- Check if the item is better than any of the k items
- If yes, then choose the item and STOP
- If no, then GO BACK TO STEP 2
Simulating the Solution
The secretary problem has the following characteristics:
- We have a finite list of things to choose from
- These things appear before us one by one
- They can appear in any order
- The items are ranked — the higher the rank, the better the item
- We don’t want to leap too early or we’ll risk missing a better candidate who is yet to appear
- We don’t want to leap too late or we’ll risk rejecting the best candidate
There are many problems that fit these simple constraints. In their book Algorithms To Live By, Brian Christian and Tom Griffiths point to hunting for an apartment in San Francisco a hot market or finding a mate as examples. My colleague Kevin Gabbard generated this list of similar problems.
In general, if we had 3 candidates (the best ranked 1, the second best ranked 2 and so on), they could appear for interviews in any one of 6 orders: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]. Let’s apply the Look-Before-You-Leap algorithm by looking and always rejecting the first one and then leaping for the next best one. Since we have 3 items, looking at the first one and leaping thereafter means leaping after 33% of the candidates have been observed.
If we look at the first candidate and reject them and then leap for the better candidate, 50% of the time we end up with the best candidate. While not great, this is significantly better than choosing at random which yields the best candidate only 33% of the time.
And so on with 4, 5, and any number of candidates. But as the number of candidates grows, the number of permutations grows very quickly. While there are 6 ways in which 3 distinct things can be permuted, there are more than 3.6 million ways in which 10 distinct things can be permuted. So in order to simulate the situation of selecting from a pool of 100 candidates, we can’t possibly check all permutations in which they appear.
Rather, we’ll start with the candidates in order 1, 2, 3, …, 100 as one of the possibilities. We’ll then scramble up the order randomly many thousands of times to simulate a the experiment of choosing a candidate based on the Look-then-Leap algorithm. Each time we pick a candidate based on the look-then-leap algorithm and then at the end of the run of simulated trials we check to see what proportion of the picks are picks of the best candidate.
Here are the results when we simulate 200,000 trials for a pool of 10 candidates and then for a pool of 100 candidates.
With 10 candidates to choose from in total, we were told that the best strategy is to look at 3 or 4 candidates first, reject them and then choose the next candidate who’s better than the ones initially rejected.
The simulation indeed validates looking at (roughly) 37% of the pool before leaping. The simulation also reveals three other curious facts:
- The probability of choosing the best candidate is also around 37%. So you look at 37% percent of the pool before you leap; and once you leap, you have a 37% chance of selecting the best candidate. This is a neat coincidence!
- The probability of choosing the best candidate is significantly higher than choosing the second or third best candidate. This is quite counter-intuitive and usually not the way things tend to be.
- And finally, it doesn’t matter if there are 10 candidates or 100 (or any number): you should always leap after you’ve looked at 37% of the pool in order to maximize the probability of selecting the best candidate.
We can check this third point by simulating the look-then-leap algorithm for a pool of 100 candidates.
In their book Algorithms to Live By, Brian Christian and Tom Griffiths underscore the miraculous nature of this third point (p.15):
“If we were hiring at random, …then in a pool of hundred applicants we’d have a 1% chance of success [of hiring the best applicant], in a pool of a million applicants we’d have a 0.0001% chance. Yet remarkably, the math of the secretary problem doesn’t change. If you’re stopping optimally, your chance of finding the single best applicant in a pool of hundred is 37%. And in a pool of a million, believe it or not, your chance is still 37%. Thus the bigger the applicant pool gets, the more valuable knowing the optimal algorithm becomes. It’s true that you’re unlikely to find the needle the majority of the time, but optimal stopping [i.e., using the look-then-leap algorithm] is your best defense against the haystack, no matter how large.”
Comments or opinions expressed on this blog are those of the individual contributors only, and do not necessarily represent the views of Gartner, Inc. or its management. Readers may copy and redistribute blog postings on other blogs, or otherwise for private, non-commercial or journalistic purposes, with attribution to Gartner. This content may not be used for any other purposes in any other formats or media. The content on this blog is provided on an "as-is" basis. Gartner shall not be liable for any damages whatsoever arising out of the content or use of this blog.