You applied for a TAship in the summers and the RO office in all their algorithmic...

 

Transcribed Image Text:

You applied for a TAship in the summers and the RO office in all their algorithmic brilliance used the Gale Shapely algorithm to assign you your preferred course and you are now happily TAing Pakistan studies and have no real workload (this was actually the case for one of your TAS). But one fine day your instructor comes and tells you that you need to assign students partners for their upcom- ing pair presentation. Your class has exactly n male and n female students, and each pair needs to have one male and one female student. Normally you would have assigned random partners but today you feel a bit nice, and allow the students to send in their preference lists (of the opposite gender) so that you can form stable pairs using the stable matching algorithm you've studied in class. However, you're unable to choose a proposing party for the algorithm (will it be the group of males or the group of females that sends the proposals?). To keep things fair, you decide to start from a random perfect matching, and then check for instabilities randomly. If an instability is found, i.e., m-w and m'-w' are matched but m prefers w' to w and w' prefers m to m', then you break the current pairs and match them as follows: m-w' and m'-w. You continue to do this until no instabilities are left. Will this strategy always help you form a stable matching for the upcoming presentations? If yes, then provide a detailed proof that shows this strategy will always terminate and allow you to find a stable matching. If not, then provide a preference list (n = 3) and an initial perfect matching such that this strategy does not terminate with a stable matching. Particularly, dry run the algorithm using this preference list, such that you show a cycle in the matching state. You applied for a TAship in the summers and the RO office in all their algorithmic brilliance used the Gale Shapely algorithm to assign you your preferred course and you are now happily TAing Pakistan studies and have no real workload (this was actually the case for one of your TAS). But one fine day your instructor comes and tells you that you need to assign students partners for their upcom- ing pair presentation. Your class has exactly n male and n female students, and each pair needs to have one male and one female student. Normally you would have assigned random partners but today you feel a bit nice, and allow the students to send in their preference lists (of the opposite gender) so that you can form stable pairs using the stable matching algorithm you've studied in class. However, you're unable to choose a proposing party for the algorithm (will it be the group of males or the group of females that sends the proposals?). To keep things fair, you decide to start from a random perfect matching, and then check for instabilities randomly. If an instability is found, i.e., m-w and m'-w' are matched but m prefers w' to w and w' prefers m to m', then you break the current pairs and match them as follows: m-w' and m'-w. You continue to do this until no instabilities are left. Will this strategy always help you form a stable matching for the upcoming presentations? If yes, then provide a detailed proof that shows this strategy will always terminate and allow you to find a stable matching. If not, then provide a preference list (n = 3) and an initial perfect matching such that this strategy does not terminate with a stable matching. Particularly, dry run the algorithm using this preference list, such that you show a cycle in the matching state.