Toward Constant-Factor Maximin Share Guarantees for Subadditive Valuations

Introduction

We study maximin share (MMS) fair allocation of $m$ indivisible goods among $n$ agents with different preferences. An agent’s MMS is the largest value she can guarantee by partitioning the goods into $n$ bundles and receiving a bundle she values least [5]. This benchmark adapts the familiar divide-and-choose principle to indivisible goods: the agent chooses the partition, but has no control over which bundle she receives. Different agents may choose different partitions. An allocation that gives every agent at least her MMS may not exist, even when valuations are additive [24]. We therefore ask for approximate MMS allocations, which give every agent at least a specified fraction of her MMS. Early work proved constant-factor guarantees for additive valuations [24], submodular valuations [4], and fractionally subadditive (XOS) valuations [19]. We review subsequent improvements in § 1.3.

In this paper, we study the more general class of subadditive valuations, for which the value of a union of sets is at most the sum of their values. This class contains all three classes above. Subadditive valuations provide a general model of complement-free preferences and play an important role in welfare maximization, budget-feasible procurement, and online allocation [11, 12, 28, 27]. In fair division, Ghodsi et al. [19] first obtained an $\Omega(1/\log m)$ MMS guarantee. Subsequent work replaced the dependence on $m$ with a dependence on $n$ [30, 17] and improved the guarantee to $\Omega(1/\log\log n)$ [31, 13]. Despite this progress, the existence of a constant-factor MMS allocation remains open:

Does every instance with subadditive valuations admit an allocation giving every agent at least a universal constant fraction of her maximin share?

We approach the above question in two directions. First, for arbitrary subadditive valuations, we improve the guarantee from $\Omega(1/\log\log n)$ to $\Omega(1/\log^* n)$, where $\log^* n$ is the iterated logarithm. Second, we ask how much additional structure suffices for a constant guarantee and study the hierarchy introduced by Bangachev and Weinberg [8], which interpolates between subadditive and XOS valuations. We obtain constant MMS guarantees for intermediate classes that can strictly contain XOS. At the XOS endpoint, we use the stronger item-level additive structure to further improve the universal guarantee from $4/17$ to $5/16$ [15].

Main results

Suppose each agent $i$ has a monotone subadditive valuation $v_i$ and MMS $\mu_i$. An $\alpha$-MMS allocation consists of pairwise disjoint bundles $A_i$ such that $v_i(A_i) \ge\alpha\mu_i$ for every agent. Our paper focuses on the existence of such allocations.

An iterated-logarithmic approximation for subadditive valuations. Our first result improves the best general guarantee from $\Omega(1/\log\log n)$ [31, 13] to $\Omega(1/\log^* n)$. To state the precise factor, we define $d(n)=1+\log_2^2 n$ and $D(n)=2^{\lceil\log_2 d(n)\rceil}$; that is $D(n)$ is the smallest power of two at least $d(n)$. Let

To prove Theorem 1.1, we construct, for each agent, a bundle worth at least half of her MMS. These bundles may overlap, so the same good can appear in bundles intended for different agents. Our construction ensures that each good appears in $O(\log^{*} n)$ bundles, improving the previous $O(\log\log n)$ bound [31]. We then apply Feige’s rounding theorem [13] to obtain disjoint bundles. The smaller overlap bound reduces the loss from rounding and yields our improved MMS guarantee. We explain the construction in the technical overview.

Constant approximations for $q$-partitioning valuations. Bangachev and Weinberg [8] recently introduced a hierarchy of $q$-partitioning valuations to study the classes between subadditive and XOS valuations. We use this hierarchy to ask what additional structure beyond subadditivity suffices for a constant MMS guarantee. A valuation is $q$-partitioning if, for every set of goods and every partition of that set into at most $q$ groups, the groups admit nonnegative prices whose sum equals the set’s value and whose sum on any collection of groups is at most the value of their union. These are supporting prices for the partition. The prices may depend on the partition, and the parameter $q$ bounds the number of groups for which they are required. We denote this class by $Q_q$. The class $Q_2$ is precisely the subadditive class, whereas $Q_m$ is the XOS class. The inclusions are strict before the hierarchy reaches XOS [8]. In this paper, we give the first study of MMS in the intermediate classes. Our second result gives a constant MMS approximation whenever $c=q/n$ is bounded below by a positive constant.

