3
$\begingroup$

I am trying to find an algorithm which calculates an optimal and stable allocation of $n$ students to $m$ projects, where each student strictly ranks all projects by preference. The available projects are predetermined and of fixed number and each student needs to be allocated to exactly one project. Each project needs at least one student, but can hold up to a maximum of $y$ students.

For my purposes, there will be on average between 8 to 15 projects available and 80 to 250 students to assign to these projects, resulting in average group sizes of 8 to 15 students per project. A reasonable value for $y$ is usually $\frac{n}{m}+2$.

The definition of optimal and stable as put by @Gassa:

(1) There is no student $S$ assigned to project $P$ such that $S$ likes $Q$ more and $Q$ has an empty slot; (2) there is no pair of students $(S,T)$ such that the current assignments are $S→P$ and $T→Q$, but $S→Q$ and $T→P$ would both be more preferred.

All sort relevant sources I could find so far (listed below) either require an equal number of students and projects (stable marriage) or allocate only one student to each project (exchange-stable matching [1] / the matching problem) and I find it non-trivial to adapt these algorithms for the described purpose.

Sources

$\endgroup$
  • 1
    $\begingroup$ What does "stable" mean , if projects don't rank students? Can you define precisely what "optimal" means in this context? $\endgroup$ – D.W. Jul 5 '18 at 6:52
  • $\begingroup$ @D.W. I'd state it as such: (1) there is no student $S$ assigned to project $P$ such that $S$ likes $Q$ more and $Q$ has an empty slot; (2) there is no pair of students $(S, T)$ such that the current assignments are $S \to P$ and $T \to Q$, but $S \to Q$ and $T \to P$ would both be more preferred. The approach in my answer seems so trivially take care of these. But it could fail if the definition of stableness is in fact different. $\endgroup$ – Gassa Jul 5 '18 at 9:05
  • $\begingroup$ OK. That sounds like a definition of "stable". What's the definition of "optimal"? Or are you really asking only to find any stable assignment (and you will consider any stable assignment to also be optimal)? And, can you edit the question to incorporate this information into the question? We want questions to stand on their own, so people don't have to read the comments to understand what you are asking. $\endgroup$ – D.W. Jul 5 '18 at 14:48
  • $\begingroup$ So @ingr8, what's are the definitions of "stable" and "optimal", and is my answer sufficient? $\endgroup$ – Gassa Jul 8 '18 at 10:37
  • $\begingroup$ Yes, it is indeed sufficient and I included it in the answer. Thank you so much! $\endgroup$ – ingr8 Jul 9 '18 at 16:30
1
$\begingroup$

This sounds much like a problem for minimum-cost maximum flow.

Construct a network. The nodes will be the students, the projects, and the added source and sink.

Add an edge with capacity $1$ and cost $0$ from the source to each student.

Add an edge with capacity $y$ and cost $0$ from each project to the sink.

Add an edge with capacity $1$ and cost $r_{i,j}$ from each student $i$ to each project $j$, where $r_{i,j}$ is the rank given by student $i$ to project $j$, the most preferred being ranked $1$. (Alternatively, we can give negative scores, $-m$ up to $-1$, or even $-(2^m)$ up to $-(2^1)$, and more negative is more preferred. I believe the exact scheme is not significant.)

Now find the minimum-cost maximum flow. The maximum-ness of the flow means that each student is assigned to some project, because the maximum flow is obviously equal to the number of students.

The condition which can break is that each project gets at least one student. (Before proceeding to remedy this, first, check if the values $n$, $m$, and $y$ make failing this condition at all possible.) We can force it by splitting the edges from projects to the sink: instead of one edge of capacity $y$ and cost $0$, we can have an edge of capacity $1$ and cost $-L$, and another of capacity $y - 1$ and cost $0$. The value $L$ is a large constant, effectively infinite compared to all other costs: if we just use the ranks from $1$ to $n$, perhaps something like $m \cdot n$ will suffice. This way, a minimum-cost flow will have to add at least one student to every project in order to use all of the available edges of cost $-L$.

The thing left to prove is that the resulting arrangement is stable. Indeed, if the stable condition was not satisfied, we could just make a local change, like switching a student to their more preferred project, or swapping the projects for two students. These would result in strictly lower cost with the same flow, which would in turn contradict the fact that we found the minimum cost flow.

I'm not going into details here (we should start with a formal definition of stableness when only one side has preferences), but hope that they turn out trivially right. In the unfortunate case they don't, the first I'd do is revisit the cost assignments for $r_{x,y}$.

$\endgroup$
  • $\begingroup$ Great idea for an algorithm -- has this been implemented anywhere such that it could be shared, generalized, or used by others? $\endgroup$ – Zediiiii Aug 8 at 4:11
  • $\begingroup$ @Zediiiii No implementations I know of. However, didn't search for it specifically. Anyway, I think an ad hoc solution would be no more than 200 lines in any modern imperative language. The way to go may be asking your local students to implement it as a bonus problem :) . $\endgroup$ – Gassa Aug 8 at 9:53
  • 1
    $\begingroup$ See my answer here for a list of a bunch of implementations. $\endgroup$ – Zediiiii Aug 9 at 19:31

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.