Seminars & Colloquia Calendar

We study the amount of communication needed to fi nd a stable matching in a two-sided matching market with private preferences when agents have some knowledge of the preference distribution. In a two-sided market with workers and fi rms, when the preferences of workers are arbitrary and private and the preferences of firms follow an additively separable latent utility model with commonly known and heterogeneous parameters, we describe an algorithm that fi nds a stable matching with high probability and requires at most O*( sqrt{n}) bits of communication per agent. (We also show that this is the best possible under this setting.) Our algorithm is a modification of worker-proposing deferred acceptance that skips wasteful applications. Firms help workers better target applications by signaling workers that they privately like and broadcasting to the market a qualifi cation requirement to discourage those with no realistic chances from applying. Our results yield insights on how matching markets can be better organized to reduce congestion. Broadly, agents should reach out to their favorites among 'gettable' partners, while waiting for their dream matches to reach out to them.

Joint work with Itai Ashlagi, Mark Braverman and Peng Shi.