Question 1

In this world, there are only two kinds of people: people who love Hanumankind, and people who do not love Hanumankind. We are searching for a stable matching for everyone. The situation is as follows: - For some $n \geq 5$, there are $n$ men, $n$ women, and one Hanumankind. We also use $k$ to denote $n - 5$. - Men and women can be matched to each other as usual. - Anyone can be matched with Hanumankind. - Everyone is either Skeptic or a Believer. Skeptics want to be matched with anyone except Hanumankind. Believers really want to be matched with Hanumankind but don't mind being matched with other people. - Men and women still have preference lists, as usual, but if they are a Believer, Hanumankind is always in the first position. If they are Skeptic, Hanumankind is always in the last position. - Hanumankind desires to match with 10 people — to be known as the *Believers Club* — to party forever. As Hanumankind is a kind person and wishes to be inclusive, the goal Believers Club will have exactly 5 men and 5 women. - Hanumankind also has a preference list containing all $2n$ men and women. A stable matching is defined as follows: - Hanumankind has 10 partners, of which 5 are men and 5 are women. - All men and women not matched up with Hanumankind are married to someone of the opposite gender. - No unstable couples exist; i.e., there is no man M and woman W such that M prefers W to his current wife, and W prefers M to her current husband. - No skeptic is matched with Hanumankind, i.e, the Believer's Club only admits Believers. - There is no man who (1) is not matched with Hanumankind; and (2) who is preferred by Hanumankind over one of his current male partners; and (3) who prefers Hanumankind over his matched partner. - There is no woman who (1) is not matched with Hanumankind; and (2) who is preferred by Hanumankind over one of his current female partners; and (3) who prefers Hanumankind over her matched partner. Based on the above data, answer the given subquestions. What is a necessary condition for the existence of a stable matching? A condition is a necessary condition if, when it does not hold, a stable matching cannot exist. Check all that apply. In this world, there are only two kinds of people: people who love Hanumankind, and people who do not love Hanumankind. We are searching for a stable matching for everyone. The situation is as follows: - For some $n \geq 5$, there are $n$ men, $n$ women, and one Hanumankind. We also use $k$ to denote $n - 5$. - Men and women can be matched to each other as usual. - Anyone can be matched with Hanumankind. - Everyone is either Skeptic or a Believer. Skeptics want to be matched with anyone except Hanumankind. Believers really want to be matched with Hanumankind but don't mind being matched with other people. - Men and women still have preference lists, as usual, but if they are a Believer, Hanumankind is always in the first position. If they are Skeptic, Hanumankind is always in the last position. - Hanumankind desires to match with 10 people — to be known as the *Believers Club* — to party forever. As Hanumankind is a kind person and wishes to be inclusive, the goal Believers Club will have exactly 5 men and 5 women. - Hanumankind also has a preference list containing all $2n$ men and women. A stable matching is defined as follows: - Hanumankind has 10 partners, of which 5 are men and 5 are women. - All men and women not matched up with Hanumankind are married to someone of the opposite gender. - No unstable couples exist; i.e., there is no man M and woman W such that M prefers W to his current wife, and W prefers M to her current husband. - No skeptic is matched with Hanumankind, i.e, the Believer's Club only admits Believers. - There is no man who (1) is not matched with Hanumankind; and (2) who is preferred by Hanumankind over one of his current male partners; and (3) who prefers Hanumankind over his matched partner. - There is no woman who (1) is not matched with Hanumankind; and (2) who is preferred by Hanumankind over one of his current female partners; and (3) who prefers Hanumankind over her matched partner. Based on the above data, answer the given subquestions. What is a sufficient condition for the existence of a stable matching? A condition is a sufficient condition if, when it holds, a stable matching is guaranteed to exist. Check all that apply. In this world, there are only two kinds of people: people who love Hanumankind, and people who do not love Hanumankind. We are searching for a stable matching for everyone. The situation is as follows: - For some $n \geq 5$, there are $n$ men, $n$ women, and one Hanumankind. We also use $k$ to denote $n - 5$. - Men and women can be matched to each other as usual. - Anyone can be matched with Hanumankind. - Everyone is either Skeptic or a Believer. Skeptics want to be matched with anyone except Hanumankind. Believers really want to be matched with Hanumankind but don't mind being matched with other people. - Men and women still have preference lists, as usual, but if they are a Believer, Hanumankind is always in the first position. If they are Skeptic, Hanumankind is always in the last position. - Hanumankind desires to match with 10 people — to be known as the *Believers Club* — to party forever. As Hanumankind is a kind person and wishes to be inclusive, the goal Believers Club will have exactly 5 men and 5 women. - Hanumankind also has a preference list containing all $2n$ men and women. A stable matching is defined as follows: - Hanumankind has 10 partners, of which 5 are men and 5 are women. - All men and women not matched up with Hanumankind are married to someone of the opposite gender. - No unstable couples exist; i.e., there is no man M and woman W such that M prefers W to his current wife, and W prefers M to her current husband. - No skeptic is matched with Hanumankind, i.e, the Believer's Club only admits Believers. - There is no man who (1) is not matched with Hanumankind; and (2) who is preferred by Hanumankind over one of his current male partners; and (3) who prefers Hanumankind over his matched partner. - There is no woman who (1) is not matched with Hanumankind; and (2) who is preferred by Hanumankind over one of his current female partners; and (3) who prefers Hanumankind over her matched partner. Based on the above data, answer the given subquestions. Consider the algorithms below: > *Algorithm A.* If there are fewer than 5 male believers or fewer than 5 female believers, stop and conclude that there is no stable matching. Otherwise, take Hanumankind's 5 favorite male Believers and his 5 favorite female Believers, and include them in the Believer's club.\ >\ > Remove Hanumankind and the club from all remaining preference lists, and run the Gale-Shapley algorithm on everyone else ($k$ men and $k$ women).\ >\ > Return this matching. > *Algorithm B.* Take Hanumankind's top 5 male preferences and top 5 female preferences, and include them in the Believer's club. Remove Hanumankind and the club from all remaining preference lists, and run the propose and reject algorithm on everyone else ($k$ men and $k$ women).\ >\ > Return this matching. > *Algorithm C.* In this algorithm, we will try to leverage the original Gale-Shapley algorithm on the entire instance by artificially making 5 male and 5 female “copies” of Hanumankind, and their matched partners will ultimately form the Believer's club. We do this as follows:\ >\ > - Introduce 5 new male and 5 new female entities to the world, say $M_1, \ldots, M_5$ and $W_1, \ldots, W_5$.\ > - Let $W^\star$ be Hanumankind's preference list projected on the $n$ women, followed by $W_1, \ldots, W_5$.\ > - Let $M^\star$ be Hanumankind's preference list projected on the $n$ men, followed by $M_1, \ldots, M_5$.\ > - The preference list of $M_i$ is $W^\star$ for all $1 \leqslant i \leqslant 5$.\ > - The preference list of $W_i$ is $M^\star$ for all $1 \leqslant i \leqslant 5$.\ > - For all the male Skeptics, replace the Hanumankind entry at the bottom of the list with $W_1, \ldots W_5$.\ > - For all the female Skeptics, replace the Hanumankind entry at the bottom of the list with $M_1, \ldots M_5$.\ > - For all the male Believers, replace the Hanumankind entry at the top of the list with $W_1, \ldots W_5$.\ > - For all the female Believers, replace the Hanumankind entry at the top of the list with $M_1, \ldots M_5$.\ >\ > Now run the Gale-Shapley algorithm on this instance with $n + 5$ men and $n + 5$ women.\ >\ > Take everyone matched with $M_1, \ldots, M_5$ and $W_1, \ldots, W_5$ and include them in the Believer's Club, and keep the rest of the matching as-is.\ >\ > Return this matching. Which of the algorithms above is correct?