Pairing students with labs

Question

We have a practical problem in a MSc program at a university in which a student has to be assigned to a lab. The numbers involved are not very large so I am not looking for a fast solution, but rather an easy to understand solution so that both students and the group leader can be provided justification for the proposed pairing.

Given 2 list

 S1 Li,Lj,Lk
 S2 Lu,Lv,Lw
 .
 Sn

Here each student S has listed their top 3 labs in order of preference. So student S1 would ideally be like to be in Lab i. If that Lab does not want him, then he would want to be in Lab j and so forth.

and

 L1 Si,Sj,Sk
 L2 Su,Sv,Sw,Sx,Sy
 .
 Lm

Where each lab lists students in that they would like in the lab. So here Lab 1 would first want student i if he has selected this lab (in one of his top 3 choices). Note that the lab can pick as many students as the like.

Constraint is that each student can be in only one lab, but each lab may have 0,1 or more students.

Goal is to produce a matching (Si,Lj) in which all students are assigned to a lab and the pairing leads to the greatest satisfaction.

The satisfaction score is defined as

Z=sum_{i=1..n}( sum_{j=1...m} (abs( i-j))

Intuitively this tries to pair up as many students and labs with their best choice.

So I seek an algorithm for this optimization algorithm which seeks a solution that is to minimize Z.

A possible partial solution is the following:

Define an array called Assigned of length L. And initialize it to all false

First, match the first choices and discard these students

for each s in {S1,..,Sn}:
      Assigned[s]=False
Assigned[s]=j
repeat until all(Assigned)==True:
for each s in S:
     if RANK(Lj,s)==1:
          Assigned[s]=j # i.e. pair student s with lab Lj
          del(S,s) # delete s from the list S

The function RANK(Lj,s) returns the position in the preferred list of students in Lab j. If student s is not in the list of desired students in lab j then return infinity.

I am not sure how to proceed from here or whether this approach minimizes the score Z.

Any help would be much appreciated.

mcdowella mcdowella · Accepted Answer · 2017-02-19T05:43:33

It seems to me that you are trying to solve an instance of the https://en.wikipedia.org/wiki/Assignment_problem which therefore can be solved by e.g. https://en.wikipedia.org/wiki/Hungarian_algorithm. The assignment problem talks in terms of agents and tasks. Here an agent might be a student and a task a free slot in a lab. If you have more free slots than students, then you can create dummy students, where the cost of assigning any dummy student to any free slot is always the same.

You might wish to look at https://en.wikipedia.org/wiki/Stable_marriage_problem and the hospital/residents problem it points at. This looks like it is trying to solve the sort of problem you are looking at, but it probably doesn't use your particular satisfaction score. These solutions have been round long enough to be tested against potential political problems that you don't mention. Is there any incentive for people to lie about their preferences? Will the solution lead to a situation in which two students agree that they want to swap their assigned slots after the assignment?

Pairing students with labs

1 Answers