A Truthful-in-Expectation 2-Approximation for Pair-Specific Cascade Auctions in AI-Generated Content
Tao Jiang, Minbo Gao, Shaowei Cai
cs.GT
Oct 25, 2026 · v1
TL;DR
An anonymous artifact includes a Lean 4 formalization that machine-checks key steps of the mechanism's theoretical proofs.
Abstract
Generative AI interfaces can insert sponsored content at multiple points in an answer, where click-through rates (CTRs) depend on the advertiser-position pair. Under the cascade model, users read ads sequentially and stop after their first click, so both ad assignment and display order affect welfare. For arbitrary pair-specific CTRs, Balseiro et al. (WWW 2026) gave a $4/(1-\varepsilon)$-approximation whose monotonicity has not been established, and a monotone $O(\log m)$-approximation for $m$ candidate positions. Earlier truthful constant-factor mechanisms require factorized CTR models and do not apply. Whether monotonicity is compatible with a constant-factor approximation in this general setting was left open by that work. We give a polynomial-time mechanism for arbitrary pair-specific CTRs and any limit on displayed ads that is truthful and individually rational in expectation and achieves a 2-approximation to optimal cascade welfare. Our mechanism selects an advertiser-position matching and a designated last ad, then randomly thins earlier ads so that each selected ad's expected cascade CTR is the same fraction of its standalone CTR. This yields an exact closed-form expression for expected welfare, which we maximize over a bid-independent lottery range using linear programming. Exact optimization ensures monotonicity, while a random-prefix decomposition proves the factor-two guarantee, which is tight for this range. We also show that exactly optimizing the previous welfare surrogate can violate monotonicity, and evaluate welfare and running time on synthetic instances.
Problem
In generative-AI ad auctions under the cascade model with arbitrary advertiser-position CTRs, no known mechanism is both truthful and constant-factor approximate. Prior work achieved either a 4/(1-ε) approximation without established monotonicity or a monotone O(log m) approximation.
Approach
The mechanism picks an advertiser-position matching and a designated last ad, then randomly thins the earlier ads. Each selected ad's expected cascade CTR is then the same fraction of its standalone CTR, which gives a closed-form expected welfare. This welfare is maximized exactly over a bid-independent lottery range using a Charnes–Cooper linearized LP over the integral matching polytope. A random-prefix decomposition proves the approximation bound, and key proof steps are machine-checked in Lean 4.
Results
The mechanism runs in polynomial time, is truthful and individually rational in expectation, and achieves a 2-approximation to optimal cascade welfare, which is tight for this lottery range. A counterexample shows that exactly optimizing the earlier restricted-welfare surrogate is not monotone. Synthetic experiments compare welfare and running time against prior methods.
| Work | Incentive guarantee | Factor |
|---|
| Gatti–Rocco 2013 (factorized) | monotone; TIE | 4/(1-ε) |
| Farina–Gatti 2017 (equal prominences) | MIR; DSIC | 2 |
| Balseiro et al. 2026 (restricted welfare) | not established | 4/(1-ε) |
| Balseiro et al. 2026 (CTR buckets) | monotone | O(log m) |
| This work | TIE; IR in expectation | 2 |
Comparison of incentive guarantees and approximation factors