On choice and communication in random matching markets

Itai Ashlagi
Assistant Professor, Stanford University
Date: May 6th, 2016


We study the structure of stable matchings in two-sided random matching markets. First we show that even the slightest imbalance yields an essentially unique stable matching explaining why unique stable matching are empirically ubiquitous. This raises the question of how the composition of the market determines the set of potential matches. Towards this goal we study the communication requirements for reaching a stable matching in tiered random markets. We find that in such markets, a small amount of communication is needed from each agent to reach a stable matching with high probability. In particular, we construct a communication protocol that finds a stable matching with $O(\log^2 n)$ bits of communication on average per agent, and $O(\sqrt{n}\polylog (n))$ bits in worst case for an agent. Our results are tight in the sense that any communication protocol requires at least these costs, both on average and for the worst case agent.

Our construction reveals an illuminating structure of stable matchings. Agents ``apply'' to their favorite agents in a ``target tier'', which is the worst tier they can guarantee to be matched into. On the other hand, each agent maybe reached out by other agents from her top potential tier(s). Our results suggest that agents do not need to know their complete preferences, but only their favorite potential matches in their target tier and their preferences among agents who reach out to them.

Based on joint works with (i) Yash Kanoria and Jacob Leshno, and (ii) with Mark Braverman, Yash Kanoria and Peng Shi.


Itai Ashlagi is an Assistant Professor at the Management Science & Engineering Department. He is interested in game theory and market design. He is especially interested in matching markets, for which he developed mechanisms using tools from operations/cs and economics. His work influenced the practice of Kidney exchange, for which he has become a Franz Edelman Laureate. Ashlagi received his PhD in operations research from the Technion-Israel Institute of Technology. Before coming to Stanford he was an assistant professor of Operations Management at Sloan, MIT and prior to that a postdoctoral researcher at HBS. He is the recipient of the outstanding paper award in the ACM conference of Electronic Commerce 2009. His research is supported by the NSF including an NSF-CAREER award.