Assignment problem with priorities and scores

Question

I have run into a real problem that is actually a sort of assignment problem. I am describing it here because I am interested in knowing whether this problem already has a name (and whether there is an algorithm to efficiently solve it). It can be stated as follows:

We have $n$ candidates $C_1, \dots, C_n$ (workers, students, etc.), and we also have $m$ available job posts or categories $P_1, \dots, P_m$. Each job post $j$ includes $p_j \ge 1 $ available slots (job places), so that the total number of available jobs is $M = \sum_{j=1}^m{p_j}$; tipically $n > M$.

Each candidate $i$ applies for $c_i \ge 1$ different job posts. Also, they are asked to express their preferences by ranking the job positions they are applying for. Let us call $A_i = (a_1^i, \dots, a_{c_i}^i)$ the set of jobs applied for by $C_i$ sorted by descending preference. This means that each $a_k^i$ is a different element of the set of post indexes $\{1, \dots, m\}$. More precisely, $a_k^i$ stands for the job post that candidate $i$ has applied for as their $k$-th preference (so, the smaller $k$ the higher preference post $a_k^i$ has for candidate $i$; particularly, $P_{a_1^i}$ is the job post they want the most).

Each applicant is given a score, which can be different for each job post. Let us call $s_{i,j}$ the score that candidate $i$ gets for post $j$.

The problem consists of assigning candidates to jobs, so that the following conditions are met:

1. Each candidate can only be assigned to a post they have applied for, and only one post at most.
2. For each post $j$, a maximum of $p_j$ candidates can be assigned to $P_j$.

These were quite obvious. More importantly:

3. Higher scores have to be chosen before than lower ones: A candidate cannot be left without a job if, in any of the posts they applied for, a candidate with a lower score was admitted. In other words: a candidate can be assigned to a post only if all the candidates with higher score than them for that post are also assigned to that post or to any other post (with more priority for them).

4. Priorities have to be taken into account: A candidate has to be assigned to the post with the highest preference for them, if possible. In other words, if a candidate can be assigned to more than one post, they must be assigned to the post for which they expressed the highest priority among them.

My question is: Is this problem known by any concrete name (such as assignment problem with priorities and scores or something similar)? The point is: I want to look for information about this problem, but I do not know how it should be referred to.

I have figured out an algorithm to solve this problem on my own. I am sure that this algorithm must have been already published by someone somewhere. Do you know any numerical algorithm to solve this assignment problem? I am not asking for a complete algorithm; as I have just said, I already have one. I just want to check if my solution was already given by someone else before.

Answer 1

This seems to be the assingment/matching problem for the National Resident Matching Program which is closely related to the stable marriage problem.

In the resident matching problem your $C_i$ are medical students which have finished and need to apply to do residency. The $P_i$ are hospitals where they can train. Each hospital has some limit $p_i$ of people they can train.

Here is a video explaining the algorithm from the National Resident Matching Program.