Computing Competitive Equilibria with Mixed Manna (d4-conf-atal-2020-0047)

Given \(m\) item classes with rational per-capita supplies \(q_j\), a finite set \(T\) of complete linear-utility types, and rational masses \(\mu_t\) summing to \(1\), compute a competitive equilibrium for a negative mixed-manna market with type-level allocation masses \(z_{tj}\), \(\sum_t z_{tj}=q_j\), representative bundles \(a_{tj}=z_{tj}/\mu_t\), prices \(p_j\), per-capita virtual budget \(-1\), and conditions \(\sum_j p_j a_{tj}=-1\) and \(a_t\in\arg\max_{y\ge0}\{\sum_j u_{tj}y_j:\sum_j p_jy_j\le-1\}\) for every \(\mu_t>0\). For fixed \(m\), determine whether one equilibrium, or a finite cell-and-polytope representation of all equilibria, can be computed in time polynomial in \(\tau=|T|\) and the input encoding length.

A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) divisible, nondisposable item classes with supplies \(q_j\in\mathbb Q_{>0}\). Each type has a complete utility vector \(u_t\in\mathbb Q^m\), allowing positive, negative, and zero entries; let \(L\) be the total input bit length.
An allocation is \(z\in\mathbb R_{\ge0}^{\tau\times m}\) with \(\sum_tz_{tj}=q_j\); its representative bundles are \(a_{tj}=z_{tj}/\mu_t\). The instance is promised negative: no feasible allocation satisfies \(\sum_j u_{tj}a_{tj}\ge0\) for every type.
A competitive equilibrium is an allocation and prices \(p\in\mathbb R^m\) such that, for every type, \(\sum_jp_ja_{tj}=-1\) and \(a_t\in\arg\max_{y\in\mathbb R_{\ge0}^m}\{\sum_ju_{tj}y_j:\sum_jp_jy_j\le-1\}\). Prices may have either sign or be zero; all maximizing bundles are allowed, without tie-breaking or supply bounds on individual demand.
Consider both computing one exact equilibrium and computing all equilibria as a finite union \(\bigcup_k(P_k\times\{p^{(k)}\})\), where each \(p^{(k)}\) is rational and each allocation polytope \(P_k\) is specified by rational linear inequalities.

For each fixed \(m\), is computing one equilibrium polynomial-time solvable in \(\tau\) and \(L\), or NP-hard?
For each fixed \(m\), is computing the stated representation of all equilibria polynomial-time solvable in \(\tau\) and \(L\), or NP-hard? State running times with their dependence on \(m,\tau,L\).

