Monday, 1 February 2010

The Stable Marriage Problem

Previously I wrote about a mathematical model called the "Marriage Problem" which, whilst interesting, has a lot of shortcomings. Under very particular conditions (which are arguably quite unrealistic), it can optimise the chances of marrying the best possible partner I could expect. But even then it only optimises the probability of doing so, and that's small comfort if I marry someone today only to meet my true True Love tomorrow.

Go To Him
I still love you so, but if he loves you more, go with him.

Life is messy. What if you do fall even more in love with someone else than with your current spouse, and what if they fall in love with you? What if they also are married to another? Then should your respective vows forever keep your two hearts apart, or should you abandon that which once was beautiful but which beauty now hath ruined? What mockery is made of love in either case!
Oh, that this tragedy could have been averted! If only there were a way to ensure that everyone be happily married and never be tormented by temptation! If only Mathematics had something to tell us...
There is another mathematical problem, of similar name though quite distinct, called the "Stable Marriage Problem". Consider an equal number of men and women to be married to one another. Is it possible for everyone to marry, such that you could never find yourself in that lamentable hypothetical situation: preferring to be with someone else who would also prefer to be with you?

I'm Henry The Eighth
And every one was an 'enry...

Yes - it is possible.
Gale & Shapley devised a simple iterative algorithm for solving the problem: Each man should rank the women from best to worst according to his personal preferences, and each woman should rank the men according to hers. Then, each man should propose to the woman he prefers most. If a woman receives a proposal, she accepts it, and the couple are engaged. If a woman receives multiple proposals, she accepts the proposal from the man she prefers most. Then, each man who was rejected (because the woman he preferred most accepted another man's proposal) should propose to the next-most preferred woman on his list. As before, if a free woman receives a proposal, she accepts it, and if she receives multiple proposals, she accepts the one she prefers most. If an engaged woman receives a proposal from a man she prefers more than her current fiance, she dumps her current fiance and accepts the new proposal. Then, each man who was rejected or dumped proposes to the next-most preferred woman on his list... and so the process continues until every man (and therefore every woman) is engaged. At this point everyone marries their current fiance and the algorithm is complete.
This algorithm is guaranteed to finish (it won't keep iterating endlessly), and it is guaranteed to result in a "stable pairing" - an arrangement of marriages in which no two people prefer each other to their current spouses.
It is interesting to note how similar this model is, in principle, to the way our society has approached marriage in recent history.

Hungry Heart
Got a wife and kids in Baltimore, Jack, I went out for a ride and I never went back...

So if everyone followed these rules, would the world be a happier place? Not necessarily. Stability, in this sense, doesn't imply happiness: just because your marriage is "stable" doesn't mean that you wouldn't rather be with someone else - it just means that that person wouldn't rather be with you.
The mathematical "happiness" score of your marriage is determined by how high your spouse sits on your own personal preference ranking of all partners. The overall happiness of a given arrangement of marriages can be defined as the average happiness scores of all people. Note that husband and wife can have different happiness scores!
For any large enough group of men and women there will be multiple alternative arrangements of marriages that are all "stable", in the sense that no two people prefer each other to their current spouses. Some arrangements will be "happier" than others.
Gale & Shapley's model produces just one of many possible stable arrangements. In fact, there's a very interesting mathematical property of Gale & Shapley's model: It will always produce the arrangement that, whilst still being stable, is happiest for the men (who propose)... and unhappiest for the women.
Reflect for a moment, if you will, upon the parallels between this model and conservative real-life society: I wonder if it is coincidence that this model predicts unhappy marriages for women, and that our real-life notions about marriage are changing as women become more empowered?

All This Useless Beauty
What shall we do, what shall we do?

Remember that every man and woman ranks each potential partner from best to worst. These personal preferences are necessary for establishing that an arrangement is "stable" (we need some way of knowing whether any two people prefer each other to their current spouses), and is used to calculate the happiness of an arrangement of marriages. So far, and very politically correctly, we've assumed that the preferences are arbitrary, random - that beauty is in the eye of the beholder. But what if each person has an intrinsic "beauty" (or personality or intelligence; call it what you will, mathematically it's equivalent) that influences their standing in other people's preferences?
Caldarelli & Capocci showed that the more that "beauty" is allowed to influence the preferences, the more miserable everyone is in general. That's because the more homogenised our notion of beauty is, the more similar everyone's "personal" preferences become. The more similar everyone's preferences are, the less likely it is for you to marry high on your list, because the people high on your list are also high on the lists of rivals more attractive than you are. It's fine if you're beautiful, but rough for everyone else.
Surprisingly though, according to Caldarelli & Capocci's model, the more that beauty influences preferences, the happier that women are, on average, relative to men. The arrangements found by this model are still happiest for men and unhappiest for women, but the difference is less. And depending on how much weight is placed on beauty (not too little, not too much), a majority of women can end up much happier than if beauty plays no role.
I wonder, then, if emphasising beauty is a strategy for women as a group to maximise their happiness within a traditionally male-dominated society - making the best of an unfair situation?

So Far Away
You're so far away from me, so far I just can't see.

"Spatial homogamy" is the idea that people tend to marry people from their own area. "Propinquity" is the idea that the probability of forming a relationship is proportional to the square of the physical distance between people. Many studies have cemented these ideas in sociology: People tend to prefer partners who live close by. Someone commented on my previous article that the trick was to fall in love with someone within a certain distance. He was probably thinking about fuel prices and airfares, but how right he was - from a mathematical point of view!
If adding "beauty" to the model reduces overall happiness by homogenising people's preferences, then adding "distance" to the model does the opposite by mixing the preferences up again. Because everyone occupies a unique position in space, everyone's preferences are influenced in a unique way by the distances to other people.
In fact, I think it's probably even better than that. The distance relationship between two people is symmetrical, and therefore affects both of their preferences the same way - the person that you prefer because they live close by is more likely to prefer you as well, for the same reason. So the more emphasis placed on distance, the happier everyone should be. So - say hi to that cute guy or girl you see at the local market next time!

The Stable Marriage Problem is an incredibly rich area of research, bringing together combinatorial optimisation, game theory, economics, and even real sociological research. As far as I know it's not actually used to marry people off anywhere, but it is used for analogous problems like assigning students to schools and residents to hospitals.
There are a lot of other variants on the classical Gale-Shapley model that I haven't even touched - like models that take into account three-way matches (actually, even kinkier than it sounds if you were to apply it to dating...) and models that take into account "cheating" to get a better match for yourself.
There's even a variant, commonly called the Stable Roommate Problem, which matches pairs of people from within a single group, not across two groups like the Stable Marriage Problem. This might be a good model for gay marriage, but there's some bad news: there's no mathematical guarantee of stability in this single-group variant. But then, we've just seen that stability is no guarantee of happiness, so maybe that's not such a bad thing after all!


melanie said...

tuesday, 2 february, 2010 11:50 MAT

The heart has its reasons of which reason knows nothing.

-Blaise Pascal

,` )

Nick said...

Pascal also made Pascal's Wager, which in my opinion doesn't give him much authority to talk about reason... :p

I'm a Rock said...

Hi, I'm from Brazil, and I have enjoyed both of yours articles about marriage. I'm working with Gale-Shapley alghorithm and recently posted about it in my own blog:, it's only in portuguese, but most of links are in english).

In fact, Gale-Shapley is more general, women can propose first, and men stick with the best offer received. By this way, the men are at least so good as women, but women are better off. But life is fuzzy and there is no stable match for two sides proposing at same time, that's will be pretty much like real life.

I'm working with GS to rearrange students by schools considering distance, score test, and others parametres...

Nicholas Young said...


I hadn't read about the variant where both sides can propose at the same time. I guess it makes sense that it results in unstable arrangements. You could think about that variant as being basically the same as the "Stable Roommate Problem" I mentioned, where you pair people up from a single pool - the variant where there's two sides (pools) but both sides can propose at the same time would be similar to having one large single pool, except that all of the men would rank all of the women above all of the other men, and vice versa.

I read your blog post thanks to Google Translate - it's interesting and I hope your research goes well!

I'm a Rock said...

Thanks for your answer comment, Nick. I was concerned about writing to a deceased blog because last topic date. I know it's hard bloggin and that stuff, but I do encourage you to go on. Topics at more deeper level about games are very rare.

Making me more precisely: "two side proposing it's not guarantee of stable match", eventually (more often probably) the pairs could be matching.

Very interesting looking at it by the 'roomate problem' perspective, I think its very insightfull. It's also possible have truncated preferences. One person could rank p1, p2 and p3 and no one else, but she (or he) will have to face the consequences of being alone (match to yourself).

If you don't mind, I will link your blog. It's Ok?! Take care with google translator, sometimes it goes poorly, i'm not responsible about what google translates... :D

Nicholas Young said...

Thanks for the encouragement :)

You're very welcome to link to this article or blog. I'm glad someone else has found it interesting :)

I'm a Rock said...

Just Added. Sorry, for the inverted phrase question above. I do this blunder sometimes. Nice to see new posts. Best wishes.