There are n hospitals recruiting doctors, and there are m med school graduates applying for the n vacancies. For each hospital i (i n), it has vi...

There are n hospitals recruiting doctors, and there are m med school graduates applying for thenvacancies. For each hospital i (i ≤ n), it has vi vacancies.∑vi≤ m . Every hospital has its owni =1preference over all m applicants. And every applicant has his or her own preference over allhospitals. Naturally, we’re interested in an employment that is stable. An employment isunstable if one of the following holds:• There exists a hospital h and a doctor d not employed by h, such that d prefers h to hisor her current employer, and that there’s a doctor d' employed by h who is less favoredthan d by h.• There is a hospital h and an unemployed doctor d, such that there’s a doctor d'employed by h who is less favored by h than d.An employment is stable if it is not unstable. Prove the existence of a stable employment.