One-to-one matching 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 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 and Gale Shapley stability. We partially characterize coalition-exchange* stable matchings through providing an interesting link between exchange* dominance and indirect dominance. Finally, we bridge recent developments in the computer science literature and economics literature on one-to-one matching problems by showing that deciding whether the farsighted core of an individually rational roommate problem exists is NP-complete