Inequality
It is clear from the description of the Gale-Shapley algorithm for finding a stable marriage that the algorithm is not symmetrical. Men propose to women, and women reject or accept their suitors. Women never get to propose, and men never get to reject. It would be easy to run the algorithm in the opposite direction, with women proposing and men rejecting. But men and women are treated inherently unequally in an execution of the algorithm. It is not surprising, therefore, to find out that the stable marriage produced by the Gale-Shapley algorithm is favorable to one gender: the gender that is proposing. The algorithm favoring one gender does not mean that every man, if the men are proposing, gets his first choice, nor does it mean that every man is better off than every woman. It means that every man gets the best partner he could possibly have in any stable matching given the preference lists.
Theorem: Let M be Gale-Shapley matching with men as proposers,
and let M' be another stable matching. Let man m be paired with woman w in M,
and let m be paired with w', a different woman, in M'. Then m prefers w to w'.
Proof: Assume towards contradiction that m prefers w' to w.
Then m proposes to w' before he proposes to w in the Gale-Shapley algorithm.
So w' must have rejected m for some man, call him m', during the algorithm.
Assume without loss of generality, that this rejection is the first rejection
of this execution of the algorithm. Then w' is at the top of m'’s list.
So m' prefers w' to any other woman, and w' prefers m' to m. So m cannot be
matched to w' in any stable marriage. So M' is not stable, which is a contradiction.
So the marriage determined by the Gale-Shapley algorithm in which men are proposers
is at least as good as any other stable marriage for every man involved. Executing
the algorithm with men as proposers is therefore known as the man-oriented version
of the algorithm, and it is said to be man-optimal.
Corollary: Let M be a man-oriented Gale-Shapley matching,
and let M' be another stable matching. Let w be paired with m in M and with
m', a different man, in M'. Then w prefers m' to m.
Proof: Assume towards contradiction that w prefers m to m'.
We know that w is the best partner m could get in any stable matching, since
M is man-optimal. So m must prefer w to his partner in M', let’s call
her w', since M' is stable. So w prefers m to m' and m prefers w to w'. So M'
is not stable, and we have reached a contradiction.
The marriage created by the man-oriented version of the Gale-Shapley algorithm
is therefore woman-pessimal. The woman-oriented version of the algorithm creates
a woman-optimal, man-pessimal stable marriage.
Corollary: If the man-oriented and woman-oriented versions
of the Gale-Shapley algorithm produce the same marriage, then M is the only
possible stable marriage.
Proof: Let M be the Gale-Shapley version of the matching,
and let M' be another stable matching. Let man m be paired with woman w in M
and with woman w' in M'. M is man-optimal, so m ranked w at least as high as
he ranked w'. But M is also woman-optimal, and therefore man-pessimal. So m
ranked w' at least as high as he ranked w. So m ranked w and w' equally. Since
a man cannot give two different women the same rank, w and w' are the same person.
This is true for every man-woman pair, so M=M'.
An algorithm exists for finding a more fair stable marriage. The algorithm uses a rotation elimination method similar to the one used in the stable roommates extension of the stable marriage problem. The equal algorithm is slower than the Gale-Shapley algorithm, running in O(n4) time instead of O(n2) time.[GD2]