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

EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments⋆ Zih-Sian Yang1† , Yi-Hao Chen1† , Yu-Te Kuan1 , Cheng-Jui Wu1 , Chuang-Chieh Lin1†* , and Po-An Chen2* National Taiwan Ocean University, Keelung City 202301, Taiwan {01257049,01357144,01257109,josephcclin,01057139}@mail.ntou.edu.tw 2 National Yang Ming Chiao Tung University, Hsinchu City 300, Taiwan poanchen@nycu.edu.tw

arXiv:2609.03846v1 [cs.GT] 3 Sep 2026

1

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 maximumNSW 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 NPcomplete. 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 ε-small-item condition, every EF1 allocation achieves an explicit approximation ratio ρn (ϵ) satisfying ρn (ε) = 1 − O(ε2 ) as ε → 0 for fixed n. We further consider the stronger sequential requirement that EF1 be maintained after every item assignment. For this setting, we propose 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 ∈ [2, 20] and m ∈ [5, 100]), PriorityNet attains mean normalized 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. Keywords: Fairness · Envy-freeness up to one good (EF1) · Nash social welfare · Deep reinforcement learning · Prospective action masking · Online streaming

1

Introduction

Fair allocation of indivisible goods is a central problem in artificial intelligence, computational social choice, and multiagent resource allocation. In this problem, a set of indivisible goods must be allocated among agents with possibly different preferences over bundles of goods. Since exact envy-freeness may fail to exist even in very simple indivisible-goods instances, much of the modern literature focuses on relaxations of envy-freeness and on welfare objectives that balance efficiency and fairness. One particularly influential objective is the Nash social welfare (NSW), defined as the geometric mean of the agents’ utilities. Originating from Nash’s bargaining solution [18], NSW has become a canonical objective in fair division because it interpolates between utilitarian welfare and egalitarian welfare. It rewards efficiency while strongly penalizing allocations in which some agents receive very low utility. For an allocation
1/n Qn A = (A1 , A2 , . . . , An ), the NSW is NSW(A) = . When the valuations are additive and the i=1 vi (Ai ) goods are indivisible, maximizing NSW is computationally challenging. It is NP-hard and even APX-hard in general [15, 20]. Nevertheless, the objective has received substantial attention due to its strong fairness and efficiency properties. In this paper, we study NSW maximization under the fairness constraint of envy-freeness up to one good (EF1). EF1 is one of the most widely used relaxations of envy-freeness for indivisible goods. An allocation is EF1 if, for every pair of agents i and j, any envy of agent i toward agent j can be eliminated by removing one good from j’s bundle. EF1 allocations are guaranteed to exist and can be computed efficiently under broad valuation classes [16]. The relationship between EF1 and NSW is also well known: maximum Nash welfare ⋆

The full version of this work with full appendix is available at arXiv:xxxx.xxxxx. † The authors contributed equally. * Corresponding authors.

allocations are EF1 and Pareto optimal for additive valuations [6]. Moreover, Barman, Krishnamurthy, and Vaish showed that, for identical additive valuations, every EF1 allocation gives an e−1/e -approximation to the optimal NSW [2]. We focus on the special but important case in which all agents have identical additive valuations. In this setting, every agent assigns the same value v(g) to each good g, and the value of a bundle is the sum of the values of its goods. This restriction captures resource-allocation problems in which the goods have a common objective quality or utility, and the main issue is to divide the goods as evenly as possible. In contrast with the case of general additive valuations, the total utilitarian welfare is fixed across all complete allocations. Thus, maximizing NSW becomes a balancing problem. That is, one seeks a partition of the goods whose bundle values are as equal as possible. Our goal is to understand the interaction between EF1 and NSW in this identical additive setting. We consider the following EF1-constrained NSW decision problem: given an identical additive valuation instance and a threshold T , decide whether there exists an EF1 allocation A such that NSW(A) ≥ T . We also study structural approximation guarantees: for an arbitrary EF1 allocation A, how close must NSW(A) be to the optimal NSW? The contributions of this paper are as follows.

1.1

Our Contributions

Theoretical Results Offline Setting. First, we note that EF1-constrained NSW maximization is strongly NP-complete even under identical additive valuations. The proof, which can be rediscovered in [6, 13], is by a direct reduction from 3-Partition. The reduction exploits the fact that an allocation with NSW equal to the average share must have perfectly equal bundle values. Such an allocation is automatically envy-free, and hence EF1. We include a direct proof in the full version for completeness. Second, we revisit the known e−1/e approximation guarantee for EF1 allocations under identical additive valuations. This guarantee shows that EF1 alone already provides a constant-factor approximation to the unconstrained optimal NSW. We then identify natural conditions under which this guarantee can be improved. Third, we show that if the identical valuation is uniform, then every EF1 allocation is exactly NSW-optimal. This provides a simple but useful benchmark: when all goods have the same value, EF1 forces the bundle cardinalities to be as balanced as possible, which maximizes the geometric mean. Finally, we prove an improved approximation guarantee under a small-item condition. Let V = v(M ), µ = Vn , ∆ = maxg∈M v(g). If each good has value at most an ε-fraction of the average share, i.e., ∆ ≤ εµ, then EF1 implies that all bundle values differ by at most ∆. This bounded-spread property yields an explicit NSW approximation ratio that tends to 1 as ε → 0. Thus, in large-market instances where individual goods are small relative to the average share, EF1 allocations are nearly NSW-optimal. The theoretical results in the offline setting are summarized in Table 1.

Setting

Guarantee or Complexity

Comment

Identical additive valuations Uniform identical valuations Identical valuations with ε-small-item condition Exact EF1-constrained NSW

e -approximation optimal (1-approximation) ρn (ε)-approximation, ρn (ε) → 1 as ε→0 Strongly NP-complete

[2] this work this work

−1/e

Inherited from [6, 13]

Table 1. Theoretical results on EF1-constrained NSW maximization in the offline setting.

Online Setting. We first show that the online allocation of indivisible goods does not always have the EF1 guarantee even for agents with additive valuations, by providing an illustrating counterexample. Aside from the impossibility result, we show that there always exists an EF1 allocation at any time prefix interval when agents have identical additive valuations. This further motivates our investigation on NSW maximization under the EF1 constraint for agents with identical additive valuations. 2

Experimental Results To translate our theoretical guarantees into scalable algorithms, we propose PriorityNet, a deep reinforcement learning framework trained via PPO equipped with prospective EF1 action masking. Under identical additive valuations, fair division shares a natural structural equivalence with multiprocessor scheduling: assigning incoming items to the agent with the lowest accumulated utility mirrors Graham’s classical Longest Processing Time (LPT) heuristic [11]. In the fair division literature, this greedy principle corresponds to the 1.061-NSW approximation algorithm Alg_Identical in the offline setting [3] and the least-valued-bundle rule in the online streaming setting (Theorem 5; see also [8, 19]). With a slight abuse of terminology, we call the LPT heuristic and the least-valued-bundle rule online and offline LPT rules, respectively, for simplicity. We evaluate PriorityNet against these canonical offline and online LPT benchmarks across 3,000 multi-scale instances (n ∈ [2, 20], m ∈ [5, 100]), demonstrating that PriorityNet achieves near-continuous optimal welfare (≥ 99.8% and ≥ 97.0% of MaxNSW). PriorityNet also achieves instance-wise win-minus rates of +27.10% and +17.87% with respect to offline and online LPT benchmarks, respectively. 1.2

Related Work

Nash social welfare and indivisible goods. The Nash social welfare objective originates from Nash’s bargaining solution [18] and has since become a fundamental welfare criterion in fair division and multiagent resource allocation. For divisible resources, NSW is closely connected to market equilibrium and convex programming formulations. For indivisible goods, however, NSW maximization becomes algorithmically difficult. Nguyen and Rothe studied the allocation of indivisible goods with additive utilities and considered, among other objectives, the maximization of average Nash social welfare [20]. They showed that the problem is computationally challenging and gave approximation algorithms, including a PTAS for the case of identical additive valuations. Lee later proved that maximizing NSW with indivisible goods and additive utilities is APX-hard [15], thereby ruling out a polynomial-time approximation scheme for the general additive case unless P = NP. A major algorithmic breakthrough was obtained by Cole and Gkatzelis, who gave the first constant-factor approximation algorithm for NSW maximization with indivisible goods and additive valuations [7]. Subsequent work improved and generalized this line of research using techniques from Fisher markets, matching, local search, and configuration linear programs. Barman, Krishnamurthy, and Vaish gave a combinatorial approach that obtains a 1.45-approximation and also produces fair and efficient allocations [2]. More recently, Feng and Li obtained an (e1/e + ε)-approximation for the weighted NSW problem with additive valuations [9]. Their analysis explicitly uses the worst-case gap between the optimal NSW and the NSW of an EF1 allocation in identical additive instances. Identical additive valuations. The identical additive valuation setting is a natural special case in which all agents agree on the value of each good. Although this setting is more structured than the general additive case, the problem remains nontrivial: the goal is to partition the goods into bundles whose total values are as balanced as possible. Barman, Krishnamurthy, and Vaish studied simple greedy algorithms for special valuation classes and showed that, for identical additive valuations, a greedy algorithm that processes goods in decreasing order of value and assigns each good to a currently least-valued agent gives a 1.061-approximation to the optimal NSW [3]. They also observed that NSW maximization remains NP-hard even under identical valuations. Inoue and Kobayashi later gave an additive approximation scheme for identical additive valuations, achieving an additive error of εvmax , where vmax is the maximum value of a good [13]. Our work is complementary to this literature. Prior work on identical additive valuations primarily studies unconstrained NSW maximization. In contrast, we focus on the EF1-constrained problem and on approximation guarantees that hold for every EF1 allocation, not only for the output of a particular algorithm. EF1 and maximum Nash welfare. EF1 was introduced as an algorithmically tractable relaxation of envyfreeness for indivisible goods [16]. It has become a standard fairness notion because EF1 allocations exist under very general conditions, whereas exact envy-free allocations may not exist. A fundamental connection between EF1 and NSW was established by Caragiannis et al., who showed that every maximum Nash welfare allocation for additive valuations is EF1 and Pareto optimal [6]. This result explains why NSW is not only an efficiency objective but also a fairness-promoting rule. Barman, Krishnamurthy, and Vaish strengthened this connection algorithmically by developing methods for finding allocations that are EF1 and Pareto optimal, and by proving approximation guarantees for NSW [2]. Of particular relevance to our paper is their result that, under identical additive valuations, every EF1 allocation is an e−1/e -approximation to the optimal NSW. This guarantee serves as the baseline for our approximation 3

