Facebook
Google
GitHub
Linkedin
Hi,
I want to understand Stable Matching algorithm from wiki which is given below:
The attached image1 shows an example for stable matching. The green background shows one possible matching but the link below says that its not right:
Matching Algorithm
According to link, this is not a stable choice even though Bradley and Charles are getting their first choices.
On the other hand it shows image2 as the right answer but again in the image 2 only 2 persons are getting the correct choices
If we apply the algorithm on image2 then first Albert would go to Diane and Diane would accept the proposal. But she can reject it in round2 because Albert is not the first choice of Diane. Similarly Bradley will propose to Emily and Emily would accept the proposal, but again Emily can reject it because Bradley is not the first choice of Emily. Now Charles can’t propose to Diane because Diane has already accepted Albert, similarly Charles can’t propose to Emily because Emily has already accepted Bradley, but Fergie accepts his proposal.
In addition to the correct matching answer in the image2, I can't understand the following sentence:
Stable matching: No unmatched man and woman both prefer each other to their current spouses
Somebody please explain me how we do the optimal matching.
Zulfi.
I want to understand Stable Matching algorithm from wiki which is given below:
Code:
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
}Matching Algorithm
According to link, this is not a stable choice even though Bradley and Charles are getting their first choices.
On the other hand it shows image2 as the right answer but again in the image 2 only 2 persons are getting the correct choices
If we apply the algorithm on image2 then first Albert would go to Diane and Diane would accept the proposal. But she can reject it in round2 because Albert is not the first choice of Diane. Similarly Bradley will propose to Emily and Emily would accept the proposal, but again Emily can reject it because Bradley is not the first choice of Emily. Now Charles can’t propose to Diane because Diane has already accepted Albert, similarly Charles can’t propose to Emily because Emily has already accepted Bradley, but Fergie accepts his proposal.
In addition to the correct matching answer in the image2, I can't understand the following sentence:
Stable matching: No unmatched man and woman both prefer each other to their current spouses
Somebody please explain me how we do the optimal matching.
Zulfi.
Attachments
Last edited:
