var _gaq = _gaq || []; _gaq.push(['_setAccount', 'UA-39795839-1']); _gaq.push(['_setDomainName', 'mathophilia.com']); _gaq.push(['_trackPageview']);

(function() { var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true; ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s); })();

Dear readers,

Many people around the world today will be celebrating Valentine’s Day, a day that celebrates romantic relationships. It may be surprising to you that mathematics can say something helpful on that topic, a never-ending source of complexity that resists clean definitions. Nevertheless, mathematics can in fact provide useful insights in some specific contexts, which I’m going to talk about in today’s post.

Perhaps some of you are considering making a marriage proposal to your significant other, or will have to respond to one (for those of you who don’t like the idea of marriage, feel free to substitute civil union or whatever other form of commitment works for you, as long as it entails long-term exclusivity). In case you have to respond to such a proposal, what is the best way to decide whether to say yes or no? This is a difficult problem, involving a host of variables such as compatibility, emotional connection, similarity of values, and chemistry. One of the challenges of this situation is the fact that, assuming that you’ve been in several other relationships before, your current partner is unlikely to be superior to all your previous romantic partners on all these criteria. In fact, it’s easy to see that the more partners you’ve had, the less likely the current one is to simultaneously maximize all these criteria. But suppose for the moment that you’re able to compare any two of your partners. What’s the optimal decision then?

There is a simple mathematical answer to this question, originally called the fiancée problem, solved in 1958. It depends on a number of critical assumptions. First, you have to be able to give each partner a “suitability score”. Second, you have to assume that the partners present themselves in an order that’s random with respect to this score. Third, you have to respond immediately and can’t change your mind later. Lastly, you need to know how many partners you might have to choose from over your lifetime, which we will call n. Under those conditions, the optimal strategy for choosing the best possible partner turns out to be to say no to roughly the first n/e partners, then to say yes to the first one who happens to be better than every other one you’ve considered so far. Here, e = 2.71828… is Euler’s number, the base of the natural logarithm. This strategy gives you a roughly 1/e (or about 37%) chance of finding the best partner for large n. For small values of n, there is an explicit formula. For example, if you expect to have 8 to 10 partners, you should say no to the first 3 and then yes to the first one who is better than all the previous ones, which will give you an approximately 40% chance of saying yes to the best one.

Of course, finding the best possible partner is not a guarantee of the stability of the marriage, because it may happen that other options will present themselves to either yourself or your partner later on, and an incentive to deviate from exclusivity (or towards commitment with a different person) will appear. Can we guarantee that this doesn’t happen? Not an easy task, when both infidelity and divorce rates are so high. But part of the problem lies in the fact that we as a society have more options now than we ever had, and we can no longer exhaustively evaluate all of them ahead of time when making a decision. Suppose, however, that all of us do know all of our options ahead of time, and can rank them without any ties. Is there a way to guarantee stable marriages in this case? It turns out that there is, provided, of course, that there are as many men as women (I do realize that this is a heteronormative restriction, but it will make the discussion easier – in general, the important thing is that there are two distinct groups of people who can only form marriages with someone from the other group, not from the same group).

This problem, known as the stable marriage problem, was solved in the early 1960s by David Gale and Lloyd Shapley, the latter being a co-laureate of the latest Nobel Prize in Economics for his varied work. The solution is both natural and very elegant. Once again, we use n to denote the number of men (and women) who need to be married. Each woman has a ranking of the men, and each man, of the women. Initially, none of them is engaged. The solution proceeds by rounds. In each round, an unengaged man proposes to the highest-ranked woman on his list to whom he has not proposed yet. The woman always provisionally says “maybe” to him if she is not engaged or is engaged to someone she prefers less (in which case the man she is currently engaged to gets the initial “maybe” changed to a “no”), and “no” otherwise. At the end of this process, every man will be engaged to some woman, and marriages occur. These marriages will be stable in the sense that no man and woman will want to run away with each other from their spouses. Indeed, if a man, say Bob, likes a woman, say Alice, more than his wife, this means that he proposed to Alice before he proposed to her. But then, Alice must have said “no” to him at some point (otherwise they would be engaged at the end), so she prefers her assigned spouse to Bob.

An interesting side note is that the marriages that result from this process are optimal for the men (in the sense that no man can do better in a stable solution than the spouse he ends up with). This is due to the fact that a man is in principle able to propose to every woman on his list, while a woman may only get a limited number of proposals. From that point of view, it pays to be proactive in making proposals (though I’m not necessarily advocating for a reversal of the “traditional” model based on this analysis).

Many of you will be quick to object that the two problems I discussed so far – the fiancée problem and the stable marriage problem – are fairly unrealistic and do not reflect the way our society works. That’s a fair criticism, to which I can only respond that all mathematical models, especially those that have an elegant analysis or solution, involve simplifications of reality. But there is also a more serious approach to the mathematical modeling of relationship dynamics that appeared a few years ago. It is based on a system of differential equations, and, like any good model, it has parameters that can be estimated from experiments and makes falsifiable predictions. The book describing this approach has made it onto my reading list, right behind Nate Silver’s book that I mentioned in an earlier post, and I’ll report on it as soon as I get to read it. Meanwhile, I wish you all a happy Valentine’s Day, no matter your relationship status! And remember that mathematics is like love; a simple idea, but it can get complicated.