Prove that at most one man obtains his worst choice in stable matching algorithm 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! 
 A: 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.
A: 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:


*

*$M_1$ must propose to every woman over the course of the algorithm, proposing to $W_1$ last.

*$M_1$ makes at most one proposal per round.

*Once a woman is proposed to, they remain engaged for the rest of the algorithm (though maybe not to the same person).


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.
A: 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.
