Answer: polynomial-time solvable
Theorem 23 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAn 𝜖-approximate ADHZ equilibrium for rational 𝜖∈(0, 1), can be computed in time polynomial in 1 𝜖 and 𝑛, i.e. by a fully polynomial time approximation scheme.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational \(\mu\in\mathbb{Q}^{\tau}\), type utilities \(u_t\in\{0,1\}^{G}\), type endowments \(e_t\), aggregate supplies \(s_g=\sum_t\mu_t e_{tg}\), and rational \(\epsilon\in(0,1)\), compute prices \(p\), type budgets \(b_t\), and unit bundles \(x_t\) such that \(\sum_t\mu_t x_{tg}=s_g\), each \(x_t\) is a cheapest utility-maximizing bundle at budget \(b_t\), and \( (1-\epsilon)p\cdot e_t\le b_t\le\epsilon+p\cdot e_t \) for every type \(t\).
A society is given by its support: the list of \(\tau\) types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible types. Normalize \(\sum_t\mu_t=1\).
There are \(m\geq1\) divisible goods \(G\). Type \(t\) has linear utility \(u_t\in\{0,1\}^{G}\), with at least one liked good, and a binary-rational endowment \(e_t\geq0\) satisfying \(\sum_g e_{tg}=1\). Supplies are \(s_g=\sum_t\mu_t e_{tg}>0\).
Given binary-rational \(\epsilon\in(0,1)\), compute rational prices \(p\geq0\), budgets \(b_t\geq0\), and bundles \(x_t\geq0\) satisfying \(\sum_gx_{tg}=1\) and \(\sum_t\mu_t x_{tg}=s_g\).
Each \(x_t\) must maximize \(u_t\cdot y\) over \(y\geq0\) with \(\sum_g y_g=1\) and \(p\cdot y\leq b_t\), and minimize expenditure among these maximizers.
Require \((1-\epsilon)p\cdot e_t\leq b_t\leq\epsilon+p\cdot e_t\), and \(e_t=e_{t'}\Rightarrow b_t=b_{t'}\). Let \(L\) be the total binary input length.
Can such an equilibrium be computed in time polynomial in \(m,\tau,L,1/\epsilon\), or is computing such an equilibrium NP-hard?
For explicitly listed agents with unit supplies and fractional-perfect-matching endowments, a dichotomous-utility equilibrium with these budget tolerances is computable in time polynomial in the number of agents and \(1/\epsilon\). [Garg–Tröbst–Vazirani](https://arxiv.org/html/2009.10320)
No computational result for this exact support-encoded mass version was located in the literature search.
The equilibrium can be computed in time polynomial in \(m,\tau,L,1/\epsilon\). The population need not be expanded into explicitly listed agents.
The proof below gives a weighted price procedure and controls both its number of iterations and the binary lengths of its rational outputs. The budget update follows the approach of [Garg–Tröbst–Vazirani, Theorem 22](https://arxiv.org/html/2009.10320); the required support-level price computation is proved here.
Let \(T\) be the set of supported types, and let \(H_t=\{g:u_{tg}=1\}\) be the nonempty set of goods liked by type \(t\). For subsets, write
\(\mu(I)=\sum_{t\in I}\mu_t\) and \(s(S)=\sum_{g\in S}s_g\).
It is convenient to allocate aggregate quantities \(z_{tg}=\mu_t x_{tg}\). Their row sums must be \(\mu_t\), and their column sums must be \(s_g\). Since every supported mass is positive, recovering \(x_{tg}=z_{tg}/\mu_t\) is well-defined.
We use the following capacitated version of Hall’s condition.
Flow criterion. Consider a bipartite graph between types \(I\) and goods \(C\), type capacities \(c_t\geq0\), and required good quantities \(s_g\). There exists a flow filling every good without exceeding any type capacity if and only if
\(s(S)\leq\sum_{t\in N_I(S)}c_t\quad\text{for every }S\subseteq C,\)
where \(N_I(S)\) denotes the types adjacent to at least one good in \(S\).
To prove this, construct a network with source-to-type capacities \(c_t\), unbounded capacities on bipartite edges, and good-to-sink capacities \(s_g\). A finite cut whose sink-side goods are \(S\) has minimum possible capacity
\(\sum_{t\in N_I(S)}c_t+s(C\setminus S).\)
Thus every cut has capacity at least \(s(C)\) precisely when the displayed inequalities hold. The max-flow min-cut theorem proves the criterion. Unbounded arcs can be replaced by a rational capacity exceeding \(\sum_t c_t+s(C)\).
All networks used below have polynomially many vertices and arcs. We use standard polynomial-time algorithms for exact rational maximum flow and rational linear programming.
Construct the liked-edge flow network with source-to-type capacities \(\mu_t\) and good-to-sink capacities \(s_g\), and compute a maximum flow \(f\).
If its value is \(1\), set \(z=f\), \(p=0\), and \(b=0\). Every type receives one unit entirely of liked goods, hence achieves utility \(1\) at minimum expenditure \(0\). All requested conditions hold. This settles the case in which the liked-edge graph admits a complete allocation.
Suppose henceforth that the maximum-flow value is less than \(1\). In its residual network, let \(A_1\) and \(G_1\) be the type and good vertices reachable from the source. Put \(A_2=T\setminus A_1\) and \(G_0=G\setminus G_1\).
The residual-network definition gives four properties.
Consequently, \(f\) restricted to \(A_1\times G_1\) fills all goods in \(G_1\) with type capacities \(\mu_t\). Its restriction to \(A_2\times G_0\) allocates each type in \(A_2\) entirely to liked goods.
Moreover, if the flow value is \(F<1\), then
\(F=\mu(A_2)+s(G_1),\qquad \mu(A_1)-s(G_1)=1-F>0.\)
Both \(G_1\) and \(G_0\) are therefore nonempty. We keep this decomposition throughout the algorithm, always assigning price \(0\) to \(G_0\).
Fix strictly positive budgets \(b_t\). Suppose the goods in \(G_1\) have positive prices. Define, for each \(t\in A_1\),
\(q_t=\min_{g\in H_t}p_g,\qquad d_t=\mu_t\min\{1,b_t/q_t\}.\)
We seek an allocation that fills every good in \(G_1\), assigns type \(t\) exactly aggregate quantity \(d_t\), and uses only its cheapest liked goods.
Such an allocation produces an equilibrium for the fixed budgets:
The completion is possible because its total row deficit is
\(\mu(A_1)-s(G_1),\)
equal to the free-good supply remaining after allocating \(A_2\). A greedy transportation allocation fills these rows and columns exactly.
For \(t\in A_1\), the resulting per-capita bundle has utility
\(v_t=\min\{1,b_t/q_t\}\)
and expenditure \(q_t v_t\). Indeed, its positive-price goods are cheapest liked goods, while its fillers are free and disliked.
For any competing bundle \(y\), nonnegative prices imply
\(p\cdot y\geq q_t(u_t\cdot y).\)
Therefore every affordable bundle has utility at most \(\min\{1,b_t/q_t\}\), and every bundle attaining utility \(v_t\) costs at least \(q_t v_t\). The constructed bundle attains both bounds. It is thus utility-maximizing and expenditure-minimizing among maximizers.
Types in \(A_2\) attain utility \(1\) at expenditure \(0\), so their bundles also satisfy both optimality requirements.
It remains to compute the positive prices and their liked allocation efficiently, while permitting only price increases.
For a positive price vector on \(G_1\), call the vector admissible for budgets \(b\) if each price class can be filled using its cheapest-liked-edge graph, with type capacities
\(\mu_t\min\{1,b_t/q_t\}.\)
The flows in this definition need not exhaust all type capacities.
Two observations supply the inputs needed later.
We now prove that any admissible vector can be raised to one having the exact allocation from Section 3.
Initially, all goods in \(G_1\) and types in \(A_1\) are active. During the procedure, frozen goods receive their final allocations, and the participating types are removed.
Maintain the following invariant: no active type likes a frozen good, and the active goods satisfy the admissibility condition on their cheapest-edge graph.
Let \(a\) be the smallest active price, let \(C\) be its price class, and let \(I_C\) be the active types liking at least one good in \(C\). Since \(C\) is the lowest class, it consists of cheapest liked goods for all these types.
Let \(c>a\) be the next active price level, if one exists. Raise all prices in \(C\) together by solving this linear program. Its variables are a common price \(q\) and monetary flows \(w_{tg}\) on liked edges between \(I_C\) and \(C\):
\(\text{maximize }q,\)
subject to
\(\sum_{t\in I_C}w_{tg}=q s_g\quad(g\in C),\)
\(\sum_{g\in C}w_{tg}\leq\mu_t b_t\quad(t\in I_C),\)
\(\sum_{g\in C}w_{tg}\leq\mu_t q\quad(t\in I_C),\)
\(w_{tg}\geq0,\qquad q\geq a,\)
and, when the next level exists, \(q\leq c\).
This is a rational linear program with polynomially many variables and constraints. Admissibility makes it feasible at \(q=a\). It is bounded because
\(q s(C)\leq\sum_{t\in I_C}\mu_t b_t.\)
Let \(q^*\) be its optimum.
If \(q^*=c\), raise \(C\) to \(c\), merge the two price classes, and continue. Their separate filling flows remain feasible in the merged cheapest-edge graph; merging only adds available edges.
Otherwise, raise \(C\) to \(q^*\) and freeze a nonempty tight subset, as follows.
At price \(q>0\), feasibility of the class is equivalent, by the flow criterion, to
\(q s(S)\leq\sum_{t\in N_{I_C}(S)}\mu_t\min\{b_t,q\}\quad(S\subseteq C).\)
At an optimum below the next price level, some nonempty \(S\subseteq C\) must satisfy equality. Otherwise all nonempty-subset inequalities would be strict, and continuity, together with finiteness of the subsets, would allow a small further increase of \(q\).
A tight set can be found in polynomial time. Use the physical-quantity network with type capacities \(\mu_t\min\{1,b_t/q^*\}\) and good capacities \(s_g\). For each good in \(C\), compute a minimum cut constrained to put that good on the sink side. At least one such cut has capacity \(s(C)\). Its sink-side goods form a nonempty tight set \(S\). The constraint can be implemented with one sufficiently large-capacity arc.
Freeze the goods in \(S\) at price \(q^*\), and let \(N=N_{I_C}(S)\). Tightness says
\(s(S)=\sum_{t\in N}\mu_t\min\{1,b_t/q^*\}.\)
In any flow filling \(C\), all flow into \(S\) comes from \(N\). The equality forces every type in \(N\) to exhaust its capacity on \(S\), with none of its flow going elsewhere. Thus:
No remaining type likes \(S\), because every active neighbour of \(S\) was removed. The invariant is preserved.
Each freezing event removes at least one good, so there are at most \(m\) freezing events.
Each merging event reduces the number of active price classes. Raising and partially freezing a lowest class does not increase that number. Hence there are at most \(m-1\) merging events.
The procedure therefore uses polynomially many linear programs and flow computations.
Every type in \(A_1\) is eventually removed: it has a liked good, and it is removed when the first such good is frozen. At that event, it receives exactly its required quantity on cheapest liked goods. Later price changes cannot make another liked good cheaper, because only the lowest active class is processed and prices only rise.
We have proved:
Monotone price lemma. From any admissible positive prices and strictly positive budgets, one can compute, in polynomial time in their binary encoding length, weakly higher prices and an exact liked allocation of the form required in Section 3.
In particular, after increasing budgets, an equilibrium produced by this procedure can be updated using only price increases. Throughout, the prices of \(G_0\) remain zero.
Set
\(\delta=\epsilon/2,\qquad r=\frac{1-\delta}{1-\epsilon}>1.\)
Initialize \(b_t^{(1)}=\delta\). Starting with price \(\delta\) on every good in \(G_1\), apply the monotone price lemma and complete the allocation using free goods. Denote the resulting equilibrium by \((x^{(1)},p^{(1)})\).
For each \(k\geq1\), define
\(b_t^{(k+1)}=\delta+(1-\delta)\,p^{(k)}\cdot e_t.\)
Apply the monotone price lemma to obtain an equilibrium for these budgets with
\(p^{(k+1)}\geq p^{(k)}.\)
The first budget update weakly increases every budget because \(p^{(1)}\geq0\). Subsequently, price monotonicity and nonnegative endowments imply
\(b^{(k+1)}\geq b^{(k)}.\)
Thus every update is well-defined.
Stop at the first \(K\geq2\) for which
\(p^{(K)}\leq r p^{(K-1)}\)
coordinatewise. This condition is checked using exact rational comparisons.
Nonnegative endowments and the stopping condition give
\((1-\epsilon)p^{(K)}\cdot e_t\leq(1-\epsilon)r p^{(K-1)}\cdot e_t=(1-\delta)p^{(K-1)}\cdot e_t\leq b_t^{(K)}.\)
Price monotonicity also gives
\(b_t^{(K)}=\delta+(1-\delta)p^{(K-1)}\cdot e_t\leq\epsilon+p^{(K)}\cdot e_t.\)
Hence both budget tolerances hold.
The budget formula depends only on the endowment vector. Therefore
\(e_t=e_{t'}\ \Longrightarrow\ b_t^{(K)}=b_{t'}^{(K)}.\)
By Sections 3 and 4, the final bundles have the required row sums, clear every good, and satisfy exact utility maximization and expenditure minimization.
Define weighted total budgets and revenue by
\(B_k=\sum_t\mu_t b_t^{(k)},\qquad R_k=\sum_g s_g p_g^{(k)}.\)
Market clearing and budget feasibility imply \(R_k\leq B_k\). Using the supply definition and \(\sum_t\mu_t=1\), the budget update gives
\(B_{k+1}=\delta+(1-\delta)R_k\leq\delta+(1-\delta)B_k.\)
Since \(B_1=\delta<1\), induction yields \(B_k\leq1\). Consequently,
\(p_g^{(k)}\leq1/s_g\quad\text{for every }g.\)
Meanwhile, every price in \(G_1\) starts at least at \(\delta\) and never decreases. Let \(s_{\min}=\min_g s_g>0\), and define the potential
\(\Phi_k=\sum_{g\in G_1}\log\!\left(p_g^{(k)}/\delta\right).\)
It satisfies
\(0\leq\Phi_k\leq |G_1|\log\!\left(1/(\delta s_{\min})\right).\)
Whenever the stopping condition fails, some positive-price coordinate increases by a factor greater than \(r\). All other coordinates weakly increase, so the potential increases by more than \(\log r\).
Finally,
\(\log r\geq1-1/r=\frac{\epsilon}{2-\epsilon}\geq\epsilon/2.\)
It follows that
\(K=O\!\left(1+\frac{m}{\epsilon}\log\!\frac{1}{\epsilon s_{\min}}\right).\)
The supplies have polynomial binary encoding length, so \(\log(1/s_{\min})=O(L)\). Thus the number of updates is polynomial in the requested parameters. No factor proportional to an expanded population appears.
A bound on the number of exact linear programs alone would not rule out excessive growth of intermediate rational encodings. We therefore give an explicit denominator bound.
Choose positive integers:
Products of the relevant input denominators suffice, and all three integers have binary length \(O(L)\).
Consider a freezing price \(q>0\). Because this event occurs below the next price level, \(q\) is the maximum feasible class price without that upper bound.
For a subset \(S\) of the class, put
\(h_S(v)=\sum_{t\in N(S)}\mu_t\min\{b_t,v\}-v s(S).\)
At \(q\), all \(h_S(q)\) are nonnegative. Some tight subset must have negative right derivative. Indeed, if every tight subset had nonnegative right derivative, all subset inequalities would remain valid on a common sufficiently short interval to the right of \(q\), contradicting maximality.
For such a subset, define
\(J=\{t\in N(S):b_t\leq q\},\qquad H=N(S)\setminus J.\)
The right derivative is \(\mu(H)-s(S)<0\). Tightness therefore gives
\(q=\frac{\sum_{t\in J}\mu_t b_t}{s(S)-\mu(H)},\qquad s(S)-\mu(H)>0.\)
Set \(a_t=Q\mu_t\) and \(d=Q(s(S)-\mu(H))\). These are integers, with \(1\leq d\leq Q\), and
\(q=\frac{\sum_{t\in J}a_t b_t}{d}.\)
Thus, if the current budgets have common denominator \(D_b\), each frozen price has a denominator dividing \(D_b d\) for an integer \(d\leq Q\).
There are at most \(m\) freezing events per call. Every final positive price is a frozen price. Hence their common denominator can be chosen with binary length at most
\(\log D_b+m\log Q.\)
If the preceding prices have common denominator \(D_{k-1}\), the new budgets have common denominator
\(D_b=D_{k-1}Q_eQ_\delta.\)
Therefore a common price denominator after the update satisfies
\(\log D_k\leq\log D_{k-1}+\log Q_e+\log Q_\delta+m\log Q.\)
Starting with budgets of denominator \(Q_\delta\), the denominator lengths after \(K\) iterations are consequently \(O(K(m+1)L)\).
Prices are bounded by \(1/s_{\min}\), and budgets by \(\delta+(1-\delta)/s_{\min}\). Their numerators therefore also have polynomial binary length.
Every linear program and flow network consequently has polynomial input length. Exact rational solutions and the final transportation completion have polynomial output length. Dividing aggregate allocations by the positive input masses preserves polynomial encoding length.
This establishes polynomial bit complexity, as well as a polynomial number of arithmetic and optimization steps.
The algorithm returns rational prices, budgets, and bundles satisfying every condition in the task, in time polynomial in \(m,\tau,L,1/\epsilon\).
The essential change from equal-mass agents is to bound weighted revenue by \(1\), giving \(p_g\leq1/s_g\). Although a small supply can permit a numerically large price, only its logarithm enters the iteration bound, and that logarithm is controlled by the binary input length.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes a polynomial-time algorithm for the support-encoded problem, including polynomial bounds on intermediate rational encoding lengths. I found no mathematical errors or gaps requiring clarification.
The proof addresses the actual support representation: each type is represented once, and all allocations and flow capacities incorporate its mass. It never expands binary-rational masses into explicitly listed agents.
The reference to Garg–Tröbst–Vazirani supplies attribution for the budget-update approach; their theorem is not used to infer the support-encoded result. The cited update agrees with the update in the [proof of Theorem 22](https://arxiv.org/html/2009.10320). The weighted price procedure and its complexity analysis are established separately in the submitted argument.
The algorithmic dependencies are standard polynomial-time exact rational maximum flow and rational linear programming. Their relevant hypotheses are satisfied: the networks and linear programs have polynomial size, rational data, and, for the optimization programs used here, feasible bounded objectives. Section 7 supplies the necessary encoding-length control.
The substitution \(z_{tg}=\mu_t x_{tg}\) is valid because every supported mass is strictly positive. The stated aggregate row and column constraints are exactly the task’s allocation constraints.
The capacitated Hall criterion is correctly formulated for filling goods while permitting unused type capacity. The cut expression
\[ \sum_{t\in N_I(S)}c_t+s(C\setminus S) \]
has the correct orientation: a finite cut placing goods \(S\) on the sink side must also place their neighboring types there. Comparing this expression with \(s(C)\) gives precisely the stated inequalities.
Replacing unbounded arcs by capacities larger than the stated total is valid and preserves the relevant minimum-cut calculations.
Assessment: correct.
If the initial flow has value \(1\), both sides’ total capacities equal \(1\). Thus all type and good capacities are saturated. Every bundle consists entirely of liked goods, and zero prices and budgets satisfy utility optimality, expenditure minimization, and both budget tolerances.
In the deficient-flow case, all four residual-reachability properties are valid:
These establish the two restricted allocations and the identity
\[ F=\mu(A_2)+s(G_1). \]
The strict deficit follows from normalization. Both good sets are nonempty: the positive type deficit makes \(A_1\) nonempty, and its types have liked goods in \(G_1\); also \(s(G_1)<\mu(A_1)\leq1\), so positive total supply remains in \(G_0\).
Assessment: correct, including the degenerate complete-flow case.
Every type in \(A_1\) dislikes every free good, by the decomposition. Consequently, free-good completion does not alter its liked-good utility.
The remaining free supply and remaining row demand have the same total. With unrestricted nonnegative transportation on the filler entries, the stated completion is feasible.
For types in \(A_1\), the expenditure inequality
\[ p\cdot y\geq q_t(u_t\cdot y) \]
holds because every liked good costs at least \(q_t\), and all other prices are nonnegative. The constructed bundle attains both the utility upper bound and the expenditure lower bound among utility maximizers.
Types in \(A_2\) attain utility \(1\) at expenditure \(0\), which satisfies both optimality requirements regardless of their positive budgets.
Assessment: correct. The argument verifies expenditure minimization as well as utility maximization.
The initial equal-price, equal-budget vector gives each relevant type its full physical capacity \(\mu_t\), so the restricted initial flow proves admissibility.
Increasing budgets preserves admissibility because the cheapest-edge graph is unchanged and capacities weakly increase.
At a common class price \(q>0\), the two monetary row bounds jointly give capacity
\[ \mu_t\min\{b_t,q\}. \]
Dividing monetary flows by \(q\) gives precisely the required physical capacity. Thus the linear program faithfully represents class feasibility.
Feasibility at the current price follows from admissibility. Boundedness follows from positive class supply and finite total monetary capacity.
At a merger, the two old classes have disjoint sets of types for their respective cheapest-edge flows. Their flows remain feasible at the common price, where additional cheapest edges become available.
If the optimum is below the next level, strictness of every nonempty-subset inequality would allow a further price increase. The finite number of subsets makes the continuity argument valid.
The constrained minimum-cut searches correctly identify a nonempty tight set. The equality between its supply and its neighbors’ total capacities forces every neighboring type to exhaust its capacity within that set. Consequently, removing those goods and types preserves feasibility elsewhere.
Removing every active neighbor also preserves the invariant that no remaining type likes a frozen good.
Every freezing event removes a good; every merging event reduces the number of active price classes. Partial freezing does not introduce new classes. The stated polynomial event bounds are therefore valid.
Every relevant type is eventually removed because it has a liked good. Its allocated goods are cheapest when it is removed and remain cheapest afterward: subsequent price changes only increase other active prices.
Assessment: the monotone price lemma is proved as stated.
The first budget update weakly increases budgets. Subsequent updates do so by price monotonicity and nonnegative endowments. Therefore every invocation of the monotone price lemma is justified.
The stopping multiplier satisfies \(r>1\). At termination, the displayed inequalities correctly establish both required budget bounds:
\[ (1-\epsilon)p^{(K)}\cdot e_t \leq b_t^{(K)} \leq \epsilon+p^{(K)}\cdot e_t. \]
Equal endowments receive equal budgets because the update formula depends only on the endowment vector.
Zero-price coordinates remain zero and cause no problem for the coordinatewise stopping test.
Assessment: correct.
Weighted market clearing and individual budget feasibility give \(R_k\leq B_k\). The supply definition correctly yields
\[ B_{k+1}=\delta+(1-\delta)R_k. \]
The induction \(B_k\leq1\), and hence \(p_g^{(k)}\leq1/s_g\), is valid.
The potential uses only positive-price goods, whose prices remain at least \(\delta\). Every failed stopping test increases the potential by more than \(\log r\), while its upper bound is finite.
The calculation
\[ \log r\geq1-\frac1r =\frac{\epsilon}{2-\epsilon} \geq\frac{\epsilon}{2} \]
is correct throughout the specified range. The resulting iteration bound is polynomial in the requested parameters. Positive binary-rational supplies have logarithmic reciprocal size controlled by the input length.
Assessment: correct; small masses or supplies do not introduce a population-expansion factor.
This section addresses the necessary distinction between polynomially many optimization calls and polynomial bit complexity.
The functions \(h_S\) are continuous and piecewise linear. At a maximal feasible freezing price, some tight subset must have negative right derivative; otherwise all inequalities persist on a sufficiently short common interval.
The definition of \(J\) correctly includes budget breakpoints \(b_t=q\). The resulting price formula is valid, and its denominator is strictly positive:
\[ q=\frac{\sum_{t\in J}a_t b_t}{d}, \qquad 1\leq d\leq Q. \]
Thus newly frozen prices introduce only the stated bounded integer denominator factors. Merger events introduce no new numerical price values, and every final price is eventually frozen.
The common-denominator recurrence across budget updates is valid. Combined with the polynomial iteration bound and the magnitude bounds, it controls both denominators and numerators.
Intermediate class prices are inherited values or newly computed optima covered by this analysis. Exact flow and linear-program solutions therefore have polynomial encoding length. Transportation completion and division by positive input masses preserve polynomial output length.
Assessment: correct; the bit-complexity claim is supported.
No additional clarification is needed to verify the argument. The proof establishes the polynomial-time alternative for the exact support-encoded task and satisfies all allocation, optimality, budget, and equal-endowment requirements.
⟨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.