There are n med-school students and n hospitals. Each med-school student has a strict preference over the hospitals, and each hospital has a strict preference over the med-school students. Hospitals and students are matched using the Gale-Shapely algorithm. (a) Prove that there is no matching, stable or unstable, in which every hospital has a stu- dent whom it prefers to its student in the stable matching resulted by Gale-Shapely algorithm. (Use contradiction to prove the argument, and consider the last student who receives a proposal in the Gale-Shapely algorithm.) (b) Provide an example in which a student benefits from falsifying their preference list in the Gale-Shapely Algorithm. (Use the example with three med-school students and three hospitals.)
There are n med-school students and n hospitals. Each med-school
student has a strict preference over the hospitals, and each hospital has a strict preference over the
med-school students. Hospitals and students are matched using the Gale-Shapely algorithm.
(a) Prove that there is no matching, stable or unstable, in which every hospital has a stu-
dent whom it prefers to its student in the stable matching resulted by Gale-Shapely algorithm.
(Use contradiction to prove the argument, and consider the last student who receives a
proposal in the Gale-Shapely algorithm.)
(b) Provide an example in which a student benefits from falsifying their preference list in
the Gale-Shapely Algorithm. (Use the example with three med-school students and three
hospitals.)
The goal of the Gale-Shapely algorithm is to find stable and mutually satisfying pairings in the stable marriage problem, which is a situation where two sets of people have preferences over members of the other set. Through a series of proposals and acceptances, this algorithm functions. Each person in one set makes a proposal to their favorite person in the other set, and people in the other set tentatively accept proposals based on those preferences. Once there are no more improvements that can be made, the process stops, leaving behind stable pairings in which no two people would choose the other over their current partners. The Gale-Shapely Algorithm ensures an effective and equitable way to create stable matches that respect individual preferences in a variety of real-world contexts, such as matching students to schools or patients to hospitals.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
