For this problem, we will explore 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, we 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 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 GaleShapley algorithm; or (b) Give an example of a set of preference lists for which there is a switch that would improve the partner of a woman who switched preferences.
For this problem, we will explore the issue of truthfulness in the Stable
Matching Problem and specifically in the Gale-Shapley
basic question is: Can a man or a woman end up better off by lying about
his or her preferences? More concretely, we 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 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 GaleShapley algorithm; or
(b) Give an example of a set of preference lists for which there is
a switch that would improve the partner of a woman who switched
preferences.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
