Posted by: yuanzhan | September 24, 2010

## Grades of HW1 and some explanations

HW1 has been graded and will be handed out in today’s lecture. The main statistics about the scores (out of a total of 85) are:

• Mean: 47.3085106
• Median: 52.5
• Standard Deviation: 24.295239

2. Also for most of you, points were taken off with an explanation like “you should not use G-S algorithm to prove this” or “G-S can only generate some stable matchings” in HW1. This mistake happened when you try to prove a claim about every stable matching for a stable matching instance. One example in the homeworks is (Q1,b). The claim here is the “special” pair $(m,w)$ belongs to every stable matching $S$ for this instance. Some of you used the G-S algorithm to generate one stable matching for this instance, and according to the algorithm, $(m,w)$ is in this stable matching. The reason why this can’t work is that we need to show $(m,w)$ is in every stable matching of this problem. What you’ve shown is only one stable matching which is found by G-S has one such pair. Therefore it’s not sufficient to prove the claim. I guess there’s a misunderstanding between the relation of Stable Marriage Problem and G-S algorithm. Note that one if a problem and the other is an algorithm to solve it. G-S outputs only one of the possible solutions for the stable marriage instance. So if we want to prove some property of all stable matchings, you cannot assume that G-S algorithm will “solve” it. Furthermore, G-S algorithm can only generate/find one stable matching of the problem, but you can not assume G-S algorithm will find all stable matchings for you. Recall that Atri mentioned in class that the G-S algorithm always outputs the same stable matching no matter how the free woman who proposes in every iteration is chosen. (For a more detailed discussion on this part, please see the textbook.) Thus, a stable matching instance that has more than one stable matching (and we saw an example in class), the G-S algorithm will not be able to output all of the stable matchings.