Geodesic
On the complexity of the Shapley-Scarf economy with several types of goods
Kybernetika, Tome 45 (2009) no. 5, pp. 689-700

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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.
Classification : 68Q17, 68Q25, 91A06, 91A12
Keywords: Shapley–Scarf economy; core; algorithm; NP-completeness 
@article{KYB_2009__45_5_a0,
     author = {Cechl\'arov\'a, Katar{\'\i}na},
     title = {On the complexity of the {Shapley-Scarf} economy with several types of goods},
     journal = {Kybernetika},
     pages = {689--700},
     publisher = {mathdoc},
     volume = {45},
     number = {5},
     year = {2009},
     mrnumber = {2599106},
     zbl = {1200.91027},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2009__45_5_a0/}
}
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
SP  - 689
EP  - 700
VL  - 45
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/KYB_2009__45_5_a0/
LA  - en
ID  - KYB_2009__45_5_a0
ER  - 
%0 Journal Article
%A Cechlárová, Katarína
%T On the complexity of the Shapley-Scarf economy with several types of goods
%J Kybernetika
%D 2009
%P 689-700
%V 45
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/KYB_2009__45_5_a0/
%G en
%F KYB_2009__45_5_a0
Cechlárová, Katarína. On the complexity of the Shapley-Scarf economy with several types of goods. Kybernetika, Tome 45 (2009) no. 5, pp. 689-700. http://geodesic.mathdoc.fr/item/KYB_2009__45_5_a0/