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

1 Introduction

• With identical additive valuations, agents assign the same value to each good and bundle values sum across goods, so maximizing NSW is a problem of balancing bundle values.Total utilitarian welfare is fixed across complete allocations in this setting.Source: §1 · p. 2

Theoretical Results

• The EF1-constrained NSW threshold problem is strongly NP-complete, because the optimal NSW allocation is EF1 and the problem inherits the hardness of unconstrained NSW maximization.The proof uses a direct reduction from 3-Partition.Source: Theoretical Results · p. 2, §1.2 · p. 4
• Every EF1 allocation is NSW-optimal under uniform valuations, while an explicit small-item approximation ratio approaches 1 as item values shrink relative to the average share.The small-item guarantee applies when each good is at most an ε-fraction of the average share; for fixed n, ρ_n(ε) = 1 − O(ε^2).Source: Theoretical Results · p. 2, §1.2 · p. 4
• Although online EF1 is not always guaranteed for additive valuations, an EF1 allocation exists at every time prefix when valuations are identical and additive.Source: Theoretical Results · p. 2
• Across 3,000 instances, PriorityNet achieves at least 99.8% and 97.0% of MaxNSW and win-minus-loss rates of +27.10% and +17.87% against offline and online LPT baselines, respectively.The experiments cover multi-scale instances with n ∈ [2, 20] and m ∈ [5, 100].Source: Experimental Results · p. 3

1.2 Related Work

• Unlike prior work centered on unconstrained NSW optimization, this paper studies guarantees for every EF1 allocation and complements learning-based methods that repair EF1 violations after assignment.The related-work discussion contrasts this focus with FairFormer’s post-processing repair step.Source: §1.2 · pp. 3–4

2 Preliminaries and Problem Specification

• EF1 requires that any envy toward another agent’s nonempty bundle can be eliminated by removing one good from that bundle.Source: §2 · p. 4
• For identical additive valuations, an EF1 allocation attaining maximum NSW exists, so imposing EF1 on the final allocation leaves the optimal objective value unchanged.The approximation question therefore concerns arbitrary EF1 allocations, not the best EF1 allocation.Source: §2 · p. 5
• The decision problem asks whether an EF1 allocation exists whose NSW reaches a given threshold T.Source: §2 · p. 5

2.1 Known Baseline Guarantee

• Every EF1 allocation under identical additive valuations achieves at least an e^-1/e fraction of optimal NSW.The passage gives e^-1/e ≈ 0.6922 as a constant-factor baseline.Source: §2.1 · p. 5

3.1 Equivalence and Known Computational Hardness

• EF1-Identical-NSW is strongly NP-complete because imposing final-allocation EF1 does not change the optimal NSW value.The hardness transfers from identical-additive NSW maximization, since every maximum-NSW allocation is EF1 under additive valuations.Source: §3.1 · p. 5

3.2 Special Case I: Uniform Identical Valuations

• Under uniform identical valuations, every EF1 allocation is NSW-optimal because EF1 forces bundle sizes to differ by at most one.With equal-valued goods, that cardinality balance maximizes the product of bundle values.Source: §3.2 · pp. 5–6

3.3 Special Case II: Small-Item Condition

• Under v* ≤ εµ, every EF1 allocation achieves at least max{e^-1/e, ρ_n(ε)} of optimal NSW, and for fixed n, ρ_n(ε) tends to 1 as ε tends to 0.The condition bounds each good's value by an ε-fraction of the average share.Source: §3.3 · p. 6

3.4 Positive and Negative Results on the Online EF1 Allocation

• Prefix-wise EF1 is impossible for irrevocable online allocation on general valuations, but the least-valued-bundle rule guarantees it for identical nonnegative valuations.The identical-valuation domain restores prefix-wise feasibility, leaving welfare maximization as a feasible objective.Source: §3.4 · p. 7
• For values 3, 3, 2, 2, 2 in fixed order, prefix-wise EF1 forces a final utility profile of (7, 5), with NSW √35 below the final-time optimum of 6.The example shows prospective EF1 constraints can exclude a final-time EF1-optimal allocation.Source: §3.4 · pp. 7–8

4.1 Problem Formulation & Allocation Protocol

• Offline allocation assumes the complete goods catalog and valuations are known a priori and goods are sorted by descending value; online allocation uses sequential random-order arrivals with zero future lookahead, under the same masked allocation mechanism.The online benchmark evaluates PriorityNet8k on 3,000 independent test instances across Small (n ∈[2, 5], m ∈[5, 20]), Medium (n ∈[6, 10], m ∈[20, 50]), and Large (n ∈[11, 20], m ∈[50, 100]) regimes.Source: Offline vs. Online Allocation Regimes · p. 8, Online Dynamic Streaming Benchmark · p. 12

