1. Introduction Flashcards
GS Algo (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)
Justify this.
GS Algo (1.2) The sequence of women to whom m proposes gets worse and worse (in terms of her preference list)
Justify this.
GS Algo (1.3) The G-S algorithm terminates after at most n^2 iterations of the While loop
Find a measure of “progress”
Each iteration consists of some man proposing to a woman he has never proposed to before. If we let P(t) denote the set of pairs such that m has proposed to w by the end of iteration t, for all t, the size of P(t+1) is strictly > the size of P(t). But there are only n^2 possible pairs of m and w in total, so the value of P(.) can increase at most n^2 times over the course of the algorithm. It follows that there can be at most n^2 iterations.
GS Algo (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.
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 me total, and m is not engaged, so this is a contradiction.
GS Algo (1.5) The set S returned at termination is a perfect matching.
At no time is anyone engaged to more than one person, and so the set of engaged pairs always forms a matching. Suppose the algo 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.
GS Algo (1.6) Consider an execution of the GS algorithm that returns a set of pairs S. The set S is a stable matching.
Assume there is an instability and obtain a contradiction for (m,w),(m’,w’).
For an instability: m prefers w’ to w, and w’ prefers m to m’
In the execution of the algo, m’s last proposal was by definition to w. Did m propose to w’ at some point? If he didn’t, w must appear before w’ on his pref list, so that’s not possible. If he did, then he was rejected by w’ in favor of some other m. Either way, this contradicts our assumption that w’ prefers m to m’. It follows that the set is a stable matching.
GS Algo (1.7) Every execution of the GS algorithm results in the set S*
Suppose that some execution results in a matching S in which some m is paired with a w who is not his best valid partner. Since m propose in decreasing order of pref, this means that some m is rejected by a valid partner during execution. The rejection of m by his most preferred 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 m. Either way, w forms an engagement with m’, who 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, it must be that m’ had not been rejected by any valid partner at the point in ex 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 she rejected m in favor of m’. Since (m’,w) is not within S’, (m’,w) is an instability in S’. This contradicts our claim that S’ is stable, and hence contradicts our initial assumption.
GS Algo (1.8) In the stable matching S*, each woman is paired with her worst valid partner.
Suppose there were a pair (m,w) in S* so 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 parter 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.
