CSCI 570 Homework 1 Solution

1. Solve Kleinberg and Tardos, Chapter 1, Exercise 1. (5pts)

1. Solve Kleinberg and Tardos, Chapter 1, Exercise 2. (5pts)

1. 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.

1. 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)

1. Solve Kleinberg and Tardos, Chapter 1, Exercise 4. (15pts)

1. Solve Kleinberg and Tardos, Chapter 1, Exercise 8. (10pts)

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 man is matched with their most preferred woman.

1. Consider a stable marriage problem where the set of men is given by M = m₁, m₂, ..., m_N and the set of women is W = w₁, w₂, ..., w_N . Consider their preference lists to have the following properties:

∀w_i ∈ W : w_i prefers m_i over m_j ∀j > i

∀m_i ∈ M : m_i prefers w_i over w_j ∀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.

1. Consider the Gale-Shapley algorithm operating on n men and n women, with women proposing.

1. 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.

1. 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.