Suppose n men and n women survived after a spaceship crush on a planet orbiting Alpha Centauri. They happen all to be heterosexuals and all single (or their partners died in the crush). Each man then ranks women in order of preference and each woman ranks all men in order of preference. We could formalize this as follows. Denote the set of men by M and the set of women by W. Each man [tex]m\in M[/tex] picks a bijection [tex]b_m\colon W\to \{1,\dots,n\}[/tex] and each woman [tex]w\in W[/tex] picks a bijection [tex]b_w\colon M\to \{1,\dots,n\}.[/tex] The bigger number is assigned by [tex]b_m[/tex] to [tex]w[/tex] the higher [tex]m[/tex] ranks [tex]w[/tex] and vice versa.
Good News: It is possible for all of them to get married such that if [tex]m\in M[/tex] and [tex]w\in W[/tex] are not married to each other then either m prefers his wife to w or w prefers her husband to m.
This is called the Stable Marriage Theorem and was proved by D. Gale and L. S. Shapley in their 1962 published article
College Admissions and the Stability of Marriage
in The American Mathematical Monthly, Vol. 69, No. 1 (Jan., 1962), pp. 9-15.
Of course marriage is not the only application of this theorem and the initial interest of authors was the question of how to pair applicants with colleges taking into account that each applicant has a preference list of the colleges and each college has a preference list of the applicants. Also it appears that the algorithm given by Gale and Shapley has been widely applied to the assignment of graduating medical students to their first hospital appointments.
Happy Valentines Day!
The proof is surprisingly straightforward and it actually suggests that in natural circumstances the pairing should really fall quite close to a stable pairing.
Proof of Good News: We shall go in rounds. On the first round each man makes a proposal to his favourite woman. After this is done each woman chooses her favorite among those who proposed to her and replies Maybe to him and No to others. Consider a man and a woman engaged if a the woman replied Maybe to the man. On the second round these men who are not engaged, i.e. got a negative answer on the first round, make proposals to their second-to-favourites. After that each woman chooses the best out of the group consisting of new proposers together with the boy she is engaged to, if any. Note that it means that an engaged man can become single again. They proceed in the same manner. At each stage each single man makes a proposal to the best girl to whom he hasn’t proposed yet. Eventually every girl has received at least one proposal, because each man proposes at most once to each woman. At this point everyone are engaged and get married with the respective partners.
We claim that the stability requirement is met. Suppose Eloise and Abelard are not married to each other but Abelard prefers Eloise to his own wife. Let us show that then Eloise does not prefer Abelard to her own husband. Since Abelard prefers Eloise to his wife, he must have proposed to Eloise before proposing to his wife. The fact that Abelard after all proposed to his wife, means that Eloise rejected Abelard at some point which implies that she accepted someone she prefers to Abelard. [tex]\square[/tex]
This theorem is closely related to the Hall’s theorem.
