A Complexity Approach for Core-Selecting Exchange with Multiple Indivisible Goods under Lexicographic Preferences
A Complexity Approach for Core-Selecting Exchange with Multiple Indivisible Goods under Lexicographic Preferences
复制标题
DOI：
10.1609/aaai.v29i1.9318
复制
发表时间：
2015-01
期刊：
影响因子：
--
通讯作者：
Etsushi Fujita;Julien Lesca;Akihisa Sonoda;Taiki Todo;M. Yokoo
中科院分区：
文献类型：
--
作者：
Etsushi Fujita;Julien Lesca;Akihisa Sonoda;Taiki Todo;M. Yokoo
核心选择是社会选择文献中社会选择函数或规则的一个重要属性。还需要解决代理人通过误报其偏好进行欺骗的动机。本文研究了一个交换问题，其中每个代理人可以有多个不可分割的商品，代理人的偏好集的商品被假定为字典序，并不允许边支付。我们提出了一个交换规则称为增广顶部交易周期（ATTC）程序的基础上，原来的TTC程序。我们首先表明，ATTC程序是核心选择。然后，我们发现，在ATTC程序下找到一个有益的误报是NP难的。在ATTC程序下，我们最终澄清了偏好误报和分裂之间的关系，这是一种不同类型的操纵。
Core-selection is a crucial property of social choice functions, or rules, in social choice literature. It is also desirable to address the incentive of agents to cheat by misreporting their preferences. This paper investigates an exchange problem where each agent may have multiple indivisible goods, agents' preferences over sets of goods are assumed to be lexicographic, and side payments are not allowed. We propose an exchange rule called augmented top-trading-cycles (ATTC) procedure based on the original TTC procedure. We first show that the ATTC procedure is core-selecting. We then show that finding a beneficial misreport under the ATTC procedure is NP-hard. Under the ATTC procedure, we finally clarify the relationship between preference misreport and splitting, which is a different type of manipulation.