• 아티클

September 2016

Volume 31 Number 9

[Test Run]

The Secretary Problem

By James McCaffrey

James McCaffreySuppose you want to hire a secretary. You have a pool of 100 applicants and you interview one applicant per day. After each interview, you must immediately decide to hire the current applicant or not. If you don’t hire an applicant, you can’t call her back. You don’t have time to interview all 100 candidates, so what algorithm can you use to maximize your chance of selecting the best applicant?

What I’ve just described is one example of the Secretary Problem. Solutions to the Secretary Problem have many important uses. For example, in machine learning, it’s often necessary to come up with some approach for stopping training in a way to optimize the probability of selecting the best prediction model.

The Secretary Problem is part of a larger class of problems sometimes called best choice problems, and also part of what are called optimal stopping problems. To the best of my knowledge, a description of the Secretary Problem (in a slightly different form) was first published in Scientific American magazine in 1960. There are dozens of interesting variations of the problem.

In this article I’ll show you how to tackle the Secretary Problem using what’s called the 1/e stopping rule. A good way to see where this article is headed is to examine the demo program in Figure 1. I coded the demo using C#, but you shouldn’t have any trouble refactoring the code to another language if you wish.

Secretary Problem Demo Program Run
Figure 1 Secretary Problem Demo Program Run

This article assumes you have at least intermediate programming ability, but doesn’t assume you know anything about the Secretary Problem. The complete source code for the demo program is presented in this article, and you can also get the source from the accompanying code download.

The 1/e Stopping Rule

It can be mathematically proved that, subject to certain conditions, you can theoretically maximize the probability of selecting the best applicant in the Secretary Problem by using what’s called the 1/e rule or algorithm. In the context of the Secretary Problem, the term Candidate means the best applicant seen at a given point in time. I capitalize the word Candidate to emphasize that the word has a different meaning than in normal English, where a candidate and an applicant are essentially synonymous.

In the following explanation, N represents the total number of applicants, and e represents Euler’s constant, which is approximately 2.71828. In words, the 1/e rule is, “Skip over the first N / e applicants, but track the best Candidate. Then hire the first Candidate who appears. If no new Candidate appears after the first N / e applicants have been skipped, then fail and hire nobody.”

A concrete example should make the algorithm clear. The 1/e stopping algorithm is illustrated graphically in Figure 2. Suppose you have 10 applicants. Each applicant has (unknown to you until after you interview them) a rating between 0.0 and 9.0, where higher values are better. The applicants’ ratings are:

(5.0, 2.0, 7.0, 1.0, 4.0, 0.0, 8.0, 3.0, 9.0, 6.0)
  0    1    2    3    4    5    6    7    8    9

The 1/e Algorithm for the Secretary Problem
Figure 2 The 1/e Algorithm for the Secretary Problem

Applicant 0 has a rating of 5.0 and will be interviewed first; applicant 1 has a rating of 2.0 and will be interviewed second; and so on. The best applicant is person 8 with a rating of 9.0.

The number of applicants to skip is N / e = 10 / 2.71828 = 3.6788, which is 3 if truncated, and 4 if rounded. As it turns out, as long as N is not very small it makes very little difference whether you truncate or round. Suppose you truncate to 3.

You interview applicant 0 and find she has a rating of 5.0, so she becomes the Candidate because she has the best rating seen (so far, the only rating seen). Next, you interview applicant 1 and find they have a rating of 2.0 so they don’t become the Candidate because their rating isn’t better than 5.0. You interview applicant 2 and find a rating of 7.0 and they become the new Candidate. At this point you’ve interviewed the first N / e = 3 applicants so you’re now ready to hire the first new Candidate who appears.

You interview applicant 3 and find a rating of 1.0 so they don’t become the Candidate. You interview applicant 5 and find a rating of 0.0 (Ouch! I’ve worked with this person) so they’re not the Candidate, either. You interview applicant 6 and find a rating of 8.0. This is the highest rating seen so they become the Candidate, and because you’re past the first N / e applicants, you immediately hire applicant 6.

Notice that the 1/e algorithm did not find the best applicant in this example, but did find the second best applicant. If you use the 1/e algorithm for the Secretary Problem, the probability that you’ll select the best applicant from N applicants is approximately 1 / e = 1 / 2.71828 = 0.3679.

The Demo Program

