Test Your Intuition (19): The Advantage of the Proposers in the Stable Matching Algorithm

Stable mariage

The Gale-Shapley stable matching theorem and the algorithm.

GALE-SHAPLEY THEOREM Consider a society of n men and n women and suppose that every man [and every woman] have a preference (linear) relation on the women [men] he [she] knows. Then there is a stable marriage, namely a perfect matching between the men and the women so that there are no men and women which are not matched so that both of them prefer the other on their spouces.

Proof: Consider the following algorithm, on day 1 every man goes to the first woman on his list and every woman select the best man among those who come to her and reject the others. On the second day every rejected men go to the second woman on his list and every woman select one man from all man that comes to her (including the man she selected in the previous day if there was such a man) and rejects all others, and so on. This process will terminate after finitely many days and with a stable marriage! To see that the process terminate note that each day at least one man will come to a new women, or go back home after beeing rejected from every women (n+1 possibilities) and none of these possibilitie will ever repeat itself so after at most days things will stabilize. When it terminates we have a stable marriage because suppose women W and men M are not married at the end. If M is married to a women he prefers less then W or to no women at all it means that M visited W and she rejected him so she had a better men than M.  Sababa!
It turns out that the above algorithm where the men are proposing and being rejected is optimal for the men! If a man M is matched to a woman W then there is not a single stable marriage where M can be matched to a woman higher on his list. Similarly this algorithm is worst for the women. But by how much?

Random independent preferences

Question 1:  There are n men and n women. If the preferences are random and men are proposing, what is the likely average women’s rank of their husbands, and what is the likely average men’s rank of their wives.

You can test your intuition, or look at the answer and for a follow up question after the fold.

Answer to Question 1: On average a man will be matched to the woman in place log n on his list. (Place one is his most preferred woman.) A woman will be matched on average to a man ranked n/log n on her list.

Boris Pittel proved this result in the  beautiful 1989 paper the average number of stable matchings  were he also proved  that that the number of stable matching behaves on average like n log n/e. A related 1990 paper is entitled “stable husbands” and was written by Donald Knuth, Rajeev Motwani, and Pittel.

Having one extra man

Suppose now that we have n women and n+1 men. Again we let the men propose, we apply exactly the same algorithm, and this time one man will be left unmatched. (Still this will give for every man his most preferred woman out of all stable marriages.)

Question 2, Test your intuition!: There are n+1 men and n women. If the preferences are random and men again are proposing, what is the likely average women’s rank of their husbands, and what is the likely average men’s rank of their wives.

OK, a poll: