| paper | d4-conf-sagt-2015-0022 |
| 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 solvable under the promised verifier, using at most \(s\lceil\varepsilon^{-2}\ln s\rceil\) verifier calls. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1
Given a finite item set \([m]\), a distribution \(\mu\) over buyer types with support size \(\tau\), per-capita item supplies \(b_j\), and a population scale \(N\) with \(N\mu_t,Nb_j\in\mathbb Z\), let \(x^*_{t,S}\) be a feasible per-capita fractional allocation of bundle \(S\) to type \(t\). Given an efficient \(\alpha\)-integrality-gap verifier for the aggregate count-allocation polytope, find a finite lottery over feasible integer count allocations \(y_{t,S}\) such that \(\mathbb E[y_{t,S}/N]=\frac{\alpha}{1+4\varepsilon}x^*_{t,S}\) for every type and bundle. The decomposition should use at most \(s\lceil\varepsilon^{-2}\ln s\rceil\) verifier calls, where \(s\) is the number of nonzero coordinates of \(Nx^*\).
Types are buyer valuation profiles with mass \(\mu_t\); each lottery outcome assigns whole bundles and uses integer counts \(y_{t,S}\), subject to type capacities \(N\mu_t\) and item capacities \(Nb_j\). The decision is a distribution over these feasible outcomes, with expected per-capita allocation equal to \(\frac{\alpha}{1+4\varepsilon}x^*\); there is no separate optimization objective.
The mirror covers Theorem 1's convex-decomposition step for a type-aggregated auction allocation. It does not extend the paper's approximate truthfulness, payment, or individual-rationality guarantees to a continuous population.
The strongest honest case is a narrow type mass allocation lottery mirror of Theorem 1, proved in this paper. The paper gives no numbered hardness result, so an algorithmic anchor is appropriate. Theorem 1 says: for any \(\varepsilon>0\), given a fractional point \(x^*\in\mathcal Q\) and an efficient \(\alpha\)-integrality-gap verifier for \(\mathcal Q_{\mathcal I}\), the authors find an exact convex decomposition
\[
\frac{\alpha}{1+4\varepsilon}x^*=\sum_j\lambda_jx^j.
\]
Its support has size at most \(s(1+\lceil\varepsilon^{-2}\ln s\rceil)\), and it makes at most \(s\lceil\varepsilon^{-2}\ln s\rceil\) verifier calls, where \(s\) is the number of nonzero coordinates of \(x^*\). The authors prove this result here; it replaces the Ellipsoid step in the allocation implementation used by the Lavi–Swamy mechanism. [Theorem 1 and its role in the mechanism](https://link.springer.com/article/10.1007/s00224-016-9704-2)
A plausible regime is a large combinatorial auction with many buyers sharing a small number \(\tau\) of valuation functions: for example, advertisers with recurring valuation templates for bundles of ad inventory. Let \(\mu_t\) be the rational mass of buyer type \(t\), with \(\sum_t\mu_t=1\), and let \(N\) clear the denominators of the masses and per capita item supplies. Then type \(t\) represents \(N\mu_t\) interchangeable buyers. The inventory scales with \(N\), so the mass model retains meaningful supply per capita as the market grows. A type records the valuation function used by the auction, along with any other attributes the allocation problem uses. The interesting regime is \(N\gg\tau\).
Here is the continuous problem I would hand to a prover:
Type Mass Lottery Implementation. The input is a finite item set \([m]\); a rational type distribution \(\mu\) with support \(\tau\); per capita item supplies \(b_j\); a nonnegative valuation \(v_t(S)\) for each type \(t\) and bundle \(S\subseteq[m]\); a feasible fractional allocation \(x^*\); an accuracy parameter \(\varepsilon\); and an \(\alpha\)-integrality-gap verifier for the type aggregated allocation polytope. The polytope has one variable \(x_{t,S}\) for each type and bundle, constraints \(\sum_S x_{t,S}\le N\mu_t\) and \(\sum_{t,S:j\in S}x_{t,S}\le Nb_j\). Its integer points are feasible allocations of whole bundles to buyers. The task is to output a finite lottery over those integer allocations whose expected type by bundle count vector is exactly \(\frac{\alpha}{1+4\varepsilon}x^*\). Each lottery outcome is a feasible allocation, and each buyer receives an integral bundle. Thus the society is represented by type masses, while fractional coordinates record averages across buyers.
For a basic fractional optimum in this configuration polytope, \(s\le \tau+m\). Theorem 1 therefore gives at most \(s\lceil\varepsilon^{-2}\ln s\rceil\) calls to the verifier, independent of the number \(N\) of represented buyers. In the verifier oracle model, this is a Class A result for the lottery implementation task. The expected welfare for any nonnegative valuation weights is scaled by the same factor. The type aggregated verifier itself remains a separate computational question; the theorem’s call bound does not settle its running time.
The authors could recognize this as their convex decomposition problem applied to repeated buyer types, with the type masses and scaled inventory making the population the continuous object. The mirror covers that allocation implementation stage. It does not claim that the paper’s full approximate truthfulness result carries over to a type mass mechanism: individual incentive constraints require extra care when reports are represented through a distribution.
That is the soft spot. The paper’s known combinatorial auction verifier has \(\alpha=1/\sqrt n\), so using it with \(N\) buyers makes the welfare factor shrink as \(N\) grows. A useful high multiplicity result needs a verifier whose approximation factor and running time remain controlled by \(m,\tau\), and the input bit length. Finding one—or showing why the bundle structure prevents one—is a central follow up question. Another is whether the resulting allocation lottery can be coupled with the paper’s payment rule while preserving individual truthfulness in the type mass setting.
The strongest objection is that the proposed mirror gets its population scaling from an oracle the paper never supplies. Theorem 1 bounds the number of integrality-gap-verifier calls in terms of the support size \(s\). For the type-aggregated auction, \(s\leq \tau+m\) at a basic feasible solution, so that call bound can be independent of \(N\). But the bound says nothing about the verifier’s running time or approximation factor. The paper’s cited combinatorial-auction guarantee has \(\alpha=1/\sqrt{n}\); applying it to \(N\) buyers makes the welfare factor deteriorate as the market grows. An aggregate verifier with controlled \(\alpha\) and running time in \(m,\tau,L\) would address the real computational bottleneck, but that is a further algorithmic problem. The proposed mirror supplies that verifier as an input, so its Class A claim is conditional.
A broader mirror of the mechanism faces a separate obstacle. Buyers’ valuation functions can define population types for welfare allocation, but the paper’s incentives concern each buyer’s unilateral report and use leave-one-out comparisons. In a nonatomic population, one buyer’s report does not change the distribution, so the individual externality vanishes. Giving a whole type mass the ability to misreport instead models a coalition acting as one player. Preserving individual deviations requires finite agents of mass \(1/N\), bringing back the dependence on \(N\). This makes it hard to carry the paper’s truthfulness result into a genuinely continuous population.
Those objections weaken the full mechanism mirror, but they do not dispose of the named anchor. The narrower lottery task is coherent: individual identities and incentive constraints are unnecessary to ask whether a feasible fractional type allocation can be implemented as a lottery over whole-bundle allocations with the stated expectation. A market with many buyers sharing valuation templates is plausible, and the theorem gives a type-support-sensitive bound on verifier calls for exactly that decomposition. The oracle condition limits what the theorem establishes, yet a conditional implementation result can still be useful.
So I cannot make the universal negative case stick. The strategic-mechanism mirror has a substantial population-limit problem, and the stated auction mirror lacks an end-to-end verifier. The standalone type-mass lottery remains a defensible mirror of Theorem 1; that is the weak point in the case against.
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.