The "Secretary Problem" -
From a bygone era where mathematicians were reinforcing really terrible gender stereotypes in describing a real world situation, we got out of it a new way of modeling the process of making a decision. Namely, the decision of hiring a qualified applicant from a job pool -- the so-called Secretary Problem.
What is that problem you might ask?
We have
Ncandidates (perhaps applicants for a job or possible marriage partners). The assumptions are:
-- The candidates are totally ordered from best to worst with no ties.
-- The candidates arrive sequentially in random order.
-- We can only determine the relative ranks of the candidates as they arrive. We cannot observe the absolute ranks.
-- Our goal is choose the very best candidate; no one less will do.
-- Once a candidate is rejected, she is gone forever and cannot be recalled.
-- The number of candidatesNis known.
source
We've come a long way as a society with gender stereotypes, so we might call this problem now the "job applicant" problem, or something similar. If you think about it though, this really could be applied to any situation where one is making a decision from a crowded field.
On the surface, it might seem like a solution to this problem is completely relative to the field of applicants you have. For instance, if you are interviewing for a math teacher and the first person interviewed has twenty years of experience and dozens of local and national teaching awards, you may want to just stop the rest of the interviews right there and hire. And, you might be correct and justified in your position.
However, as we will soon observe, mathematics teaches us this might not be the optimal stopping point in the process.
Don't believe me? Try this game below for just 10 candidates to get a feel for the decision making process:
CLICK ME TO PLAY - courtesy of math.uah.edu
Just picking one candidate arbitrarily gives you a probability of success of 1/N, or in this field 1/10 = 10%. We can SO do better than this.
It should be painfully obvious, after trying this game for a few times, that picking the first candidate is a terrible decision and stopping somewhere after a few interviews or so seems to work out well. But, exactly where does one stop? What is the optimal probability?
Spoiler Alert:
We should stop after about 37% of our interviews. If doing so, we will have an optimal probability of success of 37%!!!!
Before we officially solve this problem, some assumptions/declarations:
- There are
Ncandidates, and you only are interested in selecting the best one,i - Candidates arrive randomly for the interview.
- You rank each candidate interviewing relative to the ones that you’ve seen by that point.
- No candidate can have the same relative ranking (e.g. no ties for 2nd).
- Each candidate is completely independent and their ranking has no influence
on the quality of those that follow. - At each interview,
i, you have the opportunity to accept the candidate, in which case you may not continue viewing the rest of theN − icandidates, or you may reject them and move on to thei + 1th candidate, - You will never have the option of returning to candidate
i; once a candidate is rejected
they are rejected for life.
I get that in the job process, you probably don't let someone know you are rejecting them on the spot. So the last assumption is kind of some hand waving. In the dating application however, you probably should let someone know you are rejecting them before moving onto the next candidate, but who am I to judge ;)
TIME TO GET THE MATH ON!
Let's start small - Three candidates
Assume you can "peek behind the curtain" and know the values of every candidate. We can start with some small cases and then work our way up to observe some really cool things.
With three candidates, assume arbitrarily they have the relative ranks (1, 2, 3) where 1 = Best, 3 = Worst.
Since the candidates will be arriving randomly, we have no way of knowing when the best for us will arrive. So, we consider all random permutations of arrivals and strategies for picking the best candidate. If we do that, we get the table as follows:
| Permutation | Stop after 1st Interview | Stop after 2nd Interview | Stop after 3rd Interview |
|---|---|---|---|
| (1,2,3) | 1 | 3 | 3 |
| (1,3,2) | 1 | 2 | 2 |
| (2,1,3) | 2 | 1 | 3 |
| (2,3,1) | 2 | 1 | 1 |
| (3,1,2) | 3 | 1 | 2 |
| (3,2,1) | 3 | 2 | 1 |
- If we stop after the first interview, it is obvious - we just pick that person, regardless of their rank to the field. In this strategy we are successful in getting the best candidate two times out of six.
- If we stop after the second interview, we have to adopt a new strategy. We select the first candidate we see who is better than all of the previous candidates, if possible. If no candidate better than all previous candidates appears, we accept the last candidate even if we get someone worse. For example, the reason why for (1,2,3) we select 3 is because the second person we interviewed had a worse rank (2) relative to the first person interviewed (1). Therefore we select the last person (3) because we cannot select 1 again. In this strategy we are successful in getting the best candidate three times out of six.
- If we stop after the third interview, we must select the last candidate as we have already rejected the first two. In this strategy we are successful in getting the best candidate two times out of six.
| Stop after 1st Interview | Stop after 2nd Interview | Stop after 3rd Interview | |
|---|---|---|---|
| Times Selecting Best Candidate: | 2 | 3 | 2 |
| Probability | 2/6 | 3/6 | 2/6 |
| Percent(rounded) | 33.3% | 50.0% | 33.3% |
So, our optimal decision making process here is to stop after the 2nd interview.
Let's Expand - Four Candidates:
Same logic, new field. Let's have four candidates with ranks (1,2,3,4). Again, 1 = Best, 4 = Worst.
| Permutation | Stop after 1st Interview | Stop after 2nd Interview | Stop after 3rd Interview | Stop after 4th Interview |
|---|---|---|---|---|
| (1,2,3,4) | 1 | 4 | 4 | 4 |
| (1,2,4,3) | 1 | 3 | 3 | 3 |
| (1,3,2,4) | 1 | 4 | 4 | 4 |
| (1,3,4,2) | 1 | 3 | 2 | 2 |
| (1,4,2,3) | 1 | 3 | 3 | 3 |
| (1,4,3,2) | 1 | 2 | 2 | 2 |
| (2,1,3,4) | 2 | 1 | 4 | 4 |
| (2,1,4,3) | 2 | 1 | 3 | 3 |
| (2,3,1,4) | 2 | 1 | 1 | 4 |
| (2,3,4,1) | 2 | 1 | 1 | 1 |
| (2,4,1,3) | 2 | 1 | 1 | 3 |
| (2,4,3,1) | 2 | 1 | 1 | 1 |
| (3,1,2,4) | 3 | 1 | 4 | 4 |
| (3,1,4,2) | 3 | 1 | 2 | 2 |
| (3,2,1,4) | 3 | 2 | 1 | 4 |
| (3,2,4,1) | 3 | 2 | 1 | 1 |
| (3,4,1,2) | 3 | 1 | 1 | 2 |
| (3,4,2,1) | 3 | 2 | 2 | 1 |
| (4,1,2,3) | 4 | 1 | 3 | 3 |
| (4,1,3,2) | 4 | 1 | 2 | 2 |
| (4,2,1,3) | 4 | 2 | 1 | 3 |
| (4,2,3,1) | 4 | 2 | 1 | 1 |
| (4,3,1,2) | 4 | 3 | 1 | 2 |
| (4,3,2,1) | 4 | 3 | 2 | 1 |
- Remember - if not the first or last candidate, our strategy is we select the first candidate we see who is better than all of the previous candidates, if possible. If no candidate better than all previous candidates appears, we accept the last candidate even if we get someone worse.
- This explains why, for instance, (1,2,3,4) when stopping after the 2nd interview produces 4. After two interviews, we observed we had a worse candidate than the first interview so we select the last individual (rank of 4).
| Stop after 1st Interview | Stop after 2nd Interview | Stop after 3rd Interview | Stop after 4th Interview | |
|---|---|---|---|---|
| Times Selecting Best Candidate: | 6 | 11 | 10 | 6 |
| Probability | 6/24 | 11/24 | 10/24 | 6/24 |
| Percent(rounded) | 25.0% | 45.8% | 41.7% | 25.0% |
To infinity, and beyond!
Let's run this fella out to infinity. But first...
Below would be for N = 5 candidates.
| Stop after 1st Interview | Stop after 2nd Interview | Stop after 3rd Interview | Stop after 4th Interview | Stop after 5th Interview | |
|---|---|---|---|---|---|
| Times Selecting Best Candidate: | 24 | 50 | 52 | 42 | 24 |
| Probability | 24/120 | 50/120 | 52/120 | 42/120 | 24/120 |
| Percent(rounded) | 20.0% | 41.7% | 43.3% | 35% | 20% |
And, walking up the ladder:
| Candidates | Optimal Stopping Interview | Ratio: Stopping interview/number of candidates | Probability of picking the best candidate |
|---|---|---|---|
| 10 | 4 | 0.4 | 0.3987 |
| 20 | 8 | 0.4 | 0.3842 |
| 30 | 12 | 0.4 | 0.3786 |
| 40 | 16 | 0.4 | 0.3757 |
| 50 | 19 | 0.38 | 0.3743 |
| 60 | 23 | 0.3833 | 0.3732 |
| 70 | 27 | 0.3857 | 0.3724 |
| 80 | 30 | 0.375 | 0.3719 |
| 90 | 34 | 0.3778 | 0.3714 |
| 100 | 38 | 0.38 | 0.371 |
Notice the visulization for N = 100 candidates:
[source]
That is a probability of success of about 37.1% stopping after the 38th interview. We can immediately make some pretty cool observations:
- Every time we use this process, we are generating in essence a concave down curve, with a local maximum solution.
- This solution is appearing as though it is the limit of two items. One being the ratio of the stopping interview to the number of candidates, the other being the probability of picking the optimal candidate.
Therefore, we should be able to generalize this curve for N candidates and stopping after the i th interview.
There is some heavy math I will leave out of this piece that proves this curve limits to the following function:
Here, for instance, would be our optimal curve for 100 interviews as a function of interviews:
So, in general, we have a logartihmic function that for some optimal value between 0 and 1, the ratio between the optimal stopping interview and the number of candidates produces an optimal value when we let the number of candidates approach infinity. An optimal value we will call x.
Substituting x into the equation of our optimal curve yields:
We can now use a bit of calculus to prove where the global optimal solution lies. We start by realizing we will never find a solution at the beginning (0) or end (1) of our process. Furthermore, our curve is continues and differentiable for all x on the interval from 0 to 1, so we will have some optimal value.
To find the value in the middle, we start by taking a first derivative:
We then prove this is a max by plugging into the second derivative and showing we get a negative result. This means we must have had the maximum value.
WHOA!!!
1/e, or approximately 0.37 is what optimizes our solution! Graphically:
But, what does it all mean?!?!?!?!
We can conclude the following facts from this analysis:
- The best strategy with the rules we adopted from the beginning is to reject the first 37% of our candidates
- We should select the first candidate that is better than all of the previous candidates, if they appear.
- We have about a 37% chance to find our best candidate with the rules given above.
So take a note from me, @team-leibniz, the next time you decide on a difficult breakup:
Just let your partner know the following:
"Hey, it's not me, it's totally you! You are in the first 37%!"
Very good article.
I'd like to include it in N.4 of our math-trail magazine - N.3 can be found here - hope that's OK with you.
Just let me know.
Thanks
Following you now too; I see you post on many topics but that's OK.
!-=o0o=-!
you then read this article.
Click here for Mathematics forum on chainBBTo follow curated math content follow @math-trail. If you wish @math-trail to follow
Well, I have many interests, just so happens Math is my favorite ;)
I would be honored. Thank you very kindly for the consideration!
Complex post man! Keep it up!
Thanks! This is a pretty cool problem with an elegant solution. Pretty neat that it comes up with e in it as well!
Well I hate math...
meep
I love math, even though I'm not a great practitioner at some levels :)
I enjoyed your clear and concise breakdown of the problem. Excellent work!
I'm sure you are a better practitioner than you think! Most people are, we just think we aren't when we make silly mistakes and occasionally lose patience.
Thanks much for the kind words!
click here!This post received a 1.7% upvote from @randowhale thanks to @team-leibniz! For more information,
I really enjoyed this! Thanks.