Let A be a matching (not necessarily stable), and let MA,Om be the set of men who prefer the women to whom they are matched under A to the women to whom they are matched under the men's courtship matching Om.
(a) Prove that if A is a stable matching then MA,Om = ∅. In this exercise we prove that if MA,Om ≠ ∅, then there exists a pair (m, w) who object to the matching A, and m ≠ MA,Om . Denote by W1 the set of the women who are matched to men in MA,Om under the matching A, and by W2 the set of the women matched to men in MA,Om under Om.
(b) Prove that if W1 ≠ W2, then W1 \ W2 ≠ ∅.
(c) Prove that if W1 ≠ W2, every woman w ∈ W1 \ W2 objects to A along with the man to whom she is matched under Om.
(d) From here to the end of the exercise, assume that W1 = W2. Prove that every woman in W1 dismisses at least one man under the men's courtship algorithm (her match under the matching A).
(e) Consider the woman w∗ ∈ W1 who was the last woman approached by a man m∗ from the set MA,Om under the men's courtship algorithm. Prove that when w∗ receives an offer from m∗, there was another man at her doorstep, call him m" , whom she dismissed in favor of m∗.
(f) Use the fact that w∗ is the last woman to get an offer from a man in MA,Om to show that m" is not in MA,Om.
(g) Prove that the pair (m" , w∗) object to the matching A.