# How to achieve best matching?

#### zulfi100

Joined Jun 7, 2012
656
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

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

• 128.9 KB Views: 1
Last edited: