Stability in Large Matching Markets with Complementarities
Itai Ashlagi, Mark Braverman, Avinatan Hassidim
Operations Research · 2014 · Volume 62 · Issue 4
Abstract
Labor markets can often be viewed as many-to-one matching markets. It is well known that if complementarities are present in such markets, a stable matching may not exist. We study large random matching markets with couples. We introduce a new matching algorithm and show that if the number of couples grows slower than the size of the market, a stable matching will be found with high probability. If however, the number of couples grows at a linear rate, with constant probability (not depending on the market size), no stable matching exists. Our results explain data from the market for psychology interns.
Keywords
stability, matching, couples, deferred acceptance, market design
Enable JavaScript for citation tools and additional paper interactions.