Answer: A valid bound is \(B_\delta=\min\{1,[E_\delta(x^\star)+E_\delta(\widehat x)]/W(x^\star)\}\), where \(E_\delta(x)=\sum_{t,S}x_{t,S}\eta_{t,\delta/\tau}(S)\). The mechanism makes exactly \(\tau q\) value queries. Enumeration and exact rational linear programming give \(2^{O(m)}\operatorname{poly}(m,\tau,L)\) optimization overhead, separately from sampling, query-answering, training, and prediction-evaluation costs. Direct SVR enumeration uses \(2^mK\) kernel evaluations. Exact succinct optimization is \(\mathrm{NP}\text{-hard}\), even for fixed quadratic-kernel SVR with zero prediction error.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateSuppose the generalized valuation functions in mechanism M(A, X, q) have a ηi,δ(s)-prediction interval with respect to distribution over valuation profiles V. Then M(A, X, q) is PAE with respect to V with εδ = ηδ(a∗ v) + ηδ(a∗ ˜v) V (a∗v) (3) where ηδ(a) = 1≤i≤n ηi,1−n√1−δ (ai).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) goods, \(\tau\) complete valuation types with rational masses \(\mu_t\), rational per-capita supplies \(\beta_j\), a valuation distribution \(\mathcal V\), query distributions \(X_t\), and learner \(A\), draw \(q\) value queries per type and compute a feasible allocation \(x_{t,S}\ge 0\) maximizing predicted welfare, subject to \(\sum_S x_{t,S}=\mu_t\) and \(\sum_{t,S:j\in S}x_{t,S}\le\beta_j\). Under specified simultaneous prediction-error envelopes \(\eta_{t,\alpha}(S)\), establish a PAE bound on the relative true-welfare loss against the best feasible mass allocation, and characterize the query and running-time complexity in \(m,\tau,L,q\), and the number of learner support vectors.
Let \(M\) contain \(m\ge1\) goods. A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible valuations. Supplies are binary rationals \(\beta_j\in[0,1]\).
Each type has a complete valuation \(v_t:2^M\to\mathbb Q_{\ge0}\), accessible through truthful value queries. No monotonicity or empty-bundle normalization is assumed. The joint law \(\mathcal V\) of these valuations may correlate types; masses and supplies are fixed.
For each type, draw \(q\ge1\) bundles without replacement from \(X_t\), sequentially conditioning on unqueried bundles, and query their values; require \(|\operatorname{supp}X_t|\ge q\). Sampling randomness is independent across types and independent of valuations. Train the supplied learner \(A\) once to obtain rational-valued predictions \(\widetilde v_t\), which may be negative.
Feasible allocations are masses \(x_{t,S}\ge0\) satisfying \(\sum_{S\subseteq M}x_{t,S}=\mu_t\) and \(\sum_{t,S:j\in S}x_{t,S}\le\beta_j\). Define \(W(x)=\sum_{t,S}x_{t,S}v_t(S)\) and \(\widetilde W(x)=\sum_{t,S}x_{t,S}\widetilde v_t(S)\); let \(x^\star\) maximize \(W\), and let \(\widehat x\) maximize \(\widetilde W\), using a fixed deterministic tie-breaking rule. Assume \(W(x^\star)>0\) almost surely.
Supplied nonnegative envelopes satisfy, for every type and \(\alpha\in(0,1)\), \(\Pr_{\mathcal V,\mathrm{queries},A}[\forall S\subseteq M:\ |v_t(S)-\widetilde v_t(S)|\le\eta_{t,\alpha}(S)]\ge1-\alpha\). No independence of prediction errors is assumed.
For \(\delta\in(0,1)\), an envelope-derived PAE loss bound \(B_\delta\), possibly depending on the realized valuations and allocations, means \(\Pr[1-W(\widehat x)/W(x^\star)>B_\delta]\le\delta\).
Use supplied sampling and exact prediction-evaluation routines, accounting separately for their costs and learner training cost. Let \(L\) be the total bit length of supplied finite descriptions and generated rational data; valuation tables are not explicitly supplied. For SVR, predictions have the form \(\widetilde v_t(S)=b_t+\sum_{k=1}^{K_t}c_{tk}\kappa(S,Z_{tk})\), with signed rational coefficients, rational-valued kernel evaluation, and total support-vector count \(K=\sum_tK_t\).
What envelope-derived PAE bound on relative true-welfare loss is valid for this mass mechanism, and what query and running-time bounds hold in \(m,\tau,L,q,\delta\), the supplied routine costs, and, for SVR, \(K\)?
For finite bidders, Brero, Lubin and Seuken (2017) state a PAE guarantee relating relative welfare loss to prediction radii at true and predicted optimal allocations ([source](https://people.bu.edu/blubin/papers/md/PAE-CA-ML2017AAAI.pdf)). Their later discrete analysis establishes a deterministic loss bound assuming bounded errors at those two allocations ([source](https://arxiv.org/html/1911.08042v4)).
No result settling this exact mass-allocation PAE question was identified in the search.
Fix confidence levels \(\alpha_t\in(0,1)\), chosen before the random experiment, with \(\sum_{t=1}^{\tau}\alpha_t\le\delta\). Define
\(\displaystyle E_\delta(x)=\sum_{t=1}^{\tau}\sum_{S\subseteq M}x_{t,S}\eta_{t,\alpha_t}(S).\)
In particular, one may take \(\alpha_t=\delta/\tau\).
Proven bound. The following is an envelope-derived PAE loss bound:
\(\displaystyle B_\delta=\min\left\{1,\frac{E_\delta(x^\star)+E_\delta(\widehat x)}{W(x^\star)}\right\}.\)
A sharper valid bound is
\(\displaystyle B_\delta^{\mathrm{diff}}=\min\left\{1,\frac{\sum_{t,S}|x^\star_{t,S}-\widehat x_{t,S}|\eta_{t,\alpha_t}(S)}{W(x^\star)}\right\}.\)
These statements require neither independent prediction errors nor nonnegative predictions.
Let \(F\) denote the feasible allocation set. It is nonempty: allocating mass \(\mu_t\) to the empty bundle for every type satisfies all constraints. It is closed and bounded, since every coordinate satisfies \(0\le x_{t,S}\le\mu_t\). Thus both welfare objectives attain maxima on \(F\).
For each type, define the event
\(\displaystyle G_t=\left\{\forall S\subseteq M:\ |v_t(S)-\widetilde v_t(S)|\le\eta_{t,\alpha_t}(S)\right\}.\)
The hypotheses give \(\Pr(G_t^c)\le\alpha_t\). Consequently, the union bound gives
\(\displaystyle \Pr\left(\bigcap_{t=1}^{\tau}G_t\right)\ge1-\sum_t\alpha_t\ge1-\delta.\)
Write \(G=\bigcap_tG_t\). On \(G\), for every feasible allocation \(x\),
\(\displaystyle |W(x)-\widetilde W(x)|\le\sum_{t,S}x_{t,S}|v_t(S)-\widetilde v_t(S)|\le E_\delta(x).\)
This holds simultaneously for all feasible allocations, so it applies to the random allocations \(x^\star\) and \(\widehat x\).
Predicted optimality gives \(\widetilde W(x^\star)-\widetilde W(\widehat x)\le0\). Therefore, on \(G\),
\(\displaystyle W(x^\star)-W(\widehat x)\)
\(\displaystyle =\bigl(W(x^\star)-\widetilde W(x^\star)\bigr)+\bigl(\widetilde W(x^\star)-\widetilde W(\widehat x)\bigr)+\bigl(\widetilde W(\widehat x)-W(\widehat x)\bigr)\)
\(\displaystyle \le E_\delta(x^\star)+E_\delta(\widehat x).\)
For the sharper version, put \(d_{t,S}=x^\star_{t,S}-\widehat x_{t,S}\). On the same event,
\(\displaystyle W(x^\star)-W(\widehat x)=\widetilde W(x^\star)-\widetilde W(\widehat x)+\sum_{t,S}d_{t,S}\bigl(v_t(S)-\widetilde v_t(S)\bigr)\)
\(\displaystyle \le\sum_{t,S}|d_{t,S}|\eta_{t,\alpha_t}(S).\)
True optimality and nonnegative true valuations give
\(\displaystyle 0\le1-\frac{W(\widehat x)}{W(x^\star)}\le1\)
almost surely. Dividing the preceding inequalities by the almost surely positive \(W(x^\star)\), and clipping at \(1\), proves both bounds. Their strict-exceedance events are contained in \(G^c\), whose probability is at most \(\delta\). ∎
The deterministic welfare argument parallels [Proposition 1 of the later discrete analysis](https://arxiv.org/html/1911.08042v4#S4.SS1.SSS1). The confidence allocation here deliberately uses a union bound: the multiplicative confidence calculation appearing in [Theorem 1 of the 2017 paper](https://people.bu.edu/blubin/papers/md/PAE-CA-ML2017AAAI.pdf) cannot be inferred from the present assumptions. Independent bundle sampling does not imply independent error events when valuations may correlate.
Define
\(\displaystyle h_{t,\delta}=\max_{S\subseteq M}\eta_{t,\alpha_t}(S),\qquad H_\delta=\sum_t\mu_t h_{t,\delta}.\)
For every feasible allocation \(x\), the type-mass equalities imply
\(\displaystyle E_\delta(x)\le\sum_t h_{t,\delta}\sum_Sx_{t,S}=H_\delta.\)
Thus another valid bound is
\(\displaystyle B_\delta^{\mathrm{uniform}}=\min\left\{1,\frac{2H_\delta}{W(x^\star)}\right\}.\)
In particular, if every envelope radius is at most \(\eta\), then \(H_\delta\le\eta\), because \(\sum_t\mu_t=1\). The resulting numerator is \(2\eta\); it does not acquire an additional factor of \(\tau\).
The sharper numerator also cancels overlapping allocated mass. Indeed,
\(\displaystyle \sum_S|x^\star_{t,S}-\widehat x_{t,S}|\le\sum_S(x^\star_{t,S}+\widehat x_{t,S})=2\mu_t.\)
Neither monotonicity nor empty-bundle normalization entered these arguments.
The allocation-dependent bounds above need not be observable: finding \(x^\star\) is a separate true-welfare optimization problem. An alternative uses predictions and envelopes only.
Let
\(\displaystyle p=\widetilde W(\widehat x),\qquad e=E_\delta(\widehat x),\qquad \ell=p-e.\)
Define
\(\displaystyle B_\delta^{\mathrm{obs}}= \begin{cases} \min\{1,(H_\delta+e)/\ell\},&\ell>0,\\ 1,&\ell\le0. \end{cases}\)
On \(G\), the previous proof gives
\(\displaystyle W(x^\star)-W(\widehat x)\le H_\delta+e,\)
while
\(\displaystyle W(x^\star)\ge W(\widehat x)\ge p-e=\ell.\)
If \(\ell>0\), division proves the asserted bound. If \(\ell\le0\), the bound \(1\) always holds. Hence \(B_\delta^{\mathrm{obs}}\) is also a valid PAE bound.
Computing this certificate requires evaluating the supplied envelopes. Their probabilistic coverage assumption alone does not specify evaluation costs or a rational representation.
Take one type, one good, and supply \(1\). For positive rationals \(\eta\) and \(a\) with \(0<a<\eta\), let
\(\displaystyle v(\varnothing)=0,\quad v(\{1\})=2\eta-a,\quad \widetilde v(\varnothing)=\eta,\quad \widetilde v(\{1\})=\eta-a.\)
The constant envelope \(\eta\) holds deterministically. Nevertheless, the predicted optimum allocates all mass to the empty bundle, whereas the true optimum allocates all mass to the good. Relative loss is \(1\).
This example is compatible with a supplied learner that ignores its training data. It also shows that the factor \(2\) in the uniform absolute loss bound is sharp: the absolute loss is \(2\eta-a\), approaching \(2\eta\) as \(a\) decreases to zero. Thus arbitrarily small absolute envelopes need not yield small relative loss without a suitable welfare scale.
Put \(N=2^m\) and \(n=\tau N\).
The support requirement ensures \(q\le N\). Before each of the first \(q\) draws, the distribution conditioned on unqueried bundles has positive remaining probability, so the prescribed sampling operation is well-defined.
The one-shot mechanism makes exactly
\(\displaystyle Q=\tau q\)
truthful value queries, and invokes the supplied learner once.
Let:
These costs must remain separate. In particular, sampling by repeated rejection from an unconditional distribution need not have a uniformly bounded cost when little unqueried probability remains.
Enumerate all type–bundle pairs, evaluate their predictions, and solve
\(\displaystyle \max_{x\ge0}\sum_{t,S}x_{t,S}\widetilde v_t(S)\)
subject to the given \(\tau\) mass equalities and \(m\) supply inequalities.
This is a rational linear program with \(n=\tau2^m\) variables. Its explicit constraint-matrix encoding has size polynomial in \(n,m,\tau\); its supplied and generated rational data are covered by \(L\). The polynomial-time theorem for exact rational linear programming applies because the coefficients are rational and the feasible set is nonempty and bounded. Negative objective coefficients present no difficulty.
Accordingly, an enumeration-based bound is
\(\displaystyle T\le C_{\mathrm{samp}}+C_{\mathrm{val}}+C_A+\sum_{t,S}C_{\mathrm{pred}}(t,S)+\operatorname{poly}(\tau2^m,m+\tau,L).\)
With uniform per-call upper bounds \(C_s,C_v,C_p\), this becomes
\(\displaystyle T\le\tau q(C_s+C_v)+C_A+\tau2^mC_p+2^{O(m)}\operatorname{poly}(m,\tau,L).\)
Here \(L\) includes generated rational data; it must not be interpreted as the length of an unprovided true-valuation table.
These optimization bounds include a standard fixed lexicographic optimal-vertex tie-breaking rule, implemented through polynomially many rational LP solves. The welfare guarantee holds for any fixed measurable tie-breaking rule, but the problem’s assumptions do not bound the computational cost of an arbitrary specified rule; that cost must be supplied separately.
There exists an optimal vertex with at most \(\tau+m\) positive coordinates.
To prove this, associate to coordinate \((t,S)\) its column of type indicators and good indicators in \(\mathbb R^{\tau+m}\). If a feasible point has more than \(\tau+m\) positive coordinates, those columns are linearly dependent. There is consequently a nonzero perturbation \(d\), supported on its positive coordinates, that preserves every type total and every good usage.
For sufficiently small \(\varepsilon>0\), both \(x+\varepsilon d\) and \(x-\varepsilon d\) remain nonnegative. They preserve all constraints, and their midpoint is \(x\). Thus \(x\) is not a vertex.
Vertex coordinates have polynomial rational bit length: after adding supply slacks, a basis has size \(\tau+m\) and integer entries of bounded magnitude. Cramer’s rule bounds its determinant bit length by \(O((\tau+m)\log(\tau+m))\), and the rational right-hand side has encoding length at most \(L\).
Sparse output therefore does not require enumerating the entire output allocation. It does not, however, make finding an optimum polynomial in the succinct input size.
There is no additional value-query dependence on \(\delta\): the mechanism still makes \(\tau q\) queries. Confidence enters through the supplied envelopes, for example at \(\alpha_t=\delta/\tau\). No sample-complexity relationship between \(q\) and \(\delta\), and no learner-training rate, follows from the stated coverage assumption.
If one additionally wants to compute a true optimum by enumeration, querying every previously unqueried type–bundle pair uses exactly
\(\displaystyle \tau(2^m-q)\)
additional value queries, followed by another rational LP solve. These are verification costs, not part of the one-shot mechanism.
For vertex choices of both optima, evaluating the allocation-dependent envelope numerator requires at most \(2(\tau+m)\) envelope evaluations once the allocations are known. Computing \(H_\delta\) by enumeration requires \(\tau2^m\) envelope evaluations.
For the supplied representation
\(\displaystyle \widetilde v_t(S)=b_t+\sum_{k=1}^{K_t}c_{tk}\kappa(S,Z_{tk}),\)
evaluating every prediction directly uses exactly
\(\displaystyle \sum_t2^mK_t=2^mK\)
kernel evaluations, followed by rational multiplication and addition.
If \(C_\kappa\) bounds one exact kernel evaluation, an upper bound is therefore
\(\displaystyle T_{\mathrm{SVR}}\le C_{\mathrm{samp}}+C_{\mathrm{val}}+C_A+2^mK C_\kappa+2^{O(m)}\operatorname{poly}(m,\tau,L,K).\)
The polynomial term includes rational arithmetic and exact LP optimization. More precisely, varying kernel-evaluation costs can be summed over the individual triples \((t,S,k)\).
For ordinary SVR whose support vectors come from the queried training bundles, \(K_t\le q\), hence \(K\le\tau q\). This relation should not be assumed for an arbitrary supplied expansion unless its support vectors are constrained accordingly.
Also, the intercept contribution is allocation-independent:
\(\displaystyle \sum_{t,S}x_{t,S}b_t=\sum_t\mu_tb_t.\)
Proven limitation. Exact predicted-welfare optimization is \(\mathrm{NP}\)-hard even with one type, unrestricted supplies, a fixed quadratic kernel, polynomially many support vectors, and zero prediction error.
Use the standard \(\mathrm{NP}\)-complete integer-weighted MAX CUT decision problem, established in [Karp’s original paper](https://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf).
Let its graph have vertices \(1,\ldots,m\), edges \(E\), and integer weights \(w_{ij}\). For a bundle indicator \(s\in\{0,1\}^m\), define
\(\displaystyle f(s)=\sum_{\{i,j\}\in E}w_{ij}(s_i+s_j-2s_is_j).\)
For binary \(s_i,s_j\), the parenthesis is \(1\) exactly when the edge crosses the cut. Thus \(f(s)\) is its cut weight.
Let
\(\displaystyle A_0=\sum_{\{i,j\}\in E}|w_{ij}|,\qquad B=1+A_0,\qquad d_i=\sum_{j:\{i,j\}\in E}w_{ij}.\)
Use the fixed kernel
\(\displaystyle \kappa(s,z)=\langle s,z\rangle^2.\)
It is rational-valued and positive semidefinite: the feature map \(\phi(s)=s\otimes s\) satisfies \(\langle\phi(s),\phi(z)\rangle=\langle s,z\rangle^2\).
Writing \(e_i\) for the singleton indicator gives
\(\displaystyle \kappa(s,e_i)=s_i,\qquad \kappa(s,e_i+e_j)=(s_i+s_j)^2.\)
Consequently,
\(\displaystyle f(s)=\sum_i2d_i\kappa(s,e_i)-\sum_{\{i,j\}\in E}w_{ij}\kappa(s,e_i+e_j).\)
This is the required signed-coefficient representation, with at most \(m+|E|\) nonzero terms. Add the empty-bundle term with coefficient
\(\displaystyle c_{\varnothing}=-3\sum_{\{i,j\}\in E}w_{ij}.\)
It contributes zero to predictions, since \(\kappa(s,0)=0\), and makes the total coefficient sum zero.
Now take one type with mass \(1\), supplies \(\beta_j=1\), and
\(\displaystyle v(s)=\widetilde v(s)=B+f(s).\)
These valuations are positive: \(f(s)\ge-A_0\), so \(v(s)\ge1\). Every probability distribution on bundles is feasible. Hence
\(\displaystyle \max_{x\in F}\widetilde W(x)=B+\max_{s\in\{0,1\}^m}f(s).\)
Thus computing optimal predicted welfare computes maximum cut weight. Fractional allocation provides no improvement: an average of cut weights cannot exceed their maximum. Every positive-mass bundle in an optimal allocation must itself attain that maximum.
All coefficients and support vectors have polynomial encoding length. The prediction error is zero, so zero envelopes satisfy the coverage hypothesis for every confidence level.
The construction can also arise from ordinary SVR training, rather than merely having an SVR-shaped expansion.
Query the empty bundle, every singleton, and every edge bundle. Let \(X\) have exactly this support and let \(q\) equal its size; without-replacement sampling then queries all these bundles.
Index them by \(Z_a\), let \(c_a\) be the coefficients above, and put
\(\displaystyle \bar w=\sum_ac_a\phi(Z_a),\qquad y_a=B+\langle\bar w,\phi(Z_a)\rangle.\)
Train SVR with zero insensitive width and penalty \(C>\max_a|c_a|\), minimizing
\(\displaystyle J(w,b)=\frac12\|w\|^2+C\sum_a|y_a-\langle w,\phi(Z_a)\rangle-b|.\)
The candidate \((\bar w,B)\) has zero training error. For any candidate \((w,b)\), let its residuals be \(r_a=y_a-\langle w,\phi(Z_a)\rangle-b\). Since \(\sum_ac_a=0\),
\(\displaystyle \sum_ac_ar_a=\|\bar w\|^2-\langle\bar w,w\rangle.\)
Also \(C\sum_a|r_a|\ge\sum_ac_ar_a\). Therefore,
\(\displaystyle J(w,b)\ge\frac12\|\bar w\|^2+\frac12\|w-\bar w\|^2.\)
The candidate \((\bar w,B)\) attains the lower bound. Every minimizer must have \(w=\bar w\); attaining its objective value then requires zero residuals and hence \(b=B\). Thus the trained predictions are exactly \(B+f\).
This proves hardness even for genuine SVR outputs with \(K\le q\) and polynomial-size training data. The enumeration bounds above are valid general upper bounds; a polynomial bound in the succinct parameters would imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The output resolves the task in substance. The welfare guarantees, query counts, enumeration bounds, and SVR hardness reduction are correct. I found no major error. Two minor clarifications are needed: precise statements of the standard LP results being invoked, and a distinction between succinct input length and the length of data generated by enumeration.
The discussion of independence is also accurate: the product-form confidence expression in the [2017 paper](https://people.bu.edu/blubin/papers/md/PAE-CA-ML2017AAAI.pdf) does not follow from the present marginal coverage assumptions. The comparison with the [later deterministic proposition](https://arxiv.org/html/1911.08042v4#S4.SS1.SSS1) is descriptive; the prover supplies its own mass-allocation argument rather than assuming that discrete proposition applies directly.
Minor issue: The write-up invokes exact polynomial-time rational LP optimization and existence of an optimal vertex without explicitly stating those standard results in theorem form. Their relevant hypotheses are satisfied here, so this is an expositional omission.
Minimum clarification: State the exact LP algorithm’s guarantee in terms of binary input length, and state the optimal-vertex existence theorem being used. Explicitly connect their hypotheses to the already established rationality, nonemptiness, and boundedness.
The evaluation accounting is correct:
These are direct-enumeration bounds; the output does not incorrectly claim that every implementation must perform that many kernel calls.
The training argument checks out:
Thus the hardness result applies to genuine minimizers of the specified SVR objective, rather than merely to arbitrary kernel expansions.
Minor issue: The final statement about polynomial time in “the succinct parameters” needs an explicit encoding qualification. Earlier, \(L\) includes generated rational data; exhaustive enumeration can make that quantity exponential. Polynomial time in an already expanded data length is compatible with the hardness result.
Minimum clarification: Specify that the hardness consequence concerns polynomial time in the supplied succinct description and polynomial-size training/model data, before exhaustive enumeration. Keep the generated-data interpretation of \(L\) for the enumeration upper bound.
This ambiguity does not undermine the reduction or its NP-hardness conclusion.
The answer establishes the requested guarantees and worst-case computational limitation. Both identified issues require clarification of standard results or encoding conventions, without new mathematics.
⟨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.