On Houseswapping, the Strict Core, Segmentation, and Linear Programming
AbstractWe 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 InfoIf 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.
Bibliographic InfoPaper provided by Yale School of Management in its series Yale School of Management Working Papers with number ysm373.
Date of creation: 28 Jul 2004
Date of revision:
Shapley-Scarf Economy; Strict Core; Linear Inequality System; Extreme Points;
Find related papers by JEL classification:
- C60 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - General
- C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
- C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games
This paper has been announced in the following NEP Reports:
- NEP-ALL-2004-07-18 (All new papers)
You can help add them by filling out this form.
CitEc Project, subscribe to its RSS feed for this item.
- 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.
- Alvin E Roth & Tayfun Sönmez & M. Utku Ünver, 2005. "Efficient Kidney Exchange: Coincidence of Wants in a Structured Market," Levine's Bibliography 784828000000000126, UCLA Department of Economics.
- M.Utku Unver, 2005. "Efficient Kidney Exchange: Coincidence of Wants in a Structured Market," Working Papers 263, University of Pittsburgh, Department of Economics, revised Jan 2005.
- Alvin E. Roth & Tayfun Sonmez & M. Utku Unver, 2005. "Efficient Kidney Exchange: Coincidence of Wants in a Structured Market," NBER Working Papers 11402, National Bureau of Economic Research, Inc.
- Alvn E. Roth & Tayfun Sonmez & M. Utku Unver, 2005. "Efficient Kidney Exchange: Coincidence of Wants in a Structured Market," Microeconomics 0506001, EconWPA, revised 01 Jun 2005.
- ALCALDE-UNZU, Jorge & MOLIS, Elena, 2009.
"Exchange of indivisible goods and indifferences: the Top Trading Absorbing Sets mechanisms,"
CORE Discussion Papers
2009062, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
- 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.
- Subiza, Begoña & Peris, Josep, 2013. "A Pareto Efficient Solution for General Exchange Markets with Indivisible Goods," QM&ET Working Papers 12-18, Universidad de Alicante, Departamento de Métodos Cuantitativos y Teoría Económica.
- Paula Jaramillo & Vikram Manjunath, 2011.
"The Difference Indifference Makes in Strategy-Proof Allocation of Objects,"
008746, UNIVERSIDAD DE LOS ANDES-CEDE.
- Jaramillo, Paula & Manjunath, Vikram, 2012. "The difference indifference makes in strategy-proof allocation of objects," Journal of Economic Theory, Elsevier, vol. 147(5), pages 1913-1946.
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.