The Stable Marriage Problem

(Originally posted at on December 4, 2010 4:33 AM)

I was looking for some good stuff at 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.


Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s