The key idea of this algorithm is similar to the stable marriage problem.In this algorithm H represents hospitals and S represents students. Each hospital has to fill itspositions and the combined total positions of the set of hospitals is less than the number ofstudents and therefore there will be some students left without a position. Initially, each studentis free and every position in the hospital is free without any offers. The student is offered aposition from the hospital and is matched to the hospital but the student can leave if anotherhospital is preferred and the hospital prefers that student as well. When a position is taken, thenumber of positions decreases by 1. The positions can increase again if a student accepts aposition from h1 and then gets an offer for a position in h2, leaving h1 for h2 due to preference.The program terminates and the set is then returned to matched hospitals and matchedstudents along with left out students after it iterates through all hospitals and all hospitalpositions. Students take the first offer and the positions in a hospital get better and better interms of the students preference list ( student will only leave a position if offered a position at amore preferred hospital). In contrast, the students that the hospital gives offers to get worsesince it goes from their top preference list of students all the way to the bottom of the list untilthere are no free positions left.

When there are multiple stable assignments exist, which side does the solution found by this algorithm favor, the companies or the applicants?

Proof of Stability: We can prove that this algorithm does return a stable assignment of students to hospitals through contradiction. Assume there is a perfect matching set with students s and sand a hospital h. Now we assume that s is assigned to h s' is assigned to no hospital And h prefers s' to s This implies that h last offered s to fill its position but h should have asked s' to join due to preference. This contradicts the assumption that h prefers s' to s. If s rejected the position from h then, according to the algorithm, s should be with another hospital and cannot be free so it is a contradiction. We can also assume that there is a perfect matching set with students s and s' and hospitals h and h'. Now we assume that s is assigned to h s' is assigned to h' h prefers s' to s s' prefers h to h' This implies that h last asked s to join but h should have asked s' to join due to preference. This contradicts the assumption that h prefers s' to s. If s denied the position from h then this also contradicts the assumption that s' prefers h to h'. Therefore, the matching must be stable. Proof of Stability: We can prove that this algorithm does return a stable assignment of students to hospitals through contradiction. Assume there is a perfect matching set with students s and sand a hospital h. Now we assume that s is assigned to h s' is assigned to no hospital And h prefers s' to s This implies that h last offered s to fill its position but h should have asked s' to join due to preference. This contradicts the assumption that h prefers s' to s. If s rejected the position from h then, according to the algorithm, s should be with another hospital and cannot be free so it is a contradiction. We can also assume that there is a perfect matching set with students s and s' and hospitals h and h'. Now we assume that s is assigned to h s' is assigned to h' h prefers s' to s s' prefers h to h' This implies that h last asked s to join but h should have asked s' to join due to preference. This contradicts the assumption that h prefers s' to s. If s denied the position from h then this also contradicts the assumption that s' prefers h to h'. Therefore, the matching must be stable