Answer: polynomial-time solvable
Theorem 3.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere exists an EFX allocation of chores when m ≤2n and each agent has an additive cost function. Moreover, we can find an EFX allocation in polynomial time. Our algorithm is described in Algorithm 1. If m ≤n, then an EFX allocation can be obtained by allocating at most one chore to each agent.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite cost types \(T\), rational population masses \(\mu\), chore categories \(E\), rational per-capita supplies \(\rho\) with \(\sum_{e\in E}\rho_e\le 2\), and additive costs \(c_t(e)\), find a finite-support rational assignment \(x_{t,b}\ge 0\), indexed by \(t\in T\) and \(b\in\mathbb{Z}_{\ge0}^{E}\), satisfying \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}b_e x_{t,b}=\rho_e\), such that whenever \(x_{t,b}>0\) and \(x_{u,d}>0\), every individual receiving \(b\) satisfies \(c_t(b\setminus\{e\})\le c_t(d)\) for every chore copy \(e\) in \(b\).
A society is given by its support: a nonempty list \(T\) of \(\tau\) cost types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m=|E|\) chore categories, nonnegative binary-rational supplies \(\rho_e\) with \(\sum_{e\in E}\rho_e\le 2\), and nonnegative binary-rational additive costs \(c_t(e)\); zero costs are allowed. Let \(L\) be the total input bit length.
An individual bundle is a multiplicity vector \(b\in\mathbb Z_{\ge0}^{E}\), including the empty bundle; its cost is \(c_t(b)=\sum_{e\in E}b_e c_t(e)\). Removing one copy of category \(e\) gives \(b-\mathbf1_e\).
An assignment is a finitely supported family of nonnegative rational masses \(x_{t,b}\) satisfying \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}b_e x_{t,b}=\rho_e\). It is EFX if, for every \((t,b),(u,d)\) with \(x_{t,b}>0\) and \(x_{u,d}>0\), and every \(e\) with \(b_e>0\), \(c_t(b-\mathbf1_e)\le c_t(d)\). This includes comparisons between individuals of the same type and removal of zero-cost copies.
Is finding an EFX assignment, or reporting that none exists, solvable in polynomial time in \(m,\tau,L\), or is this computational problem NP-hard?
For finitely many agents with nonnegative additive costs, an EFX allocation always exists and is computable in polynomial time when the number of chores is at most twice the number of agents ([Kobayashi–Mahara–Sakamoto](https://arxiv.org/abs/2305.04168)). The [journal version](https://doi.org/10.1016/j.tcs.2024.115010) retains this algorithmic result. No result settling the exact mass-assignment problem above was located.
1. Result. The problem is solvable in polynomial time in \(m,\tau,L\), including when costs are zero. Every instance satisfying the stated hypotheses has an EFX assignment, so the algorithm never needs to report nonexistence.
Clearing denominators and applying the [Kobayashi–Mahara–Sakamoto theorem](https://arxiv.org/abs/2305.04168) already proves existence, but may create exponentially many agents and chores. The construction below avoids that expansion. It combines batched greedy insertions with a compression lemma that handles zero-cost copies explicitly.
Throughout, bundles and masses are represented in binary. Zero-mass entries are omitted.
2. Preliminary cases and the invariant. Write \(R=\sum_e\rho_e\).
If \(R\le 1\), set
\(x_{t,\mathbf1_e}=\mu_t\rho_e\) and \(x_{t,\mathbf0}=\mu_t(1-R)\).
These masses meet every marginal constraint. Every nonempty bundle is a singleton, so every required removal leaves cost zero; hence the assignment is EFX.
If every cost is zero, another immediate construction is
\(x_{t,2\mathbf1_e}=\mu_t\rho_e/2\) and
\(x_{t,\mathbf0}=\mu_t(1-R/2)\).
Thus assume henceforth that \(1<R\le2\) and some cost is positive.
Define
\(C=\max_{t,e}c_t(e)>0\),
\(\gamma=\min\{c_t(e):c_t(e)>0\}>0\), and
\(H=1+\lceil 3C/\gamma\rceil\).
The binary encoding length of \(H\) is polynomial in \(L\).
An intermediate state allocates supplies \(\sigma_e\), where \(0\le\sigma_e\le\rho_e\). For each type \(t\), a prescribed mass \(q_t\) is designated *active*. We maintain:
An active or inactive designation is bookkeeping; it does not alter costs or the EFX comparisons.
For a bundle distribution of total mass one, define
\(a_t=\min\{c_t(b):b\text{ has positive mass}\}\).
EFX is exactly the condition that each bundle assigned to type \(t\) satisfies
\(c_t(b)-c_t(e)\le a_t\) for every \(e\) with \(b_e>0\).
Two bounds will be used repeatedly. First, minimum cost is at most average cost, so
\(a_t\le\sum_e\sigma_e c_t(e)\le2C\).
Second, for any nonempty bundle assigned to type \(t\), EFX gives
\(c_t(b)\le a_t+c_t(e)\le3C\),
using any category \(e\) occurring in \(b\).
These statements allow zero costs.
3. Compression lemma, including zero costs. Suppose an intermediate state satisfying the invariant is given by finitely many rational positive entries. Suppose also that \(\sigma\) and \(q\) have encoding lengths polynomial in the original input length.
We will replace it by another state with the same \(\sigma,q,\mu\), using at most
\((2\tau+m)(m+1)\)
positive entries. Its entire encoding length is polynomial in \(m,\tau,L\) and the number of entries supplied to the compression procedure. Crucially, this bound does not depend on the sizes of the original bundle coordinates.
Treat active and inactive individuals as separate rows. There are at most \(2\tau\) rows, with required masses \(q_t\) and \(\mu_t-q_t\).
Index the given positive entries by \(j\). Entry \(j\) has row \(v_j\), underlying type \(t_j\), bundle \(b^j\), and mass \(y_j>0\). Define its truncated bundle by
\(\bar b^j_e=\min\{b^j_e,H\}\).
We first establish three properties of this truncation.
*Every truncated bundle remains above all comparison thresholds.* For every type \(u\),
\(c_u(\bar b^j)\ge a_u\).
Indeed, if no truncated coordinate has positive cost for \(u\), truncation does not change its cost for \(u\). Otherwise, one retained coordinate alone contributes at least
\(H\gamma>3C\ge a_u\).
*Every deleted copy has zero cost for its recipient.* If \(b^j_e>H\) and \(c_{t_j}(e)>0\), then
\(c_{t_j}(b^j)\ge b^j_e\gamma>3C\),
contradicting the bound from Section 2. Consequently,
\(c_{t_j}(\bar b^j)=c_{t_j}(b^j)\).
Truncation also preserves which categories occur, because \(H\ge1\). Thus \(\bar b^j\) still satisfies every recipient removal inequality against \(a_{t_j}\).
*If any copies are deleted, the recipient's cost equals its threshold.* A deleted copy has zero recipient cost. Removing that copy in the original EFX assignment gives
\(c_{t_j}(b^j)\le a_{t_j}\).
The reverse inequality follows from the definition of \(a_{t_j}\). Hence, whenever \(b^j\ne\bar b^j\),
\(c_{t_j}(\bar b^j)=a_{t_j}\).
Moreover, such an entry is inactive, because an active bundle is a singleton.
For entry \(j\), allow a surplus variable \(z_{j,e}\) precisely when the entry is inactive and
\(c_{t_j}(e)=0\) and \(c_{t_j}(\bar b^j)=a_{t_j}\).
All other surplus variables are absent.
The original assignment proves feasibility of the following linear equations, with nonnegative variables \(x_j,z_{j,e}\):
\(\sum_j\bar b^j_e x_j+\sum_j z_{j,e}=\sigma_e\).
Specifically, take \(x_j=y_j\) and, for allowed variables,
\(z_{j,e}=y_j(b^j_e-\bar b^j_e)\).
The properties just proved ensure that every nonzero surplus is allowed.
Now perform two rational linear programs.
First, maximize \(\eta\), subject to these equations, nonnegativity, and \(x_j\ge\eta\) for every \(j\). The original feasible assignment shows that the optimum \(\eta_*\) is positive. The feasible region is bounded: \(x_j\le1\), \(z_{j,e}\le2\), and \(\eta\le1\). Its coefficients are bounded by \(H\); its right-hand sides are the prescribed marginals. Therefore standard rational linear programming gives an exact optimum \(\eta_*>0\) of polynomial encoding length.
Set \(M=2/\eta_*\).
Second, retain the marginal equations and nonnegativity, replace the lower bounds on \(x_j\) by
\(z_{j,e}\le Mx_j\),
and compute a vertex of this polytope. It is feasible: the first optimum has \(x_j\ge\eta_*\) and \(z_{j,e}\le2\). It is again bounded.
At this vertex, at most \(d=2\tau+m\) groups have \(x_j>0\). To prove this, associate to each positive group its contribution vector \(w_j\) to the row and category equations. Its row contribution is \(x_j\), and its category contributions are \(\bar b^j_e x_j+z_{j,e}\). If more than \(d\) groups were positive, these vectors would have a nontrivial linear dependence
\(\sum_j\alpha_j w_j=0\).
For sufficiently small \(\varepsilon>0\), multiplying each group's entire vector of variables by either \(1+\varepsilon\alpha_j\) or \(1-\varepsilon\alpha_j\) produces two distinct feasible points. The global equations remain unchanged; all within-group constraints are homogeneous and remain valid. Their midpoint is the proposed vertex, a contradiction. Also, \(x_j=0\) forces every associated \(z_{j,e}=0\).
It remains to turn a positive group into integer bundles. Put
\(u_e=z_{j,e}/x_j\),
\(k_e=\lfloor u_e\rfloor\), and
\(f_e=u_e-k_e\).
For absent surplus variables, take \(u_e=0\).
Partition the unit interval at the distinct values among \(0,1,f_1,\ldots,f_m\). On each positive-length interval choose a point \(U\), and create the bundle with coordinates
\(\bar b^j_e+k_e+\mathbf1_{\{U<f_e\}}\),
giving it mass \(x_j\) times the interval length. There are at most \(m+1\) bundles. Since the total interval length on which \(U<f_e\) is \(f_e\), their aggregate category-\(e\) contribution is exactly
\(x_j\bar b^j_e+z_{j,e}\).
All these bundles are EFX-compatible. Each remains above every threshold \(a_u\), because it dominates \(\bar b^j\) coordinatewise. If the group has positive surplus, every added copy has zero recipient cost and the recipient's bundle cost is \(a_{t_j}\); consequently every removal leaves cost at most \(a_{t_j}\). If there is no surplus, compatibility was already established for \(\bar b^j\). Active bundles receive no surplus and remain singletons.
Finally, \(u_e\le M\). The output coordinates are therefore bounded by \(H+\lfloor M\rfloor+1\), and the interval masses have polynomial encoding length. The first LP's coefficient sizes depend only on \(H\) and the prescribed marginals; the second LP and rounding consequently have polynomial encoding bounds independent of the incoming bundle magnitudes. This proves the compression lemma.
4. A singleton-swap insertion lemma. Suppose a state satisfies the invariant. Let type \(t\) have active mass at least \(h>0\). Suppose category \(e\) satisfies
\(c_t(e)\le c_t(f)\)
for every category \(f\) currently occurring.
Insert mass \(h\) of copies of \(e\), repeatedly adding a copy to a bundle of minimum cost for type \(t\). There is an EFX assignment to the resulting bundle distribution in which the active mass of type \(t\) has decreased by \(h\), while all other active masses are unchanged.
Here is a finite argument proving this statement; it is not an algorithmic expansion. Clear the denominators of the current assignment, \(h\), and any rational subdivisions used in the insertions. This yields finitely many individuals of equal mass and an integer number of insertions. Select a distinct active type-\(t\) individual for each insertion.
For one insertion, let \(b\) be the selected minimum-cost bundle, and let \(s\) be the selected active individual's current singleton.
Give \(b+\mathbf1_e\) to that individual, mark them inactive, and give \(s\) to the previous owner of \(b\). If the selected individual already owned \(b\), simply add the copy and mark them inactive.
The updated bundle is EFX-compatible for type \(t\): removing the new copy leaves \(c_t(b)\), and removing any old copy \(f\) leaves
\(c_t(b)+c_t(e)-c_t(f)\le c_t(b)\).
The new minimum bundle cost for type \(t\) is at least the old minimum \(c_t(b)\).
For every other type, adding a nonnegative-cost copy cannot decrease the minimum bundle cost. Thus all unchanged assigned bundles remain compatible. The transferred singleton is compatible with every type. Every other active individual still holds a singleton.
Induction proves the insertion lemma, including insertion of zero-cost copies and comparisons within the same type.
5. Computing an insertion batch without expansion. Suppose the current bundle distribution consists of \(K\) bundles \(b^i\) with positive rational masses \(p_i\). We must carry out the insertion from Section 4.
If \(c_t(e)=0\), choose any minimum-cost bundle class of mass \(p>0\). Write
\(h/p=k+f\), where \(k=\lfloor h/p\rfloor\) and \(0\le f<1\).
Give \(k\) extra copies to mass \(p(1-f)\) of this class and \(k+1\) extra copies to mass \(pf\). Every involved bundle remains minimum-cost for type \(t\), so this is a permissible greedy insertion sequence. It creates at most \(K+1\) bundle classes.
Now suppose \(c_t(e)>0\). Multiply costs by a common denominator so that the starting loads
\(s_i=c_t(b^i)\)
and the increment \(A=c_t(e)\) are integers, with \(A>0\). In this paragraph these symbols denote the scaled costs.
For an integer \(z\ge0\), define
\(G(z)=\sum_i p_i\max\{0,\lfloor(z-s_i)/A\rfloor+1\}\).
This is the mass of insertion opportunities whose pre-insertion load is at most \(z\).
Find the smallest integer \(z\ge0\) for which \(G(z)\ge h\). Binary search suffices: a valid upper bound is
\(\max_i s_i+A\lceil h/\min_i p_i\rceil\).
Set
\(k_i=\max\{0,\lceil(z-s_i)/A\rceil\}\).
Exactly \(k_i\) insertions per individual in class \(i\) have pre-insertion load strictly below \(z\). Their total mass is
\(F=\sum_i p_i k_i<h\).
The remaining mass \(h-F\) is at most the combined mass of classes whose resulting load \(s_i+k_iA\) equals \(z\). Distribute one further copy across that much mass of those classes.
This produces at most two final bundles per original class. It is exactly a greedy insertion sequence: all opportunities below \(z\) are used, then an appropriate portion of the opportunities at \(z\) is used. All counts, subdivisions, and binary-search operations use rational or integer arithmetic.
After either kind of batch, compute an assignment to the new distribution by a transportation flow. Row capacities are the new active and inactive masses; bundle-class capacities are their computed masses. Inactive row \(t\) can receive a bundle precisely when all its removal costs are at most the current threshold \(a_t\); active rows can receive singletons. Section 4 proves this flow is feasible. Exact rational maximum flow computes it in polynomial time.
Apply the compression lemma to its positive entries.
6. Reserving the insertion batches. We now specify an initialization and insertion order that satisfy the insertion lemma's hypotheses.
Reserve a total chore mass \(R-1\), using at most the mass \(\mu_t\) of individuals of each type. Process types in any fixed order. While processing type \(t\), select a cheapest category \(e\) among those with remaining positive chore supply. Reserve a mass
\(h=\min\{\text{remaining type capacity},\text{remaining supply of }e,\text{remaining reservation target}\}\).
Record the block \((t,e,h)\), and subtract its mass from all applicable remaining quantities.
The procedure succeeds because \(R-1\le1=\sum_t\mu_t\). Every nonfinal block exhausts a type capacity or a category supply, so there are at most \(m+\tau+1\) blocks.
Let \(q_t\) be the total mass reserved using type \(t\). The unreserved chore supply has total mass exactly one. Make one singleton class per unreserved category, with mass equal to that category's unreserved supply. Assign these classes to active and inactive rows in proportions \(q_t\) and \(\mu_t-q_t\). All bundles are singletons, so the invariant holds.
Restore the recorded blocks in reverse order.
For a block \((t,e,h)\), every currently allocated category was still available when this block was reserved, or is \(e\) itself. Therefore
\(c_t(e)\le c_t(f)\)
for every currently occurring category \(f\). This remains true throughout the block's insertions.
The active mass of type \(t\) is the total mass of its blocks not yet restored, so it is at least \(h\). Thus Sections 4–5 apply. Restore the block, decrease \(q_t\) by \(h\), and compress.
After all blocks are restored, the supplies are exactly \(\rho\), every \(q_t\) is zero, and the invariant gives the required EFX assignment.
7. Polynomial running time and encoding length. The essential issue is to prevent repeated compression from causing growing denominators or bundle coordinates. The construction does prevent this.
Let \(Q\) be a common denominator of all input masses and supplies. Its binary encoding length is at most polynomial in \(L\). Every reservation amount, every intermediate supply \(\sigma_e\), and every prescribed active mass \(q_t\) is an integer multiple of \(1/Q\), obtained by subtraction and taking minima of such quantities. Their encoding lengths consequently remain polynomial in \(L\).
After compression, the number of supported entries is at most
\(S=(2\tau+m)(m+1)\).
A positive-cost batch creates at most \(2S\) bundle classes; a zero-cost batch creates at most \(S+1\). Its transportation flow therefore has polynomial size, and its positive entries provide polynomially many groups for the compression LPs.
The first compression LP has integer bundle coefficients bounded by \(H\), together with coefficients of magnitude one. Its right-hand sides are the prescribed marginals just bounded. Standard vertex and determinant bounds for rational linear programs imply a polynomial encoding bound for its positive optimum \(\eta_*\), depending only on \(m,\tau,L\) and the polynomially bounded number of groups. Thus \(M=2/\eta_*\) also has a uniform polynomial encoding bound.
The second compression LP has the same polynomial dimension and coefficient lengths. Its vertex, the rounded masses, and the resulting coordinates bounded by \(H+\lfloor M\rfloor+1\) all have uniform polynomial encoding bounds. These bounds are independent of the preceding state's denominators and coordinates: those preceding values establish feasibility but do not appear as coefficients or right-hand sides in the compression LPs.
It follows inductively that every stored state has polynomial encoding length. The batching arithmetic, threshold comparisons, binary searches, transportation flows, and two rational LPs therefore each take polynomial time. There are at most \(m+\tau+1\) restoration blocks.
The algorithm consequently runs in polynomial time in \(m,\tau,L\) and outputs a finitely supported rational EFX assignment of polynomial total encoding length. The proof includes removal of zero-cost copies and all comparisons between individuals of the same type.
⟨structured verdict parsed — rendered above⟩
The claimed polynomial-time result is sound in substance, with minor expositional gaps. I found no false central step or gap requiring new mathematics. The compression argument controls both support size and binary encoding length, and the insertion construction preserves the EFX definition in the task, including removal of zero-cost copies and comparisons within a type.
The minimum clarifications concern the rationality of insertion amounts, the thresholds used in the transportation flow, and the precise standard linear-programming results invoked.
For \(R\le 1\), the proposed singleton masses sum to \(\mu_tR\), and the empty-bundle mass supplies the remaining \(\mu_t(1-R)\). Each category marginal is \(\rho_e\), using \(\sum_t\mu_t=1\). Every removal from an assigned singleton leaves zero cost, so comparisons with empty bundles cause no problem.
The all-zero-cost construction also has the correct type and supply marginals, including at \(R=2\).
The definition of \(a_t\) takes the minimum over all supported bundles, rather than only bundles assigned to type \(t\). This is the correct threshold for the task’s pairwise EFX condition. Positive type masses and finite support make these minima well-defined.
Both bounds
\(a_t\le 2C\) and \(c_t(b)\le 3C\) for bundles assigned to type \(t\) are valid. The latter uses nonemptiness, which the invariant explicitly requires. It remains valid when the removed copy has zero cost.
The cited finite-agent result covers nonnegative additive costs and defines EFX using removal of every item, including zero-cost items. Its chore-count hypothesis is the one needed after clearing denominators. See the paper’s preliminaries and Theorem 3.1 in the [Kobayashi–Mahara–Sakamoto paper](https://arxiv.org/html/2305.04168v1).
The prover correctly distinguishes this existence argument from a polynomial-time algorithm in the succinct input representation. The subsequent construction does not rely on explicitly generating the expanded population.
The choice of \(H\) ensures \(H\gamma>3C\).
The first truncation argument is valid when “truncated coordinate” means a coordinate actually reduced by truncation. If a reduced coordinate has positive cost for an observing type, its retained copies alone exceed that type’s comparison threshold. Otherwise truncation preserves the observing type’s cost.
A coordinate exceeding \(H\) cannot have positive recipient cost: that would contradict the established \(3C\) recipient-cost bound. Thus truncation preserves recipient cost and the set of occurring categories.
The equality \(c_{t_j}(\bar b^j)=a_{t_j}\) whenever copies are deleted is also justified. It uses EFX for removal of a deleted zero-cost copy and the reverse inequality supplied by the definition of the minimum. This correctly identifies when adding arbitrary zero-cost recipient surplus is safe.
Consequently, the original assignment witnesses feasibility of the compression equations. Every nonzero surplus used by that witness is permitted.
The first program has a feasible strictly positive value of \(\eta\), because the supplied list is finite and every listed entry has positive mass. Its nonnegative variables are bounded as claimed.
The choice \(M=2/\eta_*\) makes the first optimum feasible for the second program. The constraints \(z_{j,e}\le Mx_j\) also ensure that a group with \(x_j=0\) has no surplus.
The vertex argument is valid. More than \(2\tau+m\) positive groups would yield a linear dependence among their marginal contribution vectors. Scaling whole groups preserves their homogeneous internal constraints; a sufficiently small scaling perturbation preserves nonnegativity. The two resulting feasible points are distinct because each positive group has \(x_j>0\). Thus the proposed point could not be a vertex.
The interval construction produces at most \(m+1\) bundles per positive group and preserves every category contribution exactly. The resulting bundles remain above all original comparison thresholds. Added copies have zero recipient cost, and their permitted groups have recipient cost equal to the relevant threshold. Therefore all required removal inequalities hold.
Active groups receive no surplus and remain singletons. Nonemptiness is preserved. The claimed support bound follows.
Minor issue: “standard rational linear programming” and “standard vertex and determinant bounds” are not stated precisely. The required hypotheses appear satisfied, so this is an expositional omission rather than an unverified substantive application.
Minimum clarification: State the standard results being invoked for exact rational optimization, polynomial-time vertex extraction from a nonempty bounded rational polytope, and polynomial vertex encoding bounds, with their dependence on dimension and coefficient bit length.
The swap preserves the multiset of bundles except for replacing the chosen minimum-cost bundle by its enlargement. The selected active individual becomes inactive, while any other active individual affected by the swap receives a singleton.
The removal inequalities for the enlarged bundle follow from the stated cheapest-category hypothesis. For every observing type, the minimum bundle cost cannot decrease: the only changed bundle gains a nonnegative-cost copy. Transferred singletons are universally EFX-compatible.
Selecting distinct active type-\(t\) individuals is justified by the active-mass bound after a common-denominator expansion. The expansion is used only for existence, so its potentially exponential size does not invalidate the running-time claim.
Minor issue: The lemma states \(h>0\) without explicitly requiring \(h\) to be rational, although it subsequently clears its denominator and promises a rational assignment. All reservation amounts used by the algorithm are rational, so this omission does not affect the algorithm.
Minimum clarification: Require positive rational \(h\) and rational subdivisions in the lemma statement.
For zero insertion cost, every affected bundle remains minimum-cost for the inserting type. The two-way split has the specified total insertion mass.
For positive insertion cost, the formulas for \(G(z)\) and \(k_i\) correctly distinguish opportunities with pre-insertion load at most \(z\) from those strictly below \(z\). Minimality of \(z\) gives \(F<h\); at \(z=0\), nonnegative starting loads give \(F=0\). The residual insertion mass fits among opportunities at load \(z\). The stated search bound is sufficient.
These counts describe a finite greedy insertion sequence after rational subdivision. Each original class produces at most two final classes.
The transportation formulation correctly separates active and inactive rows. Singleton eligibility suffices for active rows, and recipient removal inequalities characterize eligibility for inactive rows. Section 4 supplies feasibility.
Minor issue: “the current threshold \(a_t\)” could refer to either the incoming state or the newly computed bundle distribution. Flow feasibility requires the latter interpretation. Reusing the incoming thresholds is not justified by Section 4, because minima can rise during a batch.
Minimum clarification: Explicitly define the flow thresholds from the positive-mass bundle classes after the batch, before constructing flow edges.
The reservation target is feasible because \(R-1\le 1\). Every nonfinal block exhausts a type capacity or category supply, giving the claimed polynomial block bound.
The unreserved singleton distribution has total mass one. Its proportional allocation realizes the prescribed active and inactive row masses.
In reverse restoration order, every currently occurring category was available when the relevant block was reserved, or is the restored category itself. Thus the cheapest-category hypothesis holds throughout that block. The remaining active mass also has the stated value.
The encoding argument addresses the essential difficulty. Reservation quantities and intermediate marginals remain multiples of the fixed input denominator. Compression uses incoming thresholds and bundles to determine its permitted variables, but their potentially larger numerical values do not enter its coefficient matrix or right-hand sides. The coefficient bound \(H\), polynomial dimension, and prescribed marginals therefore give uniform bounds for \(\eta_*\), \(M\), the second-program vertex, and rounded output.
Binary representation permits exponentially large numerical coordinates when their bit lengths are polynomial. The batching calculations, rational flows, and compression programs consequently have polynomial-sized inputs at every iteration. No population expansion is part of the implemented algorithm.
The write-up establishes the intended complexity classification. The three requested clarifications make its assumptions and standard algorithmic dependencies explicit; none requires changing the construction.
⟨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.