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

Abstract

-cross Abstract: 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 $\rho_n(\varepsilon)$ satisfying $\rho_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$.

Authors 6

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

Specification

Official page: arxiv.org/abs/2609.03846
Source:arXiv (Atom API + RSS)T1observed 6 h agohigh
Arxiv announce type: replace
Source:arXiv (Atom API + RSS)T1observed 6 h agohigh
arXiv id: 2609.03846
Source:arXiv (Atom API + RSS)T1observed 6 h agohigh
Categories: cs.GT, cs.LG
Source:arXiv (Atom API + RSS)T1observed 6 h agohigh
PDF: arxiv.org/pdf/2609.03846
Source:arXiv (Atom API + RSS)T1observed 6 h agohigh
Primary category: cs.GT
Source:arXiv (Atom API + RSS)T1observed 6 h agohigh
Published: 11 Sept 2026
Source:arXiv (Atom API + RSS)T1observed 6 h agohigh

Each value shows its source, tier and observation time. Conflicting claims are kept side by side and flagged — never averaged. How AI Atlas records facts →

Provenance

Attributed facts

9

Source tiers

T19

Freshest observation

6 h ago

Conflicts

None

No models linked to this paper yet.

Authors: Zih-Sian Yang, Yi-Hao Chen, Yu-Te Kuan

As of

Rewind the record: see this entity's attributes exactly as AI Atlas knew them on a given day.

Claim history · Categories

1 claims · 1 propertiesShow all properties

Categoriescategories1

Claim history for Categories
Value	Valid from → to	Status	Source	Confidence	Extractor
cs.GT, cs.LG	11 Sept 2026 21:02 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

Claims are temporal and append-only: a new observation closes the previous claim (valid_to) instead of overwriting it. Conflicting claims from different sources are kept side by side and flagged — never averaged. Methodology →

11 Sept 2026
New paperPaperEF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments
New paper: EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments
arxiv
rss.arxiv.org

Full timeline →

Source documents
Source	Document	Type	Tier	Last observed	Snapshots
arXiv (Atom API + RSS)	rss.arxiv.org/rss/cs.LG	feed	T1· Official	4 h ago	1

Tier 1 = official/primary, 2 = quality secondary, 3 = community, 4 = unverified. Every snapshot is archived; see all sources and the methodology.