Distributed Memory Problem

STABLE MARRIAGE

You have n men and n women.  You want to pair them off so that all marriages are stable.

This means:

If I am married to someone, and there's someone else I like better.  I would totally be willing to dump my spouse for that better person.  However, that person is already married to someone they like better than me.  I'm willing to trade up but that other person would be trading down to me.

And everyone is like this.  Everyone is matched to someone so that cheating is impossible.  If any person likes someone else more than they like their spouse, that other person likes their spouse more than they like the first person.  Cheating doesn't happen, because no one you want to cheat with wants to cheat with you.

Surprisingly, assuming an equal amount of men and women, itS is ALWAYS possible to find a stable marriage.  Everyone ranks the other sex from most desirable to least desirable; there are no ties and no omissions.  If you have n men and n women, everyone makes a list of n members of the sex ranked by desirability.

So, here's how this works.

Every man proposes to the first woman on his list.  It is not a race.

If that woman has no proposal yet.  She responds with "TENTATIVE YES".

If that woman has a proposal, and the one to whom she is betrothed is higher on her list than the new proposal, she tells her suitor "NO".

If that woman has a proposal, and the new proposal is from someone higher on her desirability list than her current betrothed, she tells her current beau "NO" and tells the new guy "TENTATIVE YES".

When all pairs are connected by a "TENTATIVE YES"--and this is guaranteed to happen eventually, then the "TENTATIVE YES"es all become "YES".  And everyone is now in a stable marriage.

For example,

A: (D,E,F)                 D: (A,B,C)
B: (E,F,D)                 E: (B,C,A)
C: (F,D,E)                 F: (B,C,A)

A proposes to D:  tentative yes
B proposes to E:  tentative yes
C proposes to F:  tentative yes

We're done.  A<->D  B<->E    C<->F

If all the men have different first choices, it always works out that way.  Whether the women have the same or different first choices is irrelevant.

A,B,C all got their first choices.  D and E did as well.  But F did not.  F would rather be with B.  But B prefers his own wife E to F so B won't cheat.

A:  (D,E,F)           D:  (A,B,C)
B:  (D,E,F)           E:  (A,B,C)
C:  (D,E,F)           F:  (A,B,C)

A proposes to D.  Tentative yes.
B proposes to D.  No.
B proposes to E.  Tentative yes.
C proposes to D.  No.
C proposes to E.  No.
C proposes to F.  Tentative yes.

Everyone has a tentative yes.  So  A<->D  B<->E   C <->F   .  A and D are pretty happy with the arrangement but nobody else is.  C might want to cheat with D or E, but D or E would never risk their marriage to cheat with C.


It so happens that there may be more than one solution to the stable marriage problem.  There may be more than one way to connect everybody so that nobody cheats.

This algorithm does not guarantee men their first-choice pick or even guarantee one that is semi-decent.  However, it does guarantee that all men will get the best pick they can get.  In other words, this algorithm will find a matching in which every man has at least as desirable a partner as he would get in ANY stable marriage.

Women do not have this guarantee and it's very possible that any woman might do better for herself in a different stable matching.

This works very well for in a Distributed Computing model.

Every "male" processor sends a proposal (simultaneously) to a "female" processor.

When a woman receives a proposal when she already has one on the table, she sends a "No" back to the lesser man.  (You don't actually need to have the processors send back a "tentative yes".

When a man receives a "no" he sends a proposal to the next woman on his list.

When a woman receive her first proposal she sends an "I'm getting hitched" to the "master" process.  When the "master" receives an "I'm getting hitched" from all the women, that's it, the marriage is stable.  And so the "master" sends a message to all the processes that the proposal period is done.  Everybody  sends their spouse to the master (or perhaps only the men or only the women do).  The Master prints out the stable marriages.

If you have n men and n women, you need 2n+1 processes.  One for each man, one for each woman, one for the matchmaker.