Source-linked AI summary
A Truthful-in-Expectation 2-Approximation for Pair-Specific Cascade Auctions in AI-Generated Content
Tao Jiang, Minbo Gao, Shaowei Cai
TL;DR
Generative content can place ads at multiple positions, where advertiser-position CTRs and sequential first-click stopping make allocation and order consequential. The paper gives a truthful-in-expectation mechanism that thins ads in a bid-independent lottery range and exactly optimizes expected welfare. It achieves a 2-approximation for arbitrary pair-specific CTRs, with the factor tight for that range.
Problem
For arbitrary pair-specific cascade CTRs, it remains open whether a polynomial-time monotone allocation can achieve a constant-factor welfare approximation.
Source: §1 · p. 1Method
The mechanism selects a matching and designated last ad, then thins earlier ads so each selected ad’s expected cascade CTR is a common fraction of its standalone CTR.
Source: §1 · p. 2Results
A polynomial-time mechanism for arbitrary public pair-specific CTRs and any displayed-ad limit is truthful and individually rational in expectation and achieves at least half of optimal cascade welfare.
Source: §1 · pp. 1–2Takeaways & Limitations
The factor-two loss is tight for the designated-last lottery range, but this does not establish a lower bound for truthful mechanisms generally.
Source: §1 · p. 2The guarantees assume public CTRs correctly describe user behavior and require control of display order without changing standalone CTRs.
Source: §9 · p. 8
Abstract
from arXiv · showhide
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.
1 Introduction
The paper addresses whether truthful, polynomial-time allocation can achieve a constant-factor welfare guarantee for arbitrary pair-specific cascade CTRs. It gives a truthful-in-expectation 2-approximation using a fixed lottery range and exact expected-welfare optimization.
1 Introduction
- Prior work leaves a gap: Balseiro et al. give a 4/(1 − ε)-approximation without established monotonicity and a monotone O(log m)-approximation, while earlier truthful constant-factor results require factorized CTRs.The open question is whether a polynomial-time monotone allocation can achieve a constant-factor guarantee for arbitrary pair-specific cascade CTRs.Source: §1 · p. 1
- For arbitrary public pair-specific CTRs and any displayed-ad limit, a polynomial-time mechanism is truthful and individually rational in expectation and achieves at least half of optimal cascade welfare.Source: §1 · p. 1
- The mechanism chooses a matching and designated last ad, then thins earlier ads so each selected advertiser’s expected cascade CTR is a common fraction of its standalone CTR.This gives each lottery a closed-form expected welfare, which the mechanism optimizes over a bid-independent range.Source: §1 · p. 2
- Exact optimization over that range makes the allocation monotone because the objective is delivered welfare, and standard payments yield truthfulness in expectation.For a fixed last ad, a linear program exactly optimizes the welfare ratio over matchings.Source: §1 · p. 2
- The lottery range loses at most a factor of 2 in welfare, with tightness applying only to that range; exact optimization of Balseiro et al.’s surrogate can still violate monotonicity [4].The paper also evaluates welfare, running time, and sensitivity to CTR errors on synthetic instances.Source: §1 · p. 2
1.1 Related Work
- For the arbitrary CTR matrix, APDC mechanisms do not apply; concurrent independent work also gives a truthful-in-expectation 2-approximation, using order-invariant thinning for fixed editorial order [25].This paper instead uses a designated-last lottery and gives a counterexample for exact optimization of the earlier restricted-welfare surrogate. Exact welfare optimization over bid-independent ranges and thinning approaches are related principles.Source: §1.1 · p. 2
2 Model
The model assigns advertisers to positions in an ordered display, with at most K ads. Advertisers have private per-click values, while public pair-specific standalone CTRs determine cascade click probabilities and expected welfare.
2 Model
- A matching assigns each advertiser and position at most once, and at most K ads may be displayed; advertisers have private nonnegative values per click.The feasible matching set includes the empty matching, and excluded advertiser-position pairs are removed from the graph.Source: §2 · p. 2
- The platform controls display order, while standalone CTRs remain unchanged by order; fixed-order layouts are outside this assumption.The mechanism uses control of order to place one ad last.Source: §2 · p. 2
- A standalone CTR is an ad’s click probability when shown alone, while a cascade CTR is its click probability in a realized ordered display.Expected cascade CTR is the allocation probability averaged over the mechanism’s display distribution.Source: §2 · p. 2
- Welfare is the sum of advertisers’ values times their cascade click probabilities, and monotonicity requires expected clicks not to decrease as an advertiser raises its bid.Advertisers are risk-neutral, have quasi-linear expected utility, and report only their per-click value.Source: §2 · p. 3
3 The Designated-Last Mechanism
The mechanism selects a matching and a designated last ad, then thins earlier ads so each selected ad has the same scaled expected cascade CTR. This gives an exact welfare objective for the lottery and a largest possible common scale under the fixed-designated-last constraint.
3 The Designated-Last Mechanism
- For a fixed matching, the best designated ad is one with the largest standalone CTR, so choosing it does not depend on bids.The welfare numerator is independent of the designated ad, while the denominator decreases as its CTR increases.Source: §3 · p. 3
3.1 An exact cascade lottery
- Non-designated ads are independently thinned using retention probabilities based on public CTRs and the selected matching and designated ad.The designated ad is always retained and placed last.Source: §3 · p. 3, §3.1 · p. 3, Figure 1 · p. 3
- Each selected ad has expected cascade CTR c(M,d) times its standalone CTR, giving the lottery an exact expected-welfare expression.The allocation is independent of the order of the matching’s non-designated ads.Source: §3.1 · pp. 3–4
- The common scale c(M,d) cannot be improved among lotteries that use the matching and place d after every other displayed ad whenever d appears.The bound applies to lotteries that give every matching edge the same scaled expected cascade CTR.Source: §3.1 · p. 4
4 Exact Optimization in Polynomial Time
The section maximizes the mechanism’s welfare objective by solving linear programs for candidate designated ads and recovering an optimal matching. For rational inputs, the maximizing pair, expected allocation, and expected payments are computable in deterministic polynomial time.
4 Exact Optimization in Polynomial Time
- A Charnes–Cooper transformation linearizes the welfare ratio, and a convex-combination argument makes the LP relaxation exact.The fractional LP objective is a convex combination of integral matching objectives.Source: §4 · p. 4
- For each designated edge, a maximum-weight matching computation recovers an optimal matching containing that edge.The matching uses at most K−1 additional edges and weights (v_e−r_d)p_e.Source: §4 · p. 4
- The maximizing matching and designated ad, objective value, expected allocation, and expected payments are computable in deterministic polynomial time for rational inputs.The algorithm solves an LP for each candidate designated edge and recovers a matching.Source: §4 · p. 4
- The random-prefix process belongs to the approximation proof, not Algorithm 1.Each edge’s inclusion probability in a random prefix equals its probability of being reached in the cascade.Source: Figure 2 · p. 5
- Sampling has expected polynomial running time, but the mechanism claims no worst-case bound for sampling.Exact rational Bernoulli draws use two fair bits in expectation; ties may be broken by any fixed rule.Source: §4 · pp. 4–5
5 A Factor-Two Approximation
A random-prefix decomposition bounds the welfare of any cascade display by twice the symmetric benchmark, which the mechanism’s expected welfare matches or exceeds. The factor-two guarantee is tight for the designated-last lottery range, though not a lower bound for truthful mechanisms generally.
5 A Factor-Two Approximation
- OPT(v) ≤ 2r0(v) ≤ 2Φ(v), giving Algorithm 1 a factor-two approximation to optimal cascade welfare.The proof represents any display’s welfare as expected standalone welfare of a random prefix and compares prefixes with the symmetric benchmark.Source: §5 · p. 5
- The symmetric ratio r0 is only a certificate; designating the last ad raises welfare on tested synthetic instances, but not in the worst case.For a fixed matching, nonincreasing value order maximizes cascade welfare, while Algorithm 1’s expected allocation does not depend on the order of non-designated ads.Source: §5 · p. 5
- For every δ > 0, some instance has OPT(v) > (2 − δ)Φ(v), so the factor two is tight for the designated-last range.This is not a lower bound for truthful mechanisms in general.Source: §5 · p. 5
- In the tightness instance, the optimal display puts the high-value, low-CTR ad first and then collects nearly one more welfare unit from low-value ads, while range lotteries scale selected ads uniformly.The contrast explains how the range can lose nearly a factor of two.Source: §5 · p. 5
6 Monotonicity and Payments
Exact maximization of delivered welfare over a bid-independent range yields monotone expected clicks and supports truthful, individually rational payments in expectation. The formal result gives a polynomial-time mechanism with at least half of optimal cascade welfare.
6 Monotonicity and Payments
- Exact maximization over a fixed, bid-independent lottery range makes the allocation monotone because the optimized objective equals delivered welfare.The range selects a matching and designated last ad; its lotteries depend on public CTRs and order.Source: §6 · p. 5
- For fixed bids of the other advertisers, raising advertiser i’s bid cannot lower its expected cascade CTR, even across matching changes, designated-edge changes, and ties.The argument requires exact maximization of delivered welfare.Source: §6 · pp. 5–6
- Pivot payments make truthful reporting maximize expected utility and satisfy 0 ≤ T_i(v) ≤ v_i q_i(v).Per-click billing can charge T_i(v)/q_i(v) when q_i(v) > 0; expected incentives are unchanged, but the mechanism is not universally truthful.Source: §6 · p. 6
- The mechanism achieves expected welfare at least 1/2 of OPT, with monotone expected cascade CTRs and truthfulness and individual rationality in expectation.These guarantees hold for rational pair-specific standalone CTRs, nonnegative rational per-click values, and any cardinality bound K.Source: §6 · p. 6
- The selected lottery, expected allocation, and expected payments are computable in deterministic polynomial time; sampling uses at most K independent Bernoulli draws.The draws have rational parameters of polynomial bit length, giving expected polynomial-time sampling with fair random bits.Source: §6 · p. 6
7 Why Exact Surrogate Optimization Is Not Enough
Exact optimization of the earlier restricted-welfare surrogate can still violate monotonicity: as advertiser 3’s bid rises, the unique surrogate optimum switches matchings and its cascade CTR falls. This example concerns that surrogate, not other approaches generally.
7 Why Exact Surrogate Optimization Is Not Enough
- Advertiser 3’s cascade CTR falls from 0.486 to 0.3825 as its bid rises from 0.4 to 0.6, while the unique restricted-welfare optimum switches from M_A to M_B.The value order and number of displayed ads remain unchanged, and all 34 feasible matchings are enumerated.Source: §7 · p. 6, Table 2 · p. 7
- The counterexample does not establish that other deterministic or surrogate-based approaches must fail, nor that the PTAS-based allocation is non-monotone.It motivates optimizing an objective equal to delivered welfare instead.Source: §7 · p. 7
8 A Descriptive Synthetic Comparison
Synthetic experiments compare DL with benchmarks on small instances, larger instances, and under CTR estimation error; they illustrate the theorems rather than statistically validating them. DL performs strongly in the tested settings, but its factor-two guarantee is conditional on accurate CTRs.
8.1 Small instances with exact optimum
- The small-instance comparison uses 12,000 seeded instances across six settings, with OPT computed by enumerating matchings displayed in value order.Figure 4 plots empirical CDFs of welfare/OPT, with a vertical line at DL’s 1/2 worst-case guarantee.Source: §8.1 · p. 7, Figure 4 · p. 7
- 85–93% of OPT on average across six synthetic settings, DL improves on Sym by 10–32 percentage points and weakly outperforms Bkt on all 12,000 sampled instances.RW achieves higher mean welfare but is a non-monotone oracle; Table 3 reports mean, 5th-percentile, and minimum welfare/OPT for 2,000 seeded instances per row.Source: §8.1 · p. 7, Table 3 · p. 8
8.2 Larger instances: running time and welfare brackets
- At the largest tested size, median allocation time is below one second and maximum time including payments is 5.32 s; DL has higher welfare than Bkt on all 160 sampled instances.OPT is not enumerated at these sizes, so welfare/OPT is reported as brackets.Source: §8.2 · p. 7, Table 4 · p. 8
8.3 Sensitivity to CTR estimation error
- At σ=0.5, DL loses about ten points of mean welfare, and its smallest observed true-welfare/OPT ratio is 0.26, below 1/2.The factor-two guarantee is relative to the CTR estimates; Bkt’s mean increase with noise mainly reflects fewer empty buckets in the low-CTR regime, not robustness to misestimation.Source: §8.3 · p. 8, Table 5 · p. 8
9 Limitations and Future Work
The guarantees rely on public CTRs that match user behavior and on control of display order without changing standalone CTRs. Incentive guarantees hold in expectation, and random thinning can leave selected ads undisplayed.
Limitations
- If estimated CTRs differ from actual behavior, the true-optimum welfare guarantee and monotonicity of actual click allocations may fail, so actual-click truthfulness in expectation is not guaranteed.The mechanism also requires control over display order without changing standalone CTRs; fixed-order layouts are outside the designated-last construction.Source: §9 · p. 8
- Random thinning may leave selected ads undisplayed, and incentive guarantees apply only in expectation, not to every realization.The assumed pipeline uses public CTRs for eligible advertiser–position pairs and renders retained ads with the designated ad last.Source: §9 · p. 8
Future Work
- Whether polynomial-time monotone mechanisms can improve on factor 2 remains open; the factor is tight only for this lottery range.Robust design under CTR misspecification, strategic creatives, and feedback between allocation and learning are also future directions.Source: §9 · p. 8
10 Reproducibility
The anonymous artifact provides the experimental code and data, plus a Lean 4 formalization that machine-checks key steps in the theoretical proofs.
Reproducibility
- The anonymous artifact includes code and data for all experiments and a Lean 4 formalization that machine-checks key proof steps.Source: §10 · p. 9
A Implementation Details
The implementation appendix describes exactness-preserving shortcuts for the experiments and gives an exact certificate for a counterexample involving the surrogate objective.
A Implementation Details
- Dinkelbach’s parametric method can implement Algorithm 1’s Step 1, but does not replace Theorem 4’s bound.The experimental shortcuts restrict the LP to edges with p_e ≤ p_d and skip d when a bound certifies r_d < r*, preserving the mathematical optimum.Source: A Implementation Details · p. 10
B Counterexample Certificate
- At u=2/5, exact enumeration gives M_A the optimum 4/5; at u=3/5, M_B is optimal at 91/100, certifying the counterexample’s switch in optimum.The runner-up values are 79/100 at u=2/5 and 9/10 at u=3/5.Source: B Counterexample Certificate · p. 10