In this SODA ‘08 paper, they studied the problem of sampling stable matchings in the variants of stable marriage problem. It’s interesting to see that producing a fair stable marriage is a not-so-easy problem.

In the standard stable marriage problem, we have two sets M and W, corresponding men and women. Each person has a preference list of his/her possible partner of opposite sex. The goal is to produce a stable matching such that there does not exist a pair of m and w who prefer each other than their spouses in the matching. This problem has been solved by Gale and Shapley using a very simple polynomial time algorithm to produce a man-optimal matching. Here man-optimal matching means that men like their spouses better than those in any other stable matching. The matching Gale-Shapley algorithm produces also has the property that it is the worst stable matching women can get.

A fair stable matching roughly means that, in this stable matching, some men have their best achievable spouses and this is also true for some women. Since some instances of stable marriage problem do not have such stable matchings (one can find instances only have man and woman optimal matchings), we hope we can have a random sampling procedure to achieve the fairness in a expected sense. It is known that all the stable matchings of a stable marriage problem instance forms a distributive lattice. A simple idea is to do some random walk on this lattice. But they said this is hard. Instead, they studies some restricted models such as

  • k-attributes model Each person has k attributes and we rank them by projecting a point in \mathbb{R}^k into a line.
  • k-range model Any person has a predetermined rank i and it can only fall into the set \{i, i+1, \ldots, i+k-1\} in any person’s preference list.
  • k-list model Each gender is partitioned into k different groups. People in the same group have the same preference list.

They studied the distributive lattice structure under these constrained model and devise some algorithms using Markov Chain to sample stable matchings uniformly.

Since I don’t know anything about Markov Chain except its name. I cannot describe any details of this paper. Hope in the near future, I can understand this paper better.