The Short-Side Advantage in Random Matching Markets by Linda Cai and Clayton Thomas (guest post by Itai Ashlagi)

 Itai Ashlagi writes: 

Linda Cai and Clayton Thomas, both graduate students, have a very short, elegant and straightforward proof for why the short side has a large advantage in two-sided matching markets with uniformly random generated preferences (in a large market with n men and n+1 women, in any stable matching men get on average their logn rank and women get on average their n/logn rank).   Here is the paper.

So let’s just describe the proof.

Quick background:

In a balanced market with n people on each side, the men-proposing deferred acceptance (MPDA) terminates the moment all women received at least one proposal. It is quite straightforward to show that this happens after O(nlogn) proposals by men. Why?  The number of proposals dominates (but very similar) to the number of steps in the famous “coupon collector” problem: there are n different coupons which are drawn with replacement until all coupons are drawn: the number of draws is the sum of expectations of geometric random variables, which sums to n times the n-th harmonic, or O(nlogn).   So each man makes on average O(logn) proposals. Since women receive on average O(logn) proposals their average rank for their stable partner is least n/logn.

A lemma by Immorlica and Mahdian, in another beautiful and important paper: a woman w* has a stable partner who she ranks better than k if and only if w* remains matched in the MPDA when she truncates her list after rank k. well, matching theory….

Let’s go to the market with n men and n+1 women:

By the lemma, w*’s rank in a woman-optimal stable matching is the minimum rank k she can truncate her list at while still being matched under MPDA.   Now suppose w* decides to reject all proposals she receives.  Run MPDA until it terminates - when all women other than w* receive a match. The total number of proposals from men is again like the coupon collector, O(nlogn).  And so w* received an average of O(logn) proposals. So she cannot expect to have a stable partner she ranks better than n/logn (and in expectation will remain unmatched if she truncates below that).