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!