The stable marriage problem

The first problem considered in Algorithm Design, by Jon Kleinberg and Éva Tardos, is the stable marriage problem. (I think this is a fairly standard first problem in an algorithms text, but I may be wrong.) The problem is as follows: let there be n men and n women. Let us say that each of the men can rank the women in order of how much he would like to be married to them, and the women have a similar ordering for the men. We would like to pair these people off in marriage in such a way that we can't find a man and a woman who both prefer each other to the person that they're currently married to. (It's a bit unclear who "we" are, at least in this version of the problem; most of the real-world examples I can think of where everybody gets matched at the same time are more like what the Wikipedia article calls the "college admissions" or "hospitals/residents" problem.) Anyway, the procedure works as follows:

All individuals start out in the state "free". The state "engaged" is also possible.

Pick a man arbitrarily. He proposes to the women who is highest on his preference list that he has not already proposed to. If she is free, or if she prefers the man who just proposed to the man she's currently with, she accepts the proposal and they become "engaged". (If she just broke off an engagement, then the man in question becomes "free" again.) Repeat until everybody's married.

Now, it turns out that which men we choose arbitrarily at each juncture when we're allowed to do so doesn't matter. Regardless of the choices, each man ends up with the best woman that he possibly could among all stable matchings; each woman ends up with the worst.

Although this is clearly a toy version of the real-life marriage problem, this has an interesting implication; historically, men did the proposing. Now, women can propose as well (although anecdotal evidence suggests men do most of the proposing). This is probably good for women, bad for men.

There's also an interesting combinatorial question hidden here, which I haven't thought about -- there are (n!)²ⁿ possible sets of preference lists when we have n men and n women. Some of these sets of preferences will have more stable matchings than others; what is the largest possible number of stable matchings? How is it distributed? Is the number of stable matchings corresponding to some set of preference lists even something one could easily count?

One final comment: I've seen the stable marriage problem a few times before, and usually a mention is worked in of something called the "same-sex stable marriage problem" -- often called the "stable roommates problem" -- in which everybody has a preference list for everybody else. This could just as well be called the bisexual stable marriage problem, but this usage doesn't seem to be as common.

Edit (Saturday, 12:15 pm): stable matchings aren't unique. But as I recently learned from Alexander Holroyd, Robin Pemantle, Yuval Peres, Oded Schramm. "Poisson Matching" (arXiv: 0712.1867), they are unique when the preferences are symmetric in a certain sense. One example of symmetric preferences -- the one considered in that paper -- is the case when the men and women are associated with points in Euclidean space, and each prefers to be matched with the people of the opposite gender who are closest in distance. (When they first claimed that stable matchings were unique, I was tempted to just stop reading -- but I didn't, and I'm glad.)