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.

Algorithm OP:

1. Run the men suggest algorithm, and refuse all proposal 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 associate for w.

           Remark. Gale and Sotomayor (1985b) showed that when each woman declare all the men        inferior to her women optimal partner as undesirable, then the men optimal mechanism will be forced to return the women optimal stable matching.

b.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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