On the Complexity of the Shapley-Scarf Economy with Several Types of Goods
On the Complexity of the Shapley-Scarf Economy with Several Types of Goods
复制标题
论多类商品的沙普利-围巾经济的复杂性
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
K. Cechlárová
中科院分区：
文献类型：
--
作者：
K. Cechlárová
在沙普利-斯卡夫经济中，每个行为人都被赋予一个不可分割的商品（房屋）单位，并希望将其交换为另一个单位，可能是市场上房屋中最受欢迎的一个。在这种经济中，核心总是非空的，可以通过著名的Top Trading Cycles算法找到核心分配。最近，引入了对这种经济的修改，包含Q ≥ 2种商品（例如，Q = 2的房屋和汽车）。我们表明，如果代理的数量是2，一个完整的描述的核心，可以有效地找到。然而，当代理商的数量不受限制时，在两种商品的情况下，决定核心的非空性的问题已经成为NP-难的。我们还表明，即使是问题，以决定是否存在一个分配，每个代理人严格改善相比，他的禀赋，是NP完全的。
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.