The Dating Problem

I first found out about this problem through a YouTube video by Viks recommended to me by the algorithm around two years ago.* This post will be somewhat of a ramble expanding on the problem proposed by this video. They're not the first one to think of it, but it was my first introduction to the problem (I later found out that Numberphile made a video on it as well, in the context of toilets*).

For the people who haven't watched it, it's probably best to explain what I'm talking about first:

Suppose you want to find the very best person to settle down with. You meet people one by one, and you have to decide if you want to settle down with them or reject them and move on to the next person. Once you have rejected someone there's no going back to them anymore. How do you determine who you settle down with?

It's a very simple problem, with an elegant mathematical solution. I won't go into too much depth (watch the videos for more context), but the strategy is to reject a number of people first (regardless of how nice they are) and then to accept the first person better then all of those.

The problem can be solved mathematically as follows. Suppose you reject the first r people out of n total people. Then the probability that you end up with the very best person is

Differentiating with respect to r and setting the expression to zero gives

so

This was the conclusion reached by both videos: to find the very best partner (toilet) you have to reject 37% of your options first, before accepting the first one better than everything so far. Doing so you have a 37% chance of finding the very best partner.

Having gotten this introduction out of the way, there is something that irked me about this solution: no-one actually decides based on only finding the very best partner. What if you don't get your number one pick (which happens in 63% of cases)? Then we end up having to settle with someone we might not like too much. To me it makes much more sense to optimize for a best average. That is, to get the best partner we can without having to settle for someone worse if we fail.

The next part will be a bit more math-heavy. If you just want the results, you can skip to the conclusion below (somewhat hidden in the middle, sorry).

Let X be a random variable representing the "goodness" of the partner chosen (from 1 being the worst to n being the best). For context, the previous problem could be formulated as

We would like to maximize the expected value of X:

We can calculate this expected value by introducing another random variable M, which is the best partner we found in the first r people. Lets first consider the case where n (the very best partner) is in the first r people, so M = n. This happens r in every n times, so

Next, if the second best partner is the best person in the first r people, then M = n-1. Meaning that n is not in the first r people, but n-1 is.

Notice that if n is not in the first r people, then the chance that n-1 is in there becomes slightly larger, since n is now "blocking a spot" in the last n-r places. We can do this again for n-2:

Convince yourself that this pattern repeats:

There is one asterisk we have to take note of. What happens when n-k is less than r? There are r people, so the maximum has to be at least r as well. In this case we will define the probability to be zero.

Now finally, we will clean up our probability function a little bit

You can check for yourself that this is true. Then, we can use this for our expected value. If we have that M = n-k (for k > 0), then the partner we end up with will be any of

and there is an equal chance to end up with any one of them. The average value will then be

For the last case, where k=0 so M = n, there is no partner better than any one we have already encountered. This is kind of a worst case scenario and we choose the very last person we meet. This will be anyone up to n-1 (with equal chance for each one), so

is our expected value in this case.

Putting everything together, we can say that

In the end, this simplifies quite nicely (exercise for the reader, bla bla bla) to

Then all that is left is taking the derivative with respect to r, setting it zero and solving for r:

giving us the solutions

Obviously, n and r are greater than zero, so the only solution remaining is

Nice.

After all this math we can finally say that the amount of people we need to reject is exactly one less than the square root of the total. Out of 100 people we reject the first 9. Out of 10000 we (only!) reject the first 99, then accept the first one better than those 99. Amazing right?

In the case that we don't end up on a whole number, we have to round either up or down. I can't be bothered to find out in which case you have to round down and when to round up.

There are a couple of things that amaze me about this result. First of all, that all these complex formulas collapse so nicely. But more specifically the edge case that we added. The idea that removing the k=0 term from the series and replacing it with our edge case is necessary to get a simple result is just crazy. If we had just defined our expected value as

we would have had no solution for r at all, and if we had left the first term out completely (meaning if we encounter the very best person in the first r people, we reject everyone and end up completely lonely) we would have gotten

as a result. Which is much less nice (though still somewhat nice).

A final thought (or almost) is about what the expected value would be. Plugging our solution into E gives

Though this is not exactly a clean formula for specific n, writing it in this form clearly shows that

meaning that for large enough n, we can on average get the best (though not the very best) partner we want. This is in contrast to the original solution, where plugging in

gives

so

Meaning that on average, that strategy will never give you perfect results. On the other hand, plugging in our new solution to the old probability to get the very best partner,

Of course, this is all theoretical as we all know the chance of actually finding more than one date is basically zero.

PS. Some equation were very hard to solve by hand, so I did it the lazy way. Here is the code I used to solve some of the more egregious equations:

from sympy import *

n, k, r = symbols('n k r')

P = ( r*factorial(n - r)*factorial(n - k) ) / ( (n - k)*factorial(n - k - r)*factorial(n) )
W = (2*n + 1 - k)/2

E = r/2 + Sum(P*W, (k, 1, n - r))

F = E.doit().simplify()
print(F)

D = diff(F, r).simplify()
print(D)

S = solve(D, r)
print(S)