| paper | d4-conf-aaai-2017-0887 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
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. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
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.
A repeated-market distribution over complete bidder valuation types, with rational mass per type and supplies proportional to population. Value queries train one shared learner per type; variables \(x_{t,S}\) assign type mass to integral bundles, and the objective maximizes predicted welfare under per-capita goods constraints.
The paper’s per-bundle prediction intervals do not themselves establish simultaneous control of allocations chosen from the same samples; the proposed guarantee assumes a stronger uniform envelope whose dependence on \(m\) and \(q\) remains unresolved.
fatal: False
The mirror covers Theorem 1’s welfare guarantee for learned valuations and welfare-maximizing allocation in a repeated-type market. It leaves the expressiveness results, PACO result, winner-determination formulation and complexity, payment rules, and incentives aside.
The strongest mirror I believe is the paper’s welfare guarantee for a large auction population with only a few repeated valuation types. Each type has a mass, and the mechanism learns one valuation model per type, then assigns mass to bundles to maximize predicted welfare. The bundles remain indivisible for each agent; only the population assigned to each bundle is continuous.
The anchor is Theorem 1, proved in this paper. It states that if bidder \(i\)’s generalized valuation has an \(\eta_{i,\alpha}(s)\) prediction interval, then \(M(A,X,q)\) is probably approximately efficient with bound
\[
\epsilon_\delta =
\frac{\eta_\delta(a_v^*)+\eta_\delta(a_{\tilde v}^*)}{V(a_v^*)},
\qquad
\eta_\delta(a)=\sum_i \eta_{i,\,1-\sqrt[n]{1-\delta}}(a_i).
\]
Here \(a_v^*\) maximizes true welfare, \(a_{\tilde v}^*\) maximizes predicted welfare, and the probability that the mechanism’s relative welfare loss is at least \(\epsilon_\delta\) is at most \(\delta\). This is a performance guarantee, not a numbered P-versus-NP result. The paper’s statement that ordinary winner determination is NP-hard is unnumbered, so I use it only as context.
I would pose the mirror as Mass PAE Winner Determination. An instance has \(m\) goods, a finite set \(T\) of \(\tau\) complete bidder types, rational masses \(\mu_t\) summing to one, and rational per-capita supplies \(\beta_j\) for each good \(j\). A type includes everything relevant to the paper’s problem, especially its valuation function over bundles. The actual type valuation profile is drawn from a specified distribution \(\mathcal V\). For each type \(t\), the mechanism samples \(q\) bundles from a specified query distribution \(X_t\), receives their values, and fits the paper’s chosen learning algorithm \(A\), producing \(\tilde v_t\).
A feasible answer is an aggregate allocation \(x_{t,S}\): the mass of type \(t\) receiving the integral bundle \(S\subseteq M\). It must satisfy \(\sum_S x_{t,S}=\mu_t\) for each type and \(\sum_{t,S:j\in S}x_{t,S}\le\beta_j\) for each good. The task is to output an allocation maximizing predicted welfare, \(\sum_{t,S}x_{t,S}\tilde v_t(S)\), and study its relative true-welfare loss against the best feasible allocation under the realized \(v_t\). Runtime should be measured in \(m,\tau,L,q\), and the number of SVR support vectors, where \(L\) includes the encodings of masses, supplies, query distributions, and valuation-model information. The mechanism uses \(\tau q\) value queries, rather than \(Nq\) when \(N\) agents fall into those \(\tau\) types.
The direct analogue of Theorem 1 uses mass-weighted error. Suppose that for each type \(t\), with probability at least \(1-\alpha\), its prediction error is bounded simultaneously over all bundles by \(\eta_{t,\alpha}(S)\). Taking \(\alpha=\delta/\tau\), define \(E_\delta(x)=\sum_{t,S}x_{t,S}\eta_{t,\delta/\tau}(S)\). Then the predicted-welfare maximizing allocation \(\hat x\) satisfies, with probability at least \(1-\delta\),
\[
W_v(x_v^*)-W_v(\hat x)\le E_\delta(x_v^*)+E_\delta(\hat x),
\]
where \(W_v(x)=\sum_{t,S}x_{t,S}v_t(S)\) and \(x_v^*\) is the true-welfare optimum. Thus its PAE bound is the right-hand side divided by \(W_v(x_v^*)\). The simultaneous-envelope condition makes the guarantee apply even though the allocation depends on the sampled predictions.
A plausible regime is a repeated procurement or spectrum market across many regions: there are many bidders but only a few recurring technology or operating templates, and each additional region brings a proportional supply of the same good categories. Then \(N\gg\tau\), and a value report for a bundle by one member of a type applies to the rest of that type. Supply scales with population, but each agent still receives a discrete bundle. This keeps the paper’s core question—whether limited value queries support an efficient allocation—while making the population itself the continuous object.
I expect the welfare-optimization part to remain hard, most likely because the combinatorics still live in choosing bundles from \(m\) goods. The aggregate problem has exponentially many type-bundle variables; its tractability depends on pricing over bundles for the learned SVR valuations. The paper gives an IP formulation for its discrete winner determination and says the ordinary problem is NP-hard, but neither fact proves hardness for this fractional mass version. Whether the relaxation permits a tractable pricing method, or whether hardness transfers through \(m\), is a central follow-up question.
The mirror covers the allocation and PAE claim, not payment rules, incentives, or the separate expressiveness results. It also opens the finite-to-continuous questions: when can a finite auction be approximated by these type masses, and how do query count and welfare error depend on \(\tau\) rather than \(N\)?
My weakest point is the regime assumption. A literal auction with a fixed stock of licenses and idiosyncratic bidders does not become this model just by taking \(N\) large: supplies must scale, and many bidders must genuinely share complete valuation types. The paper’s bidder-by-bidder proxies also become type-level shared learning here. I think authors would recognize the result as their welfare problem in a high-multiplicity market, since bundle queries, learned valuations, and welfare-maximizing allocation all remain central. But that recognition depends on accepting the replicated-market regime as a sensible setting for their problem.
I would vote against this as a ChoCo mirror, but the case is much stronger against the paper’s *anchor* than against the existence of a sensible continuous model.
The proponent’s best version is coherent: exact valuation functions define types, each type gets one shared learner, and per-capita supplies let a continuum of agents receive integral bundles. Under a simultaneous error envelope for each type, the mass PAE inequality follows by the usual approximate-argmax argument:
\[
W_v(x_v^*)-W_v(\hat x)\le E_\delta(x_v^*)+E_\delta(\hat x).
\]
So I would not reject it on the grounds that bidders cannot be grouped, or that bundle integrality rules out fractional mass assignments.
The problem is that Theorem 1 is not a computational result. It gives a welfare-loss bound conditional on prediction intervals; it gives no running time, query complexity, or algorithm for obtaining those intervals. Its mass analogue is essentially the same inequality with sums weighted by type masses. That can be a valid statement, but by itself it does not chart the complexity landscape this programme is meant to study.
There is also a gap between the paper’s stated prediction intervals and the proponent’s repaired version. The theorem’s proof applies the bounds to the true and predicted welfare optima, which depend on the valuations and training samples. Pointwise guarantees for each fixed bundle do not automatically cover those data-dependent choices. The proponent avoids that issue by assuming simultaneous error envelopes over all bundles. That is a stronger premise; establishing it for the paper’s learners could require substantial additional work, potentially with a costly dependence on the bundle space. The resulting question is about uniform learning guarantees, not a computational mirror supplied by Theorem 1.
The proposed mass allocation optimization does create a possible algorithmic project: optimize over type-bundle masses and study pricing over bundles. But that is a mirror of the paper’s winner-determination formulation, not of its named theorem. The paper gives an IP formulation and calls winner determination NP-hard, but presents no numbered complexity result for it. A project on typed, replicated combinatorial auctions may be worthwhile in its own right; the paper does not establish that it is a worthwhile *continuization* of one of its computational results.
The honest limit of this negative case is that the replicated-market regime is plausible. If many bidders truly share complete valuation functions and supplies scale with the population, the authors could recognize the mass model as their welfare problem. I cannot rule out a useful result there. My case against is that the sole named anchor yields a largely routine weighted PAE bound, while the more substantive complexity question is an unnumbered, separate winner-determination problem.
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.