1
1.
CSCI 270 – Spring 2020 – HW 1 Due Jan 23rd
Graded Problems
State True/False: An instance of the stable marriage problem has a unique stable matching if and only if the version of the Gale-Shapely algorithm where the male proposes and the version where the female proposes both yield the exact same matching.
True.
Claim: “If there is a unique stable matching then the version of the Gale- Shapely algorithm where the male proposes and the version where the fe- male proposes both yield the exact same matching.”
The proof of the above claim is clear by virtue of the correctness of Gale- Shapely algorithm. That is, the version of the Gale-Shapely algorithm where the male proposes and the version where the female proposes are both correct and hence will both yield a stable matching. However since there is a unique stable matching, both versions of the algorithms should yield the same matching.
Converse of Claim: “If the version of the Gale-Shapely algorithm where the male proposes and the version where the female proposes both yield the exact same matching then there is a unique stable matching.”
The proof of the converse is perhaps more interesting. For the definition of best valid partner, worst valid partner etc., see page 10-11 in the textbook.
Let S denote the stable matching obtained from the version where men propose and let S0 be the stable matching obtained from the version where women propose.
From (page 11, statement 1.8 in the text), in S, every woman is paired with her worst valid partner. Applying (page 10, statement 1.7) by symmetry to the version of Gale-Shapely where women propose, it follows that in S0, every woman is paired with her best valid partner. Since S and S0 are the same matching, it follows that for every woman, the best valid partner and the worst valid partner are the same. This implies that every woman has a unique valid partner which implies that there is a unique stable matching.
1
2. 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 match- ing is defined as the separation of the students into two disjoint pairs. A matching is stable if no two separated students prefer each other to their current roommates. Does a stable matching always exist? If yes, give a proof. Otherwise give an example roommate preference where no stable matching exists.
A stable matching need not exist. Consider the following list of prefer- ences. Let a, b, c all have d last on their list. Say a prefers b over c, b prefers c over a, and c prefers a over b. In every matching, one of a, b, c should be paired with d and the other two with each other. Now, d’s roommate and the one for whom d’s roommate is the first choice prefer to be with each other. Thus every matching is unstable no stable matching exists in this case.
3. Solve Kleinberg and Tardos, Chapter 1, Exercise 4.
We will use a variation of Gale and Shapley (GS) algorithm, then show that the solution returned by this algorithm is a stable matching.
In the following algorithm (see next page), we use hospitals in the place of men; and students in the place of women, with respect to the earlier version of the GS algorithm given in Chapter 1.
while there exists a hospital h that has available positions do
Offer position to the next highest ranked student s in the preference list of h
if s has not already matched to another hospital h′ then
accept the offer of h else
Let s be matched with h′. if s prefers h′ to h then
then s does not accept the offer of h else
s accepts the offer from h end if
end if end while
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.
The algorithm terminates by producing a matching M for any given pref- erence list. Suppose there are p > 0 positions available at hospital h. 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 still
2
has available positions, p > n, where 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. Suppose, towards a contradiction, that the M produced by our adapted GS algorithm contains one or more instabilities. If the instability was of the first type (a preferred student was not admit- ted), then h must have considered s before s′, which is a contradiction because h prefers s′ to s. The instability was not of the first type. If the instability was of the second type (there is a mutually beneficial swap between hospitals and students), then h must not have admitted s when it considered it before s, which implies that s′ prefers h′ to h, a contradic- tion. The instability was not of the second type. If the contradiction was of neither type it must not have existed, thus the matching was stable. Thus at least one stable matching always exists (and it is produced by the adapted GS algorithm).
4. N men and N women were participating in a stable matching process in a small town named Walnut Grove. A stable matching was found after the matching process finished and everyone got engaged. However, a man named Almazo Wilder, who is engaged with a woman named Nelly Oleson, suddenly changes his mind by preferring another woman named Laura Ingles, who was originally ranked right below Nelly in his preference list, therefore Laura and Nelly swapped their positions in Almanzos preference list. Your job now is to find a new matching for all of these people and to take into account the new preference of Almanzo, but you don’t want to run the whole process from the beginning again, and want to take advantage of the results you currently have from the previous matching. Describe your algorithm for this problem.
Assume that no woman gets offended if she got refused and then gets proposed by the same person again.
First, Almanzo leaves Nelly and proposes to Laura:
• If Laura rejects Almanzo and decides to stay with her current fiance (her current fiance is ranked higher than Almanzo in her preference list), then Almanzo just goes back and proposes to Nelly again and gets engaged with her. Algorithm stops. This is where you take advantage of the previous matching.
• Else, Laura accepts Almanzo proposal, she will get engaged with him and leave her current fiance (say Adam). And here comes the main part of the matching puzzle.
(a) Note that Adam may or may not simply propose to Nelly and be engaged with her. The reason is Nelly may be far below Laura in his preference list and there are more women (worse than Laura and better than Nelly), to whom he prefers to propose first. Furthermore, the fact that Nelly becomes single can create
3
2
1. 2.
3.
4.
more instabilities for those men, who once proposed to Nelly and were rejected by her because she preferred Almanzo. Thus, Nelly is ranked higher than the current fiances of those once unlucky men and they are ready to propose to Nelly again for a second chance.
(b) Thus, one way is to put Adam and all those rejected-by-Nelly men in the pool of single men, and put Nelly and the fiancees of the rejected-by-Nelly men in the pool of free women. Similar to Nellys case, moving any woman from the engaged state to the single state may create more instabilities; thus one needs execute step (b) recursively to build the pools of free men and women. In the worst case, all men and all women will end up in the single pools; in the best case (when Laura accepted Almanzo’s proposal), only Adam and Nelly are in the 2 single pools, one for men and another for women.
(c) Execute G-S algorithm until there is no free man. For each man, if there is a woman who once rejected him and is now free, he will try to propose to her again. Otherwise, he will propose to those women that he has never proposed to, moving top down in his preference list. In the latter case, more men (subsequently more women) may go to the single pools.
Note: The above solution is described in details in order to clarify the problem. For this problem, students can simply write pseudo code without having to discuss the details of each case as above.
Practice Problems
Reading Assignment: Kleinberg and Tardos, Chapter 1. Solve Kleinberg and Tardos, Chapter 1, Exercise 1.
False. Suppose we have two men m,m0 and two women w,w0. Let m rank w first; w rank m0 first; m0 rank w0 first; and w0 rank m first. We see that such a pair as described by the claim does not exist.
Solve Kleinberg and Tardos, Chapter 1, Exercise 2.
True. Suppose S is a stable matching that contains the pairs (m,w0) and (m0,w), for some m0 ̸= m,w0 ̸= w. Clearly, the pairing (m,w) is preferred by both m and w over their current pairings, contradicting the stability of S.
Solve Kleinberg and Tardos, Chapter 1, Exercise 3.
We will give an example (with n = 2) of a set of TV shows/associated ratings for which no stable pair of schedules exists. Let a1, a2 be set the shows of A and let b1; b2 be the set of shows of B. Let the ratings of a1;
4
a2; b1; b2 be 1, 3, 2 and 4 respectively. In every schedule that A and B can choose, either a1 shares a slot with b1 or a1 shares a slot with b2. If a1 shares a slot with b1, then A has an incentive to make a1 share a slot with b2 thereby increasing its number of winning slots from 0 to 1. If a1 shares a slot with b2, then B has an incentive to make b2 share a slot with a2 thereby increasing its number of winning slots from 1 to 2. Thus every schedule that A and B can choose is unstable.
5