Answer: —
Theorem 3.7 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven a chore division problem 𝐼= (N, M, v) with bivalued utilities, Algorithm 1 finds a PO and EF1 allocation in poly(𝑛,𝑚) time. The algorithm starts with an (x, p) that is guaranteed to be an equilibrium. Then, it proceeds in iterations. The value 𝑘, maintained by the algorithm, signifies the current iteration number.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set \(T\) of complete easy/difficult worker types with rational mass vector \(\mu\), chore classes \(R\), rational \(p>1\), and rational per-capita supplies \(\rho\), find a finite-support rational kernel \(y_{t,B}\) over integer bundles \(B\in\mathbb Z_{\ge 0}^{R}\), where \(d_t(B)=\sum_{r\in R}d_t(r)B_r\) and \(d_t(r)\in\{1,p\}\), satisfying \(\sum_B y_{t,B}=\mu_t\) and \(\sum_{t,B}y_{t,B}B_r=\rho_r\), such that every ordered pair of supported assignments \((t,B),(u,D)\) satisfies chore-EF1—either \(B=\varnothing\) or some \(r\) with \(B_r>0\) has \(d_t(B-\mathbf e_r)\le d_t(D)\)—and no feasible \(y'\) admits a type-preserving coupling \(\pi_{t,B,D}\) with weak cost improvement everywhere and strict improvement on positive mass.
A society is given by its support: a nonempty list \(T\) of \(\tau\) complete worker 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=|R|\) chore classes, binary-rational per-capita supplies \(\rho_r\ge0\), and a common binary-rational \(p>1\). Each type specifies \(d_t(r)\in\{1,p\}\) for every class; constant-cost types are allowed. Write \(d_t(B)=\sum_r d_t(r)B_r\).
A feasible allocation is a finite-support nonnegative rational array \(y_{t,B}\), over integer bundles \(B\in\mathbb Z_{\ge0}^{R}\), satisfying \(\sum_B y_{t,B}=\mu_t\) and \(\sum_{t,B}y_{t,B}B_r=\rho_r\) for every \(r\). Bundles and rational entries are encoded in binary.
It is EF1 if every ordered pair \((t,B),(u,D)\) with \(y_{t,B}>0\) and \(y_{u,D}>0\) satisfies \(B=\mathbf0\) or \(d_t(B-\mathbf e_r)\le d_t(D)\) for some \(r\) with \(B_r>0\), where \(\mathbf e_r\) is the unit bundle of class \(r\).
It is Pareto optimal if no feasible allocation \(y'\) admits a nonnegative rational coupling \(\pi_{t,B,D}\) with \(\sum_D\pi_{t,B,D}=y_{t,B}\), \(\sum_B\pi_{t,B,D}=y'_{t,D}\), and \(d_t(D)\le d_t(B)\) whenever \(\pi_{t,B,D}>0\), with \(\sum_{t,B,D:\,d_t(D)<d_t(B)}\pi_{t,B,D}>0\). The competing allocation need not satisfy EF1.
Is finding a feasible EF1 and Pareto-optimal allocation solvable in polynomial time in \(m,\tau,L\), or is it NP-hard, where \(L\) is the total input bit length?
For finite lists of agents and individual bivalued chores, an EF1 and Pareto-optimal allocation always exists and can be found in polynomial time ([verified result](https://www.cs.toronto.edu/~nisarg/papers/chores.pdf)).
No result settling the exact support-encoded mass problem above was identified in the literature search.
The general polynomial-time versus NP-hardness question remains unresolved here. I prove several additional results:
For completeness, I also give self-contained proofs of existence and polynomial-size witnesses, using only the supplied finite-agent existence theorem as an external result.
Throughout, repeated occurrences of the same pair $(t,B)$ are combined by summing their masses.
Fix a feasible allocation $y$. Define
$$
x_{tr}=\sum_B y_{t,B}B_r,
\qquad
n_t=\sum_r x_{tr},
\qquad
h_{tr}=\frac{d_t(r)-1}{p-1}\in\{0,1\}.
$$
Thus
$$
d_t(r)=p^{h_{tr}}.
$$
Construct a directed multigraph $G_x$ with vertex set $T$. For every triple $(s,t,r)$ with $x_{sr}>0$, include an arc from $s$ to $t$, labeled $r$, of weight
$$
w(s,t,r)=h_{tr}-h_{sr}.
$$
Every arc weight belongs to $\{-1,0,1\}$.
The following conditions are equivalent:
$$
\sum_{t,r}h_{tr}z_{tr}
$$
over nonnegative matrices satisfying
$$
\sum_r z_{tr}=n_t,
\qquad
\sum_t z_{tr}=\rho_r.
$$
$$
0\le k_t\le\tau-1,
\qquad
0\le j_r\le\tau,
$$
satisfying
$$
j_r\le k_t+h_{tr}
$$
for every pair $(t,r),$ with equality whenever $x_{tr}>0$.
Suppose $G_x$ has a negative cycle. Choose one having the minimum possible number of arcs. It is simple: a closed walk with a repeated vertex splits into shorter closed walks, and if its total weight is negative, at least one of those walks has negative weight.
Write its distinct vertices as
$$
t_1,\ldots,t_\ell,
$$
with indices interpreted cyclically. Let the arc from $t_i$ to $t_{i+1}$ have label $r_i$. In particular,
$$
x_{t_i r_i}>0.
$$
I claim that every vertex satisfies
$$
h_{t_i r_{i-1}}\le h_{t_i r_i}.
$$
Otherwise, at some vertex $v=t_i$, the incoming class is difficult and the outgoing class is easy. Let $s=t_{i-1}$ and $u=t_{i+1}$. The sum of the two incident arc weights is
$$
1-h_{s r_{i-1}}+h_{u r_i}.
$$
Because $x_{s r_{i-1}}>0$, there is also an arc directly from $s$ to $u$ labeled $r_{i-1}$. Its weight satisfies
$$
h_{u r_{i-1}}-h_{s r_{i-1}}
\le 1-h_{s r_{i-1}}
\le 1-h_{s r_{i-1}}+h_{u r_i}.
$$
Replacing the two arcs by this shortcut produces a shorter negative cycle, a contradiction. If the original cycle has two vertices, this shortcut is a loop of weight zero, and the displayed inequality already contradicts negativity.
For every $i$, choose a supported bundle $B_i$ of type $t_i$ containing a chore of class $r_i$. Such a bundle exists because $x_{t_i r_i}>0$. Define
$$
D_i=B_i-\mathbf e_{r_i}+\mathbf e_{r_{i-1}}.
$$
These bundles are nonnegative integer bundles and have the same cardinalities as $B_i$. Their cost changes are
$$
d_{t_i}(D_i)-d_{t_i}(B_i)
=(p-1)\bigl(h_{t_i r_{i-1}}-h_{t_i r_i}\bigr)
\le0.
$$
Moreover,
$$
\sum_{i=1}^{\ell}
\bigl(h_{t_i r_{i-1}}-h_{t_i r_i}\bigr)
=
\sum_{i=1}^{\ell}w(t_i,t_{i+1},r_i)<0,
$$
so at least one participating type strictly improves.
Set
$$
\varepsilon=\min_i y_{t_i,B_i}>0.
$$
Begin with the identity coupling, and for each $i$ redirect mass $\varepsilon$ from $B_i$ to $D_i$. The participating types are distinct, so each original array entry is modified at most once. If $D_i=B_i$, the corresponding modification simply cancels.
The resulting allocation is feasible because
$$
\sum_i(D_i-B_i)=\mathbf0.
$$
The coupling is rational, every worker weakly improves, and at least mass $\varepsilon$ strictly improves. Consequently, $y$ is not Pareto optimal.
This argument also proves the promised local property: whenever Pareto optimality fails, an improvement exists using at most $\tau$ supported bundles, with each affected worker exchanging one outgoing chore for one incoming chore.
Suppose $G_x$ has no negative cycle. Add a new source with a zero-weight arc to every type, and let $a_t$ be its shortest-path distance to $t$.
The distances are integers. A shortest path can be chosen simple, so after its initial source arc it uses at most $\tau-1$ arcs. Since each arc has weight at least $-1$, and a direct zero-weight source arc is available,
$$
-(\tau-1)\le a_t\le0.
$$
For every arc labeled $r$ from $s$ to $t$,
$$
a_t-a_s\le h_{tr}-h_{sr}.
$$
Set
$$
k_t=-a_t,
\qquad
j_r=\min_t(k_t+h_{tr}).
$$
These integers have the asserted bounds.
If $x_{sr}>0$, the displayed shortest-path inequality implies, for every $t$,
$$
k_s+h_{sr}\le k_t+h_{tr}.
$$
Therefore
$$
j_r=k_s+h_{sr}.
$$
This establishes condition 4.
Assume condition 4, and define positive rational numbers
$$
\lambda_t=p^{k_t},
\qquad
q_r=p^{j_r}.
$$
Then
$$
q_r\le\lambda_t d_t(r),
$$
with equality whenever $x_{tr}>0$.
For every nonnegative matrix $z$ having the prescribed class supplies,
$$
\sum_{t,r}\lambda_t d_t(r)z_{tr}
\ge
\sum_r q_r\rho_r
=
\sum_{t,r}\lambda_t d_t(r)x_{tr}.
$$
Because every $\lambda_t$ is positive, an aggregate Pareto improvement would strictly decrease the left-hand weighted cost. Hence condition 5 holds.
To see that condition 5 implies condition 1, let $y'$ and $\pi$ be a coupling Pareto improvement and put
$$
z_{tr}=\sum_D y'_{t,D}D_r.
$$
For every type,
$$
\sum_r d_t(r)(x_{tr}-z_{tr})
=
\sum_{B,D}\pi_{t,B,D}
\bigl(d_t(B)-d_t(D)\bigr).
$$
Every summand is nonnegative. Positive mass strictly improves, so at least one type has a strict aggregate decrease. This contradicts condition 5.
Together with the negative-cycle argument, these implications establish the equivalence of conditions 1, 2, 4, and 5.
Under condition 4, put
$$
a_t=-k_t,
\qquad
b_r=j_r.
$$
Then
$$
a_t+b_r\le h_{tr},
$$
with equality on the positive entries of $x$.
Every matrix $z$ with the prescribed row and column sums therefore satisfies
$$
\sum_{t,r}h_{tr}z_{tr}
\ge
\sum_t a_t n_t+\sum_r b_r\rho_r
=
\sum_{t,r}h_{tr}x_{tr}.
$$
Thus condition 2 implies condition 3.
Conversely, the coupling improvement constructed from a negative cycle preserves every participating worker’s bundle size. Its aggregate assignment consequently preserves all row sums $n_t$. Its transportation objective changes by
$$
\varepsilon\sum_i w(t_i,t_{i+1},r_i)<0.
$$
Thus a negative cycle contradicts condition 3. This completes the proof. $\square$
The graph has $\tau$ vertices and at most $\tau^2m$ arcs. Negative-cycle detection is polynomial-time. The aggregate quantities $x_{tr}$ can be computed exactly in polynomial time in the explicit allocation length.
The integer certificate in condition 4 has polynomial encoding length. Its corresponding rational weights also do: if $p$ has binary encoding length at most $L$, then $p^{k_t}$ and $p^{j_r}$ have encoding length bounded by a polynomial in $\tau$ and $L$.
Two further consequences follow directly from the graph definition:
Neither consequence asserts independence of EF1 from $p$.
The local exchange theorem can be strengthened to a polynomial-time construction. Repeatedly making local exchanges alone would not establish a polynomial running-time bound.
Given an explicitly listed feasible rational allocation $y$, a Pareto-optimal feasible rational allocation $\widehat y$ and a rational coupling from $y$ to $\widehat y$ can be computed in polynomial time in the input and allocation lengths, such that:
If $y$ is not Pareto optimal, the coupling gives positive mass a strict improvement.
Index the positive entries of $y$ by atoms $a$. An atom has type $t(a)$, original bundle $B_a$, and mass $w_a>0$. Define its integer counts
$$
K_a=\sum_r(B_a)_r,
\qquad
H_a=\sum_r h_{t(a)r}(B_a)_r.
$$
Consider the rational linear program
$$
\min_{z\ge0}\ \sum_{a,r}h_{t(a)r}z_{ar}
$$
subject to
$$
\sum_r z_{ar}=w_aK_a,
$$
$$
\sum_r h_{t(a)r}z_{ar}\le w_aH_a,
$$
and
$$
\sum_a z_{ar}=\rho_r.
$$
The initial assignment $z_{ar}=w_a(B_a)_r$ is feasible. The feasible region is bounded, since each variable is bounded by its class supply. The program has polynomially many variables and constraints, with polynomial-length rational coefficients. Exact rational linear programming therefore gives an optimal rational solution $z^*$ of polynomial encoding length.
It remains to realize $z^*$ by integer bundles while respecting the constraints separately for every original atom.
Fix an atom $a$, and let
$$
\beta_a=\frac{\sum_r h_{t(a)r}z^*_{ar}}{w_a}.
$$
Then
$$
0\le\beta_a\le H_a\le K_a.
$$
Write
$$
b_a=\lfloor\beta_a\rfloor,
\qquad
\delta_a=\beta_a-b_a.
$$
Use two count profiles:
| Easy count | Difficult count | Conditional mass |
|---|---|---|
| $K_a-b_a$ | $b_a$ | $1-\delta_a$ |
| $K_a-b_a-1$ | $b_a+1$ | $\delta_a$ |
Discard a row of zero mass. Every retained count is nonnegative. If $\delta_a>0$, the integer inequalities $\beta_a\le H_a\le K_a$ imply
$$
b_a+1\le H_a\le K_a.
$$
Thus every profile has exactly $K_a$ chores and at most $H_a$ difficult chores.
The expected difficult count is $\beta_a$, and the expected easy count is $K_a-\beta_a$.
For each category whose expected count is positive, select a class in that category with probability proportional to $z^*_{ar}$, and put all chores of that category in the selected class. Make the easy and difficult selections independently. A category with zero expected count is omitted; its count is zero in every retained profile.
This produces integer bundles whose mean class quantities, conditional on atom $a$, are exactly
$$
\frac{z^*_{ar}}{w_a}.
$$
Assign their unconditional masses by multiplying by $w_a$. Record these masses as coupling entries from $B_a$ to the generated bundles, combining repeated occurrences.
Every generated bundle $D$ has cardinality $K_a$ and difficult count at most $H_a$. Therefore
$$
d_{t(a)}(D)
\le K_a+(p-1)H_a
=d_{t(a)}(B_a).
$$
The resulting allocation $\widehat y$ is feasible and weakly improves every worker.
I now prove that it is Pareto optimal. Suppose otherwise. Theorem 1 supplies a cyclic improvement of $\widehat y$ that preserves individual bundle sizes and weakly decreases every affected worker’s difficult count, with a strict decrease for some positive mass.
Compose that cyclic coupling with the constructed coupling from $y$ to $\widehat y$. Explicitly, if the first coupling is $\pi$ and the cyclic coupling is $\sigma$, composition uses
$$
\widetilde\pi_{t,B,E}
=
\sum_{D:\,\widehat y_{t,D}>0}
\frac{\pi_{t,B,D}\sigma_{t,D,E}}
{\widehat y_{t,D}}.
$$
This is a finite rational coupling with the required marginals.
Every worker originating from atom $a$ still has exactly $K_a$ chores and at most $H_a$ difficult chores. Its aggregate class quantities therefore give another feasible solution of the linear program. The positive strict decrease in difficult counts gives a strictly smaller objective, contradicting optimality of $z^*$.
If $y$ was not Pareto optimal, its negative-cycle improvement already gives a feasible solution of the same program with objective strictly below the initial value. Hence the optimal value is strictly smaller, and the constructed weak-improvement coupling must have positive strict-improvement mass.
There are at most two profiles and polynomially many class pairs per atom. Floors, probabilities, bundle coordinates, and generated masses all have polynomial binary length. Thus the entire construction is polynomial-time. $\square$
Write
$$
S=\sum_r\rho_r.
$$
For $S=0$, the allocation giving every worker the empty bundle is feasible, EF1, and Pareto optimal.
The following constructions work with arbitrary support size.
If
$$
0<S\le1,
$$
an EF1 and Pareto-optimal allocation can be found in polynomial time.
Set
$$
n_t=S\mu_t.
$$
Find a matrix $x$ minimizing the binary transportation objective from Theorem 1, with row sums $n_t$ and column sums $\rho_r$.
This transportation problem is feasible: the matrix
$$
x_{tr}=\frac{n_t\rho_r}{S}
$$
has the required margins. It is bounded and has polynomial-size rational data, so an optimum can be found in polynomial time.
Define
$$
y_{t,\mathbf e_r}=x_{tr},
\qquad
y_{t,\mathbf0}=\mu_t-n_t=\mu_t(1-S).
$$
Discard zero entries.
These entries have the prescribed masses and supplies, and their aggregate assignment is $x$. Every nonempty supported bundle is a singleton. Removing its sole chore leaves cost zero, so every ordered EF1 comparison holds.
Transportation optimality and Theorem 1 establish Pareto optimality. $\square$
Suppose
$$
S=k\in\mathbb Z_{\ge2},
\qquad
p(k-1)\le k.
$$
Then an EF1 and Pareto-optimal allocation can be found in polynomial time.
Choose a transportation-optimal matrix $x$ with row sums
$$
n_t=k\mu_t
$$
and column sums $\rho_r$, as above. Define
$$
y_{t,k\mathbf e_r}=\frac{x_{tr}}{k}.
$$
The type-mass equations follow from
$$
\sum_r\frac{x_{tr}}k=\mu_t.
$$
The class-supply equations follow because each such bundle contains $k$ chores of its class. Its aggregate assignment is again $x$, so Theorem 1 gives Pareto optimality.
Every supported bundle contains exactly $k$ chores. For any comparing type $t$, removing one chore from its own bundle leaves cost at most
$$
p(k-1)\le k.
$$
Every other supported bundle has cost at least $k$ under $d_t$. Thus every ordered EF1 comparison holds.
The integer $k$ may be numerically large, but its binary length is polynomial in the input length. The construction has at most $\tau m$ entries and uses polynomial-length rational operations. $\square$
For example, Proposition 4 covers arbitrary supported types and supplies with $S=2$ and $1<p\le2$.
Theorem 2 preserves each worker’s bundle size, but it need not preserve EF1. The following example proves a stronger limitation: specified type-average bundle sizes can admit an EF1 allocation and a Pareto-optimal allocation, while admitting no allocation satisfying both.
Take three classes $a,b,c$, three types of mass $1/3$, and $p=2$:
| Type | $d_t(a)$ | $d_t(b)$ | $d_t(c)$ | Initial bundle |
|---|---|---|---|---|
| $1$ | $2$ | $1$ | $1$ | $3\mathbf e_c$ |
| $2$ | $2$ | $1$ | $2$ | $\mathbf e_a$ |
| $3$ | $1$ | $1$ | $1$ | $\mathbf e_b+\mathbf e_c$ |
The supplies are
$$
\rho_a=\frac13,
\qquad
\rho_b=\frac13,
\qquad
\rho_c=\frac43,
$$
and the aggregate type chore counts are
$$
n_1=1,
\qquad
n_2=\frac13,
\qquad
n_3=\frac23.
$$
Type $1$ has own cost $3$ and residual cost $2$ after removing a chore. Both other bundles have cost $2$ under $d_1$.
Type $2$ holds a singleton, so its residual cost is zero.
Type $3$ has residual cost $1$; every supported bundle has cost at least $1$ under $d_3$.
These observations verify all ordered EF1 comparisons.
Exchange the class-$a$ chore of type $2$ with the class-$b$ chore of type $3$. The bundles become
$$
3\mathbf e_c,
\qquad
\mathbf e_b,
\qquad
\mathbf e_a+\mathbf e_c.
$$
Own costs change from
$$
(3,2,2)
\quad\text{to}\quad
(3,1,2).
$$
Thus this is a Pareto improvement preserving every bundle size.
The resulting allocation is Pareto optimal: every assigned chore is easy for its recipient, so its binary transportation objective is zero.
It is not EF1. Type $1$ still has residual cost $2$, whereas the type-$2$ bundle has cost $1$ under $d_1$.
Suppose an allocation has these supplies, masses, and aggregate type counts and is Pareto optimal. The displayed improved allocation shows that the minimum transportation objective for these margins is zero. Theorem 1 therefore forces the supposed allocation also to assign only easy chores.
Type $2$ can receive only class $b$. Its aggregate count $1/3$ uses the entire class-$b$ supply. Hence type $1$, whose easy classes are $b$ and $c$, can receive only class $c$.
Type $2$ has average bundle size
$$
\frac{n_2}{\mu_2}=1.
$$
Consequently, some supported type-$2$ bundle is $j\mathbf e_b$ with integer $j\le1$.
For every nonempty supported type-$1$ bundle $q\mathbf e_c$, EF1 relative to that bundle requires
$$
q-1\le j\le1,
$$
so $q\le2$. Empty bundles also have size at most $2$. This contradicts type $1$’s required average bundle size
$$
\frac{n_1}{\mu_1}=3.
$$
Thus no EF1 and Pareto-optimal allocation preserves these aggregate type counts. In particular, selecting suitable type-average chore counts is a genuine part of the general construction problem.
I use the supplied finite-agent theorem: every finite chore instance with a common pair of costs $\{1,p\}$ admits an EF1 and Pareto-optimal integral allocation. Constant-cost agents are permitted by the bivalued definition. See [Ebadian, Peters, and Shah, Definition 2.4 and Theorem 3.7](https://www.cs.toronto.edu/~nisarg/papers/chores.pdf).
Choose an integer $Q$ clearing all input mass and supply denominators. Expand the instance into
$$
Q\mu_t
$$
agents of type $t$ and
$$
Q\rho_r
$$
individual chores of class $r$. Apply the finite theorem, and let $y_{t,B}$ be the number of agents of type $t$ receiving bundle $B$, divided by $Q$.
This allocation is feasible and EF1.
Its aggregate graph cannot contain a negative cycle. Indeed, the exchange argument in Theorem 1 would select one actual finite agent of each participating type and cyclically exchange their chores, giving an integral Pareto improvement of the finite allocation. That contradicts its Pareto optimality.
Theorem 1 now establishes Pareto optimality under the required rational-coupling definition.
The expansion may be exponentially large; this is an existence proof, not a polynomial-time algorithm.
For a supported nonempty bundle $B$ of type $t$, let
$$
M_t(B)=\max_{r:\,B_r>0}d_t(r).
$$
Removing a maximum-cost chore minimizes the residual cost. Thus EF1 implies
$$
d_t(B)-M_t(B)\le d_t(D)
$$
for every supported bundle $D$, regardless of its holder’s type.
Average over the population, whose total mass is one:
$$
d_t(B)-M_t(B)\le d_t(\rho).
$$
Since $M_t(B)\le p$ and $d_t(\rho)\le pS$,
$$
\sum_r B_r\le d_t(B)\le p(S+1).
$$
Therefore every supported bundle has cardinality at most
$$
K=\lfloor p(S+1)\rfloor.
$$
The binary length of $K$ is polynomial in the input length.
Start with an existing EF1 and Pareto-optimal allocation. Take its positive weighted-cost certificate from Theorem 1. Every supported pair $(t,B)$ satisfies
$$
\lambda_t d_t(B)=\sum_r q_rB_r.
$$
Associate to that pair the integer column
$$
(\mathbf e_t,B)\in\mathbb Z^{\tau+m}.
$$
Consider nonnegative reweightings of these finitely many columns satisfying the original type-mass and class-supply equations. The resulting polytope is nonempty and bounded.
At a vertex, the columns with positive weights are linearly independent. Otherwise, a nonzero dependence supported on those columns would permit sufficiently small perturbations in both directions while retaining nonnegativity and all equations. Hence a vertex has at most
$$
m+\tau
$$
positive entries.
Reweighting to such a vertex preserves:
Finally, the vertex weights have polynomial binary length. To verify this explicitly, put $N=m+\tau$ and clear the right-hand-side denominators with an integer $Q_0$ of polynomial binary length. A vertex with $k\le N$ positive weights is determined by an invertible $k$-by-$k$ integer submatrix.
All coefficient entries are bounded by $K$. If $V$ bounds the absolute cleared right-hand-side entries, Cramer’s rule gives weight denominators bounded in absolute value by
$$
Q_0\,k!K^k
$$
and numerators bounded by
$$
k!\max\{K,V\}^k.
$$
Both bounds have polynomial binary length. There are at most $N$ bundles, each with polynomial-length coordinates.
Thus every instance has a polynomial-size EF1 and Pareto-optimal witness. Feasibility and EF1 can be checked directly, and Theorem 1 supplies a polynomial-time Pareto test.
These results remove existence, output size, Pareto verification, and Pareto improvement of a supplied allocation as obstacles.
They do not give a polynomial-time method for choosing an EF1-compatible efficient allocation for arbitrary support and arbitrary supplies. The obstruction in Section 4 shows why optimizing assignments at previously chosen type-average chore counts is insufficient.
No general polynomial-time construction or hardness reduction is proved here.
⟨structured verdict parsed — rendered above⟩
Overall assessment: valid partial results; the general complexity question remains unresolved.
The proofs establish the stated Pareto characterization, the polynomial-time improvement procedure for an explicitly supplied allocation, both restricted construction regimes, the obstruction example, and existence of polynomial-size witnesses. I found no substantive mathematical error in those arguments.
The output does not resolve USER_TASK: it supplies neither a polynomial-time construction for arbitrary support-encoded inputs nor a hardness reduction. This is an acknowledged limitation, not a concealed gap in a claimed general solution.
Assessment: correct.
Since $p>1$ and $d_t(r)\in\{1,p\}$,
$$
h_{tr}=\frac{d_t(r)-1}{p-1}\in\{0,1\},
\qquad
d_t(r)=p^{h_{tr}}.
$$
The aggregate quantities are finite rational numbers because the allocation has finite rational support.
An arc labeled $r$ from $s$ exists precisely when some positive-mass bundle of type $s$ contains class $r$. Thus the subsequent selection of an outgoing chore from a supported bundle is justified.
The minimum-length negative-cycle argument is valid. A repeated vertex would split the closed walk into shorter closed walks, at least one of which is negative.
The shortcut calculation correctly rules out a vertex whose incoming class is difficult and outgoing class is easy. The shortcut exists because its source holds positive aggregate quantity of the incoming class. Its weight is no larger than the sum of the replaced weights.
The two-vertex case is also correctly covered: the shortcut is a zero-weight loop, contradicting negativity under the displayed inequality. A negative one-vertex cycle is impossible because every loop has weight zero.
Consequently,
$$
h_{t_i r_{i-1}}\le h_{t_i r_i}
$$
at every participating vertex. The proposed bundles are nonnegative, preserve cardinality, and weakly decrease individual cost.
The identity
$$
\sum_i\bigl(h_{t_i r_{i-1}}-h_{t_i r_i}\bigr)
=
\sum_i w(t_i,t_{i+1},r_i)
$$
is correct by cyclic reindexing. Negativity therefore guarantees a strict improvement at some participating vertex.
The choice
$$
\varepsilon=\min_i y_{t_i,B_i}
$$
is positive and rational. Distinct participating types prevent competing withdrawals from the same source entry. Equal exchange masses preserve every class supply because the bundle changes sum to zero. The resulting coupling satisfies the task’s workerwise improvement requirements.
The shortest-path construction is valid when there are no negative cycles. Removing nonnegative closed subwalks allows a shortest path to be chosen simple, giving
$$
-(\tau-1)\le a_t\le0.
$$
The signs in the conversion to $k_t=-a_t$ are correct:
$$
a_t-a_s\le h_{tr}-h_{sr}
\quad\Longrightarrow\quad
k_s+h_{sr}\le k_t+h_{tr}.
$$
Taking the minimum over $t$ gives equality at every positive pair $(s,r)$. The bounds on $k_t$ and $j_r$ follow as stated.
Zero-supply classes cause no difficulty: their certificate inequalities still hold, and no equality is required at an unused pair.
The passage to positive weights
$$
\lambda_t=p^{k_t},
\qquad
q_r=p^{j_r}
$$
is valid because exponentiation by $p>1$ preserves order. The weighted lower bound holds for every nonnegative real aggregate assignment with the prescribed column sums.
Any aggregate Pareto improvement would strictly decrease this weighted objective because every $\lambda_t$ is positive.
A rational coupling improvement induces an aggregate improvement through the displayed coupling identity. All summands are nonnegative, and positive strict-improvement mass gives a strict decrease for at least one type. Hence the implication to the task’s Pareto optimality is justified.
The transportation lower-bound calculation uses the prescribed row and column sums correctly.
Conversely, the negative-cycle exchange preserves row sums and strictly decreases the binary transportation objective. Together with the previously established implications, this proves all five conditions equivalent.
The graph size, exact aggregate computation, certificate encoding bounds, and the two stated invariance consequences are also justified.
Assessment: correct.
The initial aggregate assignment satisfies every constraint. Nonnegativity and the class-supply equations bound every variable, so the feasible region is bounded.
The number of variables and constraints is polynomial in the explicit allocation length and input length. Products such as $w_aK_a$ have polynomial binary length even when $K_a$ is numerically large. The invocation of exact rational linear programming is appropriate for this feasible, bounded rational program.
The two difficult-count profiles have the stated mean $\beta_a$. When $\delta_a>0$, integrality of $H_a$ and $K_a$ ensures
$$
b_a+1\le H_a\le K_a,
$$
so every retained profile is valid.
The class-selection construction has the claimed mean quantities. Within a category, the selected-class probability is proportional to the corresponding $z^*_{ar}$; multiplying by the category’s expected count gives $z^*_{ar}/w_a$. A zero-expectation category has zero count in every positive-mass profile.
Thus every generated bundle preserves cardinality, has at most the original difficult count, and weakly improves its originating worker. The masses and recorded coupling are rational.
The contradiction argument is valid. A negative-cycle improvement preserves cardinality and weakly decreases difficult count, with a strict decrease on positive mass.
The displayed coupling-composition formula has the required marginals; its denominators are restricted to positive intermediate masses. Tracking the originating atoms through this composition gives another feasible solution of the atom-level linear program. Its objective is strictly smaller, contradicting optimality.
If the original allocation is inefficient, its negative-cycle improvement already supplies a strictly better feasible linear-program solution. Hence the constructed weak improvement must include positive strict-improvement mass.
There are only polynomially many profiles and class combinations per atom. No step enumerates individual chores. The output and coupling therefore have polynomial encoding length.
Assessment: both propositions are correct.
For $S=0$, nonnegativity and zero supplies force every positive-mass bundle to be empty. The stated allocation is feasible, EF1, and Pareto optimal.
For $0<S\le1$:
For integer $S=k\ge2$ with $p(k-1)\le k$:
The binary encoding argument for potentially large $k$ is sound. These remain restricted regimes, not a classification of arbitrary inputs.
Assessment: correct.
The supplies and aggregate counts match the displayed allocation.
All initial EF1 comparisons are verified correctly. The proposed exchange changes own costs from
$$
(3,2,2)
\quad\text{to}\quad
(3,1,2),
$$
preserves supplies and bundle sizes, and is a Pareto improvement.
The resulting allocation has zero binary transportation objective, proving its optimality for those margins. Its failure of EF1 is correctly witnessed by type $1$ comparing against the type-$2$ singleton.
For any Pareto-optimal allocation with the same margins, Theorem 1 forces objective zero and therefore allocation only along easy pairs. Type $2$ consequently exhausts class $b$, leaving type $1$ only class $c$.
Finite support and type $2$’s average cardinality $1$ guarantee a supported bundle $j\mathbf e_b$ with $j\le1$. EF1 then bounds every supported type-$1$ bundle’s cardinality by $2$, contradicting its required average cardinality $3$.
The example establishes the claimed limitation. It does not establish hardness, and the output does not suggest otherwise.
Assessment: correct.
The cited Definition 2.4 allows valuations taking values in a common two-element set without requiring every agent to attain both values. Constant-cost agents are therefore covered. Theorem 3.7 provides the stated finite-agent EF1 and Pareto-optimal allocation. Using utilities $-d_t$ matches its chore convention. [Ebadian, Peters, and Shah, Definition 2.4 and Theorem 3.7](https://www.cs.toronto.edu/~nisarg/papers/chores.pdf).
Clearing denominators produces integral numbers of agents and chores. Aggregating the finite allocation preserves feasibility and all required EF1 comparisons.
The transfer of Pareto optimality is justified rather than assumed: a negative aggregate cycle would select distinct actual agents and yield an integral Pareto improvement of the finite allocation. Theorem 1 then excludes rational-coupling improvements.
The output correctly identifies this potentially exponential expansion as an existence proof.
Removing a maximum-cost chore minimizes residual cost. Averaging the EF1 comparison over the entire population is legitimate because total mass is one and aggregate supply is $\rho$.
The resulting inequalities
$$
|B|\le d_t(B)\le p(S+1)
$$
are correct. Taking the floor gives the claimed integer cardinality bound. Its binary length is polynomial in the input length.
The reweighting polytope is nonempty and bounded: each column belongs to one type, and its weight is bounded by that type’s mass.
The linear-dependence perturbation argument correctly proves that a vertex uses at most $m+\tau$ columns.
Retaining a subset of support preserves EF1. The weighted-cost certificate remains valid on every retained bundle and therefore preserves Pareto optimality.
The Cramer’s-rule bounds are valid. Type-indicator coefficients are also bounded by $K$, since $K\ge1$. Clearing right-hand-side denominators has polynomial binary length, and the determinant bounds give polynomial-length rational weights.
Thus polynomial-size witnesses and polynomial-time verification are established. Neither fact supplies a polynomial-time method for finding a witness.
Major incompleteness — the requested general classification is absent.
The output explicitly states:
No general polynomial-time construction or hardness reduction is proved here.
No clarification of the existing arguments can close this omission. Resolving USER_TASK requires an additional general algorithm with a polynomial bit-complexity analysis, or a hardness reduction under a precisely stated reduction notion for the search problem.
There are no additional mathematical issues requiring repair in the partial results audited above.
⟨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.