|
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 |
|||||
|
|
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. |
|||
|
|
