According to Wikipedia, The Stable marriage problem is stated as, "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"."
If this sounds confusing, let me restate it for you. There are two disjoint sets $M$ and $W$. The cardinality of both the sets are equal and let it be $n$. If each element in $M$ has ranked all the elements in $N$ from $1$ to $n$ (A unique number to each element of the set) and vice-verse, we have to find a stable match between the two sets. Let $A\inM$ and $B\inN$, where $A$ and $B$ are not matched with each other, then a match between the two sets is said to be stable if for any pair $(A,B)$, it should not happen such that $A$ would prefer $B$ over its current partner and $B$ as well prefer $A$ over its current partner.
When I first went through the problem statement, I thought how can anyone possibly find a match. I was referring to real time implications. I was flabbergasted to find out that this algorithm was basically framed to solve a problem where graduating medical students are assigned to hospital jobs. And guess what, it worked!
David Gale (left)and Lloyd Shapely (right), in the year 1962, proved that given any $n$, it is always possible to solve SMP(Stable Marriage Problem) and hence find a match.
Here's how they explain there algorithm:
It basically consists of a number of rounds. In each round, each unengaged man proposes to a woman he prefers the most and has not proposed yet. And each woman considers all her suitors and replies "Maybe" to the one she most prefers and to rest all she says a straight "No". This will go on and on unless and until there is a match. When this happens, the woman is engaged to her most preferred suitor and that suitor is engaged to her.
To begin with the first round, at first,each unengaged man proposes to the woman he prefers most. And then,each woman replies a "maybe" to the suitor she prefers most and "no" to the rest all.
In the following rounds, each unengaged man proposes to the most preferred woman he has not proposed yet. This will be irrespective of whether the woman is engaged or not. And each woman replies with "Maybe" to the most preferred suitor and "no" to the rest all. This will be again irrespective of whom she is currently engaged to.
However there is a prerequisite which says that all the participant's preference list should be complete and no candidate should be declared unacceptable.
In the end,
- Everyone gets married: A woman is always engaged to someone since she replies "May Be" to a person in each round.( If she is happy with her first choice, she might not change her decision and just say "no" to remaining candidates in all the rounds. Even in that case she will be engaged to her first choice always).
A man proposes to every woman (if necessary). So there can be no man and woman unengaged. - The marriages are stable: Plagiarising wikipedia, let me explain this with an example. Let Aishwarya and Abhishek be married at the end, but not with each other. Now, its impossible for both Abhishek and Aishwarya to prefer each other over their current partners.Here's how. Since Abhishek prefers Aishwarya over his current wife, he must have proposed Aishwarya, before he proposed his current partner. There are two cases:
1. If Aishwarya had accepted his proposal, then she surely rejected him for her current partner. And that's the reason she is currently married to him. So, Aishwarya cant prefer Abhishek over her current partner.
2. If Aishwarya hadn't accepted Abhishek's proposal, then she never liked him in the first place.
You can try out and play with this algorithm. Code it in any language you like. Its quite easy. In the following you are asked for the order of preference and it gives you a stable match.
http://sephlietz.com/gale-shapley/.
The following is a link to the paper studying the Gale-Shapely algorithm. It focuses on proving how appropriate are stable matching mechanisms. It says, even if a woman knows the preference list of all other women, she cannot cheat.
www.columbia.edu/~js1353/pubs/tst-ms01.pdf
You can also find an interactive flash demonstration of this problem. After going through it you can easily understand the problem.
This algorithm is also currently being employed in New York and Boston Public schools, to assign students to schools.
Shruti Ranade
