| paper | d4-journals-geb-2017-0041 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable (\(\mathrm P\)); every instance satisfying the stated hypotheses has answer YES. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 5.4
statement extracted from the paper’s text layer
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)\)?
A nonatomic market with \(\tau\) complete valuation types of masses \(\mu_t\), integral bundles for each agent, and rational per-capita supplies \(q_j\). The allocation variables \(z_{t,B}\) split each type’s mass among demanded bundles; the price vector minimizes the mass-weighted Lyapunov function \(\Phi(p)=\sum_t\mu_t u_t(p)+\sum_j q_jp_j\) and is found by the weighted excess-demand auction.
The paper does not specify how valuation functions are represented, so no input-size or efficiency claim transfers; a demand-access model must be fixed to assess computational bounds.
fatal: False
The mirror addresses Theorem 5.4’s minimum-price ascending-auction guarantee and uses Theorem 4.1’s minimum-price characterization as a correctness criterion. It leaves the descending and maximum-price result, Theorem 5.8, and complexity bounds for finding excess-demand sets unresolved.
The strongest mirror is the paper’s minimum Walrasian price result. A plausible regime is a large auction for replenished slots, licenses, or other standardized item categories: there are many buyers, but only \(\tau\) distinct valuation types, with \(\tau\ll N\), because buyers share complete valuation functions. The society is the distribution \(\mu\) over those types. A type’s mass is the fraction of buyers with that valuation.
There is one necessary market adjustment. In a genuinely large population, stock must scale with population for the auction to remain a substantive market. Let \(q_j\) be the supply of item category \(j\) per buyer, so a market of \(N\) buyers has \(Nq_j\) copies of category \(j\). For the paper’s one-copy-per-item market at a particular finite population size, \(q_j=1/N\). This is the permitted supply co-modification: it keeps each buyer’s bundle integral while letting the type masses and aggregate allocation be fractional. Formally, let \(z_{t,B}\) be the mass of type \(t\) assigned the integral bundle \(B\subseteq\Omega\). It must satisfy
\[
\sum_B z_{t,B}=\mu_t,\qquad
\sum_{t,B:\,j\in B}z_{t,B}=q_j.
\]
At prices \(p\), every bundle receiving positive mass must be demanded by its type. Thus people still receive whole bundles; only the mass of people assigned each bundle can be fractional.
Lead anchor: Theorem 5.4, proved in this paper. It says that when all valuations are monotone gross substitutes, any ascending auction that raises prices only for the items in an excess-demand set, and stops when there is no excess-demand set, ends at the minimum Walrasian price vector. The theorem establishes correctness, not a polynomial running-time bound.
The continuous question is: given the item categories, \(\tau\) monotone gross-substitute valuations \(v_t\), rational masses \(\mu_t\), rational per-buyer supplies \(q_j\), and integer prices, does the corresponding mass-weighted excess-demand auction always return the minimum Walrasian prices? For a set \(S\), define
\[
\ell^p_\mu(S)=\sum_t\mu_t\min_{B\in D_t(p)}|B\cap S|,
\qquad
h^p_\mu(S)=\sum_t\mu_t\max_{B\in D_t(p)}|B\cap S|,
\qquad
q(S)=\sum_{j\in S}q_j.
\]
Call \(S\) strictly over-demanded when \(\ell^p_\mu(S)>q(S)\), and weakly under-demanded when \(h^p_\mu(S)\le q(S)\). It is an excess-demand set if it is strictly over-demanded at \(p\) and no nonempty \(T\subseteq S\) is weakly under-demanded at \(p+\mathbf 1_S\). Start at \(p=0\); choose any such \(S\), raise its prices by one, and stop when no such \(S\) remains. The requested output is the minimum Walrasian price vector; a supporting mass allocation \(z\) can be returned as a certificate. I expect the continuous version to have the same correctness result. The paper’s Lyapunov identities and submodularity use aggregate requirement and supply, so replacing bidder counts by weighted masses and item counts by \(q(S)\) is a plausible extension.
I expect this lead problem to be Class A in a suitable demand-oracle model: the mass weights change the aggregate quantities, while the gross-substitutes structure remains. But Theorem 5.4 itself does not show polynomial time in \(m,\tau\), and input bit length. Finding an excess-demand set efficiently, and avoiding a running-time bound that depends on the numerical price range, are further questions for the prover.
Second anchor: Theorem 4.1, also proved in this paper. It gives three characterizations: \(p\) is Walrasian exactly when there is no strictly over-demanded set and no strictly under-demanded set; it is minimum Walrasian exactly when there is no strictly over-demanded set and no nonempty weakly under-demanded set; and it is maximum Walrasian exactly when there is no nonempty weakly over-demanded set and no strictly under-demanded set.
Its continuous problem is a price-certification problem. Given the same market and a candidate price vector \(p\), determine whether \(p\) is Walrasian, minimum Walrasian, or maximum Walrasian. Use the weighted \(\ell^p_\mu\) and \(h^p_\mu\) above, with strict over-demand defined by \(\ell^p_\mu(S)>q(S)\), weak over-demand by \(\ell^p_\mu(S)\ge q(S)\), strict under-demand by \(h^p_\mu(S)<q(S)\), and weak under-demand by \(h^p_\mu(S)\le q(S)\). A solution is the three yes/no answers, with a violating set when a characterization fails. I expect this characterization to extend and to be Class A with appropriate access to type demands and subset optimization; checking every subset directly would not give an efficient algorithm. The natural follow-up is to establish the weighted characterization and give its complexity in \(m,\tau\), and the rational input lengths.
These are computational anchors, though neither is a named hardness result. The paper contains no comparable NP-hardness anchor to prefer. The case is that its central objects already depend on aggregate demand against supply, and the proposed mirrors retain those objects instead of relaxing the auction into a fractional-bundle problem. The authors should recognize the weighted demand tests and price dynamics as their questions.
The weakest point is the supply regime. If the paper’s \(m\) one-off items stay fixed while the population grows without bound, almost all population mass receives nothing, which makes the usual continuum-market interpretation thin. Keeping per-capita supply positive repairs that problem, but means item-category stock scales with population. That is a real co-modification of the one-copy auction. It is defensible for repeated or replenished markets, and the mirror should be limited to that regime rather than claimed for every one-off auction.
The strongest objection is that neither anchor is a complexity result. Theorem 4.1 characterizes prices, and Theorem 5.4 proves that a certain auction rule reaches the minimum Walrasian prices. The latter is algorithmic, but neither theorem specifies a valuation representation, the cost of finding an excess-demand set, or a running-time bound. Since valuations are arbitrary functions on \(2^\Omega\), turning either result into a complexity question requires choosing an input model the paper does not provide.
That limits what the proposed mirrors inherit. For Theorem 5.4, replacing bidder counts with type masses and item counts with supplies gives a plausible weighted Lyapunov argument, but appears to lift the correctness proof directly. For Theorem 4.1, the weighted characterization still ranges over item subsets; its computational content depends on how demands and valuations are accessed. Explicit valuation tables and demand-oracle inputs lead to different questions. This is a reason to doubt that these theorems, as stated, anchor a new complexity landscape. It does not show that the resulting problems are uninteresting.
The stronger market formulation survives the main modelling objections. A large population with \(\tau\) shared valuation types and supplies scaled per capita is plausible; buyers can still receive integral bundles while type mass is split among bundles. Identity is irrelevant to the price characterizations, and the continuum need not collapse. That is the other analyst’s best mirror, and I cannot honestly rule it out. Scaling supply does move from the paper’s fixed one-copy auction to a replica market, but the programme explicitly permits that co-modification.
So the negative case is weak at its hardest point. The paper gives no running-time result to continuize, and the weighted versions may be close proof lifts whose computational significance depends on a newly specified input model. But a concrete question remains: whether excess-demand sets and the resulting prices can be computed efficiently in \(m,\tau\), and the input bit length. I have no sound basis for claiming that question is not worth asking.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.