论文标题
计算福利最大化不可分割商品的公平分配
Computing Welfare-Maximizing Fair Allocations of Indivisible Goods
论文作者
论文摘要
我们分析了公平和最大化功利主义社会福利的计算分配的运行时间复杂性，该福利定义为代理商的实用程序之和。我们专注于两个可行的公平概念：嫉妒性最高一项（EF1）和比例，最多可达一项（Prop1）。我们考虑了两个计算问题：（1）在功利主义最大的分配中，决定是否存在一个也是公平的； （2）在公平的分配中，计算一种最大化功利主义福利的分配。我们表明，当代理数量变化时，这两个问题都是强烈的NP - hard，并且对于大于两个的固定数量的固定代理，仍然保持NP-HARD。对于两种代理的特殊情况，我们发现问题（1）是多项式时间可溶剂的，而问题（2）仍然是np-hard。最后，有了固定数量的代理，我们为这两个问题设计了伪时间算法。我们将结果扩展到更强大的公平概念羡慕的概念，直至任何项目（EFX）和与任何项目（Propx）的比例。
We analyze the run-time complexity of computing allocations that are both fair and maximize the utilitarian social welfare, defined as the sum of agents' utilities. We focus on two tractable fairness concepts: envy-freeness up to one item (EF1) and proportionality up to one item (PROP1). We consider two computational problems: (1) Among the utilitarian-maximal allocations, decide whether there exists one that is also fair; (2) among the fair allocations, compute one that maximizes the utilitarian welfare. We show that both problems are strongly NP-hard when the number of agents is variable, and remain NP-hard for a fixed number of agents greater than two. For the special case of two agents, we find that problem (1) is polynomial-time solvable, while problem (2) remains NP-hard. Finally, with a fixed number of agents, we design pseudopolynomial-time algorithms for both problems. We extend our results to the stronger fairness notions envy-freeness up to any item (EFx) and proportionality up to any item (PROPx).
