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.)
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
