One-to-one matching problems with location restrictions

This paper introduces a novel set of one-to-one matching problems: matchings subject to location restrictions. When scarcity of matching locations exists some agents may want to form a new partnership without being able to implement it. In this general setting we develop two stability concepts, direct and (coalition) exchange* stability, akin to Gale Shapley stability and exchange stability (Alcalde, 1995) respectively. We show that coalition-exchange* stability is a refinement of direct stability. When no location scarcity exists then direct stability is equivalent to Gale Shapley stability and coalition-exchange* stability is equivalent to requiring both exchange stability (Alcalde, 1995) and Gale Shapley stability. We show that the set of coalition-exchange* stable matchings is a superset of the farsighted core, and equal to the farsighted core if locations are not scarce and the matching problem is individually rational. The paper also shows that an exchange* stable set can not be a strict subset of a farsighted stable set and provides an example of a roommate problem in which no farsighted stable set exists while an exchange* stable set does exist. Finally, the paper obtains that deciding whether the farsighted core of an individually rational roommate problem exists is NP-complete.