To create the demo program, I launched Visual Studio and made a new C# console application program named SecretaryProblem. The demo program has no significant .NET dependencies, so any version of Visual Studio will work. After the template code loaded, in the Solution Explorer window, I right-clicked on file Program.cs and renamed it to the more-descriptive SecretaryProblemProgram.cs and Visual Studio automatically renamed class Program for me. At the top of the Editor window, I removed all using statements that referenced unnecessary namespaces, leaving just the one reference to the top-level System namespace.

The demo program has two parts. The first few lines in the Main method illustrate the 1/e algorithm when applied to a specific Secretary Problem example with 10 applicants. The second part of the demo illustrates a simulation where the 1/e algorithm is run 10,000 times with 100 applicants.

The key lines of calling code for the first part of the demo are:

double[] ratings =
  new double[] { 5.0, 2.0, 7.0, 1.0, 4.0, 0.0, 8.0, 3.0, 9.0, 6.0 };
Console.WriteLine("Applicant ratings are: \n");
for (int i = 0; i < ratings.Length; ++i)
  Console.Write(ratings[i].ToString("F1") + "  ");
Console.WriteLine("\n");
int selected = Select(ratings, true);  // Verbose

A problem is set up by defining applicants as an array of type double where the index represents an applicant ID, and the cell value represents an applicant’s rating. The basic version of the Secretary Problem assumes that all applicant ratings are different, so there can be no ties.

The program-defined Select method accepts a rating array and uses the 1/e algorithm to find and return the index of the selected applicant. The Select method has a lot of WriteLine statements that print progress, as shown in Figure 1.

The key lines of calling code (with minor editing for readability) for the second part of the demo are:

int numHiringSessions = 10000;
int numApplicants = 100;
double pBest = Simulation(numApplicants, numHiringSessions);
Console.WriteLine("Simulation prob of best applicant  = " +
  pBest.ToString("F4"));
double pTheory = 1 / Math.E;
Console.WriteLine("Theoretical prob of best applicant = " +
  pTheory.ToString("F4"));

The program-defined Simulation method accepts a fixed number of applicants. An alternative design is to allow the simulation to randomly select the number of applicants in each trial. Behind the scenes, the Simulation method loops, calling a non-verbose version of the Select method, while keeping track of the number of times the best applicant was selected.

The Select Method

The definition of the Select method begins as:

static int Select(double[] ratings)
{
  int numApplicants = ratings.Length;
  int numSkip = (int)(numApplicants / Math.E);
  int candidate = 0;  // Best applicant seen
  double bestRating = ratings[0];
  double rating = 0.0;
  bool readyToHire = false;
...

The number of applicants is determined by the number of cells in the ratings array. You could make this explicit by passing an additional parameter N to Select. Variable numSkip is the number of initial applicants to skip over while tracking the best applicant so far. If you wanted to round instead of truncate, you could write:

int numSkip = (int)Math.Round(numApplicants / Math.E);

Variable candidate is the best applicant seen at any point in time during the hiring process and variable bestRating is the rating associated with the Candidate. The two variables are initialized to the values of the first applicant, rather than using dummy values such as -1 and -1.0, respectively.

Variable rating represents the rating of the current applicant, and is just for readability. Boolean variable readyToHire is false when processing the first numSkip-1 applicants, then set to true afterward.

The body of method Select is short and relatively simple:

...
  for (int applicant = 0; applicant < numApplicants; ++applicant) {
    rating = ratings[applicant];
    if (applicant >= numSkip) readyToHire = true;
    if (rating > bestRating) {
      candidate = applicant;
      bestRating = rating;
      if (readyToHire == true) return candidate;
    }
  }
  return -1;
}

The method walks through each applicant in the ratings array. For each applicant, the current applicant becomes the Candidate if the current applicant’s rating is greater than the best (highest) rating seen. When Boolean variable readyToHire is false, Candidates are identified but not returned. When readyToHire is true, the first available Candidate found is returned, corresponding to an immediate hire in the Secretary Problem.

An alternative design is to use two loops instead of a single processing loop, where the first loop iterates over the applicants to skip, and the second loop identifies the first available Candidate:

// 1. prelim loop
for (int applicant = 0; applicant < numSkip; ++applicant)
{
  // Track best rating seen
}
// 2. hiring loop
for (int applicant = numSkip; applicant < numApplicants; ++applicant)
{
  // Return first Candidate found
}

It’s possible that no new Candidate will appear after the first numSkip applicants. For example, suppose you have eight applicants with ratings (7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0, 0.0). Variable numSkip would be set to 8 / 2.71828 = 2. After the first two applicants are interviewed, the best rating would be 7.0 and none of the remaining six applicants would be identified as a Candidate. Method Select returns a dummy value of -1 when no Candidate is found.

