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

Thomas Quint () and Jun Wako ()
Additional contact information
Thomas Quint: University of Nevada, Reno
Jun Wako: Gakushuin University

Yale School of Management Working Papers from Yale School of Management

Abstract: We consider the n-player houseswapping game of Shapley-Scarf (1974), with indfferences 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 and 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 Rothbum (1991) for the marriage game of Gale and Shapley (1962).

Keywords: Shapley-Scarf Economy; Strict Core; Linear Inequality System; Extreme Points (search for similar items in EconPapers)
JEL-codes: C60 C71 C78 (search for similar items in EconPapers)
Date: 2004-07-28
References: Add references at CitEc
Citations: View citations in EconPapers (21)

Downloads: (external link)
http://papers.ssrn.com/sol3/papers.cfm?abstract_id=410807 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ysm:somwrk:ysm373

Access Statistics for this paper

More papers in Yale School of Management Working Papers from Yale School of Management Contact information at EDIRC.
Bibliographic data for series maintained by ().