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):

```
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:

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

```
guess_max(candidates, 0) # choose first
```

```
guess_max(candidates, n-1) # choose last
```

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

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:

```
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:

```
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)
```

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.

Unfortunately, this assumes we have a good scoring function which in matters of the heart I believe is tricky!

ReplyDeleteThis would be the right strategy if we did though :-)

Of course I agree, that's the hard part! But I believe that under a Bayesian perspective, if we replace "score" by "prior belief", then it becomes clear that this policy would be the most rational thing to do, in terms of maximizing your gain with the limited and imperfect information you got. Implementing it in practice would be another story though.. :-)

DeleteHope everything is going well for you by the way! Cheers

I'm not sure that you can really do "the most rational thing to do" when you're searching the love of your life, but maybe that's me :p

Delete