results. We show that the guarantee can be improved to exact optimality under uniform identical valuations and can be strengthened under a small-item condition. Welfare maximization subject to fairness constraints. Another related line of work studies the complexity of maximizing welfare subject to fairness constraints. Aziz, Huang, Mattei, and Segal-Halevi studied the problem of computing allocations that are both fair and utilitarian-welfare maximizing, focusing on EF1 and PROP1 constraints [1]. They showed strong NP-hardness results for several variants. Bu et al. studied the complexity and approximability of maximizing social welfare within EFX and EF1 allocations [5]. These works are conceptually close to ours because they investigate welfare optimization over fair allocations. However, they focus primarily on utilitarian social welfare and broader valuation models. Our paper instead studies the Nash social welfare objective under EF1, with emphasis on identical additive valuations, where the utilitarian objective is fixed and the geometric-mean objective captures balance among agents. Learning-based approaches for fair division. Most algorithmic work on NSW maximization and fair division is based on combinatorial algorithms, market-based methods, local search, or linear-programming relaxations. Recently, learning-based approaches have also been proposed for fair allocation of indivisible goods. Mascioli, Goyal, and Chakraborty introduced FairFormer, a transformer architecture for discrete fair division under additive subjective valuations [17]. Their model is an amortized, permutation-equivariant two-tower transformer that encodes agents and goods as unordered token sets, applies self-attention within each set, and uses itemto-agent cross-attention to output assignment distributions. Their method discretizes the assignment and applies a lightweight repair routine to remove violations of EF1 while attempting to preserve or improve Nash welfare. This learning-based line of work is closely related to the experimental component of our paper. Mascioli et al.’s FairFormer [17] is primarily an amortized neural optimization method for general additive subjective valuations. Their approach enforces EF1 through a post-processing repair step after discretization, whereas our experimental component examines whether a transformer-inspired [23] model can directly produce allocations with competitive NSW approximation ratios, without additional repair procedures. Thus, FairFormer provides an important recent benchmark and motivation for the learning-based part of our study, while our results complement it by giving problem-specific complexity and approximation analyses for the identical-valuation EF1-constrained setting. Positioning of this paper. The present paper lies at the intersection of EF1 fairness, Nash social welfare maximization, and identical additive valuations. On the theoretical side, we first observe that the final-time EF1 constraint is nonbinding: the best EF1 allocation has the same NSW as the unrestricted optimum. Hence, the constrained decision problem inherits the known strong NP-completeness of identical-additive NSW maximization. We include a direct proof in the full version for completeness. Our contribution concerns not the best EF1 allocation, but every EF1 allocation. We show that uniform identical valuations imply exact NSW optimality and derive an explicit small-item approximation ratio ρn (ϵ) satisfying ρn (ϵ) = 1 − O(ϵ2 ). On the experimental side, motivated by recent neural approaches such as FairFormer [17], we investigate transformer-inspired reinforcement learning methods for producing high-NSW allocations in this structured fair division setting.

2

Preliminaries and Problem Specification

Let N = {1, 2, . . . , n} be a set of agents and let M be a finite set of indivisible goods. We assume that M each agent P i ∈ N has an additive valuation function vi : 2 → R≥0 , such that for any subset S ⊆ M , vi (S) = g∈S vi (g). When v1 (g) = v2 (g) = . . . = vn (g) := v(g) for each good g ∈ M , we say that the agents have identical valuation functions. An allocation is a partition A = (A1 , A2 , . . . , An ) of M , where Ai is the bundle assigned to agent i. The Nash social welfare of an allocation A is the geometric mean of the values of agents’ bundles, that is, !1/n n Y NSW(A) = vi (Ai ) . i=1

For multiplicative approximation statements we focus on instances for which the optimal NSW is positive. Otherwise, the ratio would be degenerate. Definition 1 (EF1). An allocation A = (A1 , A2 , . . . , An ) is envy-free up to one good (EF1) if for every pair of agents i, j ∈ N with Aj ̸= ∅, there exists a good g ∈ Aj such that vi (Ai ) ≥ vi (Aj \ {g}). 4

The main approximation question considered here is the following. Approximation question. For an EF1 allocation A, how large can we guarantee the ratio NSW(A)/ NSW(A∗ ) to be, where A∗ is an allocation maximizing NSW among all allocations? By the result of Caragiannis et al. [6], an NSW-maximizing allocation is EF1 whenever the optimal NSW is positive. Therefore, maxA is EF1 NSW(A) = maxA NSW(A). Thus, requiring EF1 only for the final allocation does not change the optimal objective value. Our approximation question concerns the welfare guaranteed by an arbitrary EF1 allocation, rather than the welfare of the best EF1 allocation. We specifically consider the following exact decision problem. Definition 2 (EF1-Identical-NSW). The input consists of a set M of goods, a number n of agents, a nonnegative integer value w Pg for each good g ∈ M , and an integer threshold T . All agents have the identical additive valuation v(S) = g∈S wg for any S ⊆ M . The question is whether there exists an EF1 allocation A = (A1 , A2 , . . . , An ) such that NSW(A)Q ≥ T . Equivalently, since the values are integral, this asks whether n there exists an EF1 allocation satisfying i=1 v(Ai ) ≥ T n . Remark. By the preceding observation, EF1-Identical-NSW is equivalent, in terms of its optimal objective value, to ordinary NSW maximization under identical additive valuations. Consequently, its computational hardness is inherited from the corresponding unconstrained problem; the EF1 requirement does not introduce an additional restriction at an optimum. 2.1

Known Baseline Guarantee

A result of Barman, Krishnamurthy, and Vaish [2], as quoted by Feng and Li [9], gives the following baseline. Theorem 1 (Barman–Krishnamurthy–Vaish [2]). For the unweighted Nash social welfare problem with identical additive valuations, every EF1 allocation is an e1/e -approximate solution. Equivalently, if A is EF1 and A∗ maximizes NSW, then NSW(A) ≥ e−1/e NSW(A∗ ). Clearly, Theorem 1 implies that EF1 alone already provides a nontrivial constant-factor approximation to optimal NSW, where the approximation ratio is e−1/e ≈ 0.6922. In the subsequent sections, we investigate how this guarantee can be improved both theoretically and experimentally.

3

Theoretical Results: Hardness and Optimization

3.1

Equivalence and Known Computational Hardness

We first note that exact EF1-constrained NSW maximization is computationally hard even under identical additive valuations. The proof is direct and uses 3-Partition, which is strongly NP-complete [10]. Theorem 2 (Strong NP-completeness). EF1-Identical-NSW is strongly NP-complete. Proof (Sketch). Membership in NP follows because an allocation is a polynomial-size certificate, and its EF1 property and Nash product can be verified using polynomial-time integer arithmetic. For hardness, identical-additive NSW maximization is already known to be strongly NP-hard via a reduction from 3-Partition [13]. Moreover, every maximum-NSW allocation is EF1 under additive valuations [6]. Therefore, imposing EF1 on the final allocation does not change the optimal value, and the known strong hardness transfers directly to EF1-Identical-NSW. ⊔ ⊓ For completeness, Appendix D provides a direct self-contained reduction from 3-Partition. 3.2

Special Case I: Uniform Identical Valuations

We first consider the case in which all goods have the same value. Definition 3 (Uniform identical valuation). The identical additive valuation is uniform if there exists a constant c > 0 such that v(g) = c for every g ∈ M . Without loss of generality, one may normalize c = 1. Theorem 3 (Exact optimality under uniform valuations). Assume uniform identical valuations. Then every EF1 allocation is NSW-optimal. Hence every EF1 allocation is a 1-approximation to the optimal NSW. 5

Proof. Normalize v(g) = Q 1 for every good g. For an allocation A, let us write xi = |Ai | = v(Ai ). The NSW n objective is NSW(A) = ( i=1 xi )1/n . If A is EF1, then for every pair i, j with Aj ̸= ∅, there exists g ∈ Aj such that |Ai | ≥ |Aj \ {g}| = |Aj | − 1. Therefore |Aj | − |Ai | ≤ 1 whenever Aj ̸= ∅. Note that if Aj = ∅, the inequality is immediate. Hence all bundle sizes differ by at one. Pmost n Now consider any integer vector (x1 , x2 , . . . , xn ) with i=1 xi = m. If there exist a, b ∈ {1, 2, . . . , n} with xa ≥ xb + 2, then replacing (xa , xb ) by (xa − 1, xQ b + 1) strictly increases the product. Indeed, (xa − 1)(xb + n 1) − xa xb = xa − xb − 1 > 0. Thus the product i=1 xi is maximized exactly when all xi differ by at most one. Since every EF1 allocation has this property, every EF1 allocation maximizes the product and therefore maximizes NSW. ⊔ ⊓ Remark 1. This result is stronger than the e−1/e baseline, but it relies on a restrictive valuation class. For completely homogeneous goods, EF1 already enforces the bundle cardinalities that maximize NSW. 3.3

Special Case II: Small-Item Condition

