## Description

1. State whether the following statement is True or False: “It is possible to have an instance of the

Stable Matching problem in which two women have the same best valid partner.” (5pts)

2. In the context of a stable roommate problem involving four students (a, b, c, d), each student

ranks the others in a strict order of preference. A matching involves forming two pairs of

students, and it is considered stable if no two separated students would prefer each other over

their current roommates. The question is whether a stable matching always exists in this scenario.

If it does, provide proof; if not, present an example of roommate preferences where no stable

matching is possible. (10pts)

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

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

5. Determine whether the following statement is true or false. If it is true, give an example. If it is

false, give a short explanation. (10pts)

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.

6. Determine whether the following statement is true or false. If it is true, give a short explanation. If

it is false, give a counterexample. (10pts)

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.

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

8. There are six students, Harry, Ron, Hermione, Ginny, Draco, and Cho. This class requires them to

pair up and work on pair programming. Each has preferences over who they want to be paired

with. The preferences are:

Harry: Cho > Ron > Hermione > Ginny > Draco

Ron: Ginny > Harry > Hermione > Cho > Draco

Hermione: Ron > Harry > Ginny > Cho > Draco

Ginny: Harry > Cho > Hermione > Ron > Draco

Draco : Cho > Ron > Ginny > Hermione > Harry

Cho: Hermione > Harry > Ron > Ginny > Draco

Show that there is no stable matching. That means showing that no matter who you put together,

there will always be two potential partners who are not matched but prefer each other to the

current partner. (10pts)