A Truthful-in-Expectation 2-Approximation for Pair-Specific Cascade Auctions in AI-Generated Content

概要

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.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
A Truthful-in-Expectation 2-Approximation for Pair-Specific Cascade Auctions in AI-Generated Content

# 概要
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…

# 原典
https://arxiv.org/abs/2610.34236

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。