[Solved]: Stable marriage problem with only one side having preferences

Problem Detail: 

I was wondering about a variation on the Stable Marriage Problem. Initially, we have two sets of entities, usually males and females, and they have preference lists ranking the other group, and through a series of proposals, we end up with a stable matching.

Thinking of it like medical schools and applicants, each medical school has a different number of slots available, so is there an intuitive or simple augmentation to the basic algorithm that solves this case?

The second question is, what if only one side has a preference ranking? For example, say medical students have preferences, but the schools do not, and simply have some number of spaces available (different between each school). All (or many of) the students (say 50 students) prefer school A, but it only has 5 slots or so. Is it possible to determine if there is a "matching" that allows everyone to get a choice in their top 3 or top 5 or something along those lines?

Clearly, if schools A, B, C have only 5 slots each, and 10 students rank the schools 1. A, 2. B, 3. C it is not possible for everyone to have their top 3. There are 30 "wants" and only 15 available slots. What I am interested in is determining if it possible and if possible, finding one of those matchings.

If this question makes no sense I can try to elaborate the specific use case it came up in.

Asked By : Vishaal Kalwani

Answered By : D.W.

The answer to your first question is: yes, there is a simple augmentation. It is described in the standard literature on the stable marriage problem. See the Wikipedia article for references in the literature where this is described. It is also described here: The stable marriage algorithm with asymmetric arrays. See also http://cs.stackexchange.com/a/28528/755.

Your second question is an instance of the assignment problem. We form a bipartite graph, with an edge between a doctor $d$ and a school $s$ if the school $s$ is among $d$'s top 3 choices. Then we want to know whether there is a perfect matching in this graph. (If a school has multiple slots, then make multiple copies, one copy per slot.) There are polynomial-time algorithms to determine whether a bipartite graph has a perfect matching. See also Existence of bipartite perfect matching.

So, the answer to your second question is: yes, it is possible.

Best Answer from StackOverflow

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