CS Paper Radar

Easier, but Not Easy: Nash Welfare under Lexicographic Valuations

Soumil Aggarwal, Rohit Vaish, Jatin Yadav

cs.GT cs.DS ·submitted 2026-08-25 13:21 UTC · v1
theory

Abstract

Maximizing Nash welfare over indivisible goods is a central problem in resource allocation. For additive valuations, the best-known approximation factor is roughly $e^{-1/e}\approx0.692$, and the problem is APX-hard. We study Nash welfare maximization under lexicographic valuations, where every good is worth more than the total value of all lower-ranked goods. This large-gap structure makes preferences almost ordinal, which might suggest that the problem becomes easy. We show, however, that the picture is more nuanced: although lexicographic valuations enable stronger algorithmic guarantees, they retain significant computational hardness. Our first main result is a $(1/\sqrt{2}-ε)\approx(0.707-ε)$-approximation algorithm for weighted Nash welfare under lexicographic valuations, improving over the inherited guarantee of roughly $e^{-1/e}$. The algorithm rounds the configuration LP for Nash welfare, for which we show a matching integrality gap of $\sqrt{2}$. Our second main contribution is an exact algorithmic polynomial time framework for ordered lexicographic instances and doubling lexicographic instances. We introduce a domination-based branch-and-prune method for which we prove a mutual-exclusion property between sibling subtrees and use a matrix-based leaf-counting argument to bound the pruned recursion tree by a polynomial when the number of agents is constant. Finally, we show that large gaps do not eliminate hardness, as Nash welfare maximization is NP-hard even for ordered lexicographic valuations, and it is NP-hard to obtain a $0.9996$-approximation even for doubling lexicographic valuations. Thus, lexicographic valuations make Nash welfare maximization easier, but not easy: they admit tighter approximation and exact algorithms in important cases, yet still require intricate techniques and preserve some of the hardness of the general additive setting.

Comment
Abstract shortened to match arXiv requirements

Closest papers

Nearest neighbours by meaning across the whole index.

Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations

cs.GT cs.AI ·2026-10-04 ·Thi Ngoc Anh Vu, Trung Thanh Nguyen, Khaled Elbassioni, Jörg Rothe
theory similarity 0.75
Abstract

We study the problem of computing an allocation of indivisible items that maximizes egalitarian welfare, i.e., the utility of the worst-off agent, when agents' item values or marginal values belong to a small set. For additive valuations with values in $\{p,q\}$, where $q>p>0$ and $\gcd(p,q)=1$, we give a polynomial-time algorithm when $p=2$ and prove constant-gap hardness when $p\geq3$, already with exactly three high-valued goods per agent. We also give an $\sqrt{3/2}$-approximation for common positive bi-valued additive valuations. For mixed additive valuations in $\{-p,0,c\}$, where $p\in\{1,2\}$ and $c$ is a positive integer, a reduction to maximum-weight perfect matching resolves the conjectured tractability of $\{-2,0,c\}$-valuations. For submodular valuations with marginals in $\{-2,0,c\}$, where $c$ is odd, we establish an exact unit-gap hardness result and exponential value-query lower bounds, even when all but one agent are additive. Finally, for $\{-1,0,1\}$-submodular valuations, we prove that no finite multiplicative approximation exists unless $\p=\np$. Together, our results resolve open questions and provide a complete picture of the computational complexity of max-min allocation with ternary valuations.

0.04

Maximin Share Allocations Beyond Weakly Lexicographic Valuations

cs.GT ·2026-09-12 ·Nicholas Teh
theory similarity 0.72
Abstract

We study the fair division of indivisible goods among agents with nonnegative additive valuations. An agent's maximin share (MMS) is the value she can guarantee by partitioning the goods into as many bundles as there are agents and receiving a least-valued bundle. We prove the existence of exact MMS allocations for a valuation domain that generalizes several few-valued domains as well as weakly lexicographic valuations. For each agent, the lower-valued goods, after a positive rescaling, may take values in $\{0,1,d,d+1\}$, $\{0,1,2,2e\}$, or $\{0,1,2,3,4\}$, where $d,e\ge 2$ are integers. Above these goods, the valuation may contain arbitrarily many value classes, subject to the condition that a single good in each class is worth at least the total value of all strictly lower-valued goods. The value classes, scaling factors, and parameters may vary across agents. We give an algorithm that computes an MMS allocation in $O(nm\log^2(2+m))$ time, where $n$ is the number of agents and $m$ is the number of goods.

