This document contain relatively polished proofs with less motivation and context compared to the slides, intended only for quick reference. Please refer to the slides for the best learning experience.
Algorithm. (integer square root)
Input: A positive integer n.
Goal: An integer k such that (k-1)^2 < n \le k^2.
1. Let k = 1.
2. while k^2 < n do
3. Update k = k + 1.
4. return kClaim. The algorithm is correct. Proof. No errors occur.
The loop terminates in \lceil \sqrt{n} \rceil - 1 iterations. This because after i iterations, we have k = i + 1 (a loop invariant). After \lceil \sqrt{n} \rceil - 1 iterations, this means have k = \lceil \sqrt{n} \rceil. Thus k^2 = \lceil \sqrt{n} \rceil^2 \ge n, so the while loop exits.
To show that the code meets the specification, first note the loop invariant that (k - 1)^2 < n after every iteration. Combined with the while exit condition that k^2 \ge n, we get the desired goal that (k-1)^2 < n \le k^2. ∎
Algorithm. (Gale–Shapley)
Input: Two groups P and R of n
people each, with preference lists over the other group
Goal: A stable matching (perfect matching with no
unstable pairs)
1. while there is a free proposer p do
2. Let r be the top remaining person on p's preference list.
3. if r is also free then
4. Have r accept p.
5. else if r is paired but prefers the new proposer p then
6. Have r accept p and reject their current match p'.
7. else (if r is paired and prefers their current match)
8. Have r reject p.
9. return all matchesWe note the following three loop invariants:
Trading up) At the end of every iteration, if r is paired to someone, it prefers its current match over all previous matches.
Claim. In line 2 when p picks the next top person on their preference list, p has not yet exhausted the entire list.
Proof. Suppose for contradiction p has exhausted the entire list. This means they proposed to everyone and also got rejected by everyone. Note that every r must have been paired when they rejected p. By invariant 1, every r is still paired now.
Combining invariant 2 with every r being paired to someone, there must be exactly n pairs. Because |P| = |R| = n, every proposer must also be paired. This contradicts p being free in line 2. ∎
Claim. The algorithm terminates in n^2 iterations.
Proof. There are n^2 possible proposals (each p \in P to each r \in R). Because line 2 always picks a new proposal and never throws an error, the while loop must end within n^2 iterations. ∎
Claim. The algorithm outputs a perfect matching.
Proof. At the end of the algorithm, every p \in P is paired. Combined with invariant 2, there must be exactly n pairs. Because |P| = |R| = n, every receiver must also be paired, and the pairing is a perfect matching. ∎
Recall the definition of unstable pair.
Definition. Given a candidate matching and preference lists, a pair (p, r) is unstable if p and r prefer each other over their matches in the matching.
Claim. The perfect matching returned by the algorithm has no unstable pairs.
Proof. Let (p, r) be any pair.
Case 1: (p, r) is in the matching. They cannot prefer each other over their matches in the matching, because they are each other’s matches in the matching.
Case 2: (p, r) is not in the matching, because p stopped proposing before getting to r. Then p is matched to someone that it prefers over r, so (p, r) is not unstable.
Case 3: (p,
r) is not in the matching, because p proposed to r but got rejected or later unpaired.
At the time of rejection, r must
have been matched to someone they prefer more than p. By invariant 3 (trading up
),
r is still matched to someone
that they rank higher than p at
the end of the algorithm. Thus, (p,
r) is not unstable. ∎
Theorem. The Gale–Shapley algorithm always finds the unique stable matching that is both best for proposers and worst for receivers.
Key note: Best
does not mean that all
proposers get their top choice, since that configuration may not
be stable. It means that among all stable matchings,
every proposer is happier in this matching than any other
stable matching (or equally happy).
Definition. Say that (p, r) are valid partners if there is some stable matching where they are matched together.
Proof of Theorem. (Proposer optimality) Suppose for contradiction the output is not proposer-optimal. Consider the first time that a valid receiver rejected a proposer. More specifically, say that p ended up paired with r in the output, but prefers r' who is also valid and rejected p. Let p' be the reason r' rejected p. This means r' prefers p' over p.
Consider the other stable matching, in which p ended up paired with r' (since they are valid partners). Consider who the partner of p' is in that matching, since it can no longer be r'.
Case 1: p' is matched with someone they prefer less than r'. This cannot be the case, because (p', r') would then be a unstable pair.
Case 2: p' is matched with someone they prefer more than r'. Then in the original matching, this receiver rejected p' before p' was paired to r'. This cannot be the case, because r' was the first valid receiver ever rejected by a proposer.
We have reached a contradiction in all cases.
(Receiver pessimality) Suppose for contradiction the output is not receiver-pessimal. Then for some r, the output matched p with r, but p' is also a valid partner and r prefers p over p'. Since p' and r are valid partners, consider that matching. Consider who the partner of p is in that matching, since it can no longer be r.
Case 1: p is matched with someone they prefer less than r. This cannot be the case, because (p, r) would be an unstable pair.
Case 2: p is matched with somone they prefer more than r. This cannot be the case, because the original matching is proposer optimal, meaning r is the best possible match for p among all stable matchings.
We have reached a contradiction in all cases. ∎
These are not important for this course, but may be of interest to you. For specific examples, see the lecture slides.