(Please give explanation. Don\'t copy paste algorithm) In the stable marriage al
ID: 3843666 • Letter: #
Question
(Please give explanation. Don't copy paste algorithm)
In the stable marriage algorithm described in class, the men propose to the women in preference order, and each woman accepts the best proposal she has seen so far. If there are n men and n women, how many women (as a function of n) can be forced to settle for their last choice? Describe a scenario that would cause this many women to be matched with last-choice men: what preference orderings cause this behavior, and what does the algorithm do when given this input?
Explanation / Answer
I don't what stable marriage algorithm you have discussed in class, however the famous stable marriage algorithm Gale–Shapley can help us to match the preference. The main idea of this algorithm is to iterate through all of the man while he has not been matched. Each un-matched man goes to every women in order of preference and if the woman is also free then it is a match. If the women is not free then either see can say no or break her current matching if and only if the man is in her higher preference. here goes the algorithm :
Initialize all men and women to free
while there exist a free man m who still has a woman w to propose to
{
w = m's highest ranked such woman to whom he has not yet proposed
if w is free
(m, w) become engaged
else some pair (m', w) already exists
if w prefers m to m'
(m, w) become engaged
m' becomes free
else
(m', w) remain engaged
}
All the n women can be forced to settle for their last choice. How? If the preference ordering is inverse case, that is a particular man has some ordering and then the woman who is her first preference has inverse ordering. For example consider the following case:
MAN has the following matrix:
D C B A
A D C B
B A D C
C B A D
Women has the following matrix:
0 3 2 1
1 0 3 2
2 1 0 3
3 2 1 0
As you can see, MAN 0 has preference D C B A whereas Woman D has preference 3 2 1 0 that is MAN 0 is the last choice. This can happen when MEN have unique 1st preference and get settled at first only while Women have that man as last preference. The algorithm in the above case runs only for n times as there is no collision of preference.
I hope you understood the algorithm, if you have any doubts let me know !
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.