d4-journals-geb-2023-0130 (d4-journals-geb-2023-0130)

Given \(\tau\) types with rational masses \(\mu_t>0\) summing to \(1\), budgets \(w_t\), explicitly represented concave degree-one homogeneous utilities \(u_t\), homogeneous constraints \(A_t x\leq 0\), and per-capita supplies \(\bar s_j\), assuming an equilibrium exists, compute a common price vector \(p\) and type bundles \(x_t\) such that \(x_t\in\arg\max\{u_t(x):p^\top x\leq w_t,\ A_t x\leq 0,\ x\geq 0\}\), each type spends its budget, and \(\sum_t\mu_t x_{tj}=\bar s_j\) for every good \(j\).

A society is given by its support: the list of the \(\tau\) types with positive binary-rational masses \(\mu_t\), with \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) divisible goods. Type \(t\) has a positive rational per-capita budget \(w_t\), rational constraints \(A_t\in\mathbb Q^{\ell_t\times m}\), and a continuous, nonnegative, concave degree-one homogeneous utility \(u_t:\mathbb R_{\geq0}^m\to\mathbb R_{\geq0}\), positive on some bundle satisfying \(A_tx\leq0\). Supplies \(\bar s_j\geq0\) are rational and per capita.
Each utility is represented by a quantifier-free formula defining its graph, using rational polynomial equalities and inequalities; polynomials are listed explicitly with binary coefficients and exponents. These utility properties are promised. Let \(L\) be the total input bit length.
An equilibrium consists of signed prices \(p\in\mathbb R^m\) and one bundle \(x_t\in\mathbb R_{\geq0}^m\) per type satisfying \(x_t\in\arg\max\{u_t(x):p^\top x\leq w_t,\ A_tx\leq0,\ x\geq0\}\), \(p^\top x_t=w_t\), and \(\sum_t\mu_tx_{tj}=\bar s_j\) for every good. Any maximizing bundles satisfying these conditions are permitted.
An equilibrium is promised to exist. Exact output coordinates are encoded as real algebraic numbers by integer polynomials and rational isolating intervals.

Is exact equilibrium computation for this promised mass market solvable in polynomial time in \(m,\tau,L,\sum_t\ell_t\), or is it \(\mathrm{NP}\)-hard?

