Answer: Polynomial-time solvable: \(\mathrm P\), with bit complexity \((L+\tau m+sm^2)^{O(1)}\).
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven an allocation X with utility profiles {(ri, 1)}i∈[n], deciding the Pareto-optimality of X is coNP-complete even when ri ∈{ra, rb}. To give some intuitions, if the ratios of the two agents are close, then we may need “many-many exchange” instead of the “one-many exchange” described in Type II. For example, for two agents i and j with ratios ri = 4 3 and rj = 4 3 + ε, a Pareto-improvement may be that agent i gives 3 large items to agent j, in exchange of 4 small items from agent j.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite good classes \(G\), agent types \(T\), rational masses \(\mu_t\), ratios \(r_t>1\), high-value sets \(H_t\subseteq G\), per-capita supplies \(q_g\), and an explicit current allocation \(\lambda_{t,B}\) over integral bundles \(B\in\{0,1\}^{G}\), decide whether there exists a reassignment flow \(y_{t,B,B'}\) preserving source masses and every \(q_g\), with \(u_t(B')\ge u_t(B)\) for every used transition and \(\sum y_{t,B,B'}(u_t(B')-u_t(B))>0\), where \(u_t(B)=r_t|B\cap H_t|+|B\setminus H_t|\).
Let \(G\) be a nonempty set of \(m\) good classes. A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Each type has a binary-rational ratio \(r_t>1\) and a set \(H_t\subseteq G\). Allowed bundles are all \(B\in\mathcal B=\{0,1\}^{G}\), with \(u_t(B)=r_t\sum_{g\in H_t}B_g+\sum_{g\notin H_t}B_g\).
The current allocation is a sparse explicit list of positive binary-rational entries \(\lambda_{t,B}\), with omitted entries zero and \(\sum_B\lambda_{t,B}=\mu_t\). Supplies \(q_g\in[0,1]\) are binary rationals satisfying \(\sum_{t,B}\lambda_{t,B}B_g=q_g\) for every \(g\).
A reassignment is a nonnegative real flow \(y_{t,B,B'}\) over \(T\times\mathcal B\times\mathcal B\), satisfying \(\sum_{B'}y_{t,B,B'}=\lambda_{t,B}\) and \(\sum_{t,B,B'}y_{t,B,B'}B'_g=q_g\) for every \(g\).
Every positive transition must satisfy \(u_t(B')\geq u_t(B)\), and an improvement requires \(\sum_{t,B,B'}y_{t,B,B'}(u_t(B')-u_t(B))>0\). Mass may split among destinations, including the unchanged bundle; equal utilities are allowed without tie-breaking.
Is deciding whether such an improvement exists in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau\), the number \(s\) of listed allocation entries, and the total input bit length \(L\).
For finite agents and indivisible goods, deciding Pareto-optimality is \(\mathrm{coNP}\)-complete even with only two distinct ratios; equivalently, deciding whether a Pareto-improvement exists is \(\mathrm{NP}\)-complete. Integer ratios admit polynomial-time verification. [Source](https://arxiv.org/html/2507.18251v2).
No result settling this exact mass-flow decision problem was identified in the literature search.
The decision problem is in \(\mathrm P\), for arbitrary binary-rational ratios. It admits an exact linear program with \(O(sm^2)\) variables and constraints, and a running time of
\(\bigl(L+\tau m+sm^2\bigr)^{O(1)}\)
bit operations.
The proof preserves the requirement that each positive transition weakly increases utility.
Index the listed allocation entries by \(i\in\{1,\ldots,s\}\). Write their types, source bundles, and masses as \(t_i,B_i,\lambda_i\). Define
\(H_i=H_{t_i},\quad K_i=G\setminus H_i,\quad h_i=|H_i|,\quad \ell_i=|K_i|,\quad r_i=r_{t_i},\quad v_i=u_{t_i}(B_i).\)
For a destination bundle, let \(a\) count its goods in \(H_i\), and let \(b\) count its goods in \(K_i\). Its utility is exactly \(r_i a+b\). Consequently, its admissibility depends only on the count pair. Define
\(D_i=\{(a,b):a\in\{0,\ldots,h_i\},\ b\in\{0,\ldots,\ell_i\},\ r_i a+b\geq v_i\}.\)
There are at most \((h_i+1)(\ell_i+1)=O(m^2)\) such pairs, and exact rational arithmetic determines membership.
Lemma. Let \(E\) be a finite set and let \(k\in\{0,\ldots,|E|\}\). A vector \(p\in[0,1]^E\) is a convex combination of incidence vectors of \(k\)-element subsets of \(E\) if and only if \(\sum_{g\in E}p_g=k\).
Proof. Necessity follows by summing coordinates.
For sufficiency, induct on the number of fractional coordinates. If there are none, the vector itself is an incidence vector of a \(k\)-element subset. There cannot be exactly one fractional coordinate, because the coordinate sum is an integer.
Otherwise, choose two fractional coordinates \(p_g,p_j\), and define
\(\delta_+=\min\{1-p_g,p_j\}>0,\qquad \delta_-=\min\{p_g,1-p_j\}>0.\)
Writing \(e_g,e_j\) for coordinate unit vectors, set
\(p^+=p+\delta_+(e_g-e_j),\qquad p^-=p-\delta_-(e_g-e_j).\)
Both vectors lie in \([0,1]^E\), have coordinate sum \(k\), and have fewer fractional coordinates. Moreover,
\(p=\dfrac{\delta_-}{\delta_++\delta_-}p^++\dfrac{\delta_+}{\delta_++\delta_-}p^-.\)
Apply the induction hypothesis to both vectors. The empty-set case is included. \(\square\)
Thus coordinate marginals satisfying these bounds and a fixed integer sum are realized by a probability distribution over binary subsets of that exact cardinality.
Introduce the following nonnegative variables:
All constraints below apply over these index ranges.
Source-mass conservation:
\(\displaystyle \sum_{(a,b)\in D_i}z_{iab}=\lambda_i.\)
Count marginals:
\(\displaystyle p_{ia}=\sum_{b:(a,b)\in D_i}z_{iab},\qquad w_{ib}=\sum_{a:(a,b)\in D_i}z_{iab}.\)
High-good marginals:
\(\displaystyle 0\leq x_{iag}\leq p_{ia},\qquad \sum_{g\in H_i}x_{iag}=a\,p_{ia}.\)
Low-good marginals:
\(\displaystyle 0\leq d_{ibg}\leq w_{ib},\qquad \sum_{g\in K_i}d_{ibg}=b\,w_{ib}.\)
Supply conservation, for every \(g\in G\):
\(\displaystyle \sum_{i:g\in H_i}\sum_{a=0}^{h_i}x_{iag}+\sum_{i:g\in K_i}\sum_{b=0}^{\ell_i}d_{ibg}=q_g.\)
Maximize
\(\displaystyle \Phi=\sum_{i=1}^{s}\sum_{(a,b)\in D_i}z_{iab}(r_i a+b-v_i).\)
Every objective coefficient is nonnegative. We will prove that the attainable objective values are exactly the attainable total utility gains in the original problem.
Take a reassignment satisfying the source, supply, and weak-utility conditions. For source \(i\), abbreviate
\(y_i(B')=y_{t_i,B_i,B'}.\)
For each destination, write
\(a_i(B')=\sum_{g\in H_i}B'_g,\qquad b_i(B')=\sum_{g\in K_i}B'_g.\)
Aggregate its mass by count pair:
\(\displaystyle z_{iab}=\sum_{B':\,a_i(B')=a,\ b_i(B')=b}y_i(B').\)
Positive transitions are admissible, so their count pairs belong to \(D_i\). Define \(p,w\) through the count-marginal equations, and set
\(\displaystyle x_{iag}=\sum_{B':\,a_i(B')=a}y_i(B')B'_g,\qquad d_{ibg}=\sum_{B':\,b_i(B')=b}y_i(B')B'_g.\)
Because \(B'_g\in\{0,1\}\), the marginal bounds hold. Summing over the relevant goods gives \(a p_{ia}\) and \(b w_{ib}\), respectively. The original source and supply equalities give their LP counterparts.
Finally, each destination in count pair \((a,b)\) has gain \(r_i a+b-v_i\). Therefore
\(\displaystyle \Phi=\sum_i\sum_{B'}y_i(B')\bigl(u_{t_i}(B')-u_{t_i}(B_i)\bigr).\)
Take any feasible LP solution.
For every \(i,a\) with \(p_{ia}>0\), the vector
\(\displaystyle \left(\frac{x_{iag}}{p_{ia}}\right)_{g\in H_i}\)
lies in \([0,1]^{H_i}\) and has coordinate sum \(a\). By the lemma, there exists a probability distribution \(P_{ia}\) over \(a\)-element subsets of \(H_i\) whose inclusion probabilities are these coordinates.
Likewise, when \(w_{ib}>0\), there exists a probability distribution \(Q_{ib}\) over \(b\)-element subsets of \(K_i\) with inclusion probabilities \(d_{ibg}/w_{ib}\).
For each \(z_{iab}>0\), both \(p_{ia}\) and \(w_{ib}\) are positive. Split mass \(z_{iab}\) among bundles \(A\cup C\) by assigning
\(\displaystyle z_{iab}P_{ia}(A)Q_{ib}(C)\)
to each \(a\)-element subset \(A\subseteq H_i\) and \(b\)-element subset \(C\subseteq K_i\). This defines finitely many transitions from source \(B_i\). Set transitions from omitted sources to zero.
The two distributions have total probability one, so source \(i\) sends exactly \(\sum_{(a,b)\in D_i}z_{iab}=\lambda_i\).
For \(g\in H_i\), its receiving mass is
\(\displaystyle \sum_{a:p_{ia}>0}\sum_{b:(a,b)\in D_i}z_{iab}\frac{x_{iag}}{p_{ia}}=\sum_a x_{iag}.\)
Here zero marginal masses also force their \(x\)-variables to zero. Similarly, a good \(g\in K_i\) receives mass \(\sum_b d_{ibg}\). Hence the LP supply equations give exactly the required supplies.
Every positive transition constructed from pair \((a,b)\) has utility \(r_i a+b\geq v_i\), because that pair belongs to \(D_i\). Thus weak improvement holds on each transition, including ties. Its total utility gain is exactly \(\Phi\).
This proves the claimed equivalence.
The LP is feasible: assign each source entirely to its original bundle and use its original good marginals. This gives objective zero.
The feasible region is bounded. Source conservation bounds every \(z_{iab}\) by \(\lambda_i\); the marginal equations and bounds then bound all remaining variables by \(\lambda_i\). Consequently, the maximum \(\Phi^*\) exists, and the preceding equivalence proves
\(\text{an improvement exists}\quad\Longleftrightarrow\quad\Phi^*>0.\)
Per source, the number of variables is
\(O\bigl((h_i+1)(\ell_i+1)+h_i(h_i+1)+\ell_i(\ell_i+1)\bigr)=O(m^2).\)
There are also \(O(sm^2+m)\) constraints and \(O(sm^2)\) nonzero constraint coefficients. Since \(m,s\geq1\), these are \(O(sm^2)\).
Constructing the LP requires \(O(\tau m+sm^2)\) rational arithmetic operations, plus reading the input. Every rational coefficient has bit length \(O(L+\log(m+1))\): ratios are used through arithmetic and comparison, never through iteration up to their numerical values.
Apply the standard theorem that rational linear programming admits exact optimization in time polynomial in its encoding length; see [MIT’s linear-programming notes](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html). Its hypotheses hold here: the LP is explicitly represented, rational, feasible, and bounded. The resulting bit complexity is
\(\bigl(L+\tau m+sm^2\bigr)^{O(1)}.\)
The sign test is exact. Indeed, rational LP vertices and their objective values have polynomial bit length by Cramer’s rule, so strict positivity does not require a numerical tolerance.
The cited [finite-agent hardness theorem](https://arxiv.org/html/2507.18251v2#S3.SS3) concerns allocations to indivisible agents. Here a source mass may split among several bundles, with supplies enforced across the resulting masses. The decomposition above uses precisely that permitted splitting.
Therefore the finite-agent hardness result does not settle this model. The stated mass-flow decision problem is polynomial-time solvable, including with fractional ratios.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the assigned mass-flow decision problem. The LP represents exactly the admissible reassignments and their total utility gains. Its size and coefficient encoding lengths are polynomial, so the stated polynomial-time classification follows. I found no major or minor mathematical issues.
Indexing only positive allocation entries is sufficient: nonnegativity and source conservation force every transition from an omitted source to have zero mass.
For source \(i\), the sets \(H_i\) and \(K_i\) partition \(G\). A destination with counts \(a,b\) therefore has utility exactly \(r_i a+b\). Membership in \(D_i\) is equivalent to the required weak utility inequality for that destination.
The ranges include all possible destination counts, including zero. The bound \((h_i+1)(\ell_i+1)=O(m^2)\) holds because \(h_i+\ell_i=m\) and \(m\geq1\). Exact rational comparison suffices; enumeration does not depend on the numerical magnitude of \(r_i\).
Necessity follows from linearity of the coordinate sum.
In the sufficiency argument, exactly one fractional coordinate is impossible because all other coordinates and the total sum are integers. With two fractional coordinates, both stated displacement sizes are strictly positive.
Each displacement preserves the coordinate sum and keeps every coordinate within its allowed interval. In each resulting vector, at least one of the selected fractional coordinates becomes integral, and no previously integral coordinate changes. Thus both induction branches have fewer fractional coordinates.
The displayed convex combination is correct: its two displacement contributions cancel, and its coefficients are positive and sum to one. The induction terminates and yields a finite convex combination.
The argument covers the empty set and the endpoint cardinalities \(k=0\) and \(k=|E|\). No missing hypothesis or base case was found.
All variable ranges and constraints are compatible. Source conservation fixes the total mass from each source. The count-marginal equations connect \(z\) to \(p,w\). The bounds and cardinality equations impose exactly the hypotheses needed for the decomposition lemma after normalization by a positive marginal mass.
The supply equations count every receiving-good marginal once, using the appropriate high or low group for each source.
Every objective coefficient is nonnegative by the definition of \(D_i\). The objective measures gain relative to the particular source bundle, as required by the task.
Aggregating destination mass by count pair gives the stated source and count-marginal equations. Positive reassignment mass occurs only in \(D_i\).
Since bundle coordinates are binary, the receiving-good marginals satisfy their bounds. Summing these coordinates within each group gives the prescribed cardinality equations. Summing over sources gives precisely the original supplies.
The objective identity is exact because utility gain is constant within each count pair. Consequently, every admissible reassignment maps to a feasible LP point with the same total gain.
This is the central step, and it is sound.
Whenever \(p_{ia}>0\), the normalized high-good marginal vector satisfies the lemma with cardinality \(a\). The corresponding statement holds for the low-good vector when \(w_{ib}>0\).
If \(z_{iab}>0\), the count-marginal equations ensure both denominators are positive. The product distribution \(P_{ia}(A)Q_{ib}(C)\) therefore defines a valid distribution over destinations with precisely counts \(a,b\).
Using the same high-subset distribution for every compatible \(b\), and the same low-subset distribution for every compatible \(a\), does not impose an invalid restriction: admissibility depends only on the two counts, and supplies depend only on individual-good marginals. The displayed receiving-mass calculation verifies that the construction preserves those marginals exactly.
Zero marginal masses force the corresponding receiving-good variables to zero, so the normalization argument leaves no untreated mass.
Every constructed positive transition is individually weakly improving because its count pair belongs to \(D_i\). The construction preserves source mass, supplies, and objective value. It establishes transitionwise admissibility, rather than merely an average utility inequality.
Each source bundle’s own count pair belongs to \(D_i\), with equality in utility. Assigning its full mass to that bundle supplies a feasible LP point with objective zero.
Nonnegativity and source conservation bound each \(z\)-variable. The marginal equations then bound \(p,w\), and the receiving-good bounds control \(x,d\). The feasible region is closed, nonempty, and bounded, so the maximum exists.
The two directions already proved preserve objective values. Hence the equivalence between existence of an improvement and \(\Phi^*>0\) follows exactly, including the case in which the maximum is zero.
Per source, the count-pair variables, count marginals, and receiving-good variables together number \(O(m^2)\).
The constraint and nonzero-coefficient counts are also correct. Each count-pair variable occurs in only a constant number of constraint equations; each receiving-good variable occurs in a constant number of constraints. The coefficients connecting marginal variables to receiving-good bounds contribute only \(O(m^2)\) occurrences per source. The additional supply constraints contribute \(m\), absorbed by \(O(sm^2)\).
Constructing count pairs, utilities, coefficients, and group memberships fits the stated \(O(\tau m+sm^2)\) rational-operation bound, plus input reading. Multiplication by counts at most \(m\) and the stated rational arithmetic preserve the claimed polynomial coefficient bit lengths.
The invoked theorem—exact optimization of explicitly encoded rational LPs in time polynomial in encoding length—is applicable. The LP is rational, explicitly represented, feasible, and bounded; it need not have interior points or full dimension. The cited [MIT notes](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html) discuss polynomial LP algorithms, optimization, polynomial vertex encoding bounds, and exact recovery.
The Cramer’s-rule observation correctly supports polynomial bit length of vertex objective values. Thus an exact sign test is available, and the claimed bit-operation bound \((L+\tau m+sm^2)^{O(1)}\) follows.
The reconstructed flow may have many transitions. This does not invalidate the running time: the assigned problem asks for a decision, and the polynomial-size LP suffices for that decision.
Empty high or low groups are covered by the lemma’s empty-set case and the LP’s zero-count ranges. Supplies equal to zero or one, utility ties, and arbitrary binary-rational ratios introduce no exception to the argument.
The [cited finite-agent paper](https://arxiv.org/html/2507.18251v2#S3.SS3) concerns allocations that partition indivisible items among individual agents. The prover correctly distinguishes that setting from the permitted splitting of source masses here. Its polynomial-time conclusion rests on the explicit LP equivalence, not on an unsupported transfer of the finite-agent result.
No 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.