Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO

Recent work in fair division has focused on either simultaneously satisfying closely related fairness notions or achieving a single notion across the ex-ante and ex-post worlds. We study the compatibility of two fundamentally different fairness notions: envy-freeness and equitability. For indivisible goods-only and chores-only settings, we study the existence and complexity of simultaneously satisfying their relaxations, revealing sharp contrasts between the two settings. We show that EF1+EQ1 may fail to exist even for normalized binary goods: we construct an instance with 113 agents and 341 goods in which every agent approves exactly 165 goods, but no complete allocation satisfies both notions. Our main algorithmic result computes an EF1+EQ1 allocation for every normalized binary goods instance with at most seven agents. Thus, the smallest number of agents admitting a counterexample lies between 8 and 113, leaving the cases from 8 through 112 unresolved. In sharp contrast, binary chores admit the stronger EFX+EQX guarantee for any number of agents, even without normalization. We further initiate the study of cross-notion ex-ante and ex-post guarantees, asking whether randomized allocations can provide ex-ante guarantees for one notion while preserving ex-post guarantees for another.

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

Many allocation problems are intrinsically multidimensional, since an item may contribute differently to several criteria, and optimizing a single aggregate objective can hide severe losses in other dimensions. We study how much efficiency can be guaranteed simultaneously when indivisible items have multiple attributes. To this end, we introduce the \emph{multidimensional efficient allocation} (MDEA) model, where each agent has an additive valuation in each dimension, and investigate simultaneous efficiency under utilitarian social welfare (USW) and egalitarian social welfare (ESW). Our results reveal a sharp worst-case frontier. For exact efficiency, maximizing the number of dimensions attaining the USW optimum admits a $c/\ell$-approximation for every fixed constant $c$, and this dependence on the number $\ell$ of dimensions is essentially unavoidable; for ESW, even deciding whether two dimensions can be optimized simultaneously is NP-hard with binary valuations. For approximate simultaneous efficiency in every dimension, we identify a tight threshold of order $1/\ell$, showing that such guarantees always exist for both USW and ESW, while any asymptotically better dependence on $\ell$ is impossible, even for binary valuations. Finally, we introduce three natural multidimensional Pareto notions and characterize both their relationships and their computational complexity.