Consider the Gale-Shapley algorithm with equal number of men and women where men

Question

Consider the Gale-Shapley algorithm with equal number of men and women where men propose to women. We say that a man can manipulate the outcome by switching the ranking of some women in his preference list and end up with a partner that he prefers more than his partner under his true preference list.

a) Given a fixed preference list for all women and all other men, can a man improve his partner by changing his preference list and get matched up with a partner that he prefers to the one under his true preference list? For example, a man may change the ranking of two women w and w' , run the Gale-Shapley algorithm, and end up with a partner w'' that he prefers more to his initial partner?

b.) Focusing on women, is there a switch that would improve the partner of woman who switched her preferences, given a fixed preference list for all men and all other women?

For each parts of this question, you should either show an example of such manipulation or provide a proof of showing that manipulation is impossible.

Explanation / Answer

a. We first describe Algorithm OP—an algorithm to compute the women-optimal partner for w using the men-propose algorithm. (Recall that we do this under the assumption that woman w is allowed to remain single.)

Algorithm OP

1. Run the men-propose algorithm, and reject all proposals made to w. At the end, w and a man, say m, will remain single.

2. Among all the men who proposed to w in Step 1, let the best man (according to w) be m .

Theorem 1. m is the women-optimal partner for w.

Remark. Gale and Sotomayor (1985b) showed that when each woman declares all the men inferior to her women-optimal partner as unacceptable, then the men-optimal mechanism will be forced to return the women-optimal stable matching. This is because the only stable matching solution for the modified preference lists is the women-optimal solution (with respect to the original preference lists). To prove our result, however, we have to show that when a woman unilaterally declares all the men as unacceptable, this is enough to induce her optimal partner to propose to her in the course of executing the men-propose algorithm. Furthermore, we need to show that no higherranked man on her list will propose to her even after she rejects the proposal from her optimal partner

b. Let w denote the womenoptimal partner for w. We modify w’s preference list by inserting the option to remain single in the list, immediately after w. (We declare all men that are inferior to w as unacceptable to w.) Consequently, in the men-propose algorithm, all proposals inferior to w will be rejected. Nevertheless, since there is a stable matching (with respect to the original preferences) with w matched to w, our modification does not destroy this solution, i.e., this solution remains stable with respect to the modified list. It is also well known that in any stable matching instance, the set of people who are single is the same for all stable matchings (cf. Roth and Sotomayor 1990, p. 42). Thus, w must be matched in all stable matchings with respect to the modified preference list. The menoptimal matching for this modified preference list must match w to w, since w is now the worst partner for w with respect to the modified list. In particular, w must have proposed to w during the execution of the men-propose algorithm. Note that until w proposes to w, the men-propose algorithm for the modified list runs exactly in the same manner as in Step 1 of OP. The difference is that Step 1 of OP will reject the proposal from w, while the men-propose algorithm for the modified list will accept the proposal from w, as w prefers w to being single. Hence, clearly w is among those who proposed to w in Step 1 of OP, and so m w w. Suppose m >w w. Consider

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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