Optimal Stopping Strategy in Dating

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