1. Solve Kleinberg and Tardos, Chapter 1, Exercise 1. (5pts)
2. Determine whether the following statement is true or false. If it is true, give an example. If it is false, give a short explanation. (5pts)
For some n ≥ 2, there exists a set of preferences for n men and n women such that in the stable matching returned by the G-S algorithm when men are proposing, every woman is matched with their most preferred man, even though that man does not prefer that woman the most.
3. Solve Kleinberg and Tardos, Chapter 1, Exercise 4. (15pts)
*You will see variations of this problem throughout the semester, so spend time on it! :)
4. Solve Kleinberg and Tardos, Chapter 1, Exercise 8. (10pts)
*Hint: This problem requires a thorough step by step understanding of Gale Shapley.
UNGRADED PRACTICE PROBLEMS
1. Determine whether the following statement is true or false. If it is true, give a short explanation. If it is false, give a counterexample. For all n ≥ 2, there exists a set of preferences for n men and n women such that in the stable matching returned by the G-S algorithm when men are proposing, every woman is matched with their least preferred man.
2. Solve Kleinberg and Tardos, Chapter 1, Exercise 2. (5pts)