The Simulation Method

In high-level pseudo-code, the Simulation method is:

generate applicants / ratings
determine optimal rating
set number_times_best_applicant_selected = 0
loop numTrials times
  randomize order of applicants
  select an applicant using 1/e algorithm
  if selected applicant is optimal
    ++number_times_best_applicant_selected
  end-if
end-loop
return number_times_best_applicant_selected / numTrials

The definition of method Simulate begins with:

static double Simulation(int numApplicants, int numTrials)
{
  double[] ratings = new double[numApplicants];
  for (int i = 0; i < numApplicants; ++i)
    ratings[i] = (i * 1.0);
  double optimalRating = 1.0 * (numApplicants - 1);
  int numBestSelected = 0;
...

As described earlier, applicants and their ratings are stored in an array where the array index is the applicant ID, and the cell value is the rating. The value in cell 0 is set to 0.0, the value in cell 1 is set to 1.0, and so on. For example, if there are N = 100 applicants, the applicant IDs are 0 through 99 and the optimal rating is 99.0.

The main processing loop in method Simulation is:

for (int trial = 0; trial < numTrials; ++trial) {
  Shuffle(ratings);
  int selected = Select(ratings);
  if (selected == -1)  // failed to select an applicant
    continue;
  double rating = ratings[selected];
  if (rating == optimalRating)
    ++numBestSelected;
}

A program-defined method named Shuffle rearranges the ratings in-place using the Fisher-Yates mini-algorithm:

static void Shuffle(double[] ratings)
{
  for (int i = 0; i < ratings.Length; ++i)
  {
    int ri = rnd.Next(i, ratings.Length);  // random index in [i, N)
    double tmp = ratings[i];
    ratings[i] = ratings[ri];
    ratings[ri] = tmp;
  }
}

The Fisher-Yates algorithm is often used in machine learning and simulation programs to shuffle the values in a linear collection. Many programming languages, for example Python and R, include a built-in shuffle method as part of their standard function library. Here, the program-defined Shuffle method assumes the existence of a class-scope Random object:

class SecretaryProblemProgram
{
  static Random rnd = new Random(0);
  static void Main(string[] args)
  {
...

After the ratings are randomized, the processing loop in method Simulation calls the Select method to pick an applicant using the 1/e algorithm, and then the selected applicant is checked to see if they’re the optimal applicant.

When checking for the optimal candidate, two floating-point values are compared for exact equality:

if (rating == optimalRating)
  ++numBestSelected;

This approach is usually a bad idea because some floating-point values are stored only as approximations, to a fixed number of decimal points. The compare-for-exact-equality approach is OK in this particular example, but in general you’d want to compare for very closeness rather than exact equality.

Wrapping Up

The information presented in this article is based primarily on the 2003 research paper, “Analysis of Heuristic Solutions to the Best Choice Problem,” by W. Stein, D. Seale and A. Rapoport. You can find the paper in PDF format in several places on the Internet. The paper presents a mathematical analysis of the 1/e rule and two additional rules.

The “candidate count” rule arbitrarily selects the nth Candidate. For example, if n = 3, the third Candidate encountered will be selected. In the example presented at the beginning of this article, where the applicants and ratings are (5.0, 2.0, 7.0, 1.0, 4.0, 0.0, 8.0, 3.0, 9.0, 6.0), the third Candidate is applicant 6 with a rating of 8.0, which coincidentally is the same as the 1/e rule. As it turns out, the candidate count rule is not very effective.

The “successive non-candidate” rule selects the first Candidate seen after observing k non-Candidates. For example, suppose k = 3. For the example applicants and ratings, the first k non-Candidates have ratings 2.0, 1.0 and 4.0. The next Candidate is applicant 6 with a rating of 8.0, which again is, coincidentally, the same as the 1/e rule. The successive non-candidate rule turns out to work quite well.

Once you become familiar with the general structure of the Secretary Problem, you’ll find quite a few scenarios where the key principles are relevant. Whenever you’re faced with a programming task that involves an uncertain stopping point, the ideas of the Secretary Problem might be useful.

Dr. James McCaffrey works for Microsoft Research in Redmond, Wash. He has worked on several Microsoft products including Internet Explorer and Bing. Dr. McCaffrey can be reached at jammc@microsoft.com.

Thanks to the following Microsoft technical experts who reviewed this article: Chris Lee and Kirk Olynyk

Discuss this article in the MSDN Magazine forum