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

arXiv: https://arxiv.org/abs/2609.03846 · HTML: https://mlsanity.com/paper/2609.03846/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 31 references that are in the map.
- First posted on arXiv 3 Sep 2026.

## Builds on (most cited first, 16 of 16)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [Temporal Fair Division of Indivisible Items](https://mlsanity.com/paper/2410.14593/) (2024)
- [Finding Fair and Efficient Allocations](https://mlsanity.com/paper/1707.04731/) (2017)
- [Equitable Allocations of Indivisible Goods](https://mlsanity.com/paper/1905.10656/) (2019)
- [Online Fair Division with Additional Information](https://mlsanity.com/paper/2505.24503/) (2025)
- [Greedy Algorithms for Maximizing Nash Social Welfare](https://mlsanity.com/paper/1801.09046/) (2018)
- [Computing Welfare-Maximizing Fair Allocations of Indivisible Goods](https://mlsanity.com/paper/2012.03979/) (2020)
- [Approximability Landscape of Welfare Maximization within Fair Allocations](https://mlsanity.com/paper/2205.14296/) (2022)
- [APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items](https://mlsanity.com/paper/1507.01159/) (2015)
- [An Additive Approximation Scheme for the Nash Social Welfare Maximization with Identical Additive Valuations](https://mlsanity.com/paper/2201.01419/) (2022)
- [A Note on Approximating Weighted Nash Social Welfare with Additive Valuations](https://mlsanity.com/paper/2404.15607/) (2024)
- [Dividing Conflicting Items Fairly](https://mlsanity.com/paper/2506.14149/) (2025)
- [FAIRFORMER: A transformer architecture for discrete fair division](https://mlsanity.com/paper/2601.22346/) (2026)

## Abstract (arXiv)

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(varepsilon2) as varepsilon→ 0 for fixed n. We further consider the stronger sequential requirement that operatornameEF1 be maintained after every item assignment. For this setting, we introduce PriorityNet, a deep reinforcement learning framework trained with Proximal Policy Optimization (PPO) and equipped with prospective operatornameEF1 action masking, which guarantees prefix-wise operatornameEF1 by construction. Across 3,000 test instances in each of the offline full-information and random-order online regimes (n∈[2,20], m∈[5,100]), PriorityNet achieves mean normalized operatornameNSW values of 0.9911 and 0.9701, respectively. Relative to the offline Longest Processing Time (LPT) heuristic and the online least-valued-bundle rule, it attains instance-wise win-minus-loss rates of +27.10% and +17.87%. Its aggregate welfare matches the offline LPT baseline to four decimal places and modestly improves upon the online baseline, from 0.9694 to 0.9701.