A group of agents must divide indivisible goods, and each agent values bundles of goods differently. The maximin share (MMS) of an agent is the best value she could guarantee herself by splitting all goods into bundles and receiving the bundle she likes least (Budish 2011). Allocations giving every agent her full maximin share need not exist even for additive valuations (Kurokawa–Procaccia–Wang 2018), so the question is which fraction of the maximin share can be guaranteed to all agents simultaneously.
Constant fractions are known for additive, submodular and fractionally subadditive (XOS) valuations. For the larger class of subadditive valuations, where the value of a union is at most the sum of the values, no constant is known, and whether one exists is an open problem. Subadditive valuations model complement-free preferences in general, and they also appear in welfare maximization and budget-feasible procurement.
Timeline of guarantees for subadditive valuations:
The goods form a finite set and the agents are . Agent has a valuation that is normalized (), monotone () and subadditive ( for all ). An allocation is a tuple of pairwise disjoint bundles. Goods may be left unassigned, since by monotonicity they can be handed out afterwards without lowering any value.
For and a positive integer , let be the set of ordered partitions of into possibly empty bundles, and
An -MMS allocation gives every agent a bundle with .
The iterated logarithm is defined through the tower , by . Let , let be the least power of two at least , and let
For example , for , and for .
Some supporting results use a weaker structure than maximin shares. A valuable family for agent is a list of pairwise disjoint sets with . A -multi-allocation is a tuple of bundles that may overlap, with every good in at most bundles.
A -partitioning valuation, in , is normalized and monotone; every partition of any bundle into at most nonempty groups admits nonnegative group prices summing to its value, with every subcollection priced at most its union’s value. Prices may depend on the partition. An XOS valuation is the maximum of finitely many nonnegative additive valuations.
The paper presents three main MMS guarantees: refTheorem 1.1 for general subadditive valuations, refTheorem 1.2 for -partitioning valuations, and refTheorem 1.3 for XOS valuations. The platform allows one goal, so Theorem 1.1 remains the goal and Theorems 1.2 and 1.3 are milestones of equal standing.
For every and every instance as above,
The factor depends only on , not on the goods or the valuations. It is stated exactly as in the source, with the exact factor and not only its lower bound.
MultiAllocToAlloc.Subadditive.theorem_1, which is still open.The milestones for Sections 4 and 5 were added on 2026-11-15 so that the mission covers every theorem of the paper.
The theorem replaces the previous guarantee for subadditive valuations by . Since for every up to , the factor is at least for all instances of practical size, although it is not a universal constant. The open constant-factor question is thereby reduced to removing a very slowly growing factor. Theorem 1.4 is a general tool: it turns disjoint valuable bundles into allocations whose failure probability decays exponentially in the number of bidding trials, and it applies to any subadditive instance with that structure, beyond maximin shares.
The result has a written proof in a conference submission and has not been machine-checked. The milestone results are also unformalized, and Feige's rounding theorem, which the final step uses, is an open target on the platform. A complete formalization would check the layer bookkeeping, the finite minimax argument behind the bidding strategy and the conditioning argument behind the amplification bound. It would also provide reusable statements about maximin shares and multi-allocations for general set functions.
The natural route builds successive layers of partial allocations with the Seddighin–Seddighin lemma. Each layer only squares the ratio of agents to unserved agents, which gives layers and hence the earlier factor. Getting to layers needs a layer step under which grows exponentially. No deterministic argument for subadditive valuations is known to give such a step. The source obtains it from a probability guarantee, and an expected-value guarantee is not sufficient for this. Formally, the hard parts are the minimax theorem over a finite grid of bids, which must hold uniformly against arbitrary real competing bids, and the exact count of layers against the tower .
Goods are Fin m for an arbitrary , and agents are Fin n. For the MMS goal, valuations are real set functions with explicit normalization, monotonicity and subadditivity hypotheses, which together imply nonnegativity. The maximin share is the published LittleCharity.MMS.mms, which takes the maximum over all labellings of the goods by , that is over all ordered partitions into possibly empty bundles. Allocations are pairwise disjoint and need not be complete. A -multi-allocation bounds the number of bundles containing each good. Agents with and instances with are part of the goal's domain, and their target is . is defined by the natural-number tower of equation (2), and is the least with . Finitely supported distributions are finite supports with positive weights summing to one, and probabilities are sums of weights. Bid vectors are arbitrary nonnegative real vectors.
The goal assumes nothing about the working instance used in the proof. In particular, it does not assume , small singleton values, a fixed MMS partition or a bound on . Assuming any of these, or replacing by the weaker factor of the source's Appendix A, would give a different and weaker theorem.
Theorems 1.2 and 1.3 include . The reservation theorem concerns arbitrary finite collections of choices for monotone valuations and positive targets ; it has no XOS or MMS hypothesis.
A complete development needs:
The last item is a separate open target and is reusable on its own. Contributions toward any milestone, toward the rounding theorem, or toward general lemmas about mms for monotone set functions are welcome.
namespace SubadditiveMMS580.Amplification
/-- Theorem 1.1 (General subadditive valuations; Li–Sun, STOC 2027 submission #580, p. 2): every
instance with `n ≥ 2` agents and normalized monotone subadditive valuations on finitely many goods
`Fin m` admits an `α(n)`-MMS allocation, `α(n) = 1/(4D(n) − 2)`: pairwise disjoint bundles `A_i`
with `v_i(A_i) ≥ α(n) · MMS_n(v_i; M)`. In particular `α(n) > 1/(8(1 + log*₂ n))`. -/
theorem theorem_1_1 (n : ℕ) (hn : 2 ≤ n) {m : ℕ} (v : Fin n → Finset (Fin m) → ℝ)
(hnorm : ∀ i, IsNormalized (v i)) (hmono : ∀ i, IsMonotone (v i))
(hsub : ∀ i, SubmodOrder.Subadditive (v i)) :
(∃ A : Fin n → Finset (Fin m), IsAllocation A ∧
∀ i : Fin n, alpha n * LittleCharity.MMS.mms (v i) n Finset.univ ≤ v i (A i)) ∧
1 / (8 * (1 + (logStar n : ℝ))) < alpha n := by sorry
end SubadditiveMMS580.Amplification
Let agents have valuations on an arbitrary finite set of goods that are normalized (), monotone () and subadditive ( for all ). Let be agent 's maximin share: the maximum, over all ordered partitions of into possibly empty bundles, of the least value of a bundle. Define
so is the smallest power of two at least . Then there are pairwise disjoint bundles such that
and in particular
This improves the best known general maximin-share guarantee for subadditive valuations from to ; the factor depends only on the number of agents, not on the number of goods or the valuations.
Formalization Note Goods are Fin m for an arbitrary , agents Fin n. The bundles form a partial allocation; by monotonicity it can be completed without lowering any value. Agents with and instances with (including ) are included; their target is then . is the published LittleCharity.MMS.mms (a maximum over all labellings of the goods by ; only the definition of mms from that file is used, not its additivity predicate). , and are the definitions of this mission, with computed as the least with .
Differences from the source:
Fin m, Fin n; reason: relabelling; every finite instance is covered.IsNormalized and IsMonotone; reason: normalization and monotonicity give , so exactly the same valuations.No open leaves. Every sub-goal is proved or awaiting decomposition.