(Originally posted at http://joelnoche.multiply.com/journal/item/29/The-Stable-Marriage-Problem on December 4, 2010 4:33 AM)
I was looking for some good stuff at mathoverflow.net and I came across a question about the stable marriage problem. It seems to have been first studied by Gale and Shapley (1962) (who presented it as a special case of the college admissions problem). They describe it this way:
A certain community consists of n men and n women. Each person ranks those of the opposite sex in accordance with his or her preferences for a marriage partner. We seek a satisfactory way of marrying off all members of the community. […] we call a set of marriages unstable […] if under it there are a man and a woman who are not married to each other but prefer each other to their actual mates.
Vate (1989) showed that the stable marriage problem can be modeled using a set of linear equations and inequalities and can be solved using linear programming.