Home > Applied Algorithms, Greedy > Stable Marriage Problem

Stable Marriage Problem

Please note before diving in: This is an algorithmic problem. If you land at this page looking for solution to something different, please visit a marriage counselor. 😛

Poor jokes apart, this one is another famous problem of the computer science domain. Here is how the problem statement goes: (source: Wikipedia)

Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are “stable”.

So basically you have to pair people in such a way that they have no better choice. You are given the preference list of each of the n men and n women and are supposed to give the perfect pairing. Now with no other conditions imposed, you can treat this problem as a simple greedy problem. Here is what your algorithm should do:

The algorithm will work in iterations.

For the first time, each unengaged man proposed to the woman he prefers the most (i.e., woman highest on his priority list). All the women would consider their proposals and select the proposal from the man who is higher than others on her list of preferences. They are now tentatively engaged.

Now in every iteration from now on, each unengaged man will propose to the woman who is next on his list of preferences. The women will compare all the proposals they are currently getting along with the one whom they are tentatively engaged to (if any). They will again select the proposal of the man who is highest on their list of preferences.

This process stops when all men are engaged after an iteration.

This greedy method was simple to understand and hopefully you would have got it by now. This is known as the Gale-Shapley algorithm. If anyone has any trouble in figuring it out, check out the gif animation below to see a sample case.

Brilliant! So you are now equipped with another algorithm to tackle your day-to-day marital, friendship and roommate related problems. 🙂

Have fun!

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

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

%d bloggers like this: