Full entry |
PDF
(0.9 MB)
Feedback

Shapley–Scarf economy; core; algorithm; NP-completeness

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**. In: Algorithms and Computation (R. Fleischer and G. Trippen, eds., Lecture Notes in Comput. Sci. 3827). Springer–Verlag, Berlin 2005, pp. 1163–1175. MR 2258195

[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. MR 2014318

[5] M. R. Garey and D. S. Johnson: **Computers and Intractability**. Freeman, San Francisco 1979. MR 0519066

[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. MR 1817786

[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. MR 1119308

[8] A. Roth, T. Sönmez, and U. Ünver: **Kidney exchange**. Quarterly J. Econom. 199 (2004), 457–488.

[9] H. Scarf: **The core of an $N$-person game**. Econometrica 35 (1967), 50–69. MR 0234735 | Zbl 0183.24003

[10] L. Shapley and H. Scarf: **On cores and indivisibility**. J. Math. Econom. 1 (1974), 23–37. MR 0416531

[11] Y. Yuan: **Residence exchange wanted: A stable residence exchange problem**. European J. Oper. Res. 90 (1996), 536–546. Zbl 0907.90199