For the Stable Matching algorithm by Gale-Shapley, how do I prove that at most one man will get his worst choice?
My intuition is that I have to use contradiction. Assume that there are two men who will get their worst preferences: $M_1$ with $W_1$ and $M_2$ with $W_2$. I have to prove $M_2$ and $W_2$ are unstable. However, I can't think of anything. Can anyone help me with the proof?
Thanks!
On
Suppose all men have the same preferences and are indifferent over all women. In any stable match, any man who matches gets his worst choice.
Suppose all the men have strict preferences. Suppose there are $K$ men and $K+1$ women. All men rank the same woman last, but all women and all men find one another acceptable. None of the men get their worst choice in the outcome of the GS algorithm with the men proposing and the claim is false.
On
I assume the basic setup as described on wikipedia (ie equal numbers of men and women, strict preferences). Assume $M_1$ and $M_2$ are paired with their worst choices, $W_1$ and $W_2$, respectively. Observe the following:
Consider the state just before the final round. By 1 and 2, $M_1$ has proposed to each woman other than $W_1$ (and possibly $W_1$ also), and similarly for $M_2$. Thus every woman has been proposed to, so by 3 they are all engaged. We have assumed equal numbers of men and women, so the men are also all engaged. But this means the algorithm should terminate, a contradiction.
On
Let us begin by supposing that there are n men and n women, meaning there are n men ranking n women and vice versa. Let man x = Mx and woman x = Wx. Let us also assume, for the sake of contradiction, that there are two men M1 and M2 who have both been paired with their least-preferred choices, W1 and W2 respectively.
If we examine how M1 could have been paired with W1 (his least-preferred choice), we must recognize that this means that M1 had proposed to every other woman and had gotten rejected. M1 must have gotten rejected by every other woman because every other woman had to already have been paired with a man that she preferred to M1, by construction of the Gale-Shapley algorithm.
If every other woman had already been paired with a man that she had preferred to M1, that means that every other man besides M1 was also paired. So, once M1 was paired with it’s least-preferred woman W1, all women and men would have been paired. By construction of the Gale-Shapley algorithm, the algorithm’s terminating condition would have been met, namely that all women and men are paired, and the algorithm would stop running.
What this suggests is that Gale-Shapley would have already terminated execution before M2 even had the chance to be paired with W2 (its least-preferred choice), which contradicts our initial assumption that M1 and M2 were both paired with their least-preferred choices. This assumes, however, that M2 and W2 were not already paired. But, how can we be certain that M2 and W2 had not already been paired?
Well, the answer is, for the same reason we know that execution must stop once M1 is paired with W1. As we have established, when M1 pairs with its least-preferred choice W1, execution must stop because all men and women would have been matched by then. Therefore, we can be certain that M2 could not have been matched with W2 because that would not allow M1 to match with W1 in the first place; the algorithm’s execution would have terminated.
So, our contradiction stands, and we have proven that there is at most one man who gets their last choice.
Suppose $M_1$'s last choice is $W_1$ and $M_2$'s last choice is $W_2$. Before they are forced to select $W_1$/$W_2$ respectively, the Gale–Shapley algorithm has already directed $M_1$/$M_2$ to propose to all women other than $W_1$/$W_2$. Thus all women have been proposed to, so are now engaged, so the algorithm stops. But we assumed that the algorithm does not stop here, so we have a contradiction and at most one man can have his worst choice.