Abstract
We study how much communication is needed to find a stable matching in a two-sided matching market with private preferences. Segal (2007) and Gonczarowski et al. (2015) showed that, in the worst case, any protocol that computes a stable matching requires the communication cost per agent to scale linearly with the total number of agents. In markets with many thousands of agents, this communication requirement is implausibly high, casting doubt on whether stable matchings can arise in large markets. We study markets with realistic assumptions on the preferences of agents and their available information, and show that a stable matching can be found with a much smaller communication requirement. In our model, the preferences of workers are unrestricted, and the preferences of firms follow an additively separable latent utility model. Our efficient communication protocol modifies the worker-proposing deferred acceptance algorithm by having firms signal workers they especially like while also broadcasting qualification requirements to discourage other workers who have no realistic chances from applying. In the special case of tiered random markets, the protocol can be modified to run in two rounds and involve only private messages. Our protocols have good incentive properties and give insights into how to mediate large matching markets to reduce congestion.