What is the optimal strategy to marry the best one ?

February 13, 2011
By

(This article was first published on Freakonometrics - Tag - R-english, and kindly contributed to R-bloggers)

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's my 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 http://freakonometrics.blog.free.fr/public/maths/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 http://freakonometrics.blog.free.fr/public/maths/mariage01.png men agree to marry her. Of course, among those http://freakonometrics.blog.free.fr/public/maths/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 http://freakonometrics.blog.free.fr/public/maths/mariage01.png), but she knows if this one is better than the ones she already met. From a mathematical point of view, at time http://freakonometrics.blog.free.fr/public/maths/mariage02.png, she knows the relative rank of http://freakonometrics.blog.free.fr/public/maths/mariage02.png (compared with the first http://freakonometrics.blog.free.fr/public/maths/mariage04.png), not his absolute rank. We also assume that http://freakonometrics.blog.free.fr/public/maths/mariage01.png is known.

The optimal strategy is that she has to reject automatically the first http://freakonometrics.blog.free.fr/public/maths/mariage04.png (some kind of calibration period), and then, starting at time http://freakonometrics.blog.free.fr/public/maths/mariage02.png, she will marry the best over the ones she has already met.
So assume that our girl already met http://freakonometrics.blog.free.fr/public/maths/mariage04.png guys, and decided to reject all of them. So now she's trying to see if the http://freakonometrics.blog.free.fr/public/maths/mariage02.png can be the optimal time to stop, and start looking seriously ....For an arbitrary cut-off http://freakonometrics.blog.free.fr/public/maths/mariage02.png, the probability that the best applicant will show up at some time http://freakonometrics.blog.free.fr/public/perso2/wedd01.gif is http://freakonometrics.blog.free.fr/public/perso2/wedding01.gif

http://freakonometrics.blog.free.fr/public/perso2/wedding02.gif

i.e.

http://freakonometrics.blog.free.fr/public/perso2/wdeeing03.gif

The http://freakonometrics.blog.free.fr/public/perso2/wedd02.gif term is because there is only one "best" guy, and the http://freakonometrics.blog.free.fr/public/perso2/wedd03.gif is the probability that he shows up at time http://freakonometrics.blog.free.fr/public/perso2/wedd01.gif (this can be visualized below)

Thus, we can write
http://freakonometrics.blog.free.fr/public/perso2/wedding04.gif

i.e.

http://freakonometrics.blog.free.fr/public/perso2/wedding05.gif
Thus, since the minimum of http://freakonometrics.blog.free.fr/public/maths/mariage18.png is obtained when http://freakonometrics.blog.free.fr/public/maths/mariage19.png, which is the optimal time to stop (or here to start seeking).

Hence, the best strategy is to reject automatically the first http://freakonometrics.blog.free.fr/public/maths/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 http://freakonometrics.blog.free.fr/public/maths/mariage02.png (we consider a loop with all possible values for http://freakonometrics.blog.free.fr/public/maths/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),

n=100
ns=1000000
MOY1=MOY2=rep(NA,n)
for(m in 2:(n-1)){
WHICH=rep(NA,ns); MARIAGE=rep(0,ns)
for(s in 1:ns){
Z=sample(1:n,size=n,replace=FALSE)
mx=max(Z[1:m])
STOP=FALSE
for(k in (m+1):n){
if((Z[k]>mx)&(STOP==FALSE)){
WHICH[s]=k
STOP=TRUE
MARIAGE[s]=1
}
}
}
HIS=WHICH[is.na(WHICH)==FALSE]
TH=table(HIS)
MOY1[m]=mean(HIS)
MOY2[m]=mean(HIS)*mean(MARIAGE)
THH=rep(NA,100)
THH[as.numeric(names(TH))]=as.numeric(TH)/ns
}

If we run it over all possible http://freakonometrics.blog.free.fr/public/maths/mariage02.png we get

http://freakonometrics.blog.free.fr/public/perso2/mariage-anim.gif
The "distribution" (in green) can be seen as the probability to marry the guy of level http://freakonometrics.blog.free.fr/public/maths/mariage06.png, given that the first http://freakonometrics.blog.free.fr/public/maths/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 http://freakonometrics.blog.free.fr/public/maths/mariage06.png gives here satisfaction http://freakonometrics.blog.free.fr/public/maths/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 in Statistical 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 !

To leave a comment for the author, please follow the link and comment on his blog: Freakonometrics - Tag - R-english.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , , , , , , , , ,

Comments are closed.