## Stable marriages January 21, 2008

Posted 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:

1. 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).
2. 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.
3. 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).
4. 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?

1. Michael - January 22, 2008
2. Greg Kuperberg - January 22, 2008

From what I understand, finding a gender neutral algorithm is still an open problem

I don’t entirely understand the terms of this question. The first question that comes to mind is: Consider preference lists with an involution that exchanges men and women. Is there an example where the induced action on stable matchings is free?

I don’t know whether this question is hard or easy. If the answer is “yes”, then obviously there cannot be a deterministic gender-symmetric algorithm. But there is a trivial randomized gender-symmetric algorithm: Use any algorithm, such as Gale-Shapley, together with a coin flip at the beginning. On the other hand, if the answer is a provable “no”, then the proof is some form of an algorithm, possibly

3. John Armstrong - January 22, 2008

Greg: basically it means that the algorithm treats the two populations differently. One is the proposers and the other is the accepters.

4. Kenny - January 22, 2008

I was just posting about a related problem on another blog – http://tar.weatherson.org/2008/01/10/the-hiring-impossibility-theorem/
One thing I’m interested in there though is what further criteria we’d want besides stability in this sense. In fact, for applications like matching jobs and candidates, there might be enough incentives to play along with the system that stability isn’t even necessary. Instead we’d like something more like the Arrow theorem criteria about how preferences translate into matchings, so that there’s no incentive for strategically re-organizing one’s list.

No one there was interested in the possibility or impossibility theorem though.

Also, it’s surprising to me that men getting their most preferred stable matching means women must get their least-preferred one – I would have thought it was compatible with women getting middling-preferred ones, but I guess not.

5. Ben Webster - January 22, 2008

Consider preference lists with an involution that exchanges men and women. Is there an example where the induced action on stable matchings is free?

I’m confused, Greg. You can only get such an action after already specifying a deterministic procedure for producing a matching. It might be trivial for any given preference lists and algorithm, or it might not. For Gale-Shapley, the only fixed points are cases where there is a unique stable matching, that is, it is as unfair as possible.

One can imagine that there is a deterministic procedure which is symmetric, though my intuition is against it (if anyone knows that this is impossible, please illuminate us). One can also imagine some quantitative measure of fairness, which G-S (and your proposed G-S + coin flip) would flunk as badly as mathematically possible, and some deterministic or probabilistic algorithm could maximize.

6. David Speyer - January 22, 2008

Ben — consider the situation where there are two men — Alex and Bob — and two women — Cathy and Dorothy. Suppose that the preference lists are as follows:

A: C,D
B: D,C

C: B,A
D: A,B

Both pairings, (AC, BD) and (AD, BC), are stable. In one case, both men get their top choice, in the other, the women both do. There is no way for a symmetric, deterministic algorithm to choose between them.

7. Ben Webster - January 22, 2008

Oh, right. I still hold out hope for some probabilistic version. After all, basically anything would be fairer than Gale-Shapley with a coin.

Also, the only reason you can’t distinguish between these is you’re not allowed to take intensity into account. Obviously, the correct resolution is to figure out who feels most strongly on the matter.

8. Greg Kuperberg - January 22, 2008

I’m confused, Greg. You can only get such an action after already specifying a deterministic procedure for producing a matching.

No that’s not true, if the preference rankings are invariant under the involution that switches the men and women. In that case, the involution plainly acts on all of the stable matchings. But I suppose that you get my drift, now that David Speyer noblly did the thinking that I blegged for. (But the example is nearly trivial, sigh.)

I still hold out hope for some probabilistic version.

But is there a rigorous characterization of that hope? After all, a coin toss followed by Gale-Shipley is symmetric, technically speaking.

Also, the only reason you can’t distinguish between these is you’re not allowed to take intensity into account. Obviously, the correct resolution is to figure out who feels most strongly on the matter.

That could be an interesting twist, but part of the sentiment of Gale-Shipley is that it is not an optimization result, where trivially (because the search space is finite) an optimum exists. In fact, what first comes to mind is that if you rate each marriage by happiness, then you can find the matching that maximizes total happiness by linear programming. This is useful, but it is not Gale-Shipley.

It takes a bit of reflection to realize why the medical match might want Gale-Shipley rather than linear programming. It is so that no pair consisting of a hospital and a candidate have a mutual incentive to buck the system. Or, with marriages, it is designed to deter infidelity, which is a different requirement than making everyone as happy as possible.

9. Greg Kuperberg - January 22, 2008

Ah, here is a cool result that, while not directly addressing algorithms, does settle one question that Ben was groping for. Consider two partial orderings on stable matchings, one given by saying that f >= g if all men are at least as happy in f as in g, and the other for women. Then (a) the partial orderings are the reverse of each other, and (b) the set of stable matchings for any preference list is a distributive lattice.

