Question: Suppose we have three men m1, m2, and m3 and three women w1, w2, and w3. Furthermore, suppose that the preference rankings of the men for the three women, from highest to lowest, are m1:w3,w1,w2; m2:w1,w2,w3; m3: w2, w3, w1; and the preference rankings of the women for the three men, from highest to lowest, are w1: m1, m0, m3; w2: m2, m1, m3; w3: m3, m2, m1. For each of the six possible matchings of men and women to form three couples, determine whether this matching is stable.
The deferred acceptance algorithm, also known as the GaleShapley algorithm, can be used to construct a stable matching of men and women. In this algorithm, members of one gender are the suitors and members of the other gender the suitees. The algorithm uses a sequence of rounds; in each round every suitor whose proposal was rejected in the previous round proposes to his or her highest ranking suitee who has not already rejected a proposal from this suitor. A suitee rejects all proposals except that from the suitor that this suitee ranks highest among all the suitors who have proposed to this suitee in this round or previous rounds. The proposal of this highest ranking suitor remains pending and is rejected in a later round if a more appealing suitor proposes in that round. The series of rounds ends when every suitor has exactly one pending proposal. All pending proposals are then accepted.