Advanced Search
MyIDEAS: Login to save this paper or follow this series

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


Author Info

  • Thomas Quint

    (University of Nevada, Reno)

  • Jun Wako

    (Gakushuin University)

Registered author(s):


    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).

    Download Info

    If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
    File URL:
    Download Restriction: no

    Bibliographic Info

    Paper provided by Yale School of Management in its series Yale School of Management Working Papers with number ysm373.

    as in new window
    Date of creation: 28 Jul 2004
    Date of revision:
    Handle: RePEc:ysm:somwrk:ysm373

    Contact details of provider:
    Web page:
    More information through EDIRC

    Related research

    Keywords: Shapley-Scarf Economy; Strict Core; Linear Inequality System; Extreme Points;

    Find related papers by JEL classification:

    This paper has been announced in the following NEP Reports:


    No references listed on IDEAS
    You can help add them by filling out this form.


    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as in new window

    Cited by:
    1. Alvin E. Roth & Tayfun Sönmez & M. Utku Ünver, 2005. "Efficient Kidney Exchange: Coincidence of Wants in a Structured Market," Boston College Working Papers in Economics 621, Boston College Department of Economics.
    2. Paula Jaramillo & Vikram Manjunath, 2011. "The Difference Indifference Makes in Strategy-Proof Allocation of Objects," DOCUMENTOS CEDE 008746, UNIVERSIDAD DE LOS ANDES-CEDE.
    3. Alcalde-Unzu, Jorge & Molis, Elena, 2011. "Exchange of indivisible goods and indifferences: The Top Trading Absorbing Sets mechanisms," Games and Economic Behavior, Elsevier, vol. 73(1), pages 1-16, September.
    4. Subiza, Begoña & Peris, Josep, 2013. "A Solution for General Exchange Markets with Indivisible Goods when Indifferences Are Allowed," QM&ET Working Papers 12-18, Universidad de Alicante, Departamento de Métodos Cuantitativos y Teoría Económica, revised 12 Feb 2014.


    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.


    Access and download statistics


    When requesting a correction, please mention this item's handle: RePEc:ysm:somwrk:ysm373. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: ().

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If references are entirely missing, you can add them using this form.

    If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.