The stable marriage algorithm with asymmetric arrays

Problem Detail: 

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.

Asked By : Little

Answered By : Yuval Filmus

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)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7545