CPSC 320: Steps in Algorithm Design and Analysis Solutions*
This is a continuation of the previous worksheet, where we will examine a proof of correctness of the Gale-Shapley algorithm dierent from that presented in the textbook. Try not to look at the textbook while working on this worksheet.
Step 6: Proving the correctness of the algorithm.
It’s always good to start by writing down what it means for the algorithm to be correct. For the SMP problem, it means that the algorithm outputs a perfect matching with no instabilities.
1. Show that the output is a perfect matching (that is, each employer is matched with exactly one applicant, and each applicant is matched with exactly one employer).
We will break this down further:
Every applicant has been considered at least once upon termination.
SOLUTION: This is easy to see by examining the condition of the While loop, which is false when the algorithm terminates. When the condition is false, one of two things must be true. Either all employers have considered all applicants, in which case certainly every applicant has been considered at least once. Otherwise, all employers must be matched, and so all applicants must be also matched since no applicant is matched with two employers (see lines 12, 13 and 17, 18 of the code). But an applicant can only be matched if it has been considered, and again the statement must be true.
Every applicant is matched upon termination.
SOLUTION: To see why, note that if an applicant a is unmatched when a is considered, then a becomes matched (line 13). If a is already matched, say to employer e′ and is considered again, say by e, then a is either rematched with e (line 18) or remains matched with e′. Either way, a remains matched by the end of the iteration. We’ve already shown above that every applicant is considered at least once by the algorithm and so all applicants must be matched when the algorithm terminates.
Every employer is matched upon termination.
SOLUTION: As already noted above, no applicant can be matched to more than one employer, because whenever the algorithm adds a match (e, a) to M either a was already unmatched (lines 12, 13) or the match involving a is removed (line 17) before adding the new match (line 18). So, if all applicants are matched, all employers must be matched too.
Copyright Notice: UBC retains the rights to this document. You may not distribute this document without permission.
*
1
2. Show that the output has no instabilities.
Recall that a pair (e,a′) is an instability if (e,a) and (e′,a′) are distinct pairs in M, and also e prefers a′ to a, and a′ prefers e to e′. That is, e and a′ would prefer to be matched with each other than with their matches in M.
The approach we will take in this worksheet is to show that the (partial) matching constructed after each iteration of the While loop avoids instabilities. Let Mk be the matching at the end of iteration k ≥ 0 of the While loop (ignoring unmatched employers and applicants), and let Ek and Ak be the set of employers and the set of applicants, respectively, that are matched in Mk. We show by induction that there is no instability in Ek × Ak with respect to Mk.
Claim: There is no instability in Ek × Ak with respect to Mk. Base case:
SOLUTION: k = 0. Then Mk is empty, and so there are no instabilities.
Inductive step: We show that at the end of some iteration k ≥ 2, there are no instabilities in
Ek × Ak with respect to Mk, assuming
SOLUTION: the induction hypothesis that there are no instabilities in Ek−1 × Ak−1 with respect
to Mk−1.
Suppose that at iteration k, e considers (makes an oer to) a.
(a) There can be no instabilities in Mk that involve neither e nor a because SOLUTION: such instabilities would also have arisen in Mk−1, which is stable by the induction
hypothesis.
(b) Consider now potential instabilities involving one (or both) of e and a. There are three cases (corresponding to the cases of the if statement inside the while loop):
Case 1. a is unmatched and accepts e’s oer. No instability can involve a because
SOLUTION: the other employers that are matched in Mk have not yet considered a and so prefer their own matches to a.
No instability can involve e because
SOLUTION: if e prefers a′ to a, then a′ has already been matched with an employer that
a′ prefers to e.
Case 2. a is already matched, say to e′, and accepts e’s oer, rejecting e′. In this case
no instability can involve a because
SOLUTION: there is no instability in Mk−1 and a prefers e to its match in Mk−1.
No instability can involve e
SOLUTION: for the same reason as in Case 1.
Employer e′ is now unmatched and so not in Ek, so e′ does not concern us. Case 3. a is already matched, say to e′, and prefers e′ to e.
SOLUTION: In this case Mk = Mk−1, which has no instabilities by the induction hypoth- esis.
This completes the inductive proof.
Choosing k to be the last iteration of the While loop, we have that M = Mk, E = Ek and A = Ak. Therefore there are no instabilities in E × A with respect to M. QED
2
Note: Proof by induction is often a nice way to show that properties are preserved throughout successive iterations of a While loop. It is natural that the cases in the proof will follow the structure of If statements in the While loop. The proof by contradiction in the textbook is more streamlined than the proof presented here, and you should read that too. But inductive reasoning about While loops can be a more structured and fool-proof approach when gaining experience with proofs.
3