| paper | d4-conf-sagt-2010-0020 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Yes. A truthful mechanism retaining the full factor \(\alpha\) is computable in \(\operatorname{poly}(m,\tau,L)\) time using one black-box call. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
Given item categories \(\mathcal J\), a public function \(f:2^{\mathcal J}\to\mathbb R\), a finite set \(V\) of private values, a rational mass distribution \(\mu\) on \(V\) with support size \(\tau\), and rational per-capita supplies \(q_j\), can a direct truthful mechanism be constructed from an \(\alpha\)-approximation to the aggregate welfare problem? Aggregate assignments \(x_{v,S}\) must satisfy \(\sum_S x_{v,S}=\mu_v\) and \(\sum_{v,S:j\in S}x_{v,S}=q_j\); the benchmark is \(\operatorname{OPT}(\mu)=\max_x\sum_{v,S}v f(S)x_{v,S}\). The mechanism must specify expected bundle values and payments for a tagged agent's reports, satisfy \(v z_v-p_v\ge v z_w-p_w\) for all \(v,w\in V\), achieve welfare at least \(\frac{3\alpha}{4ab}\operatorname{OPT}(\mu)\), and run in \(\operatorname{poly}(m,\tau,L)\) time for fixed \(a,b>1\).
Types are private value tiers \(v\in V\), each carrying mass \(\mu_v\); variables \(x_{v,S}\) assign mass to integral bundles \(S\), subject to per-capita inventory constraints. The objective is \(\sum_{v,S}v f(S)x_{v,S}\), while a tagged agent receives expected bundle value and payment from a report-indexed menu that must satisfy individual incentive constraints.
The finite theorem's range construction is indexed by \(n\), and the paper supplies neither a \(\tau,L\)-bounded construction nor a tagged-agent menu for the atomless model.
fatal: False
The mirror covers Theorem 1's conversion of welfare approximation into truthful mechanisms and its polynomial-time and quasi-polynomial-time guarantees. It leaves the warm-up analysis, structural lemmas, and greedy non-monotonicity example without separate mirrors; the paper gives no named hardness result to anchor.
My lead is the paper’s main theorem, cross-referenced as Theorem \(\ref{theorem1}\) in §5.2 and proved here. The supplied text suppresses its rendered numeral, so I refer to it as Theorem 1. It says: given a polynomial-time black-box algorithm that achieves an \(\alpha\)-approximation for welfare maximization in the paper’s single-parameter auction, one can construct a truthful mechanism running in \(O((\log_a n)^{\log_b n}\operatorname{poly}(m,n))\) time whose welfare is at least \(\frac{3\alpha}{4ab}\mathrm{OPT}(\mathbf v)\), for parameters \(a,b>1\). Its polynomial-time specialization gives an \(\Omega(\alpha/\log n)\) factor; its quasi-polynomial-time specialization gives a constant factor. The result is algorithmic, but conditional on the black box: it does not by itself put welfare maximization in P. The paper gives no numbered hardness theorem of its own to anchor instead.
Here is the continuous question I would put to a prover: Continuum Partially Public Auction Mechanism. There are \(m\) recurring item categories \(\mathcal J\), a common public valuation function \(f:2^{\mathcal J}\to\mathbb R\), and a finite set \(V\) of possible nonnegative private multipliers. The population is a unit mass with rational distribution \(\mu\) over \(V\), supported on \(\tau\) values. Category \(j\) has per-capita supply \(q_j\): in a discrete market with \(N\) advertisers there are \(Nq_j\) copies of that category. Each advertiser still receives an integral bundle \(S\subseteq\mathcal J\); fractional quantities describe only what share of a value cohort receives each bundle.
For a truthful population, let \(x_{v,S}\) be the mass of value-\(v\) advertisers assigned bundle \(S\). Feasibility requires \(\sum_S x_{v,S}=\mu_v\) for every \(v\), and \(\sum_{v,S:j\in S}x_{v,S}=q_j\) for every item category \(j\). The welfare benchmark is \(\mathrm{OPT}(\mu)=\max_x\sum_{v,S}v f(S)x_{v,S}\). The question is: given a black-box \(\alpha\)-approximation for this benchmark, can one construct a direct truthful mechanism for the environment—defined on all report profiles—that achieves at least \(\frac{3\alpha}{4ab}\mathrm{OPT}(\mu)\) and runs in time polynomial in \(m,\tau,L\) for fixed \(a,b>1\), where \(L\) is the bit length of the rational masses, values, and supplies? A solution must give the mechanism, prove its truthfulness for individual deviations, and prove the welfare and running-time bounds. Truthfulness can be stated through the usual single-parameter menu inequalities: an agent with true value \(v\) must prefer the expected bundle and payment associated with reporting \(v\) to those associated with any alternative report \(w\), holding the other reports fixed.
The regime is a large, repeated ad-buying market: many advertisers share one audience-coverage function and fall into relatively few value-per-unique-viewer tiers, while the available inventory scales with the campaign. Thus \(N\) can greatly exceed \(\tau\); rational masses describe the cohorts, and their assigned bundles remain indivisible. Scaling inventory with population is a co-modification that keeps per-capita welfare meaningful. The mirror retains the paper’s private scalar \(v_i\), public \(f\), welfare objective, and truthful-mechanism goal. That is a plausible continuation of the authors’ problem, not a claim that the original fixed-inventory auction already has a continuous population.
I expect this mechanism-construction question to be Class A, conditional on the promised welfare algorithm and on adapting the paper’s vector-fitting argument to mass profiles. The direction is a conjecture: Theorem 1 already gives the finite-population black-box transformation, and a finite-support mass distribution has a compact rational description. A key follow-up is whether the range construction can depend on \(\tau\) and \(L\), rather than on the number \(n\) of individual agents. For submodular \(f\), another question is whether the continuous representation improves on the paper’s polynomial-time \(\Omega(1/\log n)\) truthful guarantee.
The weakest point is the inventory scaling. The paper’s items are a fixed set of goods allocated among named bidders, whereas this mirror uses recurring categories whose stock grows with the market. If the authors regard that as changing the auction too much, the continuum mechanism question may not count as their problem. A second limit is that the paper’s theorem does not establish a runtime polynomial in \(\tau,L\), nor does it prove that discrete hardness dissolves. The case is specifically for a continuous-population analogue of its truthful approximation result.
The anchor is the main theorem in §5: it gives a computational mechanism-design result, conditional on a welfare approximation algorithm. So “there is no result to mirror” is not a viable objection.
With the paper’s original fixed inventory, however, a population limit is degenerate. If the \(m\) items remain single-use goods while the number of advertisers grows, their supply per person tends to zero. In a unit-mass model, no positive mass can receive any of them, so the welfare objective no longer captures the auction’s allocation problem. The proponent avoids this by scaling supply with the population. That is a coherent model for recurring inventory, but it turns the auction into one for replicated item categories. It is a substantial change to the environment, even if the authors might accept it as a related problem.
The deeper difficulty is preserving the theorem’s truthfulness question. Its mechanism responds to an individual bid: changing that bid changes the multiplier vector and can change the allocation and payment. In an atomless population, one person’s report has zero mass and leaves the aggregate distribution \(\mu\) unchanged. The proposed variables \(x_{v,S}\) describe allocations to positive-mass report cohorts; they do not specify what happens to an individual who deviates to a report with zero mass. Exact truthfulness therefore needs an additional report-indexed menu of bundles and payments. The finite theorem’s guarantee does not directly supply that menu: individual incentive constraints are sensitive to a \(1/N\) change that disappears when the empirical distribution converges to \(\mu\).
That makes the proposed mirror harder to identify as a continuization of this theorem, but it does not rule it out. A tagged agent facing a menu determined by the surrounding population is a plausible continuous mechanism model, and replicated inventory is plausible in recurring ad markets. Both repairs preserve a potentially worthwhile computational question. The negative case is therefore weak: it exposes a gap between aggregate welfare allocations and individual truthfulness, but I cannot honestly conclude that no worthwhile continuous mirror exists.
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.