CSCI 570  Homework 1

CSCI 570 
Homework 1
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 when men are proposing, every woman is matched with their most preferred man, even though that man
does not prefer that woman the most.
4. A stable roommate problem with 4 students a, b, c, d is defined as follows. Each student ranks the other three in strict
order of preference. A matching is defined as the partition of the students into two groups of two roommates. A matching
is stable if no two separated students prefer each other to their current roommate.
Does a stable matching always exist? If yes, give a proof. Otherwise, give an example of roommate preferences where no
stable 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.
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 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 when men are proposing, every woman is matched with their least preferred man.
2. Consider the Gale-Shapley algorithm operating on n men and n women, with women proposing.
a) What is the maximum number of times a woman may be rejected, with respect to the problem size n? Give an example
where this can happen.
b) Consider the following modification to the G-S algorithm: at each iteration, we always pick the free woman with the
highest average preference among men, i.e. the most “popular” remaining woman (when taking an average across all men’s
preference lists). Prove or disprove: this will help reduce the number of rejections for some women.