We are considering the stable marriage theorem. Suppose that 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?
Boris Pittel proved that 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.
We asked in the post “Test your intuition (19)” what is the situation if there is one additional man, and men are still proposing. This question is based on a conversation with Jacob Leshno who told me about a remarkable paper Unbalanced random matching markets by Itai Ashlagi, Yash Kanoria, and Jacob Leshno.
Before getting to the answer let me mention that the answers to Test your intuition (18) and (17) are coming soon.
Here is how the collective intuition looks like.
The amazing result by Ashlagi, Kanoria, and Leshno asserts that a single additional man reverse the situation. Even when men propose, which gives each of them the best match in a stable marriage, with high probability every woman will get the man ranked ~log n in her list, and every man will get the woman ranked ~n/log n in his list. Unless the number of men and women is equal the outcomes for the best algorithm and for the worst algorithm are similar for both men and women.
And here is how things look in a computer simulation:
The picture plots the men’s average rank of wives (taking only matched men), calculated by averaging many draws of the market. The number of women is held fixed at 40, and the number of men varies across the x axis from 20 to 80. You can see that the men optimal stable matching (MOSM) and the Woman optimal stable matching (WOSM) are different when there are 40 men, but very close otherwise. The men get a low average rank when there are fewer men, and they get a high rank when there are more men. (note that given the men a totally random women would give them avg rank of (40+1)/2 ).
Combinatorics and more 