1. Solve Kleinberg and Tardos, Chapter 1, Exercise 1. (5pts)
2. Solve Kleinberg and Tardos, Chapter 1, Exercise 2. (5pts)
3. 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, every woman is matched with their most preferred man, even though that man does not prefer that woman the most.
4. Four students, a, b, c, and d, are rooming in a dormitory. Each student ranks the others in strict order of preference. A roommate matching is defined as a partition of the students into two groups of two roommates each. A roommate matching is stable if no two students who are not roommates prefer each other over their roommate.
Does a stable roommate matching always exist? If yes, give a proof. Otherwise, give an example of roommate preferences where no stable roommate matching exists. (8pts)
5. Solve Kleinberg and Tardos, Chapter 1, Exercise 4. (15pts)
6. Solve Kleinberg and Tardos, Chapter 1, Exercise 8. (10pts)
7. Determine whether the following statement is true or false. If it is true, give a short explanation. If it is false, give a counterexample. (5pts)
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, every man is matched with their most preferred woman.
8. Consider a stable marriage problem where the set of men is given by M = m1, m2, ..., mN and the set of women is
W = w1, w2, ..., wN . Consider their preference lists to have the following properties:
∀wi ∈ W : wi prefers mi over mj ∀j > i
∀mi ∈ M : mi prefers wi over wj ∀j > i
Prove that a unique stable matching exists for this problem. Note: the ∀ symbol means “for all”. (12pts)
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, every woman is matched with their least preferred man.
2. Consider the G-S algorithm for n men and n women. What is the maximum number of times a man may be rejected as a function of n? Give an example where this happens.
