What is the optimal strategy to marry the best one ?

Valentine’s day is a nice opportunity to post on hot and sexy topics… Well, it’s also an important day that I should not miss, probably as much as Saint Patrick’smy wife’s birthday. And as I mentioned last week (here), it is difficult to get the distribution of the age of marriage on the internet… So maybe we can build up a small model, to understand when do girls decide to get married… Consider a young girl who knows that he will not meet thousands of men willing to marry her (actually, one can consider the opposite point of view, with young man who can find only https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage01.png girls willing to marry him, the problem can be assumed as symmetric, especially if I do not want to get feminist leagues on my back).

Assume that https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage01.png men agree to marry her. Of course, among those https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage01.png men, our girl wants to marry the “best” one (assume that men can be ranked objectively). Of course, she cannot meet the “best” guy immediately, so men are met randomly, and after each “interview“, either she reject him (forever, we assume she cannot get back and admit she made a mistake), or agree to marry him. An important assumption is that rejected men cannot be recalled.

From a mathematical point of view, we need to find the optimal stopping time. Here, the problem is slightly different compared with that one (with optimal time to get a bonus) or this one (with the optimal time to sit in a bar and have a beer). Here, we do not give “grades” to guy. The only thing that is observed is their relative ranks. Our girl cannot know if she’s meting the best of all men (out of https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage01.png), but she knows if this one is better than the ones she already met. From a mathematical point of view, at time https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage02.png, she knows the relative rank of https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage02.png (compared with the first https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage04.png), not his absolute rank. We also assume that https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage01.png is known.

The optimal strategy is that she has to reject automatically the first https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage04.png (some kind of calibration period), and then, starting at time https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage02.png, she will marry the best over the ones she has already met.
So assume that our girl already met https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage04.png guys, and decided to reject all of them. So now she’s trying to see if the https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage02.png can be the optimal time to stop, and start looking seriously ….For an arbitrary cut-off https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage02.png, the probability that the best applicant will show up at some time https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/wedd01.gif is https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/wedding01.gif




The https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/wedd02.gif term is because there is only one “best” guy, and the https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/wedd03.gifis the probability that he shows up at time https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/wedd01.gif (this can be visualized below)

Thus, we can write




Thus, since the minimum of https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage18.png is obtained when https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage19.png, which is the optimal time to stop (or here to start seeking), i.e. 36.7%.

Hence, the best strategy is to reject automatically the first https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage20.png=37% of the candidates (which is the maximum value of the function above), and then to select the first one (if possible) that is better than all previous candidates.

Consider the following Monte Carlo procedure: assume that she rejects – automatically – the first https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage02.png (we consider a loop with all possible values for https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage02.png) and then gets married with the first one who is the best one she’s seen during the calibration period (or overall, which is the same),

for(m in 2:(n-1)){
WHICH=rep(NA,ns); MARIAGE=rep(0,ns)
for(s in 1:ns){
for(k in (m+1):n){

If we run it over all possible https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage02.png we get


The “distribution” (in green) can be seen as the probability to marry the guy of level https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage06.png, given that the first https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage02.png were rejected. The sum is not one since there is a non null probability to marry no one. Actually, the probability to get married is the following

The more she waits, the smaller the probability of getting married. But on the other hand, the more she waits, the “better” the husband…. On the graph below is plotted the rank of the guy she marries, if she gets married (it was actually the vertical plain line in red on the animation)

So there is a trade-off. If not getting married gives a 0 satisfaction (lower than finally marrying anyone), and if marrying the guy with rank https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage06.png gives here satisfaction https://f.hypotheses.org/wp-content/blogs.dir/253/files/2015/12/mariage06.png ,we have

(it was the vertical doted line in red on the animation). So it looks like it is optimal to test the first 35-38% men, and then to marry the best one she finds (if he is better than the best one she met during the “testing” procedure). So our previous analysis looks correct…

Now to go further, I have to admit that this model is known in academic literature as the secretary problem. In 1989, Thomas Ferguson wrote a nice paper inStatistical Science entitled who solved the secretary problem (here). Anthony Mucci published also an article in the Annals of Probability on possible extensions, in 1973 (here), or Thomas Lorenzen (there) in 1981. This problem is definitively an interesting one !

9 thoughts on “What is the optimal strategy to marry the best one ?”

  1. Assume that men agree to marry her. An important assumption is that rejected men cannot be recalled. The only thing that is observed is their relative ranks. The sum is not one since there is a non null probability to marry no one. So our previous analysis looks correct. So I do not know if connexions can be made.thanks, very informative for me

  2. I get the simplicity and beauty. But still:

    How would one incorporate a diminishing ability to find a spouse (beauty – some say, is important and decaying). Eg. max ability at, say age 25? If one did this, it would seem logical to also diminish the pool of available candidates (“The best ones are taken”).

    Also – maybe one could add an information criterion. So that certainty about a candidates ranking is comparable small when the “game” begins at age 18 (lets say you are 50% sure when you are young). As one gets older and acquires knowledge of self, and candidates earn-abilities etc., one gets more sure of candidate rank (i.e. is he/she suitable). Lets say you max out at 90% sure at age 40.

    This should be possible to acount for in simulation right? How would this change the result?

  3. This is the optimal strategy to maximize the probability of selecting the best candidate, but that seems like the wrong objective. With the story accompanying it, the girl should care about the expected rank of the man she married, not whether he is the best of all suitors.

    I haven’t looked at the literature closely, but the cutoff strategy that yields the maximum expected rank (equivalently, the maximum expected quality if the distribution is uniform) is to calibrate on the first n^0.5. This isn’t the optimal strategy, but I don’t remember the precise solution to the dynamic programming problem. It’s something like accept the k-th candidate if they are above the (100 – 100/(n – k + 1))-th quantile of candidates seen so far.

    RESPONSE: you’re right, the answer depends on the objective function. On the monte carlo simulations, we see that the problem can be seen as the maximization of the expected rank of the man she married (with a zero utility if she marries no one). The problem with that interpretation is that, for the last one, she should prefer to marry anyone than no one, which is not allowed here: she can only marry someone better than all those she met…

  4. Wow, this is the best explanation I’ve ever read for american options. I really keep that in mind. Thanks!

    ANSWER: Hi Adrien…. actually, I thought there were connexions with options… but in option pricing, you have an assumption about your diffusion (i.e. your distribution). Here, we observe only relative ranks. So I do not know if connexions can be made… If you have any idea… please let me know !

  5. An awesome book write by Don Knuth on a related subject is *Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms*.

    It’s not the secretary problem, since we have n men and n women, but hey, it’s Valentine Day !

    RESPONSE: thanks for the awesome reference ! At first, I wanted to find ideas in that book, but they did not have it available at the library… So next year, I’ll discuss matching issues….

Leave a Reply

Your email address will not be published. Required fields are marked *