Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is an example in a discrete structures book on stable marriages. Though i don't understand its solution. Any help will be appreciated

Run the girl-proposal algorithm to find a set of stable marriages for the following lists of preferences.

Boy 1: G1 > G2 > G3 > G4

Boy 2: G4 > G3 > G1 > G2

Boy 3: G1 > G2 > G4 > G3

Boy 4: G1 > G3 > G2 > G4

Girl 1: B1 > B3 > B2 > B4

Girl 2: B4 > B1 > B2 > B3

Girl 3: B3 > B1 > B4 > B2

Girl 4: B2 > B1 > B4 > B3

share|improve this question
2  
What do you know of the girl-proposal algorithm? What have you been able to do so far? –  Calvin Lin Jan 20 '13 at 19:42

1 Answer 1

up vote 4 down vote accepted

I found this algorithm here:

In round one, each boy goes to his first-choice girl and says, “Will you marry me?” Each girl, after considering the boys proposing to her (if any), answers “maybe” (gets engaged) to the one who’s highest on her preference list and “no” to the rest.

In successive rounds, each boy rejected in the previous round goes to his next-choice girl and proposes to her. Each girl, once again, looks at everyone proposing to her (including her engagement from the previous round) and says “maybe” to her most preferred boy and “no” to the rest.

Finally, when every boy is engaged to some girl, the algorithm terminates and the girls turn to their partners and say “yes.”

Now, this is the "boy-proposal algorithm," not the "girl-proposal algorithm," but let's run through it to see how it goes: you should be able to then work out the details for the "girl-proposal algorithm".

First round, boys 1, 3, and 4 propose to g1, b2 proposes to g4. g1 says "maybe" to b1 and "no" to the others; g4 says "maybe" to b2.

Second round: b3 and b4 having been rejected by g1, b3 proposes to g2, and b4 proposes to g3. g2 and g3 have no better offers, so they both say "maybe".

No boy was rejected in round 2, so every girl now says "yes" to the boy to whom she (most recently) said "maybe". We wind up with b1g1, b2g4, b3g2, and b4g3, and we all live happily ever after.

share|improve this answer
    
If only it were so easy in real life... –  Christopher A. Wong Jan 24 '13 at 23:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.