Answer: Polynomial-time learnable with polynomial sample complexity.
Theorem 3.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAllPairsLearn(δ) efficiently δ-learns the class of linear valuation functions given m = O n2 ln(n2/δ) δ observations.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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\)?
There are \(m\geq1\) divisible goods, with bundles \(x\in[0,1]^m\). A society is given by its support: a list of \(\tau\geq1\) type labels with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Each type has an unknown fixed vector \(v_t\in\mathbb R_{\geq0}^m\), giving utility \(v_t\cdot x\). Define \(x^*(v,p,B)\) to maximize this utility subject to \(p\cdot x\leq B\), choosing the cheapest maximizer and then the lexicographically smallest among remaining ties, in a fixed known coordinate order.
The learner receives independent observations \((t,p,B,x^*(v_t,p,B))\), where the type label is observed, \(t\sim\mu\), and independently \((p,B)\sim D\). The unknown distribution \(D\) is arbitrary over binary-rational \(p\in[0,1]^m\) and \(B\geq0\). Let \(L\) bound the total encoding length of the supplied support and of each market example.
For every such society, utility family, distribution, and rational \(0<\delta<1\), the learner must return rational vectors \(\hat v_t\in\mathbb Q_{\geq0}^m\) such that, with probability at least \(1-\delta\) over training and learner randomness, \(\Pr_{t\sim\mu,(p,B)\sim D}[x^*(v_t,p,B)=x^*(\hat v_t,p,B)]\geq1-\delta\).
Does this learning problem admit sample complexity and training and prediction time polynomial in \(m,\tau,L,1/\delta\), or is it NP-hard?
For one consumer, [Zadimoghaddam–Roth](https://arxiv.org/pdf/1211.4150) establish efficient learning with \(O(m^2\log(m^2/\delta)/\delta)\) observations; their formal guarantee is equality of achieved true utility.
For one consumer with almost surely unique optimal bundles, [Balcan et al.](https://www.cs.cmu.edu/~ninamf/papers/revealed-pref-optimal.pdf) establish efficient learning with \(O((m\log(1/\delta)+\log(1/\delta))/\delta)\) observations when error and confidence parameters both equal \(\delta\).
No result settling exactly the supported society problem with observed type labels and the stated tie rule was located.
1. Result
The problem admits polynomial sample complexity and polynomial training and prediction time. Exact ties, zero prices, zero utilities, and arbitrarily small type masses are all allowed.
One sufficient sample bound is
\(N=O\!\left((\tau m^2(L+\log(m+1))+\log(1/\delta))/\delta\right)\).
As usual, an arbitrarily long encoding of the accuracy parameter contributes its input-reading cost separately; the algorithm only needs a dyadic lower approximation to \(\delta\) within a factor of two.
The proof establishes equality of selected bundles directly. This matters because the formal utility-equality criterion in [Zadimoghaddam–Roth, Definition 2.3](https://arxiv.org/pdf/1211.4150) does not by itself determine choices among tied bundles.
2. The canonical demand rule
Relabel coordinates so that the given lexicographic order is \(1,\ldots,m\).
For any nonnegative utility vector \(w\), its canonical demand can be computed as follows:
We first justify this rule, including its tie-breaking direction.
The feasible set is nonempty and compact. Maximizing utility, then minimizing cost, then successively minimizing coordinates therefore defines a unique bundle.
A free positive-value good must be full: increasing it otherwise improves utility. A zero-value good must have quantity zero: decreasing its quantity either lowers cost, if its price is positive, or improves the lexicographic objective, if its price is zero.
Let \(P=\{i:p_i>0,\ w_i>0\}\), and let \(S=\sum_{i\in P}p_i\). The selected bundle spends exactly \(\min\{B,S\}\). Indeed, if its expenditure were smaller, some good in \(P\) would be unfilled and could be increased while preserving feasibility and improving utility.
Now suppose \(i,j\in P\), \(i\ne j\), \(x_i>0\), and \(x_j<1\). For sufficiently small \(\varepsilon>0\), the exchange
\(x_i\leftarrow x_i-\varepsilon/p_i\), \(x_j\leftarrow x_j+\varepsilon/p_j\)
is feasible and preserves cost. Its utility change is
\(\varepsilon(w_j/p_j-w_i/p_i)\).
Consequently, \(w_i/p_i\geq w_j/p_j\). If these ratios are equal and \(i<j\), the exchange lowers the first changed coordinate, contradicting lexicographic minimality. Hence equal ratios require \(i>j\).
Thus every purchased good precedes every distinct unfilled good in the stated total order. This forces a full prefix, followed by at most one fractional good, followed by zeros. The prescribed expenditure uniquely determines that prefix bundle, proving the rule.
In particular, rational prices and budgets produce rational selected bundles, even when the utility vector is irrational.
3. Exact consistency is a system of linear constraints
Consider one genuine observation \((p,B,x)\). We characterize precisely those nonnegative vectors \(w\) satisfying \(x^*(w,p,B)=x\).
Impose the following constraints:
\(p_jw_i-p_iw_j>0\) when \(i<j\), and
\(p_jw_i-p_iw_j\geq0\) when \(i>j\).
These are strict linear inequalities, weak linear inequalities, and linear equalities.
Necessity. If a purchased good had zero value, decreasing its quantity would improve either cost or the lexicographic objective. If an unpurchased free good had positive value, increasing it would improve utility. With budget slack, increasing any unfilled positive-value good would improve utility. Finally, the exchange argument above gives exactly the pairwise inequalities, including strictness when \(i<j\).
Sufficiency with budget slack. Every positive coordinate of \(x\) requires positive value, while every coordinate below one requires zero value. Therefore \(x\) consists precisely of all positive-value goods at quantity one and all zero-value goods at quantity zero. It is affordable and is the canonical demand.
Sufficiency with a binding budget. The free coordinates agree with the canonical rule, since a genuine observation has each free coordinate in \(\{0,1\}\). Every positive-price good with \(w_i=0\) has \(x_i=0\).
Order the positive-price, positive-value goods as in Section 2. Whenever \(x_i>0\) and \(x_j<1\), the pairwise constraints say that \(i\) precedes \(j\): for \(i<j\), the ratio comparison is strict; for \(i>j\), equality also favors \(i\).
Hence \(x\) has the required prefix form. Its expenditure is \(B\), so it is exactly the greedy prefix bundle. This also covers \(B=0\), when every positive-price coordinate is zero.
We have therefore proved the exact equivalence:
\(x^*(w,p,B)=x\) if and only if \(w\) satisfies the displayed constraints.
Each observation contributes only \(O(m^2)\) constraints.
4. Polynomial-time fitting with uniformly bounded rational output
Group the observations by their observed type labels. For each type, combine all its consistency constraints.
Introduce variables \(w_1,\ldots,w_m,\eta\), and impose
\(w_i\geq0\), \(\sum_iw_i\leq1\), and \(0\leq\eta\leq1\).
Keep every equality and weak inequality. Replace every strict inequality \(a\cdot w>0\) by \(a\cdot w\geq\eta\). Maximize \(\eta\).
The optimum is positive. To prove this, first suppose the true type vector is nonzero and normalize it to have coordinate sum one. Positive rescaling preserves every consistency constraint. There are finitely many strict constraints, and every strict left-hand side is positive at this normalized vector. Their minimum, capped at one, supplies a feasible positive \(\eta\). If there are no strict constraints, \(\eta=1\) is feasible. The zero true vector can occur only in the latter case.
Thus an optimal solution satisfies all original strict constraints and reproduces every training bundle exactly.
We use the standard rational linear programming theorem: an optimal vertex of a nonempty bounded rational polytope can be found in time polynomial in its inequality encoding. Its hypotheses hold here: the constraints are rational, feasible, and bounded by the normalization and bounds on \(\eta\).
Crucially, the output vertex has a bit bound independent of the number of observations. Here is an explicit bound.
Set \(d=m+1\). Every constraint row contains at most two price coefficients; all other coefficients and right-hand sides belong to \(\{0,1,-1\}\). Under the stated encoding bound, each price numerator and denominator is at most \(2^L\). Clearing denominators separately in each row gives integer coefficients and right-hand sides of absolute value at most \(M=2^{2L}\).
At a vertex, choose \(d\) linearly independent tight rows. Cramer’s rule expresses every coordinate as a ratio of integer determinants. The determinant expansion bounds both numerator and denominator in absolute value by
\(d!M^d\leq d^d2^{2Ld}\).
Therefore, with
\(K=2Ld+d\lceil\log_2d\rceil+1\),
every returned utility coordinate has a representation \(a/b\) with
\(0\leq a\leq2^K\) and \(1\leq b\leq2^K\).
This bound depends only on \(m,L\). It requires no lower bound on positive utility coordinates or on utility-ratio gaps. For an unobserved type, return the zero vector.
5. Generalization across the supported society
Let \(\mathcal H\) be the finite class of all families of \(\tau\) utility vectors whose coordinates lie in \([0,1]\) and have numerator and denominator bounded as above. The learner’s output always belongs to \(\mathcal H\).
There are at most \(2^{2K+2}\) possible rational coordinates, so
\(|\mathcal H|\leq2^C\), where \(C=(2K+2)m\tau\).
For a fixed family \(h\in\mathcal H\), define its error by
\(\operatorname{err}(h)=\Pr_{t\sim\mu,\,(p,B)\sim D}[x^*(v_t,p,B)\ne x^*(h_t,p,B)]\).
If \(\operatorname{err}(h)>\delta\), independence of the training observations gives
\(\Pr[h\text{ agrees with all }N\text{ observations}]=(1-\operatorname{err}(h))^N\leq e^{-\delta N}\).
Taking a union bound over the fixed finite class yields
\(\Pr[\exists h\in\mathcal H:\operatorname{err}(h)>\delta\text{ and }h\text{ is sample-consistent}]\leq2^Ce^{-\delta N}\).
For example, set \(r=\lceil\log_2(1/\delta)\rceil\) and take
\(N=\lceil(C+r)/\delta\rceil\).
Then the preceding probability is at most
\(e^{C\ln2-C-r}\leq e^{-r}\leq\delta\).
The fitting procedure always returns a sample-consistent member of \(\mathcal H\). Hence, with probability at least \(1-\delta\), its population error is at most \(\delta\), exactly as required.
Since \(K=O(m(L+\log(m+1)))\), this gives the sample bound stated in Section 1.
No minimum type mass is needed. The argument bounds error under the joint population distribution directly, including errors on types absent from the training sample.
6. Training and prediction complexity
The learner constructs \(O(Nm^2)\) observation constraints and solves at most \(\tau\) rational linear programs, each having \(m+1\) variables. Their coefficient lengths, and the returned utility lengths, are polynomially bounded as established above. Training therefore takes polynomial bit time in the stated parameters.
For prediction, retrieve the utility vector of the observed type and apply Section 2. Ratio comparisons use rational cross-products, and the final fractional quantity uses rational arithmetic on the query prices and budget. The utility encoding bound makes prediction time polynomial as well.
Thus the supported society problem with observed labels and the prescribed tie rule is efficiently learnable.
⟨structured verdict parsed — rendered above⟩
The argument establishes polynomial-time learnability under the stated encoding bound. I found no mathematical error or gap requiring additional mathematics. In particular, it proves equality of the selected bundles, including the prescribed handling of ties.
The existence and uniqueness argument is valid: the feasible set is nonempty and compact, and successive optimization of utility, expenditure, and coordinates produces a unique selected bundle.
The treatment of zero prices and zero utilities is correct. A free positive-value good must be full; a zero-value good must be zero under expenditure minimization or lexicographic minimization.
For the positive-price, positive-value goods, the claimed expenditure \(\min\{B,S\}\) follows from the stated improvement argument. The exchange preserves expenditure, and its utility change is correctly calculated as
\[
\varepsilon(w_j/p_j-w_i/p_i).
\]
When the ratios agree and \(i<j\), decreasing coordinate \(i\) and increasing coordinate \(j\) strictly improves lexicographic order. Consequently, decreasing coordinate index is the correct direction for breaking ratio ties.
The purchased-versus-unfilled comparison forces the claimed prefix structure, with at most one fractional good. The prescribed expenditure then determines its quantities uniquely. This also verifies the assertion that rational market data produce rational selected bundles.
All four families of constraints are necessary for a genuine observation:
The cross-product orientation is correct: \(p_jw_i-p_iw_j>0\) means that good \(i\) has strictly higher utility per unit price.
The slack-budget sufficiency argument is valid. Together, the positivity and zero-value constraints exclude fractional coordinates and identify exactly the full positive-value goods.
The binding-budget sufficiency argument is also valid. Its use of feasibility and binary free-good quantities is justified because the section explicitly restricts attention to genuine observations. On the positive-price, positive-value goods, the pairwise constraints enforce precisely the canonical order established in Section 2. Their prefix structure and expenditure \(B\) therefore identify the selected bundle.
The case \(B=0\) is covered: feasibility forces every positive-price quantity to zero, while the free-good constraints determine the remaining coordinates correctly.
Thus the claimed equivalence between exact demand consistency and the linear constraints holds on the stated domain.
The normalization is legitimate because positive rescaling preserves all consistency constraints and the selected demand.
For a nonzero true vector, normalization supplies a feasible vector satisfying every strict inequality. Since the training set is finite, the minimum of its finitely many positive strict left-hand sides is positive. Capping that minimum at one gives a feasible positive \(\eta\).
When there are no strict constraints, \(\eta=1\) is feasible. A zero true vector cannot generate a strict constraint, since such constraints require a purchased positive quantity.
Therefore the optimum is positive, and every optimal solution satisfies the original strict inequalities. Exact training consistency follows.
The stated rational linear programming theorem applies. The constructed polytope is rational, nonempty, and bounded; its objective is the rational linear function \(\eta\). Selecting an optimal vertex is essential to the subsequent encoding argument, and the prover explicitly requires that selection.
The coefficient bound checks out. A row has at most two price coefficients, and clearing their denominators produces integer coefficients and right-hand sides bounded by \(2^{2L}\). The normalization row and the bounds on \(\eta\) also satisfy this bound.
At a vertex in \(d=m+1\) variables, \(d\) independent tight constraint rows can be selected, including when the feasible polytope has lower dimension. Cramer’s rule applies to the resulting nonsingular integer system.
Both the denominator determinant and every numerator determinant satisfy the stated bound:
\[
|\det|\leq d!M^d\leq d^d2^{2Ld}.
\]
With
\[
K=2Ld+d\lceil\log_2d\rceil+1,
\]
this is below \(2^K\). Adjusting the signs of numerator and denominator gives the claimed nonnegative rational representation.
Crucially, this bound depends on \(m,L\), rather than the number of observations. No lower bound on true utility coordinates or ratio gaps is used.
The hypothesis class is fixed independently of the random training sample: its coordinate bounds depend only on \(m,L\), and its number of type vectors is the supplied support size \(\tau\). Every returned vector lies in this class, including the zero vectors returned for unobserved types.
The coordinate count \(2^{2K+2}\) is a valid upper bound, so
\[
|\mathcal H|\leq 2^C,\qquad C=(2K+2)m\tau.
\]
For each fixed hypothesis family, independent observations give the claimed probability of complete sample agreement. The union bound is valid even though the learner selects its hypothesis after seeing the sample.
The constants in the sample calculation also check out. For
\[
r=\lceil\log_2(1/\delta)\rceil,\qquad
N=\lceil(C+r)/\delta\rceil,
\]
one has
\[
2^Ce^{-\delta N}
\leq e^{C(\ln 2-1)-r}
\leq e^{-r}
\leq\delta,
\]
because \(r\geq\ln(1/\delta)\).
Hence the returned family has joint population error at most \(\delta\), with confidence at least \(1-\delta\). This is exactly the requested probability statement. The argument correctly includes unobserved types and requires no minimum positive type mass.
Substituting the established bound on \(K\) gives
\[
N=O\!\left(
\frac{\tau m^2(L+\log(m+1))+\log(1/\delta)}{\delta}
\right).
\]
This matches the announced bound.
Constructing the consistency constraints requires only exact rational arithmetic and comparisons. There are \(O(Nm^2)\) observation constraints, and at most \(\tau\) linear programs with polynomial encoding size. The established linear programming and output-size bounds therefore justify polynomial training bit complexity.
Prediction uses the verified canonical rule. Rational cross-products suffice for ratio comparisons, and rational arithmetic computes any fractional quantity. Prediction time is polynomial in the utility encoding size and the market encoding size.
The caveat concerning an arbitrarily long encoding of \(\delta\) is explicit. Using the stated dyadic lower approximation changes sample complexity by only a constant factor and preserves the requested error and confidence bounds.
The proof handles irrational true utilities, exact ratio ties, zero prices, zero utilities, zero budgets, and arbitrarily small positive type masses.
The distinction drawn from Zadimoghaddam–Roth is accurate: their formal Definition 2.3 compares achieved true utilities, which does not uniquely determine bundles when utility maximizers tie. The present argument independently establishes the stronger selected-bundle guarantee. [Definition 2.3](https://arxiv.org/pdf/1211.4150)
No repair or additional clarification is needed for the mathematical argument.
⟨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.