EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments

📄 arXiv: 2609.03846v1 📥 PDF

作者: Zih-Sian Yang, Yi-Hao Chen, Yu-Te Kuan, Cheng-Jui Wu, Chuang-Chieh Lin, Po-An Chen

分类: cs.GT, cs.LG

发布日期: 2026-09-03

💡 一句话要点

提出PriorityNet以解决EF1约束下的Nash社会福利问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: Nash社会福利 深度强化学习 资源分配 无嫉妒性 算法优化 EF1约束 加性估值

📋 核心要点

  1. 现有方法在相同加性估值下，最大化Nash社会福利（NSW）面临NP难度，且EF1约束下的福利保证不足。
  2. 论文提出PriorityNet，利用深度强化学习和前瞻性EF1动作屏蔽，确保每次物品分配后保持EF1。
  3. 在3000个测试实例中，PriorityNet在离线和在线环境下的NSW值分别达到0.9911和0.9701，显著优于基线方法。

📝 摘要（中文）

本文研究了在相同加性估值下，如何在个体之间分配不可分割的物品，重点关注至多一件物品的无嫉妒性（EF1）和Nash社会福利（NSW）。由于每个最大NSW分配在加性估值下都是EF1，因此相关的阈值问题继承了NSW最大化的NP难度。我们关注任意EF1分配所满足的福利保证，发现特定条件下可以获得更强的保证。通过引入PriorityNet，一个基于深度强化学习的框架，本文在多个测试实例中展示了优越的NSW值，证明了该方法的有效性。

🔬 方法详解

问题定义：本文旨在解决在相同加性估值下，如何有效分配不可分割物品以最大化Nash社会福利（NSW），同时满足至多一件物品的无嫉妒性（EF1）。现有方法在满足这些条件时面临NP难度和福利保证不足的问题。

核心思路：论文提出了一种新的深度强化学习框架PriorityNet，通过前瞻性EF1动作屏蔽，确保在每次物品分配后都能保持EF1，从而提高NSW的近似值。

技术框架：PriorityNet的整体架构包括状态表示、动作选择和奖励机制三个主要模块。状态表示用于捕捉当前分配情况，动作选择模块通过强化学习算法生成符合EF1约束的分配决策，奖励机制则用于优化NSW值。

关键创新：PriorityNet的最大创新在于引入了前瞻性EF1动作屏蔽技术，确保在分配过程中实时维护EF1约束，避免了后处理修复的复杂性。这一设计使得分配过程更加高效和可靠。

关键设计：在PriorityNet中，采用了Proximal Policy Optimization（PPO）算法进行训练，损失函数设计为结合NSW和EF1约束的复合目标，网络结构则基于深度神经网络，能够处理复杂的状态空间和动作选择。

🖼️ 关键图片

fig_0
fig_1

📊 实验亮点

实验结果显示，PriorityNet在3000个测试实例中，离线和在线环境下的NSW值分别达到0.9911和0.9701，相较于基线方法，离线和在线的胜负差率分别提高了27.10%和17.87%。此外，在线平均福利从0.9694提升至0.9701，表现出显著的改进。

🎯 应用场景

该研究的潜在应用场景包括资源分配、市场交易和拍卖系统等领域，能够为公平和高效的资源分配提供理论支持和实践指导。通过优化Nash社会福利，能够提升社会整体福利水平，具有重要的实际价值和社会影响。

📄 摘要（原文）

We study the allocation of indivisible goods among agents with identical additive valuations, focusing on envy-freeness up to one good (EF1) and Nash social welfare (NSW). Since every maximum-NSW allocation is EF1 under additive valuations, the associated threshold problem inherits the known strong NP-hardness of NSW maximization under identical additive valuations and is strongly NP-complete. We therefore focus on welfare guarantees satisfied by arbitrary EF1 allocations. Although every such allocation is known to achieve an $e^{-1/e}$-approximation to the unrestricted optimal NSW, we identify conditions yielding stronger guarantees. Under uniform valuations, every EF1 allocation is NSW-optimal. Under an $\varepsilon$-small-item condition, every EF1 allocation achieves an explicit approximation ratio $ρ_n(\varepsilon)$ satisfying $ρ_n(\varepsilon) = 1-O(\varepsilon^2)$ as $\varepsilon\to 0$ for fixed $n$. We further consider the stronger sequential requirement that EF1 be maintained after every item assignment. For this setting, we propose \emph{PriorityNet}, a deep reinforcement learning framework trained using Proximal Policy Optimization and equipped with prospective EF1 action masking. The mask restricts every decision to assignments that preserve EF1, thereby guaranteeing prefix-wise EF1 by construction without post-processing repair. Across 3,000 test instances in each of the offline and random-order online regimes ($n\in[2,20]$ and $m\in[5,100]$), PriorityNet attains mean normalized $\operatorname{NSW}$ values of $0.9911$ and $0.9701$, respectively. Relative to offline Longest Processing Time (LPT) and online least-valued-bundle baselines, it achieves instance-wise win-minus-loss rates of $+27.10\%$ and $+17.87\%$, while matching the offline baseline's mean normalized welfare to four decimal places and modestly improving the online mean from $0.9694$ to $0.9701$.