Now, the classification theorem of finite distributive lattices says that they are all isomorphic to power sets of a finite set X. Say that the maximal element — the male-dominant matching — is X. The minimal element — female-dominant — is the empty set. Then we can imagine two “best” probability distributions. One would be the uniform distribution on all of P(X). Another other would be the uniform distribution on half-sized subset, or on subsets of size (|X|+-1)/2. Either of these distributions are plausibly as fair as possible (in the sense of minimizing some sort of “variance” of unfairness). It is also plausible that there is a fast algorithm to generate the first one, i.e., a uniformly random stable matching.

10. Todd Trimble - January 23, 2008

Greg, I’m not sure it seriously affects your comment, but not all finite distributive lattices are power sets (for example, the lattice 0 < 1 < 2 is distributive). The classification theorem is that every finite distributive lattice is isomorphic to the lattice of down-closed subsets of a finite poset, ordered by inclusion. Finite Boolean algebras correspond to the case where the poset is discrete (i.e., they are power sets).

11. Greg Kuperberg - January 23, 2008

Todd,

Duh, oops, this did seem too good to be true. There is a classification theorem for one kind of lattice, Boolean lattices I suppose, which fits what I wrote. But then there is also a classification of distributive lattices which is exactly what you say: The set of order ideals in another poset. I actually knew this, since I’ve thought about plane partitions, which are of course an example of a set of order ideals. Basically I misinterpreted the paper to mean Boolean lattices.

Okay, distributive lattices instead then. This is a more general class of posets, but it does include the Boolean lattices as a special case. (And clearly you can make any finite Boolean lattice as the lattice of stable marriages.) In fact, a lot of work has been done on taking an exact random sample from a distributive lattice. The general idea is called “coupling from the past” or the Propp-Wilson algorithm. But in order to use that particular algorithm, you would first want to know how to compute the down-sets in the stable-marriage poset that are adjacent to a given down-set; then you would have to know how to make random choices so that random walks converge to the stationary distribution.

12. Carnival of Mathematics 1000 « JD2718 - February 22, 2008

[…] – Need help finding the perfect mate? No one here can help you. But Ben Webster turns a search for stable marriages into a combinatorial discussion at the Secret Blogging Seminar. Cool, btw, to have a real seminar […]

13. Christine Cheng - July 7, 2008

I just discovered these exchanges a good five months from the last post. Hope my comments are still relevant and clear some things out.

Al Roth has done some work as to why stability is an important requirement to have for matchings. In the 1980’s, he compared some centralized matching algorithms in the U.K. for matching medical professionals with jobs, and found that those that did not produce stable matchings tend to have less and less participation over time while those that did continued to be in use. This make sense — afterall, the stability requirement was meant to prevent the unraveling of the matchings. What was surprising (and delightful) was that theory did predict practice. You can find relevant papers from his website and his book on stable matchings.

People have also looked into “fair” stable matchings. Greg kinda alluded to a natural one. Consider the set of all stable matchings.
For each partipant a, let M(a) denote the partner of a in matching M.
Let happiness(a, M) denote how happy a is with matching M. The egalitarian stable matching imaximizes the sum of happiness(a,M) over all a. The minimum regret stable matching maximizes the
minimum happiness(a,M) over all a (i.e., it maximizes the happiness of the unhappiest person). If happiness(a,M) is based on the rank of M(a), both problems are known to be solvable in polynomial time.

There is an intriguing one which I’ve worked on recently called the median stable matching. (See http://www.cs.uwm.edu/~ccheng) The basic idea is as follows: for each man m, rank his partners in all stable matchings from his most favorite to his least favorite. Note that he may have the same partner a in several stable matchings, in which case a will be present in this list multiple times as well. Now, let p_i(m) denote the ith woman in m’s sorted list. Let M_i consist of all pairs (m, p_i(m)). There’s no reason to believe that M_i is a matching — but it is! Furthermore, it is a stable matching! Additionally, let N denote the number of stable matchings of the instance. For simplicity, assume N is odd. Then M_{(N+1)/2} matches each man to his median stable partner, and it turns out, each woman to her median stable partner! BTW, this result is due to Teo and Sethuraman. Among all “fair” stable matchings that have been proposed, this was the most satisfying to me because the fairness occurs at a local level, as opposed to the previous ones where some person might still be better off than others.
Unfortunately, I show that finding the median stable matching is NP-hard. The problem is related to counting the number of order ideals of a poset, which is a #P-complete problem.

Finally, finding a random stable matching seems also a reasonable way to arrive at a fair stable matching. A recent paper by Bhatnagar et al (SODA 2008) shows that the MCMC method will take exponential time even when the preference lists of the participants are severely restricted.

14. More on stable marriages « Secret Blogging Seminar - July 8, 2008

[…] from WordPress probably are no longer paying attention to this post, I thought I would top-post a comment left by Christine Cheng, a researcher who thinks about stable matchings. The full-text is below the […]

Sorry comments are closed for this entry