I'm at the Cornell Probability Summer School. (This announcement is too late for anybody who wants to find me here, as it's almost over! But I have been tracked down by at least one fan.)
In a lecture here this morning, Ander Holroyd spoke about the stable marriage problem and variations of it involving point processes (see this paper of Holroyd, Pemantle, Peres, and Schramm, which I've mentioned before, for details). The goal of the problem is to pair up n men and n women in such a way that no two people who aren't married to each other prefer each other to their current partners; this is called a "stable matching" and one always exists.
The original paper on the stable marriage problem is that of Gale and Shapley, in 1962. This paper also talks about the "stable roommates" problem, which is the analogous problem where everybody is of the same gender. Rather surprisingly, I never realized that "roommates" might be a euphemism here, which is something that Holroyd pointed out this morning to quite a bit of laughter.
Subscribe to:
Post Comments (Atom)
3 comments:
Are there interesting things to say about the stable roommate problem? I assumed that since such pairings don't exist in general*, finding a useful algorithm would be hopeless.
*For instance, consider the case with 4 people where A, B and C all prefer each other to D, and between the other two in that triplet, A prefers B, B prefers C, and C prefers A.
And I had always heard the "stable gay marriage problem" as a (facetious) political argument.
Yes, it's a euphemism. "Stable roommates" are, in fact, horses.
Post a Comment