On choice and communication in random matching markets
Friday, May 6, 2016 - 1:00pm to 2:00pm
Packard 202
Itai Ashlagi (Stanford)
Abstract / Description: 

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.


The Information Theory Forum (IT-Forum) at Stanford ISL is an interdisciplinary academic forum which focuses on mathematical aspects of information processing. With a primary emphasis on information theory, we also welcome researchers from signal processing, learning and statistical inference, control and optimization to deliver talks at our forum. We also warmly welcome industrial affiliates in the above fields. The forum is typically held in Packard 202 every Friday at 1:00 pm during the academic year.

The Information Theory Forum is organized by graduate students Jiantao Jiao and Yanjun Han. To suggest speakers, please contact any of the students.


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.