This file is part of IDEAS, which uses RePEc data


[ Papers | Articles | Software | Books | Chapters | Authors | Institutions | JEL Classification | NEP reports | Search | New papers by email | Author registration | Rankings | Volunteers | FAQ | Blog | Help! ]

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

Author info | Abstract | Publisher info | Download info | Related research | Statistics
Author Info
Thomas Quint (University of Nevada, Reno)
Jun Wake (Gakashuin University)
Abstract

We consider the n-player houseswapping game of Shapley-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 multivalued. 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(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).

Download Info
To download:

If you experience problems downloading a file, check if you have the proper application to view it first. Information about this may be contained in the File-Format links below. 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: http://cowles.econ.yale.edu/P/cd/d14a/d1416.pdf
File Format: application/pdf
File Function:
Download Restriction: no

Publisher Info
Paper provided by Cowles Foundation, Yale University in its series Cowles Foundation Discussion Papers with number 1416.

Download reference. The following formats are available: HTML (with abstract), plain text (with abstract), BibTeX, RIS (EndNote, RefMan, ProCite), ReDIF
Length: 28 pages
Date of creation: May 2003
Date of revision:
Handle: RePEc:cwl:cwldpp:1416

Contact details of provider:
Postal: Yale University, Box 208281, New Haven, CT 06520-8281 USA
Phone: (203) 432-3702
Fax: (203) 432-6167
Web page: http://cowles.econ.yale.edu/
More information through EDIRC

Order Information:
Postal: Cowles Foundation, Yale University, Box 208281, New Haven, CT 06520-8281 USA

For technical questions regarding this item, or to correct its listing, contact: (Glena Ames).

Related research
Keywords: Shapley-Scarf economy; Strict core; Linear inequality system; Extreme points;

Find related papers by JEL classification:
C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games
C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
C60 - Mathematical and Quantitative Methods - - Mathematical Methods and Programming - - - General

This paper has been announced in the following NEP Reports:

References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
  1. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March. [Downloadable!] (restricted)
  2. Ma, Jinpeng, 1994. "Strategy-Proofness and the Strict Core in a Market with Indivisibilities," International Journal of Game Theory, Springer, vol. 23(1), pages 75-83.
  3. Wako, Jun, 1984. "A note on the strong core of a market with indivisible goods," Journal of Mathematical Economics, Elsevier, vol. 13(2), pages 189-194, October. [Downloadable!] (restricted)
  4. Roth, Alvin E. & Postlewaite, Andrew, 1977. "Weak versus strong domination in a market with indivisible goods," Journal of Mathematical Economics, Elsevier, vol. 4(2), pages 131-137, August. [Downloadable!] (restricted)
Full references

Statistics
Access and download statistics

Did you know? Each page is provided with a technical contact, in case something is not right with the supplied information. See under "publisher info".

This page was last updated on 2010-1-5.

This information is provided to you by IDEAS at the Department of Economics, College of Liberal Arts and Sciences, University of Connecticut using RePEc data on a server sponsored by the Society for Economic Dynamics.