| paper | d4-conf-atal-2019-0275 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Answer: Polynomial-time solvable under the standard precision-parameter encoding. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Proposition 2
Given \(n\) goods, a finite support of \(\tau\) CES buyer types \(\theta=(b_\theta,\rho_\theta,(a_{\theta j})_{j=1}^n)\), and rational masses \(\mu_\theta^r\) summing to \(1\) and per-capita supplies \(w_j^r>0\) for rounds \(r=0,\ldots,T\), compute an \(\epsilon\)-approximation to the final price vector. Define aggregate demand by \(D_j^r(p)=\sum_\theta \mu_\theta^r b_\theta (a_{\theta j})^{1-c_\theta}p_j^{c_\theta-1}/\sum_k(a_{\theta k})^{1-c_\theta}p_k^{c_\theta}\), where \(c_\theta=\rho_\theta/(\rho_\theta-1)\), and update \(p_j^{r+1}=p_j^r[1+\lambda\min\{(D_j^r(p^r)-w_j^r)/w_j^r,1\}]\). For fixed \(\rho_\theta=1/2\), rational type data and an assumed price bound \(P\) and contraction parameter \(\delta>0\), return a certified bound on \(\Phi^T=\sum_jp_j^T|D_j^T(p^T)-w_j^T|\), in particular whether \(\Phi^T\le(1-\delta)^T\Phi^0+\sum_{r=1}^T(1-\delta)^{T-r}[\sum_\theta b_\theta|\mu_\theta^r-\mu_\theta^{r-1}|+P\|w^r-w^{r-1}\|_1]\) can be certified with running time polynomial in \(n,\tau,T\), the input bit length, and \(\log(1/\epsilon)\).
A changing society is a distribution \(\mu^r\) over finitely many complete CES buyer types, with each type's budget and utility fixed and its mass varying by round. Goods retain the paper's divisible-market interpretation, while supplies are measured per unit of population. The decision variables are prices generated by the same tatonnement update; the target is the final price vector and a certified bound on per-capita misspending.
The mirror extends the gross-substitutes CES tatonnement misspending guarantee in Proposition 2 to changing type masses and per-capita supplies, with mass variation also reflecting Proposition 3's budget perturbations. It does not reproduce Proposition 4's coefficient-specific utility-change bound or cover the general Lyapunov framework, PRD, gradient descent, or load balancing.
There is a plausible continuous-population mirror in the paper’s dynamic Fisher-market results. But there is no qualifying complexity anchor: none of the numbered results says that a problem is in P, NP-hard, FPT, or otherwise classifies its computational complexity. Proposition 2 is the closest supporting result, and it is proved in this paper: for gross-substitutes CES markets with additive supply changes \(\varepsilon^t\), prices bounded by \(P\), and tatonnement’s per-round potential decrease \(\delta\), it bounds final misspending by
\[
\Phi_{\mathrm{MS}}(\mathcal M^T,p^T)
\le
P\left(
\sum_{\tau=t+1}^{T}(1-\delta)^{T-\tau}\|\varepsilon^\tau\|_1
+\frac{(1-\delta)^{T-t}}{\delta}\kappa
\right)
+(1-\delta)^T\Phi_{\mathrm{MS}}(\mathcal M^0,p^0),
\]
where \(\kappa=\max_\tau\|\varepsilon^\tau\|_1\). Propositions 3 and 4 give corresponding bounds for budget and utility changes. These are dynamic-performance guarantees, not results of the kind the requested anchor rule requires.
The most credible mirror is Dynamic Type-Mass Tatonnement Tracking. A type is a complete CES buyer description \(\theta=(b_\theta,\rho_\theta,(a_{\theta j})_{j=1}^n)\), including budget and utility parameters. In a large platform market, many buyers may share one of a modest number \(\tau\) of such descriptions, even when the population \(N\) is very large. At round \(r\), \(\mu_\theta^r\) is the fraction of buyers of type \(\theta\), and \(w_j^r\) is the supply of good \(j\) per unit of population. Thus the input describes changing populations by rational masses over types, rather than by listing buyers. This is a sensible high-multiplicity regime, with \(\tau\ll N\).
For prices \(p\), define aggregate demand by summing each type’s CES demand weighted by its mass:
\[
D_j^r(p)=\sum_\theta \mu_\theta^r b_\theta
\frac{a_{\theta j}^{\,1-c_\theta}p_j^{\,c_\theta-1}}
{\sum_k a_{\theta k}^{\,1-c_\theta}p_k^{\,c_\theta}},
\qquad
c_\theta=\frac{\rho_\theta}{\rho_\theta-1}.
\]
Given an initial price vector and an explicitly listed sequence of masses and supplies, apply the paper’s tatonnement update to this aggregate demand:
\[
p_j^{r+1}=p_j^r\left[1+\lambda\min\left\{
\frac{D_j^r(p^r)-w_j^r}{w_j^r},1
\right\}\right].
\]
The computational question is: given this instance and an accuracy \(\epsilon\), compute an \(\epsilon\)-approximation to the final price vector and a certificate bounding its final per-capita misspending
\(\Phi^T=\sum_j p_j^T|D_j^T(p^T)-w_j^T|\).
For example, restricting to fixed \(\rho_\theta=\tfrac12\) makes demand evaluation rational; one can ask for running time polynomial in the number of goods, \(\tau\), the number of rounds, input bit length, and \(\log(1/\epsilon)\), under explicit price and parameter bounds.
This is a recognizable extension of Proposition 2: type-mass changes perturb aggregate demand just as budget changes do. In particular, at fixed prices, changing masses from \(\mu^{r-1}\) to \(\mu^r\) changes price-weighted demand by at most \(\sum_\theta b_\theta|\mu_\theta^r-\mu_\theta^{r-1}|\), since each type spends its budget across goods. Together with a supply-change term \(P\|w^r-w^{r-1}\|_1\), the same potential argument suggests the bound
\[
\Phi^T\le (1-\delta)^T\Phi^0+
\sum_{r=1}^T(1-\delta)^{T-r}
\left(
\sum_\theta b_\theta|\mu_\theta^r-\mu_\theta^{r-1}|
+P\|w^r-w^{r-1}\|_1
\right).
\]
The expected direction is tractability: this looks like a direct extension of the paper’s price update and perturbation analysis, not a hardness-transfer problem. It may generate further questions about which churn measures preserve the bound and whether the bound is tight.
The mirror covers the paper’s CES market-tracking results, especially Proposition 2, with mass changes added to the supply perturbations; it does not mirror the paper’s full PLCLDS framework or its gradient-descent and load-balancing applications. A market with many buyers sharing a few types is plausible to the authors, who already study markets through aggregate demand and perturbations. Divisible goods are already in their model, but here continuity is in the population itself.
The weak point is substantial: even this paper’s closest results are not computational-complexity results, and simulating the specified price updates may be a modest algorithmic question rather than a rich complexity classification. So this is a credible continuous-population extension of the paper’s market analysis, but it cannot be presented as a mirror of a qualifying named complexity result.
The strongest objection is that there is no computational-complexity result here to mirror. Propositions 2–4 bound how much misspending changes under supply, budget, and utility perturbations; the general theorem and the PRD result do the same for Lyapunov potentials. They analyze performance, not the running time or complexity of a computational problem. The proponent acknowledges this, and their proposed task—compute the final prices and misspending for a specified sequence—adds a new algorithmic question rather than continuizing one of the paper’s named results.
The type-mass market is a sensible high-multiplicity regime. Buyers sharing a complete CES description can be grouped, with masses and per-capita supplies as the paper’s co-modified model requires. But in this case aggregation adds little computational structure. At each round, aggregate demand is a weighted sum of the same CES demand formulas, so the proposed process can be evaluated by iterating the stated update and summing over the \(\tau\) types. Its natural cost is \(O(Tn\tau)\) arithmetic operations. A bit-complexity analysis would need a precise encoding and precision model; the paper supplies neither, because its contribution is a performance bound for the dynamics, not an algorithm for finding a solution.
The proposed mass-perturbation bound also follows directly from the paper’s existing bounds. For a type \(\theta\), its aggregate budget is \(\tilde b_\theta^r=\mu_\theta^r b_\theta\). Changing its mass therefore changes aggregate budget by \(b_\theta(\mu_\theta^r-\mu_\theta^{r-1})\), exactly the kind of perturbation covered by Proposition 3. Per-capita supply changes are covered by Proposition 2. Propositions 2–4 already handle the corresponding supply, budget, and utility changes; reweighting a finite set of types does not create a new computational bottleneck or a new analysis of the dynamics.
A stronger version could ask to compute equilibria at each round, or to optimize prices or population changes. Those would be distinct computational problems, not mirrors of the paper’s tracking guarantees. If instead the mirror uses an uncountable type space to add substance, it needs a succinct representation of the distribution; without one, it has no clear finite input for a complexity classification. With finite support, the calculation returns to weighted aggregation over types.
So I would grant the proponent’s main modeling point: many buyers sharing a modest number of CES types is plausible, and the population can meaningfully be represented by masses. The negative case is that this paper offers no named computational result to continuize, while its most natural mass-based extension is already absorbed by its perturbation analysis and reduces to evaluating an explicit dynamic process. That makes the universal claim difficult to prove, but leaves this particular paper a weak use of ChoCo’s complexity programme.
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.