Stability in large matching markets with complementarities

Itai Ashlagi, Mark Braverman, Avinatan Hassidim

Research output: Contribution to journalArticle

31 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)713-732
Number of pages20
JournalOperations Research
Volume62
Issue number4
DOIs
StatePublished - Jan 1 2014

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Management Science and Operations Research

Keywords

  • Couples
  • Deferred acceptance
  • Market design
  • Matching
  • Stability

Fingerprint Dive into the research topics of 'Stability in large matching markets with complementarities'. Together they form a unique fingerprint.

  • Cite this