On Houseswapping, the Strict Core, Segmentation, and Linear Programming
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(n 3 ) 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).
Quint, Thomas and Wako, Jun, "On Houseswapping, the Strict Core, Segmentation, and Linear Programming" (2003). Cowles Foundation Discussion Papers. 1685.