Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

Communication requirements and Informative signaling in matching markets

Yash Kanoria: Columbia University

Location:  CoRE 301
Date & time: Wednesday, 08 February 2017 at 11:00AM - 11:11AM

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.