Find True Love (on a dating site, using Python)

Imagine that after having accumulated a roster of potential candidates on a dating site, you embark on the task of meeting them, one by one, in order to find your unique soul mate. Since it could be insulting, for any particular candidate, to be chosen as a result of an a posteriori analysis of the entire list, you have to make your choice on the spot, after each meeting. In other words, if you reject a candidate, you cannot call him or her back later. But if, on the contrary, you think that the candidate is the one, you have to stop searching (and live with your choice). When making a choice, you are (only) allowed to take into account the candidates met so far. If there are $n$ candidates, you can then make your choice right after the first, wait until you met them all, or anything in between. But is there an optimal policy, i.e. a moment to stop where your chances of having found true love is maximized? This is the secretary problem, and there is indeed a solution.

Let's first implement a guessing function, which takes a list of numerical values (e.g. an "attractiveness score", or if you are Bayesian-minded like some, a prior belief in a good match with each candidate) and a cutoff point, which can be anywhere inside this list (start, end, or in between):

In [1]:

def guess_max(values, cutoff):
    before = values[:cutoff]
    max_before = max(before) if before else -1
    after = values[cutoff:]
    return next((v for v in after if v > max_before), values[-1])

If we create a list of 1000 candidates (with random attractiveness values, between 0 and 1), we can use this function with different cutoff strategies, to see what happens:

In [2]:

import random
n = 1000
candidates = [random.random() for _ in range(n)]
max(candidates) # real answer

Out[2]:

0.99992538253578345

In [3]:

guess_max(candidates, 0) # choose first

Out[3]:

0.33486707420570316

In [4]:

guess_max(candidates, n-1) # choose last

Out[4]:

0.046756671317170762

In [5]:

guess_max(candidates, int(n/2)) # stop at midpoint

Out[5]:

0.99992538253578345

These results are of course not conclusive, because the candidates could be in any order, and our policy must thus be studied in a probabilistic way. Let's do this by simply retrying a policy a certain number of times (each time reshuffling our set of candidates), and count the number of times it's right:

In [6]:

def est_prob_of_being_right(values, cutoff, n_trials=1000):
    max_val = max(values)
    n_found = 0
    for trial in xrange(n_trials):
        random.shuffle(values)
        n_found += 1 if guess_max(values, cutoff) == max_val else 0
    return n_found / n_trials

If we do this in a systematic way, by sweeping the range of possible cutoffs:

In [7]:

cutoffs = range(0, n, 10) # try a cutoff value every 10
probs = [est_prob_of_being_right(candidates, cutoff) for cutoff in cutoffs]
plot(cutoffs, probs)

Out[7]:

[<matplotlib.lines.Line2D at 0x7f128027d7d0>]

the coarse and surprisingly shaped probability distribution that results suggests that the optimal policy is to stop searching after you have met about $40\%$ of the candidates, in line with the exact solution, which is to stop rejecting after the $n/e$ first candidates have been seen, and proceed from there to pick the first most promising one so far, with whom the probability of true love will be highest, at $1/e$ ($\approx36.8\%$). If you want to understand why, these explain it well.

Tweet