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.
Ashlagi, Itai, Mark Braverman, Yash Kanoria, and Peng Shi. "Communication Requirements and Informative Signaling in Matching Markets." Columbia Business School, July 2017.
Each author name for a Columbia Business School faculty member is linked to a faculty research page, which lists additional publications by that faculty member.
Each topic is linked to an index of publications on that topic.