Problem 1: Truthfulness in Stable Marriage
This problem explores the issue of truthfulness in the Stable Matching Problem and specifically in the Gale-Shapley algorithm. The basic question is: can a man or a woman end up better off by lying about his or her preferences? More concretely, suppose each participant has a true preference order. Now consider a woman w. Suppose w prefers man m to m', but both m and m' are low on her list of preferences. Can it be the case that by switching the order of m and m' on her list of preferences (i.e., by falsely claiming that she prefers m' to m) and running the algorithm with this false preference list, w will end up with a man m'' that she truly prefers to both m and m' ? (We can ask the same question for men but will focus on the case of women for the purposes of this question.)
Resolve this question by doing one of the following two things:
(a) Give a proof that, for any set of preference lists, switching the order of a pair on the list cannot improve a woman's partner in the Gale-Shapley algorithm; or
(b) Give an example of a set of preference list for which there is a switch that would improve the partner of a woman who switched preferences.