Matching with couples in large markets: Kojima, Pathak and Roth

Fuhito Kojima, Parag Pathak and I have a paper coming out that suggests a beginning of an answer to the empirical puzzle presented by the fact that the many annual labor matching markets with couples that use the Roth-Peranson algorithm overwhelmingly find stable matchings, even though in principle they might fail to exist.  In large markets with short preference lists and without too many couples, the answer seems to be related to the fact that there remain sufficiently many unfilled positions so that vacancy chains are more likely to end than to cycle.

Here's the paper:
Kojima, Fuhito, Parag A. Pathak, and Alvin E. Roth, “Matching with Couples: Stability and Incentives in Large Markets,” April 2010, revised April 2013, Quarterly Journal of Economics, forthcoming.

Abstract: Accommodating couples has been a longstanding issue in the design of centralized labor market clearinghouses for doctors and psychologists, because couples view pairs of jobs as complements. A stable matching may not exist when couples are present. This paper's main result is that a stable matching exists when there are relatively few couples and preference lists are sufficiently short relative to market size. We also discuss incentives in markets with couples. We relate these theoretical results to the job market for psychologists, in which stable matchings exist for all years of the data, despite the presence of couples.