Problem Set Sample Solution
CS 252: Algorithms, Winter 2016
Thanks to DLN for the problem and solution (so you know its well written!)
Problem:
The phone rings. Al Gore is organizing a followup summit on climate change in Copenhagen, and he needs
your help. Each of m 1 countries has sent n delegates to the summit, and there are n UN facilitators
there as well. (So there are mn total people.) The summit began with a cocktail partyAl mentioned something about the dark, ironic poetry of the melting ice in the drinkscomplete with a band, headlined by Al
himself. (The Al Gore Rhythms, apparently.) The plan is that after the cocktail party, the delegates are
going to be split into n groups for team-building exercisestheres nothing like trust falls to get you started
thinking about carbon offsetswhere each group contains exactly one person from each of the m delegations
(the facilitators and the m 1 countries). But, of course, saving the world is never that simple. Each
person p has submitted a preference list p to Al, giving his/her rankings of each of the other mn 1 people at the summit, and Al wants your help in assembling a set of groups that are stable in the following sense:
Consider two people x and y from the same country, say assigned to groups G and G0 , respectively.
The people x and y form an instability if they both strictly prefer every delegate in the other group to the
corresponding delegate in their own group. That is, x and y form an instability if, for every delegation D,
x prefers Ds representative in G0 to Ds representative in G and y prefers Ds representative in G to Ds
representative in G0 .
(Observe that this definition precludes an instability formed by two facilitators.)
Prove that there exists a stable set of groups for any preference lists p by giving an (efficient) algorithm to
find one. As always, prove your algorithm correct and analyze its running time. (Hint: to get started, think
about the m = 2 case, where there are two delegations (one country plus the UN). Now can you find a way
to include a second country? Notice that this definition of stability is quite different from that in a stable
marriagehere an instability is formed by two people of the same type (from the same country), whereas
in the stable-matching setting an instability is formed by two people of different types (a man and a woman).)
Solution:
Let the countries be C1 , ..., Cm1 , and let the facilitators be C0 . The key idea is that we will create m 1
perfect matchings (between Ci and Ci1 for 1 i m 1), and each one of these matchings will be
constructed to ensure that there are no instabilities within one of the countries.
More specifically:
1. For each 1 i m 1, compute a matching Mi between Ci and Ci1 , as follows:
(a) Order the people in Ci arbitrarily.
(b) For each person x in Ci , match x to the unmatched person in Ci1 whom x most prefers.
2. Form the groups by assembling all matched pairs: x C0 is matched with xs match x0 in M1 , with
the person with whom x is matched in M2 , and so on.
Claim: The groups formed by this algorithm are stable.
Proof. Consider two people x and y from country Ci . We claim that there can be no instability between
x and y because of their matches in Mi . More specifically, suppose that x a and y b in Mi , where
a, b Ci1 . (Again, if i = 1 then Ci1 denotes the facilitators.) We claim the following:
() Either x prefers a to b or y prefers b to a.
To prove (), observe that either x or y was matched first in computing Mi . Suppose that x was matched
before y. Then we know that neither a nor b were matched in xs iteration (x chose a; later y chose b who
had to be unmatched even by ys iteration). But because x chose a over b, by the definition of the algorithm
x must prefer a to b. Similarly, if y chose before x in that step, then y must prefer b to a. Thus () follows.
Thus the pair x, y cannot form an instability, by definition. But x and y were arbitrary, so the claim follows.
To implement this algorithm efficiently, we need to be have, for each person x Ci , easy access to xs
preferences over the people in Ci1 . To do this, before doing anything else, we will go through the given
preferences lists and delete anyone not from that delegation. (I.e., for x Ci , we simply remove from xs
list anyone not from delegation Ci1 .) This preprocessing takes (mn) time for each x, assuming we have
constant-time access to determining from which delegation a particular person is.
It is now straightforward to compute a single matching between Ci and Ci1 in O(n2 ) time: maintain
an n-element Boolean array indicating whether each person in Ci1 is matched or unmatched, and each of
the n matching iterations we need only proceed down the n-element preference list for the current person
x Ci until we find an unmatched element of Ci1 , which we then mark. This takes O(n) time per person
x, and thus O(n2 ) time per matching, and thus (n2 m) time in total.