Answer: Polynomial-time solvable; every valid input is feasible.
Theorem 4.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven an additive chores instance, a 1-out-of- 2𝑛 3 MMS allocation exists and can be computed in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational population masses \(\mu_t\) over complete additive valuation types \(t\in T\), rational per-capita supplies \(\sigma_j\) of \(q\) replicated indivisible chore categories, and \(\sum_t\mu_t=1\), define \(\theta_{t,2/3}\) as the maximum \(\lambda\) for which a finite-support distribution \(y_b\) over integral bundles \(b\in\mathbb{Z}_{\ge0}^{q}\) satisfies \(\sum_b y_b=2/3\), \(\sum_b b_jy_b=\sigma_j\) for every \(j\), and \(v_t\cdot b\ge\lambda\) whenever \(y_b>0\). Compute a finite-support mass assignment \(x_{t,b}\ge0\) satisfying \(\sum_bx_{t,b}=\mu_t\), \(\sum_{t,b}b_jx_{t,b}=\sigma_j\), and \(v_t\cdot b\ge\theta_{t,2/3}\) whenever \(x_{t,b}>0\).
A society is given by its support: the list of the \(\tau=|T|\) types with positive mass, each with its mass \(\mu_t\) as a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m=q\ge1\) replicated indivisible chore categories, with binary rational per-capita supplies \(\sigma_j\ge0\). Each type has a complete additive valuation vector \(v_t\in\mathbb Q_{\le0}^{m}\). Bundles are arbitrary \(b\in\mathbb Z_{\ge0}^{m}\), including the empty bundle, valued at \(v_t\cdot b\).
Define \(\theta_{t,2/3}\) as the maximum \(\lambda\in\mathbb R\) admitting finitely supported nonnegative real weights \(y_b\) with \(\sum_b y_b=2/3\), \(\sum_b b_jy_b=\sigma_j\) for every \(j\), and \(v_t\cdot b\ge\lambda\) whenever \(y_b>0\).
The computational problem is to find finitely supported nonnegative rational masses \(x_{t,b}\) satisfying \(\sum_bx_{t,b}=\mu_t\), \(\sum_{t,b}b_jx_{t,b}=\sigma_j\) for every \(j\), and \(v_t\cdot b\ge\theta_{t,2/3}\) whenever \(x_{t,b}>0\), or report infeasibility. Thresholds are defined by the input, not supplied separately; bundle coordinates are encoded in binary. Let \(L\) be the total input bit length.
Is this mass-assignment problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For finite societies with \(n\ge2\) agents and additive nonpositive chore valuations, a complete \(1\)-out-of-\(\lfloor2n/3\rfloor\) MMS allocation always exists and can be computed in strongly polynomial time. [Source](https://arxiv.org/html/2201.07424).
No result settling this exact distribution-over-types problem was identified in the literature search.
The problem is polynomial-time solvable in \(m,\tau,L\). Every valid input is feasible. The construction below avoids computing the thresholds exactly.
Proof, first reducing to integer costs. Fix a type \(t\). Choose a positive integer \(D\) clearing the denominators of its valuations, and put \(a_j=-Dv_{t,j}\). Thus \(a_j\) are nonnegative integers and \(v_t\cdot b=-a\cdot b/D\).
Coordinates with \(\sigma_j=0\) must be zero in every positive-mass bundle, because all bundle coordinates and masses are nonnegative. Coordinates with \(a_j=0\) do not affect the threshold. Temporarily retain only
\[ J=\{j:\sigma_j>0,\ a_j>0\}. \]
Write \(d=|J|\), and regard \(a\) and \(\sigma\) as vectors on these coordinates. Zero-cost coordinates will be restored later.
For an integer \(C\ge0\), define
\[ K(C)=\{b\in\mathbb Z_{\ge0}^{d}:a\cdot b\le C\}. \]
Let \(C^*\) be the smallest integer \(C\) for which there are nonnegative weights on \(K(C)\) satisfying
\[ \sum_b y_b=\frac23, \qquad \sum_b b_jy_b=\sigma_j\quad(j\in J). \]
This minimum exists. Indeed, put
\[ H=\sum_{j\in J}a_j\left\lceil\frac32\sigma_j\right\rceil. \]
Round each coordinate of \(\frac32\sigma\) randomly to its floor or ceiling, preserving its expectation. This gives a finitely supported probability distribution whose bundles have cost at most \(H\). Multiplying its probabilities by \(\frac23\) supplies the required witness. Hence \(C^*\le H\).
Moreover,
\[ \theta_{t,2/3}=-\frac{C^*}{D}. \]
To verify this equality, any full threshold witness with value bound \(\lambda\) has integer costs at most \(\lfloor-D\lambda\rfloor\); its projection onto \(J\) therefore implies \(C^*\le\lfloor-D\lambda\rfloor\). Consequently \(\lambda\le-C^*/D\). Conversely, a witness at \(C^*\) can be extended to the zero-cost coordinates by taking its product with a probability distribution having mean \(\frac32\sigma_j\) on those coordinates. The extended weights have mass \(\frac23\), the correct supplies, and cost at most \(C^*\).
If \(J\) is empty, this argument gives \(C^*=0\) and \(\theta_{t,2/3}=0\).
Lemma: a polynomial-size family of configurations suffices with factor \(\frac43\). Suppose \(d\ge1\), \(a\in\mathbb Z_{>0}^{d}\), and \(C\ge1\). A family \(R(C)\subseteq K(C)\) of size \(O((d+1)^4)\) can be constructed in polynomial time such that every \(b\in K(C)\) admits nonnegative rational weights \(z_r\) satisfying
\[ \sum_{r\in R(C)}z_rr=b, \qquad \sum_{r\in R(C)}z_r\le\frac43. \]
Call coordinate \(j\) large if \(a_j>C/4\), and small otherwise. Enumerate every feasible configuration \(g\) supported on large coordinates. Each contains at most three items, since four large items would have total cost greater than \(C\). There are therefore at most \(\binom{d+3}{3}\) such configurations.
Include every such \(g\) in \(R(C)\). For each small coordinate \(j\), also include
\[ g+\left\lfloor\frac{C-a\cdot g}{a_j}\right\rfloor e_j. \]
These configurations are feasible by construction, and their number is at most \((d+1)\binom{d+3}{3}\).
To prove the representation property, fix \(b\in K(C)\). Let \(g\) be its large-coordinate part, and put
\[ r=C-a\cdot g, \qquad s=\sum_{j\text{ small}}a_jb_j\le r. \]
For each small coordinate with \(b_j>0\), define
\[ q_j=\left\lfloor\frac r{a_j}\right\rfloor\ge1, \qquad Q=\sum_{\substack{j\text{ small}\\b_j>0}}\frac{b_j}{q_j}. \]
If \(Q\le1\), assign weight \(b_j/q_j\) to \(g+q_je_j\), and weight \(1-Q\) to \(g\). This reproduces \(b\) exactly with total weight \(1\).
Now suppose \(Q>1\). Assign weight \(b_j/(Qq_j)\) to \(g+q_je_j\). These weights sum to \(1\), reproduce \(g\), and reproduce \(b_j/Q\) of each small coordinate. The uncovered amount is
\[ h_j=b_j\left(1-\frac1Q\right), \]
with total cost
\[ W=\sum_{j\text{ small}}a_jh_j =s\left(1-\frac1Q\right). \]
We claim \(W\le C/4\). If \(r\le C/4\), this follows from \(W\le s\le r\). If \(r>C/4\), then
\[ q_ja_j>r-a_j\ge r-C/4, \]
so
\[ Q\le\frac{s}{r-C/4}. \]
It follows that
\[ W=s-\frac sQ \le s-r+\frac C4 \le\frac C4. \]
For every small coordinate, the homogeneous configuration \(q_j^0e_j\), where \(q_j^0=\lfloor C/a_j\rfloor\), belongs to \(R(C)\), using \(g=0\). Furthermore,
\[ q_j^0a_j>C-a_j\ge\frac{3C}{4}. \]
Cover the remaining amount \(h_j\) with weight \(h_j/q_j^0\) on this homogeneous configuration. The additional total weight is at most
\[ \sum_{j\text{ small}}\frac{h_j}{q_j^0} \le\frac{4W}{3C} \le\frac13. \]
Together with the weight \(1\) already assigned, this proves the bound \(\frac43\). All constructed weights are rational. This completes the lemma.
Using the lemma to test a capacity. For the fixed type, and any integer \(C\ge1\), construct \(R(C)\) and solve the explicit rational linear program
\[ P(C)= \min\left\{ \sum_{r\in R(C)}z_r: \sum_{r\in R(C)}r_jz_r=\sigma_j\ (j\in J),\ z_r\ge0 \right\}. \]
If it is infeasible, set \(P(C)=+\infty\). Call the capacity successful when \(P(C)\le1\). For nonempty \(J\), declare capacity zero unsuccessful.
Every integer \(C\ge C^*\) is successful. Indeed, take a threshold witness of mass \(\frac23\), whose bundles belong to \(K(C)\). Apply the lemma to each bundle and multiply its representation weights by the bundle’s witness mass. The resulting configurations reproduce the supplies exactly and have total mass at most
\[ \frac43\cdot\frac23=\frac89<1. \]
Thus
\[ C\ge C^*\quad\Longrightarrow\quad P(C)\le\frac89. \]
In particular, failure at a capacity certifies \(C<C^*\).
Finding a safe capacity without computing \(C^*\). Initialize integer endpoints \(\ell=-1\) and \(h=H\). Capacity \(H\) is successful, as proved above; save its LP solution.
While \(h-\ell>1\), test \(c=\lfloor(\ell+h)/2\rfloor\).
The invariants are that \(h\) is successful and \(\ell<C^*\). A failed test preserves the latter invariant by the implication just proved.
At termination, \(h=\ell+1\). Since \(C^*\) is an integer and \(\ell<C^*\),
\[ h=\ell+1\le C^*. \]
This argument does not require the success predicate to be monotone below \(C^*\).
The saved solution at \(h\) has total mass at most \(1\). Add the missing mass on the empty bundle. We obtain a rational probability distribution \(p\) with mean \(\sigma\) on \(J\), every bundle of which has cost at most \(h\le C^*\).
Restoring zero-cost coordinates and assigning types. A rational probability distribution with prescribed nonnegative rational coordinate means can be constructed with at most one more bundle than the number of coordinates.
Explicitly, for a desired mean \(u_j\), write \(u_j=k_j+f_j\), where \(k_j=\lfloor u_j\rfloor\) and \(0\le f_j<1\). For a uniform parameter \(U\) on \([0,1]\), use coordinate
\[ k_j+\mathbf1_{\{U<f_j\}}. \]
The resulting bundle is constant between consecutive distinct fractional parts. Interval lengths give rational probabilities, and its coordinate expectations equal \(u_j\).
Use this construction with \(u_j=\sigma_j\) for the zero-cost coordinates, and take its product with \(p\). Set all zero-supply coordinates to zero. Denote the resulting full probability distribution by \(p_t\). It has mean \(\sigma\), and every positive-probability bundle satisfies
\[ v_t\cdot b =-\frac{a\cdot b}{D} \ge-\frac{C^*}{D} =\theta_{t,2/3}. \]
For a type with \(J\) empty, construct \(p_t\) directly on its zero-cost coordinates.
Do this independently for every type, and output
\[ x_{t,b}=\mu_t p_{t,b}. \]
Then
\[ \sum_bx_{t,b}=\mu_t, \qquad \sum_{t,b}b_jx_{t,b} =\sum_t\mu_t\sigma_j =\sigma_j, \]
and every positive-mass bundle meets its type’s threshold.
Polynomial running time and output size. Clearing denominators by their product gives \(D\), the integer costs, and \(H\) with bit lengths polynomial in \(L\). The search uses \(O(\log(H+1))\) LP calls.
Each LP has \(O((m+1)^4)\) variables and at most \(m\) equality constraints. Its configuration coordinates are bounded by \(H\), so its explicit rational matrix has polynomial encoding length. The standard polynomial-time theorem for rational linear programming therefore applies: feasibility and the finite optimum can be computed exactly in polynomial bit time.
An optimal basic solution has at most \(d\) positive variables. Its coefficients have polynomial bit length by the determinant bounds for basic solutions. Adding the empty bundle gives at most \(d+1\) bundles; restoring zero-cost coordinates by the product construction gives at most \((m+1)^2\) bundles per type. Multiplication by \(\mu_t\) preserves polynomial encoding length.
Consequently both the computation and the complete rational output have size polynomial in \(m,\tau,L\). No expansion into a finite society is required.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes polynomial-time solvability for the stated binary encoding and proves that every valid input is feasible. I found no major or minor issues requiring correction.
Clearing valuation denominators produces nonnegative integer costs \(a_j=-Dv_{t,j}\), with \(D>0\), preserving the valuation inequalities exactly.
The removal of zero-supply coordinates is justified: a sum of nonnegative terms can equal zero only if every positive-mass bundle has zero in that coordinate. Removing zero-cost coordinates does not change bundle values, and the later product construction restores their required supplies.
On the retained coordinates, all costs and supplies are strictly positive. Thus \(K(C)\) is finite for every nonnegative integer \(C\). If \(J\) is empty, the separate treatment correctly gives threshold zero.
The rounding construction has coordinate expectations \(\frac32\sigma_j\), and each rounded coordinate is at most \(\left\lceil\frac32\sigma_j\right\rceil\). Consequently every resulting bundle has cost at most \(H\). Scaling the probability distribution by \(\frac23\) gives exactly the required mass and supplies.
This establishes that the set of feasible integer capacities is nonempty, so its smallest member \(C^*\) exists.
The threshold identity has both required directions. Any threshold witness has integer bundle costs at most \(\lfloor-D\lambda\rfloor\), forcing \(\lambda\le-C^*/D\). Conversely, a witness at \(C^*\), extended on zero-cost coordinates, attains value bound \(-C^*/D\). Hence the maximum in the task’s definition is attained, and
\[
\theta_{t,2/3}=-C^*/D.
\]
A feasible configuration contains at most three large-coordinate items because each such item costs strictly more than \(C/4\). This counts repeated items as well as distinct coordinates.
The bound \(\binom{d+3}{3}\) therefore correctly bounds the number of possible large-coordinate configurations. Adding at most one extension per small coordinate gives at most
\[
(d+1)\binom{d+3}{3}
\]
configurations, which is \(O((d+1)^4)\).
Every extension is feasible by its defining floor operation. Zero residual capacity and duplicate configurations cause no difficulty.
Whenever \(b_j>0\) on a small coordinate, feasibility implies \(r\ge a_j\), so \(q_j\ge1\). Every division in the construction is therefore defined.
If \(Q\le1\), the assigned weights sum to one. The large-coordinate component is reproduced because every used configuration has the same large part \(g\); each small coordinate is reproduced by its assigned weight \(b_j/q_j\).
If \(Q>1\), the first collection of weights again sums to one, reproducing \(g\) and \(b_j/Q\) on each small coordinate. The stated residual \(h_j\) and its cost \(W=s(1-1/Q)\) are correct.
Both cases in the bound on \(W\) are valid. In particular, when \(r>C/4\), the denominator \(r-C/4\) is positive, and
\[
Q\le\frac{s}{r-C/4}
\]
implies
\[
W=s-\frac{s}{Q}\le s-r+\frac C4\le\frac C4.
\]
There is no reversal error in this inequality.
The homogeneous configurations belong to \(R(C)\), and their costs satisfy \(q_j^0a_j>3C/4\). Thus their additional total weight is at most \(4W/(3C)\le1/3\). The resulting representation reproduces \(b\) exactly with total weight at most \(4/3\). All representation weights are rational.
For every \(C\ge C^*\), a threshold witness is supported in \(K(C)\). Applying the lemma to its finitely many bundles preserves every supply equality and gives total configuration mass at most
\[
\frac43\cdot\frac23=\frac89.
\]
The witness weights may be real; this is sufficient to establish feasibility and the objective bound for the rational LP. The subsequent LP computation supplies rational output.
Therefore every \(C\ge C^*\) is successful, and failure indeed certifies \(C<C^*\). For nonempty \(J\), capacity zero cannot supply its strictly positive coordinates, so declaring it unsuccessful is correct.
The search does not assume that success is monotone below \(C^*\). Its stated invariants are sufficient:
Initially, \(H\) is successful and \(-1<C^*\). Success preserves the first invariant; failure preserves the second by the implication established above.
Each iteration shrinks the integer interval. At termination, \(h=\ell+1\), and integrality of \(C^*\) yields \(h\le C^*\). Thus the saved solution simultaneously has mass at most one and configurations meeting the required cost bound.
Adding the missing mass on the empty bundle preserves all supplies and produces a probability distribution.
The common-uniform-parameter construction for zero-cost coordinates has the claimed expectations. Its finitely many interval lengths are rational, including when fractional parts coincide or equal zero.
Taking the product preserves the retained-coordinate means and costs. Every resulting positive-probability bundle therefore meets its type’s threshold.
Finally, multiplying by \(\mu_t\) gives the required type mass, and the aggregate supply calculation is correct because \(\sum_t\mu_t=1\). The construction applies independently to every supported type.
The denominator product, integer costs, and \(H\) have polynomial bit length. The search therefore uses polynomially many LP calls, even when the numerical value of \(H\) is large.
For every tested capacity, the explicit LP has polynomially many variables and constraints, and configuration coordinates are at most \(H\). All coefficients are rational with polynomial encoding length. When feasible, its objective is bounded below by zero. These satisfy the hypotheses of polynomial-time rational linear programming. The basic-solution and determinant facts invoked for sparse rational output also apply to this standard-form LP. See the [MIT notes on LP algorithms](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html) and [basic solutions and encoding bounds](https://courses.csail.mit.edu/6.854/21/Notes/n11-lp.html).
Using the optimal basic solutions discussed in the output gives at most \(d\) positive LP variables. Adding the empty bundle and restoring zero-cost coordinates gives the stated polynomial support bound. Rational products retain polynomial bit length.
The potentially large rounding witness and the unknown threshold witness are used only to establish existence; the algorithm never enumerates them. No expansion into a finite society is required.
Repair feedback: None required. The proof settles the exact distribution-over-types problem under the stated encoding.
⟨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.