Fair division is a classical topic studied in various disciplines and captures many real applications. One important issue in fair division is to cope with (economic) efficiency and fairness. A natural question along this direction that receives considerable attention is: How to obtain the most efficient allocations among all the fair allocations? In this paper, we study the complexity of maximizing social welfare within envy-free up to one item (EF1) allocations of indivisible goods for both normalized and unnormalized valuations. With two agents, we show a fully polynomial time approximation scheme (FPTAS) and complement this positive result with the NP-hardness result where the latter resolves an open problem raised by the previous work. Further, when the number of agents $n$ is a constant, we provide a bi-criteria algorithm that finds the optimal social welfare while relaxing EF1 by a factor arbitrarily close to 1. We complement this by providing several strong inapproximability results if EF1 is not allowed to relax. In particular, we demonstrate that the inapproximability becomes stronger as $n$ increases. Last, we consider the case with general number of agents. In this case, we give a variant of the round-robin algorithm with an approximation ratio of $1/n$ for unnormalized valuations and provide inapproximability results of $n^{1/3-\varepsilon}$ and $m^{1/2-\varepsilon}$ for normalized valuations. In addition, we show that our results of bi-criteria optimization for constant $n$ cannot be extended to the setting here, unless P=NP.
翻译:公平划分是一个在不同的学科中研究的经典主题,它包含了许多真正的应用。公平划分的一个重要问题是处理(经济)效率和公平。在这个方向上,一个自然的问题是:如何在所有公平分配中获得最高效的分配?在本文件中,我们研究了在无嫉妒、无嫉妒、最多只有一个项目(EF1)内为标准化和未正常化估值分配不可分割货物的复杂性。在两个代理商中,我们展示了一个完全的多元时间近似计划(FPTAS),并用后者解决先前工作产生的一个公开问题的硬性结果来补充这一积极结果。此外,当代理商数量为美元时,我们提供了一种双标准算法,找到最佳的社会福利,同时任意地将EF1放松到一个项目(EF1)内,如果EF1不允许放松,我们提供一些强大的不兼容性结果。特别是,我们证明不适应性作为美元上涨的结果会变得更强。最后,我们用普通的汇率来评估1美元/3美元比率,除非我们用普通的汇率来显示一个不变的汇率。