Saturday, February 14, 2009

Valentine's Day Math

(The Stable Marriage Problem, in other words.)

I was recently reminded of this fun problem from Combinatorics, which was my favorite math class in college. The goal is to match N men with N women in such a way that no man and woman would both prefer to be married to each than to their assigned spouse (ie, it is a stable matching). There's a simple algorithm for this, invented by Gale and Shapley:

Each round, every single man proposes to his favorite woman who has not previously rejected him. The women collect and consider all these offers, and accept their favorites. If a woman has already accepted another proposal, this engagement is broken off, and that man becomes single again. This continues until everyone is paired up (which necessarily happens, since eventually every man can propose to every woman.)

Notice three properties of the resulting matching:
  1. It is stable. If there existed a man and woman in the final matching who wanted to have an affair, then that man would have proposed to that woman before his actual spouse, and that woman would have accepted.
  2. The men are paired with their favorite women that they could possibly be paired with in a stable matching. If this were not true, then there is some man M1 who is the first man to be rejected by his favorite feasible wife, W1. Say she rejected M1 in favor of another man, M2. Since men propose in order of preference, and M1 is the first man to be rejected by his favorite feasible wife, M2 must prefer W1 to any of his feasible wives. But in that case, in the stable matching (existent by hypothesis) in which M1 marries W1, W1 prefers M2 and M2 prefers W1 to W2. This contradicts the definition of stable.
  3. The women are paired with their least favorite man that they could possibly be paired with in a stable matching. This is true since if M1 is married to W1 in the algorithm, and in some other stable matching, M1 is married to W2 and W1 is married to M2, then by fact 2, we know M1 prefers W1 to W2, and therefore W1 must prefer M2 to M1 or otherwise that other matching wouldn't be stable.
The moral of the story is obvious.

But, now let's abandon traditional gender roles and sexual orientation and consider the PC version of the puzzle, say the Stable Life Partnering Problem. Now we have N people, all of whom might like to marry any of the other people, and each person chooses at the beginning whether s/he wants to be an asker or an askee. The trick is, asker's can now also be asked. I'm not sure what an easy fix for this would be. The problem is, in any round, an asker of course prefers to get a "yes" from their askee than to say yes to any other offer made to him. But then you can have a cycle of askers proposing to each other, and everyone is waiting for the person downstream to respond before accepting or rejecting other offers. There needs to be different rules for timing to make the problem tractable. Any ideas? (If asker's can't ask other askers, of course this boringly devolves into the other problem.)

(By the way, Happy V-day to all others whose revealed preferences rank writing about math over going out for the holiday =)


Ambrus said...

While this problem is quite interesting mathematically, there are two very obvious assumptions: 1) Complete information is available to every individual so that they can make an informed ranking of their preferences. 2) A single individual's preference ordering of all other individuals is the same for both spousal relationship as well as shorter-term affairs. I have a strange suspicion that neither of these assumptions would hold up particularly well when confronted with reality. Is it possible that randomness plays a much bigger part in human mate selection than do gender roles?

Ambrus said...

Oh yes, and happy V-day. Go math :)

Vera said...

You crazy engineers, always worried about "reality" =P

Obviously in the real world this is not how things work. I would emphasize a different pair of assumptions however: Uncertainty and stickiness. That is, males are uncertain if they will meet a more desirable female later on, and women are as well. And this is all the more important because "engagements" or "marriages" are costly to end in order to switch to someone else.

But that's not the point. It's very applicable in other settings; for example, it has been used to place med school graduates in hospitals, and could be used to match people in occupational partnerships, or in some kind of speed dating scenario, or a thousand other examples I'm sure you can think of.

Vera said...

To be more specific, I mean I acknowledge the importance of the first assumption you pointed out, and think the 2nd is irrelevant because short-term affairs are outside the realm of this problem. If preferences for short-term partners is indeed different than for spouses, this will not make the spouse-matching outcome unstable.

Ambrus said...

It's actually very cool that such a method has been used in real-world situations. What I'm interested to know is: how well did it work? I'd love to hear interviews with people even just a year after they've been matched up. It would be fascinating to hear how many of them feel it was a good matching, how many changed their minds, and what their justifications might be for the way they feel.

As long as we're talking about the real world, it seems like property 1 from your original message is on relatively shaky ground. Take a look at it again and read it aloud.

One could argue that an already-paired individual's infatuation with another individual is a primary source of instability in long-term relationships. One could further argue that, due to the emotional nature of humans, infatuation (perhaps even love?) can arise between two people who consciously and logically know that they are not long-term compatible. Certainly, stickiness plays a role in smoothing out these instabilities, but I would find it difficult to deny their very existence.

I do agree that in the purely mathematical problem this is all irrelevant, but doesn't the usefulness of a mathematical equation or a logical argument ultimately hinge upon what it can teach us about the world?

Antonio said...

Could you make the assumption that at every period t an equal number of men and women are selected as proposers and they can either propose to each other or to the ones that have not been selected.
Of course with the assumption that ex-ante everyone has the same probability of being selected as a proposer...

somebody said...