Since people who don’t get alerts 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 fold. The main upshot is that there are some deterministic algorithms which produce fairer matchings than Gale-Shapley’s but they’re hard to implement.

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.

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 maximizes 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).Yes, although to clarify, you must mean the maximum of happiness only among stable matchings. The matching theorem is non-trivial because the maximum-happiness matching doesn’t have to be stable. Two people can elope to make themselves a little happier, even if it makes their spouses deeply unhappy.

(Also note to the mods: There is an 8 and a parenthesis that was inadvertently turned into a smiley.)

Thanks, Greg. I had noticed the smiley before, but your comment motivated me to actually find the “turn off irritating emoticons” setting.

I’m just interested in the use of the word “egalitarian” here – there was a talk by a political philosopher here at ANU about egalitarianism the other day, and he pointed out the severe ambiguity in the word. I think most philosophers would prefer to use “utilitarian” to describe the “egalitarian” matching described here, and “egalitarian” to describe the “minimum regret” (which one might also call “maximin”). But that is a really neat fact about the median stable matching! (I suppose since the description of that matching only depends on ordinal facts about the rankings each man and woman give each other, it can’t guarantee anything about the total happiness given by this matching.)

“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.”

I also share this sentiment to Gale-Shapley’s theorem. It was an unexpected surprise how this theorem was used in 1994 by Fred Galvin in his solution to Dinitz’ conjecture.