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. Continue reading