Multi resource allocation with partial preferences
Multi resource allocation with partial preferences
复制标题
DOI：
10.1016/j.artint.2022.103824
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
Haibin Wang;Sujoy Sikdar;Xiaoxi Guo;Lirong Xia;Yongzhi Cao;Hanpin Wang
中科院分区：
文献类型：
--
作者：
Haibin Wang;Sujoy Sikdar;Xiaoxi Guo;Lirong Xia;Yongzhi Cao;Hanpin Wang
我们为多类型资源分配问题（MTRA）和多重分配问题提供高效、公平和不可操纵的机制，其中代理对由多个可分割项目组成的捆绑包有部分偏好。我们发现了从多重分配问题到 MTRA 的自然减少，这保留了 MTRA 机制的特性。我们将众所周知的随机优先级（RP）和概率串行（PS）机制扩展到具有部分偏好的多类型PS（MPS）和多类型RP（MRP）机制，并提出一种新的机制，多类型一般独裁（MGD），它结合了MPS和MRP的思想。我们表明，不幸的是，对于偏序偏好的不受限制的领域，没有任何机制能够同时满足 sd-efficiency 和 sd-envy-freeness，即使它们各自满足我们考虑的效率、公平性和不可操纵性的理想属性的不同较弱概念。尽管存在这种不可能的结果，但我们的主要信息是积极的：当代理的偏好由非循环CP网络表示时，MRP满足事后效率、sd-策略证明性和上不变性，而MPS满足sd-效率、sd-无嫉妒性、序数公平性和上不变性，恢复了RP和PS的属性； MGD 满足 sd 效率、平等对待以及在部分偏好不受限制的范围内的可分解性。我们引入了束网络偏好的自然域，它概括了先前研究的多重分配问题的部分偏好的域限制，并且与非循环 CP 网络的域不可比。我们表明，MRP 和 MPS 也满足捆绑网络偏好下 RP 和 PS 的所有属性。
We provide efficient, fair, and non-manipulable mechanisms for the multi-type resource allocation problems (MTRAs) and multiple assignment problems where agents have partial preferences over bundles consisting of multiple divisible items. We uncover a natural reduction from multiple assignment problems to MTRAs, which preserves the properties of MTRA mechanisms. We extend the well-known random priority (RP) and probabilistic serial (PS) mechanisms to MTRAs with partial preferences as multi-type PS (MPS) and multi-type RP (MRP) and propose a new mechanism, multi-type general dictatorship (MGD), which combines the ideas of MPS and MRP. We show that for the unrestricted domain of partial order preferences, unfortunately, no mechanism satisfies both sd-efficiency and sd-envy-freeness, even as they each satisfy different weaker notions of the desirable properties of efficiency, fairness, and non-manipulability we consider. Notwithstanding this impossibility result, our main message is positive: When agents' preferences are represented by acyclic CP-nets, MRP satisfies ex-post-efficiency, sd-strategyproofness, and upper invariance, while MPS satisfies sd-efficiency, sd-envy-freeness, ordinal fairness, and upper invariance, recovering the properties of RP and PS; the MGD satisfies sd-efficiency, equal treatment of equals, and decomposability under the unrestricted domain of partial preferences. We introduce a natural domain of bundle net preferences, which generalizes previously studied domain restrictions of partial preferences for multiple assignment problems and is incomparable to the domain of acyclic CP-nets. We show that MRP and MPS satisfy all properties of the RP and PS under bundle net preferences as well.