Publication Date: May 2003
We consider the n-player houseswapping game of Shapley-Scarf (1974), with indiﬀerences in preferences allowed. It is well-known that the strict core of such a game may be empty, single-valued, or multivalued. We deﬁne a condition on such games called “segmentability”, which means that the set of players can be partitioned into a “top trading segmentation.” It generalizes Gale’s well-known idea of the partition of players into “top trading cycles” (which is used to ﬁnd the unique strict core allocation in the model with no indiﬀerence). We prove that a game has a nonempty strict core if and only if it is segmentable. We then use this result to devise an O(n3) algorithm which takes as input any houseswapping game, and returns either a strict core allocation or a report that the strict core is empty. Finally, we are also able to construct a linear inequality system whose feasible region’s extreme points precisely correspond to the allocations of the strict core. This last result parallels the results of Vande Vate (1989) and Rothblum (1991) for the marriage game of Gale and Shapley (1962).
Shapley-Scarf economy, Strict core, Linear inequality system, Extreme points
JEL Classification Codes: C71, C78, C60