This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Quint, T. Articles by Wako, J. Search for Related Content

On Houseswapping, the Strict Core, Segmentation, and Linear Programming

Department of Mathematics, University of Nevada at Reno, Reno, Nevada 89557
Department of Economics, Gakushuin University, Tokyo 171-8588 Japan
quint{at}unr.edu
jun.wako{at}gakushuin.ac.jp

We consider the n-player houseswapping game of Shapley and Scarf (1974), with indifferences in preferences allowed. It is well known that the strict core of such a game may be empty, single valued, or multi valued. We define 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 find the unique strict core allocation in the model with no indifference). 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³) 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 (1992) for the marriage game of Gale and Shapley (1962).

Key Words: Shapley-Scarf houseswapping game; indivisible good; strict core; top trading cycle; top trading segmentation; linear programming; polyhedron; extreme point; computational complexity
History: Received: March 27, 2002; revision received: February 14, 2003;revision received: February 20, 2004;