Tata Institute of Fundamental Research

Unbalanced Random Matching Markets

Speaker: Yashodhan Kanoria (Columbia University Decision, Risk and Operations Division New York, NY United States of America)
Organiser: Jaikumar Radhakrishnan
Date: Wednesday, 24 Jul 2013, 14:30 to 15:30
Venue: A-212 (STCS Seminar Room)

(Scan to add to calendar)
Abstract:  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.