Answer: For both cost rules, the continuous threshold problem is in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\).
Theorem 1 — class: algorithmic
Input finite sets of household types \(A\) and unit types \(J\), rational population masses \(\mu_a\) summing to \(1\), per-capita unit supplies \(q_j\), initial compatible sets \(N_a\), relaxable sets \(D_a\), discomforts \(\rho_{aj}\), and a per-capita budget \(\beta\). Choose advice masses \(z_{a,S}\geq 0\) for bundles \(S\subseteq D_a\), with \(\sum_{S\subseteq D_a}z_{a,S}=\mu_a\), satisfying either \(\sum_{a,S}z_{a,S}|S|\leq\beta\) or \(\sum_{a,S}z_{a,S}\sum_{j\in S}\rho_{aj}\leq\beta\). For every partial-compliance split \(y_{a,S,R}\geq0\), where \(R\subseteq S\) and \(\sum_{R\subseteq S}y_{a,S,R}=z_{a,S}\), form cohorts compatible with \(N_a\cup R\). Require that, in every resulting maximum mass flow, initially protected type masses and every cohort with \(R\neq\varnothing\) are fully matched. Find a feasible advice policy maximizing the maximum-flow value under full compliance.
A society is given by its support: the list of \(\tau=|A|\) household types with positive binary-rational masses \(\mu_a\), where \(\sum_a\mu_a=1\); \(\tau\) counts listed types, not possible types. Each household demands one unit. There are \(m=|J|\geq1\) unit types with binary-rational supplies \(q_j\geq0\), not necessarily summing to one.
For each \(a\), input initial compatibilities \(N_a\subseteq J\), relaxable incompatibilities \(D_a\subseteq J\setminus N_a\), and positive binary-rational discomforts \(\rho_{aj}\) for \(j\in D_a\); all other incompatibilities are forbidden. Input a binary-rational budget \(\beta\geq0\) and select one cost rule: \(c_a(S)=|S|\) or \(c_a(S)=\sum_{j\in S}\rho_{aj}\).
An advice policy consists of real masses \(z_{a,S}\geq0\), indexed by \(S\subseteq D_a\), with \(\sum_{S\subseteq D_a}z_{a,S}=\mu_a\) and \(\sum_{a,S}z_{a,S}c_a(S)\leq\beta\). Bundles are implicit, not enumerated in the input; \(S=\varnothing\) means no advice, and costs are charged for advice regardless of compliance.
For any real partial-compliance split \(y_{a,S,R}\geq0\), indexed by \(R\subseteq S\), require \(\sum_{R\subseteq S}y_{a,S,R}=z_{a,S}\). Cohort \((a,S,R)\) has mass \(y_{a,S,R}\) and compatibilities \(N_a\cup R\).
Allocation is a bipartite maximum flow: source-to-cohort capacity equals cohort mass, allowed cohort-to-unit arcs have unlimited capacity, and unit-to-sink capacity is \(q_j\). A cohort is fully matched when its source arc is saturated; every maximum flow is possible, with no prescribed tie-breaking.
Let \(P\subseteq A\) contain exactly the types whose entire mass is saturated in every baseline maximum flow, using cohorts of masses \(\mu_a\) and compatibilities \(N_a\). A policy is admissible if, for every compliance split, every maximum flow fully matches each cohort with \(a\in P\) or \(R\neq\varnothing\).
Let \(V(z)\) be the maximum-flow value under full compliance, where \(y_{a,S,S}=z_{a,S}\). The optimization problem maximizes \(V(z)\) over admissible policies; its threshold decision version additionally inputs a binary rational \(t\in[0,1]\) and asks whether some admissible policy has \(V(z)\geq t\). Let \(L\) be the total input bit length.
For each of the two cost rules, is this continuous threshold problem in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
The discrete counterpart with strong no harm and strong benefit under every subset of advised relaxations has a polynomial-time exact optimization algorithm for both cost rules. [Verified discrete result](https://arxiv.org/html/2508.18325v1).
No result settling this exact continuous formulation was located in the literature search.
For both cost rules, the continuous threshold problem is in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\).
In fact, the optimum is attained by a rational policy using only singleton advice bundles. The proof below treats real masses directly; it does not rely on expanding the society into discrete households or applying the [discrete algorithm cited in the question](https://arxiv.org/html/2508.18325v1).
Let \(\nu\) be the baseline maximum-flow value. Define
\[
\mathcal E_N=\{(a,j):j\in N_a\},
\qquad
\mathcal E_D=\{(a,j):j\in D_a\}.
\]
For singleton advice, its cost coefficient is
\[
\kappa_{aj}=
\begin{cases}
1,&c_a(S)=|S|,\\
\rho_{aj},&c_a(S)=\sum_{j\in S}\rho_{aj}.
\end{cases}
\]
We first establish a useful preservation property.
Refinement property. Suppose a policy is admissible. Split each advised cohort into pieces, and replace the advice bundle \(S\) of each piece by some \(T\subseteq S\). The resulting policy is admissible.
To justify this, retain the original parent label on every piece. Under any compliance split of the refined policy, a piece advised \(T\) accepts some \(R\subseteq T\subseteq S\). Thus these same accepted sets define a permitted compliance split of the original policy.
Splitting or merging cohorts with identical compatibilities preserves the maximum-flow value: an allocation to a merged cohort can be distributed among its pieces up to their respective capacities. Moreover, a merged cohort is fully saturated exactly when all its pieces are fully saturated. Consequently, any maximum flow violating a guarantee for a refined cohort would induce a maximum flow violating the corresponding original guarantee. This proves the property.
Both costs weakly decrease under this refinement, because replacing \(S\) by a subset weakly decreases its cardinality and its sum of positive discomforts.
Singleton reduction. Every admissible policy has an admissible singleton policy with the same full-compliance value and no greater cost.
Indeed, choose a full-compliance maximum flow of the original policy. Split each cohort according to the unit receiving its allocation. A piece allocated to \(j\in S\) receives advice \(\{j\}\); a piece allocated through an initial compatibility receives empty advice. Any unmatched piece also receives empty advice.
This is a refinement, hence is admissible and costs no more. The chosen allocation remains feasible, so the new full-compliance value is at least the original value. Conversely, every allocation under the refined full-compliance policy lifts to an allocation under the original full-compliance policy, since all refined compatibilities are subsets of the original ones. Therefore the values are equal.
Henceforth, write \(x_{aj}\) for the mass advised \(\{j\}\), with
\[
x_{aj}\geq0,
\qquad
\sum_{j\in D_a}x_{aj}\leq\mu_a.
\]
The empty-advice mass is \(\mu_a-\sum_{j\in D_a}x_{aj}\).
For a vector \(r\) satisfying \(0\leq r_{aj}\leq x_{aj}\), let \(r_{aj}\) be the mass accepting singleton advice \(\{j\}\). All remaining mass of type \(a\) has initial compatibilities \(N_a\).
Let \(\Phi(r)\) be the maximum-flow value of this compliance instance. In particular, \(\Phi(0)=\nu\), and full compliance with policy \(x\) has value \(\Phi(x)\).
For \(U\subseteq J\), define
\[
B_U=\sum_{j\in U}q_j+
\sum_{a:N_a\not\subseteq U}\mu_a,
\]
and
\[
C_U=\{(a,j)\in\mathcal E_D:
N_a\subseteq U,\ j\notin U\}.
\]
The minimum-cut formula gives
\[
\boxed{\displaystyle
\Phi(r)=\min_{U\subseteq J}
\left(B_U+\sum_{(a,j)\in C_U}r_{aj}\right).}
\tag{1}
\]
Here is the calculation. Fix the source-side unit set \(U\). A cohort can lie on the source side without cutting a compatibility arc exactly when all its compatibilities lie in \(U\). Thus the cut capacity is
\[
\sum_{j\in U}q_j+
\sum_a\left(\mu_a-\sum_{j\in D_a}r_{aj}\right)
\mathbf1_{\{N_a\not\subseteq U\}}
+
\sum_{(a,j)\in\mathcal E_D}r_{aj}
\mathbf1_{\{N_a\cup\{j\}\not\subseteq U\}}.
\]
Collecting the coefficient of \(r_{aj}\) yields \(1\) precisely for \((a,j)\in C_U\), and \(0\) otherwise, proving (1).
In particular, \(\Phi\) is continuous and coordinatewise nondecreasing. Every affine function in (1) has coefficients in \(\{0,1\}\).
Reducing a singleton policy coordinatewise preserves admissibility, by the refinement property.
The following facts hold for real capacities. Unlimited compatibility capacities can be replaced by any finite capacity exceeding total household mass.
Suppose compatibility arcs are added, while all cohort masses and unit supplies remain fixed. Starting from any feasible flow, there exists a maximum flow in the enlarged network whose allocation to every cohort is at least its starting allocation.
To prove this, take a maximum flow in the residual network and discard its circulation components. Its remaining components are source-to-sink paths. Such paths never revisit the source, so they cannot traverse a reverse source-to-cohort arc. Applying them therefore never decreases any cohort's source-arc flow. The resulting flow is maximum by the residual maximum-flow theorem.
Let \(G\) be an allocation network, and let \(H\) be a collection of positive-mass cohorts saturated in every maximum flow of \(G\). Form \(G'\) by deleting compatibility arcs only from cohorts in \(H\), keeping all capacities fixed. Suppose \(G'\) and \(G\) have the same maximum-flow value.
Then every vector of cohort allocations attainable by a maximum flow of \(G\) is also attainable by a maximum flow of \(G'\).
Proof. Choose a maximum flow \(g'\) of \(G'\). It is also maximum in \(G\). Let \(g\) be any maximum flow of \(G\).
The difference between these flows is a circulation in the residual network of \(g'\) in \(G\): both flows have the same value, so their difference has zero divergence at every vertex, including the source and sink. Decompose this circulation into directed simple cycles.
A residual cycle through the source cannot visit the sink, because its source-to-sink prefix would be an augmenting path, contradicting maximality.
It also cannot visit any cohort \(h\in H\). Indeed, the source arc of \(h\) is saturated in \(g'\), so its reverse arc has positive residual capacity. A residual path from the source to \(h\), followed by that reverse arc, would give a residual cycle that decreases the allocation to \(h\) while preserving total flow value. This contradicts the definition of \(H\).
Therefore every cycle through the source avoids \(H\), and hence avoids all deleted compatibility arcs. Apply only these cycles to \(g'\). This is feasible in \(G'\): their total use of each residual arc is bounded by that of the entire difference circulation.
Cycles not through the source do not affect source-arc flows. Thus the resulting maximum flow in \(G'\) has exactly the same cohort allocations as \(g\). \(\square\)
Call \(w\) minimal for its value if there is no distinct vector \(u\) with \(0\leq u\leq w\) and \(\Phi(u)=\Phi(w)\).
We prove the central claim:
Normalization lemma. If \(w\) is an admissible singleton policy minimal for its value, then
\[
\boxed{\displaystyle
\Phi(w)=\nu+\sum_{(a,j)\in\mathcal E_D}w_{aj}.}
\tag{2}
\]
Write \(v=\Phi(w)\), and let \(e\in\mathcal E_D\) have \(w_e>0\). Denote its coordinate unit vector by \(\mathbf e_e\).
At least one cut attaining the minimum in (1) at \(w\) has coefficient \(1\) on coordinate \(e\). Otherwise all minimizing cuts would be unchanged by decreasing this coordinate, and, since there are finitely many cuts, a sufficiently small decrease would preserve \(v\). That would contradict minimality.
All cut expressions decrease by at most \(\delta\), and this minimizing cut decreases by exactly \(\delta\). Hence
\[
\Phi(w-\delta\mathbf e_e)=v-\delta
\qquad
(0\leq\delta\leq w_e).
\tag{3}
\]
Let \(w^{-e}=w-w_e\mathbf e_e\). Thus
\[
\Phi(w^{-e})=v-w_e.
\tag{4}
\]
We claim that \(w^{-e}\) is minimal for its own value.
Suppose otherwise. By coordinatewise monotonicity, there is some \(f\neq e\) and some \(\delta>0\), chosen also to satisfy \(\delta<w_e\), such that
\[
\Phi(w^{-e}-\delta\mathbf e_f)=\Phi(w^{-e})=v-w_e.
\tag{5}
\]
For example, take a strictly smaller vector preserving the value, choose one decreased coordinate, and decrease only that coordinate by a sufficiently small amount.
By (3), applied to \(f\),
\[
\Phi(w-\delta\mathbf e_f)=v-\delta.
\tag{6}
\]
We now derive a contradiction using admissibility.
Represent the mass \(w_e\) as a distinct cohort throughout. In policy \(w\), this cohort accepts its singleton advice and is fully saturated in every maximum flow. Choose a maximum flow and delete all allocation supplied by this cohort. Reduce its compatibilities to its initial set.
The resulting flow is feasible for \(w^{-e}\), has value \(v-w_e\), and leaves this entire cohort unmatched. By (4), it is maximum.
Next, split the advised cohort \(f\) into two identical pieces, one of mass \(\delta\). In the instance \(w^{-e}\), both pieces are saturated in every maximum flow, because \(w^{-e}\) is admissible and they accept advice.
Make the mass-\(\delta\) piece ignore its advice. This deletes compatibility arcs only from a forced cohort. Equation (5) says that the maximum-flow value is unchanged. Fact B therefore gives a maximum flow for \(w^{-e}-\delta\mathbf e_f\) in which the entire mass-\(w_e\) cohort remains unmatched.
Finally, let that cohort accept advice \(e\). This produces the instance \(w-\delta\mathbf e_f\). By Fact A, there is a maximum flow obtained without decreasing any other cohort's allocation. Its total increase over the preceding flow is, by (5) and (6),
\[
(v-\delta)-(v-w_e)=w_e-\delta.
\]
Since the mass-\(w_e\) cohort started unmatched, its allocation in this maximum flow is at most \(w_e-\delta<w_e\).
But \(w-\delta\mathbf e_f\) is a subpolicy of \(w\), hence is admissible. The cohort accepting advice \(e\) must therefore be fully saturated in every maximum flow—a contradiction.
Thus \(w^{-e}\) is minimal.
Induct on the number of positive coordinates of \(w\).
If there are none, \(\Phi(w)=\Phi(0)=\nu\). Otherwise remove a positive coordinate \(e\). The resulting policy is admissible and minimal by the preceding argument. Induction and (4) give
\[
\Phi(w)
=\Phi(w^{-e})+w_e
=\nu+\sum_f w_f.
\]
This proves (2). \(\square\)
For every admissible singleton policy \(x\), such a minimal subpolicy exists with the same value. Indeed, minimize \(\sum_e w_e\) over
\[
0\leq w\leq x,\qquad \Phi(w)=\Phi(x).
\]
This feasible set is nonempty and compact, because \(\Phi\) is continuous. A minimizer is minimal for its value, remains admissible, and costs no more than \(x\).
Thus every admissible policy has an admissible singleton subpolicy satisfying (2), with the same value and no greater cost.
Use nonnegative variables \(f_{aj}\) for \((a,j)\in\mathcal E_N\), and \(x_{aj}\) for \((a,j)\in\mathcal E_D\).
Maximize
\[
\nu+\sum_{(a,j)\in\mathcal E_D}x_{aj}
\tag{7}
\]
subject to
\[
\sum_{(a,j)\in\mathcal E_N}f_{aj}=\nu,
\tag{8}
\]
\[
\sum_{j\in N_a}f_{aj}
+\sum_{j\in D_a}x_{aj}\leq\mu_a
\qquad(a\in A),
\tag{9}
\]
\[
\sum_{a:j\in N_a}f_{aj}
+\sum_{a:j\in D_a}x_{aj}\leq q_j
\qquad(j\in J),
\tag{10}
\]
and
\[
\sum_{(a,j)\in\mathcal E_D}\kappa_{aj}x_{aj}\leq\beta.
\tag{11}
\]
For threshold decision, additionally require
\[
\nu+\sum_{(a,j)\in\mathcal E_D}x_{aj}\geq t.
\tag{12}
\]
The only difference between the two cost rules is the choice of \(\kappa_{aj}\).
Define
\[
z_{a,\{j\}}=x_{aj},
\qquad
z_{a,\varnothing}=\mu_a-\sum_{j\in D_a}x_{aj},
\]
with all other bundle masses zero. Constraints (9) and (11) ensure valid masses and budget.
By (8), \(f\) is a baseline maximum allocation. Therefore it fully matches every type in \(P\). Constraint (9) consequently implies
\[
x_{aj}=0
\qquad(a\in P,\ j\in D_a).
\tag{13}
\]
Consider any real compliance vector \(0\leq r\leq x\). Allocate \(f\) to the empty-advice cohorts and allocate each accepting cohort of mass \(r_{aj}\) to \(j\).
This is feasible: (9) fits \(f\) inside the empty-advice masses, and (10) remains valid when \(x\) is replaced by \(r\). Its value is
\[
\nu+\sum_{(a,j)\in\mathcal E_D}r_{aj}.
\tag{14}
\]
Conversely, in any allocation for this compliance instance, delete all allocation using relaxed compatibility arcs. What remains is a feasible baseline allocation after merging cohorts by household type, so it has value at most \(\nu\). The deleted allocation has value at most \(\sum r_{aj}\). Thus (14) is the maximum-flow value.
Equality forces every accepting cohort to send its entire mass through its relaxed arc: otherwise the total relaxed allocation would be strictly less than \(\sum r_{aj}\), making (14) impossible. The remaining baseline allocation has value exactly \(\nu\), so it fully matches every type in \(P\).
By (13), types in \(P\) receive no nonempty advice. Therefore every protected cohort and every accepting cohort is fully matched in every maximum flow. The policy is admissible.
Under full compliance, its value is exactly (7).
Start with any admissible policy of value \(v\). Apply the singleton reduction, then choose a minimal subpolicy \(w\) preserving \(v\). Its cost is no greater than the original cost. By the normalization lemma,
\[
v=\nu+\sum_e w_e.
\tag{15}
\]
Choose a full-compliance maximum flow for \(w\). Let \(h\) be its total allocation through relaxed arcs. Since each advised cohort has mass \(w_e\),
\[
h\leq\sum_e w_e.
\]
Its remaining allocation uses only initial compatibilities and is baseline-feasible after merging cohorts, so
\[
v-h\leq\nu.
\]
Together with (15), these inequalities force
\[
h=\sum_e w_e,
\qquad
v-h=\nu.
\tag{16}
\]
Because each singleton cohort's relaxed allocation is at most its mass, equality in (16) means that every such cohort sends its entire mass through its relaxed arc.
Set \(x=w\), and let \(f_{aj}\) be the flow through the initial compatibility \((a,j)\). Equations (16) give (8). Household and unit capacities give (9) and (10), while the nonincreasing cost gives (11).
The LP objective is \(v\). In particular, any admissible policy meeting the threshold yields an LP solution satisfying (12).
This proves exact equivalence.
The baseline network has \(m+\tau+2\) vertices and at most \(\tau m+m+\tau\) arcs. Its rational maximum-flow value \(\nu\) is computable in polynomial time and has polynomial bit length. For example, multiplying by the product of the input denominators gives integral capacities with polynomial bit length; no population expansion is needed.
The LP has
\[
|\mathcal E_N|+|\mathcal E_D|\leq\tau m
\]
variables, since initial and relaxable compatibilities are disjoint. It has polynomially many constraints, and every coefficient has bit length polynomial in \(L\). Exact rational linear programming therefore solves its feasibility and optimization versions in time polynomial in \(m,\tau,L\).
The LP is feasible—take \(x=0\) and any baseline maximum allocation—and its feasible region is compact by the household bounds. Consequently, an optimum exists and can be chosen rational with polynomial encoding length. Its singleton policy is an optimal policy for the original continuous formulation.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes polynomial-time solvability for both cost rules, including real compliance splits and the requirement that guarantees hold in every maximum flow. I found no major or minor issues requiring repair.
The refinement argument preserves the relevant quantifiers. For each compliance split of the refined policy, retaining parent labels produces a valid compliance split of the original policy: every accepted set remains a subset of its original advice bundle.
Merging pieces with identical compatibilities preserves maximum-flow value and saturation. If a refined piece requiring protection is unsaturated, its corresponding original cohort is unsaturated after merging. That original cohort requires protection because either its type belongs to \(P\), or its accepted set is nonempty. Thus the contradiction with original admissibility is valid.
The singleton reduction also preserves full-compliance value in both directions:
The unmatched pieces and pieces allocated through initial compatibilities are handled correctly by empty advice. Both specified costs weakly decrease under refinement.
For a fixed source-side unit set \(U\), a cohort can remain on the source side precisely when its entire compatibility set lies in \(U\). The displayed cut-capacity calculation correctly accounts for both accepting and nonaccepting masses.
The coefficient of \(r_{aj}\) is:
Consequently, equation (1) is correct. Its claimed continuity, coordinatewise monotonicity, and coefficient bounds follow from a finite minimum of these affine expressions.
This calculation also covers empty initial compatibility sets and zero unit supplies.
Fact A is valid. A maximum residual flow can be decomposed into simple source-to-sink paths after removing circulations. Such paths cannot traverse reverse source-to-cohort arcs, since those arcs return to the source. Applying the paths therefore increases total value without decreasing any cohort’s source allocation. The residual maximum-flow theorem applies to this finite network with real, finite capacities.
Replacing unlimited compatibility capacities by a capacity exceeding total household mass is legitimate: no feasible allocation needs more than total household mass on any compatibility arc.
Fact B is valid. The difference of two equal-value flows gives a residual circulation. Its decomposition into simple directed cycles is applicable with real flow amounts.
Both exclusions concerning cycles through the source are justified:
Thus source-containing cycles avoid every cohort whose compatibility arcs were deleted. Applying only those cycles remains feasible in the reduced network and reproduces exactly the desired source-arc allocations. Cycles omitting the source cannot affect those allocations.
The central argument is sound.
Equation (3). Minimality implies that each positive coordinate occurs with coefficient one in at least one minimizing cut. Otherwise, finiteness of the cut family would permit a sufficiently small decrease preserving the value.
That minimizing cut provides the upper bound \(v-\delta\). Every cut decreases by at most \(\delta\), providing the matching lower bound. This establishes equation (3) throughout the stated interval, including complete removal of the coordinate.
Preservation of minimality. If \(w^{-e}\) were not minimal, monotonicity permits choosing one remaining coordinate \(f\) and a positive decrease \(\delta\), small enough to satisfy both feasibility and \(\delta<w_e\), while preserving its value.
The subsequent network operations are justified:
This contradicts admissibility of the coordinatewise reduced policy. There is no circular dependence: coordinatewise reduction preserves admissibility independently of the normalization lemma.
The induction includes the zero-coordinate base case and reduces the number of positive coordinates at every step. Equation (2) follows.
Finally, the compact minimization argument correctly establishes existence of a minimal value-preserving subpolicy. Positivity of the cost coefficients ensures its cost does not increase.
Constraints (8)–(10), together with nonnegativity, make \(f\) a baseline maximum allocation.
For \(a\in P\), that allocation saturates the entire mass \(\mu_a\). Constraint (9) therefore forces every \(x_{aj}\) for that type to vanish, as claimed in equation (13).
For every real compliance vector \(0\leq r\leq x\), the proposed allocation is feasible. In particular, constraint (9) fits \(f\) inside the actual empty-advice mass, and constraint (10) bounds unit usage.
The upper bound on maximum-flow value is also correct. Removing relaxed-arc allocation leaves a baseline-feasible allocation of value at most \(\nu\), while relaxed allocation is bounded by \(\sum r_{aj}\). Hence equation (14) is exact.
Equality forces every accepting cohort to use its entire mass on its singleton relaxed arc. The remaining baseline allocation has value \(\nu\), so it saturates every protected type. Since protected types receive only empty advice, this proves the required cohort guarantees in every maximum flow.
The vector \(r\) represents every singleton compliance split, so the argument covers the full universal compliance requirement.
The singleton reduction and normalization preserve the original policy’s value and do not increase cost.
For the selected full-compliance maximum flow, the inequalities \(h\leq\sum_e w_e\) and \(v-h\leq\nu\), together with equation (15), correctly force both equalities in equation (16).
Equality in the relaxed-allocation bound forces each singleton advised cohort to allocate its entire mass through its relaxed arc. Its initial-compatibility allocation is therefore zero. This justifies the household constraint (9), as well as the remaining LP constraints.
The resulting LP solution has exactly the original policy’s value. Thus the threshold equivalence is established in both directions.
The network and LP sizes are polynomial in \(m,\tau,L\). Scaling rational capacities by the product of their denominators produces integers of polynomial bit length; it does not require population expansion. The resulting baseline value \(\nu\) also has polynomial bit length.
The rational LP has polynomial encoding length, so polynomial-time rational linear programming applies. Household bounds make its feasible region bounded, and its linear constraints make it closed. The stated feasible solution with \(x=0\) establishes nonemptiness for optimization. Consequently, an optimum exists and has a rational representative of polynomial encoding length.
The argument accommodates zero budget, empty relaxable sets, zero supplies, baseline value zero or one, and supplies whose sum differs from one. It does not require computing \(P\) explicitly.
No additional clarification or mathematical repair 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.