I'm going over a proof that after the Gale-Shapley algo runs, all men and women are matched.
From these slides
Claim. In Gale-Shapley matching, all men and women get matched. Pf.
[by contradiction]
・Suppose, for sake of contradiction, that Zeus is
not matched upon termination of GS algorithm.
・Then some woman, say
Amy, is not matched upon termination.
・By Observation 2, Amy was never proposed to.
・But, Zeus proposes to everyone, since he ends up
unmatched. ▪
and observation 2 is:
Observation 2. Once a woman is matched, she never becomes unmatched;
she only "trades up."
First of all it should be stated that this doesn't work if there aren't equal number of men and number of women.
I don't get the second point; if a man is unmatched how does it imply a women is not matched (unless we do have the assumption |women|=|men|, which we didn't have).
Also, isn't it sort of missing the last step of saying the last 2 points form a contradiction?
I find these types of proofs hard to follow for algorithms.
Best Answer
Yes, it is a fundamental assumption for the algorithm that there is an equal number of men and women. Otherwise it would be futile to hope for any way of matching everyone, stable or not.