Hospital Residents Problem

In this article, we introduce and discuss an algorithm used to match residency applicants to their most preferred programmes. This problem is called the 'Hospital Residents Problem'. The algorithm used is a slight variation of the Gale Shapley algorithm. You can also check this article on Stable roommmates problem

We have two groups: Applicants and Programmes.

• Each member of the group will have a choice list. All the hospital programmes will release a choice list of the preferred applicants and all the applicants will also rank the programmes in their choice list. In this matching algorithm, it is not necessary to rank all the available options in the choice list, unlike stable matching problem. An applicant may rank a few programmes in his/her choice list and the programmes may choose to extend offers to only a few shortlisted applicants.
• Also, each programme announces certain number of vacancies beforhand and takes in only those many residents for that year.
• This algorithm is applicant proposing i.e it produces a matching based on the applicants preferred choice of programmes. Here, the proposing group is always the applicant group.
• For a match to occur both the applicant and the programme should rank each other.

It may happen that an applicant is not matched to any programme and that a programme is left with vacant positions after the matching is completed. To avoid this, there are certain tips which are shared at the end of this article.

Example

When this algorithm starts, it will try to match each applicant with his/her first choice. If that does not happen the algorithm will try to match the applicant to the second choice and so on.
Let's see an example to get a better understanding of the algorithm.

We have 5 applicants {Anthony,Samantha,Jos,Lara,Darry} and 3 programmes {City,Mercy,General} each with 2 vacancies.

The choice lists of applicants are as follows :

The choice lists of programmes are as follows :

The algorithm starts by assigning Anthony to City and since City has ranked Anthony second and has no other tentative matches yet, Anthony is tentatively matched to City.

Next the algorithm matches Samantha. She ranks City first, so the algorithm tries to match her there. City ranks Samantha third and City has one vacancy left. So, Samantha is tentatively matched to City.

Jos has also ranked City first but because both positions are tentatively assigned to higher ranked applicants, Jos is not matched to City. The algorithm tries to match Jos to his next choice which is, General. General has ranked Jos 3rd and since there are no matches for General yet, Jos is matched to General.

Lara ranked Mercy first but Mercy didn't rank Lara so she can't match there. The algorithm moves to Lara's second choice - City but City already has it's 2 positions filled and this match is rejected. Lara's third choice is General, which has one vacany left, so Lara tentatively matches with General.

Finally, the algorithm goes to match Darry, whose first choice is City and City has ranked Darry as their first choice. Hence, Darry receives a confirmed match from City. But as City has only 2 positions, we need to reject one of the matches made previously. The least preferred choice (tentatively assigned) of City is rejected, who is Samantha.
Hence, now only Samantha has not been successfully matced to any programme and the algorithm attempts to match her. Samantha's second and last choice is Mercy but as Mercy hasn't ranked Samantha, she does not match there.

The algorithm is now complete. The final matches are:

• Anthony - City
• Darry - City
• Jos - General
• Lara - General
• Samantha is left unmatched.

City and General have been able to fill all of their positions completely. However, Mercy has both the positions vacant. Mercy submitted a short rank list and was left with vacant positions at the end of the matching.
Samantha too,ranked only 2 available options and could not go through. Jos, Darry and Lara played smart and used all the available options in their ranking list. Anthony took a risk of ranking only one programme in his choice list but still managed to get through as he was better ranked by the programmes.

Tip

It is observed that applicants with more choices in the choice list have a higher probability of being matched to a residency programme. Similarly, programmes which have less shortlists may be left with vacant positions at the end of the matching.

PseudoCode

function match(residents, programmes)
{
    set all residents and programmes to UNMATCHED
    while (more residents are UNMATCHED)
    {
        p = next programme on residents
        if(p is UNMATCHED)
        {
            MATCH p with resident
        }
        else
        {
            prevRes = resident matched with p
            if(p prefers resident over prevRes)
            {
                set prevRes to UNMATCHED
                MATCH p to resident
            }
         }
         remove p from residents list
    }
}

Time and Space complexity

This algorithm takes O(n^2) time where n is the number of aspirants.
For clarity, let us consider no of aspirants = a and number of residency programs = p .Note that a = p = n.

In the worst case, all aspirants will be assigned to their least preferred choice,so we make p iterations for each aspirant

Therefore,in the worst case scenario, we make a total of a * p iterations and as a = p = n , time complexity becomes O(n^2).