| paper | d4-conf-wine-2014-0012 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: Deterministic polynomial-time solvable, with \(O(d^2\tau n)\) adaptive queries, query lengths \(O(dn)\), and answer lengths \(O(d(\tau L+n))\). · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 19
statement extracted from the paper’s text layer
Let \(\mathcal A_{d,n}\) be the finite set of normalized vectors \(a\in\mathbb Q_{\ge0}^d\), with \(\sum_j a_j=1\) and coordinate bit length at most \(n\). An unknown rational distribution \(\mu\) has support size at most \(\tau\), with masses of bit length at most \(L\). An oracle queried at rational prices \(p\in\mathbb Q_{\ge0}^d\) and budget \(B\in\mathbb Q_{\ge0}\) returns \(D_\mu(p,B)=\sum_a\mu_a b_a(p,B)\), where \(b_a\) is the paper's tie-broken optimal bundle for type \(a\). Can an adaptive algorithm using time and queries polynomial in \(d,\tau,n,L\) and the query bit length output at most \(\tau\) rational type-mass pairs that induce the same \(D_\mu(p,B)\) for every rational \(p,B\)?
Types are normalized linear utility vectors \(a\in\mathcal A_{d,n}\), and \(\mu_a\) is each type's population mass. Chosen price-budget pairs are the queries and exact per-capita demand is the response. The unknown decision variable is the sparse distribution \(\mu\); the goal is exact identification up to equality of the induced demand function, rather than optimization of a scalar objective.
Mirrors Theorem 19's exact query-learning result for linear utilities; leaves the statistical PAC results, other utility classes, and the paper's other query-learning results uncovered.
The strongest honest anchor is Theorem 19, proved in this paper: for normalized linear utilities \(U_a(x)=\sum_{j=1}^d a_jx_j\), with rational parameters of bit length at most \(n\), the class \(H_{\mathrm{lin}}\) can be learned exactly from \(O(nd)\) revealed-preference queries. The learner chooses prices and a budget, observes the buyer’s optimal bundle, and outputs the utility function. This is the paper’s own result.
A plausible population mirror is Aggregate Linear Revealed-Preference Identification. There are \(N\) consumers, each with one unit of each of \(d\) goods available and the same per-person budget. A type is a normalized rational utility vector \(a\in\mathbb Q_{\ge0}^d\), with coordinates of bit length at most \(n\). The society is a rational distribution \(\mu\) over these types, with support size at most \(\tau\). Thus \(\mu_a\) is the fraction of consumers with utility type \(a\); all consumers of a type have the same preferences and treatment. For a price vector \(p\) and budget \(B\), let \(b_a(p,B)\) be type \(a\)’s optimal bundle, using the paper’s tie-breaking rule. An aggregate query returns the per-capita demand
\[
D_\mu(p,B)=\sum_a\mu_a b_a(p,B).
\]
The question is: given \(d,n,\tau\), a bound \(L\) on the bit length of the masses, and oracle access to exact \(D_\mu(p,B)\) for rational \(p,B\), can an adaptive algorithm use time and queries polynomial in \(d,\tau,n,L\) to output a list \((a^r,\lambda_r)_{r=1}^s\), \(s\le\tau\), whose aggregate demand agrees with \(D_\mu\) for every rational price vector and budget? Any such representation is acceptable, including one that differs from the original masses but induces the same demand function.
The regime is a large retail market with many recurring consumers and relatively few stable preference profiles across product categories. The population size \(N\) is large compared with \(\tau\); prices and budgets are set per consumer, while total supplies scale with the population. Mass gives the model a direct market meaning: the returned demand is average demand per consumer, and each type contributes in proportion to its share. This is population continuization. The goods are already divisible in the paper, but that is not the object being continuized here.
I would expect this problem to be continuum-specifically hard as a working hypothesis. Each oracle answer combines all types’ choices, so recovering a sparse population model requires disentangling overlapping demand responses across queries. The useful follow-up questions are whether the aggregate demand function identifies the type masses at all; whether the problem is fixed-parameter tractable in \(\tau\); and whether type recovery can be reduced to efficient pricing or separation subproblems. Rational masses also give a bridge to finite high-multiplicity markets: common-denominator masses correspond to cohort counts, while rounding masses offers a route to approximation questions.
The authors could plausibly recognize this as a continuous-population extension of their problem: it retains their revealed-preference interface, demand function, and active price-and-budget queries, and aggregates consumers who share a complete utility type. It asks about learning market demand from cohort behavior, a natural economic question.
The weak point is substantial: Theorem 19 learns one buyer’s utility from individual bundle observations. It establishes nothing about recovering a heterogeneous population from aggregate observations; that is a new problem, and the theorem’s \(O(nd)\) bound does not transfer directly. The mirror is strongest as a well-posed research question inspired by the paper, rather than as a result already implicit in its analysis. Its scope is Theorem 19’s exact query-learning result for linear utilities; it does not attempt to mirror the paper’s statistical PAC guarantees or its other utility classes.
The strongest case against rests on the distance between Theorem 19 and the proposed problem. The theorem learns one buyer’s normalized linear utility from chosen price and budget queries, observing that buyer’s bundle each time. Aggregate revealed preference asks a different question: recover a distribution of buyers from pooled responses. The theorem’s \(O(nd)\) query bound says nothing about that mixture problem, and even the target has changed from an individual utility to an aggregate demand function.
That gap is real, but it does not defeat the mirror. The stronger version is exactly the proponent’s model: a large retail population with recurring preference types, common per-person market conditions, and observed per-capita demand under chosen prices. A distribution over complete utility types is a sensible population model; pooling responses is a natural market observation; and allowing any demand-equivalent representation avoids requiring recovery of unidentifiable labels. The authors could plausibly recognize this as a revealed-preference learning problem. A statistical version using repeated market observations would be another reasonable formulation. Neither needs Theorem 19’s proof or bound to transfer: the new aggregate-learning question is the computational question the mirror would pose.
The only substantial objection is that this is a new inverse problem inspired by the theorem, rather than a direct high-multiplicity version of its single-buyer task. That weakens the claim that the paper itself already points toward this mirror. It does not show the question is outside the authors’ problem, or that the continuous population regime is implausible. The paper’s query model, utility types, and market-demand setting all carry over.
So I cannot make a strong negative case against this anchor. The proposed mirror survives the main objections available here; the honest reservation is about how closely it mirrors the theorem, not whether it is 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.