4.2 State Representation & PriorityNet Architecture

• PriorityNet encodes agent states and item values in separate streams, then uses cross-attention and self-attention to produce masked priority logits and a value estimate.Offline item sequences use a CNN encoder, while online arriving-item values are projected directly; the actor supplies priorities and the critic estimates state value.Source: §4.2 · p. 9

4.3 Policy Optimization via Proximal Policy Optimization

• PPO optimizes choices within the prospective EF1-safe action set, whose nonemptiness under identical nonnegative additive valuations ensures every allocation prefix remains EF1.The clipped surrogate stabilizes updates, while the learned policy can select non-greedy welfare-oriented actions among feasible choices.Source: Rationale for Proximal Policy… · p. 9, Masked Categorical Policy & Action… · p. 9

4.4 Experimental Results & Comparative Analysis

• 0.9911 mean normalized NSW for both PriorityNet and Offline LPT across 3,000 offline instances; PriorityNet’s win-minus-loss rate is +27.10%.PriorityNet wins on 53.03% of instances, ties on 21.03%, and loses on 25.93%; it is competitive in aggregate rather than uniformly improving mean welfare.Source: Table 2 · p. 11, Offline Full-Information Benchmark · pp. 11–12
• Offline normalized NSW approaches 0.9983 as item values become finer relative to average share, while PriorityNet’s net win rate against Offline LPT stays positive for n ≥4.Fig. 2 reports net win rates reaching +20% to +30% at larger agent counts; the authors relate this trend to the small-item condition in Theorem 4.Source: Figure 2 · p. 12, Offline Full-Information Benchmark · p. 12
• 0.9701 mean normalized NSW for PriorityNet versus 0.9694 for the online LPT baseline across 3,000 online instances, with a +17.87% win-minus-loss rate.PriorityNet wins on 54.27% of instances, ties on 9.33%, and loses on 36.40%; the overall mean-welfare improvement is modest.Source: Table 3 · p. 13, Online Dynamic Streaming Benchmark · p. 13
• Fig. 3 reports the random-order streaming benchmark (W = 1, 60 seeds per cell), showing normalized NSW with 95% confidence intervals and PriorityNet’s win, loss, and net-win rates against Online LPT across n ∈ [2, 20].Source: Figure 3 · p. 14

5 Conclusion

• The EF1-constrained NSW threshold problem remains strongly NP-complete because every maximum-NSW allocation is EF1, so the paper focuses on guarantees for arbitrary EF1 allocations.Under uniform valuations every EF1 allocation is NSW-optimal; with ε-small items, the approximation ratio is max{e−1/e, ρ_n(ε)}, where ρ_n(ε) = 1 −O(ε^2) for fixed n.Source: §5 · p. 14
• 0.9911 overall mean normalized NSW for PriorityNet and LPT offline, with a +27.10% win-minus-loss rate; online, PriorityNet scored 0.9701 versus 0.9694 and a +17.87% win-minus-loss rate.The authors characterize aggregate mean-welfare differences as modest, despite PriorityNet winning on more tested instances.Source: §5 · p. 14
• PriorityNet uses prospective EF1 masking to guarantee prefix-wise EF1; offline it matches LPT’s overall mean, while online it modestly exceeds the least-valued-bundle baseline.The guarantee applies throughout the processed item order.Source: §5 · p. 14
• Future work includes asymmetric and submodular valuations, finite-lookahead streaming, and theoretical sample-complexity and generalization bounds for constrained fair-division policies.Source: §5 · p. 14

• The appendix gives the complete formulation of the prospective EF1 action mask.Source: A Masked Categorical Policy and PPO… · p. 16
• It also formulates the Categorical policy after masking.Source: A Masked Categorical Policy and PPO… · p. 16
• The formulation includes the likelihood-ratio computation used during PPO optimization.Source: A Masked Categorical Policy and PPO… · p. 16

• The current good’s prospectively EF1-feasible recipient set determines which agents may receive it.Source: §A.1 · p. 16
• The mask is applied to Actor logits, removing infeasible actions from the policy’s support before probability normalization.Source: §A.1 · p. 16
• Under identical nonnegative additive valuations, assigning the good to a minimum-valued bundle preserves EF1, and such a bundle always exists.Source: §A.1 · p. 16
• Starting from the trivially EF1 empty allocation and restricting each action to the feasible set preserves EF1 throughout the sequence; at least one action is always available.Source: §A.1 · p. 16

• Softmax over masked logits defines a constrained policy that assigns zero probability to every EF1-infeasible action.Source: §A.2 · p. 16
• During training, the recipient is sampled from the masked Categorical policy, exploring alternatives only among EF1-feasible recipients.Source: §A.2 · p. 17
• During deterministic evaluation and inference, selection uses the highest-priority feasible agent, equivalently the arg max over masked logits.Source: §A.2 · p. 17

