Chapter 3.1, Problem 64E

1. Suppose we have three men $m_1$, $m_2$, and $m_3$and three women $w_1$, $w_2$, and $w_3$. Furthermore, suppose that the preference rankings of the men for the three women, from highest to lowest, are $m_1:w_3$, $w_1$, $w_2$; $m_2:w_1$, $w_2$, $w_3$; $m_3:w_2$, $w_3$, $w_1$; and the preference rankings of the women for the three men, from highest to lowest, are $w_1:m_1$, $m_2$, $m_3$; $w_2:m_2$, $m_1$, $m_3$; $w_3:m_3$, $m_2$, $m_1$. For each of the six possible matchings of men and women to form three couples, determine whether this matching is stable.

Thedeferred acceptance algorithm, also known as theGale-Shapley algorithm, can be used to construct a stable matching of men and women. In this algorithm, members of one gender are thesuitorsand members of the other gender thesuitees. 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.