Stability in Large Matching Markets with Complementarities

TLDR

Labor markets are often modeled as many‑to‑one matching markets, and it is well known that complementarities can prevent the existence of a stable matching. The authors propose a new matching algorithm that guarantees a stable matching with high probability when the number of couples grows sublinearly with market size. The study analyzes large random matching markets that include couples. When the number of couples grows sublinearly, a stable matching is found with high probability; if it grows linearly, a stable matching exists with only constant probability, a result that explains data from the psychology intern market.

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.