For finite agent lists, positive and null instances admit polynomial-time equilibrium computation; negative instances admit computation of all equilibria in polynomial time when the number of agents or items is fixed. [Garg–McGlaughlin](https://www.ifaamas.org/Proceedings/aamas2020/pdfs/p420.pdf)
Later work gives polynomial-time equilibrium computation for finite negative instances with a fixed number of chores, linear chore utilities, and separable piecewise-linear concave goods utilities. [Garg–Hoefer–McGlaughlin–Schmalhofer](https://algo.rwth-aachen.de/team/hoefer/papers/Garg21ConstantBads.pdf)
No result explicitly addressing this support-encoded mass problem was verified.

Classification

Under the stated definition, computing one equilibrium is polynomial-time solvable for every fixed \(m\).

Computing the specified representation of all equilibria has a different answer:

| Number of item classes | One exact equilibrium | All equilibria in the requested representation |
|---|---|---|
| \(m=1\) | Polynomial time | Polynomial time |
| \(m=2\) | Polynomial time | Polynomial time |
| Every fixed \(m\ge3\) | Polynomial time | The representation need not exist |

The obstruction in the last row is a continuum of equilibrium prices, already with two types of mass \(1/2\). Thus the proposed polynomial-time versus NP-hard dichotomy for the second task does not hold as stated.

The allowance of all maximizing bundles matters here. Nevertheless, the substantive algorithmic extension survives: for every fixed \(m\), all equilibria in which every type obtains strictly negative utility can be computed in polynomial time. At least one such equilibrium always exists.

A sufficient running-time bound for this algorithm is
\[ (\tau m^2+m+1)^{m+1}\operatorname{poly}(\tau,m,L) =\tau^{O(m)}\operatorname{poly}(L) \]
for fixed \(m\). Below, the polynomial factors have absolute, constant exponents.

1. Aggregate budgets and optimality

Write \(u_t\cdot y=\sum_j u_{tj}y_j\). Since \(a_t=z_t/\mu_t\), the representative budget equation is equivalent to
\[ p\cdot z_t=-\mu_t. \]

Moreover, multiplication by \(\mu_t>0\) gives a bijection between the two demand problems
\[ \max\{u_t\cdot y:y\ge0,\ p\cdot y\le-1\} \]
and
\[ \max\{u_t\cdot x:x\ge0,\ p\cdot x\le-\mu_t\}. \]
Their objectives differ by the positive factor \(\mu_t\). Consequently, the support-encoded problem is exactly a market with \(\tau\) aggregate consumers and budgets \(-\mu_t\). No population expansion is required computationally.

We use the following optimality characterization.

Lemma 1. Suppose \(a_t\ge0\) and \(p\cdot a_t=-1\). Then \(a_t\) is a maximizing bundle if and only if there is \(\lambda_t\ge0\) such that
\[ u_{tj}\le\lambda_t p_j\qquad\text{for every }j, \]
and
\[ a_{tj}>0\quad\Longrightarrow\quad u_{tj}=\lambda_t p_j. \]
In that case,
\[ u_t\cdot a_t=-\lambda_t. \]

Proof. The dual of the representative demand linear program is
\[ \min\{-\lambda:\lambda\ge0,\ \lambda p_j\ge u_{tj}\text{ for every }j\}. \]
If \(a_t\) is optimal, its attained objective is finite. Linear-programming strong duality gives an optimal dual multiplier, and complementary slackness gives the displayed support condition.

Conversely, suppose the conditions hold. For every affordable \(y\ge0\),
\[ u_t\cdot y\le\lambda_t p\cdot y\le-\lambda_t. \]
The support condition and the budget equation give
\[ u_t\cdot a_t=\lambda_t p\cdot a_t=-\lambda_t, \]
so \(a_t\) attains this upper bound. \(\square\)

In particular, strictly negative equilibrium utility is equivalent to \(\lambda_t>0\). The possibility \(\lambda_t=0\) must not be discarded.

2. Existence of an equilibrium with strictly negative utilities

Partition the item classes as
\[ G=\{j:\max_t u_{tj}>0\},\qquad B=\{j:\max_t u_{tj}<0\},\qquad Z=\{j:\max_t u_{tj}=0\}. \]

First, \(B\ne\varnothing\). Otherwise, each item could be assigned entirely to a type valuing it nonnegatively. Every type would then receive nonnegative utility, contradicting the promise.

Delete the classes in \(Z\) temporarily. The resulting instance is still negative: any allocation giving all types nonnegative utility could be extended by assigning each deleted item to a type valuing it at zero.

We use the finite-agent existence theorem for negative linear mixed-manna instances: with equal budgets \(-1\), a competitive equilibrium exists. This is stated as Theorem 2.4 in [Garg–McGlaughlin](https://www.ifaamas.org/Proceedings/aamas2020/pdfs/p420.pdf). Arbitrary positive supplies are covered by the change of coordinates \(x_j=y_j/q_j\), with utility coefficients \(q_j u_{tj}\).

Here is a precise application to rational masses; it establishes existence without prescribing an algorithm that expands them.

Choose an integer \(D\) such that
\[ k_t=D\mu_t\in\mathbb Z_{>0},\qquad \sum_t k_t=D. \]
Create \(k_t\) identical agents of each type \(t\), retaining the reduced supplies. This finite instance is negative: if all individual utilities were nonnegative, summing their allocations within each type would yield a forbidden allocation for the reduced society.

Let \(r\) be equilibrium prices for this finite instance. Average the bundles of the \(k_t\) identical agents, obtaining \(\bar x_t\). Their common demand set is convex, so \(\bar x_t\) is also optimal and satisfies \(r\cdot\bar x_t=-1\). Define
\[ z_t=k_t\bar x_t,\qquad a_t=D\bar x_t,\qquad p=r/D. \]
Then
\[ p\cdot a_t=-1, \]
and \(a_t\) is optimal: a bundle \(y\) is affordable at \(p\) precisely when \(y/D\) is affordable at \(r\), and utilities scale by \(D\).

For completeness, every equilibrium of the reduced instance has the following price signs:

• If \(j\in G\), then \(p_j>0\). A type with \(u_{tj}>0\) would otherwise improve without bound by adding item \(j\) to an affordable bundle.
• If \(j\in B\), then \(p_j<0\). Some type receives a positive amount of \(j\); Lemma 1 gives \(u_{tj}=\lambda_t p_j<0\), forcing both \(\lambda_t>0\) and \(p_j<0\).

Every type has negative expenditure and therefore consumes a class in \(B\). Its coefficient there is strictly negative, so Lemma 1 forces \(\lambda_t>0\). Thus every type obtains strictly negative utility.

Finally, restore each \(j\in Z\), set \(p_j=0\), and assign its supply to any type with \(u_{tj}=0\). The same multipliers certify optimality: all coefficients on these classes are nonpositive, and allocated coefficients are zero.

We have proved:

Lemma 2. Every promised instance admits an equilibrium in which every type has strictly negative utility, with prices positive on \(G\), negative on \(B\), and zero on \(Z\).

The integer \(D\) was used only in this existence proof.

3. Computing all equilibria with strictly negative utilities

We now give an algorithm operating directly on the \(\tau\) types and their rational masses.

3.1 Demand graphs are constant on price faces

Consider prices on \(G\cup B\), with the signs from Lemma 2. For each type, define
\[ \lambda_t(p)=\min_{b\in B}\frac{u_{tb}}{p_b}>0. \]

Lemma 1 shows that demand is bounded precisely when
\[ \frac{u_{tg}}{p_g}\le\lambda_t(p)\qquad\text{for every }g\in G. \]
Indeed, on a bad class the dual inequality requires
\[ \lambda_t\le\frac{u_{tb}}{p_b}, \]
whereas on a good class it requires the reverse inequality. An optimal bundle spends a negative amount, so it uses a bad class with equality; hence its multiplier must be the displayed minimum.

For prices satisfying the boundedness condition, define the bipartite demand graph \(E(p)\) by
\[ (t,j)\in E(p) \quad\Longleftrightarrow\quad u_{tj}=\lambda_t(p)p_j, \qquad j\in G\cup B. \]

Use the hyperplanes
\[ p_j=0 \]
and
\[ u_{tj}p_k-u_{tk}p_j=0 \qquad (t\in T,\ j<k,\ j,k\in G\cup B). \]
There are at most
\[ N=m+\tau\binom m2 \]
such hyperplanes. On each relatively open face, including faces of lower dimension, all ratio comparisons have fixed signs. Consequently, boundedness and the graph \(E(p)\) are constant there.

Faces of lower dimension are essential because they encode ties.

3.2 A demand graph determines at most one equilibrium price

Discard a face if demand is unbounded or an item vertex is isolated.

Consider a connected component \(C\) of its demand graph. Every type has an incident bad class. On every graph edge, both the utility coefficient and price are nonzero. If a type connects item classes \(j\) and \(k\), then
\[ \frac{p_k}{p_j}=\frac{u_{tk}}{u_{tj}}. \]
Following paths therefore expresses all prices in \(C\) as
\[ p_j=c_j\rho_C, \]
where the \(c_j\) are nonzero rational numbers. Any inconsistent relation causes the face to be discarded.

All types in \(C\) spend only on its item classes, and these classes can be assigned only to its types. Summing aggregate budgets gives
\[ \sum_{j\in C}q_jp_j=-\sum_{t\in C}\mu_t. \]
Therefore
\[ \rho_C = -\frac{\sum_{t\in C}\mu_t} {\sum_{j\in C}q_jc_j}. \]
A zero denominator makes equilibrium impossible, since the numerator is strictly positive. Otherwise, the component prices are uniquely determined and rational.

Compute these prices and check that they belong to the original face.

This is the weighted version of the price reconstruction in Section 3.3 of [Garg–McGlaughlin](https://www.ifaamas.org/Proceedings/aamas2020/pdfs/p420.pdf); the normalization uses component mass rather than an agent count.

3.3 All allocations at a candidate price form one rational polytope

Restore \(p_j=0\) on \(Z\). For a surviving candidate \(p\), define \(P(p)\) by
\[ z_{tj}\ge0, \qquad \sum_tz_{tj}=q_j, \qquad \sum_jp_jz_{tj}=-\mu_t, \]
together with
\[ z_{tj}=0 \quad\text{if }j\in G\cup B\text{ and }(t,j)\notin E(p), \]
and
\[ z_{tj}=0 \quad\text{if }j\in Z\text{ and }u_{tj}<0. \]

These are rational linear constraints. Lemma 1 proves both directions:

• Every point of \(P(p)\), together with \(p\), is an equilibrium.
• Every equilibrium with strictly negative utilities at \(p\) belongs to \(P(p)\).

All these allocations give type \(t\) representative utility \(-\lambda_t(p)<0\).

Test \(P(p)\) for feasibility by rational linear programming. Retain each nonempty polytope. Lemma 2 ensures that at least one survives; a rational feasible point gives one exact equilibrium.

3.4 Enumeration and bit complexity

An arrangement of \(N\) hyperplanes in dimension at most \(m\) has
\[ O\bigl((m+1)^2(N+1)^m\bigr) \]
faces of all dimensions. To see a sufficient bound, a face of codimension \(k\) has its affine span determined by \(k\) independent hyperplanes. For each such span, the restricted arrangement has at most
\[ \sum_{\ell=0}^{m-k}\binom N\ell \]
full-dimensional regions. Summing over choices of defining hyperplanes gives the stated bound.

Faces can be enumerated incrementally. When adding a hyperplane, test the three possible signs for each current face by linear programming. Strict feasibility can be tested by imposing
\[ -1\le p_j\le1 \]
and replacing all required strict inequalities by inequalities with a common margin \(\delta\), then maximizing \(\delta\). Homogeneity makes a positive margin equivalent to nonemptiness of the specified relatively open face. Thus at most
\[ O\bigl((m+1)^2(N+1)^{m+1}\bigr) \]
linear-programming tests suffice.

Price reconstruction has polynomial bit complexity. An item-to-item simple path uses at most \(m-1\) connecting types, so each \(c_j\) is a product of at most \(m-1\) input ratios. Component mass sums and subsequent rational arithmetic also have bit length polynomial in \(m,\tau,L\). Each allocation polytope has \(\tau m\) variables and \(O(\tau m+\tau+m)\) constraints.

Consequently, a sufficient total bound is
\[ (\tau m^2+m+1)^{m+1}\operatorname{poly}(\tau,m,L). \]
The number of retained pieces is at most
\[ O\bigl((m+1)^2(\tau m^2+m+1)^m\bigr). \]

This proves polynomial-time computation of one exact equilibrium for every fixed \(m\), without expanding binary-encoded masses.

4. A continuum of prices with three item classes

Take two types \(A,B\), with
\[ \mu_A=\mu_B=\frac12,\qquad q_1=q_2=q_3=1, \]
and utilities
\[ u_A=(0,0,-1),\qquad u_B=(-1,-1,-1). \]

The instance is negative. Nonnegative utility for \(B\) would require \(z_B=0\); nonnegative utility for \(A\) would require \(z_{A3}=0\). Together these contradict the positive supply of class \(3\).

For every real \(s\in[0,1/2]\), set
\[ p(s)=\left(-s,-\frac12+s,-\frac12\right) \]
and use the aggregate allocation
\[ z_A=(1,1,0),\qquad z_B=(0,0,1). \]
The representative bundles are
\[ a_A=(2,2,0),\qquad a_B=(0,0,2). \]
Both spend exactly \(-1\).

Type \(A\)'s utility is always nonpositive and its allocated utility is zero, so its bundle is maximizing.

For type \(B\), take \(\lambda_B=2\). Since \(s\in[0,1/2]\),
\[ (-1,-1,-1) \le 2p(s)=(-2s,-1+2s,-1) \]
coordinatewise, with equality on class \(3\). Lemma 1 certifies that \(a_B\) is maximizing.

Hence every \(s\in[0,1/2]\) gives an equilibrium, with a distinct price vector. A finite union
\[ \bigcup_{k=1}^K\bigl(P_k\times\{p^{(k)}\}\bigr) \]
has only finitely many price vectors and cannot contain this equilibrium set. Requiring the listed prices to be rational creates a further obstruction: irrational choices of \(s\) are also equilibria.

For every \(m>3\), add item classes valued at zero by both types, with positive rational supplies and zero prices, and assign them to \(A\). The same proof applies.

Thus, for every fixed \(m\ge3\), the requested representation can fail to exist.

5. All equilibria for one or two item classes

5.1 One item class

Negativity forces
\[ u_{t1}<0\qquad\text{for every }t: \]
otherwise the entire supply could be assigned to a type valuing it nonnegatively.

Summing budgets gives \(p_1q_1=-1\), and each type's budget then determines its allocation:
\[ p_1=-\frac1{q_1},\qquad z_{t1}=\mu_tq_1. \]
These bundles are optimal by Lemma 1. The equilibrium is unique and computable by polynomial-time rational arithmetic.

5.2 Two item classes without a neutral class

There is at least one class in \(B\). If the other class is also in \(B\), or is in \(G\), the price-sign argument in Section 2 applies to every equilibrium.

Every type must consume a negatively priced bad class, whose utility coefficient is strictly negative. Hence every multiplier is positive. Section 3 therefore already computes all equilibria.

5.3 One strictly bad class and one neutral class

Let \(b\in B\) and \(n\in Z\). In every equilibrium, \(p_b<0\).

We first prove \(p_n\le0\). If \(p_n>0\), any type consuming \(n\) satisfies, by Lemma 1,
\[ u_{tn}=\lambda_t p_n. \]
Because \(u_{tn}\le0\), this forces \(\lambda_t=0\) and \(u_{tn}=0\). Such a type cannot consume \(b\), since \(u_{tb}<0\). Its expenditure is therefore nonnegative, contradicting its budget \(-1\). No type could consume \(n\), contradicting market clearing.

If \(p_n=0\), budgets and market clearing force
\[ p_b=-\frac1{q_b},\qquad z_{tb}=\mu_tq_b. \]
The neutral class can be assigned exactly to types with \(u_{tn}=0\). This gives one rational allocation polytope.

It remains to handle \(p_n<0\). Both prices are now negative, all utility coefficients are nonpositive, and the optimal multiplier is
\[ \lambda_t(p) = \min\left\{\frac{u_{tb}}{p_b},\frac{u_{tn}}{p_n}\right\}. \]
Demand edges are exactly the classes attaining this minimum.

The same two-dimensional hyperplane arrangement enumerates these graphs. The only new issue is a zero multiplier. If \(\lambda_t=0\), then \(u_{tn}=0\), while \(u_{tb}<0\); thus this type has only one demand edge, to \(n\).

Therefore zero multipliers do not invalidate price reconstruction. Every type connecting the two item vertices has a positive multiplier and imposes a nonzero rational price ratio. If the vertices are connected, this ratio and the component budget sum determine both prices. If they are disconnected, each one-item component is normalized separately by
\[ q_jp_j=-\sum_{t\in C_j}\mu_t. \]
In either case there is at most one rational equilibrium price vector per face.

At each candidate price, impose market clearing, aggregate budgets, nonnegativity, and zero allocation outside the demand graph. Lemma 1 again proves that the resulting rational polytope contains exactly all equilibrium allocations at that price, including those with zero utility.

This enumerates all equilibria for \(m=2\). A sufficient running-time bound is
\[ (\tau+1)^3\operatorname{poly}(\tau,L), \]
with \(O((\tau+1)^2)\) output pieces.

6. What the finite-agent results extend to

Binary-encoded masses are not an obstacle to fixed-item polynomial-time computation: the component normalization uses \(\sum_{t\in C}\mu_t\), and allocation feasibility uses budgets \(-\mu_t\).

The obstacle to the requested representation of all equilibria is instead the demand convention. Without tie-breaking, zero-utility maximizers can generate a continuum of prices. Under the additional requirement that every equilibrium utility be strictly negative, Section 3 gives the requested finite rational representation for every fixed \(m\); under the task's actual definition, Section 4 prevents that conclusion from \(m=3\) onward.

⟨structured verdict parsed — rendered above⟩

Verification report

Verdict: proved with one minor completeness gap. The polynomial-time algorithm for one equilibrium is sound in substance. The continuum counterexample is correct and shows that, for every fixed \(m\ge3\), the requested representation of all equilibria need not exist. The arguments for computing all equilibria when \(m=1,2\) also stand.

The missing clarification concerns the completeness of Section 3: Lemma 2 establishes the existence of an equilibrium with the specified price signs, but Section 3 needs those signs for every equilibrium with strictly negative utilities. The arguments already written cover the good and strictly bad classes; the neutral classes require an additional routine justification.

1. Aggregate budgets and Lemma 1

The scaling is correct. Since \(\mu_t>0\), substituting \(x=\mu_t y\) bijectively maps the representative demand problem to the aggregate demand problem. The budget becomes \(-\mu_t\), and the objective is multiplied by a positive constant. Thus optimality is preserved.

The displayed dual is also correct: the multiplier is constrained by \(\lambda_t\ge0\), the dual inequalities are \(u_{tj}\le\lambda_t p_j\), and the dual objective is \(-\lambda_t\).

For the forward direction, the given bundle ensures primal feasibility, and its being a maximizer ensures a finite attained optimum. These are the required hypotheses for linear-programming strong duality and dual attainment. Complementary slackness gives the stated support condition.

For the converse, both inequalities have the correct direction, including when prices are negative. The support condition and budget equality give attained utility \(-\lambda_t\). Consequently, the distinction between positive and zero multipliers is valid and essential.

Finding: correct.

2. Existence with strictly negative utilities

Partition and deletion

The argument that \(B\ne\varnothing\) is valid. If every class had a nonnegative-valuing type, assigning each class to such a type would give every type nonnegative utility, contrary to the promise.

Deleting \(Z\) preserves negativity: the specified extension assigns each deleted class to a zero-valuing type and therefore preserves every type’s utility.

Cited existence theorem

I checked [Garg–McGlaughlin, Theorem 2.4 and Definition 2.1](https://www.ifaamas.org/Proceedings/aamas2020/pdfs/p420.pdf). The negative-instance clause supplies an equilibrium with equal budgets \(-1\); its demand problem uses unrestricted nonnegative bundles and the stated budget inequality.

The relevant hypotheses are satisfied here:

• The cloned agent set is finite, and every multiplicity \(k_t\) is a positive integer.
• Utilities remain linear.
• The proof establishes negativity of the cloned instance.
• Positive supplies can be converted to unit supplies by the stated coordinate change.

The source’s negative-instance condition is expressed through its nonnegative-utility cone. The prover’s stronger assertion that no feasible allocation gives all agents nonnegative utility implies that condition.

Cloning and rescaling

The cloning argument correctly uses \(D\) only for existence. It does not impose an exponential population expansion on the algorithm.

Averaging identical agents’ bundles preserves optimality because their feasible set and objective are common and linear. The quantities \(z_t=k_t\bar x_t\) clear the original supplies. Since \(\mu_t=k_t/D\), the representative bundle is indeed \(a_t=D\bar x_t\).

The price rescaling \(p=r/D\) preserves both budget equality and optimality, as claimed.

Signs and restoration

On the reduced instance:

• A class liked positively by some type must have positive price, because otherwise that type’s demand objective is unbounded above.
• A strictly bad class must have negative price by market clearing and Lemma 1.
• Negative expenditure then requires consumption of a strictly bad class, which forces a positive multiplier.

Restoring neutral classes at zero prices, allocated only to zero-valuing types, preserves the dual inequalities and support equalities.

Finding: Lemma 2 is established.

3. Algorithm for strictly negative equilibria

Issue 1 — minor: completeness of the price-sign restriction

Where: Section 3.1, “Consider prices on \(G\cup B\), with the signs from Lemma 2,” together with the claim that Section 3 computes all strictly negative equilibria.

What: Lemma 2 proves existence with those signs. It does not itself establish that every equilibrium with strictly negative utilities has zero prices on \(Z\).

The earlier price-sign arguments cover \(G\) and \(B\). The universal zero-price statement for \(Z\) is omitted. Without stating it, the write-up has not explicitly justified restricting enumeration to the prescribed signs and later restoring \(Z\) at zero prices.

Minimum clarification: State and justify that every equilibrium with positive multipliers for all types has zero prices on every neutral class, using Lemma 1 and market clearing.

This is a minor gap: it is a routine consequence of the existing characterization and requires no new mathematical machinery.

Ratio characterization

Within the prescribed price signs, the ratio inequalities are correct:

• Division by a negative bad price reverses the dual inequality.
• Division by a positive good price preserves it.
• Every budget-tight optimal bundle must consume a bad class.
• Equality on a consumed bad class determines the multiplier as the minimum bad ratio.

Feasibility of the demand problem is automatic here because \(B\ne\varnothing\) and its prices are negative. Thus the boundedness characterization does not overlook an infeasible demand problem.

Finding: correct.

Hyperplane faces and demand graphs

The listed hyperplanes capture all relevant ratio equalities. On each face respecting the required price signs, the denominator signs are fixed, so the signs of the cross-products determine the ratio comparisons.

Enumerating lower-dimensional faces correctly retains ties. Identically zero equations cause no difficulty: they impose equality everywhere.

Finding: correct.

Price reconstruction

For an actual equilibrium, every demanded edge in \(G\cup B\) has nonzero utility and nonzero price. The path equations therefore legitimately determine rational relative prices.

The component budget identity is correct: allocations use only demanded edges, so summing budgets over a component accounts for exactly the supplies of its item vertices.

The normalization formula follows from this identity. Its numerator is strictly positive because the component contains types with positive masses. Hence a zero denominator rules out equilibrium, and a nonzero denominator determines a unique scale.

Checking that the reconstructed vector belongs to the original face is necessary and is explicitly included.

Finding: correct.

Allocation polytopes

The constraints correctly enforce nonnegativity, clearing, aggregate budget equality, and allocation only on optimal edges. On neutral classes, the permitted recipients have utility coefficient zero.

Lemma 1 supplies both soundness and completeness at each candidate price. Every feasible allocation has strictly negative representative utility because the multiplier used here is positive.

The allocation set is bounded by supply constraints, so describing it as a polytope is correct. Rational linear programming can return a rational feasible point.

Finding: correct, subject to the minor universal price-sign clarification above.

4. Enumeration and bit complexity

The stated face-count bound is a valid sufficient upper bound. Counting choices of independent defining hyperplanes and regions of their restrictions can overcount faces, which is harmless for an upper bound.

The incremental enumeration procedure is also valid. All hyperplanes are homogeneous, so any feasible strict sign pattern can be scaled into the bounded box while retaining a positive common margin. Conversely, a positive margin certifies the required strict signs.

The rational bit-complexity argument is adequate:

• Relative-price paths use at most \(m-1\) connecting types.
• Products of that many input ratios have polynomial bit length.
• Component mass sums and normalization preserve polynomial bit length.
• Face tests and allocation feasibility use rational linear programs of polynomial description length.

Thus the sufficient running-time bound
\((\tau m^2+m+1)^{m+1}\operatorname{poly}(\tau,m,L)\)
is supported. For fixed \(m\), it is polynomial in \(\tau\) and \(L\).

Finding: correct.

5. Continuum counterexample

The example is negative. Type \(B\) can have nonnegative utility only if its bundle is zero, and type \(A\) can have nonnegative utility only if it receives none of class \(3\). Clearing class \(3\) makes these requirements incompatible.

The representative bundles are correctly obtained by dividing aggregate allocations by mass \(1/2\). Their expenditures are:

• Type \(A\): \(2(-s)+2(-1/2+s)=-1\).
• Type \(B\): \(2(-1/2)=-1\).

Type \(A\)’s allocated utility is zero, its global maximum.

For type \(B\), the multiplier \(2\) satisfies all dual inequalities precisely throughout \(s\in[0,1/2]\), and equality holds on its consumed class \(3\). The endpoint cases also satisfy these conditions.

Distinct values of \(s\) produce distinct prices. Therefore a finite union with singleton price coordinates cannot represent all these equilibria. Irrational values of \(s\) independently contradict the rational-price requirement.

Appending universally zero-valued classes preserves the promise, budget equalities, and optimality.

Finding: the obstruction is fully established for every fixed \(m\ge3\). It concerns the task’s actual demand convention and settles why the requested output may not exist.

6. All equilibria for \(m=1,2\)

One class

Negativity forces every utility coefficient to be strictly negative. Summing aggregate budgets determines the unique price, and individual budgets determine the unique allocation. Lemma 1 verifies optimality.

Finding: correct.

Two classes without a neutral class

There is a strictly bad class. Both possible partitions are covered, and the price-sign argument applies to every equilibrium. Every type must consume a strictly bad class and therefore has a positive multiplier.

Finding: Section 3 covers all equilibria in this case.

One strictly bad and one neutral class

The proof excluding a positive neutral price is correct: any recipient would have multiplier zero, could not consume the bad class, and could not meet its negative budget.

At zero neutral price, the stated bad price and bad allocations follow from budgets and clearing. Only zero-valuing types can receive the neutral class.

At negative neutral price, the minimum-ratio characterization is valid even when the minimum is zero. A zero-multiplier type has exactly the one neutral demand edge. Hence it does not introduce an undefined ratio when reconstructing relative item prices.

Connected and disconnected item vertices are both handled. The component budget normalization remains valid with zero-multiplier types. The allocation constraints then characterize exactly the equilibrium allocations.

The bound \((\tau+1)^3\operatorname{poly}(\tau,L)\), with \(O((\tau+1)^2)\) pieces, follows from the two-dimensional enumeration.

Finding: correct.

Overall assessment

The prover resolves the intended computational question, including identifying that the requested all-equilibria representation is unavailable in general. No false central step or incorrect critical computation was found.

One exact equilibrium is polynomial-time computable for every fixed \(m\). All equilibria in the requested representation are polynomial-time computable for \(m=1,2\); for \(m\ge3\), that representation can fail to exist. The only requested repair is the explicit completeness justification for neutral prices in the strictly negative-utility enumeration.

⟨structured verdict parsed — rendered above⟩