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?

  • $\begingroup$ I find it unclear exactly what the problem is and what the constraints are. Do you know in advance how many hospitals each doctor needs to be matched to, and how many doctors each hospital needs to be matched to? $\endgroup$
    – D.W.
    Jun 7 '18 at 21:32
  • $\begingroup$ Yeah, sorry, you do know that in advance! I did some more digging, and I think the normal way to describe what I was thinking about is close the many-to-many stable matching problem (with substitutability). The solution is the expected extension of the delayed acceptance alg. The only thing is, I haven't seen anything about what to do if one side doesn't have preferences, or might have ties in preferences. $\endgroup$
    – AWhite
    Jun 8 '18 at 2:12

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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