Exploration versus Exploitation: Deciding When to Get Married

There's all this hype about the importance of using data to support critical business decisions. But few things can be more important in someone's life than choosing the partner they plan to spend the rest of their lives with. This post presents a data-driven approach to support this critical decision: when should you stop dating and finally get married?

Here is the formal setup for the problem: there are $N$ potential marriage partners out there, and I want to choose the one and only partner of my life. My goal of course is to settle with no-one but the very best partner to marry. I can 'date' each candidate sequentially in a random order. When I date someone, I can evaluate how she ranks in comparison to all previous partners I dated before. Based on this, I can either go on and marry her in which case the process stops, or reject her and carry on dating more partners. Once a partner was rejected she cannot be called back again.

This problem is hard, because it's assumed that I know nothing about a partner before I actually dated her. Also, there is no information available about the pool of candidates so the only way to explore the space is by dating random candidates. Some might immediately recognise the typical problem of exploration versus expoitation: how much time should I spend exploring alternatives versus just greedily exploiting the policy which appears optimal now.

So when should I stop dating and marry someone? Let's say I want to maximise the probability of ending up with the best partner as wife. Firstly, there's no point in selecting someone who's not the best I have dated so far, because that also implies she cannot be the best overall. Also, the earlier you marry, the higher the chance of missing out on someone without even dating her. It turns out the optimal strategy is as follows:

date the first $k$ candidates and reject them irrespective of their 'performance'. Then, keep on dating partners, and choose the first one, who ranks above everyone I dated before.

The threshold $k$ where you stop looking should depend on $N$. It turns out that in the optimal strategy $k$ is about a third of all candidates, more precisely $k \approx \frac{1}{e}N$. (see slides for details).

I gave a talk about this theory in our lab at Cambridge not long after getting married, and did a quick back-of-the-envelope calculation to see how close my marriage decision was to the optimal. The theory predicts based on my criteria I should've dated roughly $196,132$ partners before getting married. Well, I leave it to you to guess whether I did that or not :) But at the end of the day I ended up making the best decision, so it doesn't matter.