论文标题
最大的纳什福利和其他有关EFX的故事
Maximum Nash Welfare and Other Stories About EFX
论文作者
论文摘要
我们考虑了具有添加估值功能的代理商中不可分割的商品的经典问题，并探索了两个突出的公平概念之间的联系：最大的NASH福利（MNW）和Envy-Creyeness与任何商品（EFX）之间的联系。我们确定，只要商品最多有两个可能的值，MNW的分配始终是EFX，而对于三个或更多不同的值，这种含义不再是正确的。值得注意的是，这证明了这些限制估值功能的EFX分配的存在。虽然对两个可能值的MNW分配的有效计算仍然是一个空旷的问题，但我们提出了一种新型算法，用于在这种情况下直接构建EFX分配。最后，我们研究了MNW分配是否意味着在近似EFX分配的自然新解释下，是否意味着对一般添加剂估值功能的任何EFX保证。
We consider the classic problem of fairly allocating indivisible goods among agents with additive valuation functions and explore the connection between two prominent fairness notions: maximum Nash welfare (MNW) and envy-freeness up to any good (EFX). We establish that an MNW allocation is always EFX as long as there are at most two possible values for the goods, whereas this implication is no longer true for three or more distinct values. As a notable consequence, this proves the existence of EFX allocations for these restricted valuation functions. While the efficient computation of an MNW allocation for two possible values remains an open problem, we present a novel algorithm for directly constructing EFX allocations in this setting. Finally, we study the question of whether an MNW allocation implies any EFX guarantee for general additive valuation functions under a natural new interpretation of approximate EFX allocations.
