Mechanism matches ads to spots doubling expected click value
A Truthful-in-Expectation 2-Approximation for Pair-Specific Cascade Auctions in AI-Generated Content
Computer Science and Game Theory
Summary
Sponsored ads can appear at different spots in AI-generated answers, and how well they work depends on both the ad and where it's shown. The authors solved a problem about fairly and efficiently choosing which ads to show and where, even when click rates depend on both ad and position in complicated ways. They created a method that guarantees advertisers are treated truthfully on average, and the overall value is at least half of the best possible. Their approach uses random selection and clever math to ensure fairness and good performance.
What this means in practice
- •For online advertising platform teams: Implement a truthful and efficient method to assign ads that optimizes expected clicks accounting for ad and position specifics in AI-generated content.
- •For e-commerce marketing teams: Optimize placement of sponsored content within AI product answers to maximize engagement by using double-approximation truthful auction mechanisms.
Authors
Tao Jiang, Minbo Gao, Shaowei Cai
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.