论文标题
有效的近乎划分的能力限制
Efficient Nearly-Fair Division with Capacity Constraints
论文作者
论文摘要
我们考虑在容量限制下公平有效地分配不可分割的物品（商品或坏处）的问题。在这种情况下，我们将为我们提供一组分类项目。每个类别都有一个容量约束（所有代理商相同），这是代理可以从每个类别收到的项目数量上的上限。我们的主要结果是一种多项式时间算法，该算法解决了两个具有附加实用程序的代理的问题。当每个类别都包含所有商品（正面评估）或所有代理的所有杂务（负面评估）时，我们的算法发现这些项目的可行分配，这既是帕托托（Pareto）最佳和嫉妒的，最多是一个项目。在一般情况下，当每个项目都可以任意地做事或杂务时，我们的算法会发现帕累托（Pareto）最佳且嫉妒的分配最多可达一件好事和一个琐事。
We consider the problem of fairly and efficiently allocating indivisible items (goods or bads) under capacity constraints. In this setting, we are given a set of categorized items. Each category has a capacity constraint (the same for all agents), that is an upper bound on the number of items an agent can receive from each category. Our main result is a polynomial-time algorithm that solves the problem for two agents with additive utilities over the items. When each category contains items that are all goods (positively evaluated) or all chores (negatively evaluated) for each of the agents, our algorithm finds a feasible allocation of the items, which is both Pareto-optimal and envy-free up to one item. In the general case, when each item can be a good or a chore arbitrarily, our algorithm finds an allocation that is Pareto-optimal and envy-free up to one good and one chore.