Figure 1 shows how the guarantee $\rho(c)$ varies with $c=q/n$. In particular, we obtain a 1/6-MMS allocation when $q\ge n$ and a 1/4-MMS allocation when $q\ge2n$. Our theorem applies when $q=\Theta(n)$; when also $q<m$, $Q_q$ strictly contains XOS, because its valuations need not admit supporting prices for every singleton partition. It is worth noting that, for XOS valuations, this already gives a 1/4 guarantee, improving the previous universal guarantee of $4/17$ [15]. To obtain the first two branches of (1), we group agents and round their allocations; for the last two, we transfer bundles directly to agents whose bundles do not yet meet the desired MMS guarantee.

A stronger guarantee for XOS valuations. We finally focus on the XOS endpoint of the hierarchy, and further improve the approximation factor.

The factor $5/16=0.3125$ improves the previous universal guarantee of $4/17$ [15]. It also exceeds the recent guarantees of Feige and Grinberg [16], which are above $11/40=0.275$ for sufficiently large $n$ and approach $0.2767738$ as $n$ grows. Our guarantee applies to all numbers of agents. The proof, given in Section 5, uses a reservation theorem that chooses selected goods assigned integrally together with auxiliary additive valuations on the remaining goods. This theorem accounts for the loss of one good in rounding; a cap-and-restore lemma makes the required fractional value small enough to obtain $5/16$.

Table 1 summarizes our results and compares the known MMS guarantees in the literature.

Valuations	Earlier guarantees	This paper
Subadditive	$\Omega(1/\log\log n)$ [31, 13]	$\Omega(1/\log^{*} n)$ (Theorem 1.1)
$q$-partitioning	$\Omega(1/\log\log n)$ [31, 13]	constant when $q=\Theta(n)$ (Theorem 1.2)
		$1/6$ when $q\ge n$
		$1/4$ when $q\ge2n$
XOS	$4/17\approx0.2353$ for all $n$ [15]	$5/16=0.3125$ for all $n$ (Theorem 1.3)
	$11/40$ for sufficiently large $n$ [16]

Technical overview

For each MMS guarantee, we first allocate any singleton that meets an agent’s target and remove both the agent and the good, so that, after scaling, we may assume every agent has MMS one and values every singleton below the final target $\alpha$. We fix an MMS partition for each agent.

Subadditive valuations: bidding amplification. To prove Theorem 1.1, we construct bundles worth at least half the agents’ MMS in successive layers, where the allocated bundles within each layer are pairwise disjoint. Once an agent receives a bundle worth at least half her MMS, we record that bundle and exclude her from subsequent layers, while keeping all goods available. Every unserved agent therefore still has her $n$ disjoint MMS bundles. Since each good appears in at most one recorded bundle per layer, the number of layers also bounds the number of bundles containing any particular good. Thus, fewer layers reduce the overlap that must be resolved by rounding.

Our new technical contribution is a bidding amplification theorem. We first consider an auxiliary bidding game in which a player submits nonnegative bids on goods, subject to a fixed budget, and wins each good on which her bid strictly exceeds the competing bid. Adapting the finite minimax argument of Neogi, Pashkovich, and Swamy [28, 29], we construct a distribution over bid vectors that guarantees probability at least $1/2$ of winning goods worth at least half the value of a given bundle, against every fixed competing bid vector whose total is at most half the player’s budget. Every sampled bid vector satisfies the budget constraint.

We then use this strategy in multiple independent trials. Suppose $u$ agents remain unserved. Each unserved agent divides a unit budget among $\ell$ trials, independently choosing one of her $n$ MMS bundles uniformly at random and sampling a bid vector for the chosen bundle in each trial. We sum each agent’s trial bids coordinatewise to obtain her final bid vector, and assign every good to its unique highest bidder, if one exists. Since all bids are nonnegative, every good strictly won by an individual trial against the opponents’ final bids is also won by the agent’s final bid. Thus, one successful trial suffices for the agent to receive value at least half her MMS, and the probability that all trials fail decreases exponentially with the number of trials. The following theorem formalizes this guarantee, and we present the proof in § 3.

Let $u'$ denote the number of agents left unserved after one layer. The earlier guarantee [31] gives $u' \le u^2/n$. Once $n/u$ is sufficiently large and $u \ge2$, choosing $\ell$ proportional to $n/u$ in Theorem 1.4 instead gives

Thus the guaranteed growth of $n/u$ improves from quadratic to exponential. Using the earlier guarantee for a few initial layers and amplification thereafter, we serve every agent in at most $1+\log_2^* n$ layers (§ 3.3). Finally, Feige’s rounding theorem [13], together with the singleton bound, gives the $\Omega(1/\log^* n)$ MMS guarantee.

