Compatibility of Fairness and Nash Welfare under Subadditive Valuations

我们在亚加性估值的广泛类别下建立了公平与效率之间的兼容性，通过 Nash Social Welfare (NSW) 来捕捉。我们证明，对于亚加性估值，总是存在一个部分分配，它是无嫉妒的（EFx），并且在最优解的至少一半处具有 NSW；这里，最优性是在所有分配中考虑的，无论是否公平。我们还证明了，对于亚加性估值，总是存在完全分配，它是无嫉妒的（EF1），并且也实现了最优 NSW 的 $1/2$ 近似。我们的 EF1 结果解决了 Garg 等人提出的一个开放问题（STOC 2023）。此外，我们开发了一个多项式时间算法，它以任意分配 \~A 作为输入，返回一个 NSW 至少为 \~A 的 $1/3$ 的 EF1 分配。因此，我们的结果意味着，在亚加性估值中，EF1 标准可以同时在多项式时间内（使用需求查询）达到对最优 NSW 的常数因子近似。以前已知的在 $n$ 个代理人中在 EF1 和最优 NSW 下的最佳近似因子是 $O(n)$，我们将这个界限提高到 $O(1)$。 已知 EF1 和完全 Pareto 效率（PO）与亚加性估值不兼容。与这一负面结果相对应，当前的工作表明，我们只需要考虑 $1/2$ 近似因子，就可以恢复兼容性：在亚加性估值下，EF1 可以与 $\frac{1}{2}$-PO 结合实现。因此，我们的结果是一个通用工具，可以将任何有效结果转换为公平结果，只需稍微降低效率。

解决问题：论文旨在解决公平性和效率之间的兼容性问题，针对亚加性估值，证明存在一种偏好分配方式满足EFx和至少达到最优NSW的一半；同时存在一种完全分配方式满足EF1并实现最优NSW的1/2近似。

关键思路：论文基于亚加性估值，提出了一种新的分配方式，能够在保证公平性的同时，实现高效的资源分配。通过证明存在一种偏好分配方式和完全分配方式，分别满足EFx和EF1的要求，并且能够实现接近最优NSW的近似解。

其他亮点：论文提出了一个多项式时间算法，可以在保证EF1的同时，实现NSW至少是原分配方式NSW的1/3。此外，论文还将EF1和$rac{1}{2}$-PO结合起来，实现了公平性和效率的平衡。这些结果为将任何有效结果转化为公平结果提供了一种通用工具。

相关研究：在这个领域中，最近的相关研究包括Garg等人的工作，他们提出了一个开放性问题，即是否存在一种分配方式，既满足EF1又实现最优NSW的1/2近似。