| paper | Truthful Auctions for Automated Bidding in Online Advertising |
| authors | Yidan Xing, Zhilin Zhang, Zhenzhe Zheng, Chuan Yu, Jian Xu, Fan Wu, Guihai Chen |
| venue | IJCAI 2023 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The opponent wins the decisive gate: none of Theorems 3.1–3.8 or 4.1 asserts a complexity, algorithmic, approximation, or parameterized result. The cohort formulations are plausible high-multiplicity extensions, but the stated mass variables do not preserve the report-contingent allocations and bundle structure needed for \(\mathrm{DSIC}\). A repaired cohort-level mechanism-design problem could be worthwhile, but it cannot make this paper computational under the required rule.
fails bit a — no named computational result to mirror
The proposed \(a_{t,j}\) aggregates do not determine report-contingent allocations or per-advertiser bundles needed to test \(\mathrm{DSIC}\) and compute critical-\(\mathrm{ROI}\) payments; repairing this requires a marked-agent mechanism and richer bundle structure.
fatal: False
The proposed mirror would cover the truthful-allocation characterization, the \(g(B)\) structural map, and rank-score execution, while leaving the experiments and informal runtime remarks aside; none is a qualifying computational result.
The strict caveat comes first: this paper contains no numbered theorem asserting NP-hardness, membership in \( \mathrm{P} \), FPT, or another standard complexity classification. Theorems 3.1–3.8 and Theorem 4.1 are truthfulness and structural-characterization results; Algorithm 1’s runtime claim is unnumbered. Thus, under a complexity-only anchor rule, there is no qualifying anchor. If a named constructive mechanism theorem counts, the strongest positive case is the following.
Take a recurring automated-advertising market with many exchangeable advertisers. A complete type is \(t=(q,B,R)\), where \(q\) is a public advertiser class containing its value profile \(v_{qj}\) over a finite set of impression classes \(j\), while \(B\) and \(R\) are the private budget and ROI constraints. Let \( \mu_t \) be the fraction of advertisers of type \(t\), and let \( \sigma_j \) be the number of impression opportunities of class \(j\) per unit population. The scaling is joint: with \(N\) advertisers there are \(N\mu_t\) advertisers of type \(t\) and \(N\sigma_j\) impressions of class \(j\). This is plausible for recurring cohorts of small advertisers using the same campaign templates, valuation models, and budget/ROI tiers. If every advertiser has an idiosyncratic value vector, this compression fails; that is the main regime restriction.
My lead anchor is the paper’s Theorem 3.5, proved by the authors here, with its detailed proof deferred to the full version. It gives an if-and-only-if characterization of feasible truthful allocation rules. The corresponding problem is:
Truthful Mass Auto-Bidding\(_\infty\). Given rational \( \mu \), impression supplies \( \sigma_j \), and public values \(v_{qj}\), choose per-capita allocations \(a_{t,j}\ge 0\) satisfying \( \sum_t\mu_t a_{t,j}\le \sigma_j \). Define the cumulative value of type \(t=(q,B,R)\) by \(V_t=\sum_j v_{qj}a_{t,j}\). Require, for every public class \(q\), that \(V_q(B,R)\) obey the finite-grid version of Theorem 3.5: it is non-decreasing in \(B\), non-increasing in \(R\), and any upward jump in the budget direction satisfies \(V_q(B,R)\ge BR\), while any upward jump caused by lowering the reported ROI satisfies \(V_q(B,R)\le BR\). Set the per-advertiser payment to \( \pi_t=\min(V_t/R,B) \). Maximize aggregate revenue \( \sum_t\mu_t\pi_t \), and output the allocation and payments, or report infeasibility.
This is recognizably the paper’s problem: the same private constraints, public values, cumulative allocation across many impressions, IR, DSIC, and revenue objective remain intact. The only continuization is replacing repeated advertiser identities and repeated impressions by their type and supply masses. Rational solutions can be realized by clearing denominators and creating finitely many identical advertiser and impression clones.
I would expect the explicitly listed finite-grid version to be Class A, but this is a conjecture for the mirror, not a theorem in the paper. Theorem 3.5 and Corollary 3.8, also proved here, reduce the two-dimensional cumulative-value surface to a one-dimensional non-decreasing function \(g_q(B)\), with \(g_q(0)=0\), via the paper’s map \(m\). On a finite grid this suggests a monotone optimization or configuration-LP formulation. The unrestricted version—with continuous \(B,R\), succinct value profiles, or an implicit impression space—could instead produce continuum-specific hardness.
A second, genuinely independent mirror uses Theorem 4.1, proved in this paper. It states that Algorithm 1 is truthful whenever the predetermined rank-score functions \(f_{qj}(R)\) are non-increasing. Define Rank-Score Auction Execution/Design\(_\infty\) by giving each impression class \(j\) to the highest-mass types according to \(v_{qj}f_{qj}(R)\), splitting boundary mass when necessary, and then applying the paper’s critical-ROI construction to remove marginal impression mass and set payments \( \pi_t=\min(V_t/R,B) \). The computational question is to compute the resulting type-mass allocation and revenue; or, in the design version, to choose a finite rational monotone score table \(f\) maximizing \( \sum_t\mu_t\pi_t \).
For fixed score functions, I expect this execution problem to be Class A: score types can be sorted, impression masses scanned, critical ROI thresholds computed, and boundary mass split. Optimizing over unrestricted score functions is a more interesting open problem, potentially Class A under finite parametrization but possibly Class C in a succinct representation. This anchor covers Algorithm 1 and Theorem 4.1, not the paper’s experimental \(90\%\)-of-optimum claims or its learning-based advertising motivation.
The weakest point is that the paper’s value matrix \(v_{i,j}\) may be genuinely individual-specific. Including the entire value profile in \(q\) is formally correct, but can make \( |\mathcal Q| \) almost as large as the advertiser population, destroying the computational benefit. The proposed recurring-campaign regime is plausible, but it is an extension of the paper’s formal model rather than something demonstrated empirically in the paper. A second open issue is coalition truthfulness: individual DSIC survives the mirror, but a positive-mass bloc can change the market cutoff, which the paper does not analyze.
The further questions are whether finite-grid Truthful Mass Auto-Bidding\(_\infty\) has a polynomial algorithm, what rounding guarantees connect it to finite clone markets, whether score-function optimization is Class A or Class C, and how much of the theory survives when advertiser values are represented succinctly rather than by a small number of public value classes.
The decisive objection is upstream: this paper has no qualifying computational anchor. Theorems 3.1–3.8 characterize truthfulness and feasible allocation functions; none gives a complexity classification, an algorithmic optimization theorem, or an approximation result. Theorem 4.1 proves truthfulness of Algorithm 1. Its “low time complexity” is an informal implementation remark, not a named computational result. The experiments are empirical. Under ChoCo’s stated gate, the proposed continuous problems are therefore new problems invented by the proponent, not continuous mirrors of computational results in the paper.
Theorem 3.5 does not rescue the paper. Its object is a complete allocation rule over every named bidder, every report profile, and every fixed \(t_{-i}\). The relevant function is \(v_i((B,R),t_{-i})\), not a single aggregate surface \(V_q(B,R)\) at one population distribution. The proposed variables \(a_{t,j}\) describe one aggregate allocation, but do not specify what happens after one advertiser changes her report, nor whether the resulting family of allocations is jointly realizable by one direct mechanism. They therefore do not establish DSIC.
This is not repaired by calling the grid version a finite approximation. A finite grid replaces the paper’s continuous private domain with a new finite-type mechanism-design problem; arbitrary reports between grid points disappear. Conversely, retaining the full \(B,R\) domain requires representing a mechanism on an infinite report space, not merely optimizing finitely many masses. Corollary 3.8 only gives a bijective structural description of an abstract cumulative-value function. It neither supplies an optimization problem nor guarantees that every such \(g(B)\) can be realized by the available impression matrix, supply constraints, and allocations across all report profiles. The missing realizability problem is precisely the substantive mechanism-design problem the paper leaves open.
There is also a fundamental strategic discontinuity. If the mechanism sees only a type distribution, one advertiser has zero mass and cannot change aggregate cutoffs or allocations; individual truthfulness becomes vacuous. If a positive-mass cohort reports jointly, the deviation notion becomes coalition truthfulness, which is not the paper’s DSIC notion. If one retains unilateral deviations by rational clones, then one must track a distinguished clone in addition to the histogram. That can be a useful high-multiplicity implementation technique, but it is a compressed finite mechanism, not the mass-only continuous problem proposed here.
The recurring-cohort repair is legitimate as modelling, but it changes the status rather than solving the problem. Adding a public class \(q\) and requiring many advertisers to share the same value vector gives a sensible symmetric subclass. If almost all value vectors are idiosyncratic, however, then \(q\) is essentially an advertiser identity and the multiplicity gain disappears. If there are only a few \(q\)-classes, the resulting optimization is a new anonymous, cohort-level mechanism-design problem. It may be worthwhile independently, but it is not supplied by Theorem 3.5 or Corollary 3.8.
Theorem 4.1 is no stronger. For fixed \(f_{qj}\), executing the rank-score rule on repeated classes amounts to weighted sorting, scanning, and splitting boundary mass. That is a reasonable high-multiplicity implementation exercise, but it creates no meaningful computational mirror of the theorem: the theorem asserts truthfulness, not the complexity of execution. The more ambitious design version fares worse. The functions \(f_{qj}(R)\) are arbitrary monotone functions with no finite representation or input model. Restricting them to a rational table makes the problem finite, but also turns it into a newly specified score-function optimization problem absent from the paper.
Moreover, Algorithm 1’s critical ROI and payment are computed from each advertiser’s own bundle of impressions. Aggregate mass allocations do not generally determine the distribution of those bundles. Two decompositions with the same \(a_{t,j}\) can give identical average value while producing different individual cumulative values, critical ROIs, and payments. Preserving this information requires bundle distributions or clone-level structure; forcing fractional pooled bundles produces a different auction.
The honest limitation is that I cannot prove that no future continuous theory of anonymous auto-bidding could ever be valuable. The cohort model is plausible, and a clone-compressed analysis might yield useful results. But every attractive version falls into one of three categories: a routine weighted execution of the existing algorithm, a new fractional or coalition mechanism-design problem, or a finite high-multiplicity compression that must retain individual deviations. Since the paper supplies no named computational result to mirror, neither Theorem 3.5/Corollary 3.8 nor Theorem 4.1 provides a valid ChoCo anchor.
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.