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.
Optimal stopping -
Wikipedia
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
