| paper | d4-conf-wine-2018-0016 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: The tight deterministic worst-case aggregate-demand query complexity is \(0\) for \(\epsilon\geq m\lambda/2\), and \(\Theta(m\lambda/\epsilon)\) for \(0<\epsilon<m\lambda/2\), uniformly over every prescribed support and mass vector. Non-oracle running time is \(\operatorname{poly}(L)+O(m\lceil m\lambda/\epsilon\rceil)\) with unit-cost exact-real arithmetic in the positive-query regime, and \(\operatorname{poly}(L)+O(m)\) in the zero-query regime. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 5.2
statement extracted from the paper’s text layer
Given \(n\) goods and a finite support \(T\) of valuation types with rational masses \(\mu_t\) summing to one, where each \(v_t\) is separable, concave, nondecreasing, and Lipschitz continuous, and an aggregate-demand oracle returning \(d_\mu(p)=\sum_{t\in T}\mu_t x_t(p)\), find a price \(p\geq 0\) whose per-capita revenue \(p\cdot d_\mu(p)\) is within additive error \(\epsilon\) of its maximum over prices. Determine the aggregate-demand query complexity as a function of \(n\), \(|T|\), and \(\epsilon\).
A society is a rational-mass distribution over complete valuation types. A common price \(p\) induces type demands \(x_t(p)\), aggregate per-capita demand \(d_\mu(p)\), and per-capita revenue \(p\cdot d_\mu(p)\); the decision is to return an approximately revenue-maximizing price using demand queries.
With only aggregate-demand queries, a finite mixture is exposed through one aggregate demand curve, so this mirror does not classify computation over τ itself; it establishes pricing-query difficulty even in the one-type case.
fatal: False
Covers Theorem 5.2’s revenue query lower bound and Theorem 3.1’s offline social-welfare guarantee. It leaves Theorem 4.1’s online random-permutation result and Theorem 5.1’s profit-maximization algorithm unmirrored; the online result’s arrival-order component is not itself a population continuization.
The cleanest regime is a very large market with recurring customer segments: millions of customers, but relatively few valuation types. A type is the customer’s complete valuation function and relevant market parameters; everyone in that type responds identically to a posted price. Let \(\mu_t\) be the fraction of customers of type \(t\), with rational masses summing to one. At price \(p\), type \(t\) demands \(x_t(p)\), and the market’s per-customer demand is \(d_\mu(p)=\sum_t\mu_t x_t(p)\). This preserves the paper’s revealed-preference setup and its aggregate demand oracle, while making the population itself a distribution over types. The paper’s divisible goods remain part of the model; the continuization is of the customers.
Lead — continuous revenue pricing. The paper’s Theorem 5.2, proved here in Appendix C, says that revenue maximization with \(m\) consumers and \(n\) goods requires \(\Omega(n/\epsilon)\) aggregate-demand queries to guarantee additive error \(\epsilon\), even when valuations are separable, concave, nondecreasing, and Lipschitz continuous. The cost is zero, as in the revenue-maximization case discussed in Section 5.
The mirror is: given \(n\) goods, a finite support of \(\tau\) valuation types with rational masses \(\mu_t\), separable, concave, nondecreasing, Lipschitz valuations accessible through demand oracles, and an aggregate oracle returning \(d_\mu(p)\), find a price \(p\geq 0\) whose per-customer revenue \(p\cdot d_\mu(p)\) is within \(\epsilon\) of the maximum over prices. A solution is such a price, with its induced demand. The theorem’s lower bound applies directly when \(\tau=1\): a continuum of customers of one type has the same per-customer demand and revenue as the single-consumer instance. I expect the query lower bound to persist. In the programme’s trichotomy, this is B-like persistence, though precisely it is an oracle-query lower bound, not an NP-hardness result. It shows that making the population large does not remove the difficulty caused by an \(n\)-dimensional unknown demand curve.
Second anchor — continuous social welfare pricing. The paper’s Theorem 3.1, proved here in Appendix A, says that under the paper’s offline assumptions—\(\alpha\)-strongly concave valuations, a convex, nondecreasing, \(\lambda\)-Lipschitz production cost, and feasible set \(C\) of diameter \(D\)—Algorithm 1 returns prices whose induced social welfare is within \(9\lambda mD/\sqrt{T}+16\lambda^2m/(\alpha T)\) of the offline optimum after \(T\) aggregate-demand queries.
For its mirror, let the society have finite support \(\{t\}\) with masses \(\mu_t\), and let each type have an \(\alpha\)-strongly concave valuation on \(C\). Use a convex, nondecreasing, \(\lambda\)-Lipschitz per-customer production cost \(\bar c\). The problem is to return a common price \(p\) maximizing per-customer welfare \(W_\mu(p)=\sum_t\mu_t v_t(x_t(p))-\bar c(d_\mu(p))\), to additive error \(\epsilon\); the solution includes \(p\) and its induced type demands. This is the more natural tractability story: the weighted dual objective is \(\bar c^*(p)-\sum_t\mu_t v_t^*(p)\), and revealed demands give its weighted subgradients. With a cost for total production scaled as \(N\bar c(y/N)\) for a population of size \(N\), dividing Theorem 3.1’s guarantee by \(N\) gives the per-customer bound \(9\lambda D/\sqrt{T}+16\lambda^2/(\alpha T)\). I expect this mirror to be tractable by the same smoothing and accelerated optimization approach, with query complexity independent of \(N\); if each type oracle call is charged separately, each aggregate round costs up to \(\tau\) calls.
These questions cover the paper’s offline revenue and social-welfare results. The paper’s online random-permutation result is outside this proposed mirror: extending time or the arrival process is not the population continuization at issue here. A useful next question is whether mixed-type revenue pricing has upper bounds matching the \(\Omega(n/\epsilon)\) lower bound as a function of \(n,\tau,\epsilon\). For social welfare, one could ask how the query result changes when demand oracles are replaced by finite encodings of valuations.
The weakest point is that the paper works in a revealed-preference query model with valuation functions accessed through oracles. The proposed mirror preserves that model, so its results are not automatically bit-complexity classifications for rationally encoded valuation functions. Also, the revenue lower-bound witness uses just one type: it establishes that the population continuum does not erase this obstruction, but says nothing about difficulty created specifically by a heterogeneous type distribution. The market scenario is still plausible for the paper’s online-economy motivation, and the two mirrors retain its central decisions—pricing for revenue or welfare from revealed demand.
The strongest case against both mirrors is that this paper’s oracle model has already hidden the population. With a common price, the algorithms use consumers only through aggregate demand. For a finite type distribution, define
\[
F_\mu(q)=\max\left\{\sum_t\mu_t v_t(x_t):\sum_t\mu_t x_t=q,\ x_t\in C\right\}.
\]
This is a representative valuation: its demand at price \(p\) is exactly \(d_\mu(p)=\sum_t\mu_t x_t(p)\). Per-capita welfare is therefore \(\max_q\{F_\mu(q)-\bar c(q)\}\), and revenue is \(p\cdot d_\mu(p)\). The type distribution changes the aggregate demand function, but the pricing problem sees only that function.
That weakens the Theorem 5.2 anchor. Its lower bound already holds for one type, where a continuum of customers contributes no population structure at all. A stronger heterogeneous version still reduces to pricing against the representative demand curve. If the oracle returns aggregate demand, a query costs exactly what it costs in the paper’s model; if separate type oracles are charged, forming aggregate demand takes \(\tau\) calls. The former leaves no support-level computation to classify, while the latter makes support size an oracle-accounting cost.
The Theorem 3.1 mirror has the same issue, more transparently. Replicate each rational mass \(\mu_t\) into \(N\mu_t\) consumers, where \(N\) is a common denominator, and use total production cost \(c_N(y)=N\bar c(y/N)\). The finite market’s objective is \(N\) times per-capita welfare. Dividing the theorem’s error bound by \(N\) removes population size, and its dual already aggregates consumer demands. The proposed weighted dual is mathematically natural, but in this oracle model it does not expose a new population computation.
This is a model objection, not a claim that either mirror is ill-posed or that its answer is uninteresting. Rational type masses and recurring customer segments are sensible, and an explicit finite encoding of valuations or a study charging separately for type-level queries could make support complexity a real subject. That is also where this negative case is weakest: the paper’s aggregate oracle makes the mirrors largely collapse to representative demand, but it does not rule out a worthwhile mirror under a richer computational interface.
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.