0.34

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

cs.GT cs.LG ·2026-09-03 ·Zih-Sian Yang, Yi-Hao Chen, Yu-Te Kuan, Cheng-Jui Wu, Chuang-Chieh Lin +1 more
similarity 0.71
Abstract

We study the allocation of indivisible goods among agents with identical additive valuations, focusing on envy-freeness up to one good (EF1) and Nash social welfare (NSW). Since every maximum-NSW allocation is EF1 under additive valuations, the associated threshold problem inherits the known strong NP-hardness of NSW maximization under identical additive valuations and is strongly NP-complete. We therefore focus on welfare guarantees satisfied by arbitrary EF1 allocations. Although every such allocation is known to achieve an $e^{-1/e}$-approximation to the unrestricted optimal NSW, we identify conditions yielding stronger guarantees. Under uniform valuations, every EF1 allocation is NSW-optimal. Under an $\varepsilon$-small-item condition, every EF1 allocation achieves an explicit approximation ratio $ρ_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$.

0.21

Santa Claus and Weighted Nash Social Welfare with Subadditive Valuations

cs.DS ·2026-11-03 ·Yuhang Chen, Yuda Feng, Weijiang Hu, Shi Li, Ruilong Zhang
theory similarity 0.71
Abstract

We study max-min allocation (the Santa Claus problem) and weighted Nash social welfare for $n$ agents with subadditive valuations over $m$ indivisible items. Using demand queries, we give randomized polynomial-time approximation algorithms with factors $O(\sqrt n)$ and $O(Γ(w))$, respectively, where $Γ(w)=\exp((\ln n-H(w))/2)$ and $H(w)=-\sum_i w_i\ln w_i$ for positive weights summing to one. Both ratios are independent of $m$. The max-min result improves the $2n-1$ bound of Khot and Ponnuswami (2007). We also give simpler $O(\sqrt n)$ algorithms for additive valuations and for submodular valuations with value queries, improving the $O(\sqrt{n\log n})$ bound of Saha and Srinivasan (2018) in the additive case. For Nash welfare, $Γ(w)=1$ for equal weights and $Γ(w)\le\sqrt n$ in general. We prove a configuration-LP integrality gap of $Θ(Γ(w))$ for every prescribed weight vector, even for XOS valuations. For every fixed $D>0$, we also prove information-theoretic approximation lower bounds of $Ω_D(\sqrt{n/\ln n})$ and $Ω_D(Γ(w)/\sqrt{\ln n})$, respectively, for randomized algorithms making at most $n^D$ adaptive queries. These hold on XOS instances with $m=Θ(n)$ items, even with simultaneous access to value, demand, and XOS supporting-clause oracles. They apply both to guarantees with success probability at least $2/3$ and to guarantees in expected welfare. The weighted bound holds for every prescribed weight vector and is vacuous below one. Thus the oracle lower bounds are within an $O(\sqrt{\ln n})$ factor of our upper bounds, while the configuration-LP gaps match them up to constants. Our algorithms build on random matchings for large items and charge the aggregate loss across configurations to the at most $n$ matched items.

0.17

When Maximum Nash Welfare Becomes Strongly Fair: Bi-valued Goods

cs.GT ·2026-09-09 ·Zehan Lin, Xiaowei Wu, Shengwei Zhou
similarity 0.70
Abstract

For the fair allocation of indivisible goods, the milestone work of Caragiannis et al. (2019) revolutionized the understanding of Maximum Nash Welfare (MNW) allocations by revealing their "unreasonable" ability to balance fairness (EF1) and efficiency (PO) for general additive functions. Subsequent work established that MNW allocations simultaneously satisfy EFX and GMMS (and consequently MMS and PMMS) for binary instances (Amanatidis et al. 2021 and Barman et al. 2018), and satisfy EFX for bi-valued instances (Amanatidis et al. 2021). In this paper, we revisit the (personalized) bi-valued instances and provide a tight characterization of the approximation guarantees of MNW allocations with respect to EFX, PMMS, and GMMS, showing that these guarantees are significantly stronger than what is known for general valuations. Furthermore, we demonstrate that even for the slightly more general setting of tri-valued instances, the fairness guarantees of MNW deteriorate significantly, which establishes a sharp boundary on the instances for which MNW allocations are strongly fair.

0.18

Revisiting EFX and fPO Allocations for Binary Chores