The uniform case is very special. A more flexible condition is that no single good is too large compared with the average share. Define V = v(M ), µ = Vn , v ∗ = maxg∈M v(g). Here µ is the average total value per agent, and v ∗ is the largest item value. Definition 4 (Small-item condition). For ε ∈ [0, 1], an identical additive instance satisfies the ε-small-item condition if v ∗ ≤ εµ. Equivalently, every individual good is worth at most an ε-fraction of mu. This condition is natural in large-market settings: as goods become individually negligible relative to the average share, EF1 forces the realized bundle values to become nearly balanced. Let us define "  n−k  k #1/n kε (n − k)ε ρn (ε) = min 1− 1+ . 1≤k≤n−1 n n For ε ∈ [0, 1], all factors are positive. Theorem 4 (Improved NSW guarantee under small items). Assume identical additive valuations and the ε-small-item condition v ∗ ≤ εµ for ε ∈ [0, 1]. Then every EF1 allocation A satisfies NSW(A)/ NSW(A∗ ) ≥ max{e−1/e , ρn (ε)}, where A∗ is an NSW-optimal allocation. ⊓ ⊔

Proof. Refer to Appendix E for the proof in the full paper.

Remark 2 (Asymptotics). For fixed n, we can show that ρn (ε) → 1 as ε → 0. Expanding the logarithm of the kth term by Taylor expansion gives " n−k  k # 1 kε (n − k)ε k(n − k) 2 log 1 − 1+ =− ε + O(ε3 ). n n n 2n2 2

2 The worst second-order term is obtained by maximizing k(n − k), so ρn (ε) = 1 − ⌊n2n/4⌋ + O(ε3 ) ≥ 2 ε 1 − 18 ε2 − O(ε3 ) → 1 as ε → 0.

3.4

Positive and Negative Results on the Online EF1 Allocation

Consider a set N of agents and a sequence of indivisible goods g1 , g2 , . . . arriving online. When gt arrives, its values (vi (gt ))i∈N are revealed and the good must be allocated immediately and irrevocably. Let At = (At1 , At2 , . . . , Atn ) denote the accumulated allocation after the first t arrivals. Recall that At is envy-free up to one good (EF1) if, for every pair i, j ∈ N with Atj ̸= ∅, there exists g ∈ Atj such that vi (Ati ) ≥ vi (Atj \ {g}). An online allocation sequence (At )Tt=1 is prefix-wise EF1 if At is EF1 for every t ∈ {1, 2, . . . , T }. The impossibility of maintaining exact fairness under irrevocable online allocation is well established. Benadè et al. [4, Theorem 2.13] show that, even when every single-good value lies in [0, 1], an adversary can force the maximum pairwise envy to grow polynomially with the horizon. Since an EF1 allocation with single-good values bounded by 1 has pairwise envy at most 1, their lower bound already rules out a general EF1 guarantee. More directly, He et al. [12, Theorem 3.3] study the requirement that EF1 hold after every round and prove that any uninformed online EF1 algorithm requires at least ⌊T /6⌋ reallocations in the worst case, even with two agents. In particular, an irrevocable algorithm, which permits zero reallocations, cannot guarantee prefix-wise EF1. We give below a short self-contained counterexample tailored to deterministic irrevocable algorithms. 6

