Stable Marriage Algorithm Proof

Question

I am unable to prove a lemma which is required in the proof of correctness of Gayle Shapley Algorithm for Stable marriage problem.

Lemma During the algorithm, each Boy A is rejected only by girls that are infeasible for A.

The proof in the book goes by induction.

We prove the lemma by induction. Consider an arbitrary round of the Boston Pool algorithm, in which doctor α rejects one hospital A for another hospital B. The rejection implies that α prefers B to A. Every doctor that appears higher than α in B’s preference list has already rejected B and therefore, by the inductive hypothesis, is infeasible for B. Now consider an arbitrary matching that assigns α to A. We already established that α prefers B to A. If B prefers α to its partner, the matching is unstable. On the other hand, if B prefers its partner to α, then (by our earlier argument) its partner is infeasible, and again the matching is unstable. We conclude that there is no stable matching that assigns α to A.

Here Hospitals correspond to boys (they propose in decreasing order of priority) and doctors to girls.

Can some one explain the lemma and the proof.

Answer 1

Say you (B) and your best pal (A) propose to the same girl (alpha). She prefers you to him. If you propose to her, that means there's no better girl for you than alpha (if there had been a better one, you would've gone to her instead). The girls of your dreams better than alpha will already have said no to you, so they're unavailable.

Now. Say God puts alpha with your best pal rather than you. If you prefer alpha to your current girl, the relationship is unstable, 'cause you want a better girl and you'll go to her (alpha), as she hasn't refused you yet. If on the other hand you prefer someone else to alpha, then you're stuck, because in the first paragraph we said there's no better one. That means that if alpha says no to your best pal, then she's no good for him.

Answer 2

I believe the confusion is in the lack of a definition of what infeasible means. The marriage algorithm makes these assumptions:

• A Boy is willing to be married to any Girl (but proposes to them in his order of preference).
• A free Girl will accept any proposal, but will dump her current fiancè if a Boy she prefers more proposes to her.

A marriage between Boy α and Girl β is infeasible if either:

1. There is a different Boy α′ that β prefers over α and α′ also prefers β over his current fiancè.
2. There is a different Girl β′ that α prefers over β and β′ also prefers α over her current fiancè.

The lemma illustrates that this can't happen.

• For case 1, if α′ exists, he would have proposed to her earlier and since she is engaged to someone else, she must have rejected him. So either β really likes her current partner more (rejected α′), or α′ likes his partner more (didn't get around to proposing to β).
• For case 2, if β′ exists, he would have proposed to her earlier and since he is engaged to someone else, she must have either dumped him or rejected him. Either means β′ is currently with someone she prefers more than α.

Applying the above logic on the inductive step leads to the conclusion that α and β are with their destined partners.