How to achieve best matching?

Thread Starter

zulfi100

Joined Jun 7, 2012
632
Hi,

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

}
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



image1.jpg









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




image2.jpg





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:
Top