Answer: Every valid instance has an equilibrium, and an exact equilibrium can be computed in time \(\operatorname{poly}(m,\tau,L)\). Thus equilibrium existence is polynomial-time solvable.
Corollary 9. — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximatewalrasian is strongly \NP-hard even if all the agents have identical 3-demand budget-additive valuation functions.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set \(T\) of complete \(3\)-demand budget-additive department types, rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), and rational per-capita supplies \(q_j\ge 0\) for \(m\) staff categories, decide whether a Walrasian equilibrium exists and compute one if it does. Represent an allocation by masses \(x_{t,a}\ge 0\) assigned to integral category-count bundles \(a\in\mathbb{Z}_{\ge 0}^m\) with \(\sum_j a_j\le 3\), satisfying \(\sum_a x_{t,a}=\mu_t\) and \(\sum_{t,a}a_jx_{t,a}\le q_j\). A supporting price vector \(p\ge 0\) must make every bundle receiving positive mass utility-maximizing for its type, with \(p_j=0\) whenever category \(j\) has slack supply.
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types.
There are \(m\ge1\) staff categories with binary-rational per-capita supplies \(q_j\ge0\). Each type specifies binary-rational values \(w_{tj}\ge0\) and a valuation cap \(B_t\ge0\). Its complete bundle domain is \(A=\{a\in\mathbb Z_{\ge0}^m:\sum_j a_j\le3\}\), including the empty bundle and repeated units of a category; on this domain, \(v_t(a)=\min\{B_t,\sum_jw_{tj}a_j\}\).
Utility at prices \(p\in\mathbb R_{\ge0}^m\) is \(v_t(a)-p\cdot a\); the valuation cap imposes no spending constraint. Demand maximizes this utility over all \(a\in A\), with all ties allowed.
An equilibrium consists of masses \(x_{t,a}\ge0\) and prices \(p\ge0\) satisfying \(\sum_a x_{t,a}=\mu_t\), \(\sum_{t,a}a_jx_{t,a}\le q_j\), and \(x_{t,a}>0\Rightarrow a\in\arg\max_{b\in A}(v_t(b)-p\cdot b)\). Whenever \(\sum_{t,a}a_jx_{t,a}<q_j\), require \(p_j=0\).
Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is deciding equilibrium existence and computing an equilibrium whenever one exists solvable in time polynomial in \(m,\tau,L\), or is the existence decision problem \(\mathrm{NP}\)-hard?
Discrete equilibrium existence and computation is strongly \(\mathrm{NP}\)-hard even for identical \(3\)-demand budget-additive valuations ([Deligkas–Melissourgos–Spirakis](https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p413.pdf)).
For a related continuum model, equilibrium existence is known with arbitrary quasilinear valuations and exact market clearing; that result does not state the computational complexity of this support-encoded problem ([Azevedo–Weyl–White](https://eduardomazevedo.github.io/papers/Azevedo-et-al-Walrasian.pdf)).
Every valid instance has an equilibrium, and an equilibrium can be computed exactly in time polynomial in \(m,\tau,L\).
The crucial feature is that each type’s mass may be divided among several demanded bundles. This makes the allocation problem a linear program whose dual supplies equilibrium prices.
Write \(n=|A|\). Introducing a slack coordinate \(a_0=3-\sum_{j=1}^m a_j\) gives a bijection between \(A\) and the nonnegative integer solutions of \(\sum_{j=0}^m a_j=3\). Consequently,
\( n=\binom{m+3}{3}=O(m^3). \)
This count includes the empty bundle and all bundles containing repeated units.
Enumerate these bundles and compute \(v_t(a)=\min\{B_t,\sum_j w_{tj}a_j\}\) for every \(t,a\). Each sum contains at most three units, so every computed valuation has binary encoding length \(O(L)\). Thus the valuation table can be constructed in \(O(\tau m^3\operatorname{poly}(L+\log(m+1)))\) bit operations.
Consider the following primal linear program, with variables \(x_{t,a}\):
\( \begin{aligned} \text{maximize}\quad& \sum_{t\in T}\sum_{a\in A}v_t(a)x_{t,a}\\ \text{subject to}\quad& \sum_{a\in A}x_{t,a}=\mu_t &&(t\in T),\\ & \sum_{t\in T}\sum_{a\in A}a_jx_{t,a}\le q_j &&(1\le j\le m),\\ & x_{t,a}\ge0 &&(t\in T,\ a\in A). \end{aligned} \)
This program allocates masses of whole bundles; it does not replace an individual’s bundle by a fractional bundle.
The primal is feasible: set \(x_{t,0}=\mu_t\) and all other variables to zero. Its feasible set is closed and bounded, because \(0\le x_{t,a}\le\mu_t\). Its objective is also bounded explicitly by
\( \sum_{t,a}v_t(a)x_{t,a} \le \sum_t B_t\sum_a x_{t,a} = \sum_t\mu_tB_t. \)
Associate a free dual variable \(u_t\) with each type equality and a nonnegative dual variable \(p_j\) with each supply inequality. The dual is
\( \begin{aligned} \text{minimize}\quad& \sum_{t\in T}\mu_tu_t+\sum_{j=1}^m q_jp_j\\ \text{subject to}\quad& u_t+\sum_{j=1}^m p_ja_j\ge v_t(a) &&(t\in T,\ a\in A),\\ & p_j\ge0 &&(1\le j\le m). \end{aligned} \)
The constraint for the empty bundle implies \(u_t\ge0\), although the equality multiplier was initially unrestricted.
The dual is feasible: take \(p=0\) and \(u_t=B_t\). Strong linear-programming duality applies because the primal is feasible with finite optimum. Hence both programs attain their optima, and their optimal objective values agree.
Let \(x\) be any optimal primal solution and \((u,p)\) any optimal dual solution. Define the aggregate allocation of category \(j\) by
\( y_j=\sum_{t,a}a_jx_{t,a}. \)
Using the type equalities, the difference between the dual and primal objective values is
\( \begin{aligned} \sum_t\mu_tu_t+\sum_jq_jp_j-\sum_{t,a}v_t(a)x_{t,a} ={}& \sum_{t,a}x_{t,a}\bigl(u_t+p\cdot a-v_t(a)\bigr)\\ &+\sum_jp_j(q_j-y_j). \end{aligned} \)
Every summand on the right is nonnegative:
Optimality makes the left side zero. Therefore every summand on the right is zero.
Demand optimality. If \(x_{t,a}>0\), then
\( u_t=v_t(a)-p\cdot a. \)
For every \(b\in A\), dual feasibility gives
\( v_t(b)-p\cdot b\le u_t=v_t(a)-p\cdot a. \)
Thus every bundle receiving positive mass maximizes the type’s utility over the complete domain \(A\). Ties cause no difficulty.
Unused supply. For every category \(j\),
\( p_j(q_j-y_j)=0. \)
If \(y_j<q_j\), this equality forces \(p_j=0\).
Together with primal feasibility and \(p\ge0\), these are exactly all the equilibrium conditions in the question. This proves existence for every valid instance, including instances with zero supplies or zero valuations.
The valuation cap enters only through the objective coefficients \(v_t(a)\). No spending constraint is introduced.
The primal has
\( N=\tau\binom{m+3}{3}=O(\tau m^3) \)
variables and \(m+\tau\) supply and type constraints, besides nonnegativity. The dual has \(m+\tau\) variables and \(N\) bundle constraints, besides price nonnegativity.
All coefficients are rational with encoding length \(O(L+\log(m+\tau+2))\). For example, a dense encoding of either program has total length bounded by
\( S= O\!\left( (N+1)(m+\tau+1)(L+\log(m+\tau+2)) \right). \)
We use the standard rational linear-programming theorem: a rational LP can be optimized exactly in time polynomial in its total binary encoding length, with a rational optimal solution of polynomial encoding length whenever its finite optimum is attained. The feasibility, finiteness, and attainment hypotheses were verified above for both programs.
The algorithm is therefore:
Its running time is
\( \operatorname{poly}\!\left( \tau\binom{m+3}{3},\,m+\tau,\,L \right) = \operatorname{poly}(m,\tau,L). \)
The returned masses and prices have polynomial total binary encoding length. No expansion of a type into individual agents, and no enumeration of types outside the listed support, is needed.
For the existence decision problem, every valid input is a yes-instance.
The discrete model allocates indivisible items by a partition among finitely many agents. An individual agent must receive one bundle. That integrality requirement is absent from the mass variables in this task. See the allocation and equilibrium definitions in [Deligkas–Melissourgos–Spirakis](https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p413.pdf).
Here, a positive mass of identical agents can be divided among tied utility-maximizing bundles. This is the convexification mechanism also discussed by [Azevedo–Weyl–White](https://eduardomazevedo.github.io/papers/Azevedo-et-al-Walrasian.pdf). The proof above establishes the computational conclusion directly for the stated support encoding and supply inequalities.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. Every valid instance admits an equilibrium, and the proposed algorithm computes rational equilibrium masses and prices exactly in time polynomial in \(m,\tau,L\). No major or minor mathematical gaps were found.
The slack-coordinate correspondence is a bijection: each admissible bundle uniquely determines the nonnegative integer coordinate \(a_0=3-\sum_j a_j\), and each resulting tuple determines an admissible bundle. Thus the stated count \(n=\binom{m+3}{3}\) is correct, including when \(m=1\). Empty bundles and repeated units are included.
Each valuation requires summing at most three input weights, counting multiplicity, and comparing the result with the cap. Rational arithmetic therefore produces coefficients of encoding length \(O(L)\). The claimed table-construction bound is valid using an enumeration that records the at most three occupied units of each bundle.
The empty-bundle allocation satisfies all type equalities and supply inequalities because supplies are nonnegative.
The bound \(0\le x_{t,a}\le\mu_t\) follows from nonnegativity and the corresponding type equality. Hence the feasible set is nonempty and compact. The stated welfare bound is correct, so the primal optimum is finite and attained.
The dual is correctly derived:
Since \(v_t(0)=0\), the empty-bundle constraint indeed implies \(u_t\ge0\). The proposed dual feasible point \(p=0,\ u_t=B_t\) satisfies every constraint.
The invoked finite-dimensional LP strong-duality theorem applies: the primal is feasible and has a finite optimum. Its conclusions of dual attainment and equality of optimal values are valid here.
The objective-gap identity is algebraically correct. The type equalities account for the terms involving \(u_t\), and the definition of \(y_j\) accounts for the price terms.
Every summand on its right-hand side is nonnegative. Because the sum is finite and optimal objective values agree, every summand must vanish. This reasoning works for any pair of optimal primal and dual solutions; no additional pairing condition is needed.
For each positive allocation \(x_{t,a}\), the resulting equality \(u_t=v_t(a)-p\cdot a\), together with all dual bundle constraints, proves utility maximization over the complete domain. It imposes no unintended spending constraint and preserves all ties.
Likewise, \(p_j(q_j-y_j)=0\) gives precisely the required zero price for unused supply. Primal feasibility supplies the remaining allocation requirements.
The edge cases are covered: zero supplies do not invalidate feasibility or duality, and zero valuations or caps do not invalidate the demand argument. Positive type masses ensure each type receives some bundle mass.
The stated variable and constraint counts are correct. The dense encoding bound is a valid upper bound, including coefficients, right-hand sides, objectives, and variable-sign specifications.
The rational LP theorem is stated sufficiently precisely for this application: exact optimization and polynomial output encoding length hold for rational LPs with attained finite optima. Both programs satisfy these hypotheses.
An unrestricted dual variable causes no computational difficulty: it is a standard LP variable convention, and the written empty-bundle constraints additionally force it to be nonnegative.
Consequently, constructing and solving both explicitly encoded LPs takes time polynomial in \(m,\tau,L\). Their polynomial encoding-length solutions provide an exact, polynomial-length equilibrium output.
The existence decision conclusion follows: every input satisfying the task’s validity conditions is a yes-instance.
The explanation of the discrete distinction is accurate: the cited discrete model assigns indivisible items to individual agents, whereas this task permits splitting each type’s mass across demanded bundles. See [Deligkas–Melissourgos–Spirakis](https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p413.pdf).
The continuum paper explicitly discusses convexification of aggregate demand through a continuum of consumers, supporting the prover’s contextual comparison. See [Azevedo–Weyl–White](https://eduardomazevedo.github.io/papers/Azevedo-et-al-Walrasian.pdf).
Neither reference is used as a theorem establishing this task’s existence or computational result. Those conclusions follow from the self-contained LP argument, so no hypotheses from the related continuum model need to be transferred.
No additional mathematical clarification or repair is required.
⟨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.