## IT-Forum

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.