Answer: The continuous envy decision problem is in \(\mathrm P\).
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor an arbitrary BFCMS graph G with K ≥4 stages, finding an envy minimizing assignment is NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given four fully connected stages of workstation classes, rational capacities \(\kappa_{jv}\) summing to \(1\) at each stage, and rational transition costs, find feasible path masses \(x_p\ge 0\) satisfying \(\sum_{p:p_j=v}x_p=\kappa_{jv}\) for every stage \(j\) and class \(v\), while minimizing \(\max_{p:x_p>0}\gamma(p)-\min_{p:x_p>0}\gamma(p)\), where \(\gamma(p)\) is the additive cost of complete path \(p\).
There are four nonempty stages \(V_1,V_2,V_3,V_4\), with every class in one stage connected to every class in the next. Each stage distribution is given by its support: its workstation types with positive masses \(\kappa_{jv}\), encoded as binary rationals, with \(\sum_{v\in V_j}\kappa_{jv}=1\). Write \(m=\max_j|V_j|\) and \(\tau=\sum_j|V_j|\); \(\tau\) counts supplied support entries, not possible paths or types.
Every transition has an explicitly supplied nonnegative binary-rational cost \(c_j(u,v)\). A complete path is \(p\in\mathcal P=V_1\times V_2\times V_3\times V_4\), with cost \(\gamma(p)=\sum_{j=1}^{3}c_j(p_j,p_{j+1})\).
A feasible assignment consists of divisible path masses \(x_p\in\mathbb R_{\ge0}\) satisfying \(\sum_{p:p_j=v}x_p=\kappa_{jv}\) for every stage and class. Its envy is \(E(x)=\max_{p:x_p>0}\gamma(p)-\min_{p:x_p>0}\gamma(p)\).
Given also a nonnegative binary-rational threshold \(r\), decide whether a feasible assignment has \(E(x)\le r\). Let \(L\) be the total input bit length, including \(r\); state running times in \(m,\tau,L\).
Is this continuous envy decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For the discrete version, assigning \(n\) node-disjoint complete paths through four stages of \(n\) nodes each to minimize the same cost range is NP-hard, even for deciding whether zero envy is achievable. [Vibulan J., Swapnil Dhamal, and Shweta Jain, “The Multi-Stage Assignment Problem: A Fairness Perspective,” ECAI 2025](https://arxiv.org/html/2508.13856v1).
No result settling exactly the divisible path-mass problem above was located in the literature search.
The continuous envy decision problem is in \(\mathrm P\). The decisive facts are that there are exactly four stages, so only polynomially many complete paths, and that feasibility within any fixed cost interval is a rational linear programming problem.
A valid, nonoptimized running-time bound is \(O\!\left(m^4\operatorname{poly}(\tau m^4+L)\right)\) bit operations. The proof below establishes exact feasibility, including when \(r=0\).
Write \(n_j=|V_j|\) and \(N=|\mathcal P|=\prod_{j=1}^4 n_j\). Since the stages are nonempty and explicitly supplied, \(N\le m^4\) and \(N\le(\tau/4)^4\), the latter by the arithmetic–geometric mean inequality.
Every feasible assignment has total mass one: summing its marginal equations over any one stage gives
\( \displaystyle \sum_{p\in\mathcal P}x_p=\sum_{v\in V_j}\kappa_{jv}=1. \)
Consequently, its support \(S(x)=\{p\in\mathcal P:x_p>0\}\) is nonempty. Because \(\mathcal P\) is finite, the minimum and maximum costs on this support are attained.
Define the finite set of path costs \(D=\{\gamma(p):p\in\mathcal P\}\). For each \(a\in D\), define \(Q_a=\{p\in\mathcal P:a\le\gamma(p)\le a+r\}\).
Claim. There is a feasible assignment with envy at most \(r\) if and only if, for some \(a\in D\), there is a feasible assignment supported on \(Q_a\).
Proof. Suppose \(x\) is feasible and \(E(x)\le r\). Set \(a=\min_{p\in S(x)}\gamma(p)\). This minimum is a path cost, so \(a\in D\). Every supported path satisfies \(a\le\gamma(p)\le a+E(x)\le a+r\), hence \(S(x)\subseteq Q_a\).
Conversely, suppose a feasible assignment is supported on \(Q_a\). Its supported path costs all lie in \([a,a+r]\), so their maximum minus their minimum is at most \(r\). This proves the claim. \(\square\)
The second direction does not require that a supported path actually have cost \(a\).
Fix \(a\in D\). Introduce a real variable \(y_p\) for each \(p\in Q_a\), and impose
\( \displaystyle y_p\ge0\quad(p\in Q_a), \)
\( \displaystyle \sum_{\substack{p\in Q_a\\p_j=v}}y_p=\kappa_{jv}\quad(j\in\{1,2,3,4\},\ v\in V_j). \)
This system has at most \(N\) variables and exactly \(\tau\) marginal equations. Every matrix entry is either zero or one, and every right-hand side is an explicitly supplied rational.
A solution extends to a feasible assignment on \(\mathcal P\) by setting \(x_p=0\) outside \(Q_a\). Conversely, a feasible assignment supported on \(Q_a\) restricts to a solution of this system. Thus the linear system expresses precisely the feasibility condition from Section 1.
We use the standard rational linear programming theorem: feasibility of a finite system of rational linear equalities and inequalities can be decided exactly in time polynomial in its binary encoding length. This is the polynomial-time linear programming result originating with [Khachiyan](https://www.mathnet.ru/eng/dan42319). Its hypotheses hold here: all coefficients and right-hand sides are rational, all constraints are linear, and there are no integrality requirements. Equalities may also be replaced by two inequalities.
In particular, real-valued masses do not require an approximate numerical decision procedure.
The algorithm is:
Repeated costs may be tested repeatedly; there are still at most \(N\) tests. Sections 1 and 2 prove both directions of correctness.
For the bit-complexity bound, each path cost is the sum of three input rationals. Forming a common denominator by multiplying their denominators shows that its numerator and denominator have \(O(L)\) bits. The same bound holds for \(a+r\). Exact interval membership can therefore be tested in \(O(L^2)\) bit operations using ordinary integer arithmetic.
Constructing all interval memberships by scanning all paths for each candidate costs \(O(N^2L^2)\) bit operations. Each linear system has a dense encoding of length \(B=O(\tau N+L)\): the matrix contributes \(O(\tau N)\) bits, and the supplied marginal right-hand sides contribute at most \(O(L)\) bits. Constructing these matrices and deciding their feasibility therefore costs \(N\operatorname{poly}(\tau N+L)\).
The total bound is consequently
\( \displaystyle O\!\left(N^2L^2+N\operatorname{poly}(\tau N+L)\right). \)
Since \(N,L\le\tau N+L\), the first term can be absorbed into a polynomial of the latter quantity. Using \(N\le m^4\), we obtain
\( \displaystyle O\!\left(m^4\operatorname{poly}(\tau m^4+L)\right). \)
Equivalently, using \(N\le(\tau/4)^4\), a bound solely in \(\tau,L\) is \(O\!\left(\tau^4\operatorname{poly}(\tau^5+L)\right)\). Because the support entries are explicitly supplied, \(\tau=O(L)\); hence this is polynomial in the total input length.
The cited [discrete problem](https://arxiv.org/html/2508.13856v1) requires node-disjoint paths. Its fixed-interval feasibility condition retains discrete selection requirements. The present problem instead asks for nonnegative real path masses satisfying marginal equations, exactly the linear feasibility problem above.
Thus the discrete hardness result does not obstruct this algorithm. The argument settles the specified four-stage divisible problem without any integrality assumption.
⟨structured verdict parsed — rendered above⟩
The prover’s conclusion is correct: the specified continuous decision problem is in \(\mathrm P\). The argument resolves the exact problem, including zero envy. I found no major or minor mathematical issues.
The definition \(N=\prod_{j=1}^4 |V_j|\) is correct because every consecutive pair of stages is fully connected. The bounds \(N\le m^4\) and \(N\le(\tau/4)^4\) are correct; the latter follows directly from the arithmetic–geometric mean inequality.
Crucially, the number of stages is fixed at four, and \(\tau\) counts explicitly supplied support entries. The prover therefore does not confuse the number of paths with the input size.
Summing the marginal equations over any stage counts every path variable exactly once, so every feasible assignment has total mass one. Its positive support is consequently nonempty. Since there are finitely many paths, its minimum and maximum supported costs are attained.
This justifies the use of the minimum supported cost in the subsequent reduction, even though individual masses may be arbitrary nonnegative real numbers.
In the forward direction, the chosen endpoint \(a\) is the cost of a supported path, hence belongs to \(D\). The inequality
\[
a\le\gamma(p)\le a+E(x)\le a+r
\]
holds for every supported path. Thus the assignment is supported on the corresponding \(Q_a\).
In the reverse direction, nonempty support contained in \([a,a+r]\) has cost range at most \(r\). The prover correctly notes that the assignment need not use a path of cost exactly \(a\).
The quantifiers are correct: existence of a qualifying assignment is equivalent to feasibility for at least one enumerated endpoint.
There is one nonnegative real variable for each allowed path and one marginal equation for every supplied stage-class entry. These are exactly the original constraints restricted to \(Q_a\).
Extending a solution by zeros outside \(Q_a\) preserves every marginal equation. Conversely, restricting an assignment supported on \(Q_a\) preserves those equations. There are no omitted coupling constraints or unintended integrality requirements.
The stated theorem—exact feasibility of a finite rational system of linear equalities and inequalities is decidable in time polynomial in its binary encoding length—is sufficiently precise for this application. The cited attribution corresponds to [Khachiyan’s polynomial-time linear programming result](https://www.mathnet.ru/eng/dan42319).
Every coefficient is rational: the marginal matrix uses zeros and ones, the right-hand sides are supplied rationals, and nonnegativity constraints are linear. Replacing equalities by pairs of inequalities preserves feasibility.
The theorem accommodates redundant equations and feasible sets of lower dimension. Thus neither the marginal dependencies nor the case \(r=0\) invalidates its application. The prover correctly invokes exact rational feasibility rather than numerical approximation.
Each path cost sums three input rationals. Multiplying their denominators and adding the corresponding numerators produces integers with \(O(L)\) bits. Adding \(r\) preserves this bound. Exact comparisons by cross multiplication therefore fit the stated \(O(L^2)\) bound using ordinary integer arithmetic.
There are at most \(N\) candidates, and scanning all paths for each candidate takes \(O(N^2L^2)\) bit operations. Repeated costs only repeat valid tests and do not increase the candidate count beyond \(N\).
The encoding bound \(B=O(\tau N+L)\) is valid for the marginal matrix, rational right-hand sides, and variable nonnegativity declarations. Consequently, the total bound
\[
O\!\left(N^2L^2+N\operatorname{poly}(\tau N+L)\right)
\]
is justified. The polynomial term can absorb the scanning term. Substitution of \(N\le m^4\) yields the stated bound in \(m,\tau,L\), and substitution of \(N\le(\tau/4)^4\) yields the stated bound in \(\tau,L\).
Explicit support encoding implies \(\tau=O(L)\), so these bounds are polynomial in total input length. Enumeration and path-cost computation also fit within them.
Nonempty singleton stages, coincident path costs, zero transition costs, and \(r=0\) are all covered by the same argument. Closed interval membership includes both endpoints exactly.
The distinction from the discrete problem is valid: the cited problem requires node-disjoint path selections, as described in the [paper’s problem formulation](https://arxiv.org/html/2508.13856v1). The present linear systems impose divisible masses instead. The continuous conclusion does not rely on an integrality assertion or on transferring the discrete hardness result.
No additional clarification or mathematical repair is required. The prover establishes the claimed polynomial-time classification for the full specified input model.
⟨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.