Stable marriages January 21, 2008Posted by Ben Webster in combinatorics, fun problems, things I don't understand.
So, one of my odd mathematical fixations (totally unrelated to my research) is the stable marriage algorithm. Don’t ask me why, I just find it a remarkably appealing piece of math.
The stable marriage algorithm is, unfortunately, not a fool-proof way of keeping one’s marriage stable, but rather a way of taking two sets of parties (the obvious example being a group of men and a group of women, though the real life applications tend to involve much more boring things like matching medical students to residency programs), who would like to be paired up with each other. But rather than decide who marries who in the normal way, they want to give a mathematician a preference list, and have him sort out things in a sensible way.
Being a mathematician, this chap first has to come up with definition of a rigorous “sensible.” Certainly things won’t work very well if after the matching, there are any couples who would prefer to give the mathematician the middle finger and elope with each other to Vegas rather than stick with their assigned mates. A matching with no such couples is called “stable.” Now, this doesn’t uniquely specify the matching, and could leave many people still unhappy (if one gender all has similar preference lists, somebody still has to take the duds), but anybody they prefer to their spouse will not want to leave their own spouse for our unlucky lover. But at least no couple can complain the mathematician that he should have matched them instead.
Now, it’s not clear that there is a stable matching between any two sets of the same number of men and women. One is kind of tempted to start with a random matching and start “resolving the instabilities,” that is, finding unmatched couples who like each other better than their current spouses and matching them instead. But it’s far from obvious whether this process will terminate (it could be that a stable matching exists, and this “algorithm” if it can be called that, would miss them).
But Gale and Shapley gave a beautifully simple algorithm for producing a stable matching:
- Pick a random order on the men (one of the nice results about this algorithm is that the result is independent of the order chosen).
- The first man asks the first woman on his list to marry him. She, having never been proposed to before, naively accepts. Now, they are engaged.
- In order, the men go down their preference list, proposing to each woman in turn. If she is single, or prefers the new man to her fiance, she will accept him, and kick any previous fiance to the curb. The previous fiance will pick up where he left off on his preference list, until he finds a woman who will take him. The cycle continues, until somebody proposes to an unengaged woman (which will happen eventually, since every man’s preference list is longer than the list of engaged women).
- Rinse and repeat until every one is matched.
Note that at each time a man is matched to a previously single woman, the matching thus far is a stable matching of the matched people. Thus, at the end, we have a stable matching at the end.
Now, you may’ve noticed that this matching process is not symmetric in its treatment of the genders (or as some people like to call it, “sexist”). One could just as easily have had the women do the asking, and ended up with a completely different result. In fact, these results are in some sense polar opposites.
We call a woman Alice a stable wife of a man Bob if there is a stable matching in which Alice is Bob’s wife. Similarly, Bob would be Alice’s stable husband.
Theorem. In the algorithm specified above, each man is match with his most preferred stable wife, and each woman with her least preferred stable husband.
Proof. If the first statement is untrue, at some point in the process, a man (say, Bob) will be spurned by one of his stable wives (say Alice) for another (who we’ll call Chuck). Assume that this is the first time this has happened. Let Doris be Chuck’s wife in the stable marriage that pairs Alice and Bob. If Chuck liked Doris better than Alice, then he would have already been rejected by her, but this is impossible, since Bob is the first man to be turned down by a stable wife. Thus, Alice likes Chuck more than Bob, and Chuck likes Alice better than Doris, so the matching Alice-Bob and Chuck-Doris is not stable, since Chuck and Alice would run off.
Since each man is matched with his most prefered stable wife, if the wife were matched with someone she liked less than her current husband in a different stable matching, she and her current husband would prefer each other to their spouses in that matching and run off. Q.E.D.
I can’t quite say why, but this result blows my mind. If you had asked me before ever thinking about the matter, I would probably guess that one could always get a stable matching (though similar problems, such as the “gay stable marriage problem” where the people to be married are of a single gender this isn’t true). But I wouldn’t have ever guessed there was a single matching in which all members of one gender got the best result possible, or that this matching would be produced by the simplest imaginable algorithm. Similarly, I have totally not grokked the fact that men getting the best deal is (depressingly) completely tied to women getting the worst possible (or vice versa), even though the equivalence is basically obvious.
From what I understand, finding a gender neutral algorithm is still an open problem, which has caused some consternation in the medical community where the “genders” are hospitals and residency candidates. The scuttlebut on the internet suggests that it used to be hospital-optimized but it has now switched to resident-optimized (which I think makes sense. I suspect the residents are more sure about where they want to go).
I started pondering this more after seeing Al Roth’s talk on market design on Google Video (sadly, not at Google, which I understand has better food). It’s not exactly mathematical, but I still found it interesting, and I think it raises some interesting questions for the mathematics job market. Is the mathematics job market going to slowly unravel without a match? If not, why not? My guesses are “no” and “because the supply of talent is broad enough and the world small enough that attempting to unravel the market will be mostly be unproductive.” What say you, gentle readers?