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.
Theorem 5.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe revenue maximization problem needs Ω(n/ǫ) queries to get an additive error ǫ, even if the valuations are separable, concave, non-decreasing, and Lipschitz continuous.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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\).
There are \(m\geq1\) divisible goods. A society is given by its support: a list \(T\) of \(\tau\geq1\) type identifiers with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts supported types, not possible types.
Each type has an unknown valuation \(v_t(x)=\sum_{j=1}^{m}v_{tj}(x_j)\) on \([0,1]^m\), where every \(v_{tj}:[0,1]\to\mathbb R_+\) is concave, nondecreasing, and \(\lambda\)-Lipschitz for a known rational \(\lambda>0\). Production cost is zero.
At prices \(p\in\mathbb R_+^m\), demand is defined coordinatewise by \(x_{tj}(p_j)=\max\operatorname*{arg\,max}_{z\in[0,1]}\{v_{tj}(z)-p_jz\}\). Thus indifference is resolved toward greater consumption.
The only access to valuations is an exact aggregate-demand oracle returning \(d_\mu(p)=\sum_{t\in T}\mu_t x_t(p)\); posting one entire price vector counts as one query. Revenue is \(R_\mu(p)=p\cdot d_\mu(p)\).
For rational \(\epsilon>0\), the required output is a price \(p\geq0\) with \(R_\mu(p)\geq\sup_{q\geq0}R_\mu(q)-\epsilon\). Algorithms are deterministic, with exact real arithmetic and exact oracle replies; \(L\) is the total bit length of the explicit rational input. State query bounds and non-oracle arithmetic running times in \(m,\tau,L,\lambda,\epsilon\).
What are tight worst-case upper and lower bounds on the aggregate-demand query complexity of this additive-\(\epsilon\) revenue problem, as functions of \(m,\tau,L,\lambda,\epsilon\)?
For a finite list of \(N\) consumers with unnormalized total revenue, an additive-\(\epsilon\) algorithm uses \(O(Nm\lambda/\epsilon)\) queries, while a lower bound of \(\Omega(m/\epsilon)\) is stated even for one consumer and fixed Lipschitz bound greater than one. [Ji, Mehta, and Telgarsky](https://arxiv.org/pdf/1711.02211v2)
No result explicitly addressing this mass-weighted oracle formulation was located in the literature search.
Let \(Q^*\) be the minimum worst-case number of aggregate-demand queries among deterministic algorithms, with the explicit input—including the support and its masses—fixed.
Then, uniformly over every admissible support and mass vector,
\( Q^*=0 \quad\text{if }\epsilon\geq m\lambda/2, \)
and
\( Q^*=\Theta(m\lambda/\epsilon) \quad\text{if }0<\epsilon<m\lambda/2. \)
The constants are independent of \(\tau\), the masses, and \(L\). More explicitly, in the latter regime,
\( \max\{1,\lfloor m\lambda/(24\epsilon)\rfloor-1\} \leq Q^* \leq \lceil m\lambda/\epsilon\rceil. \)
The upper-bound algorithm uses \(\operatorname{poly}(L)+O(m\lceil m\lambda/\epsilon\rceil)\) non-oracle time, counting exact-real arithmetic and comparisons at unit cost. In the zero-query regime, its time is \(\operatorname{poly}(L)+O(m)\).
The proof below is self-contained. The grid upper bound follows the same principle as the zero-cost remark in Section 5 of [Ji, Mehta, and Telgarsky](https://arxiv.org/pdf/1711.02211v2); normalization removes the consumer-count factor.
Write \(D_j(s)=\sum_{t\in T}\mu_t x_{tj}(s)\) and \(r_j(s)=sD_j(s)\). Separability gives
\( R_\mu(p)=\sum_{j=1}^m r_j(p_j). \)
Each coordinatewise maximizer exists because its objective is continuous on the compact interval \([0,1]\). Its maximizer set is compact, so the specified largest maximizer exists.
For any one component valuation \(v\), let \(x(s)\) denote its selected demand. If \(s<t\), optimality gives
\( v(x(s))-sx(s)\geq v(x(t))-sx(t) \)
and
\( v(x(t))-tx(t)\geq v(x(s))-tx(s). \)
Adding yields \((t-s)(x(s)-x(t))\geq0\). Thus demand is nonincreasing. Consequently, every \(D_j\) is nonincreasing and satisfies \(0\leq D_j(s)\leq1\), since the masses sum to \(1\).
If \(s>\lambda\), then for \(z_2>z_1\),
\( [v(z_2)-sz_2]-[v(z_1)-sz_1] \leq(\lambda-s)(z_2-z_1)<0. \)
Hence demand is zero above \(\lambda\). Revenue optimization can therefore be restricted to \([0,\lambda]^m\).
Set \(n=\lceil m\lambda/\epsilon\rceil\) and \(h=\lambda/n\). Query the \(n\) entire price vectors
\( p^{(k)}=(kh,\ldots,kh),\qquad k=1,\ldots,n. \)
For each good \(j\), retain a price \(\widehat p_j\) maximizing its observed revenue, also allowing price zero with its known revenue zero. Output the vector \(\widehat p\).
Fix \(q\in[0,\lambda]\), and put \(s=h\lfloor q/h\rfloor\). If \(s>0\), monotonicity gives
\( qD_j(q)-sD_j(s) \leq(q-s)D_j(q)\leq h. \)
If \(s=0\), the same bound follows from \(qD_j(q)\leq q\leq h\). Since \(\widehat p_j\) is at least as good as the grid price \(s\),
\( r_j(\widehat p_j)\geq r_j(q)-h. \)
Applying this independently to every coordinate of any \(q\in[0,\lambda]^m\) gives
\( R_\mu(\widehat p)\geq R_\mu(q)-mh \geq R_\mu(q)-\epsilon. \)
Taking the supremum over \(q\) proves the guarantee. This argument does not require the supremum to be attained.
There are \(n\) queries, because each query samples every good simultaneously. Processing each reply requires \(O(m)\) exact-real operations and comparisons. Maintaining only the current best prices and revenues uses \(O(m)\) working registers.
Computing \(n\) and the rational grid requires polynomial-time preprocessing in \(L\); the grid prices have polynomial encoding length in \(L\). Thus the non-oracle running time is \(\operatorname{poly}(L)+O(mn)\). A bit-cost bound for operations on arbitrary exact-real oracle replies is not defined by the stated model.
Without querying, post \(\overline p=(\lambda/2,\ldots,\lambda/2)\). Let \(s=\lambda/2\).
For \(0\leq q\leq s\),
\( r_j(q)-r_j(s)\leq qD_j(q)\leq s. \)
For \(s\leq q\leq\lambda\), monotonicity gives
\( r_j(q)-r_j(s) \leq(q-s)D_j(s)\leq s. \)
Prices above \(\lambda\) have zero revenue. Therefore,
\( \sup_{q\geq0}R_\mu(q)-R_\mu(\overline p) \leq m\lambda/2. \)
A deterministic zero-query algorithm outputs some fixed \(p\). For each good, assign every supported type the same linear valuation \(v_{tj}(z)=a_jz\).
Under the specified tie rule, demand is \(1\) at prices at most \(a_j\), and zero at prices greater than \(a_j\). The optimal revenue is \(a_j\).
If \(p_j\leq\lambda/2\), choose \(a_j=\lambda\). The revenue loss is \(\lambda-p_j\geq\lambda/2\).
If \(p_j>\lambda/2\), choose \(a_j\) satisfying \(\lambda/2<a_j\leq\lambda\) and \(a_j<p_j\). Such a choice exists. The posted price has zero demand, so its loss is \(a_j>\lambda/2\).
Combining these choices gives total loss at least \(m\lambda/2\). Hence zero queries cannot guarantee any \(\epsilon<m\lambda/2\).
We construct admissible valuations whose demands differ only within one small price interval.
Put \(a=\lambda/4\). Define a marginal-value function \(g_0\) by
Let \(V_0(z)=\int_0^z g_0(y)\,dy\).
The function \(g_0\) is nonnegative, nonincreasing, and bounded by \(\lambda\). Therefore \(V_0\) is nonnegative, nondecreasing, and \(\lambda\)-Lipschitz. It is concave: for \(x<y<z\), the average of \(g_0\) over \([x,y]\) is at least its average over \([y,z]\), so successive secant slopes decrease.
Its selected demand \(D_0\) is
Indeed, utility increases where \(g_0>p\), decreases where \(g_0<p\), and the largest maximizer includes any intervening flat interval. In particular, at \(p=\lambda\), the flat interval is \([0,1/4]\), giving demand \(1/4\).
Thus \(pD_0(p)\leq a\) everywhere, with equality throughout \([a,\lambda]\).
Fix \(\lambda/2\leq u<v\leq3\lambda/4\). Replace \(g_0\) on the quantity interval \([a/v,a/u]\) by the constant \(v\), leaving it unchanged elsewhere. Call the resulting function \(g_{u,v}\), and define
\( V_{u,v}(z)=\int_0^z g_{u,v}(y)\,dy. \)
Before that interval, \(g_0\geq v\). After it, \(g_0\leq u<v\). Hence \(g_{u,v}\) remains nonincreasing and lies in \([0,\lambda]\). The same argument as above verifies all valuation hypotheses.
Its selected demand satisfies
\( D_{u,v}(p)=D_0(p)\quad\text{for }p\notin(u,v], \)
and
\( D_{u,v}(p)=a/u\quad\text{for }u<p\leq v. \)
For \(u<p<v\), marginal utility is positive up to quantity \(a/u\) and negative afterwards. At \(p=v\), utility is flat on \([a/v,a/u]\); greater-consumption tie-breaking selects \(a/u\). At \(p=u\), demand also equals \(a/u=D_0(u)\). Outside this price range, the baseline crossing occurs outside the modified quantity interval.
The maximum revenue is attained at \(p=v\), and its increase over the baseline maximum is
\( av/u-a=a(v-u)/u. \)
Let \(K=\lfloor m\lambda/(24\epsilon)\rfloor\). Suppose \(K\geq2\). Partition \((\lambda/2,3\lambda/4]\) into \(K\) disjoint intervals \(I_k=(u_k,v_k]\), each of width \(w=\lambda/(4K)\).
Every corresponding peak has height above the baseline at least
\( a(v_k-u_k)/u_k \geq(\lambda/4)\,w/(3\lambda/4) =\lambda/(12K) \geq2\epsilon/m. \)
Consider an algorithm claiming worst-case query count \(Q<K-1\). Run it against the baseline instance, assigning \(V_0\) to every type and good, and let \(\widehat p\) be its output.
For each good \(j\), its queried coordinate prices and its output coordinate occupy at most \(Q+1<K\) intervals. Choose an interval \(I_{k_j}\) containing none of those prices.
Now assign every supported type the component valuation \(V_{u_{k_j},v_{k_j}}\) for good \(j\). Because all types have identical demands and their masses sum to \(1\), aggregate demand equals the constructed demand.
Every queried coordinate lies outside its modified interval. All oracle replies therefore remain identical. Determinism implies, inductively, that the algorithm follows the same adaptive query sequence and returns the same \(\widehat p\).
At the output price, each good has revenue at most \(a\). Each good’s optimal revenue is at least \(a+2\epsilon/m\). Posting the peak price independently for every good therefore gives
\( \sup_{q\geq0}R_\mu(q)-R_\mu(\widehat p) \geq2\epsilon>\epsilon. \)
This contradicts the required guarantee. Consequently \(Q^*\geq K-1\). Together with Section 3, this proves the stated explicit lower bound.
The construction works for every prescribed mass vector. If distinct identifiers are additionally required to represent distinct valuations, adding different nonnegative constants to their valuations makes them distinct without changing demands or any hypothesis.
Put \(\rho=m\lambda/\epsilon\). In the positive-query regime, \(\rho>2\).
If \(\rho<96\), the lower bound \(Q^*\geq1\) implies \(Q^*\geq\rho/96\). If \(\rho\geq96\), then
\( Q^*\geq\lfloor\rho/24\rfloor-1 \geq\rho/24-2 \geq\rho/48. \)
Thus throughout this regime,
\( \rho/96\leq Q^*\leq\lceil\rho\rceil, \)
establishing the claimed tight asymptotic bound.
Neither support size nor mass encoding introduces an additional query factor. The numerical dependence can nevertheless be exponential in \(L\): already with \(m=\tau=\lambda=1\) and \(\epsilon=2^{-b}\), the required query count is \(\Theta(2^b)\), while the explicit input length is \(\Theta(b)\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The upper bound, exact zero-query threshold, and matching lower bound hold uniformly for every prescribed support and positive mass vector. I found no major or minor mathematical issues requiring repair.
The result concerns deterministic aggregate-demand query complexity in the stated exact-real model. Its dependence on inverse accuracy can be exponential in the explicit input length; it does not establish a conventional complexity-class hardness result.
All claims in Section 1 are valid.
Separability justifies the decomposition \(R_\mu(p)=\sum_{j=1}^m r_j(p_j)\).
The algorithm and error calculation are correct.
With \(n=\lceil m\lambda/\epsilon\rceil\) and \(h=\lambda/n\), every positive grid price is queried. Price zero needs no query because its revenue is known.
For \(s=h\lfloor q/h\rfloor>0\), monotonicity gives precisely the stated bound \(qD_j(q)-sD_j(s)\leq(q-s)D_j(q)\leq h\). For \(s=0\), the bound follows from \(D_j(q)\leq1\). At \(q=\lambda\), the rounded price is \(\lambda\), which is included in the grid.
Choosing the best observed price independently for each coordinate is legitimate: coordinate demand depends only on its own price. Summing coordinate errors gives \(mh\leq\epsilon\).
The inequality holds for every comparison vector, so taking a supremum requires neither attainment nor continuity of revenue.
The count is \(n\) entire-vector queries, rather than \(mn\) queries.
Both directions are correct.
For the proposed price \(s=\lambda/2\), the two price ranges cover \([0,\lambda]\), and each coordinate’s revenue loss is at most \(\lambda/2\). Prices above \(\lambda\) yield zero revenue. Thus the guarantee includes the boundary \(\epsilon=m\lambda/2\).
For necessity, a deterministic zero-query algorithm has a fixed output once the explicit input is fixed. The chosen linear valuations satisfy every valuation assumption. Greater-consumption tie-breaking gives demand one at equality with the slope.
The slope choices are valid in both cases:
These choices can be made simultaneously for all goods and assigned to every supported type. Total loss is at least \(m\lambda/2\), disproving any smaller zero-query guarantee.
The baseline construction is admissible.
Its marginal function is nonnegative, nonincreasing, and bounded by \(\lambda\). Integration therefore gives a nonnegative, nondecreasing, concave, \(\lambda\)-Lipschitz valuation. The secant-slope explanation supplied in the proof justifies concavity directly.
The stated demand formula is correct, including its endpoints:
Thus baseline revenue never exceeds \(a\), and equals \(a\) throughout \([a,\lambda]\).
The modification preserves all valuation hypotheses.
At the left quantity boundary, the unchanged marginal value is \(v\). At the right boundary, the modified value is \(v\), followed by unchanged values at most \(u<v\). Hence the modified marginal function remains nonincreasing and bounded by \(\lambda\). Values at individual integration endpoints do not change the valuation.
The demand formulas are correct. In particular:
Consequently, the exceptional price set is exactly \((u,v]\). Outside it, revenue is at most \(a\); inside it, revenue is \(pa/u\), maximized at \(p=v\). The peak increase \(a(v-u)/u\) is correct.
The construction and constants are valid.
For \(K=\lfloor m\lambda/(24\epsilon)\rfloor\geq2\), the interval width is \(w=\lambda/(4K)\). The peak increase satisfies
\(\lambda/(12K)\geq2\epsilon/m\), because \(K\leq m\lambda/(24\epsilon)\).
For each good, at most \(Q+1\) intervals contain a queried coordinate price or the output coordinate price. The half-open intervals are disjoint, including at their shared endpoints. If \(Q<K-1\), an unoccupied interval therefore exists for every good.
Choosing a different hidden interval for each good is permitted by additive valuations. Assigning identical component valuations to every type makes aggregate demand equal to the constructed demand for every prescribed mass vector.
All replies on the baseline execution remain unchanged after modification. Determinism then justifies the induction preserving the complete adaptive transcript and final output.
At that output, every coordinate has revenue at most \(a\). Independently posting each peak price gives total revenue at least \(ma+2\epsilon\). The resulting loss exceeds \(\epsilon\), proving the contradiction.
For \(K<2\), the separately proved one-query lower bound supplies the stated bound \(\max\{1,K-1\}\).
The conversion to a uniform asymptotic bound is correct.
For \(2<\rho<96\), the lower bound one implies \(Q^*\geq\rho/96\). For \(\rho\geq96\), the displayed floor estimates give \(Q^*\geq\rho/48\). Combined with \(Q^*\leq\lceil\rho\rceil\), these prove the claimed \(\Theta(\rho)\) bound throughout the positive-query regime.
Neither construction introduces dependence on support size or mass encoding. If distinct valuations are required, adding distinct nonnegative constants preserves demands and all component hypotheses.
The example \(\epsilon=2^{-b}\), with all other parameters fixed, correctly demonstrates exponential query dependence on input length.
Processing each reply costs \(O(m)\) exact-real operations and comparisons. Rational preprocessing and grid-price encoding have polynomial cost and length in \(L\); enumerating and processing the grid gives the stated \(\operatorname{poly}(L)+O(mn)\) non-oracle time. The zero-query implementation has the stated \(\operatorname{poly}(L)+O(m)\) bound.
The qualification concerning arbitrary exact-real replies correctly matches the stipulated computational model.
The attribution is accurate: Section 5 contains the zero-cost grid-query remark described by the prover. The submitted proof nevertheless establishes its bounds independently. [Ji, Mehta, and Telgarsky, Section 5](https://arxiv.org/pdf/1711.02211v2)
No mathematical repairs or additional clarification are 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.