Answer: Polynomial-time solvable; every valid instance is feasible.
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIn chore allocation with factored cost func- tions, HFFD with the thresholds of all agents equal to their maximin share always allocates all chores.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational masses \(\mu_t\) for finitely many complete agent types, rational per-capita supplies \(q_j\) of finitely many chore classes, and positive rational factored costs \(v_t(j)\), define \(\theta_t\) as the minimum \(\theta\) admitting a finite rational distribution \(y\) over integral bundles \(b\) in \(\mathbb{Z}_+^r\) with \(\sum_b y_b=1\), \(\sum_b b_j y_b=q_j\), and \(v_t(b)\le\theta\) on its support. Compute, or decide feasibility of, a finite rational distribution \(x_{t,b}\) satisfying \(\sum_b x_{t,b}=\mu_t\), \(\sum_{t,b} b_j x_{t,b}=q_j\), and \(v_t(b)\le\theta_t\) whenever \(x_{t,b}>0\).
A society is given by its support: the list of \(\tau\) complete types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) chore classes with positive binary-rational per-capita supplies \(q_j\). Type \(t\) specifies positive rational additive costs \(v_t(j)\); its distinct costs, sorted increasingly as \(a_{t,1}<\cdots<a_{t,k_t}\), satisfy \(a_{t,\ell+1}/a_{t,\ell}\in\mathbb Z_{\geq2}\). These integer ratios may vary by level and type.
Bundles are \(b\in\mathbb Z_{\geq0}^{m}\), including the empty bundle, with \(v_t(b)=\sum_jv_t(j)b_j\). Let \(L\) be the total binary input length; bundle coordinates are encoded in binary.
Define \(\theta_t\) as the minimum \(\theta\geq0\) admitting a finitely supported rational distribution \(y_b\geq0\) with \(\sum_b y_b=1\), \(\sum_b b_jy_b=q_j\) for every \(j\), and \(v_t(b)\leq\theta\) whenever \(y_b>0\).
The allocation problem is to compute finitely supported rational masses \(x_{t,b}\geq0\), or decide their feasibility, subject to \(\sum_bx_{t,b}=\mu_t\), \(\sum_{t,b}b_jx_{t,b}=q_j\), and \(v_t(b)\leq\theta_t\) whenever \(x_{t,b}>0\). The thresholds are defined by the input, not supplied separately.
Is this distributional allocation problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite societies with explicitly listed chores and factored additive costs, HFFD at the agents’ MMS thresholds allocates all chores, and an exact MMS allocation is computable in polynomial time ([Garg–Huang–Segal-Halevi](https://arxiv.org/html/2411.04391v1)). Factored-cost MMS values and optimal partitions are also polynomial-time computable ([Ebadian–Peters–Shah](https://www.ifaamas.org/Proceedings/aamas2022/pdfs/p372.pdf)).
No result settling this exact distributional formulation was located in the literature search.
The problem is solvable in deterministic polynomial time in \(m,\tau,L\). Every valid instance is feasible. Moreover, all thresholds can be computed exactly, and an allocation can be output using at most \(\tau(2m+1)\) nonzero type–bundle masses, each of polynomial binary encoding length.
The exact threshold formula is
\( \displaystyle \theta_t= \max_{1\leq \ell\leq k_t} a_{t,\ell} \left\lceil \sum_{\{j:\,v_t(j)\geq a_{t,\ell}\}} \frac{v_t(j)}{a_{t,\ell}}\,q_j \right\rceil . \)
We prove the formula and give a constructive algorithm.
Once threshold-attaining distributions \(y^t\) have been computed, define
\( \displaystyle x_{t,b}=\mu_t y^t_b. \)
Then
\( \displaystyle \sum_b x_{t,b}=\mu_t, \qquad \sum_{t,b}b_jx_{t,b} =\sum_t\mu_t q_j=q_j, \)
and every positive mass respects its type’s threshold.
Thus feasibility follows directly from the threshold definitions, provided the minima are attained. The substantive computational task is to find threshold-attaining distributions with polynomially bounded representations. The following lemma establishes both attainment and efficient construction under the factored-cost hypothesis.
Let \(w_1,\ldots,w_m\) be positive integers satisfying
\( \displaystyle 1=w_1\leq w_2\leq\cdots\leq w_m, \qquad w_i\mid w_{i+1}\quad(1\leq i<m). \)
Equal consecutive weights are allowed. For an integer \(C\geq0\), define
\( \displaystyle B_C=\left\{ b\in\mathbb Z_{\geq0}^m: \sum_{j=1}^m w_jb_j\leq C \right\}, \qquad d_i=w_i\left\lfloor\frac{C}{w_i}\right\rfloor, \)
and
\( \displaystyle Q_C=\left\{ z\in\mathbb R_{\geq0}^m: \sum_{j=i}^m w_jz_j\leq d_i \text{ for every }i \right\}. \)
Lemma. We have \(\operatorname{conv}(B_C)=Q_C\). Every rational point of \(Q_C\) can be decomposed into a rational convex combination of at most \(2m+1\) elements of \(B_C\), in polynomial time in its binary input length.
For \(b\in B_C\), the integer \(\sum_{j=i}^m w_jb_j\) is a multiple of \(w_i\), because \(w_i\) divides every later weight. It is also at most \(C\). Consequently,
\( \displaystyle \sum_{j=i}^m w_jb_j \leq w_i\left\lfloor\frac{C}{w_i}\right\rfloor=d_i. \)
These linear inequalities also hold for convex combinations. Hence \(\operatorname{conv}(B_C)\subseteq Q_C\).
The sequence \(d_1,\ldots,d_m\) is nonincreasing: \(d_{i+1}\) is a multiple of \(w_i\) at most \(C\), whereas \(d_i\) is the largest such multiple.
For a nonempty index set \(S=\{p_1<\cdots<p_s\}\), construct \(b(S)\) by
\( \displaystyle b(S)_{p_h}= \begin{cases} (d_{p_h}-d_{p_{h+1}})/w_{p_h},&h<s,\\ d_{p_s}/w_{p_s},&h=s, \end{cases} \)
and set all other coordinates to zero. Also define \(b(\varnothing)=0\).
These coordinates are nonnegative integers. Indeed, the numerators are nonnegative, and \(w_{p_h}\) divides both terms in each difference.
If \(p_h\) is the first member of \(S\) at least \(i\), telescoping gives
\( \displaystyle \sum_{j=i}^m w_jb(S)_j=d_{p_h}\leq d_i. \)
If no such member exists, the sum is zero. Therefore \(b(S)\in Q_C\); its total weighted cost is at most \(d_1=C\), so \(b(S)\in B_C\).
Start with \(z\in Q_C\), and initialize a remaining mass \(\alpha=1\) and a residual vector \(r=z\). Maintain
\( \displaystyle \alpha\geq0,\qquad r_j\geq0,\qquad s_i:=\alpha d_i-\sum_{j=i}^m w_jr_j\geq0. \)
Suppose \(\alpha>0\). Let \(S=\{j:r_j>0\}\), choose \(b=b(S)\), and define
\( \displaystyle h_i=d_i-\sum_{j=i}^m w_jb_j\geq0. \)
We first establish the property that makes the procedure terminate: every currently zero coordinate or slack remains zero when a mass of \(b\) is removed.
If \(r_j=0\), then \(j\notin S\), so \(b_j=0\).
If \(s_i=0\) and \(p_h\) is the first member of \(S\) at least \(i\), then the tails of \(r\) starting at \(i\) and at \(p_h\) coincide. Thus feasibility at \(p_h\) gives
\( \displaystyle \alpha d_i =\sum_{j=p_h}^m w_jr_j \leq\alpha d_{p_h} \leq\alpha d_i. \)
Since \(\alpha>0\), it follows that \(d_i=d_{p_h}\). The telescoping identity for \(b(S)\) now gives \(h_i=0\). If there is no member of \(S\) at least \(i\), then \(s_i=\alpha d_i=0\), so again \(h_i=0\).
Choose
\( \displaystyle \delta= \min\left( \{\alpha\} \cup \left\{\frac{r_j}{b_j}:b_j>0\right\} \cup \left\{\frac{s_i}{h_i}:h_i>0\right\} \right). \)
All included ratios are strictly positive: a positive denominator cannot correspond to a zero numerator, by the property just proved. Record the mass \(\delta\) on bundle \(b\), and update
\( \displaystyle \alpha\leftarrow\alpha-\delta, \qquad r\leftarrow r-\delta b. \)
The new upper-constraint slacks are \(s_i-\delta h_i\). The choice of \(\delta\) therefore preserves all invariants.
If the new \(\alpha\) is zero, the first upper constraint and nonnegativity imply \(r=0\). Otherwise, at least one previously positive coordinate \(r_j\) or slack \(s_i\) becomes zero. All zero coordinates and slacks remain zero in subsequent iterations.
There are only \(2m\) coordinates and upper-constraint slacks. Hence the procedure terminates after at most \(2m+1\) iterations. Writing its recorded outputs as \((\delta_h,b^h)\), telescoping the updates yields
\( \displaystyle \sum_h\delta_h=1, \qquad z=\sum_h\delta_h b^h. \)
Every \(b^h\) belongs to \(B_C\). This proves \(Q_C\subseteq\operatorname{conv}(B_C)\), and all recorded masses are rational when \(z\) is rational.
The case \(C=0\) has only the point \(z=0\), so assume \(C\geq1\).
Choose an initial common denominator \(D_0\) for the coordinates of \(z\), for example the product of their input denominators. Its binary length is polynomial in the input length.
If \(\alpha\) and all coordinates of \(r\) have common denominator \(D\), so do all slacks \(s_i\). The denominators \(b_j\) and \(h_i\) appearing in the ratios above are integers between \(1\) and \(C\). Thus, after an update, a common denominator can be chosen as \(Dg\) for some integer \(1\leq g\leq C\); choosing \(\delta=\alpha\) allows \(g=1\).
After at most \(2m+1\) updates, a common denominator is therefore bounded by
\( \displaystyle D_0C^{\,2m+1}. \)
Its binary length is polynomial. Also, \(\alpha\leq1\), \(r_j\leq C\), and \(s_i\leq C\), so the corresponding numerators have polynomial binary length.
Each iteration uses a polynomial number of exact arithmetic operations and comparisons. This proves the algorithmic assertion of the lemma.
Fix a type \(t\). Reorder its chore classes by nondecreasing cost, and write \(a=a_{t,1}\). Define
\( \displaystyle w_j=\frac{v_t(j)}a. \)
The factored-cost hypothesis implies that these are positive integers satisfying the lemma’s divisibility conditions, with \(w_1=1\). Supplies are reordered by the same permutation.
Every bundle cost is an integer multiple of \(a\). Consequently, a threshold \(\theta\) allows exactly the bundles in \(B_C\), where
\( \displaystyle C=\left\lfloor\frac{\theta}{a}\right\rfloor. \)
By the lemma, a rational distribution over these bundles with mean \(q\) exists exactly when
\( \displaystyle \sum_{j=i}^m w_jq_j \leq w_i\left\lfloor\frac C{w_i}\right\rfloor \quad\text{for every }i. \)
For each \(i\), this is equivalent to
\( \displaystyle C\geq w_i\left\lceil \sum_{j=i}^m\frac{w_j}{w_i}q_j \right\rceil. \)
Indeed, the first inequality says that the integer \(\lfloor C/w_i\rfloor\) is at least the displayed rational sum, and therefore at least its ceiling.
It follows that the least feasible integer capacity is
\( \displaystyle C_t= \max_{1\leq i\leq m} w_i\left\lceil \sum_{j=i}^m\frac{w_j}{w_i}q_j \right\rceil. \)
Applying the lemma at \(C_t\) constructs a rational distribution with mean \(q\) and maximum cost at most \(aC_t\). Conversely, every admissible threshold \(\theta\) has \(\lfloor\theta/a\rfloor\geq C_t\), and hence \(\theta\geq aC_t\). Therefore
\( \displaystyle \theta_t=aC_t. \)
Within a block of equal costs, the suffix beginning at the first class in that block has the largest sum. All other suffix conditions in the block are redundant. Grouping these equal-cost blocks gives precisely
\( \displaystyle \theta_t= \max_{1\leq \ell\leq k_t} a_{t,\ell} \left\lceil \sum_{\{j:\,v_t(j)\geq a_{t,\ell}\}} \frac{v_t(j)}{a_{t,\ell}}q_j \right\rceil. \)
This establishes the minimum in the question, including its attainment by a finitely supported rational distribution.
For each listed type \(t\):
This produces masses \(y^t_b\) on at most \(2m+1\) bundles, satisfying
\( \displaystyle \sum_b y^t_b=1,\qquad \sum_b b_jy^t_b=q_j,\qquad y^t_b>0\Longrightarrow v_t(b)\leq\theta_t. \)
Output \(x_{t,b}=\mu_t y^t_b\), merging repeated bundles for a type if necessary. Section 1 verifies all allocation constraints.
Finally, normalization, ceiling calculations, and decomposition all have polynomial bit complexity. To see explicitly that the capacities have polynomial binary length, observe that
\( \displaystyle C_t\leq \sum_jw_jq_j+\max_jw_j. \)
This follows from \(\lceil u\rceil\leq u+1\). Each normalized weight and supply has polynomial binary length, so the bound has polynomial binary length as well. The decomposition’s denominator bound then applies, and multiplying its masses by the input masses \(\mu_t\) preserves polynomial encoding length.
The algorithm processes only the \(\tau\) listed types. It never expands binary supplies into an explicit list of chores or constructs a finite society.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the assigned distributional problem: every valid instance is feasible, the thresholds are computed exactly, and an allocation with polynomial encoding length is constructed in deterministic polynomial time. No major or minor mathematical issues were found.
The proof is self-contained. It does not rely on transferring the cited finite-society results to this distributional setting.
The construction \(x_{t,b}=\mu_t y^t_b\) is valid once each \(y^t\) is a rational threshold-attaining distribution with mean \(q\).
The type-mass constraint follows from \(\sum_b y^t_b=1\). The aggregate supply calculation is correct because every type’s distribution has the same mean \(q\) and \(\sum_t\mu_t=1\). Multiplication by a positive rational \(\mu_t\) preserves rationality and the permitted bundle support.
Attainment is initially identified as a dependency and is subsequently proved in Section 3. There is no circular reasoning.
For every suffix beginning at \(i\), each later weight is divisible by \(w_i\). Therefore the suffix cost of an integer bundle is an integer multiple of \(w_i\). Its upper bound by \(C\) implies its upper bound by \(d_i\).
Passing these inequalities to convex combinations is valid.
The monotonicity of \(d_i\) is correctly justified: \(d_{i+1}\) is a multiple of \(w_i\) bounded by \(C\), and \(d_i\) is the largest such multiple.
For consecutive selected indices \(p_h,p_{h+1}\), divisibility ensures that both \(d_{p_h}\) and \(d_{p_{h+1}}\) are divisible by \(w_{p_h}\). Thus every specified bundle coordinate is a nonnegative integer.
The suffix sums telescope exactly as asserted. They are bounded by the corresponding \(d_i\), and the total cost is bounded by \(d_1=C\), using \(w_1=1\). Consequently every constructed bundle belongs to \(B_C\).
These arguments remain valid with repeated weights, zero differences between successive \(d_i\), and weights exceeding \(C\). In particular, the construction does not require every selected coordinate to receive a positive bundle coordinate.
The coordinate argument follows directly from the definition of \(S\).
For a zero slack \(s_i\), the displayed chain of inequalities is valid: the residual suffixes at \(i\) and its first supported index \(p_h\) agree, feasibility bounds that suffix by \(\alpha d_{p_h}\), and monotonicity gives \(d_{p_h}\leq d_i\). Since \(\alpha>0\), equality forces \(d_i=d_{p_h}\), which gives \(h_i=0\).
When no supported index remains in that suffix, \(s_i=\alpha d_i=0\) likewise implies \(h_i=0\). Thus all cases needed for zero-slack preservation are covered.
Every included ratio in the definition of \(\delta\) is strictly positive, for the reasons supplied. The minimum is defined because \(\alpha\) is always included.
The updated slack is exactly \(s_i-\delta h_i\), so the minimum preserves all nonnegativity constraints. If \(\alpha\) becomes zero, the first suffix inequality forces the residual vector to vanish.
If \(\alpha\) remains positive, some coordinate or slack becomes newly zero. Previously zero quantities remain zero. Counting the \(2m\) coordinates and slacks therefore justifies the bound of \(2m+1\) iterations, including a possible final iteration that exhausts \(\alpha\).
Telescoping the updates establishes both the total recorded mass and the required mean. The construction applies to real points for the convex-hull equality; rational input produces rational coefficients for the algorithmic assertion.
The denominator argument is correct.
Given a common denominator \(D\) for \(\alpha\) and the residual coordinates, all slacks also have denominator \(D\), since the weights and capacities are integers. A selected ratio introduces at most one additional integer denominator \(g\), with \(1\leq g\leq C\). All updated quantities consequently admit common denominator \(Dg\).
The constructed positive bundle coordinates and positive \(h_i\) are indeed integers bounded by \(C\). The cumulative denominator bound \(D_0C^{2m+1}\) therefore follows.
The numerator bounds also hold: the first suffix constraint gives \(r_j\leq C\), while \(\alpha\leq1\) and \(s_i\leq C\). Recorded masses are bounded by \(1\) and have denominators dividing a later common denominator. Bundle coordinates themselves are bounded by \(C\).
Thus the iteration count, arithmetic operand lengths, and output lengths are polynomial in the complete lemma input length. The separately handled case \(C=0\) is valid.
Normalization by the smallest cost yields positive integer weights forming a divisibility chain. This follows from the stated integer ratios between consecutive distinct cost levels; repeated costs give equal weights.
Every bundle cost is an integer multiple of \(a\), so the allowed bundle set at threshold \(\theta\) is exactly \(B_{\lfloor\theta/a\rfloor}\).
The convex-hull characterization supplies necessary conditions for a mean-\(q\) distribution. Its rational decomposition supplies sufficiency with precisely the finite rational distributions required by the task.
The conversion of a suffix inequality into a capacity lower bound is correct: an integer \(\lfloor C/w_i\rfloor\) exceeds the rational suffix sum exactly when it exceeds that sum’s ceiling. Hence the maximum of the displayed integer lower bounds is the least feasible capacity.
The construction at \(C_t\), together with the lower bound on every admissible \(\theta\), proves both \(\theta_t=aC_t\) and attainment.
Within a block of equal weights, the first suffix has the largest sum and the same capacity multiplier. Therefore discarding the remaining suffix conditions in that block gives exactly the claimed formula over distinct cost levels.
The final capacity estimate follows from the ceiling bound, since each suffix weighted sum is at most the full weighted sum. Normalized weights, rational sums, capacities, and thresholds all have polynomial binary encoding length.
Applying the decomposition once per listed type and multiplying its masses by \(\mu_t\) preserves polynomial encoding length. Restoring the class order preserves the original supply coordinates and costs.
The support bound of \(\tau(2m+1)\) follows directly from the per-type decomposition bound. Merging duplicates cannot increase it.
The algorithm depends on the listed support size \(\tau\), handles binary-encoded supplies without expanding chores, and computes the thresholds from the input. It therefore addresses the exact formulation in USER_TASK.
Actionable feedback: No mathematical repair or additional clarification is needed.
⟨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.