patternMinor
The stable marriage algorithm with asymmetric arrays
Viewed 0 times
asymmetricmarriagethearrayswithstablealgorithm
Problem
I have a question about the stable marriage algorithm, for what I know it can only be used when I have arrays with the same number of elements for building the preference and the ranking matrices.
For example if we have 10 students that should be assigned to 10 dorms, then I can build the preference and ranking matrix of this data. The question that I have is what to do in the case that I have, for example, only 5 students to assign and for example 10 dorms. Can I still apply the stable marriage algorithm?
Maybe this question is a little bit foolish, but as I said I only saw this algorithm applied to quadratic arrays.
For example if we have 10 students that should be assigned to 10 dorms, then I can build the preference and ranking matrix of this data. The question that I have is what to do in the case that I have, for example, only 5 students to assign and for example 10 dorms. Can I still apply the stable marriage algorithm?
Maybe this question is a little bit foolish, but as I said I only saw this algorithm applied to quadratic arrays.
Solution
Yes, the stable marriage problem still makes sense with unequal arrays. Permit me to use men and women as opposed to students and dorms. There are different stable matchings that you can ask for resulting in different cases.
Let's consider the first case where we want a specific stable matching. Suppose there are $m$ men and $w$ women. Depending on which set is larger we modify the termination condition of the standard algorithm accordingly. Suppose without loss of generality we want the male optimal solution. If $m w$ then we continue until each man is either on the string of some women or has been rejected by all the women.
It's easy to see how the above algorithm can be applied to the second case where any such stable matching is required. Just have the smaller set be the one that proposes.
The third case depends on a theorem that states that if a person is unmarried in one stable matching then they are unmarried in every stable matching. The case then becomes identical to the case with equal sized sets.
More detail on all three cases as well as pseudo-code for each algorithm can be found in McVitie and Wilson's paper titled "Stable marriage assignment for unequal sets".
- A specific stable matching is desired, either male optimal or female optimal solution
- Any valid stable matching is desired
- All the stable matchings are required
Let's consider the first case where we want a specific stable matching. Suppose there are $m$ men and $w$ women. Depending on which set is larger we modify the termination condition of the standard algorithm accordingly. Suppose without loss of generality we want the male optimal solution. If $m w$ then we continue until each man is either on the string of some women or has been rejected by all the women.
It's easy to see how the above algorithm can be applied to the second case where any such stable matching is required. Just have the smaller set be the one that proposes.
The third case depends on a theorem that states that if a person is unmarried in one stable matching then they are unmarried in every stable matching. The case then becomes identical to the case with equal sized sets.
More detail on all three cases as well as pseudo-code for each algorithm can be found in McVitie and Wilson's paper titled "Stable marriage assignment for unequal sets".
Context
StackExchange Computer Science Q#7545, answer score: 9
Revisions (0)
No revisions yet.