Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
marriage problems in general do not require having same numbers in both sides. For example, assigning reviewers to submissions in scientific conferences can be seen as a marriage problem. Here the problem is an optimization problem. –  seteropere Dec 22 '12 at 21:56
add comment

2 Answers

up vote 2 down vote accepted

You can add $5$ dummy students, and put them low in the dorms' preference order. The resulting perfect matching $\pi$ will have the following two properties:

  1. There is no student $s$ and dorm $d$ which are not matched such that $s$ prefers $d$ to $\pi(s)$ and $d$ prefers $s$ to $\pi(d)$.
  2. There is no student $s$ and empty dorm $d$ such that $s$ prefers $d$ to $\pi(s)$.
share|improve this answer
    
after adding the 5 dummy students can I use the Gale Shapley algorithm for solving the matching? –  Little Dec 23 '12 at 23:19
    
You ca use whatever algorithm you want that finds a stable matching. The properties I mention are just a restatement of what a stable matching is. –  Yuval Filmus Dec 24 '12 at 10:39
add comment

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.

  • 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$ we continue until $m$ women have been proposed to. 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".

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.