Answers to Homework # 1

1. In every instance of the stable marriage problem there is a stable matching containing a pair (m, w) such that m is ranked first on the preference list of w and w is ranked first on the preference list of m.

False. Consider the following scenario where there are two men and women each in M and W

with the following preferences:

m prefers w to w'

m' prefers w' to w

w prefers m' to m

w' prefers m to m'

There is no possible pairing in which both partners prefer the other to all other choices.

2. Consider an instance of the stable marriage problem in which there exists a man m and a woman w such that m is ranked first on the preference list of w and w is ranked first on the preference list of m. Then in every stable matching S for this instance, the pair (m,w) belongs to S.

True. Suppose there were a stable matching S containing the pairs (m, w') and (m', w).

Then since m and w both prefer each other to their current partner, an instability occurs

contradicting the assertion that S is stable.

3. # 4. This is an example of a "polygamous" association between hospitals and residents. We modify the Gale-Shapley algorithm as follows:

While some hospital h_i has available positions

h_i offers a position to the next student s_j on its preference list

if s_j is free, he accepts

else (s_j is already committed to hospital h_k)

if s_j prefers hospital h_k to h_i he rejects the offer

else s_j accepts the offer from h_i

the number of available positions at h_k increases by 1

the number of available positions at h_i decreases by 1

This algorithm terminates in O(mn) steps because each hospital offers a

position to a student at most once, and in each iteration some hospital offers a

position to some student.

Suppose there a p_i > 0 positions available at hospital h_i. The algorithm terminates

with all of the positions filled. Any hospital that did not fill all of its positions

must have offered them to every student. But then every student must be

committed to some hospital. But if h_i still has available positions, S p_i > n, where

i is the index over m hospitals and n is the number of students. This contradicts

the assumption that the number of students is greater than the number of available

positions.

The assignment is stable. First kind of instability: There are students s and s', and

hospitals h and h', so that s is assigned to h, and s' is assigned to no hospital, and h

prefers s’ to s. If h prefers s' to s, then it would have offered a position to s' before s.

From that point forward s' would be associated with some hospital, and would not be

free at the end -- a contradiction.

For the second kind of instability there are students s and s', and hospitals h and h'

such that s is assigned to h, s' is assigned to h', and h prefers s' to s, and s' prefers h

to h'. Let (h_i, s_j) be a pair that causes an instability. Then h_i must have offered a

position to s_j; otherwise it has p_i residents all of whom it prefers to s_j. Furthermore

s_j must have rejected h_i in favor of some h_k which he/she preferred; and s_j must therefore

be committed to some h_l possibly different from h_k which he/she also prefers to h_i. Therefore

(h_i, s_j) is not a pair in the final matching.

4. We will say an assignment of ships to stopping ports is acceptable if the resulting truncations

satisfy the conditions of the problem -- specifically each ship must have a distinct stopping port

in any acceptable assignment. Let each ship rank each port according to the order in which

it makes a visit and each port rank each ship in reverse chronological order of their visits.

Now run the Gale - Shapley Algorithm.

We need to show that a stable matching of ships and ports defines an acceptable

assignment of stopping ports.

Proof. If the assignment is not acceptable then it violates the property that each ship has

a distinct stopping port -- that is some ship S_i passes through port P_k after ship S_j has

already stopped there. But then ship S_i prefers port P_k to its own stopping port and

P_k prefers S_i to ship S_j. This contradicts the assumption that we chose a stable

matching between ports and ships.