A friend of mine recently asked me if his girlfriend “could be the one”. He should have known better. I don’t mean about knowing whether his girlfriend is the one, although admittedly he has been married before. I mean about asking me such a question and not expecting a mathematically-derived response. My post details my answer and will help those you who want the optimal strategy for choosing their partner. But remember, if my wife asks … it was always just from the heart.
The “bride problem” is a well-known conundrum. The basis of the problem is how does my friend select the best bride from the \(N\) people he knows, when he can only date one at a time and has to decide whether to propose or break up before moving on to the next. Once he’s broken up with someone, there is no going back. If he hasn’t proposed by the time of the last candidate, he will be stuck with them ’till death do them part’. What strategy should he choose to maximise his chances of proposing to the best candidate?
My friend is in a quandary. It is impossible for him to know in the moment of dating someone whether they are the best candidate. He can only compare them with those he has previously let down (gently). And even if his current date is a wonderful person, the best one might come after them.
The strategy he seems to have followed to date is to leave it purely to chance. But this can’t be the most optimal. The probability of any one candidate, \(r\), chosen arbitrarily being the best is \(P(r) = 1/N\). This means that the more people in his social circle, the worse his strategy will perform. If he has 3 people in his social circle from which he can choose, the chances any one of them will be the best is 33%, but if his pool of potential dates was instead 10 people the probability of randomly selecting the best reduces to 10%.
Instead, the strategy most adults adopt — insofar as they consciously adopt a strategy — is to date around for a while, gain some experience, figure out their options, and then choose the next best thing that comes around.
Mathematically speaking, this strategy is to date and decline the first \(r-1\) people (let candidate \(m\) be the best among these \(r-1\) candidates) and then select the first subsequent candidate that is better than candidate \(m\). Being careful not to let any candidates know what strategy you’re following (or they are likely to dump you first).
We can calculate, for a given value of \(r\), the probability that the best candidate is selected as follows:
\(
P(r) = \displaystyle\sum_{i=1}^N P(\mathrm{applicant} \, i \, \mathrm{is \, selected} \, \cap \, \mathrm{applicant} \, i \, \mathrm{is \, the \, best}) \\
\)
From conditional probability, \(P(A \cap B)=P(A \vert B) \cdot P(B)\), which we use to derive the following:
\(\begin{align}
P(r) & = \displaystyle\sum_{i=1}^N P(\mathrm{applicant} \, i \, \mathrm{is \, selected} \, \cap \, \mathrm{applicant} \, i \, \mathrm{is \, the \, best}) &\\
& = \displaystyle\sum_{i=1}^N P(i \, \mathrm{is \, selected} \, \vert \, i \, \mathrm{is \, the \, best}) \, \cdot \, P( i \, \mathrm{is \, the \, best}) &\\
\end{align}\)
We then split the candidates into two groups, \(\lbrack 1, r-1 \rbrack \) and \(\lbrack r, N \rbrack \). For the first, because our strategy is to decline the first \(r-1\) candidates regardless, the probability of picking someone from this group is zero. For the second, because our strategy is to select the first candidate \(i\) in \(\lbrack r, N \rbrack \) who is better than the best in \(\lbrack 1, r-1 \rbrack \), the second best candidate to \(i\) must be in the first group, or alternatively put, the best applicant in \(\lbrack 1, i-1 \rbrack \) must be in \(\lbrack 1, r-1 \rbrack \) because otherwise we would have selected an earlier candidate. Finally, we know that the probability that any candidate \(i\) is the best is \(\frac{1}{N}\).
This gives the following:
\(\begin{align}
P(r) & = \displaystyle\sum_{i=1}^N P(i \, \mathrm{is \, selected} \, \vert \, i \, \mathrm{is \, the \, best}) \, \cdot \, P( i \, \mathrm{is \, the \, best}) &\\
& = \displaystyle\sum_{i=1}^{r-1}0 \, + \, \displaystyle\sum_{i=r}^N P(\mathrm{best \, applicant \, in \,} \lbrack 1, i-1 \rbrack \, \mathrm{is \, in \,} \lbrack 1, r-1 \rbrack) \, \cdot \frac{1}{N} &\\
& = \displaystyle\sum_{i=r}^N \frac{r-1}{i-1} \cdot \frac{1}{N} &\\
& = \frac{r-1}{N} \displaystyle\sum_{i=r-1}^{N-1} \frac{1}{i} &\\
\end{align}
\)
We recognise this as a Riemann approximation of an integral, so we can rewrite it. By letting \(\lim_{N \to \infty} \frac{r-1}{N} = x \) and \(\lim_{N \to \infty} \frac{i}{N} = t \), we get:
\(\begin{align}
P(r) & = \frac{r-1}{N} \displaystyle\sum_{i=r-1}^{N-1} \frac{1}{i} &\\
& = \lim_{N \to \infty} \frac{r-1}{N} \displaystyle\sum_{i=r-1}^{N-1} \frac{N}{i}\frac{1}{N} &\\
& = x \int_{x}^{1} \frac{1}{t} \,dt &\\
& = -x \ln x
\end{align}
\)
Now we can find the optimal \(r\) by setting the differential of \(P(r)\) to zero and solving:
\(\begin{align}
P'(r) & = -\ln x \, – 1 = 0 \iff x = \frac{1}{e}
\end{align}
\)
In conclusion.
The optimal solution for my friend is for him to estimate how many people he believes he might reasonably be prepared and able to date and divide this number by \(e\). So, for example, if he is prepared to date 15 ladies then \(N=15\) and as \(\frac{1}{e} \approx 0.37\), he would get \(r=6\). So he should date 6 ladies and then marry the next lady who is better than all of them.