Description
-
Solve Kleinberg and Tardos, Chapter 1, Exercise 1. (5pts)
-
Solve Kleinberg and Tardos, Chapter 1, Exercise 2. (5pts)
-
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.
-
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)
-
Solve Kleinberg and Tardos, Chapter 1, Exercise 4. (15pts)
-
Solve Kleinberg and Tardos, Chapter 1, Exercise 8. (10pts)
-
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.
-
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
-
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.
-
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.