The Secretary Problem

19 Aug 2016

Suppose that you have 12 applicants for a job, and you interview them in random order. Suppose further that immediately after you interview them, you have to either accept them or reject them. Finally, suppose that if you reject them, you can never call them back again - they get another job immediately or something. What policy would get you the highest probability of selecting the very best applicant?

The first applicant that you interview will, of course, be the best applicant so far. Suppose that your policy is to accept the first applicant. That policy clearly has a one-in-twelve chance of selecting the very best applicant.

On the other hand, if you have for some reason rejected eleven applicants and the twelfth is the best so far, then you know that you can accept them, because there are no more applicants who might turn out to be better.

It seems like you need information about the distribution of quality among the population (in order to set a quality bar of some kind), but it turns out that the “maximize the probability of selecting the best”, goal can be achieved with a simple rule of the form “Reject the first N applicants, and then accept the next applicant who is best-so-far.”