Answer: Polynomial-time solvable; every valid instance is feasible.
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere is an algorithm that computes a 1-out-of-⌈3n/2⌉MMS allocation in time polynomial in the length of the binary representation of the problem.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite catalogue \(G\) of \(m\) good types, integral total supply \(Q=Nq\in\mathbb{Z}_{\ge0}^{m}\), a finite set \(T\) of \(\tau\) additive valuation types, and type masses \(N\mu_t\), set \(d=\lceil3N/2\rceil\) and \(\theta_t=\operatorname{MMS}^{1,d}_t(Q)\). Decide, and construct when possible, finite-support masses \(x_{t,b}\ge0\) over integral bundles \(b\in\mathbb{Z}_{\ge0}^{m}\) satisfying \(\sum_b x_{t,b}=N\mu_t\), \(\sum_{t,b}b_gx_{t,b}=Q_g\), and \(x_{t,b}>0\Rightarrow v_t(b)\ge\theta_t\), in time polynomial in \(m\), \(\tau\), \(\log N\), and the input encoding lengths.
Let \(G\) be a catalogue of \(m\ge1\) good types, with binary-encoded supply \(Q\in\mathbb Z_{\ge0}^{m}\), and let \(N\ge1\) be a binary-encoded integer population scale.
A society is given by its support: the list of the \(\tau\) valuation types with positive mass \(a_t=N\mu_t\), each mass a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; the masses need not be integral.
Each type has additive valuations specified by binary rationals \(v_{t,g}\ge0\). An admissible bundle is \(b\in\mathbb Z_{\ge0}^{m}\) with \(b\le Q\) coordinatewise; empty bundles are allowed.
Set \(d=\lceil3N/2\rceil\) and define \(\theta_t=\operatorname{MMS}^{1,d}_t(Q)=\max_{\sum_{j=1}^{d}b^j=Q}\min_{1\le j\le d}v_t(b^j)\), where the partition bundles are integral and may be empty. These thresholds are defined by the input, not supplied separately.
A feasible allocation consists of finitely supported masses \(x_{t,b}\ge0\) satisfying \(\sum_bx_{t,b}=a_t\), \(\sum_{t,b}b_gx_{t,b}=Q_g\) for every good type, and \(x_{t,b}>0\Rightarrow v_t(b)\ge\theta_t\). Construction means an explicit list of bundles and binary rational masses.
Is deciding feasibility and constructing a feasible allocation whenever one exists solvable in time polynomial in \(m,\tau,\log N,L\), or is this computational problem NP-hard, where \(L\) is the total binary input length?
For explicitly listed agents and individual goods, a \(1\)-out-of-\(\lceil3n/2\rceil\) MMS allocation always exists and is computable in polynomial time in the binary input length ([Hosseini, Searns, and Segal-Halevi](https://arxiv.org/abs/2109.01925)).
No result settling this exact mass allocation problem with binary-encoded supplies was identified in the literature search.
Theorem. Every valid instance is feasible. Moreover, a feasible allocation with \(O(\tau m)\) supported type–bundle pairs can be constructed in time polynomial in \(m,\tau,\log N,L\).
The construction does not compute the exact MMS thresholds. It constructs a suitable partition for each valuation type separately, using a bin-covering guarantee, and then averages these partitions with rational masses.
Suppose that, for each type \(t\), we construct an \(N\)-partition of \(Q\) whose every bundle has value at least \(\theta_t\). Represent this partition by distinct bundles \(b^{t,1},\ldots,b^{t,s_t}\) and positive integer multiplicities \(k_{t,1},\ldots,k_{t,s_t}\), satisfying
\(\displaystyle \sum_{i=1}^{s_t}k_{t,i}=N,\qquad \sum_{i=1}^{s_t}k_{t,i}b^{t,i}=Q,\qquad v_t(b^{t,i})\ge\theta_t.\)
Define the allocation masses by
\(\displaystyle x_{t,b^{t,i}}=\frac{a_tk_{t,i}}{N}.\)
The total mass assigned to type \(t\) is
\(\displaystyle \sum_i x_{t,b^{t,i}}=\frac{a_t}{N}\sum_i k_{t,i}=a_t.\)
For every good type \(g\), total consumption is
\(\displaystyle \sum_t\sum_i b^{t,i}_g x_{t,b^{t,i}}=\sum_t\frac{a_t}{N}Q_g=Q_g,\)
because \(\sum_t a_t=N\). Every supported bundle meets its type’s threshold.
Thus it suffices to construct, separately for each valuation type, a compactly represented \(N\)-partition meeting its \(1\)-out-of-\(d\) MMS threshold. These partitions are auxiliary objects; no integrality assumption on the masses is needed.
We use the following known result.
Bin-covering lemma. Given a finite multiset of positive item values and a positive threshold \(T\), repeatedly take one largest remaining item and add smallest remaining items until the bundle reaches value \(T\). Stop when the remaining total value is below \(T\). If \(C(T)\) bundles are produced and \(\operatorname{OPT}(T)\) is the maximum number of disjoint bundles having value at least \(T\), then
\(\displaystyle C(T)\ge\frac{2}{3}\bigl(\operatorname{OPT}(T)-1\bigr).\)
This is the homogeneous version of Algorithm 3, with its guarantee stated in Lemma 3 of [Hosseini, Searns, and Segal-Halevi](https://arxiv.org/html/2109.01925v3). Items worth at least \(T\) become singleton bundles. Zero-valued items can be omitted.
Fix a valuation type and temporarily write its valuation as \(v\) and its MMS threshold as \(\theta\). If \(\theta>0\), an optimal \(d\)-partition supplies \(d\) disjoint bundles worth at least \(\theta\). Hence \(\operatorname{OPT}(\theta)\ge d\), and the lemma gives
\(\displaystyle C(\theta)\ge\frac{2}{3}(d-1)\ge N-\frac{2}{3}>N-1.\)
Since \(C(\theta)\) is integral, \(C(\theta)\ge N\).
The lemma applies to the finite multiset containing \(Q_g\) individual copies of each positively valued good type. This expanded multiset is used only in the proof; the algorithm below never explicitly constructs it.
Fix one type. Write its rational valuations as \(v_g=p_g/q_g\), with positive integer denominators. Let
\(\displaystyle D=\prod_{g=1}^{m}q_g,\qquad w_g=Dv_g\in\mathbb Z_{\ge0},\qquad V=\sum_g Q_gw_g.\)
Scaling valuations by \(D\) scales the MMS threshold by \(D\). Therefore
\(\displaystyle \sigma=D\theta=\max_{\sum_{j=1}^{d}b^j=Q}\min_j\sum_g w_gb^j_g\)
is a nonnegative integer.
For a positive integer \(T\), let \(P(T)\) mean that the bin-covering algorithm produces at least \(N\) bundles with weights \(w\). Set \(P(0)\) to true: the partition consisting of \(Q\) once and the empty bundle \(N-1\) times meets threshold zero.
We need monotonicity to search for a successful threshold.
Lemma. If \(0\le T\le U\) and \(P(U)\) holds, then \(P(T)\) holds.
Proof. The case \(T=0\) follows from its definition. Assume \(T>0\).
Conceptually list the positively valued copies in nonincreasing order, with values \(z_1,\ldots,z_M\), using a fixed ordering for ties. After \(j\) successful iterations at threshold \(A\), the unused items form an interval of indices
\(\displaystyle j+1,\ldots,R_j(A),\)
where \(R_j(A)=j\) means that nothing remains. Initially \(R_0(A)=M\).
We prove inductively that, whenever the run at threshold \(U\) completes its first \(j\) bundles, the run at threshold \(T\) also completes them and
\(\displaystyle R_j(T)\ge R_j(U).\)
Suppose this holds after \(j-1\) iterations. Both runs initialize their next bundle with item \(z_j\). If the lower-threshold run has not already stopped filling before reaching the higher-threshold run’s stopping position, its bundle there has value
\(\displaystyle z_j+\sum_{i=R_j(U)+1}^{R_{j-1}(T)}z_i \ge z_j+\sum_{i=R_j(U)+1}^{R_{j-1}(U)}z_i \ge U\ge T.\)
The first inequality uses \(R_{j-1}(T)\ge R_{j-1}(U)\) and nonnegative item values. Thus the lower-threshold run succeeds and stops with \(R_j(T)\ge R_j(U)\). This proves the induction and the lemma. \(\square\)
The bin-covering guarantee establishes \(P(\sigma)\) when \(\sigma>0\); it holds by definition when \(\sigma=0\). Also, \(P(V+1)\) is false.
Consequently, exact integer binary search between the successful endpoint \(0\) and unsuccessful endpoint \(V+1\) returns the largest successful threshold \(T^\star\), satisfying
\(\displaystyle T^\star\ge\sigma.\)
It remains to implement each threshold test in polynomial time with binary-encoded multiplicities.
Fix a positive threshold \(T\). Sort the positively valued good types by nonincreasing weight, with a fixed ordering for ties. Maintain their remaining integer multiplicities \(c_g\), initially \(Q_g\), and the number \(K\) of covered bundles produced. Stop successfully when \(K=N\).
At the start of an iteration, report failure if the remaining total value is below \(T\). Otherwise, let \(h\) and \(\ell\) denote the largest and smallest remaining good types.
The following operations exactly simulate the expanded algorithm.
If \(h=\ell\), each next covered bundle consists of
\(\displaystyle r=\left\lceil\frac{T}{w_h}\right\rceil\)
copies of this type. Produce
\(\displaystyle p=\min\left\{N-K,\left\lfloor\frac{c_h}{r}\right\rfloor\right\}\)
such bundles in one operation.
If this does not reach \(N\), the remaining value is below \(T\), so report failure.
If \(h\ne\ell\) and \(w_h\ge T\), produce
\(\displaystyle p=\min\{N-K,c_h\}\)
copies of the singleton bundle \(e_h\). This either reaches the target or exhausts type \(h\).
Suppose \(h\ne\ell\) and \(w_h<T\). Define
\(\displaystyle r=\left\lceil\frac{T-w_h}{w_\ell}\right\rceil.\)
If \(c_\ell\ge r\), the next expanded bundle is exactly \(e_h+re_\ell\). Produce
\(\displaystyle p=\min\left\{N-K,c_h,\left\lfloor\frac{c_\ell}{r}\right\rfloor\right\}\)
copies of this bundle, and subtract the corresponding multiplicities.
If this batch neither reaches the target nor exhausts a type, its limiting quantity must have been \(\lfloor c_\ell/r\rfloor\). The remaining multiplicity of type \(\ell\) is then strictly below \(r\).
When \(c_\ell<r\), start one bundle with a copy of type \(h\), then fill it from the smallest remaining types.
For current deficit \(\Delta>0\) and current smallest type \(g\), take
\(\displaystyle q=\min\left\{c_g,\left\lceil\frac{\Delta}{w_g}\right\rceil\right\}\)
copies. Either the bundle reaches \(T\), or type \(g\) is exhausted and filling continues with the next smallest type.
The initial smallest type \(\ell\) is necessarily exhausted: fewer than \(r\) of its copies cannot close the initial deficit. The check on remaining total value ensures that the bundle can be completed.
Every singleton batch exhausts a type or reaches the target. Every two-type batch either does the same, or is immediately followed by a boundary-crossing bundle or terminal failure. Every boundary-crossing bundle exhausts at least one type.
A type can be exhausted only once. Therefore there are \(O(m)\) batches and boundary-crossing bundles. Filling a boundary-crossing bundle requires at most \(m\) type-level operations. Thus a threshold test uses \(O(m^2)\) arithmetic operations and records only \(O(m)\) bundle patterns with integer multiplicities.
These are exactly the first \(N\) bundles of the expanded algorithm whenever the test succeeds.
Run the exact threshold search from Section 3 using the compressed simulation. At its successful threshold \(T^\star\), obtain covered bundle patterns \(b^1,\ldots,b^s\) with multiplicities \(k_1,\ldots,k_s\), where
\(\displaystyle \sum_i k_i=N,\qquad S:=\sum_i k_i b^i\le Q,\qquad \sum_g w_gb^i_g\ge T^\star\ge\sigma.\)
Let \(R=Q-S\) be the unallocated supply. Choose one occurrence of any covered bundle \(b^i\) and replace that occurrence by \(b^i+R\).
This replacement remains admissible, because
\(\displaystyle b^i+R=Q-(S-b^i)\le Q,\)
and \(S-b^i\) is coordinatewise nonnegative. It preserves the number of bundles and changes their total supply to exactly \(Q\). Nonnegative valuations ensure that adding \(R\) preserves the utility guarantee.
Dividing weights by \(D\), every resulting bundle satisfies
\(\displaystyle v(b)\ge\frac{\sigma}{D}=\theta.\)
The partition still has \(O(m)\) patterns. If \(T^\star=0\), use \(Q\) once and the empty bundle \(N-1\) times instead. Since \(T^\star\ge\sigma\), this case has \(\sigma=0\), so that partition is also valid.
Repeating this procedure independently for every type supplies all the partitions required in Section 1.
The denominator product \(D\) has binary length at most the sum of the binary lengths of the input denominators. Consequently, the integers \(w_g\) and \(V\) have polynomial binary length.
The threshold search uses \(O(1+\log(V+1))\) tests, hence polynomially many. Each test performs \(O(m^2)\) arithmetic operations. All counts are bounded by supplies or by \(N\), and the intermediate integer values also have polynomial binary length. The procedure therefore runs in time polynomial in \(m,\log N,L\) for each type.
Finally, output the masses
\(\displaystyle x_{t,b^{t,i}}=\frac{a_tk_{t,i}}{N}\)
from Section 1, combining duplicate bundles within each type if necessary. These are binary rationals of polynomial encoding length: each is obtained from an input rational by multiplication by an integer at most \(N\) and division by \(N\). There are \(O(\tau m)\) supported type–bundle pairs, and every bundle has \(m\) binary-encoded coordinates bounded by \(Q\).
Section 1 verifies the required type masses, exact supply equalities, and threshold conditions. This completes the polynomial-time construction and the proof.
⟨structured verdict parsed — rendered above⟩
The argument resolves the target in substance: every valid instance is feasible, and the stated construction runs in polynomial time. I found no major gap. There is one minor imprecision in the bit-complexity discussion.
Section 1 is correct.
For each type, the multiplicities describe exactly \(N\) integral bundles whose total supply is \(Q\). Assigning mass \(a_tk_{t,i}/N\) gives total type mass \(a_t\). Summing consumption over types gives exactly \(Q_g\), because \(\sum_t a_t=N\).
Every mass is nonnegative and rational. Each supported bundle satisfies its own type’s threshold. The argument does not require integral population masses.
Combining repeated bundles within a type preserves all these identities.
The citation supports the stated guarantee. Algorithm 3 uses one largest remaining item followed by smallest remaining items; Lemma 3 gives the bound \(\frac23(\operatorname{OPT}-1)\) for identical valuations and thresholds. The accompanying discussion explicitly addresses this variant of the algorithm. [Hosseini, Searns, and Segal-Halevi, Section 5.1](https://arxiv.org/html/2109.01925v3)
The hypotheses are satisfied here: the conceptual expanded instance is finite, item values are positive after omitting zero-valued copies, and the threshold under consideration is positive. The expansion is used for correctness, not as an algorithmic step.
If \(\theta>0\), an optimal \(d\)-partition gives \(d\) disjoint threshold-meeting bundles. Hence \(\operatorname{OPT}(\theta)\ge d\). The numerical deduction is correct:
\[ \frac23(d-1)\ge N-\frac23>N-1. \]
Integrality therefore gives at least \(N\) covered bundles. This includes \(N=1\). The case \(\theta=0\) is handled separately.
The denominator product \(D\) is positive and makes every weight \(w_g\) a nonnegative integer. There are finitely many integral \(d\)-partitions of \(Q\), so the scaled MMS value \(\sigma\) is an attained nonnegative integer.
The monotonicity proof is valid:
The stopping condition causes no gap: the higher run’s remaining total is at least \(U\), and the lower run retains a superset of those items, so it cannot stop for insufficient total value before this iteration.
Thus \(P\) is monotone. The endpoints are valid: \(P(0)\) holds by definition, and \(P(V+1)\) fails because even all items together have value only \(V\). Since \(P(\sigma)\) holds, integer binary search returns \(T^\star\ge\sigma\).
When \(V=0\), the endpoints are already adjacent and the search returns zero.
The simulation correctly reproduces the expanded algorithm up to its first \(N\) covered bundles.
One remaining type. Every bundle requires exactly \(\lceil T/w_h\rceil\) copies. If the batch does not reach \(N\), fewer than that many copies remain, whose total value is below \(T\).
Singletons. When \(w_h\ge T\), each largest item immediately covers a bundle. Batching these copies is exact.
Two-type bundles. When \(w_h<T\), the stated ceiling is exactly the number of smallest items needed after taking one largest item. While both types remain available in those quantities, every expanded iteration produces the same pattern. The minimum defining the batch size prevents overconsumption.
Boundary crossings. Taking the minimum of the available multiplicity and the ceiling of the remaining deficit reproduces the smallest-item filling rule. The initial smallest type is exhausted because its available multiplicity is strictly below the required number. The total-value check guarantees eventual completion.
Operation count. A batch either finishes the test, exhausts a type, or leaves too few smallest items for another identical bundle. In the last case, the next boundary-crossing bundle exhausts a type, unless the test terminates. Since exhaustion is permanent, there are \(O(m)\) recorded patterns and \(O(m^2)\) arithmetic operations.
Zero-valued goods can remain outside the simulation and be included in the final remainder.
The remainder modification is correct.
For any chosen occurrence, \(S-b^i\) is coordinatewise nonnegative, and therefore
\[ 0\le b^i+R=Q-(S-b^i)\le Q. \]
Replacing that occurrence preserves the number of bundles, allocates exactly the full supply, and cannot decrease value. In the compressed representation, this decreases the old pattern’s multiplicity by one and introduces at most one additional pattern; a zero multiplicity is omitted.
The zero-threshold branch is valid because \(T^\star=0\) implies \(\sigma=0\). For \(N=1\), the empty-bundle multiplicity is zero and is simply omitted.
The denominator product, scaled weights, total value, search thresholds, and actual supply counts have polynomial binary length. The search uses polynomially many tests, and each test uses polynomially many arithmetic operations.
The final bundles have coordinates bounded by \(Q\). Their multiplicities are at most \(N\), and the masses \(a_tk_{t,i}/N\) have polynomial encoding length. Thus the claimed support bound and total construction time follow.
There is one minor wording issue:
Location: Section 6, “All counts are bounded by supplies or by \(N\).”
Issue: If “counts” includes the computed requirement \(r\), this statement is false. For example, take weights \(100,1\), supplies \(2,1\), \(N=1\), and test threshold \(151\). The two-type formula gives \(r=51\), exceeding every supply count and \(N\), although the test can complete through a boundary-crossing bundle.
Minimum clarification: Restrict the bounded-count assertion to actual consumed, remaining, and recorded multiplicities, and explicitly include the computed ceiling parameters in the polynomial-bit-length assertion. This is an expositional correction; it does not affect correctness or polynomial running time.
The output establishes universal feasibility and a polynomial-time explicit construction for the exact input representation in the task. No exact MMS computation is required. The sole issue is minor wording in the complexity justification.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.