$q$-partitioning valuations: bounding losses from transfers. To prove Theorem 1.2, we compare an agent’s gain from receiving a bundle with the losses caused to the other agents, whom we call donors. For an agent below the target, we consider transferring either a whole MMS bundle or one of two complementary pieces into which we split it. The transfer gives her its goods and removes them from the donors’ bundles. We compare a disjoint family of candidates, evaluating each transfer separately from the same allocation.

Intersecting these candidates with a donor’s bundle gives disjoint subsets. Supporting prices then bound their summed deletion loss: for a nonnegative integer $L$, a valuation $f \in Q_q$, a bundle $S$, and pairwise disjoint subsets $B_1,\ldots,B_L \subseteq S$,

Capping preserves $Q_q$, so the same bound controls each donor’s contribution to capped social welfare, the sum of agents’ bundle values capped at one. This potential is used in earlier XOS arguments [19 AMSS23, 16]. With all agents and whole MMS bundles, however, the comparison guarantees an improving transfer only while the recipient’s capped value is below $1/n$, even when $q \ge n$.

Our first construction divides the agents into groups and uses capped social welfare within each group. An agent still has all $n$ MMS bundles available, but fewer donors can lose value. More groups improve the guarantee within each group while increasing the rounding loss, since the group allocations use the same goods. Balancing these effects gives the first two branches of (1), including $1/6$ when $q \ge n$.

For $q > n$, our second construction keeps all agents together and changes the potential. Each agent contributes a bounded function of her bundle value that is zero below the target $\alpha$. We choose this function so that splitting an MMS bundle increases the guaranteed sum of its pieces’ contributions, following the use of pieces in [AMSS23]. The difficulty is to bound donor losses: the function is concave only above $\alpha$, so the capping argument does not apply. We prove sufficient conditions for converting an aggregate bound on value losses into a bound on potential losses (Lemma 4.5). Supporting prices supply the required aggregate bound.

The comparison uses at most $q$ disjoint candidates, choosing either each whole MMS bundle or its two pieces. Each split adds one candidate, so larger $q$ permits more splits and a larger recipient gain. When $q \ge2n$, splitting every bundle gives $1/4$. Both constructions repeatedly improve a bounded potential until all participating agents meet their target. Taking the better guarantee gives Theorem 1.2; we give the proofs in § 4.2 and § 4.5.

XOS valuations: a reservation theorem. To prove Theorem 1.3, we again use disjoint MMS bundles to bound the cost imposed by other agents, now through additive lower bounds on individual goods. We fix such a lower bound of total value one for each MMS bundle. We seek a fractional allocation under auxiliary additive valuations and round it following Shmoys and Tardos [32]. Rounding may lose the largest auxiliary coefficient. We therefore reserve selected goods for integral assignment and choose them together with an auxiliary valuation on the other goods and a threshold on fractional auxiliary value. We call this triple a choice; its threshold accounts for the loss in rounding.

Our reservation theorem (Theorem 5.2) coordinates these choices. Against any fixed choices of the other agents with disjoint reserved sets, an agent must have a choice whose reserved goods avoid those sets and whose fractional auxiliary value exceeds the sum of its threshold and the cost of reserving its goods. We bound this cost by the other agents’ auxiliary coefficients on those goods. To coordinate the choices, we use one independent mean-one exponential variable per agent. Our potential sums, over unreserved goods, the expected maximum of the agents’ auxiliary coefficients multiplied by their variables, and subtracts the thresholds. The expected increase from adding an agent on a good equals her auxiliary coefficient times the probability that her product exceeds the others. These probabilities give feasible fractional shares. At a maximum of the potential, comparison with omitting an agent forces her fractional auxiliary value above her threshold, so rounding and adjoining the reserved goods meets her target.

For choices without reserved goods, we prove the cap-and-restore lemma (Lemma 5.4). We cap the coefficients of an additive lower bound and rescale them to sum to one. The capped coefficients control the rounding loss, while the original coefficients prove the target after rounding. When the original total value minus its largest coefficient exceeds the target, the sufficient fractional auxiliary value depends only on the target and this difference.

