CS Paper Radar

Toward Constant-Factor Maximin Share Guarantees for Subadditive Valuations

Bo Li, Ankang Sun

cs.GT ·submitted 2026-11-03 15:37 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Maximin Share Allocations Beyond Weakly Lexicographic Valuations

cs.GT ·2026-09-12 ·Nicholas Teh
theory similarity 0.73
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

On MMS allocations with few items

cs.GT ·2026-10-05 ·Uriel Feige
theory similarity 0.72
Abstract

We consider the problem of allocating $m$ indivisible items to $n$ agents. For $n \ge 2$, we define $μ(n)$ as the largest $m$ for which every allocation instance with $n$ agents and $m$ items has an allocation that gives each agent at least her maximin share (MMS). We prove that for general monotone valuations, $μ(n) = n + Θ(\log n)$. This holds both for goods and for chores. For arbitrary valuations (not monotone), we prove that $μ(n) = \log n + O(1)$.

0.38

Fair Share Allocations for Almost All Agents

cs.GT ·2026-09-27 ·Tomer Ezra, Tamar Garbuz
similarity 0.71
Abstract

We study fair allocation of indivisible goods among agents with additive valuations. Our main result guarantees every agent her exact AnyPrice Share (APS) whenever the total entitlement is at most $1-\varepsilon$ and each individual entitlement is sufficiently small. For equal entitlements, this yields a $1$-out-of-$(n+O(\sqrt{n\log n}))$ maximin share (MMS) allocation. We also establish two best-of-both-worlds guarantees that preserve proportionality in expectation: each agent receives her full MMS with probability at least $1-O((\log n/n)^{1/3})$, or every agent receives her $1$-out-of-$(n+O(n^{2/3}(\log n)^{1/3}))$ MMS in every outcome. Both guarantees extend to sufficiently small unequal entitlements, with APS replacing MMS. Quantitatively, our deterministic result allows an entitlement cap of order $\varepsilon^2/\log(1/\varepsilon)$, while an impossibility construction shows that any universally sufficient cap must be $O(\varepsilon)$.

0.24

On best of both worlds allocations with subadditive valuations

cs.GT ·2026-09-27 ·Uriel Feige
theory similarity 0.70
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

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

Subquadratic Subsidies for Nonnegative or Nonpositive Valuations

cs.GT ·2026-09-08 ·Max Dupré la Tour, Mashbat Suzuki
theory similarity 0.70
Abstract

We study envy-freeness with subsidies for indivisible items beyond additive valuations. Assuming that every single-item marginal value lies in $[-1,1]$, we prove that a total subsidy of $O(n^{3/2}\sqrt{\log n})$ suffices to achieve envy-freeness among $n$ agents whenever all agents assign nonnegative values to every bundle or all assign nonpositive values to every bundle. These valuation classes include monotone goods and monotone chores, respectively, but do not require monotonicity. Our result establishes the first subquadratic total-subsidy bound for general monotone valuations that holds for every number of agents.

0.37

Tight Maximin Share Guarantees of EFX and PMMS

cs.GT ·2026-08-31 ·Qinghua Qin
benchmarktheory similarity 0.70
Abstract

In the fair division of indivisible goods among autonomous agents, allocations frequently satisfy strong pairwise fairness criteria while failing to guarantee an agent's full maximin share. Maximin share (MMS) is a global benchmark: the value an agent can guarantee by partitioning all goods into $n$ bundles and receiving her least preferred bundle. In contrast, local pairwise fairness notions---most notably envy-freeness up to any good (EFX) and pairwise maximin share (PMMS)---evaluate fairness through bilateral bundle comparisons. We resolve the open question of determining the optimal universal MMS approximation factor guaranteed by either local notion under nonnegative additive valuations, proving that both factors equal exactly $10/17$. For the lower bound, we show that both EFX and PMMS imply a common local residual inequality: the value of any foreign bundle after removing its least valuable item cannot exceed the focal agent's allocated value. We design a continuous piecewise weight function that converts this local constraint into the global $10/17$ MMS guarantee. The same charging argument establishes that $α$-EFX implies $(10α/17)$-MMS. For tightness, we construct an explicit family of complete allocations that simultaneously satisfy PMMS and EFX$_0$, including comparisons involving zero-valued goods, and whose MMS ratios converge to $10/17$. For each fixed number of agents, we also establish exact reciprocal identities connecting fair division to scheduling: the EFX guarantee is the reciprocal of the pure price of anarchy in selfish identical-machine covering, while the PMMS guarantee is the reciprocal of a locality gap for exact repartition of two machines.

0.38

Almost-MMS allocations with small agent redundancy

cs.GT ·2026-11-03 ·Uriel Feige, Vadim Grinberg
similarity 0.70
Abstract

For a fixed $ε\ge 0$, let $ρ_{ε, n}$ be the maximum value of $ρ_n$ such that, in every allocation instance with $m$ indivisible goods and $(1 + ε)n$ agents, there is a subset of $n$ agents with the following property. The allocation instance restricted to only this subset of $n$ agents has an allocation that gives each agent at least $ρ_n$-fraction of her $n$-maximin share (MMS). When $ε> 0$ we refer to $εn$ as the {\em agent redundancy}. The case $ε= 0$ is the standard setting without agent redundancy, and we use $ρ_{0,n}$ and $ρ_n$ interchangeably. For allocation instances with additive valuations, % agents, it is known that $\frac{7}{9} \le ρ_n < 1-Ω(\frac{1}{\log^2 n})$ for every $n \ge 2$ (with stronger lower bounds for small $n$). It is an open question whether $ρ_n$ tends to~1 as $n$ grows. We show that with agent redundancy, the answer to this question is positive. That is, for every $ε> 0$, $ρ_{ε, n}$ tends to~1 as $n$ grows. A straightforward corollary of this result is that for every $c > 0$, if the number of items satisfies $m \le (2 - c)n$, then the answer is positive also for $ρ_n$ (with no agent redundancy). Adapting our techniques to a related setting, we also improve a recent result of Ezra and Garbuz, and show that without agent redundancy, there always exists an allocation that gives $n - O(\log^2 n)$ agents their full MMS.

0.13