In this exercise, we present a family of algorithms, each of which produces the men's courtship matching, and contains the Gale-Shapley algorithm. Consider the following algorithm for matching men and women. At the start of the algorithm, all the men leave the room, while all the women remain in the room.
In every stage of the algorithm, one of the men who is outside the room enters, and goes directly to the woman whom he most prefers from among the women who have not previously dismissed him. If another man is already standing next to that woman, the woman asks the man whom she prefers from among those two who are now next to her to stay, and dismisses the other one, who then leaves the room.
If, however, a man entering the room goes to a woman who is standing alone, she asks him to stay. The algorithm terminates when every woman has exactly one man standing next to her.
(a) Prove that this algorithm satisfies the three properties of the Gale-Shapley algorithm.
(b) Prove that this algorithm terminates, and that it always yields a stable matching.
(c) Prove that the algorithm always produces the men's courtship matching Om.