The saying goes that you should quit when you're ahead. Making a decision on when to conclude a selection process is often not that easy in real life. In mathematical statistics, a puzzle known as the "secretary problem" [1] sums this up nicely. A number of candidates are applying for a secretary position at a company. In the selection process, the employer must decide after each interview, whether to accept the candidate or reject them and hope for a more suitable applicant later on. The decision is final, the employer is not allowed to invite back any rejected applicants.

An employer who is thinking logically should carefully check the first few candidates and not simply take the first one. Later, when the line starts to come to an end, the employer will possibly take on a more-or-less suitable candidate for fear of being left with only unsuitable candidates, and – not having any other options – grudgingly just bite the bullet, and grab whoever is left.

Ideal: 37 Percent

How should the employer proceed to mathematically ensure the best possible odds of finding an above-average candidate? How long should the try-before-buy phase last, in which the employer explores the unknown capabilities of candidates before immediately snapping up the one that is better than all the previous ones and hopefully scores favorably against future candidates further down the line? Mathematicians have been tackling stop problems [2] for thousands of years.

As the recently published book Algorithms to Live By [3] entertainingly explains, the answer is 37 percent, or more precisely 1/e * 100%. Given 100 candidates, an employer is well advised to check out the first 37 without any intention to employ anyone, just to gain some idea of the talents available on the labor market. As of candidate number 38, smart bosses then immediately sign a contract if one candidate is obviously better than all the previous ones.

Love-Crazed Stargazers

This task is also known as the wedding problem. The story of the famous star gazer Johannes Kepler, who was desperately looking for a new wife after the death of his first wife in 1611, is legendary. With meticulous mathematical skills, he launched himself into a lengthy process of research, looking at no less than 11 candidates. Completely exhausted and remorseful, he then returned to candidate number five, proposed to her, and to his great joy luckily received a glowing "Yes!" as an answer to his question.

Simulating Reality

To work your way through the secretary problem with a Perl program, the script needs to make some assumptions about the distribution of the supply in the labor market. The controversial "20-70-10" rule of American tycoon Jack Welch [4] dictates that the 20 percent top performers in a company return exceed expectations, 70 percent work quite well, and 10 percent are unproductive. For the experiment, we let the labor market also follow this scheme; the available talents thus roughly lie on the bell curve of a Gaussian normal distribution (Figure 1).

Figure 1: The Gaussian bell curve of normally distributed events (from Wikipedia; public domain).

Because the candidates arrive in random order, the script needs a random generator that outputs a normally distributed pool of talents. The random_normal function of the Math::Random CPAN module already has such a generator; in Listing 1 [5], it uses the parameters 100_000, 10, 2 to return 100,000 random values that fluctuate around the mean value of 10 with a standard deviation of 2.

To check whether the distribution also roughly meets the requirements visually, Listing 1 uses the get_histogram() function from the Statistics::Histogram CPAN module to print a histogram of distributed values as ASCII art on the command line. The bell shape is indeed visible (Figure 2), and although the maximum of the random data is at around 10, the frequency drops off towards both sides, and there are hardly any values less than 4.5 or greater than 15.5.

Figure 2: Histogram of events following a bell curve.

The script for simulating the secretary interviews (Listing 2) takes on the randomly arriving candidates one by one. Following the 37 percent rule, it breaks down the @data array into two parts. The first part, stored in @look, contains the first 37 percent of the random numbers, which are merely for analysis of the labor market without any intention to employ; the second part (@act) contains the other 63 percent; the employer will immediately make a decision here if one of the candidates is better than all previous encountered ones. Line 41 stops the script when this occurs.

If no better candidate shows up by the end of the array, the boss has lost out and has to employ the last candidate as a final option, which is what line 46 does. If the script is called with the --verbose option, line 9 of Listing 2 switches Log4perl's logging function to debug mode to produce diagnostic messages on how the hiring process is proceeding.

The script then outputs a number of messages to standard output at run time. Figure 3 shows that the bar for the candidates during the screening stage was at 11.05, and then at 11.52. In employment mode, a number of candidates with suitability values below the previous record of 11.52 then follow, before one with a value of 11.68 gets the job.

Figure 3: The selection process for secretaries, first run.

Although the procedure has been proven to be optimal, it still often goes wrong. Figure 4 shows a run in which a candidate with an extremely high suitability value (12.84) interviews during the test phase, a value that puts all the others later in the employment round to shame. Bad luck, the boss has to take the last candidate with a rating of 9.36.

Figure 4: This procedure does not always turn out well for the boss.

How often do these embarrassing and significant suboptimal outcomes occur in the algorithm? To measure this, Listing 3 calls the secretary script 100 times and measures how often a candidate is given preference although they are below average. The Stats::Histogram CPAN module shows the distribution.

Figure 5 shows that the procedure finds a useful candidate in about 80 percent of the cases, including some superstars with ratings of 12 and more. However, it failed in 20 percent of cases where the boss had to take on the last candidate, whether they were a star or a clown. All told, the strategy is optimal; check out [1] for the mathematical proof.

Figure 5: In 20 percent of cases, the boss has to take the last candidate.