Recall that one algorithm to solve the StableMarriage problem is ProposeDispose (also known as Gale-Shapley) with the me
Posted: Fri May 20, 2022 6:16 pm
Recall that one algorithm to solve the StableMarriage problem is
ProposeDispose (also known as
Gale-Shapley) with the men proposing and the women disposing.
Answer the following 2-part
question assuming that this algorithm will be used.
a) Give an instance of StableMarriage where ProposeDispose with the
men proposing results in
every woman getting her least favorite man (last choice on her
preference list).
b) Show that no instance of StableMarriage where ProposeDispose
with the men proposing
never results in every man getting his least favorite woman (last
choice on his preference
list)
Please answer questions by creating a table, with (m1-m4) and
(w1-w4) as the notation.
ProposeDispose (also known as
Gale-Shapley) with the men proposing and the women disposing.
Answer the following 2-part
question assuming that this algorithm will be used.
a) Give an instance of StableMarriage where ProposeDispose with the
men proposing results in
every woman getting her least favorite man (last choice on her
preference list).
b) Show that no instance of StableMarriage where ProposeDispose
with the men proposing
never results in every man getting his least favorite woman (last
choice on his preference
list)
Please answer questions by creating a table, with (m1-m4) and
(w1-w4) as the notation.