Hw 1 Grading Explanation. 

2. For this problem, you need to prove the pair (m, w) must be in any stable matching. It is not proper to show that G-S algorithm will give you a stable matching with (m, w). Since stable matchings are not unique, and G-S algorithm will find only one stable mtaching. The proof is not sufficient, the (m, w) pair may not exit in other stable matchings which are not returned by G-S algorithm.

8. Key point: G-S algorithm is not fair for women. For woman w, maybe the man m she prefers most never proposed to her, so she can make m propose to her by cheating.