Implementation in Generalized Matching Problems

Abstract

We search for (Nash) implementable solutions on a class of one-to-one matching problems which includes both the housing market (Shapley and Scarf 1974) and marriage problems (Gale and shapley 1962). We show that the core correspondence is implementable. We furthermore show that any solution that is Pareto-efficient, individually rational, and implementable is a supersolution of the core correspondence. That is, the core correspondence is the minimal solution that is Pareto-efficient, individually rational, and implementable. A corollary of the independent interest in the context of the housing market is that the core correspondence is the only single-valued solution that is Pareto-efficient, individually rational, and implementable.