A.3 Masked PPO Likelihood Ratio

• Reapplying each rollout’s state-dependent mask in PPO keeps the likelihood ratio normalized over the same EF1-feasible actions, so updates change preferences only among feasible recipients.The unconstrained Actor may assign different total probability mass to infeasible actions under the behavior and updated policies, making its likelihood ratio inappropriate for the constrained policy.Source: §A.3 · p. 17

B.1 Generalized Advantage Estimation

• GAE-λ estimates advantages by combining temporal-difference residuals across future steps, with λ controlling the bias–variance trade-off between shorter and longer horizons.The terminal bootstrap value is set to zero; smaller λ emphasizes short-horizon bootstrapped estimates.Source: §B.1 · p. 18

B.2 Advantage Normalization

• Advantages are standardized within each mini-batch for the policy objective, while unnormalized advantages remain the Critic’s regression targets.A 10^-8 constant is included for numerical stability.Source: §B.2 · p. 18

B.3 Clipped PPO Surrogate Objective

• The clipped PPO surrogate uses the masked likelihood ratio, and the complete Actor–Critic objective adds Critic regression and entropy regularization.The entropy term encourages exploration among EF1-feasible actions.Source: §B.3 · p. 18

B.4 Optimization Details.

• PPO updates use shuffled mini-batches across multiple epochs, reusing rollout data and applying Adam after computing policy, value, and entropy terms.The learning rate and other optimization settings are reported in Table 5.Source: §B.4 · p. 19

Bounded utility spread

• In any EF1 allocation with identical additive valuations, the largest and smallest bundle values differ by at most the largest good’s value.For any pair of bundles, EF1 guarantees one can remove a good from the envied bundle whose value is at most the largest good’s value.Source: C Lemmas and Their Proofs · p. 19

Product lower bound

• The product lower bound minimizes across possible counts k of upper-endpoint coordinates, since the extremal product need not have only one poor bundle.The resulting bound applies to positive bundle values with fixed sum and spread at most D.Source: C Lemmas and Their Proofs · pp. 19–20
• For a fixed sum and bounded spread, a product-minimizing vector can be chosen with all coordinates at one of the two endpoints.If two coordinates are interior, shifting them apart decreases their product; concavity then permits eliminating any remaining interior coordinate.Source: C Lemmas and Their Proofs · pp. 19–20

NP-membership

• An allocation is a polynomial-size certificate, and validity and EF1 can be checked in polynomial time from bundle values and each bundle’s largest good.Under identical additive valuations, EF1 checking reduces to comparing each bundle value with another bundle’s value after subtracting its largest good.Source: D A Self-Contained Proof of Theorem 2 · pp. 20–21
• The NSW threshold can also be checked in polynomial time using integer arithmetic, so the EF1-Identical-NSW decision problem belongs to NP.The product of bundle values and the threshold raised to the number of agents have polynomially many bits.Source: D A Self-Contained Proof of Theorem 2 · p. 21

NP-hardness reduction

• The reduction maps 3-Partition numbers to goods with identical additive values, uses q agents, and sets the NSW threshold to B.A valid triple partition yields equal-valued bundles, making the allocation envy-free, EF1, and at the threshold.Source: D A Self-Contained Proof of Theorem 2 · p. 21
• Conversely, meeting the threshold forces equality in AM-GM, and the item-size bounds then force exactly three goods per bundle, yielding a 3-Partition solution.Thus the decision problem is strongly NP-complete, and its optimization version is strongly NP-hard.Source: D A Self-Contained Proof of Theorem 2 · p. 21

Small-item guarantee

• Every EF1 allocation has bundle-value spread at most v* ≤ εµ, so the bounded-spread product estimate applies with D = εµ.Here, µ is the mean bundle value and v* is the largest item value.Source: E Proof of Theorem 4 · p. 21
• Taking the n-th root of the product bound gives NSW(A) ≥ µρ_n(ε) for every EF1 allocation.The proof obtains the product estimate by applying the bounded-spread lemma with D = εµ.Source: E Proof of Theorem 4 · p. 21
• The final guarantee takes the maximum of the small-item lower bound and the unrestricted bound because both hold simultaneously.The supplied proof identifies this maximum as the combined lower bound.Source: E Proof of Theorem 4 · p. 21

F State Representation & PriorityNet Architecture, and Hyperparameter Configuration

• Table 4 presents the engineered observation features.Source: Table 4 · p. 22
• Together, the tables cover observation features and training hyperparameters.Source: Table 4 · p. 22, Table 5 · p. 22
• Table 5 presents the hyperparameter configuration for PriorityNet training.Source: Table 5 · p. 22