Random Assignment of Indivisible Goods under Constraints
Random Assignment of Indivisible Goods under Constraints
复制标题
DOI：
10.48550/arxiv.2208.07666
复制
发表时间：
2022-08
期刊：
影响因子：
--
通讯作者：
Yasushi Kawase;Hanna Sumita;Yu Yokoi
中科院分区：
文献类型：
--
作者：
Yasushi Kawase;Hanna Sumita;Yu Yokoi
研究了不可分物品的随机分配问题，其中每个代理人都有一个顺序偏好和一个约束条件。我们的目标是描述总是存在同时满足效率和无嫉妒的随机分配的条件。概率串行机制确保了无约束设置的这种分配的存在。在本文中，我们考虑一个更一般的设置，每个代理可以消费一组项目，只有当一组满足她的可行性约束。这样的限制必须考虑到学生的课程安排，员工轮班assignments，等等，我们证明了一个有效的和羡慕自由的分配可能不存在，即使是简单的情况下，分区拟阵约束，其中的项目进行分类，每个代理要求从每个类别的一个项目。然后，我们确定一个有效的和无羡慕的分配总是存在的特殊情况。对于这些情况下，概率序列不能自然扩展，因此，我们提供了使用各种方法来找到所需的分配机制。
We investigate the problem of random assignment of indivisible goods, in which each agent has an ordinal preference and a constraint. Our goal is to characterize the conditions under which there always exists a random assignment that simultaneously satisfies efficiency and envy-freeness. The probabilistic serial mechanism ensures the existence of such an assignment for the unconstrained setting. In this paper, we consider a more general setting in which each agent can consume a set of items only if the set satisfies her feasibility constraint. Such constraints must be taken into account in student course placements, employee shift assignments, and so on. We demonstrate that an efficient and envy-free assignment may not exist even for the simple case of partition matroid constraints, where the items are categorized, and each agent demands one item from each category. We then identify special cases in which an efficient and envy-free assignment always exists. For these cases, the probabilistic serial cannot be naturally extended; therefore, we provide mechanisms to find the desired assignment using various approaches.