| paper | d4-conf-wine-2012-0035 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time learnable with polynomial sample complexity. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3.2
statement extracted from the paper’s text layer
Given \(n\) goods, \(\tau\) known consumer types with rational masses \(\mu_t\), and an unknown linear utility vector \(v_t\) for each type, training observations are drawn by sampling \(t\sim\mu\), then \((p,B)\sim D\), and observing that type’s utility-maximizing bundle. Can an efficient learner return hypotheses \(\hat v_t\) such that, with high probability over training, a random type and future market example satisfy \(x^*(v_t,p,B)=x^*(\hat v_t,p,B)\) with probability at least \(1-\delta\)?
A finite-support population with known type labels and rational masses \(\mu_t\), where each type has an unknown linear valuation vector \(v_t\). The learner uses labeled purchase observations to return one hypothesis \(\hat v_t\) per type, and its exact-prediction guarantee is weighted by \(\mu\) over consumers and by \(D\) over future price-budget examples.
Known labels let the learner handle each utility type independently, so μ mainly weights separate single-consumer guarantees and the paper does not study a collective decision.
fatal: False
The mirror covers the exact-prediction result in Theorem 3.2 and the approximate-learning result in Theorem 4.5; it leaves aside unrestricted utility classes, rationalizability, and the open sample-complexity bounds.
The strongest mirror is a large, segmented market in which millions of consumers choose bundles of divisible goods, but only \(\tau\) distinct preference types occur. A type is a consumer’s complete utility function; its mass \(\mu_t\) is the fraction of consumers with that function. Consumers face price and budget examples drawn from a market distribution \(D\), and the learner sees each purchase together with its known segment label. The number of consumers can be enormous while \(\tau\) stays small. A standardized benefits marketplace is one plausible setting: many employees in each segment share a preference profile, while prices and budgets vary across purchase occasions.
The paper’s distribution over price and budget examples is not itself a population distribution. The mirror adds a population distribution over preference types, while preserving the paper’s core question: learn the utility governing a consumer’s choices well enough to predict future purchases. The divisible bundles are already part of the paper’s model; the continuization here is the mass of consumers.
My lead anchor is Theorem 3.2, proved in this paper. It states that AllPairsLearn efficiently \(\delta\)-learns the class of linear valuation functions from \(m=O(n^2\ln(n^2/\delta)/\delta)\) observations. In the paper’s definition, with high probability over the training observations, the learned hypothesis predicts the agent’s exact chosen bundle on at least a \(1-\delta\) fraction of future examples from \(D\).
The population mirror I would hand to a prover is Population Linear Revealed-Preference Learning. Its input is \(n\) goods, a finite set of \(\tau\) known consumer segments with rational masses \(\mu_t\), and sample access to consumers drawn by first choosing \(t\sim\mu\), then drawing \((p,B)\sim D\) and observing that consumer’s utility-maximizing bundle. Each segment has an unknown linear utility vector \(v_t\in\mathbb{R}^n_+\). The learner must return hypotheses \(\hat v_t\) so that, with high probability over training, a random consumer and future example satisfy
\[
x^*(v_t,p,B)=x^*(\hat v_t,p,B)
\]
with probability at least \(1-\delta\). The solution is the tuple of hypotheses and the resulting prediction rule. The expected answer is tractable: run the paper’s learner on sufficiently sampled segments, and leave segments of total mass at most a small fraction of \(\delta\) uncovered. This lifts the paper’s exact-prediction guarantee to population-weighted accuracy with polynomial dependence on \(n,\tau,1/\delta\). The mirror asks whether this population guarantee can be achieved; the anchor already supplies the per-segment algorithm.
A second, broader anchor is Theorem 4.5, also proved here. For linearly separable concave utility functions with bounded second derivatives and normalized range, it gives an efficient \((\epsilon,\delta)\)-learner. On a future example, its predicted bundle either falls short of the optimal bundle by at most \(\epsilon\) in every coordinate, or loses at most \(\epsilon\) in utility. The algorithm discretizes marginal utilities with \(k\) at least \((2Q/\epsilon)R\), where \(Q\) bounds second derivatives and \(R=\max_{(p,B),j} B/p_j\); its stated sample bound is \(O((n(k+2))^2\log((n(k+2))^2/\delta)/\delta)\).
Its mirror, Population Separable Revealed-Preference Learning, uses the same labeled population and sampling process, but each segment’s unknown utility is linearly separable, concave, and satisfies those derivative and range bounds. The learner returns a predicted bundle for each segment and future price-budget example, and must achieve utility within \(\epsilon\) of that segment’s optimum for at least a \(1-\delta\) fraction of the population-example pairs, with high probability over training. The expected answer is again tractable under the theorem’s regularity and bounded-price-ratio assumptions, by learning separately on segments with enough mass and bounding the total ignored mass. This extends the mirror beyond linear preferences, but its assumptions make it the weaker anchor.
The supplied paper has no numbered hardness result, so these algorithmic anchors are the appropriate ones. Neither mirror should be presented as showing that discrete hardness dissolves: the paper establishes learning algorithms, not a discrete hardness classification. It covers the exact and approximate predictive-learning results above, not rationalizability, unrestricted utility functions, or the paper’s open sample-complexity bounds.
The soft spot is that this is a population lift of a single-agent learning model. It requires observable segment labels and shared utility within each segment; the paper does not learn a heterogeneous population or infer latent types. Also, the paper’s stated efficiency bounds are in its learning model and do not separately spell out bit-length dependence. Still, the segment-level question is recognizable as the authors’ problem: each type faces the same revealed-preference task they study, and mass makes prediction accuracy reflect how many consumers the learned rule serves.
The strongest case against is about the object being computed. The paper’s distribution \(D\) is over price and budget examples; every example is presented to an agent with the same unknown utility. Theorem 3.2 and Theorem 4.5 are genuine computational results, so “there is nothing computational to mirror” would be wrong. But neither result takes a society as input or computes a collective choice.
For Theorem 3.2, the proposed labeled-segment mirror adds a distribution \(\mu\) over agents’ utilities and asks for a hypothesis for each segment. That is a coherent population-learning problem. Yet its guarantee reduces to learning each fixed utility from that segment’s examples and averaging the errors by \(\mu_t\). The mass changes how much each segment matters, while the learned object remains a tuple of single-agent hypotheses. If everyone shares one utility, the population distribution disappears from the prediction problem. If utilities vary, a known label makes the task separate conditional learning problems. Neither case gives a new computation over the society of the kind ChoCo is trying to chart.
A stronger version could hide the labels, ask the learner to discover latent utility types, or predict aggregate demand such as \(\sum_t\mu_t x^*(v_t,p,B)\). Those are more population-specific questions, but the paper’s theorem does not anchor them: it assumes one fixed utility and studies predictions for that agent. Latent-type inference or aggregate-demand prediction changes the learning target and requires new assumptions about observations and consumers’ histories. Such work may be worthwhile in population learning, but it is not a continuous mirror of Theorem 3.2 in the programme’s sense.
Theorem 4.5 has the same boundary. With labeled segments, one can seek a mass-weighted version of its per-agent utility guarantee and learn each segment’s separable concave utility. Without labels, the task again becomes inference over a mixture of different utilities. The derivative and range assumptions carry over, but they do not create a population-level decision problem; the theorem still predicts one agent’s bundle on a future price-budget example.
So the negative case is strongest as a scope argument: these results concern predictive learning of consumer behavior, not a computational social-choice operation on a continuous society. Divisible bundles are already in the paper, and should not be mistaken for population continuization. I cannot make the universal case airtight: the paper’s motivation mentions populations of consumers, and its authors might well recognize a labeled, mass-weighted learning extension as their problem. If ChoCo counts any such population-level learning guarantee as sufficient, the Theorem 3.2 mirror survives.
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.