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

Shapleygale

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 n^2+n 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.

Boris

rajeevDonald

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:

About these ads
This entry was posted in Combinatorics, Games, Probability, Test your intuition and tagged , , , , , , . Bookmark the permalink.

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

  1. Peter Shor says:

    Suppose you find the stable marriage that minimizes the average rank of the spouse (averaged over both sexes). What is this average?

    • Gil Kalai says:

      Dear Peter, I am sure that people studied it but I dont know what is known.

      • Peter Shor says:

        Hi Gil,
        This then provides a perfect opportunity for you to test your intuition.

      • Gil Kalai says:

        Peter, in some cases, my “test your intuition” questions refer to questions where I already tested my intuition and failed. Especially painful was the question about colored balls (19). So maybe a moral of this series is that it is important to have intuitions and it is of no less importance to work things out and check very carefully those intuitions. On this specific question I would guess that for random preferences the average ranking for both sexes in the best stable marriage is on the order of n/log n.

      • Gil Kalai says:

        My intuition was wrong! Boris Pittel proved in 1992 that with high probability, for every stable matching the product of the two total ranks is asymptotic to n^3. So the average Peter asked about is likely to be n^{3/2}. (Ignoring log n s)

  2. Peter Shor says:

    I can’t see how the men could lose their advantage by having just one extra man, although I certainly think they will by the time there are n extra men, and I’d bet they would lose it with just \sqrt{n} extra men, so I’ll say that the men retain their advantage.
    I have no idea how to prove this, and I have fairly little confidence in this intuition.

  3. Pingback: Itai Ashlagi, Yashodhan Kanoria, and Jacob Leshno: What a Difference an Additional Man makes? | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s