Unbalanced Random Matching Markets


Yashodhan Kanoria


Columbia University
Decision, Risk and Operations Division
New York, NY
United States of America


Wednesday, 24 July 2013, 14:30 to 15:30


  • A-212 (STCS Seminar Room)


We analyze large random matching markets with unequal numbers of men and women. We find that being on the short side of the market confers a large advantage. For each agent, assign a rank of 1 to the agent's most preferred partner, a rank of 2 to the next most preferred partner and so forth. If there are $n$ men and $n + 1$ women then, we show that with high probability, in any stable matching, the men's average rank of their wives is no more than $3 log n$, whereas the women's average rank of their husbands is at least $n/(3 log n)$. Furthermore, with high probability, the fraction of agents with multiple stable partners is vanishing as the market grows large, i.e., such unbalanced random matching markets have a 'small core'.

Our results suggest that a 'small core' may be generic in matching markets, contrary to prior beliefs (based on joint work with Itai Ashlagi and Jacob Leshno).

Bio: Yashodhan Kanoria is Assistant Professor in the Decision, Risk and Operations Division at Columbia Business School. He obtained a B. Tech. from IIT Bombay and a PhD from Stanford, both in Electrical Engineering. His current research interests include matching markets, graphical models and probability.