Problem 2. Say that we have three women, A, B, and C, and three are being matche

Question

Problem 2. Say that we have three women, A, B, and C, and three are being matched in heterosexual pairs. Each woman h, W, X, and yh erences over are as follows. man has preferences over the three women. Their prefeer the three men. W XY A B C (Best) X W x (Best) A BI B A A (Worst) W x Y (Worst) CC [ For example, woman A likes man X best, Y second-best, and W least. Note that man Y's preferences are not completely specified: there are "blanks" in his preferences. There are two possibilities for man Y's preferences: it is possible that man Y likes B best, A second-best, and C worst, and it is possible that man Y likes C best, A second-best, and B worst a. Is it possible to fill in the blanks in man Y's preferences so that more than one stable matching exists? If so, fill in the blanks which make it so that more than one stable matching exists, and show what the stable matchings are. If not, explain why not. (3 points)

Explanation / Answer

We have a group of 3 men and 3 women who want to be paired of. We know that:
(1) Everyone has a complete preference list of partners (with no ties).
(2) Everyone is heterosexual and being in a relationship is preferred to being single.

A stable matching is an assignment of n men to n matching so that no two people prefer each other to their respective partners.

In the above setting if we just pair of men and women arbitrarily, there can always be two couples (m, w) and (m', w') such that m rates w' higher than w in his preference list and w' rates m higher than m'
in her list. Obviously such a situation is not stable as nothing stops m and w' from breaking off from their respective partners and getting paired themselves. Now if m and w' pair up, this leaves m' and w free. Due to assumption (2) it is natural for them to pair up but this may lead to new clashes in the preference lists.

Now in above question it is given that a group of n men and n women satisfying the above two assumptions, can one always find a stable matching?

The answer is yes. Consider the following algorithm due to Gale and Shapley (see [1]).
Each man proposes, in order, to the women on his list, pausing when a woman agrees to consider his proposal, but continuing if a proposal is either immediately or subsequently rejected. When a woman receives a proposal, she rejects it if she already holds a better proposal, but otherwise agrees to hold it for consideration, simultaneously rejecting any poorer proposal that she may currently hold. (Here the better
proposal is the one according to her preference list.) The algorithm stops when every woman holds a proposal.

To illustrate the workings of the above algorithm let us consider the following example. Let n = 4 and {A, B, C, D}, {W, X, Y, Z} be the set of males and females respectively. Let the following be the preference
lists:
A (X, W, Y, Z), B (W, Y, X, Z), C (X, W, Z, Y ), D (Z, Y, X, W)
W (A, C, B, D), X (B, D, A, C), Y (C, A, B, D), Z (C, A, D, B).
It is easy to check that the final matching is going to be
(A, X),(B, Y ),(C, W),(D, Z).
Observe that:
1) A woman w remains engaged from the point at which she receives her first proposal and the sequence of partners to which she is engaged gets better and better (in terms of her preference list).
2) The sequence of women to whom a man m proposes gets worse and worse (in terms of his preference list).
It is clear from the above observations that the G-S algorithm terminates.

Consider an execution of the G-S algorithm that returns a set of pairs S. The set S is a stable matching.
Proof. It is easy to see that the set S is a perfect matching. Let if possible it is not stable. Then there exists two pairs (m, w) and (m', w') such that m prefers w' to w and w' prefers m to m'. This means m
must have proposed w' and got rejected in favor of some man m''. Now since w' is with m', this means either m' = m'' or m' is higher than m'' in w'’s preference list. Since w' prefers m to m' this leads to a
contradiction.
Call a woman w a valid partner of a man m (and vice versa) if there exists a stable matching that contains the pair (m, w). We will say that w is the best valid partner of m if w is a valid partner of m, and no woman whom m prefers more than w is a valid partner of his. We will denote best valid partner of m by best(m). Let S be the matching {(m, best(m))}. The next proposition offers a nice description of the stable matching obtained by the G-S algorithm.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.