Answer: Polynomial-time solvable: feasibility holds exactly when \(\sum_{e\in E}q_e\le r\). A decision algorithm takes \(O(L+mL^2)\) bit operations.
Corollary 3.8 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe round-robin algorithm outputs a 3 2-PMMS allocation in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite worker types \(T\), rational masses \(\mu_t\), additive type costs \(c_t(e)\) for chore categories \(e\in E\), per-capita chore supplies \(q_e\), and workload cap \(r\), decide whether there exists finite-support rational mass variables \(x_{t,b}\) over integral bundles \(b\in\mathbb{Z}_{\ge 0}^{E}\) with \(\sum_e b_e\le r\), satisfying \(\sum_b x_{t,b}=\mu_t\), \(\sum_{t,b}b_e x_{t,b}=q_e\), and \(c_t(b)\le(3/2)\operatorname{MMS}_t(2,b\uplus b')\) for every positively supported pair \((t,b),(u,b')\).
A society is given by its support: a list \(T\) of \(\tau\ge1\) worker types with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) chore categories \(E\), nonnegative binary rational costs \(c_t(e)\) and per-capita supplies \(q_e\), and a binary-encoded integer workload cap \(r\ge0\). Costs are additive and need not be normalized.
Let \(B_r=\{b\in\mathbb Z_{\ge0}^{E}:\sum_e b_e\le r\}\). Each coordinate counts indivisible copies of its category; empty bundles are allowed.
For a multiset represented by \(s\), define \(\operatorname{MMS}_t(2,s)=\min_{a\in\mathbb Z_{\ge0}^{E},\,a\le s}\max\{c_t(a),c_t(s-a)\}\), with coordinatewise inequalities; these partitions have no workload restriction.
A feasible allocation consists of finitely supported nonnegative rational masses \(x_{t,b}\), indexed by \(t\in T\) and \(b\in B_r\), satisfying \(\sum_bx_{t,b}=\mu_t\) and \(\sum_{t,b}b_ex_{t,b}=q_e\) for every \(e\in E\).
It must also satisfy \(c_t(b)\le\frac32\operatorname{MMS}_t(2,b+b')\) for every ordered pair with \(x_{t,b}>0\) and \(x_{u,b'}>0\), including identical support entries; \(b+b'\) represents multiset union.
Is deciding whether such a feasible allocation exists solvable in polynomial time, or is it NP-hard? State running times in \(m\), \(\tau\), \(r\), and the total input bit length \(L\).
For finite lists of agents with nonnegative additive chore costs, round-robin computes a \(\frac32\)-PMMS allocation in polynomial time ([verified result](https://link.springer.com/article/10.1007/s10458-023-09618-5)); this result imposes no workload cap.
No result settling this exact mass feasibility problem was identified in the literature search.
The decision problem is polynomial-time solvable. More precisely, a feasible allocation exists if and only if
\( \displaystyle \sum_{e\in E}q_e\le r. \)
The key observation is that round-robin bounds each worker’s number of chores by the ceiling of the average workload. Thus the workload cap is compatible with the given fairness guarantee. The proof below establishes the needed round-robin properties directly, including for zero and non-normalized costs.
Suppose a feasible allocation exists. Summing the supply equations gives
\( \displaystyle \sum_{e\in E}q_e =\sum_{t,b}\left(\sum_{e\in E}b_e\right)x_{t,b} \le r\sum_{t,b}x_{t,b} =r\sum_t\mu_t =r. \)
The inequality uses the workload restriction on every supported bundle. Consequently, total supply exceeding \(r\) makes feasibility impossible.
Consider finitely many workers with nonnegative additive costs and finitely many individually labeled chore copies. Fix a cyclic order of the workers. On each turn, the current worker takes a remaining chore of minimum cost according to their own costs. Stop when every chore has been allocated.
Write \(A_i\) for worker \(i\)’s bundle and \(h_i=|A_i|\).
If there are \(N\) workers and \(H\) chores, every complete round gives each worker one chore, and the final incomplete round gives each worker at most one. Therefore,
\( \displaystyle h_i\le\left\lceil\frac{H}{N}\right\rceil. \)
We first prove that, for any distinct workers \(i,j\) with \(A_i\ne\varnothing\), some chore \(g\in A_i\) satisfies
\( \displaystyle c_i(A_i\setminus\{g\})\le c_i(A_j). \)
Let \(i_k\) and \(j_k\) denote their respective chores picked in round \(k\). Choose \(g=i_{h_i}\), worker \(i\)’s last pick.
If \(i\) precedes \(j\) in the cyclic order, then \(h_i-1\le h_j\). For every \(k\le h_i-1\), chore \(j_k\) was still available when \(i\) picked \(i_k\). The minimum-cost choice therefore gives \(c_i(i_k)\le c_i(j_k)\). Summing and using nonnegativity gives
\( \displaystyle c_i(A_i\setminus\{g\}) =\sum_{k=1}^{h_i-1}c_i(i_k) \le\sum_{k=1}^{h_i-1}c_i(j_k) \le c_i(A_j). \)
If \(i\) follows \(j\), then \(h_i\le h_j\). For every \(k\le h_i-1\), chore \(j_{k+1}\) was still available when \(i\) picked \(i_k\). Hence
\( \displaystyle c_i(A_i\setminus\{g\}) \le\sum_{k=1}^{h_i-1}c_i(j_{k+1}) \le c_i(A_j). \)
This proves the asserted inequality in both cases, including when removing \(g\) leaves the empty bundle.
Now put \(X=c_i(A_i)\), \(Y=c_i(A_j)\), and \(M=\operatorname{MMS}_i(2,A_i\cup A_j)\). Every partition of the union has total cost \(X+Y\), so \(2M\ge X+Y\). Moreover, the partition part containing \(g\) has cost at least \(c_i(g)\), so \(M\ge c_i(g)\). The preceding inequality implies
\( \displaystyle X-Y\le c_i(g)\le M. \)
Combining these bounds yields
\( \displaystyle 2X=(X+Y)+(X-Y)\le 2M+M=3M. \)
Thus \(c_i(A_i)\le\frac32M\). If \(A_i=\varnothing\), the same conclusion follows immediately from nonnegative costs.
This proves the required round-robin guarantee without normalization or strict positivity assumptions. It agrees with the supplied paper’s Corollary 3.1. [Fairness criteria for allocating indivisible chores](https://link.springer.com/article/10.1007/s10458-023-09618-5)
Assume \(Q:=\sum_{e\in E}q_e\le r\).
Because all masses and supplies are rational, choose a positive integer \(N\) such that every \(N\mu_t\) and every \(Nq_e\) is integral. Twice the product of their denominators is one valid choice.
Construct a finite instance with:
There are exactly \(N\) workers and \(H=NQ\) chores. Run the round-robin procedure from Section 2. Each worker receives at most
\( \displaystyle \left\lceil\frac{H}{N}\right\rceil=\lceil Q\rceil\le r \)
chores, where the last inequality uses that \(r\) is an integer.
For each worker \(i\), let \(b(i)\) be the vector counting the categories in their bundle. Define
\( \displaystyle x_{t,b} =\frac{|\{i:\text{worker }i\text{ has type }t,\ b(i)=b\}|}{N}. \)
These are nonnegative rational masses with finite support, and every supported bundle belongs to \(B_r\). Counting workers and chore copies gives
\( \displaystyle \sum_bx_{t,b}=\mu_t, \qquad \sum_{t,b}b_ex_{t,b}=q_e. \)
It remains to check every required ordered support pair.
For distinct entries \((t,b)\ne(u,b')\) with positive mass, choose workers representing those entries. They are distinct workers, so Section 2 gives
\( \displaystyle c_t(b)\le\frac32\operatorname{MMS}_t(2,b+b'). \)
Here the MMS values for labeled copies and category-count vectors coincide: every partition of labeled copies determines a vector \(a\le b+b'\), and every such vector can be realized by selecting the specified number of copies of each category. Corresponding partitions have equal costs.
For an identical support entry, observe that
\( \displaystyle \operatorname{MMS}_t(2,2b)=c_t(b). \)
Indeed, the total cost is \(2c_t(b)\), giving the lower bound \(c_t(b)\), while the partition into two copies of \(b\) attains that bound. Hence the identical-entry constraint also holds.
The aggregated allocation therefore satisfies every requirement. This proves sufficiency, including when \(r=0\) or all costs vanish.
The algorithm reads the input, computes \(Q=\sum_e q_e\) exactly, and accepts precisely when \(Q\le r\). It does not construct the replicated population.
For an explicit bit bound, write \(q_e=a_e/d_e\) with \(d_e>0\). Accumulate the sum without reducing fractions: adding \(a/d\) to \(A/D\) replaces the accumulator by numerator \(Ad+aD\) and denominator \(Dd\). All intermediate integers have \(O(L)\) bits: denominator lengths are bounded by the total input denominator length, and numerator lengths have the same bound up to the input numerator lengths and \(O(\log m)\).
Using schoolbook integer arithmetic, the \(m\) updates and final comparison require
\( \displaystyle O(L+mL^2)\subseteq O(L^3) \)
bit operations. Thus the running time is polynomial in the total input bit length \(L\). Dependence on \(\tau\) and on the numerical value of \(r\) occurs only through reading their binary-encoded input; there is no enumeration of \(B_r\) and no factor polynomial in the numerical value of \(r\).
The potentially large replication is an existence proof, while the decision algorithm is the exact supply comparison.
⟨structured verdict parsed — rendered above⟩
The prover resolves the target correctly. Feasibility is equivalent to \(\sum_e q_e\le r\), and the stated decision algorithm runs in polynomial time. I found no major or minor issues requiring repair.
Summing the supply equations is legitimate because the allocation has finite support. Each supported bundle satisfies \(\sum_e b_e\le r\), and the total allocated worker mass equals \(\sum_t\mu_t=1\). Therefore the displayed calculation correctly establishes \(\sum_e q_e\le r\).
With \(N\) workers and \(H\) chores, complete rounds allocate one chore to every worker, and the last incomplete round allocates at most one more. Thus \(h_i\le\lceil H/N\rceil\), including when \(H=0\).
Both ordering cases use valid indices and availability claims:
Minimum-cost selection gives the stated termwise inequalities. Nonnegativity justifies bounding each selected partial sum by \(c_i(A_j)\). When \(h_i=1\), the sums are empty and the inequality still holds. Consequently, removing \(i\)'s last pick gives the claimed comparison for every distinct ordered worker pair.
Every partition of the combined bundles has total cost \(X+Y\), so its larger part costs at least \((X+Y)/2\). Every partition also places the particular chore \(g\) in a part costing at least \(c_i(g)\), by nonnegativity. Hence both \(2M\ge X+Y\) and \(M\ge c_i(g)\) hold for the minimum over partitions.
The previously established comparison gives \(X-Y\le c_i(g)\le M\). The calculation \(2X=(X+Y)+(X-Y)\le3M\) is correct, even when \(X-Y\) is negative. Empty bundles satisfy the fairness inequality directly.
The external attribution is also accurate: [Corollary 3.1 of the cited paper](https://link.springer.com/article/10.1007/s10458-023-09618-5) states the polynomial-time round-robin guarantee for additive costs. The submitted argument proves the required guarantee directly, so it does not depend on importing additional hypotheses from that result.
The chosen \(N\) clears all mass and supply denominators. Each \(N\mu_t\) is a positive integer, each \(Nq_e\) is a nonnegative integer, and the worker count is exactly \(N\). The chore count is \(H=NQ\).
Since \(Q\le r\) and \(r\) is an integer, \(\lceil Q\rceil\le r\). Thus every replicated worker receives a bundle in \(B_r\). Replication may be large, but the proof uses it only to establish existence.
The proposed masses are rational, nonnegative, and finitely supported. Counting workers establishes the type-mass equations; counting labeled copies establishes every supply equation.
Distinct positive support entries necessarily have distinct representative workers. The finite fairness guarantee therefore applies, including when the two entries have the same type or the same bundle vector.
The correspondence between labeled-copy partitions and category-count partitions preserves costs in both directions. Thus it preserves the MMS value exactly, with no workload restriction imposed on partition parts.
For identical support entries, the equality \(\operatorname{MMS}_t(2,2b)=c_t(b)\) follows from the total-cost lower bound and the explicitly identified equal split. This verifies self-pair constraints even if an entry has only one representative worker.
If \(r=0\), the acceptance condition forces all supplies to vanish, and replication gives only empty bundles. Zero costs and arbitrary nonnegative cost scales do not invalidate any inequality. No positivity of bundle costs or division by a cost is used.
The algorithm decides the established equivalence by an exact rational sum and comparison.
Without fraction reduction, accumulated denominators have bit length bounded by the total denominator input length. Accumulated numerators have \(O(L)\) bits as well: their terms consist of an input numerator multiplied by other input denominators, and summing at most \(m\) terms adds at most \(O(\log m)\) bits.
Therefore schoolbook arithmetic gives the stated \(O(L+mL^2)\) bit-operation bound. Since \(m\le O(L)\), the \(O(L^3)\) upper bound follows. Dependence on \(\tau\) and the binary encoding of \(r\) is accounted for through \(L\); no dependence polynomial in the numerical value of \(r\) is needed.
No additional clarification or repair is required.
⟨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.