Proposition 1 (Impossibility of prefix-wise EF1 for general additive valuations). For general nonnegative additive valuations, no deterministic irrevocable online allocation algorithm can guarantee that the accumulated allocation At is EF1 after every arriving good gt . Proof. It suffices to consider two agents. Fix any constant K > 1, and let A be an arbitrary deterministic irrevocable online algorithm. We construct an adversarial input for A. The first arriving good g1 has v1 (g1 ) = v2 (g1 ) = 1. Since A is deterministic, it assigns g1 to one of the two agents. WLOG, rename the recipient agent 1 and the other agent 2. Hence, A11 = {g1 }, A12 = ∅. 1 The second good g2 has values v1 (g2 ) = K, v2 (g2 ) = K . If A assigns g2 to agent 1, then A21 = {g1 , g2 } 2 and A2 = ∅. From agent 2’s perspective, deleting either one good from A21 leaves strictly positive value, 1 that is, v2 (A21 \ {g1 }) = K > 0 = v2 (A22 ) and v2 (A21 \ {g2 }) = 1 > 0 = v2 (A22 ). Thus A2 would not be EF1. Consequently, any algorithm that preserves EF1 after the second arrival is forced to assign g2 to agent 2, so A21 = {g1 }, A22 = {g2 }. Now let a third good g3 arrive with v1 (g3 ) = v2 (g3 ) = K. There are only two possible irrevocable assignments. If g3 is given to agent 1, then agent 2 has value 1/K, whereas deleting either good from agent 1’s 1 1 bundle leaves value strictly larger than 1/K, that is, v2 ({g3 }) = K > K , v2 ({g1 }) = 1 > K . Hence EF1 fails for the ordered pair (2, 1). If instead g3 is given to agent 2, then agent 1 has value 1, while deleting either good from A32 = {g2 , g3 } leaves value K > 1 according to agent 1. That is, v1 ({g2 }) = K > 1, v1 ({g3 }) = K > 1. Hence EF1 fails for the ordered pair (1, 2). Therefore no assignment of g3 preserves EF1, contradicting the claimed guarantee of A. Since A was arbitrary, no deterministic irrevocable online algorithm can guarantee prefix-wise EF1 for the full class of additive valuations. ⊔ ⊓ For identical valuations the situation changes. Suppose all agents share the same nonnegative additive valuation v. Consider the least-valued-bundle rule: when gt arrives, we choose r ∈ arg mini∈N v(At−1 ) and i assign gt to agent r. The following result is also covered by a stronger result of Elkind et al. [8, Theorem 3.7]. They prove temporal EF1 (TEF1), i.e., EF1 at every prefix, for the more general class of generalized binary (restricted additive) valuations. Their greedy algorithm for goods assigns each positively valued arriving good to an interested agent whose current bundle has minimum value (see Algorithm 3 in their full version). Under identical nonnegative valuations, every positive-valued good is valued by every agent, so their rule specializes exactly to the least-valued-bundle rule below. Theorem 5 (Prefix-wise EF1 under identical additive valuations). If all agents have the same nonnegative additive valuation v, then the least-valued-bundle rule maintains EF1 after every arriving good. Proof. We proceed by induction on t. All bundles are empty initially, so EF1 holds. Assume that At−1 is EF1, and let r ∈ arg mini∈N v(At−1 ) receive the newly arriving good gt . Thus Atr = At−1 ∪ {gt }, Ati = At−1 (i = ̸ r). r i i Note that only agent r’s bundle changes. Hence, for every ordered pair (i, j) with j = ̸ r, the EF1 witness from time t − 1 remains valid. Indeed, if i = ̸ r, neither relevant bundle changes, while if i = r, the value of i’s own bundle can only increase. It remains to consider possible new envy toward agent r. Fix any i = ̸ r. Since r had a least-valued bundle t−1 immediately before the arrival of gt , we obtain that v(At−1 ). Agent i’s bundle is unchanged, and r ) ≤ v(Ai removing the newly assigned good from agent r’s bundle restores the old bundle. Therefore, v(Ati ) = v(At−1 )≥ i t v(At−1 r ) = v(Ar \ {gt }). Thus gt itself is an EF1 witness for every possible new envy toward r. Consequently At is EF1. By induction, the allocation is EF1 after every arrival. ⊓ ⊔ Remark 3. In an online Nash-social-welfare formulation with a prefix-wise EF1 constraint, Proposition 1 shows that feasibility already fails on the unrestricted additive domain. Theorem 5 identifies the identical-value domain as a natural setting in which prefix-wise EF1 feasibility is restored, leaving welfare maximization as a feasible algorithmic objective. Final-time EF1 versus prefix-wise EF1. The requirement of maintaining EF1 after every assignment can be strictly stronger than requiring EF1 only for the final allocation. To illustrate this distinction, consider two agents with identical additive valuations and five goods processed in descending order, with values 3, 3, 2, 2, 2. The final allocation (A1 , A2 ) = ({3, 3}, {2, 2, 2}) gives utility profile (6, 6) and therefore attains the optimal Nash social welfare NSW(A) = 6. In particular, it is envy-free and hence EF1. However, reaching this allocation requires assigning the first two value-3 goods to the same agent. Immediately afterward, the partial allocation would be ({3, 3}, ∅), which violates EF1 because removing either value-3 good from the first bundle still leaves value 3 > 0 for the empty-bundle agent. Consequently, any policy maintaining prefix-wise EF1 under this fixed order must assign the first two goods to different agents. Each agent then holds one value-3 7

good, and the√most balanced possible distribution of the three remaining value-2 goods yields utilities (7, 5), √ with NSW = 7 · 5 = 35 < 6. Thus, prospective EF1 action masking may exclude a final-time EF1-optimal allocation, showing that prefix-wise EF1 maximization and final-time EF1 maximization are generally different optimization problems.

4

Reinforcement Learning Optimization via PPO PriorityNet

Having studied welfare guarantees for final EF1 allocations, we now consider a different and stronger sequential problem. Given a fixed item order, the allocation must remain EF1 after every assignment. We introduce PriorityNet, which is a reinforcement learning architecture trained via Proximal Policy Optimization (PPO) [22], for solving this prefix-wise EF1 problem. Note that it does not in general optimize over all final-time EF1 allocations. PriorityNet parameterizes dynamic priority fields over agents to guide sequential allocations toward maximum welfare. To ensure strict fairness, we integrate a prospective EF1 action mask directly into the policy: at every decision step, actions that would violate the EF1 invariant are strictly filtered, guaranteeing exactly prefix-wise EF1 by construction without heuristic post-processing. This section presents the formal MDP formulation, the modular neural architecture, the PPO policy optimization pipeline, and extensive empirical benchmarks across offline and online streaming regimes. 4.1

Problem Formulation & Allocation Protocol

Constrained Sequential Allocation as an MDP. We formulate fair sequential allocation as a finitehorizon Constrained Markov Decision Process (S, A, M, P, R). At step t ∈ {1, 2, . . . , m}, exactly one good gt is allocated: t−1 t−1 – State st ∈ S: Encodes the current partial allocation (At−1 1 , A2 , . . . , An ), agent utility state features n×11 Ft ∈ [0, 1] , and visible item valuations. – Action Space & EF1 Mask A = {1, 2, . . . , n}: The recipient agent at ∈ A. The prospective EF1 mask Mt ∈ {0, 1}n restricts decisions to the feasible set Afeas = {i ∈ A | At−1 ∪ {(i, gt )} is EF1}. t – Policy Decision: The Actor network outputs continuous priority logits ℓt ∈ Rn . The allocated recipient is selected via at = arg maxi∈Afeas ℓt,i during deterministic evaluation. t – State Transition P: The chosen agent receives gt (Atat = At−1 at ∪ {gt }), and the environment advances to gt+1 .

Offline vs. Online Allocation Regimes. We evaluate PriorityNet under two canonical information regimes sharing the identical sequential masked allocation mechanism: (a) Offline Full-Information Regime: The complete goods catalog and valuations are known a priori. Goods are pre-sorted in descending value order (v(g1 ) ≥ v(g2 ) ≥ · · · ≥ v(gm )), and unallocated goods are dynamically tracked via global attention. (b) Online Dynamic Streaming Regime: Goods arrive sequentially under the Random-Order Arrival Model (window W = 1) with zero future lookahead. Each arriving good must be irrevocably allocated upon arrival. Nash Social Welfare Objective and Continuous Optimal Ceiling. For n P agents with final accumulated Qn n utilities u = (u1 , u2 , . . . , un ), we obtain NSW(u) = ( i=1 ui )1/n = exp( n1 i=1 ln ui ). To ensure scaleinvariant rewards across varying market dimensions, utility geometric means are normalized by the continuous AM–GM upper bound ceiling (referred to as the continuous optimal ceiling MaxNSW). That is, MaxNSW = Pm NSW(u) 1 g=1 maxi=1,2,...,n vi,g , and define Rnorm = MaxNSW as the normalized NSW. Crucially, this full-instance n ceiling is computed strictly post-hoc upon allocation termination (i.e., t = m) for external benchmarking and terminal reward normalization; it is never accessible to the online policy during sequential decision-making. Valuation Generators and Curriculum Training Setup. Each problem instance generates a valuation matrix V ∈ {1, 2, . . . , 100}n×m . Under identical additive valuations (vi,g = v1,g for all i), item values are drawn from five representative generator classes: (1) Uniform, (2) Gaussian N (µ, σ 2 ), (3) Bimodal Beta Mixture (high variance), (4) Heavy-Tailed Exponential / Skewed (dominant star items), and (5) Flat (low variance). During training, market dimensions (n, m) are sampled dynamically across n ∈ [2, 20] and m ∈ [3, 40]. Batches consist of B = 64 parallel environment workers running up to a trajectory horizon length of T = 32 steps. Hyperparameters are detailed in Appendix Table 5. 8

4.2

State Representation & PriorityNet Architecture

At each decision step t, the environment constructs an 11-dimensional normalized state feature matrix F ∈ [0, 1]n×11 for the active agents (formally defined in Table 4 in the Appendix). In the offline setting, the full sequence of unallocated goods is visible and processed in descending value order. In the online sequential setting, goods arrive one at a time, so only the currently arriving good gt is visible (Wt = {gt }) while future goods remain unrevealed. All item valuations are normalized by 100.0 (matching the valuation support v ∈ [1, 100]), avoiding future-value leakage. Agent cumulative utilities and envy gaps are normalized relative to max(Utmax , 1.0) where Utmax = maxi∈N ui . Crucially, the running normalized welfare is computed causally P \ = NSWcur / max(MaxNSWt , 10−8 ), where MaxNSWt = 1 as NSW g∈Ht v(g) is evaluated strictly over the n revealed history Ht = {g1 , g2 , . . . , gt } (Ht = M in the offline setting), ensuring a strict zero-lookahead online policy. Agent utility ranks, utility shares, One-Hot last-selected indicators I(i = at−1 ), and idle starvation counters are tracked dynamically across steps. As illustrated in Fig. 1, PriorityNet processes agent and item state information through four interconnected neural modules: (1) 1D Convolutional Goods Encoder : In the offline setting with a catalog of unallocated goods, a two-layer 1D CNN (Conv1D(1 → 128 → 64, k = 3)) extracts latent representations from the (masked) item valuation sequence, aggregated via masked mean pooling into a global item embedding egoods ∈ R64 . In the online setting where goods arrive strictly one at a time under identical valuations, sequence-level spatial convolution is unnecessary; omitting the CNN encoder streamlines the architecture, directly encodes the arriving item valuation into F, and substantially accelerates policy training convergence. (2) Cross-Attention Layer : A Pre-LayerNorm Multi-Head Cross-Attention block (4 heads) [23] projects concatenated agent state features and item embeddings [F, egoods ] to dimension 128, enabling agent Queries to attend dynamically to item Keys/Values. (3) Agent Self-Attention Layer : A Pre-LayerNorm Multi-Head Self-Attention block (4 heads) captures interagent utility relations and envy dependencies. (4) Dual Output Heads: An Actor head computes agent priority logits ℓt ∈ Rn , which are filtered through the EF1 action mask to determine the winning agent, while a Critic head estimates the state value V (s) ∈ R. 4.3

Policy Optimization via Proximal Policy Optimization

Rationale for Proximal Policy Optimization. We use an EF1 action mask to ensure that every selected allocation remains EF1 throughout the allocation process. The mask restricts the policy to prospectively EF1-safe agents, reducing the feasible action space to fairness-preserving choices while still leaving multiple valid decisions at many states. PPO is then used to optimize the policy within this constrained action space. Its clipped surrogate objective stabilizes policy updates, preventing outlier high-reward trajectories from inducing destructively large policy shifts. This allows the model to systematically discover non-greedy, welfare-maximizing sequential allocations while preserving the EF1 feasibility guaranteed by action masking. Masked Categorical Policy & Action Sampling. At each allocation step t ∈ {1, 2, . . . , m}, the Actor produces priority logits ℓt ∈ Rn . Before sampling an action, we apply a prospective EF1 mask that removes any agent whose selection would violate EF1 after assigning the current good. The policy therefore operates only over the feasible action set Afeas . t Under identical nonnegative additive valuations, Theorem 5 guarantees that assigning the arriving good to an agent with a least-valued current bundle preserves EF1 at every prefix. Hence, Afeas ̸= ∅ for every allocation t step t, so the masked policy always admits at least one valid action and no fallback allocation rule is required. During training, the recipient is sampled from the resulting masked categorical policy, enabling stochastic exploration exclusively among EF1-feasible allocations. During deterministic evaluation and inference, the highest-priority feasible agent is selected. The complete masked policy definition, action-selection rules, and masked PPO likelihood-ratio formulation are provided in Appendix A. Relative Advantage Reward Formulation. To direct policy optimization toward welfare dominance over strong heuristic baselines while preventing gradient scale disparities across varying instance sizes, we define a normalized relative advantage terminal reward measured against Offline LPT: Rterm = wreward ·

NSWRL − NSWLPT , MaxNSW 9

where NSWLPTP is the welfare achieved by the offline descending greedy baseline (equivalent to Alg_Identical [3]), m MaxNSW = n1 k=1 vk represents the continuous theoretical welfare upper bound (via the AM-GM inequality), and wreward = 20.0 is an amplification constant that scales minute relative welfare differentials (∼ 0.005–0.05) into a well-conditioned numerical range [−2.0, +2.0]. Intermediate step rewards are set to zero (rt = 0 for t < m), focusing value estimation entirely on the quality of the final complete allocation. Surrogate Loss Objective. The network parameters θ are trained end-to-end using the standard PPO clipped surrogate objective [22], together with value-function regression and policy entropy regularization. Temporal advantages are estimated using Generalized Advantage Estimation (GAE-λ) [21] and standardized within each mini-batch before policy optimization. The overall training objective is Ltotal (θ) = Lclip (θ) + cvf Lvalue (θ) − cent H(πθ ), where cvf and cent control the Critic loss and entropy regularization, respectively. The PPO likelihood ratio is evaluated under the same state-dependent EF1 mask used during rollout collection. The complete GAE formulation, Critic target, advantage normalization, clipped surrogate objective, PPO likelihood-ratio computation and optimization details are provided in Appendix B. Goods Encoder State Features F [B, n, 11]

Valuations V/100 [B, n, m]

1D-CNN Goods Backbone Conv1D(1 → 128 → 64, k = 3) Masked Mean Pool → [B, 64]

PriorityNet Core Transformer Agent Feature Projection Concat(Goods Rep., F) → [B, n, 75] → Dense(75 → 128) + ReLU

Cross-Attention Block (×1) Pre-Norm Masked Cross-Attention (4 heads) Queries: Agent, Keys/Values: Items DeepFFN(128 → 512 → 128) + Residual

Transformer Encoder Block (×1) Pre-Norm Masked Self-Attention (4 heads) Agent-to-Agent Interaction DeepFFN(128 → 512 → 128) + Residual Dual Output Heads Actor Head (Policy) Dense(128 → 64) → GELU → Dense(1) Priority Logits ℓ ∈ Rn

Critic Head (Value) Masked Mean Pool → Dense(64) → Dense(1) State Value V (s) ∈ R

Fig. 1. Data flow and module layout of PriorityNet.

4.4

Experimental Results & Comparative Analysis

Offline Full-Information Benchmark. We evaluate policy performance under the static full-information offline setting across 3,000 independent test instances (1,000 per scale regime: Small n ∈ [2, 5], m ∈ [5, 20]; 10

Medium n ∈ [6, 10], m ∈ [20, 50]; and Large n ∈ [11, 20], m ∈ [50, 100]) drawn from the five representative valuation generator classes under identical additive valuations. In this setting, the full catalog of goods is sorted in descending order and allocated sequentially. We benchmark PriorityNet (PPO, converged checkpoint PriorityNet8k ) against four baselines: (a) Offline LPT (Greedy): Drawing inspiration from Graham’s classical Longest Processing Time first rule in multiprocessor scheduling [11], this greedy heuristic pre-sorts goods in descending order and iteratively assigns each item to the agent with the lowest accumulated utility (arg mini ui ). In fair division literature, this exact protocol was analyzed by Barman et al. [3] as Alg_Identical, which guarantees EFX and a 1.061-approximation to optimal NSW under identical valuations. (b) Reverse Round-Robin (Reverse-RR): The classical non-adaptive fair division protocol adopting alternating snake pick order (1, 2, . . . n, n, n − 1, . . . , 1). (c) Random EF1 Mask : An ablation baseline that selects a feasible recipient uniformly at random from Afeas t at each step, isolating the welfare contribution of learned priorities from feasibility masking. (d) Random RBS : A baseline enforcing round-level item count balance (∆Count ≤ 1) via random agent permutations per round. Table 2 summarizes the comparative performance across all scale regimes.

Scale Regime

Method / Baseline

Mean NSW

vs. LPT Win (%)

vs. LPT Tie (%)

vs. LPT Lose (%)

Overall (n ∈ [2, 20])

PriorityNet (PPO) Offline LPT (Greedy) Reverse-RR Random EF1 Mask Random RBS

0.9911 0.9911 0.9819 0.9774 0.9784

53.03% — 15.53% 4.77% 6.13%

21.03% — 6.67% 1.00% 1.23%

25.93% — 77.80% 94.23% 92.63%

Small (n ∈ [2, 5])

PriorityNet (PPO) Offline LPT (Greedy) Reverse-RR Random EF1 Mask Random RBS

0.9788 0.9787 0.9683 0.9619 0.9620

24.00% — 11.80% 6.70% 9.40%

61.00% — 19.30% 3.00% 3.70%

15.00% — 68.90% 90.30% 86.90%

Medium (n ∈ [6, 10])

PriorityNet (PPO) Offline LPT (Greedy) Reverse-RR Random EF1 Mask Random RBS

0.9963 0.9961 0.9869 0.9829 0.9845

68.50% — 17.00% 4.50% 5.00%

1.90% — 0.60% 0.00% 0.00%

29.60% — 82.40% 95.50% 95.00%

Large (n ∈ [11, 20])

PriorityNet (PPO) Offline LPT (Greedy) Reverse-RR Random EF1 Mask Random RBS

0.9983 0.9984 0.9904 0.9874 0.9887

66.60% — 17.80% 3.10% 4.00%

0.20% — 0.10% 0.00% 0.00%

33.20% — 82.10% 96.90% 96.00%

Table 2. Offline Benchmark Results: PriorityNet (PPO) vs. Baselines across 3,000 independent test instances (n ∈ [2, 20], m ∈ [5, 100]).

Performance Analysis and Ablation Insights. As shown in Table 2, PriorityNet performs competitively with Offline LPT and attains higher mean normalized NSW than the other considered baselines. Across all 3,000 test instances, PriorityNet and Offline LPT both achieve an overall mean normalized NSW of 0.9911. Nevertheless, PriorityNet attains higher NSW than LPT on 53.03% of the instances, ties on 21.03%, and attains lower NSW on 25.93%, yielding a win-minus-loss rate of +27.10% and a non-loss rate of 74.06%. Across the Small, Medium, and Large regimes, the respective mean normalized NSW values of PriorityNet and LPT are (0.9788, 0.9787), (0.9963, 0.9961), and (0.9983, 0.9984). Thus, PriorityNet has slightly higher mean welfare in the Small and Medium regimes and slightly lower mean welfare in the Large regime, although it wins more often than it loses in all three regimes. In particular, its win rates increase to 68.50% and 66.60% in the Medium and Large 11

regimes, respectively. The Random EF1 Mask ablation attains an overall mean normalized NSW of 0.9774 and, relative to LPT, records a 4.77% win rate and a 94.23% loss rate. Its lower performance is consistent with the importance of learned action selection beyond feasibility masking alone, although a direct paired comparison between PriorityNet and Random EF1 Mask would be needed to quantify this contribution more precisely. The round-robin baselines also perform less favorably than LPT: Reverse-RR and Random RBS attain overall mean normalized NSW values of 0.9819 and 0.9784, respectively, with corresponding loss rates of 77.80% and 92.63% against LPT. Overall, these results show that PriorityNet is competitive with LPT in aggregate welfare and obtains higher welfare on a larger fraction of the tested instances, rather than demonstrating a uniformly large improvement in mean welfare. Multi-Scale Scaling Dynamics and Theoretical Alignment. The multi-scale breakdown reveals consistent theoretical alignment with Theorem 4 (Small-Item Condition). In Small instances where item counts are small, Offline LPT is frequently near-exact; PriorityNet achieves a 61.00% Tie Rate and an 85.00% Non-Loss Rate (24.00% Win vs. 15.00% Lose). As problem scale expands to Medium (m ∈ [20, 50]) and Large (m ∈ [50, 100]), individual item values become finer fractions of average share µ, allowing PriorityNet to exploit global combinatorial cross-attention to surpass myopic greedy choices in over two-thirds of all instances. Concurrently, Mean Normalized NSW approaches 0.9983 MaxNSW, directly verifying that empirical welfare scales toward the theoretical continuous optimum as ϵ → 0. Fig. 2(a) illustrates this normalized NSW convergence toward the continuous optimal ceiling MaxNSW = 1.00 across agent counts n ∈ [2, 20], corroborating the asymptotic scaling behavior predicted by Theorem 4. Fig. 2(b) decomposes the detailed head-to-head matchup dynamics against Offline LPT, directly demonstrating how PriorityNet’s Net Win Rate (Win − Loss%, shaded green) remains strictly positive across n ≥ 4 and scales up to +20%– + 30% in larger problem dimensions.

Fig. 2. Offline full-information scaling dynamics and head-to-head matchup evaluation across agent count n ∈ [2, 20] (60 random seeds per cell). Panel (a) shows Normalized NSW (NSWALG /MaxNSW) with 95% Confidence Interval error bands (1.96 × SEM) converging toward the continuous upper bound MaxNSW = 1.00. Panel (b) illustrates PriorityNet’s Win Rate (%), Loss Rate (%), and Net Win Rate (Win − Loss%, shaded green) against Offline LPT across scaling dimensions.

Online Dynamic Streaming Benchmark. We evaluate policy performance in the dynamic online streaming setting under the standard Random-Order Arrival Model (window W = 1), where indivisible goods arrive sequentially in a uniformly random arrival permutation with zero future visibility. To maintain direct symmetry with the offline benchmark, we evaluate the converged online policy PriorityNet8k across 3,000 independent test instances over the identical multi-scale regimes: Small (n ∈ [2, 5], m ∈ [5, 20]), Medium (n ∈ [6, 10], m ∈ [20, 50]), and Large (n ∈ [11, 20], m ∈ [50, 100]) drawn across the full spectrum of eight distinct valuation distribution profiles. We benchmark PriorityNet against three online baseline mechanisms: (a) Online LPT (Greedy): The online greedy counterpart that immediately assigns each sequentially arriving item to the agent with the lowest accumulated utility (arg mini ui ) without pre-sorting, which strictly preserves prefix-wise EF1 at every arrival step under identical valuations (Theorem 5). 12

(b) Online Reverse-RR: The non-adaptive fair division protocol assigning arriving items in alternating snake order (1, 2, . . . n, n, n − 1, . . . , 1). (c) Random EF1 Mask : The neural ablation baseline selecting actions uniformly at random from Afeas at t each dynamic arrival step. Table 3 summarizes the comparative performance across all scale regimes.

Scale Regime

Method / Baseline

Mean NSW

vs. LPT Win (%)

vs. LPT Tie (%)

vs. LPT Lose (%)

Overall (n ∈ [2, 20])

PriorityNet (PPO) Online LPT (Greedy) Online Reverse-RR Random EF1 Mask

0.9701 0.9694 0.9005 0.9608

54.27% — 8.43% 27.13%

9.33% — 1.97% 5.60%

36.40% — 89.60% 67.27%

Small (n ∈ [2, 5])

PriorityNet (PPO) Online LPT (Greedy) Online Reverse-RR Random EF1 Mask

0.9610 0.9617 0.9165 0.9531

37.00% — 18.30% 26.10%

28.00% — 5.90% 16.80%

35.00% — 75.80% 57.10%

Medium (n ∈ [6, 10])

PriorityNet (PPO) Online LPT (Greedy) Online Reverse-RR Random EF1 Mask

0.9765 0.9759 0.9039 0.9676

58.10% — 5.10% 30.50%

0.00% — 0.00% 0.00%

41.90% — 94.90% 69.50%

Large (n ∈ [11, 20])

PriorityNet (PPO) Online LPT (Greedy) Online Reverse-RR Random EF1 Mask

0.9726 0.9705 0.8811 0.9616

67.70% — 1.90% 24.80%

0.00% — 0.00% 0.00%

32.30% — 98.10% 75.20%

Table 3. Online Dynamic Streaming Benchmark under the Random-Order Arrival Model: PriorityNet (PriorityNet8k ) vs. Online Baselines across 3,000 independent test instances (n ∈ [2, 20], m ∈ [5, 100]).

Performance Analysis across Online Regimes. As shown in Table 3, PriorityNet performs competitively with the online LPT baseline under random-order arrivals. Across all 3,000 test instances, PriorityNet attains a mean normalized NSW of 0.9701, compared with 0.9694 for the baseline. PriorityNet obtains higher NSW on 54.27% of the instances, ties on 9.33%, and obtains lower NSW on 36.40%, yielding a win-minus-loss rate of +17.87% and a non-loss rate of 63.60%. Thus, PriorityNet wins on a larger fraction of the tested instances, although the improvement in overall mean normalized welfare is modest. Across the Small, Medium, and Large regimes, the respective mean normalized NSW values of PriorityNet and the LPT baseline are (0.9610, 0.9617), (0.9765, 0.9759), and (0.9726, 0.9705). PriorityNet therefore has a slightly lower mean in the Small regime and slightly higher means in the Medium and Large regimes. Its corresponding win-minus-loss rates are +2.00%, +16.20%, and +35.40%, respectively. These results suggest that PriorityNet’s instance-wise advantage becomes more frequent as the tested scale increases, although the differences in mean normalized welfare remain relatively small. The Random EF1 Mask ablation attains an overall mean normalized NSW of 0.9608 and, relative to the LPT baseline, records a 27.13% win rate and a 67.27% loss rate. Its lower performance is consistent with the benefit of learned action selection beyond feasibility masking alone. However, a direct paired comparison between PriorityNet and Random EF1 Mask would be required to quantify this contribution more precisely. Online Reverse-RR performs less favorably, attaining a mean normalized NSW of 0.9005 and losing to the least-valued-bundle baseline on 89.60% of the instances. Fig. 3(a) illustrates the normalized-welfare results under the sampled random-order arrivals, with PriorityNet attaining regime-level means between 0.9610 and 0.9765. Fig. 3(b) presents the corresponding instance-wise win, loss, and win-minus-loss rates against the LPT baseline as the number of agents varies. Together, these results indicate that PriorityNet maintains high normalized welfare and frequently improves upon the greedy baseline, particularly in the larger tested regimes.

13

Fig. 3. Online dynamic streaming benchmark under the Random-Order Arrival Model (W = 1, 60 random seeds per cell). Panel (a) illustrates Normalized Nash Social Welfare (NSWALG /MaxNSW) with 95% Confidence Interval error bands under arrival uncertainty. Panel (b) displays PriorityNet’s Win Rate (%), Loss Rate (%), and Net Win Rate (Win − Loss%, shaded green) against Online LPT across agent count n ∈ [2, 20].

5

Conclusion

In this work, we provided a comprehensive theoretical and algorithmic investigation of Nash social welfare maximization under envy-freeness up to one item (EF1) for indivisible goods allocation with identical additive valuations. On the theoretical side, we clarified that requiring EF1 only for the final allocation does not change the optimal NSW, because every maximum-NSW allocation is already EF1. Thus, the problem inherits the known strong NP-completeness of identical-additive NSW maximization. Our main theoretical contribution instead concerns the welfare of arbitrary EF1 allocations. While every EF1 allocation inherently provides a universal e−1/e -approximation to the unrestricted optimal NSW, we further proved structural conditions under which this guarantee is significantly amplified: uniform identical valuations guarantee exact NSW optimality, and under the ϵ-small-item condition, every EF1 allocation achieves an explicit approximation factor ρn (ϵ) = 1 − O(ε2 ) that converges asymptotically to the continuous ceiling as individual goods become negligible. Separately, we considered the stronger sequential problem in which EF1 must be maintained after every item assignment. For this setting, we introduced PriorityNet, a reinforcement-learning framework trained using Proximal Policy Optimization and equipped with prospective EF1 action masking. The masking mechanism guarantees prefix-wise EF1 by construction for the processed item order. In the offline experiments, PriorityNet and LPT both attained an overall mean normalized NSW of 0.9911, although PriorityNet won on more individual instances, yielding a reported win-minus-loss rate of +27.10%. On the large offline subset, PriorityNet attained a mean normalized NSW of 0.9983, compared with 0.9984 for LPT. In the online streaming experiments, PriorityNet attained an overall mean normalized NSW of 0.9701, compared with 0.9694 for the online least-valued-bundle baseline, together with a win-minus-loss rate of +17.87%. These results indicate that PriorityNet is competitive with the considered heuristics and wins on a larger fraction of the tested instances, although the differences in aggregate mean welfare are modest. Promising avenues for future research include extending the prospective priority field architecture to asymmetric agent valuations and general submodular valuation profiles, investigating dynamic streaming with finite lookahead buffer windows (W > 1), and establishing theoretical sample-complexity and generalization bounds for reinforcement learning policies in constrained fair division. Acknowledgments. This work is funded and supported by the National Science and Technology Council, Taiwan, under grant nos. NSTC 115-2221-E-019-045-.

References [1] Aziz, H., Huang, X., Mattei, N., Segal-Halevi, E.: Computing welfare-maximizing fair allocations of indivisible goods. European Journal of Operational Research 307(2), 773–784 (2023). https://doi.org/ 10.1016/j.ejor.2022.10.013 14

[2] Barman, S., Krishnamurthy, S.K., Vaish, R.: Finding fair and efficient allocations. In: Proceedings of the 2018 ACM Conference on Economics and Computation (EC’18). pp. 557–574 (2018). https: //doi.org/10.1145/3219166.3219176 [3] Barman, S., Krishnamurthy, S.K., Vaish, R.: Greedy algorithms for maximizing Nash social welfare. In: Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’18). pp. 7–13 (2018), https://dl.acm.org/doi/10.5555/3237383.3237392 [4] Benade, G., Kazachkov, A.M., Procaccia, A.D., Psomas, C.A.: How to make envy vanish over time. In: Proceedings of the 2018 ACM Conference on Economics and Computation (EC’18). pp. 593–610 (2018). https://doi.org/10.1145/3219166.3219179 [5] Bu, X., Li, Z., Liu, S., Song, J., Tao, B.: Approximability landscape of welfare maximization within fair allocations (2025), https://arxiv.org/abs/2205.14296 [6] Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A.D., Shah, N., Wang, J.: The unreasonable fairness of maximum Nash welfare. ACM Transactions on Economics and Computation 7(3), 1–32 (2019). https://doi.org/10.1145/3355902 [7] Cole, R., Gkatzelis, V.: Approximating the Nash social welfare with indivisible items. SIAM Journal on Computing 47(3), 1211–1236 (2018). https://doi.org/10.1137/15M1053682 [8] Elkind, E., Lam, A., Latifian, M., Neoh, T.Y., Teh, N.: Temporal fair division of indivisible items. In: Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’25). pp. 676–685 (2025), https://dl.acm.org/doi/10.5555/3709347.3743584 [9] Feng, Y., Li, S.: A note on approximating weighted Nash social welfare with additive valuations. In: 51st International Colloquium on Automata, Languages, and Programming (ICALP’24). LIPIcs, vol. 297, pp. 63:1–63:18 (2024). https://doi.org/10.4230/LIPIcs.ICALP.2024.63 [10] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences, W. H. Freeman (1979) [11] Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics 17(2), 416–429 (1969). https://doi.org/10.1137/0117039 [12] He, J., Procaccia, A.D., Psomas, A., Zeng, D.: Achieving a fairer future by changing the past. In: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI’19). pp. 343–349 (2019). https://doi.org/10.24963/ijcai.2019/49 [13] Inoue, A., Kobayashi, Y.: An additive approximation scheme for the Nash social welfare maximization with identical additive valuations. Journal of the Operations Research Society of Japan 68(4), 133–150 (2025). https://doi.org/10.15807/jorsj.68.133 [14] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014). https://doi.org/10.48550/arXiv.1412.6980 [15] Lee, E.: APX-hardness of maximizing Nash social welfare with indivisible items. Information Processing Letters 122, 17–20 (2017). https://doi.org/10.1016/j.ipl.2017.01.012 [16] Lipton, R.J., Markakis, E., Mossel, E., Saberi, A.: On approximately fair allocations of indivisible goods. In: Proceedings of the 5th ACM Conference on Electronic Commerce (EC’04). pp. 125–131 (2004). https://doi.org/10.1145/988772.988792 [17] Mascioli, C., Goyal, S., Chakraborty, M.: FAIRFORMER: A transformer architecture for discrete fair division (2026). https://doi.org/10.48550/arXiv.2601.22346 [18] Nash, J.F.: The bargaining problem. Econometrica 18(2), 155–162 (1950). https://doi.org/10.2307/ 1907266 [19] Neoh, T.Y., Peters, J., Teh, N.: Online fair division with additional information. In: Proceedings of the 43rd International Conference on Machine Learning (ICML’26) (2026). https://doi.org/10.48550/ arXiv.2505.24503 [20] Nguyen, T.T., Rothe, J.: Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods. Discrete Applied Mathematics 179, 54–68 (2014). https://doi.org/10.1016/j. dam.2014.09.010 [21] Schulman, J., Moritz, P., Levine, S., Jordan, M., Abbeel, P.: High-dimensional continuous control using generalized advantage estimation. In: International Conference on Learning Representations (ICLR’16) (2016), http://arxiv.org/abs/1506.02438 [22] Schulman, J., Wolski, F., Dhariwal, P., Radford, A., Klimov, O.: Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 (2017). https://doi.org/10.48550/arXiv.1707.06347 [23] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, Ł., Polosukhin, I.: Attention is all you need. In: Advances in Neural Information Processing Systems (NeurIPS’17). vol. 30 (2017). https://doi.org/10.48550/arXiv.1706.03762

15

Appendix A

Masked Categorical Policy and PPO Likelihood Computation

This appendix provides the complete formulation of the prospective EF1 action mask, the resulting masked Categorical policy, and the corresponding likelihood-ratio computation used during PPO optimization. A.1

Prospective EF1 Action Mask

At allocation step t ∈ {1, 2, . . . , m}, the Actor produces a vector of raw priority logits ℓt = (ℓt,1 , ℓt,2 , . . . , ℓt,n ) ∈ Rn . For the current good gt , the prospectively EF1-feasible recipient set is defined as  Afeas = i ∈ A At−1 ∪ {(i, gt )} is EF1 . t The corresponding binary action mask Mt ∈ {0, 1}n is defined componentwise by ( 1, i ∈ Afeas , t Mt,i = feas 0, i ∈ / At . The mask is applied directly to the Actor logits: ( ℓt,i , i ∈ Afeas , t e ℓt,i = feas −∞, i ∈ / At .

(1)

(2)

(3)

(4)

Thus, infeasible actions are removed from the support of the policy before probability normalization. Under identical nonnegative additive valuations, Theorem 5 guarantees that assigning the arriving good to an agent whose current bundle has minimum value preserves EF1. Therefore, whenever the current prefix allocation At−1 is EF1, arg min v(At−1 ) ⊆ Afeas . (5) t i i∈N

Since a minimum-valued bundle always exists, Afeas ̸= ∅ t

for every t ∈ {1, 2, . . . , m}.

(6)

The empty initial allocation is trivially EF1, and every subsequent action is restricted to Afeas . Hence, t EF1 is preserved throughout the entire allocation sequence. Moreover, Eq. (6) guarantees that at least one admissible recipient is available at every step, so no fallback allocation rule is required. A.2

Masked Categorical Policy

Applying softmax to the masked logits in Eq. (4) yields the constrained policy   exp ℓet,i πθMt (at = i | st ) = n  . X exp ℓet,j

(7)

j=1

Equivalently, the masked Categorical distribution can be written explicitly as    P exp(ℓt,i ) , i ∈ Afeas , t Mt exp(ℓt,j ) πθ (at = i | st ) = j∈Afeas t   0, i∈ / Afeas . t

(8)

Thus, the Actor produces scores for all agents, while probability normalization is performed only over the state-dependent feasible action set Afeas . In particular, every EF1-infeasible action receives zero probability. t 16

During training rollouts, the recipient agent is sampled from the masked Categorical policy: at ∼ πθMt (· | st ).

(9)

This provides stochastic exploration among alternative allocations while restricting exploration entirely to EF1-feasible recipients. During deterministic evaluation and inference, sampling is replaced by selection of the highest-priority feasible agent: at = arg max ℓt,i . (10) i∈Afeas t

Because every infeasible logit is replaced by −∞ before action selection, Eq. (10) is equivalently obtained by taking the arg max over the masked logits ℓet . A.3

Masked PPO Likelihood Ratio

The feasible action set depends on the current allocation state. Consequently, the same state-dependent mask used to generate a rollout action must also be used when evaluating that action during PPO optimization. For each rollout transition, the mask Mt associated with state st is retained together with the rollout information and reapplied when the sampled action is evaluated under the updated policy. The behavior-policy log-probability is therefore t log πθM (at | st ), (11) old whereas the corresponding log-probability under the updated policy is log πθMt (at | st ).

(12)

The PPO likelihood ratio is consequently defined as rt (θ) =

πθMt (at | st ) t πθM (at | st ) old

.

Equivalently, using stored log-probabilities,   t rt (θ) = exp log πθMt (at | st ) − log πθM (a | s ) . t t old

(13)

(14)

The use of the mask in both terms is important because the rollout action was sampled from the constrained policy rather than from the unconstrained Actor distribution. To make this distinction explicit, let πθraw denote the Categorical distribution obtained by applying softmax directly to the unmasked logits. For a feasible action i ∈ Afeas , the masked probability can be expressed as t πθMt (at = i | st ) =

πθraw (at = i | st ) , Zθ (st , Mt )

(15)

X

πθraw (at = j | st )

(16)

where Zθ (st , Mt ) =

j∈Afeas t

is the total probability mass that the unconstrained policy assigns to EF1-feasible actions. Substituting Eq. (15) into Eq. (13) gives rt (θ) =

πθraw (at | st ) Zθold (st , Mt ) · . πθraw (at | st ) Zθ (st , Mt ) old

(17)

Equation (17) shows that the likelihood ratio of the masked policy is generally not equal to the likelihood ratio computed from the unmasked Actor distributions. In particular, the updated and behavior policies may assign different total probability mass to infeasible actions, so that Zθ (st , Mt ) ̸= Zθold (st , Mt )

(18)

in general. Therefore, computing the PPO ratio from unmasked probabilities would evaluate a policy different from the constrained policy that generated the rollout. Reapplying the same mask Mt ensures that both the numerator and denominator of the PPO likelihood ratio are normalized over the identical EF1-feasible action set. PPO updates consequently modify the relative preferences among feasible recipients while EF1-infeasible actions remain outside the support of the policy. 17

B

PPO Objective and Advantage Estimation

This appendix provides the detailed formulation of the advantage estimator, Critic regression target, PPO clipped surrogate objective, and the complete Actor–Critic optimization loss. B.1

Generalized Advantage Estimation

Temporal advantages are estimated using Generalized Advantage Estimation (GAE-λ). The temporal-difference residual at step t is δt = rt + γV (st+1 ) − V (st ), (19) where rt is the environment reward and γ is the discount factor. The corresponding GAE estimate is At =

TX −t−1

(γλ)l δt+l ,

(20)

l=0

where λ controls the bias–variance trade-off of the estimator. The value-function regression target is constructed from the unnormalized advantage estimate: R̂t = At + V (st ). The Critic is optimized using the squared-error objective  2  1 . Lvalue (θ) = Êt Vθ (st ) − R̂t 2 B.2

(21)

(22)

Advantage Normalization

For policy optimization, the advantages are standardized within each mini-batch: At − µ A , Āt = p 2 σA + 10−8

(23)

2 where µA and σA denote the mean and variance of the valid advantage estimates in the current mini-batch. Advantage normalization is applied only to the policy surrogate objective. The original, unnormalized advantages At are retained when constructing the Critic targets in Eq. (21).

B.3

Clipped PPO Surrogate Objective

Because actions are sampled from the EF1-constrained policy, the PPO likelihood ratio is evaluated using the same state-dependent mask Mt : πθMt (at | st ) rt (θ) = M . (24) πθoldt (at | st ) The clipped surrogate loss is then 
 Lclip (θ) = −Êt min rt (θ)Āt , clip (rt (θ), 1 − ϵ, 1 + ϵ) Āt ,

(25)

where ϵ is the PPO clipping coefficient. The complete Actor–Critic objective is   Ltotal (θ) = Lclip (θ) + cvf Lvalue (θ) − cent H πθMt .

(26)

Here, cvf controls the contribution of the Critic regression loss, while cent controls entropy regularization and encourages sufficient exploration among EF1-feasible actions. 18

B.4

Optimization Details.

The Actor–Critic network is jointly optimized using the Adam optimizer [14]. For each PPO update, the collected rollout samples are randomly shuffled at the beginning of every optimization epoch and partitioned into mini-batches. Each mini-batch is then used to compute the clipped policy loss, value-function loss, and entropy regularization term, followed by an Adam parameter update. The same rollout data are reused for multiple PPO optimization epochs, with a new random permutation generated at each epoch. The learning rate, PPO clipping coefficient, GAE parameters, value-loss coefficient, entropy coefficient, mini-batch size, and number of PPO optimization epochs are reported in Table 5.

C

Lemmas and Their Proofs

Lemma 1 (EF1 implies bounded utility spread). Let A be an EF1 allocation under identical additive valuations. Then for all agents i, j, v(Aj ) − v(Ai ) ≤ v ∗ . Equivalently, the largest and smallest bundle values differ by at most v ∗ . Proof. Fix i, j ∈ {1, 2, . . . , n}. If Aj = ∅, the inequality is immediate. Otherwise, since A is EF1, there exists g ∈ Aj such that v(Ai ) ≥ v(Aj \ {g}) = v(Aj ) − v(g). Because v(g) ≤ v ∗ , we have v(Ai ) ≥ v(Aj ) − v ∗ , which is equivalent to v(Aj ) − v(Ai ) ≤ v ∗ . ⊓ ⊔ The next lemma is the product estimate used for the small-item guarantee. The minimum over k is important in the sense that the extremal product needs not occur when exactly one bundle is poor and all other bundles are rich. Lemma 2 (Product lower bound under bounded spread). Let n ≥ 2 and let x1 , x2 , . . . , xn > 0 satisfy n X

xi = nµ

and

xi ≥ µn

min

max i∈{1,2,...,n}

i=1

xi −

min j∈{1,2,...,n}

xj ≤ D,

where 0 ≤ D ≤ µ. Then n Y i=1

 1≤k≤n−1

1−

kD nµ

n−k  1+

(n − k)D nµ

k .

Proof. Let d :=

max i∈{1,2,...,n}

xi −

min j∈{1,2,...,n}

xj .

We first prove the structureQof a product-minimizing vector with fixed sum and spread at most D. Consider a n feasible vector minimizing i=1 xi . Such a minimizer exists because the constraints n X

xi = nµ,

xi − xj ≤ D

for all i, j ∈ {1, 2, . . . , n}

i=1

define a closed and bounded feasible region. Moreover, since D ≤ µ, all feasible coordinates are nonnegative, and in fact positive unless all coordinates are equal. Let M = maxi∈{1,2,...,n} xi and m = minj∈{1,2,...,n} xi , so that M − m = d ≤ D. Suppose two coordinates xp ≤ xq both lie strictly between m and M . For sufficiently small t > 0, replacing them by xp − t and xq + t, respectively, preserves the total sum and keeps all coordinates in the interval [m, M ], and hence preserves feasibility. However, the product of these two coordinates changes from xp xq to (xp − t)(xq + t) = xp xq + t(xp − xq ) − t2 < xp xq . All other coordinates are unchanged, so the total product strictly decreases. This contradicts the minimality of the vector. Therefore, at a product minimizer, at most one coordinate can lie strictly between the minimum value m and the maximum value M . We next show that the possible interior coordinate can also be eliminated. Fix the spread d = M − m and fix the number k of coordinates equal to the upper endpoint. Suppose there is one interior coordinate. Write 19

the lower endpoint as a, the upper endpoint as a + d, and the interior coordinate as a + t, where 0 < t < d. Then the sum constraint gives (n − k − 1)a + (a + t) + k(a + d) = nµ, so a(t) = µ −

kd + t . n

For this fixed k and d, the logarithm of the product is       kd + t kd + t kd + t ϕ(t) = (n − k − 1) log µ − + log µ − + t + k log µ − +d . n n n Each term is the logarithm of an affine function of t, and hence ϕ(t) is concave on its feasible interval. A concave function on an interval attains its minimum at an endpoint. Thus the product cannot be increased by replacing the interior coordinate by one of the two endpoints. Consequently, a product-minimizing vector may be chosen with all coordinates equal either to a or to a + d. Hence, for some k ∈ {1, 2, . . . , n−1}, the extremal vector has n−k coordinates equal to a and k coordinates equal to a + d. The sum constraint gives (n − k)a + k(a + d) = nµ, and therefore

kd , n

a=µ−

a+d=µ+

(n − k)d . n

Thus the product is at least  µ−

kd n

n−k  µ+

(n − k)d n

k

for some k ∈ {1, 2, . . . , n − 1}. It remains to replace d by the upper bound D. For fixed k ∈ {1, 2, . . . , n − 1}, define  Fk (d) =

kd µ− n

n−k 

(n − k)d µ+ n

k .

A direct calculation gives k(n − k) d k(n − k) 1 1 + log Fk (d) = − < 0 kd (n−k)d dd n n µ− n µ+ n

whenever d > 0. Hence Fk (d) is nonincreasing in d. Since d ≤ D, we have Fk (d) ≥ Fk (D). Therefore

n Y

xi ≥

i=1

 n−k  k kD (n − k)D µ− µ+ . 1≤k≤n−1 n n min

Equivalently, n Y

n

xi ≥ µ

i=1

 min

1≤k≤n−1

kD 1− nµ

(n − k)D 1+ nµ

k . ⊔ ⊓

Thus the claimed bound follows.

D

n−k 

A Self-Contained Proof of Theorem 2

Proof. NP-membership. We first show that the problem belongs to NP. A certificate is an allocation A = (A1 , A2 , . . . , An ), which can be encoded by specifying, for each good, the agent to whom it is assigned. The size of this certificate is polynomial in the input size. Given such an allocation, we can verify in polynomial time that it is a valid allocation,P namely that every good is assigned to exactly one agent. We then compute the bundle values xi := v(Ai ) = g∈Ai v(g) for all i ∈ N . Since the valuation is additive and the item values are part of the input, all these values can be computed in polynomial time using integer arithmetic. Next, we verify the EF1 condition. For every ordered pair of agents i, j, if Aj = ∅, then agent i does not envy 20

agent j. Otherwise, under identical additive valuations, the condition that there exists a good g ∈ Aj such that v(Ai ) ≥ v(Aj \ {g}) is equivalent to xi ≥ xj − maxg∈Aj v(g). Thus, for each j, we compute maxg∈Aj v(g), and then check the above inequality for all pairs i, j. This requires only polynomial time. Finally, we verify Qn 1/n theQNash social welfare threshold. Since NSW(A) = ( i=1 xi ) , the condition NSW(A) ≥QT is equivalent n n n to i=1 xi ≥ T , hence we can verify the inequality using integer arithmetic. The product i=1 xi and the n value T have polynomially many bits, because each xi is at most the total value of all goods. Therefore the threshold condition can also be checked in polynomial time. Consequently, a proposed allocation can be verified in polynomial time, and the problem belongs to NP. NP-hardness reduction. We consider a reduction from 3-Partition. An instance of 3-Partition consists P3q of positive integers a1 , a2 , . . . , a3q and an integer B such that j=1 aj = qB and B4 < aj < B2 for every j ∈ {1, 2, . . . , 3q}. The question is whether the 3q numbers can be partitioned into q triples, each summing exactly to B. We construct an allocation instance with q agents and 3q goods g1 , g2 , . . . , g3q . All agents have the same additive valuation v, defined by v(gj ) = aj for each j = 1, 2, . . . , 3q. Set the NSW threshold to T = B. This construction is clearly polynomial. Suppose first that the 3-Partition instance is a yes-instance. Then the goods can be divided into q bundles A1 , A2 , . . . , Aq such that v(Ai ) = B for every i ∈ {1, 2, . . . , q}. The resulting allocation is envy-free, because all agents have identical valuations and all bundles have equal value. Hence it is EF1. Moreover, Qq 1/q NSW(A) = ( i=1 B) = B = T . Thus the constructed EF1-Identical-NSW instance is a yes-instance. Conversely, suppose that the constructed allocation instance admits an EF1 allocation A = (A1 , A2 , . . . , Aq ) with NSW(A) ≥ B. Since the valuation is identical and additive, the total value over all bundles is fixed. Pq P3q That is, i=1 v(Ai ) = v(M ) = j=1 aj = qB. By the arithmetic-geometric mean inequality (AM-GM), Pq Qq 1/q NSW(A) = ( i=1 v(Ai )) ≤ 1q i=1 v(Ai ) = B. Since NSW(A) ≥ B, equality must hold in AM-GM. Therefore v(A1 ) = v(A2 ) = · · · = v(Aq ) = B. Thus the goods are partitioned into q bundles, each of total value B. Finally, the size bounds B/4 < aj < B/2 imply that each such bundle contains exactly three goods since one or two goods have total value strictly less than B, while four or more goods have total value strictly greater than B. Hence the bundles define a valid 3-Partition solution. Concluding. Since the yes-direction constructs an allocation that is actually envy-free, the EF1 constraint is fully respected by the reduction. Because 3-Partition is strongly NP-complete, the decision problem is strongly NP-complete, and the corresponding optimization problem is thus strongly NP-hard. ⊓ ⊔

E

Proof of Theorem 4

Pn Proof. Let xi = v(Ai ). Since valuations are identical and additive, i=1 xi = v(M ) = nµ. By the boundedspread lemma, every EF1 allocation satisfies maxi∈{1,2,...,n} xi − minj∈{1,2,...,n} xi ≤ v ∗ ≤ εµ. Applying Lemma 2 with D = εµ gives n Y

xi ≥ µn

i=1

n−k  k  (n − k)ε kε 1+ . 1− 1≤k≤n−1 n n min

Taking the n-th root yields NSW(A) ≥ µρn (ε). On the other hand, for any allocation B, the AM-GM inequality gives NSW(B) =

n Y

!1/n v(Bi )

n

≤

i=1

1X v(M ) v(Bi ) = = µ. n i=1 n

In particular, NSW(A∗ ) ≤ µ. Hence NSW(A) ≥ ρn (ε). NSW(A∗ ) The maximum with e−1/e follows because both lower bounds hold simultaneously.

F

State Representation & PriorityNet Architecture, and Hyperparameter Configuration

21

⊓ ⊔

Feature Index

Symbol

Mathematical Definition

Semantic Description & Interpretation

0

ūi

ui max(Utmax , 1.0)

Normalized cumulative utility relative to current maximum utility Utmax = maxk uk

1

rank(ui )

rank(ui ) n−1

Relative utility rank among all agents (0.0 = poorest, 1.0 = richest)

2

m̂rem

Fraction of remaining unallocated goods (allocation progress clock)

3

v̂t

4

v̄t

5

∆umax i

6

ϕi

7

\t NSW

m−t m vt 100.0 vt 100.0 Utmax − ui max(Utmax , 1.0) ui P −8 k uk + 10 NSWcur max(MaxNSWt , 10−8 )

8

rilast

I(i = at−1 )

One-Hot indicator for agent selected at step t − 1 (1.0 if i = at−1 , 0.0 otherwise)

9

τiidle

  t − tlast i min , 1.0 2n

10

∆vitop

|vt − max(Ai )| 100.0

Normalized valuation of the current arriving/available item gt Valuation channel slot for arriving item representation Normalized maximum envy gap relative to the richest agent Relative utility share of total realized social welfare Running normalized NSW relative to revealed-history ceiling P MaxNSWt = n1 g∈Ht v(g) (offline: Ht = M )

Normalized starvation indicator (idle steps elapsed since agent i’s last pick) Normalized value gap between arriving item vt and agent i’s top existing item

Table 4. Engineered observation features.

22

Hyperparameter

Symbol / Key

Value

Total Training Episodes episodes 5,500–8,000 Batch Size (Parallel Envs) B / batch_size 64 Learning Rate learning_rate 3 × 10−4 (Cosine Decay to 10%) PPO Clip Epsilon ϵ / ppo_clip_epsilon 0.1 PPO Epochs ppo_epochs 4 PPO Minibatch Size ppo_minibatch_size 32 GAE Lambda λgae 0.95 Discount Factor γ 0.995 Value Loss Coefficient cvf / vf_coef 0.5 Entropy Coefficient cent / entropy_coef 0.02 Gradient Clipping Norm max_grad_norm 1.0 Table 5. Hyperparameter Configuration for PriorityNet Training.

23

Related documents

• EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments#1084368
• Revisiting EFX and fPO Allocations for Binary Chores#1083458
• PMMS Allocations Need Not Exist for 3 Agents with Additive Valuations#986573
• A Note on EFX Inapproximability for Chores#1155208
• Weighted Fair Division of Indivisible Mixed Manna#971885