# Algorithm for creating a matching while satisfying multiple priority lists - Bipartite Graph Theory

I have to design a student-job placement algorithm. The problem statement is :

Let there be two sets - one set of jobs $J = \{j_1, j_2, j_3 .... j_m\}$ and other set of students $S = \{s_1, s_2, s_3 .... s_n\}$ with $n \ge m$.

Each job $j_i$ has its priority list (ranked list) of students and each student $s_i$ has its priority list (ranked list) of jobs.

I have to create a matching in the bipartite graph of J and S as : $M= \{ (s_{i_1},j_{k_1}), (s_{i_2},j_{k_2}), (s_{i_3},j_{k_3})....(s_{i_m},j_{k_m}) \}$ with the following constraints :

• Each job must be matched with exactly 1 student, i.e the matching M should be J-saturated with each job getting only 1 student.

• There should be no unstable pairs, i.e there should be no pairs in M like $(s_i,j_i)$ and $(s_k,j_k)$ where $s_i$ prefers $j_k$ over $j_i$ and simultaneously $j_k$ prefers $s_i$ over $s_k$. In other words, all the priority lists of students and jobs must be followed.

• Let the rank of a student selected in a job $j_i$ in its priority list be $r_i$ and so for each student $s_i$, the rank of the job which he/she gets in his/her priority list be $t_i$. For a student who does not get a job, $t_i$ would be one more than the length of that student's priority list. Let $w_1$ and $w_2$ be constants. The constraints here are :

• $w_1 \sum_{i=1}^m r_i$ + $w_2 \sum_{i=1}^n t_i$ should be minimized so that both jobs and students are happy with the allocation (matching M).

• $w_1$ + $w_2$ = $1$ and they both are constants. A simple particular case would be $w_1$=$w_2$=$0.5$

Please help me design this kind of a combinatorial algorithm which would make both students and jobs happy by giving both of their priority list some predefined weightage.