Answer: Polynomial-time solvable (\(\mathrm P\)); every instance satisfying the stated hypotheses has answer YES.
Theorem 5.4 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateIf all valuations are monotone gross substitute then any ascending auction that only updates prices of all items that belong to an excess demand set and terminates when there is none, will result in the minimum Walrasian price vector.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite item set \(\Omega\), integer-valued monotone gross-substitute valuation types \(t=1,\ldots,\tau\), rational masses \(\mu_t>0\) summing to \(1\), and rational per-capita supplies \(q_j\in(0,1)\), define \(\ell^p_\mu(S)=\sum_t\mu_t\min_{B\in D_t(p)}|B\cap S|\) and \(h^p_\mu(S)=\sum_t\mu_t\max_{B\in D_t(p)}|B\cap S|\). Call \(S\) excess-demanded at \(p\) if \(\ell^p_\mu(S)>q(S)\) and no nonempty \(T\subseteq S\) satisfies \(h^{p+\mathbf 1_S}_\mu(T)\le q(T)\). Starting at \(p=0\), repeatedly raise prices by one on an excess-demanded set and stop when none exists: does every such process terminate at the componentwise minimum Walrasian price vector, supporting a feasible mass allocation \(z_{t,B}\ge0\) with \(\sum_B z_{t,B}=\mu_t\), \(\sum_{t,B:j\in B}z_{t,B}=q_j\), and positive mass only on bundles \(B\in D_t(p)\)?
Let \(\Omega\) be an item set with \(m\geq1\). A society is given by its support: a list of \(\tau\) valuation types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types. Each normalized monotone gross-substitute valuation \(v_t:2^\Omega\to\mathbb Z_{\geq0}\) is supplied by its complete binary-encoded value table, with \(v_t(\emptyset)=0\). Supplies satisfy \(q_j\in\mathbb Q\cap(0,1)\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Prices belong to \(\mathbb Z_{\geq0}^m\). Write \(p(B)=\sum_{j\in B}p_j\), \(q(S)=\sum_{j\in S}q_j\), and \(D_t(p)=\operatorname*{arg\,max}_{B\subseteq\Omega}(v_t(B)-p(B))\), retaining all utility ties.
Define \(\ell^p_\mu(S)=\sum_t\mu_t\min_{B\in D_t(p)}|B\cap S|\) and \(h^p_\mu(S)=\sum_t\mu_t\max_{B\in D_t(p)}|B\cap S|\). A nonempty \(S\subseteq\Omega\) is excess-demanded at \(p\) when \(\ell^p_\mu(S)>q(S)\) and \(h^{p+\mathbf1_S}_\mu(T)>q(T)\) for every nonempty \(T\subseteq S\); \(\mathbf1_S\) is its coordinate indicator vector.
A maximal process starts at \(p=0\), chooses any excess-demanded set at each step, and replaces \(p\) by \(p+\mathbf1_S\); it stops exactly when no such set exists, or continues indefinitely.
A Walrasian price vector is a \(p\in\mathbb Z_{\geq0}^m\) admitting real masses \(z_{t,B}\geq0\) with \(\sum_{B\subseteq\Omega}z_{t,B}=\mu_t\), \(\sum_t\sum_{B\ni j}z_{t,B}=q_j\), and \(z_{t,B}>0\) only if \(B\in D_t(p)\). A componentwise minimum is a Walrasian \(p^*\) satisfying \(p^*_j\leq r_j\) for every item and every Walrasian vector \(r\).
Is deciding, for a given society and supply vector, whether every maximal process terminates at a componentwise minimum Walrasian price vector in \(\mathrm P\), or is it NP-hard?
For finite bidders and one indivisible copy of each item, every such excess-demand ascending auction yields the minimum Walrasian price vector for normalized monotone gross-substitute integer valuations; this is a convergence guarantee without a polynomial-time bound ([Ben-Zwi](https://arxiv.org/pdf/1605.03826)).
A targeted literature search did not identify a result settling this exact mass-allocation process.
The decision problem is in \(\mathrm P\). In fact, every instance satisfying the stated hypotheses has answer YES.
Every maximal process terminates, and its terminal price vector is the componentwise minimum integer Walrasian price vector. This does not imply a polynomial bound on the number of auction steps.
The proof below treats the supplied list as the support of the society; no enumeration of other valuation types is needed.
For a single valuation, extend the auxiliary indirect utility to all integer price vectors:
\( u(p)=\max_{B\subseteq\Omega}\{v(B)-p(B)\}, \qquad p\in\mathbb Z^m. \)
This auxiliary extension permits negative coordinates in proofs; the process itself still uses only nonnegative prices.
Write \(\ell_p(S)=\min_{B\in D(p)}|B\cap S|\) and \(h_p(S)=\max_{B\in D(p)}|B\cap S|\). We will establish
\[ u(p+\mathbf1_S)=u(p)-\ell_p(S), \qquad u(p-\mathbf1_S)=u(p)+h_p(S). \tag{1} \]
We use the standard equivalence between gross substitutes and \(\mathrm M^\natural\)-concavity: for any bundles \(A,C\) and \(i\in A\setminus C\), there is \(j\in(C\setminus A)\cup\{0\}\) such that
\( v(A)+v(C) \leq v(A-i+j)+v(C+i-j). \)
Here \(0\) is a dummy symbol whose insertion or deletion leaves a bundle unchanged. This equivalence applies to the finite-valued set functions in the question. Subtracting the modular function \(p(B)\) preserves the exchange inequality. See [Fujishige and Yang, *A Note on Kelso and Crawford’s Gross Substitutes Condition*](https://doi.org/10.1287/moor.28.3.463.16393).
Single improvement. Let \(f(B)=v(B)-p(B)\), and suppose \(B\) does not maximize \(f\). Choose a maximizing bundle \(C\) minimizing \(|B\mathbin{\triangle}C|\).
If \(i\in B\setminus C\), exchange gives
\( f(B)+f(C)\leq f(B-i+j)+f(C+i-j). \)
Since \(f(C+i-j)\leq f(C)\), the first term on the right is at least \(f(B)\). Equality would make \(C+i-j\) a maximizing bundle closer to \(B\), a contradiction. Thus deleting or exchanging one item strictly improves \(B\).
If \(B\setminus C=\emptyset\), then \(B\subsetneq C\). Applying exchange to \(C,B\) and any \(i\in C\setminus B\) gives
\( f(C)+f(B)\leq f(C-i)+f(B+i). \)
The same closest-maximizer argument shows that adding \(i\) strictly improves \(B\).
Now assume \(p\) is integral. All utility values are integers. If \(k=u(p)-f(B)\), repeated single improvements reach some \(D\in D(p)\) in at most \(k\) moves. Each move inserts at most one item and deletes at most one item, so
\( |D\setminus B|\leq k, \qquad |B\setminus D|\leq k. \)
Consequently,
\( \ell_p(S)\leq |B\cap S|+k, \qquad |B\cap S|\leq h_p(S)+k. \)
These inequalities imply, for every \(B\),
\( f(B)-|B\cap S|\leq u(p)-\ell_p(S), \qquad f(B)+|B\cap S|\leq u(p)+h_p(S). \)
Taking maxima proves the upper bounds in (1). Demanded bundles attaining \(\ell_p(S)\) and \(h_p(S)\) give the reverse bounds. Thus (1) holds.
Applying both identities between \(p\) and \(p+\mathbf1_S\) also gives
\[ h_{p+\mathbf1_S}(S)=\ell_p(S). \tag{2} \]
We first record a direct consequence of gross substitutes. If \(a\leq b\) and their coordinates agree on \(T\), then
\[ h_a(T)\leq h_b(T). \tag{3} \]
Indeed, take a demanded bundle at \(a\) maximizing its intersection with \(T\). Gross substitutes supplies a demanded bundle at \(b\) containing all its items whose prices are unchanged, including its intersection with \(T\).
The utility function satisfies lattice submodularity:
\[ u(a\wedge b)+u(a\vee b)\leq u(a)+u(b) \qquad(a,b\in\mathbb Z^m). \tag{4} \]
To verify this, put \(c=a\wedge b\), \(d=a\vee b\). Follow any sequence of coordinate unit increases from \(c\) to \(a\), and follow the identical sequence from \(b\) to \(d\). The additional prices \(b-c\) are supported outside the coordinates increased along these paths.
For a matching step increasing coordinate \(j\), (1) gives
\( u(r+\mathbf1_{\{j\}})-u(r) =-h_{r+\mathbf1_{\{j\}}}(\{j\}). \)
The endpoint of the second step has higher prices outside \(j\) and the same price on \(j\). By (3), its utility loss is at least that of the first step. Summing yields \(u(a)-u(c)\geq u(d)-u(b)\), proving (4).
Define the society’s auxiliary potential
\( F(p)=\sum_t\mu_t u_t(p)+\sum_jq_jp_j, \qquad p\in\mathbb Z^m. \)
Positive weighted sums preserve (4), and the supply term is modular. Hence \(F\) is lattice-submodular. Equation (1) gives
\[ F(p+\mathbf1_S)-F(p)=q(S)-\ell_\mu^p(S), \tag{5} \]
\[ F(p-\mathbf1_T)-F(p)=h_\mu^p(T)-q(T). \tag{6} \]
These formulas retain all utility ties.
We need the following characterization:
\[ p\text{ admits the required mass allocation} \iff \ell_\mu^p(S)\leq q(S)\leq h_\mu^p(S) \quad\text{for every }S\subseteq\Omega. \tag{7} \]
Here is a justification, including the aggregation step.
For each type, let
\( P_t=\operatorname{conv}\{\mathbf1_B:B\in D_t(p)\}. \)
A demanded family has the simultaneous exchange property: applying the exchange inequality to two demanded bundles produces two bundles whose utilities sum to at least twice the maximum utility. Both therefore remain demanded. Thus its incidence vectors form an \(\mathrm M^\natural\)-convex set.
We use the standard polyhedral characterization: if \(X\) is a finite nonempty \(\mathrm M^\natural\)-convex set, then the convex hull of its lift \(\{(-x(\Omega),x):x\in X\}\) is a submodular base polytope on \(E=\{0\}\cup\Omega\). The lifting correspondence and base-polyhedron characterization are described in [Murota, *Discrete Convex Analysis: A Tool for Economics and Game Theory*, Section 4.1](https://www.mechanism-design.org/arch/v001-1/p_05.pdf).
All hypotheses hold here: demand is nonempty because the bundle set is finite, and its incidence vectors have the exchange property just verified. Consequently,
\( \widetilde P_t = \operatorname{conv}\{(-|B|,\mathbf1_B):B\in D_t(p)\} = \mathcal B(r_t), \)
where \(r_t\) is submodular, \(r_t(\emptyset)=r_t(E)=0\), and
\( \mathcal B(r_t)= \{y\in\mathbb R^E:y(E)=0,\ y(A)\leq r_t(A)\text{ for every }A\subseteq E\}. \)
Taking the canonical bound \(r_t(A)=\max_{y\in\widetilde P_t}y(A)\), we obtain
\( r_t(A)=h_{t,p}(A)\quad(0\notin A), \)
\[ r_t(A)=-\ell_{t,p}(E\setminus A)\quad(0\in A). \tag{8} \]
For completeness, the weighted Minkowski-sum identity is
\[ \sum_t\mu_t\mathcal B(r_t) = \mathcal B\!\left(\sum_t\mu_t r_t\right). \tag{9} \]
To see this, order the elements \(e_1,\ldots,e_n\) of \(E\) by decreasing coordinates of any weight vector \(a\), and set \(A_i=\{e_1,\ldots,e_i\}\). For a normalized submodular function \(r\) with \(r(E)=0\), the greedy vector
\( y_{e_i}=r(A_i)-r(A_{i-1}) \)
belongs to \(\mathcal B(r)\): diminishing returns, summed over the elements of any subset, gives \(y(A)\leq r(A)\). Moreover, telescoping shows that the support function is
\( \max_{y\in\mathcal B(r)}a\cdot y = \sum_{i=1}^{n-1}(a_{e_i}-a_{e_{i+1}})r(A_i). \)
This expression is linear in \(r\). Hence both sides of (9) have identical support functions and, being compact convex sets, are equal.
Set \(\widetilde q=(-q(\Omega),q)\). By (8)–(9), membership of \(\widetilde q\) in the weighted sum is exactly the inequalities in (7). Projecting away coordinate \(0\) gives \(q=\sum_t\mu_t x_t\) with \(x_t\in P_t\). Writing each \(x_t\) as a convex combination of demanded incidence vectors, and multiplying its coefficients by \(\mu_t\), gives precisely the required masses \(z_{t,B}\). This proves (7).
For each item define its maximum marginal value
\( \Delta_j= \max_{\substack{t\\B\subseteq\Omega\setminus\{j\}}} \bigl(v_t(B\cup\{j\})-v_t(B)\bigr). \)
Suppose an update raises item \(j\), producing \(x=p+\mathbf1_S\). The excess-demand condition applied to \(\{j\}\) gives
\( h_\mu^x(\{j\})>q_j>0. \)
Some demanded bundle of some type therefore contains \(j\). Comparing that bundle with the bundle obtained by removing \(j\) shows \(x_j\leq\Delta_j\).
Thus every reachable price satisfies \(0\leq p_j\leq\Delta_j\). Each step increases the sum of coordinates by at least one, so every process has at most
\( \sum_j\Delta_j \)
steps. Infinite maximal processes are impossible.
We claim that every reachable price satisfies
\[ h_\mu^p(T)>q(T) \quad\text{for every nonempty }T\subseteq\Omega. \tag{10} \]
At \(p=0\), monotonicity makes \(\Omega\) demanded by every type. Therefore \(h_\mu^0(T)=|T|>q(T)\), using \(\sum_t\mu_t=1\) and \(q_j<1\).
Suppose (10) holds at \(p\), and an excess-demanded \(S\) is raised, producing \(x=p+\mathbf1_S\). Fix nonempty \(T\), and put
\( I=S\cap T,\qquad U=T\setminus S. \)
If \(U=\emptyset\), (10) at \(x\) follows directly from the update condition.
Otherwise, apply submodularity to \(p\) and \(x-\mathbf1_T\). Their meet is \(p-\mathbf1_U\), and their join is \(x-\mathbf1_I\). Thus
\( F(x-\mathbf1_T)-F(x-\mathbf1_I) \geq F(p-\mathbf1_U)-F(p)>0, \)
where the strict inequality follows from the old invariant and (6).
If \(I=\emptyset\), then \(x-\mathbf1_I=x\). If \(I\neq\emptyset\), the update condition and (6) give \(F(x-\mathbf1_I)>F(x)\). In either case,
\( F(x-\mathbf1_T)>F(x). \)
By (6), this proves (10) at \(x\).
Next, whenever some set is overdemanded, an excess-demanded set exists. Choose an inclusion-minimal \(S\) satisfying \(\ell_\mu^p(S)>q(S)\). Equation (5) gives \(F(p+\mathbf1_S)<F(p)\).
If \(S\) were not excess-demanded, there would be nonempty \(T\subseteq S\) with \(h_\mu^{p+\mathbf1_S}(T)\leq q(T)\). By (6),
\( F(p+\mathbf1_{S\setminus T}) \leq F(p+\mathbf1_S)<F(p). \)
By (5), \(S\setminus T\) would be a smaller overdemanded set. It cannot be empty because the displayed strict inequality would then contradict itself. This contradicts minimality.
Consequently, at a terminal price \(\widehat p\),
\( \ell_\mu^{\widehat p}(S)\leq q(S) \quad\text{for every }S\subseteq\Omega. \)
Together with (10), characterization (7) proves that \(\widehat p\) is Walrasian.
Fix any integer Walrasian vector \(r\). We prove inductively that every price along every process satisfies \(p\leq r\).
Initially this holds because \(p=0\) and \(r\geq0\). Suppose it holds before raising an excess-demanded \(S\). Let
\( T=\{j\in S:p_j=r_j\}. \)
If \(T\neq\emptyset\), define \(x=p+\mathbf1_S\) and \(y=r+\mathbf1_T\). Integrality ensures \(x\leq y\), and their coordinates agree on \(T\). Applying (3) type by type, followed by (2), gives
\( h_\mu^x(T) \leq h_\mu^{r+\mathbf1_T}(T) =\ell_\mu^r(T) \leq q(T). \)
The last inequality follows from the allocation at \(r\): every demanded bundle contributes at least its type’s minimum intersection with \(T\).
This contradicts the excess-demand condition at \(x\). Therefore \(T=\emptyset\). For every raised coordinate, integrality gives \(p_j+1\leq r_j\), establishing the inductive step.
Every terminal vector is Walrasian by Section 5 and is bounded componentwise by every integer Walrasian vector by this argument. It is therefore a componentwise minimum. Any two terminal vectors must bound each other, so all maximal processes terminate at the same vector.
On the promised input class, the decision algorithm reads the input and returns YES. Its running time is \(\mathrm O(L)\), with no additional dependence on \(m\) or \(\tau\).
The auction itself can require exponentially many steps. For \(m=\tau=1\), let \(v(\{1\})=M\), \(\mu_1=1\), and \(q_1=\tfrac12\). The sole item is excess-demanded at every price below \(M\), and the process stops at \(M\). Thus it takes exactly \(M\) steps, while the input length is \(\Theta(\log M)\).
⟨structured verdict parsed — rendered above⟩
The prover’s argument resolves the assigned problem. Every valid instance has answer YES, so the decision problem is in \(\mathrm P\). I found no major or minor mathematical issues.
The stated exchange inequality is the appropriate \(\mathrm M^\natural\)-concavity condition for finite-valued set functions. The gross-substitutes equivalence applies to the valuations supplied in the task. The equivalence also supports using arbitrary integer prices, including negative coordinates, in the auxiliary arguments. These facts agree with Theorem 3.7 and Section 4.1 of the cited [Murota survey](https://www.mechanism-design.org/arch/v001-1/p_05.pdf).
Subtracting the modular price function preserves the exchange inequality because the two bundles’ total incidence vector is preserved by an exchange.
The closest-maximizer argument is valid in both cases:
Thus every nonmaximizing bundle admits a strict single improvement. At integer prices, each improvement increases utility by at least one. Starting with utility deficit \(k\), at most \(k\) improvements are possible before reaching demand. The bounds on inserted and deleted items follow from the stated move sizes.
The two intersection inequalities follow from the distance bounds to the resulting demanded bundle. Substituting \(f(B)=u(p)-k\) gives exactly the two upper bounds needed for equation (1).
A demanded bundle attaining the minimum intersection supplies equality for the price increase; a demanded bundle attaining the maximum intersection supplies equality for the price decrease. Both extrema exist because demand is finite and nonempty.
Applying the increase identity at \(p\) and the decrease identity at \(p+\mathbf1_S\) gives equation (2), with the prices and signs correctly matched. The argument retains all utility ties.
Equation (3) follows from gross substitutes: the demanded bundle selected at the lower prices has a demanded counterpart at the higher prices containing its unchanged-price items.
In the paired coordinate paths used for equation (4), every coordinate increased from \(c\) to \(a\) has \(a_j>b_j\). Therefore the offset \(b-c\) vanishes on every such coordinate. Matching endpoints have the same price on the coordinate being increased and ordered prices elsewhere, as required by equation (3).
The utility change is the negative of the endpoint maximum demand for that coordinate. Consequently, the second path has utility changes no larger than the first. The summed inequality has the correct direction for lattice submodularity.
Positive weighted sums preserve that inequality, and the supply term is modular. Equations (5) and (6) then follow directly from equation (1); no integrality of masses or supplies is needed.
Applying the exchange inequality to two demanded bundles forces both exchanged bundles to remain demanded: neither can exceed maximum utility, while their sum must reach twice that maximum. This establishes precisely the simultaneous exchange property needed for the incidence-vector set to be \(\mathrm M^\natural\)-convex.
The invoked polyhedral characterization is valid. Its hypotheses—finiteness, nonemptiness, integer vectors, and the exchange property—are satisfied. Section 4.1 of the [Murota survey](https://www.mechanism-design.org/arch/v001-1/p_05.pdf) supplies the lifting correspondence and identifies constant-sum \(\mathrm M\)-convex sets with integral base polyhedra.
The canonical bounds in equation (8) are correctly computed. A subset excluding the dummy coordinate measures bundle intersection directly; a subset including it measures the negative intersection with its complement.
The weighted Minkowski-sum identity is also adequately justified:
Membership of \(\widetilde q\) therefore gives exactly both families of subset inequalities. The subsequent convex-combination construction yields nonnegative masses with the required type totals, item totals, and demand restrictions. Conversely, any required allocation satisfies those inequalities. Equation (7) is established in both directions.
Whenever item \(j\) is raised, the update condition for the singleton \(\{j\}\), together with \(q_j>0\), implies that some demanded bundle at the updated prices contains \(j\).
Comparing this bundle with its deletion of \(j\) correctly yields \(x_j\leq\Delta_j\). The maxima defining \(\Delta_j\) exist, and monotonicity makes them nonnegative.
Initial prices satisfy the bound, and every subsequent raised coordinate satisfies it. Every step increases the integer coordinate sum by at least one, proving the stated bound of \(\sum_j\Delta_j\) steps. This also covers items with zero maximum marginal value: they cannot be raised.
At zero prices, monotonicity makes \(\Omega\) demanded for every type. Hence \(h_\mu^0(T)=|T|\), and \(q_j<1\) gives the required strict inequality for every nonempty \(T\).
For the induction, the stated meet and join of \(p\) and \(x-\mathbf1_T\) are correct. Submodularity gives the displayed difference inequality in the correct direction. When \(U\neq\emptyset\), the old invariant makes its right-hand side strictly positive. The update condition supplies the additional strict inequality when \(I\neq\emptyset\). The cases \(U=\emptyset\) and \(I=\emptyset\) are explicitly covered.
The stopping-rule argument is likewise valid. If an inclusion-minimal overdemanded set fails the update condition, equation (6) produces a strictly lower potential at the smaller set \(S\setminus T\). Equation (5) then makes that smaller set overdemanded. If it is empty, the strict potential decrease is impossible. Thus an excess-demanded set exists whenever any overdemanded set exists.
A terminal price consequently satisfies every lower subset inequality. The invariant supplies every upper subset inequality, so equation (7) proves exact Walrasian feasibility.
The induction correctly ranges over every nonnegative integer Walrasian vector \(r\), which is exactly the comparison class in the task.
If \(T\neq\emptyset\), integrality and \(p\leq r\) ensure \(x\leq y\), with equality on \(T\). Equations (3) and (2) therefore apply as written. Feasibility at \(r\) supplies \(\ell_\mu^r(T)\leq q(T)\), contradicting the strict update condition.
Thus no raised coordinate can equal its corresponding coordinate of \(r\) before the update. Integrality then ensures that the update preserves \(p\leq r\).
This argument does not assume Walrasian existence circularly: terminal feasibility has already established existence. Every terminal vector is therefore Walrasian and bounded by every Walrasian vector. Uniqueness of the terminal vector follows.
The task supplies a promised input class. Since every instance in that class has answer YES, reading the input and returning YES takes \(\mathrm O(L)\), uniformly in \(m\) and \(\tau\). Recognition of the promise is not part of the assigned decision problem.
In the one-item example, at every integer price below \(M\), lower demand is one; after the next increase, maximum demand remains one, including the tie at price \(M\). At \(M\), lower demand becomes zero, so the process stops. The claimed \(M\) steps and logarithmic input length are correct.
No repair or additional clarification 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.