Advanced Algorithms End Term: 22 December 2024 (September 2024 term)

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?