Couples on the labor market

One of the longstanding puzzles in market design is why we have been as lucky as we have been in the design and operation of labor market clearinghouses that allow couples to state preferences over pairs of jobs. You can't get a stable matching without allowing couples to state their preferences this way, but when they do, the set of stable matching can be empty. But it almost never is, in practice.

Here's a first step towards understanding that:
Kojima, Fuhito, Parag A. Pathak, and Alvin E. Roth, " Matching with Couples: Stability and Incentives in Large Markets," working paper, April 8 2010.

Abstract: Complementarities pose problems in models of two-sided matching markets. This has been a longstanding issue in the design of centralized labor market clearinghouses that need to accommodate complementarities due to couples, as in the US market for medical doctors. These clearinghouses aim for a stable matching but a stable matching does not necessarily exist when
couples are present. This paper provides conditions under which a stable matching exists with high probability in large markets. Moreover, we present a mechanism that finds a stable matching with high probability and in which truth-telling by all participants is an approximate equilibrium. We relate these theoretical results to data from the labor market for clinical psychologists, in which stable matchings exist for all years of our data, despite the presence of couples.