4
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 1. One question at a time, please. I suggest you edit your question to focus on just one question. If you have two questions, post two separate questions. This site is designed for a single question that can be answered (so you can accept one right answer, and we can vote on answers). 2. What research have you done? The Wikipedia article contains information about how to solve your first problem, and contains links and resources where you can learn more. en.wikipedia.org/wiki/Stable_marriage_problem In the future, please try to do a bit more research before asking. $\endgroup$
    – D.W. ♦
    Commented Oct 5, 2014 at 2:57

1 Answer 1

Reset to default
5
$\begingroup$

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 https://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.

Improve this answer
$\endgroup$

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