For $\alpha= 5/16$, we first allocate pairs that meet an agent’s target. We assign nonnegative credits to the surviving MMS bundles to account for the removed goods, with total credit at least the number of remaining agents. We bound each agent’s auxiliary coefficient sum plus a fixed charge per reserved good by one. Disjointness then ensures that some bundle’s credit exceeds the sum of the other agents’ auxiliary coefficients on its unreserved goods and the charges for its goods reserved by those agents. We prove that such a bundle supplies a suitable choice. In the remaining local case, a weighted combination of lower bounds on the potential increases for three choices cancels the other agents’ coefficients on the two goods with largest coefficients in the original additive lower bound. At least one actual choice therefore works. This gives a 5/16-MMS allocation; we give the proof in § 5.

Related work

MMS guarantees for additive, submodular, and XOS valuations. Budish [5] introduced the MMS benchmark for the allocation of indivisible goods. For additive valuations, Kurokawa, Procaccia, and Wang [24] proved that a 2/3-MMS allocation always exists; subsequent improvements [18 AG24, 20, 22] have raised the guarantee to 7/9 [22]. For submodular valuations, the initial 1/10 guarantee of Barman and Krishnamurthy [4] was improved to 1/3 by Ghodsi et al. [19] and then to 10/27 by Ben Uziahu and Feige [6]. Ghodsi et al. [19] also proved constant guarantees for XOS valuations, followed by improvements [30 AMSS23, 15, 16]. Feige and Grinberg [15, 16] prove their XOS guarantees for the stronger anyprice share (APS) benchmark and hence also for MMS. Informally, APS is the largest value an agent can guarantee with budget 1/$n$ under any nonnegative prices summing to one. Related work also considers hereditary set systems [25, 21], matroid-rank valuations [7], and XOS valuations with marginal values in $\{0,1\}$ [23, 10]. We refer to Amanatidis et al. [1] for a survey of fair division of indivisible goods.

General subadditive valuations. Ghodsi et al. [19] obtained an $\Omega(1/\log m)$ guarantee. Seddighin and Seddighin [30] replaced the dependence on the number of goods with a dependence on the number of agents, and Feige and Huang [17] improved the guarantee to $1/(14\log n)$. Seddighin and Seddighin [31] then constructed half-MMS bundles using $O(\log\log n)$ copies of each good. Combining this construction with Feige’s rounding theorem [13], whose loss is linear in the number of copies, gives an $\Omega(1/\log\log n)$ guarantee. We use the same rounding step and reduce the number of copies. Even two subadditive agents can rule out guarantees above 1/2 [19]. Christodoulou et al. [9] attain 1/2 for at most four agents and for any number of agents with only two distinct valuations. Feige [14] studies a related direction: randomized allocations that preserve an MMS guarantee in every outcome and give additional guarantees in expectation relative to the best average value of a partition into $n$ bundles. For MMS guarantees for chores with nonadditive costs, we refer to Li, Wang, and Zhou [26].

Bidding and amplification. Neogi, Pashkovich, and Swamy [28, 29] develop randomized bidding strategies with expected-value guarantees and budgets that hold in every outcome, using finite minimax arguments and random selection. We adapt this minimax framework to an indicator payoff for winning half a bundle’s value and enforce strict wins by a grid construction. A bidding-based proof of the earlier partial-allocation result [31] appears in [27], using samples of opponents’ bids and their coordinatewise maxima. Our amplification instead combines independent trials of an agent’s own strategy with coordinatewise summation, so that one successful trial suffices and every final bid obeys its budget. Conditioning on the opponents’ final bids makes the trial successes independent and gives the exponential failure bound in Theorem 1.4.

Partitioning valuations and capped welfare. Bangachev and Weinberg [8] introduced the partitioning hierarchy and its supporting-price characterization. Earlier XOS arguments use capped social welfare [19 AMSS23, 16], complementary pieces [AMSS23], and bounds on losses from disjoint deletions [19]. We extend the deletion bound to $q$-partitioning valuations and prove a scalar criterion that controls losses after applying a function that is zero below the target. This criterion permits the potential in our second construction to strengthen the gain from pieces while bounding each donor’s summed loss. Our stronger XOS result uses additive assignment rounding with a loss of at most one good, following Shmoys and Tardos [32]. The reservation theorem chooses the goods assigned integrally together with the auxiliary coefficients used in this rounding step. The cap-and-restore lemma and the combination of local reservation choices account for large coefficients and competing demands on the same goods. Unlike the hierarchy proof, this argument uses additive lower bounds on arbitrary subsets of an MMS bundle.

Preliminaries

Model and solution concepts