The Secretary Problem
Introduction
The Secretary Problem occurs when we have to choose the best option among the ones available while deciding to reject or accept an option quickly. A common example is interviewing 100 employees and selecting the best one with optimal probability. Another example is checking different houses to rent or buy (e.g. when moving to another country) and choosing the best one.
If we were able to to interview every single house or employee and then select the best with hindsight, this would be an easy task. Although, the twist is that, after interviewing or checking an option, we need to reject or accept it instantly; we cannot go back to an option that we have already rejected.
Approaches
Let’s consider the former example: 100 employees. At first, it might seem almost impossible to select the best employee, as there are so many and we might reject the best one expecting someone better next in the line.
You might think to interview the first 90 employees and reject them all, and then select the next best. However, doing so would result in a very high chance of losing the best employee: he or she would have most likely been interviewed in the first 90. So, how should we do it?
Optimal Method
The best approach to selecting the best employee is first interviewing and rejecting the first 37, and then hiring the person who is better than all those who have been interviewed. In this scenario, if the best has been rejected in the first 37, then we would go all the way to the 100th employee and hire him/her - which is why this isn’t the perfect model.
This approach gives us a 37% chance of winning (if the number of options isn’t too large*). This is actually quite impressive as this approach gives us a much better chance of selecting the best option. Going with intuition or random chance would generally give a much lower probability of success.
* When there are few options, the chance of success is slightly higher. Say, for example, we have 2 people. Here, 37% of 2 is 0.74 ≈ 1. We reject the first person, and hire the second one. This gives a 50/50 of selecting the best. Simply put, the probability converges to 37% (or exactly 1/e ≈ 0.368 ≈ 37%) as the number of options increase.
Math
If you are interested in the math behind these probabilities and where 37% (or 1/e) is derived from, you can read this. article which explains it quite clearly. (Note that to understand it, you would need to know some calculus and have general high school math knowledge).
If you don’t understand the math, here’s a brief intuitive explanation. So, using the example of 100 options, imagine a line of the 100 options, where the best option can be anywhere. There’s a 37% chance that it is in the first 37 options. So 37% of the time, we would get it wrong from this case. If this does not happen, there is another chance that after the 37th option, there is a non-best option, which we would select - thus not choosing the best one (which would be another 26% of the time). These cases would add up to us being wrong 37 + 26 = 63% of the time, and thus a 37% success rate.
Further Applications
An interesting real life application of this problem is choosing a marriage partner. In this case, we would date the first 37% of potential marriage partners, and then select the one that is better than all the previous ones dated. Obviously, there is a chance that this ‘best’ partner we select might not want to marry us (what if they are also applying this problem to real life, and you are in the first 37%) - which is what makes this application imperfect, yet interesting.
Problems & Assumptions
This model does have some problems, however. In real life, it’s hard to assign a ‘rating’ or quantify how good someone or some object is. In the hiring scenario, the model assumes that we know perfectly how good a certain employee is, and thus we can reject or accept them easily. However, realistically, it might be hard to tell whether the current employee interview (after the 37th) is better than all the ones before.
Of course, if all the options are very distinct in their qualities (for example, there is a clear best option), then this problem is slightly alleviated. Conversely, if all the options are of a similar quality (no clear winner), it would be difficult in deciding which the best one is.
