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.

Is there always a stable assignment of applicants to companies in ANY PROBLEM INSTANCES?