stable marriage/residency problem with multiple matches

Question

Consider the stable marriage problem, where both sides want to match with multiple individuals from the other side (perhaps a fixed number, or perhaps within some range). Something like, if doctors could choose to go to more than one medical school at the same time.

Is there a variation on the deferred acceptance algorithm to handle this generalization? Can I just have each "doctor" propose to n hospitals at each step, where n is the number of hospitals he is trying to attend at once? Also, what if hospitals do not have preferences?

Answer 1

Suppose you have a doctor that you want to assign to three hospitals. Replace that doctor by three copies of him. In other words, instead of a single vertex for Dr. Smith, you have three clones, Dr. Smith #1, Dr. Smith #2, and Dr. Smith #3. They all have the same preference list.

Suppose you have a hospital that wants two doctors. You can do the same thing: instead of a single hospital, you have one entity per open position at that hospital. They all have the same preference rankings.

Now use the standard stable marriage algorithm on the resulting set of clones and open positions. This will find a stable matching that obeys the multiplicity constraints you identified; that follows directly from the correctness property of the standard algorithm.