For finite-agent markets with homogeneous constraints and concave degree-one homogeneous utilities, ADMM is claimed to converge at rate \(O(1/k)\), with a utility-independent positive step size; an equilibrium characterization by convex optimization is also established. These are convergence and characterization results, rather than an exact bit-complexity classification. [Source](https://arxiv.org/pdf/2106.10412)
No result settling this exact mass-market problem with the stated utility and output encodings was verified.

Proven partial result: exponential output size and algebraic degree

Polynomial total running time is impossible under the stated explicit algebraic-number output encoding. I prove this using promised instances with $m=2$, $\tau=1$, no additional constraints, and a unique equilibrium.

The construction strengthens the result in the notes: its forced price is irrational of degree $2^n$, and every integer polynomial representing that price has a coefficient requiring at least $n2^n+1$ binary bits, although the input length is $\Theta(n)$.

This does not establish $\mathrm{NP}$-hardness. The classification therefore remains partial.

1. A succinct family of utilities

Fix $n\geq1$ and put $N=2^n$. There is one type, with mass and budget both equal to $1$. Supplies are
$$ \bar s=(1,1), $$
and there are no additional constraints.

Define
$$ f_N(t)=t+\frac{t^N}{2},\qquad t\geq0. $$
This function is continuous, strictly increasing, and maps $[0,\infty)$ onto itself. Let $h_N$ denote its inverse. Define
$$ u_N(a,b)= \begin{cases} a\,h_N(b/a),&a>0,\\ 0,&a=0, \end{cases} \qquad a,b\geq0. $$

The inverse notation is only a mathematical description. The actual input graph formula is
$$ a\geq0\ \land\ b\geq0\ \land\ z\geq0\ \land\ \left[ (a=0\land z=0) \ \lor\ \left(a>0\land z^N+2a^{N-1}z-2a^{N-1}b=0\right) \right]. $$

For $a>0$, the polynomial expression on the second branch is strictly increasing as a function of $z\geq0$: its derivative is
$$ Nz^{N-1}+2a^{N-1}>0. $$
Its value at $z=0$ is nonpositive, and it tends to infinity. Thus it has exactly one nonnegative root. Substituting $z=a\,h_N(b/a)$ verifies that this root is the stated utility.

The graph polynomial has three monomials, coefficients in $\{1,2,-2\}$, and exponents with $O(n)$ binary digits. All other market data have constant length. Consequently, the total input length satisfies
$$ L_n=\Theta(n). $$

2. Verification of all utility promises

Nonnegativity, positivity, and continuity

Nonnegativity follows from the definition. If $a,b>0$, then $b/a>0$, so $h_N(b/a)>0$ and $u_N(a,b)>0$. In particular, $(1,1)$ witnesses the required positivity on a feasible bundle.

Writing $z=u_N(a,b)$, its graph equation gives
$$ z^N+2a^{N-1}z=2a^{N-1}b. $$
For $a>0$, both terms on the left are nonnegative. Hence
$$ 0\leq z\leq b, \qquad z\leq 2^{1/N}a^{(N-1)/N}b^{1/N}. $$
The second bound tends to zero as $a$ tends to zero while $b$ remains bounded. It proves continuity at every point with $a=0$. Elsewhere, continuity follows from continuity of $h_N$.

Degree-one homogeneity

For $a>0$ and $\lambda>0$,
$$ u_N(\lambda a,\lambda b) =\lambda a\,h_N(b/a) =\lambda u_N(a,b). $$
The same identity holds when $a=0$, and when $\lambda=0$, by the zero boundary values.

Concavity

First, $h_N$ is concave. Indeed, $f_N$ is increasing and convex. For $v,w\geq0$ and $\theta\in[0,1]$, convexity gives
$$ f_N\!\left(\theta h_N(v)+(1-\theta)h_N(w)\right) \leq \theta v+(1-\theta)w. $$
Applying the increasing inverse $h_N$ yields
$$ \theta h_N(v)+(1-\theta)h_N(w) \leq h_N\!\left(\theta v+(1-\theta)w\right). $$

Now take $(a,b)$ and $(c,d)$ with $a,c>0$. For $0<\theta<1$, put
$$ e=\theta a+(1-\theta)c, \qquad \eta=\frac{\theta a}{e}. $$
Then
$$ \frac{\theta b+(1-\theta)d}{e} =\eta\frac ba+(1-\eta)\frac dc. $$
Concavity of $h_N$, multiplied by $e$, gives
$$ u_N\!\left(\theta(a,b)+(1-\theta)(c,d)\right) \geq \theta u_N(a,b)+(1-\theta)u_N(c,d). $$
The cases $\theta=0,1$ are equalities.

For arbitrary nonnegative endpoints, add $\varepsilon>0$ to both first coordinates, apply the preceding inequality, and let $\varepsilon$ decrease to zero. Continuity proves concavity on the entire nonnegative orthant.

Thus every promised utility property holds.

3. Existence and uniqueness of equilibrium

Let
$$ s=(1,1),\qquad r=u_N(s)=h_N(1). $$
By definition,
$$ r^N+2r-2=0. $$
Since $f_N(0)=0$ and $f_N(1)=3/2$, we have
$$ 0<r<1. $$

Because there is one type of mass $1$, market clearing forces its bundle to be $s$.

Suppose $p$ is an equilibrium price vector. Full expenditure requires
$$ p^\top s=1, $$
so $p\neq0$. For every direction $v$ with $p^\top v=0$, sufficiently small perturbations $s+\varepsilon v$ of either sign remain strictly positive and spend exactly the same budget. Optimality of $s$ and differentiability there imply
$$ \nabla u_N(s)^\top v=0. $$
Therefore $\nabla u_N(s)$ is proportional to $p$:
$$ \nabla u_N(s)=\lambda p. $$
Differentiating homogeneity along the ray through $s$ gives
$$ \nabla u_N(s)^\top s=u_N(s)=r. $$
Taking the scalar product of the proportionality with $s$ shows that $\lambda=r$. Thus every equilibrium necessarily has
$$ p=\frac{\nabla u_N(s)}r. $$
This argument also excludes alternative signed equilibrium prices.

Inverse differentiation gives
$$ h_N'(1)=\frac{1}{1+\frac N2r^{N-1}}. $$
Since $u_N(a,b)=a\,h_N(b/a)$,
$$ \frac{\partial u_N}{\partial b}(s)=h_N'(1), \qquad \frac{\partial u_N}{\partial a}(s)=r-h_N'(1). $$
Using $r^N=2(1-r)$, the forced prices simplify to
$$ p_2=\frac{1}{N-(N-1)r}, \qquad p_1=1-p_2. $$
Because $0<r<1$, both prices are strictly positive and their sum is $1$.

It remains to verify optimality at these prices. Concavity and differentiability at $s$ imply the supporting inequality
$$ u_N(x)\leq u_N(s)+\nabla u_N(s)^\top(x-s) $$
for every $x\geq0$. Explicitly, concavity gives, for $0<t<1$,
$$ u_N(x)-u_N(s) \leq \frac{u_N(s+t(x-s))-u_N(s)}t. $$
Letting $t$ decrease to zero proves the supporting inequality, including for boundary bundles.

Substituting $\nabla u_N(s)=rp$ and $p^\top s=1$ gives
$$ u_N(x)\leq r\,p^\top x. $$
Every affordable bundle therefore satisfies $u_N(x)\leq r=u_N(s)$. Hence $s$ maximizes utility, spends its full budget, and clears the market.

The equilibrium exists and all its coordinates are unique.

4. The forced price has exponential algebraic degree

Set
$$ \alpha=p_2=\frac{1}{N-(N-1)r}. $$

We first prove that
$$ F_N(T)=T^N+2T-2 $$
is irreducible over $\mathbb Q$.

An integer polynomial is called *primitive* if its coefficients have greatest common divisor $1$. The product of two primitive integer polynomials is primitive: otherwise, reduction modulo a prime dividing every product coefficient would give a zero product of two nonzero polynomials over a field, which is impossible.

This observation also shows that a primitive integer polynomial admitting a factorization over $\mathbb Q$ admits one over $\mathbb Z$. To see this, scale the rational factors to primitive integer polynomials. Their product is primitive, so the remaining rational scalar must be an integer, because its denominator divides every product coefficient. Primitivity of the original polynomial forces that scalar to be $1$ or $-1$.

If the monic polynomial $F_N$ were reducible, it would therefore factor into monic integer polynomials of positive degree. Modulo $2$, their product would be $T^N$. Each monic factor must consequently reduce to a positive-degree power of $T$, so both constant coefficients would be even. Their product would be divisible by $4$, contradicting the constant coefficient $-2$ of $F_N$. This proves irreducibility.

It follows that
$$ [\mathbb Q(r):\mathbb Q]=N. $$
Moreover,
$$ r=\frac{N\alpha-1}{(N-1)\alpha}. $$
Thus $\mathbb Q(r)=\mathbb Q(\alpha)$, and
$$ [\mathbb Q(\alpha):\mathbb Q]=N=2^n. $$

5. Every representing polynomial needs an exponentially long coefficient

Substitute the expression for $r$ into $F_N(r)=0$ and clear denominators. This gives
$$ P_N(\alpha)=0, $$
where
$$ P_N(T) =(NT-1)^N+ 2(N-1)^{N-1}T^{N-1}(T-1). $$
Its degree is $N$, and its leading coefficient is
$$ D_N=N^N+2(N-1)^{N-1}. $$
Because $N$ is even, its constant coefficient is $1$. Hence $P_N$ is primitive.

The algebraic degree of $\alpha$ is $N$, so $P_N$ is irreducible over $\mathbb Q$ and is a rational scalar multiple of its minimal polynomial.

Let $Q\in\mathbb Z[T]$ be any nonzero polynomial satisfying $Q(\alpha)=0$. Minimal-polynomial divisibility gives
$$ Q=P_NH,\qquad H\in\mathbb Q[T]. $$
In fact, $H$ has integer coefficients. Write
$$ H=\frac abH_0, $$
where $H_0$ is primitive, $a,b$ are coprime integers, and $b>0$. Since $P_NH_0$ is primitive and $Q$ has integer coefficients, $b$ divides every coefficient of $P_NH_0$. Therefore $b=1$.

Consequently, the leading coefficient of $Q$ is a nonzero integer multiple of $D_N$. In particular,
$$ \left|\operatorname{lc}(Q)\right| \geq D_N >N^N =2^{n2^n}. $$
Writing this coefficient explicitly in binary requires at least
$$ n2^n+1 $$
magnitude bits.

This conclusion permits arbitrary degree, sparse polynomials, reducible polynomials, and nonminimal representations. It does not depend on the choice of isolating interval.

For completeness, a short isolating interval is available: $P_N$ has exactly one root in $(1/N,1)$. On this interval, the substitution
$$ r=\frac{NT-1}{(N-1)T} $$
is a strictly increasing bijection onto $(0,1)$, and $F_N$ has exactly one root there. Thus the coefficient requirement persists even though an isolating interval with $O(n)$ bits exists.

Since $L_n=\Theta(n)$ while all other complexity parameters are fixed, every permitted equilibrium output has length
$$ 2^{\Omega(L_n)}. $$
A bit-model algorithm must spend at least the number of steps needed to write its output. Therefore exact equilibrium computation cannot have polynomial total running time in the requested parameters, irrespective of whether $\mathrm P=\mathrm{NP}$.

6. What is settled and what remains open

The polynomial-total-time alternative is ruled out under the stipulated output encoding. The construction also proves exponential algebraic degree for a forced equilibrium coordinate.

The cited paper’s convex characterization and ADMM convergence statements concern optimization and iterative convergence; they do not remove this explicit-output requirement. [Jalota et al., *Fisher Markets with Linear Constraints*](https://arxiv.org/pdf/2106.10412).

An output-size lower bound is not a reduction from an $\mathrm{NP}$-hard problem. No such reduction is established here. To finish the requested classification, one must specify a reduction notion for this exact-output search problem and prove hardness while respecting every promise and handling potentially exponential answers.

⟨structured verdict parsed — rendered above⟩

Verification report

The construction and its output-size lower bound are correct. It establishes that polynomial total running time is impossible under the intended explicit algebraic-number output encoding, even for a single type and two goods. It does not establish $\mathrm{NP}$-hardness, so the requested complexity classification remains partial.

No false mathematical step was found.

1. Input construction and utility representation

For $n\geq1$, the choice $N=2^n$ ensures $N\geq2$. The function
$$ f_N(t)=t+\frac{t^N}{2} $$
is continuous, strictly increasing, convex, and unbounded on $[0,\infty)$. Consequently, its inverse $h_N$ exists on the entire nonnegative half-line.

For $a>0$, the graph equation
$$ z^N+2a^{N-1}z-2a^{N-1}b=0 $$
has exactly one nonnegative solution: its left-hand side is strictly increasing in $z$, is nonpositive at zero, and tends to infinity. Substituting $z=a\,h_N(b/a)$ gives the stated equation. The separate branch for $a=0$ assigns exactly the stated boundary value.

The formula is quantifier-free and uses rational polynomial relations with explicitly listed monomials. Binary encodings of $N$ and $N-1$ require $\Theta(n)$ bits. Since the remaining data have constant size, the claim
$$ L_n=\Theta(n) $$
is justified. The masses, budget, supplies, and absence of additional constraints satisfy the input requirements.

2. Utility promises

All promised utility properties are verified.

• Nonnegativity and positivity: The inverse is nonnegative, and $h_N(b/a)>0$ whenever $a,b>0$. Thus $(1,1)$ witnesses positivity on a feasible bundle.
• Continuity: The graph equation implies both displayed bounds. In particular,

$$ z\leq 2^{1/N}a^{(N-1)/N}b^{1/N} $$
tends to zero as $a$ tends to zero with $b$ bounded, because $N\geq2$. This covers every boundary point with $a=0$, including the origin. Continuity elsewhere follows from continuity of the inverse.

• Homogeneity: The calculation covers positive scaling, and the boundary definition covers $a=0$ and zero scaling.
• Concavity: The inverse-concavity argument has the correct inequality direction. The perspective calculation uses valid weights because $a,c>0$. Passing to arbitrary nonnegative endpoints by continuity is legitimate.

There is no missing boundary case that invalidates these conclusions.

3. Equilibrium existence and uniqueness

Market clearing forces the only type’s bundle to be
$$ s=(1,1). $$
The equation for $r=u_N(s)$ and the bound $0<r<1$ are correct.

Differentiability at $s$ is justified by the inverse differentiation rule: $f_N$ is differentiable and its derivative is strictly positive at $r$. For an equilibrium price, full expenditure gives $p^\top s=1$, hence $p\neq0$. Every sufficiently small perturbation in a direction orthogonal to $p$ remains positive and has the same expenditure. Optimality therefore forces the gradient to annihilate those directions, giving
$$ \nabla u_N(s)=\lambda p. $$
Differentiating homogeneity and taking the scalar product with $s$ correctly identifies $\lambda=r$. This necessity argument applies to signed prices as required.

The derivative calculation and price simplification are correct:
$$ p_2=\frac{1}{N-(N-1)r}, \qquad p_1=1-p_2. $$
Since
$$ 1<N-(N-1)r<N, $$
both prices are positive.

The supporting inequality is proved directly from concavity and differentiability, including for boundary bundles. Its substitution yields
$$ u_N(x)\leq r\,p^\top x. $$
Thus every affordable bundle has utility at most $r$, and $s$ attains that value. Existence, expenditure, clearing, and uniqueness of the equilibrium coordinates all follow.

The proof does not require uniqueness of every individual maximizing bundle; clearing already forces the equilibrium bundle.

4. Algebraic degree

The irreducibility argument for
$$ F_N(T)=T^N+2T-2 $$
is valid.

The primitive-product argument correctly establishes the integer-factorization consequence of Gauss’s lemma. Because $F_N$ is monic, a hypothetical factorization can be taken into monic integer factors. Their reductions modulo $2$ retain their positive degrees and multiply to $T^N$, so both reduced factors are positive-degree powers of $T$. Both integer constant coefficients would therefore be even, contradicting the constant coefficient $-2$.

Consequently,
$$ [\mathbb Q(r):\mathbb Q]=N. $$
The displayed rational transformations between $r$ and $\alpha=p_2$ have nonzero denominators and establish equality of their generated fields. Hence $\alpha$ also has degree $N=2^n$.

5. Coefficient and output-size lower bound

Clearing denominators gives exactly
$$ P_N(T)=(NT-1)^N+ 2(N-1)^{N-1}T^{N-1}(T-1). $$
Its leading coefficient is
$$ D_N=N^N+2(N-1)^{N-1}, $$
and its constant coefficient is $1$, since $N$ is even. Thus it is primitive and has degree $N$. The already established degree of $\alpha$ implies that $P_N$ is irreducible over $\mathbb Q$.

For any nonzero integer polynomial $Q$ vanishing at $\alpha$, minimal-polynomial divisibility gives $Q=P_NH$ over $\mathbb Q$. The primitive-product argument correctly shows that $H$ must have integer coefficients: coprimality of the scalar numerator and denominator forces that denominator to divide every coefficient of a primitive product.

Therefore the leading coefficient of $Q$ is a nonzero integer multiple of $D_N$. The bound
$$ |\operatorname{lc}(Q)|>2^{n2^n} $$
is correct and implies at least $n2^n+1$ binary magnitude bits.

This argument covers higher-degree, reducible, and sparse representing polynomials. It establishes a coefficient-size obstruction independently of whether polynomial exponents are encoded sparsely.

The isolating-interval claim also checks out. The stated substitution maps $(1/N,1)$ strictly increasingly onto $(0,1)$, with nonzero denominators throughout. Its endpoints are not roots. The interval therefore isolates $\alpha$ and has endpoints of $O(n)$ encoding length.

Under the intended convention that integer coefficients are written explicitly in binary, every equilibrium output consequently has length
$$ 2^{\Omega(L_n)}. $$
The conclusion excluding polynomial total running time follows.

6. Scope and actionable feedback

The distinction between this lower bound and $\mathrm{NP}$-hardness is correct. Exponential required output length does not itself supply a hardness reduction.

The discussion of the cited paper is appropriately limited: its optimization and iterative-convergence results do not eliminate the cost of writing an exact algebraic output. The paper describes convex formulations and ADMM convergence guarantees, consistent with that limited observation. [Jalota et al., *Fisher Markets with Linear Constraints*](https://arxiv.org/pdf/2106.10412).

Major unresolved issue — completion of the assigned classification. The output rules out polynomial total time but provides no $\mathrm{NP}$-hardness reduction. This is an acknowledged limitation of the partial result, rather than a flaw in its proof.

To complete the assignment, the prover must specify the reduction notion for the promised exact-output search problem and supply a hardness proof under that notion. The proof must preserve the input promises and justify how the reduction handles potentially exponential output length. No additional clarification is needed to verify the lower bound already written.

⟨structured verdict parsed — rendered above⟩