CS Paper Radar

Santa Claus and Weighted Nash Social Welfare with Subadditive Valuations

Yuhang Chen, Yuda Feng, Weijiang Hu, Shi Li, Ruilong Zhang

cs.DS ·submitted 2026-11-03 17:13 UTC · v2
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

On best of both worlds allocations with subadditive valuations

cs.GT ·2026-09-27 ·Uriel Feige
theory similarity 0.73
Abstract

We consider allocation of indivisible goods to agents with equal entitlements and subadditive valuations. As an ex-post fairness notion we consider the maximin share (MMS), and as an ex-ante fairness notion we consider the maximum expectation share (MES), which is always at least as large as the MMS, and sometimes much larger. We present a simple transformation that for every $0 < ρ\le 1$, given any algorithm that produces $ρ$-MMS allocations, transforms it into a randomized allocation algorithm that offers $ρ$-MMS ex-post simultaneously with $η$-MES ex-ante. We prove several new properties of MES, and use them to show that $η\ge \min[\fracρ{2 + ρ}, \frac{1}{4}]$. We also present cases in which the transformation results in a higher value of $η$. Applying our transformation to currently known allocation algorithms shows for subadditive valuations the existence of randomized allocations that are simultaneously $Ω(\frac{1}{\log\log n})$-MES ex-ante and $Ω(\frac{1}{\log\log n})$-MMS ex-post, and for XOS valuations the existence of randomized allocations that are simultaneously $\frac{4}{27}$-MES ex-ante and $\frac{4}{17}$-MMS ex-post.

0.26

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.73
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

Improving the Bounds on Approximating Weighted Maximin Share for Chores

cs.GT cs.AI ·2026-10-11 ·Trung Thanh Nguyen, Khaled Elbassioni, Jörg Rothe
similarity 0.72
Abstract

We investigate the problem of allocating indivisible chores among agents with arbitrary positive weights and additive nonnegative cost functions. An allocation is said to be $α$-weighted-maximin-share (WMMS) fair if the cost incurred by each agent is at most $α$ times her weighted maximin share. We establish that every instance admits a $4.124234528$-WMMS allocation. Moreover, for instances in which all weights and costs are rational numbers represented in binary, we give an algorithm that computes a $4.12424$-WMMS allocation in time polynomial in the number of agents, the number of chores, and the total binary encoding length of the input. Complementing these upper bounds, we construct a family of instances with strictly positive, identically ordered costs for which the optimal WMMS approximation factors converge to $e$. Together, our results substantially narrow the previously best-known gap of $[2,12]$ established by Li et al.~\cite{LWX26} to $[e,4.12424]$.

0.15

Easier, but Not Easy: Nash Welfare under Lexicographic Valuations

cs.GT cs.DS ·2026-08-25 ·Soumil Aggarwal, Rohit Vaish, Jatin Yadav
theory similarity 0.71
Abstract · Abstract shortened to match arXiv requirements

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.

0.25

MMS Allocation for Chores with Online Agent Arrivals

cs.GT ·2026-09-10 ·Haolong Li, Zehan Lin, Huahua Miao, Xiaowei Wu
theory similarity 0.71
Abstract

We study the fair allocation of $m$ indivisible chores to $n$ agents with subadditive cost functions arriving online in an arbitrary order. Upon an agent's arrival, we are informed of her cost function and must irrevocably assign her a set of chores. We focus on the Maximin Share (MMS) fairness notion and aim to compute an allocation in which all items are assigned, and no agent incurs a cost more than $α$ times her MMS. Without any prior information about the instance (other than $n$ and $m$), we design an algorithm with a competitive ratio of $O(\min\{n, k\log^{1+ε}k, \log m\})$ for any constant $ε> 0$, where $k$ denotes the number of cost function types. Our bound matches the best known offline approximation guarantees for MMS under subadditive costs and is nearly optimal with respect to all three parameters: we show that even for binary additive cost functions, no online algorithm can achieve a competitive ratio of $o(\min\{n, k\log k, \log m\})$. We then consider the setting in which the $k$ cost function types are known in advance (though the realized types of arriving agents are not). For additive cost functions, we provide an algorithm with a competitive ratio of $O(\min\{\log k, \log(kn)/\log\log(kn)\})$, and show that constant-competitive algorithms do not exist for general $k$, even for the binary additive setting. For binary additive functions when $k \le n$, we propose a $3$-competitive algorithm and establish a lower bound of $2$.

0.39

Toward Constant-Factor Maximin Share Guarantees for Subadditive Valuations

cs.GT ·2026-11-03 ·Bo Li, Ankang Sun
theory similarity 0.70
Abstract

For $n$ agents and $m$ indivisible goods, an agent's maximin share (MMS) is the largest minimum bundle value she can obtain by partitioning the goods into $n$ bundles. Constant MMS approximations are known for additive, submodular, or XOS valuations, but whether such a guarantee exists for general subadditive valuations remains open. We advance this question in two directions. For general subadditive valuations, we exponentially improve the guarantee from $Ω(1/\log\log n)$ to $Ω(1/\log^* n)$, where $\log^* n$ is the iterated logarithm. We then seek constant MMS guarantees under additional structure on subadditive valuations by studying $q$-partitioning valuations: every partition of a bundle into at most $q$ groups admits nonnegative group prices that sum to the bundle's value and whose sum on any collection of groups is at most the value of their union. This hierarchy ranges from subadditivity at $q=2$ to XOS for $q\ge m$. We give the first study of MMS in the intermediate classes and prove constant guarantees whenever $q/n$ has a fixed positive lower bound, including $1/6$ for $q\ge n$ and $1/4$ for $q\ge2n$. For XOS valuations, we further improve the universal guarantee from $4/17\approx 0.2353$ to $5/16=0.3125$. For subadditive valuations, we prove a bidding amplification theorem that gives an exponential bound on each agent's probability of receiving less than half her MMS, while satisfying her budget in every outcome. For $q$-partitioning valuations, we give a scalar criterion that converts bounds on the value lost from disjoint deletions within a bundle into bounds on potential losses, even when an agent contributes zero below the target bundle value. For XOS valuations, we prove a reservation theorem that selects goods for integral assignment together with auxiliary additive valuations and accounts for the loss in rounding.

0.09

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.70
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

Exact MMS Allocations under Personalized Bivalued Valuations: Goods and Chores

cs.GT cs.DS ·2026-08-16 ·Yuhao Zhang
benchmarktheory similarity 0.69
Abstract

The maximin share (MMS) is a central fairness benchmark for allocating indivisible goods and chores. We study additive valuations in the personalized bivalued setting, where each agent assigns one of two agent-specific values to every item. Whether exact MMS allocations always exist in this setting has remained a major open question, as highlighted by Ebadian, Peters, and Shah and by Garg, Huang, and Segal-Halevi. We answer this question affirmatively: we prove that exact MMS allocations always exist for both goods and chores and can be computed in polynomial time. Our proof combines a quota-based reformulation with an envelope relaxation, a sparse extreme-point construction, and flow-based rounding that controls the total rounding loss.

0.40