Mechanism Design for Multi-Type Housing Markets
Mechanism Design for Multi-Type Housing Markets
复制标题
DOI：
10.1609/aaai.v31i1.10601
复制
发表时间：
2016-11
期刊：
影响因子：
--
通讯作者：
Sujoy Sikdar;Sibel Adali;Lirong Xia
中科院分区：
文献类型：
--
作者：
Sujoy Sikdar;Sibel Adali;Lirong Xia
我们研究了多类型住房市场，其中有p ≥ 2种类型的物品，每个代理人最初被赋予每种类型的一个物品，目标是设计没有货币转移的机制，根据代理人对捆绑物品的偏好将物品（重新）分配给代理人，使得每个代理人获得每种类型的一个物品。与经典住房市场形成鲜明对比的是，以往对多类型住房市场的研究一直受到缺乏自然解概念的阻碍，因为严格的核心可能是空的。我们通过利用人工智能技术并对代理人的偏好进行自然假设来打破文献中的障碍。我们发现，当代理人的偏好是字典式的，即使有不同的重要性顺序，经典的顶部交易周期机制可以扩展，同时保持其大部分的好属性。我们还调查了计算复杂性检查是否分配是在严格的核心，并检查严格的核心是否为空。我们的研究结果传达了一个积极的信息：在自然偏好假设下，为多类型住房市场设计良好的机制是可能的。
We study multi-type housing markets, where there are p ≥ 2 types of items, each agent is initially endowed one item of each type, and the goal is to design mechanisms without monetary transfer to (re)allocate items to the agents based on their preferences over bundles of items, such that each agent gets one item of each type. In sharp contrast to classical housing markets, previous studies in multi-type housing markets have been hindered by the lack of natural solution concepts, because the strict core might be empty. We break the barrier in the literature by leveraging AI techniques and making natural assumptions on agents’ preferences. We show that when agents’ preferences are lexicographic, even with different importance orders, the classical top-trading-cycles mechanism can be extended while preserving most of its nice properties. We also investigate computational complexity of checking whether an allocation is in the strict core and checking whether the strict core is empty. Our results convey an encouragingly positive message: it is possible to design good mechanisms for multi-type housing markets under natural assumptions on preferences.