Brian Christian and Tom Griffiths begin their popular science book Algorithms to Live By with none other than the famous Secretary Problem, more formally known as Optimal Stopping. For those unfamiliar with this problem, it outlines the optimal algorithm for picking a new secretary based on his credentials. The selector has two serious limitations — she has no idea what a good secretary looks like, and she must pick a secretary immediately after reviewing his credentials. She must therefore compare the applicants with one another. This is the predicament: select too early, and you may not have enough information to make a good choice; select too late, and you may have missed your opportunity at the best candidate.
The authors do tell the solution to the problem. The answer is 37%. If you want to maximize your chances of getting the best “secretary,” pick the best option you have seen after you have seen 37% of the candidates. The authors also point out that, in a great moment of mathematical symmetry, you will have a 37% chance of selecting the best candidate when you follow this rule. Business Insider and The Washington Post have posted their own articles on this phenomenon, and, along with the book, recommend to heed this as wisdom in your daily life.
The book clearly defines the caveats to this algorithm, and it also covers additional criteria for consideration. One such criteria is the cost of waiting. If the value of each secretary decreases by 1%, the optimal value decreases to 31%. In fact, participants in an experiment tended to choose their secretary after hitting 31%, showing that humans can indeed make optimal choices with the information available.
Yet, imagine yourself an ignorant employer trying to hire a secretary. Are you hoping to maximize your chances of getting the single best secretary that applies? Most employers likely just want to get the best employee possible, so the algorithm should optimize on average quality of the employee and not on the chances of getting the single best employee. One might believe that optimizing for either would achieve the same results. I decided to run a simulation in order to see for myself.
I wrote a 28 line Python script that plainly simulates the Secretary Problem with an applicant pool of 100 secretaries. New secretaries receive a random quality value, and the employer chooses the best value she has seen so far after hitting a specific threshold. The script repeats this selection 1 million times in order to get a statistically significant set of data. The script does this for all integer thresholds from 3 to 99. The simulation has two outputs per threshold — the average quality value of the secretary and the percentage of times that the best secretary was chosen. The results are below.
The green chart shows the secretary problem as we know it. The curve peaks nicely at 37% and does indeed give a 37% chance of selecting the best secretary. The second graph paints a more dismal picture. The average value of the secretary that the employer will choose only increases initially as she increases her threshold. The graph peaks at a threshold of 9 or 9% since we chose a pool of 100 secretaries. This means that the employer should pick the best secretary that she has seen after looking at only 9 secretaries, if she wants to optimize the quality of secretary that will work for her. She will sacrifice some of her chances of picking the best secretary possible — a chance of ~24% with a 9% threshold, but the quality of her secretary will be, on average, ~9 on a scale of ten as compared to ~8 at the 37% threshold.
The secretary problem appears frequently in our day to day life. Most cite its use as a means to select marriage partners. One should select his marriage partner 37% of the way through the dating process if he has found the best partner so far. Most people likely do not take such a mechanical approach to their love lives, but when making these decisions, consider optimizing the quality of your choice and not the chances of picking the very best choice. You may have to commit to a choice sooner than feels natural, and you may feel regret of not waiting for the best. You will, however, save yourself from a sub-standard result.