×

zbMATH — the first resource for mathematics

On the complexity of the Shapley-Scarf economy with several types of goods. (English) Zbl 1200.91027
Summary: 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 \geq 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.

MSC:
91A12 Cooperative games
91A06 \(n\)-person games, \(n>2\)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
91B54 Special types of economic markets (including Cournot, Bertrand)
PDF BibTeX XML Cite
Full Text: Link
References:
[1] A. Abdulkadiroglu, P. Pathak, A. Roth, and T. Sönmez: The Boston public school match. Amer. Econom. Rev. 95 (2005), 2, 368-371.
[2] D. Abraham, K. Cechlárová, D. Manlove, and K. Mehlhorn: Pareto optimality in house allocation problems. Algorithms and Computation (R. Fleischer and G. Trippen, Lecture Notes in Comput. Sci. 3827). Springer-Verlag, Berlin 2005, pp. 1163-1175. · Zbl 1115.90049
[3] P. Berman, M. Karpinski, and A. D. Scott: Approximation Hardness of Short Symmetric Instances of MAX-3SAT. Electronic Colloquiumon Computational Complexity, Report No. 49, 2003.
[4] S. Fekete, M. Skutella, and G. Woeginger: The complexity of economic equilibria for house allocation markets. Inform. Process. Lett. 88 (2003), 5, 219-223. · Zbl 1165.91433 · doi:10.1016/j.ipl.2003.08.008
[5] M. R. Garey and D. S. Johnson: Computers and Intractability. Freeman, San Francisco 1979.
[6] H. Konishi, T. Quint, and J. Wako: On the Shapley-Scarf economy: the case of multiple types of indivisible goods. J. Math. Econom. 35 (2001), 1-15. · Zbl 1007.91036 · doi:10.1016/S0304-4068(00)00061-6
[7] A. Roth and M. A. O. Sotomayor: Two-sided matching: a study in game-theoretic modeling and analysis. (Econometric Society Monographs 18.) Cambridge University Press, Cambridge 1990. · Zbl 0726.90003
[8] A. Roth, T. Sönmez, and U. Ünver: Kidney exchange. Quarterly J. Econom. 199 (2004), 457-488. · Zbl 1064.92029 · doi:10.1162/0033553041382157
[9] H. Scarf: The core of an \(N\)-person game. Econometrica 35 (1967), 50-69. · Zbl 0183.24003 · doi:10.2307/1909383
[10] L. Shapley and H. Scarf: On cores and indivisibility. J. Math. Econom. 1 (1974), 23-37. · Zbl 0281.90014 · doi:10.1016/0304-4068(74)90033-0
[11] Y. Yuan: Residence exchange wanted: A stable residence exchange problem. European J. Oper. Res. 90 (1996), 536-546. · Zbl 0907.90199 · doi:10.1016/0377-2217(94)00358-0
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.