Homework 1

Due Wednesday, January 28

1. This exercise concerns the stable matching problem between $n$ computer science majors and $n$ engineering majors discussed in class. Determine whether each of the following statements is true or false. Prove your claim.

   (a) If $S$ is a stable matching returned by the Gale–Shapley algorithm, then $S$ contains a pair $(a, b)$ of a computer science major $a$ and an engineering major $b$ such that $a$ and $b$ are the top-ranked choices of each other.

   (b) Consider an instance of the stable matching problem in which there are a computer science major $a$ and an engineering major $b$ such that $a$ and $b$ are the top-ranked choices of each other. Then the Gale–Shapley algorithm returns a stable matching $S$ containing the pair $(a, b)$.

2. An even number of students in a class are to be divided up into pairs of partners. Each student ranks the classmates in the order of one's preference with no ties according their expertises. We wish to determine a stable pairing in which there are no two students who are not partners but prefer each other to their given partners. Solve one of the following:

   (a) Prove that there is always such a stable pairing of students, and give an efficient algorithm to find one.

   (b) Give an instance under which there is no such stable pairing. Prove your claim.

3. Consider a set of $m$ colleges and a set of $n$ applicants. Each college can only accommodate up to its own quota. Each applicant ranks the colleges in the order of one's preference, omitting those colleges to which one did not apply. Each college similarly ranks those who have applied to it in the order of its preference, omitting those it would never accept even if it meant not filling its quota. For simplicity, we assume that there are no ties in these rankings. We wish to determine a stable assignment of applicants to colleges in which (i) each applicant is assigned to at most one college, (ii) each college accommodates as many applicants as possible up to its quota (except for those it never accepts under any circumstance), (iii) and the following never occurs:

   Applicants $\alpha$ and $\beta$ are assigned to colleges $A$ and $B$, respectively, although $\beta$ prefers $A$ to $B$, and $A$ prefers to $\beta$ to $\alpha$.

   Prove that there is always such a stable assignment of applicants to colleges, and give an efficient algorithm to find one.

CPSC 320 home page