On the complexity of the Shapley-Scarf economy with several types of goods

Katarína Cechlárová

Kybernetika (2009)

  • Volume: 45, Issue: 5, page 689-700
  • ISSN: 0023-5954

Abstract

top
In the Shapley-Scarf economy each agent is endowed with one unit of an indivisible good (house) and wants to exchange it for another, possibly the most preferred one among the houses in the market. In this economy, core is always nonempty and a core allocation can be found by the famous Top Trading Cycles algorithm. Recently, a modification of this economy, containing Q >= 2 types of goods (say, houses and cars for Q=2) has been introduced. We show that if the number of agents is 2, a complete description of the core can be found efficiently. However, when the number of agents is not restricted, the problem to decide the nonemptyness of the core becomes NP-hard already in the case of two types of goods. We also show that even the problem to decide whether an allocation exists in which each agent strictly improves compared to his endowment, is NP-complete.

How to cite

top

Cechlárová, Katarína. "On the complexity of the Shapley-Scarf economy with several types of goods." Kybernetika 45.5 (2009): 689-700. <http://eudml.org/doc/37696>.

@article{Cechlárová2009,
abstract = {In the Shapley-Scarf economy each agent is endowed with one unit of an indivisible good (house) and wants to exchange it for another, possibly the most preferred one among the houses in the market. In this economy, core is always nonempty and a core allocation can be found by the famous Top Trading Cycles algorithm. Recently, a modification of this economy, containing Q >= 2 types of goods (say, houses and cars for Q=2) has been introduced. We show that if the number of agents is 2, a complete description of the core can be found efficiently. However, when the number of agents is not restricted, the problem to decide the nonemptyness of the core becomes NP-hard already in the case of two types of goods. We also show that even the problem to decide whether an allocation exists in which each agent strictly improves compared to his endowment, is NP-complete.},
author = {Cechlárová, Katarína},
journal = {Kybernetika},
keywords = {Shapley–Scarf economy; core; algorithm; NP-completeness; NP-completeness; core; Shapley-Scarf economy; algorithm},
language = {eng},
number = {5},
pages = {689-700},
publisher = {Institute of Information Theory and Automation AS CR},
title = {On the complexity of the Shapley-Scarf economy with several types of goods},
url = {http://eudml.org/doc/37696},
volume = {45},
year = {2009},
}

TY - JOUR
AU - Cechlárová, Katarína
TI - On the complexity of the Shapley-Scarf economy with several types of goods
JO - Kybernetika
PY - 2009
PB - Institute of Information Theory and Automation AS CR
VL - 45
IS - 5
SP - 689
EP - 700
AB - In the Shapley-Scarf economy each agent is endowed with one unit of an indivisible good (house) and wants to exchange it for another, possibly the most preferred one among the houses in the market. In this economy, core is always nonempty and a core allocation can be found by the famous Top Trading Cycles algorithm. Recently, a modification of this economy, containing Q >= 2 types of goods (say, houses and cars for Q=2) has been introduced. We show that if the number of agents is 2, a complete description of the core can be found efficiently. However, when the number of agents is not restricted, the problem to decide the nonemptyness of the core becomes NP-hard already in the case of two types of goods. We also show that even the problem to decide whether an allocation exists in which each agent strictly improves compared to his endowment, is NP-complete.
LA - eng
KW - Shapley–Scarf economy; core; algorithm; NP-completeness; NP-completeness; core; Shapley-Scarf economy; algorithm
UR - http://eudml.org/doc/37696
ER -

References

top
  1. The Boston public school match, Amer. Econom. Rev. 95 (2005), 2, 368–371. 
  2. Pareto optimality in house allocation problems, In: Algorithms and Computation (R. Fleischer and G. Trippen, eds., Lecture Notes in Comput. Sci. 3827). Springer–Verlag, Berlin 2005, pp. 1163–1175. MR2258195
  3. Approximation Hardness of Short Symmetric Instances of MAX-3SAT, Electronic Colloquiumon Computational Complexity, Report No. 49, 2003. 
  4. The complexity of economic equilibria for house allocation markets, Inform. Process. Lett. 88 (2003), 5, 219–223. MR2014318
  5. Computers and Intractability, Freeman, San Francisco 1979. MR0519066
  6. On the Shapley–Scarf economy: the case of multiple types of indivisible goods, J. Math. Econom. 35 (2001), 1–15. MR1817786
  7. Two-sided matching: a study in game-theoretic modeling and analysis, (Econometric Society Monographs 18.) Cambridge University Press, Cambridge 1990. MR1119308
  8. Kidney exchange, Quarterly J. Econom. 199 (2004), 457–488. 
  9. The core of an N -person game, Econometrica 35 (1967), 50–69. Zbl0183.24003MR0234735
  10. On cores and indivisibility, J. Math. Econom. 1 (1974), 23–37. MR0416531
  11. Residence exchange wanted: A stable residence exchange problem, European J. Oper. Res. 90 (1996), 536–546. Zbl0907.90199

NotesEmbed ?

top

You must be logged in to post comments.