Analyzing the Algorithm
First consider the view of a woman w during the execution of the algorithm. For a while, no one has proposed to her, and she is free. Then a man m may propose to her, and she becomes engaged. As time goes on, she may receive additional proposals, accepting those that increase the rank of her partner. So we discover the following
(1.1) w remains engaged from the point at which she receives her first proposal; and the sequence of partners to which she is engaged gets better and better (in terms of her preference list).
The view of a man m during the execution of the algorithm is rather different. He is free until he proposes to the highest-ranked woman on his list; at this point he may or may not become engaged. As time goes on, he may alternate between being free and being engaged; however, the following property does hold.
(1.2) The sequence of women to whom m proposes gets worse and worse (in terms of his preference list).
Now we show that the algorithm terminates, and give a bound on the maximum number of iterations needed for termination.
(1.3) The G-S algorithm terminates after at most n2 iterations of the While loop.
Proof. A useful strategy for upper-bounding the running time of an algorithm, as we are trying to do here, is to find a measure of progress. Namely, we seek some precise way of saying that each step taken by the algorithm brings it closer to termination.
In the case of the present algorithm, each iteration consists of some man proposing (for the only time) to a woman he has never proposed to before. So if we let P(t) denote the set of pairs (m, w) such that m has proposed to w by the end of iteration t, we see that for all t, the size of P(t + 1) is strictly greater than the size of P(t). But there are only n2 possible pairs of men and women in total, so the value of P(·) can increase at most n2 times over the course of the algorithm. It follows that there can be at most n2 iterations.
Two points are worth noting about the previous fact and its proof. First, there are executions of the algorithm (with certain preference lists) that can involve close to n2 iterations, so this analysis is not far from the best possible. Second, there are many quantities that would not have worked well as a progress measure for the algorithm, since they need not strictly increase in each iteration. For example, the number of free individuals could remain constant from one iteration to the next, as could the number of engaged pairs. Thus, these quantities could not be used directly in giving an upper bound on the maximum possible number of iterations, in the style of the previous paragraph.
Let us now establish that the set S returned at the termination of the algorithm is in fact a perfect matching. Why is this not immediately obvious? Essentially, we have to show that no man can “fall off” the end of his preference list; the only way for the While loop to exit is for there to be no free man. In this case, the set of engaged couples would indeed be a perfect matching. So the main thing we need to show is the following.
(1.4) If m is free at some point in the execution of the algorithm, then there is a woman to whom he has not yet proposed.
Proof. Suppose there comes a point when m is free but has already proposed to every woman. Then by (1.1), each of the n women is engaged at this point in time. Since the set of engaged pairs forms a matching, there must also be n engaged men at this point in time. But there are only n men total, and m is not engaged, so this is a contradiction.
(1.5) The set S returned at termination is a perfect matching.
Proof. The set of engaged pairs always forms a matching. Let us suppose that the algorithm terminates with a free man m. At termination, it must be the case that m had already proposed to every woman, for otherwise the While loop would not have exited. But this contradicts (1.4), which says that there cannot be a free man who has proposed to every woman.
Finally, we prove the main property of the algorithm—namely, that it results in a stable matching.
(1.6) Consider an execution of the G-S algorithm that returns a set of pairs S. The set S is a stable matching.
Proof. We have already seen, in (1.5), that S is a perfect matching. Thus, to prove S is a stable matching, we will assume that there is an instability with respect to S and obtain a contradiction. As defined earlier, such an instability would involve two pairs, (m, w) and (m, w), in S with the properties that.
m prefers w to w,
and. w prefers m to m
It follows that S is a stable matching.
Extensions
We began by defining the notion of a stable matching; we have just proven that the G-S algorithm actually constructs one. We now consider some further questions about the behavior of the G-S algorithm and its relation to the properties of different stable matchings.
To begin with, recall that we saw an example earlier in which there could be multiple stable matchings. To recap, the preference lists in this example were as follows:
m prefers w to w
.
m prefers w to w.
w prefers m to m.
w prefers m to m
Now, in any execution of the Gale-Shapley algorithm, m will become engaged to w, m will become engaged to w (perhaps in the other order), and things will stop there. Thus, the other stable matching, consisting of the pairs (m, w)and (m, w), is not attainable from an execution of the G-S algorithm in which the men propose. On the other hand, it would be reached if we ran a version of the algorithm in which the women propose. And in larger examples, with more than two people on each side, we can have an even larger collection of possible stable matchings, many of them not achievable by any natural algorithm.
This example shows a certain “unfairness” in the G-S algorithm, favoring men. If the men’s preferences mesh perfectly (they all list different women as their first choice), then in all runs of the G-S algorithm all men end up matched with their first choice, independent of the preferences of the women. If the women’s preferences clash completely with the men’s preferences (as was the case in this example), then the resulting stable matching is as bad as possible for the women. So this simple set of preference lists compactly summarizes a world in which someone is destined to end up unhappy: women are unhappy if men propose, and men are unhappy if women propose.
Let’s now analyze the G-S algorithm in more detail and try to understand how general this “unfairness” phenomenon is.
To begin with, our example reinforces the point that the G-S algorithm is actually underspecified: as long as there is a free man, we are allowed to choose any free man to make the next proposal. Different choices specify different executions of the algorithm; this is why, to be careful, we stated (1.6) as “Consider an execution of the G-S algorithm that returns a set of pairs S,” instead of “Consider the set S returned by the G-S algorithm.”
Thus, we encounter another very natural question: Do all executions of the G-S algorithm yield the same matching? This is a genre of question that arises in many settings in computer science: we have an algorithm that runs asynchronously, with different independent components performing actions that can be interleaved in complex ways, and we want to know how much variability this asynchrony causes in the final outcome. To consider a very different kind of example, the independent components may not be men and women but electronic components activating parts of an airplane wing; the effect of asynchrony in their behavior can be a big deal.
In the present context, we will see that the answer to our question is surprisingly clean: all executions of the G-S algorithm yield the same matching. We proceed to prove this now.
All Executions Yield the Same Matching There are a number of possible ways to prove a statement such as this, many of which would result in quite complicated arguments. It turns out that the easiest and most informative approach for us will be to uniquely characterize the matching that is obtained and then show that all executions result in the matching with this characterization.
What is the characterization? We’ll show that each man ends up with the “best possible partner” in a concrete sense. (Recall that this is true if all men prefer different women.) First, we will say that a woman w is a valid partner of a man m if there is a stable matching that contains the pair (m, w). We will say that w is the best valid partner of m if w is a valid partner of m, and no woman whom m ranks higher than w is a valid partner of his. We will use best(m) to denote the best valid partner of m.
Now, let S∗ denote the set of pairs {(m, best(m)) : m ∈ M}. We will prove the following fact.
(1.7) Every execution of the G-S algorithm results in the set S∗.
This statement is surprising at a number of levels. First of all, as defined, there is no reason to believe that S∗ is a matching at all, let alone a stable matching. After all, why couldn’t it happen that two men have the same best valid partner? Second, the result shows that the G-S algorithm gives the best possible outcome for every man simultaneously; there is no stable matching in which any of the men could have hoped to do better. And finally, it answers our question above by showing that the order of proposals in the G-S algorithm has absolutely no effect on the final outcome. Despite all this, the proof is not so difficult.
Proof. Let us suppose, by way of contradiction, that some execution E of the G-S algorithm results in a matching S in which some man is paired with a woman who is not his best valid partner. Since men propose in decreasing order of preference, this means that some man is rejected by a valid partner during the execution E of the algorithm. So consider the first moment during the execution E in which some man, say m, is rejected by a valid partner w. Again, since men propose in decreasing order of preference, and since this is the first time such a rejection has occurred, it must be that w is m’s best valid partner best(m).
The rejection of m by w may have happened either because m proposed and was turned down in favor of w’s existing engagement, or because w broke her engagement to m in favor of a better proposal. But either way, at this moment w forms or continues an engagement with a man m whom she prefers to m.
Since w is a valid partner of m, there exists a stable matching S containing the pair (m, w). Now we ask: Who is m paired with in this matching? Suppose it is a woman w = w.
Since the rejection of m by w was the first rejection of a man by a valid partner in the execution E, it must be that m had not been rejected by any valid partner at the point in E when he became engaged to w. Since he proposed in decreasing order of preference, and since w is clearly a valid partner of m, it must be that m prefers w to w. But we have already seen that w prefers m to m, for in execution E she rejected m in favor of m. Since (m, w) ∈ S, it follows that (m, w) is an instability in S.
This contradicts our claim that S is stable and hence contradicts our initial assumption.
So for the men, the G-S algorithm is ideal. Unfortunately, the same cannot be said for the women. For a woman w, we say that m is a valid partner if there is a stable matching that contains the pair (m, w). We say that m is the worst valid partner of w if m is a valid partner of w, and no man whom w ranks lower than m is a valid partner of hers.
(1.8) In the stable matching S∗, each woman is paired with her worst valid partner.
Proof. Suppose there were a pair (m, w) in S∗ such that m is not the worst valid partner of w. Then there is a stable matching S in which w is paired with a man m whom she likes less than m. In S, m is paired with a woman w = w; since w is the best valid partner of m, and w is a valid partner of m, we see that m prefers w to w
But from this it follows that (m, w) is an instability in S, contradicting the claim that S is stable and hence contradicting our initial assumption.
Thus, we find that our simple example above, in which the men’s preferences clashed with the women’s, hinted at a very general phenomenon: for any input, the side that does the proposing in the G-S algorithm ends up with the best possible stable matching (from their perspective), while the side that does not do the proposing correspondingly ends up with the worst possible stable matching.
.