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 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.
- 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.
- 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.
- 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.
- 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).
- 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.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: ().
If references are entirely missing, you can add them using this form.