An important question in life is how many people to date before deciding on a spouse. I’m the first to admit that matchmaking is much more nuanced than what can be broken down to a formula.
The dating question is known as an optimal stopping problem. It occurs in many decision-making situations. Here are some other situations where people are faced with the optimal stopping problem:
· Consider a very tight rental market where you are looking for an apartment. In this “tight” market, one must decide on taking a lease on an apartment immediately upon visiting an available unit. If you go on and continue to shop, the unit will not be available later. So, in this situation, you can’t visit several and come back to pick the best fit for you. Is it better to just take the very first unit seen, or do you check out several units to see what is available and then pick the next unit that suits you?
· In another situation, consider you are selling property in a buyer’s market. Each week that passes with you not accepting an offer, adds to your expenses (advertising, taxes, mortgage etc.). Do you accept the very first offer, or do you wait for a better offer?
· Like the dating problem, is the “hiring problem” is a labor market where workers are scarce. In this situation, you must make an offer to a candidate immediately after the interview. That is, you can’t interview several people and choose the best because the candidates interviewed early in the process will have moved on to take other positions.
· The “parking problem” is where you are going to event. You can pay for expensive parking at the event, or you can try to find a free parking spot on the street along the way. Time constraints prevent you from exploring the neighborhood and returning to an available spot. Do you take the first available spot or do you chance driving closer?
So, in all these situations, we recognize that we will not always be able to choose the best of the available options. However, we would like to have a strategy that maximizes our probability of choosing the best option.
The approach used to maximize the probability of choosing the best option is to use a stopping rule. In the hiring problem, let n be the number of candidates and r as the stopping point. This means one automatically rejects the first r-1 candidates and then chooses the next candidate who is better than all the prior candidates. There are two suboptimal outcomes using this strategy. The first is when the best candidate is among the early group (r-1) who are automatically rejected. One would interview all the remaining candidates in this case, and none would be better than the best of rejected candidates. Next is when best candidate is late in the series and is not chosen because an earlier candidate met the criterion of being better than the r-1 group.
For a small number of candidates, we can directly determine the best r to maximize our chance of choosing the best candidate. We’ll rate the potential candidates from best to worst as: 1, 2,...n.
With 2 candidates, there are just two ways the candidates can be presented:
1-2 or 2-1
If r=1 or r=2, we have a 50% probability of picking the best candidate.
With 3 candidates, it becomes more interesting. Here are the six possible permutations:
123
132
213
231
312
321
Next, we can see how often we
choose the best candidate using different values of r. For r=1. We reject the
first r-1 candidates and pick the first that is better than those rejected. For
r=1, therefore, we pick the first candidate. Therefore, only in the first two
permutations, 123 and 132, we would have chosen the best candidate (33%).
Next, let’s try r=2. So, we reject the first candidate and choose the next
candidate who was better the first. Here how each permutation comes out.
123 suboptimal (best candidate rejected)
132 suboptimal (best candidate
rejected)
213 best candidate chosen
231 best candidate chosen
312 best candidate chosen
321 suboptimal (2 chosen before 1 is
interviewed)
So, r=2 scores the best candidate 50% of the time.
Finally, we check using an r=3. This means we reject the first two candidates. The value of r=3, like r=1, also picks the best candidate 33% of the time.
123 suboptimal (best candidate rejected)
132 suboptimal (best candidate
rejected)
213 suboptimal (best candidate
rejected)
231 best candidate chosen
312 suboptimal (best candidate
rejected)
321 best candidate chosen
We explore all possible values of r, and found our probability of choosing the best candidate is optimized at 50% when r=2. The other two values of r, r=1 and r=3, chose the best candidate 33% (no better than simply selecting the candidate randomly by chance).
With four candidates, they can be presented in 24 ways.
The table below shows the outcome of using the four values of r.
|
Order |
r=1 |
r=2 |
r=3 |
r=4 |
|
1234 |
Yes |
No |
No |
No |
|
1243 |
Yes |
No |
No |
No |
|
1324 |
Yes |
No |
No |
No |
|
1342 |
Yes |
No |
No |
No |
|
1423 |
Yes |
No |
No |
No |
|
1432 |
Yes |
No |
No |
No |
|
2134 |
No |
Yes |
No |
No |
|
2143 |
No |
Yes |
No |
No |
|
2314 |
No |
Yes |
Yes |
No |
|
2341 |
No |
Yes |
Yes |
Yes |
|
2413 |
No |
Yes |
Yes |
No |
|
2431 |
No |
Yes |
Yes |
Yes |
|
3124 |
No |
Yes |
No |
No |
|
3142 |
No |
Yes |
No |
No |
|
3214 |
No |
No |
Yes |
No |
|
3241 |
No |
No |
Yes |
Yes |
|
3412 |
No |
Yes |
Yes |
No |
|
3421 |
No |
No |
No |
Yes |
|
4123 |
No |
Yes |
No |
No |
|
4132 |
No |
Yes |
No |
No |
|
4213 |
No |
No |
Yes |
No |
|
4231 |
No |
No |
Yes |
Yes |
|
4312 |
No |
No |
Yes |
No |
|
4321 |
No |
No |
No |
Yes |
|
Times best chosen |
6 |
11 |
9 |
6 |
|
% |
25% |
46% |
38% |
25% |
The best value of r is r=2 with the best candidate being chosen 11 times in the 24 permutations of the order in which the candidates are presented.
The following table gives the best r for different sizes of n and the probability, p, of choosing the best candidate (table from Wikipedia).
|
{\displaystyle n} |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
{\displaystyle r} |
1 |
1 |
2 |
2 |
3 |
3 |
3 |
4 |
4 |
|
p |
1.000 |
0.500 |
0.500 |
0.458 |
0.433 |
0.428 |
0.414 |
0.410 |
0.406 |
As the candidate pool increases, both the value of r/n and the probability of selecting the best candidate approaches 0.368, or 1/e. Therefore, the strategy is referred to as the 37% rule.
4/21/2022 Bigthink article: The 37% rule: How many people should you date before settling down? (bigthink.com)
Vsause has a good video demonstrating the stopping strategy. The Game You Quit - Bing video
Update 3/30/2024 - another article on 37% https://www.upworthy.com/pick-a-random-number-between-100-you-probably-chose-37-and-there-s-a-big-reason-for-that
