The Stable Marriage Problem

(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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s