cs.GT ·2026-09-12 ·Zehan Lin, Xiaowei Wu, Shengwei Zhou
similarity 0.69
Abstract · 28 pages, no figure

We study fair and efficient allocations of indivisible chores under binary additive costs, with a focus on unequal entitlements and best-of-both-worlds guarantees. While binary valuations have been extensively studied for goods, their chore counterpart remains much less understood. A notable exception is due to Tao et al. (TCS 2025), who established that EFX and fPO are compatible for binary chores with equal entitlements. We revisit binary chores under unequal entitlements and establish the computation of allocations that satisfy WEFX and fPO. Our key technical contribution is a new lexicographic potential function tailored to chores: any allocation minimizing this potential ensures both WEFX and fPO. This potential further guides a polynomial-time local-search algorithm for computing allocations with such fairness and efficiency guarantees. For best-of-both-worlds guarantees, we show that unequal entitlements create a sharp obstruction: even with two agents and identical binary additive costs, no lottery can simultaneously satisfy ex-ante WEF and ex-post WEF1. In contrast, for equal entitlements, we construct in polynomial time a lottery that is ex-ante EF and fPO, while every realization is both EFX and fPO.

0.41

Fair and Efficient Allocations: Decision Problems in the Gap of Polynomial Hierarchy

cs.GT ·2026-09-25 ·Xiaolin Bu, Biaoshuai Tao
published similarity 0.69
Abstract · Accepted by WINE'26

We consider the fair division problem with indivisible goods and study the following decision problem: given a fair division instance, does there exist an allocation that is envy-free and efficient? We consider two efficiency criteria: Pareto-optimality and social welfare optimality. We provide a complete landscape on the computational complexity of this decision problem, with the number of agents ranging from $2$ to $\infty$, both additive valuations and general valuations, and the more restricted class of $k$-ary valuation functions (where an item's marginal value is restricted to $\{0,1,\ldots,k-1\}$ for some constant $k\geq2$). One interesting observation is that many versions of the above-mentioned decision problems fall into the ``gap'' between the first and the second levels of the polynomial hierarchy. Specifically, assuming the polynomial hierarchy does not collapse to the first level (i.e., assuming $\text{NP}\neq\text{coNP}$), these problems are in $(Σ_2^{\text{p}}\capΠ_2^{\text{p}})\setminus(\text{NP}\cup\text{coNP})$. In particular, we provide a fine-grained complexity analysis across different parameter regimes, including the number of agents and the choice of valuation models. Depending on different parameters, many problems admit different complexity classifications, ranging from the intermediate classes $Θ_2^{\text{p}}$ and $Δ_2^{\text{p}}$ between the two levels to $Σ_2^{\text{p}}$-completeness. Finally, De Keijzer et al. show the $Σ_2^{\text{p}}$-completeness of the decision problem when considering Pareto-optimality as the efficiency criterion with additive valuations. Our main results extend this result to more restricted settings, such as instances with a constant number of agents or $3$-ary valuation functions, which resolves the open problem given by Bouveret and Lang.

0.16

Subjective Valuations Make It Hard to be Fair: The Complexity of Resource Allocation to Groups of Agents

cs.GT cs.CCcs.DS ·2026-10-20 ·Argyrios Deligkas, Eduard Eiben, Robert Ganian, Tiger-Lily Goldsmith, Marlene Gründel +1 more
similarity 0.67
Abstract

We study the parameterized complexity of finding an EF1 allocation of indivisible items in the group-sharing setting, which has received increasing attention in recent years. There, items are not allocated to individual agents but rather to one of two (or possibly more) groups, and agents within that group all share the assigned items. We consider both the "fixed" (EF1-Fix) and "variable" (EF1-Var) group cases, where in the former the assignments of agents to groups are prescribed. While both are NP-hard in the classical sense, we show that their algorithmic behavior differs significantly from the parameterized perspective. As our main results, we: (1) prove that both cases are NP-hard even when the number of agents is a small constant; (2) circumvent this hardness by establishing fixed-parameter tractability for EF1-Var w.r.t. the number of "subjective" items, that is, items which are viewed as chores or goods by different agents---but rule out an analogous result for EF1-Fix; and (3) establish fixed-parameter tractability for EF1-Fix w.r.t. the number of item types, but link the existence of an analogous fixed-parameter algorithm for EF1-Var to a fundamental open question in the setting of Integer Linear Programming.

0.19