研究少量多余物品时,公平分配如何影响福利最大化效率。
The Cost of EFX: Generalized-Mean Welfare and Complexity Dichotomies with Few Surplus Items
- 区分不同福利目标下,EFX分配的计算难易程度
- 当福利偏好非负时,优化面临指数级复杂度
- 适合关注公平与效率权衡的研究者阅读
公平分配不可分物品的中心概念之一是‘对任意物品无嫉妒’(EFX),但其存在性尚未在一般情形中解决。在物品数仅比人数多出少量(至多三个)的情况下,EFX分配保证存在,研究重点转向效率与计算问题。本文研究EFX与广义均值(p-均值)福利之间的关系,该类包含常用的总和(p=1)、纳什(p=0)及平等(p→-∞)目标。我们证明了在p=0处存在严格的复杂性分界:对任意固定的p∈(0,1],判断是否存在达到全局p-均值最优的EFX分配,以及计算最大化p-均值福利的EFX分配,均为NP-hard,即使仅有最多三个多余物品;相反,对任意固定的p≤0,我们给出了多项式时间算法,可在EFX分配空间内优化p-均值福利,并高效验证是否达到全局最优。进一步通过公平价格框架量化了强制执行EFX带来的福利损失:当p>0时,损失随人数线性增长;而当p≤0时,损失被依赖于多余物品数的常数所限制(对纳什福利,该损失在大样本下趋于零)。最后,我们证明同时要求帕累托最优与EFX是NP-hard的(更强变体下为Σ₂^P完全)。总体而言,我们的结果清晰刻画了在少量多余物品情形下,何时EFX计算成本高昂,何时与福利最大化结构相容。
原文摘要 · Abstract (English)
Envy-freeness up to any good (EFX) is a central fairness notion for allocating indivisible goods, yet its existence is unresolved in general. In the setting with few surplus items, where the number of goods exceeds the number of agents by a small constant (at most three), EFX allocations are guaranteed to exist, shifting the focus from existence to efficiency and computation. We study how EFX interacts with generalized-mean ($p$-mean) welfare, which subsumes commonly-studied utilitarian ($p=1$), Nash ($p=0$), and egalitarian ($p \rightarrow -\infty$) objectives. We establish sharp complexity dichotomies at $p=0$: for any fixed $p \in (0,1]$, both deciding whether EFX can attain the global $p$-mean optimum and computing an EFX allocation maximizing $p$-mean welfare are NP-hard, even with at most three surplus goods; in contrast, for any fixed $p \leq 0$, we give polynomial-time algorithms that optimize $p$-mean welfare within the space of EFX allocations and efficiently certify when EFX attains the global optimum. We further quantify the welfare loss of enforcing EFX via the price of fairness framework, showing that for $p > 0$, the loss can grow linearly with the number of agents, whereas for $p \leq 0$, it is bounded by a constant depending on the surplus (and for Nash welfare it vanishes asymptotically). Finally we show that requiring Pareto-optimality alongside EFX is NP-hard (and becomes $Σ_2^P$-complete for a stronger variant of EFX). Overall, our results delineate when EFX is computationally costly versus structurally aligned with welfare maximization in the setting with few surplus items.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。