Truthful by Omission: Click Thinning for LLM-Native Advertising
LLM-native advertising introduces new auction-design challenges because an ad’s click-through rate depends on its context passage and earlier ads steal clicks from later ones under a first-click cascade. This paper studies truthful mechanism design when the LLM answer and its passage order are fixed before bidding, showing that a constant-factor welfare approximation is compatible with truthfulness even under this editorial-order restriction. The authors propose click thinning—randomly omitting earlier ads to equalize click services across positions—which turns welfare maximization into a tractable linear-fractional matching problem and yields an elegant optimal tradeoff between approximation, truthfulness, and computational efficiency.
This paper delivers a crisp theoretical answer to an open question posed by Balseiro et al.: it gives the first computationally efficient, dominant-strategy truthful mechanism that achieves a constant approximation to the optimal welfare under a fixed editorial order. The click-thinning construction is conceptually clean, the approximation factor of $2-(1-\delta)^{K-1}$ is shown to be tight among all order-preserving rules, and the analysis carefully separates the loss due to fixing the order from the additional loss due to the mechanism’s range restriction. However, the practical relevance is bounded by the strong omission-invariance assumption and the small synthetic experiments, which leave open how the mechanism would fare with realistic click-probability distributions and passage-generation dynamics.
The strongest element is the click-thinning transformation itself, which replaces the combinatorial mess of cascade externalities with a simple order-invariant service formula $q_e(M) = p_e / (1 + \sum_{f \in M} p_f)$, making exact welfare maximization a linear-fractional matching problem solvable in polynomial time. The subsequent characterization of the full attainable service region (Theorem 4.2) and the proof that the improved factor $2-(1-\delta)^{K-1}$ is tight for every order-preserving rule (Theorem 5.1) are technically sophisticated and settle the approximation landscape cleanly.
The analysis rests heavily on omission invariance—the assumption that omitting an ad leaves the answer and the other standalone probabilities unchanged—which is plausible when ads are self-contained toggles but may fail if ad removal alters the text flow, user scroll depth, or passage salience. The empirical validation is limited to 144 enumerated instances with at most four advertisers and four contexts; although the authors decompose welfare loss into range and order components, the experiments are too small to assess robustness or sensitivity to calibration error in practice. Additionally, the model abstracts away answer quality, user-platform welfare, and revenue, all of which matter for a deployable system.
The theoretical evidence is rigorous: Lemma 3.1 derives the exact thinning retention probabilities, Theorem 3.2 proves truthfulness and the factor-two welfare guarantee, and Theorem 5.1 closes the gap with a tightness construction on disjoint edges. The related-work comparison with Balseiro et al. and Farina and Gatti is careful, noting exactly which modeling differences prevent prior constructions from transferring. The synthetic experiments support the claim that most welfare loss comes from restricting to order-invariant services rather than from fixing the editorial order itself, but the absence of larger-scale or real-data experiments limits the empirical support for the practical superiority over prior heuristics.
The paper provides deterministic polynomial-time algorithms and exact rational arithmetic procedures, and the proof that exact computation and fair-bit sampling run in polynomial time is self-contained. Nevertheless, no code repository or artifact link is provided, and the experiments are small enough that an independent reproduction would require re-implementing the prototype from scratch. The omission-invariance assumption is described as testable via randomized omission, yet no such empirical test or dataset is included, which leaves a gap between the theoretical model and empirical validation.
Generative AI assistants are becoming an advertising medium, embedding sponsored content in their answers. This setting departs from classical position auctions in two ways: an ad's click-through rate depends on the passage that hosts it, and because users stop at their first click, earlier ads take clicks from later ones. This competition for clicks makes truthfulness delicate: a higher bid can reshape the allocation and put a competitor ahead of the bidder, reducing the bidder's clicks. Existing mechanisms either attain a constant fraction of the optimal welfare (advertisers' total click value) but are not known to be truthful, or are truthful but their welfare guarantee degrades as the number of passages grows. We achieve both even when the answer and its editorial order are fixed before bidding. Assuming each ad's click-through rate when reached is known and unaffected by omitting other ads, we give a computationally efficient mechanism that is truthful in expectation and attains at least half the optimal welfare under free reordering. Our key idea, click thinning, omits ads at random, showing earlier ads less often so that each ad's overall click probability no longer depends on the order of the ads. Welfare maximization then reduces to a tractable matching problem, and solving it exactly with VCG-style payments makes truthful bidding optimal in expectation. Characterizing the click probabilities that omission can achieve sharpens the approximation factor from $2$ to $2-(1-\delta)^{K-1}$ when at most $K$ ads are shown and each click-through rate is at most $\delta$. This factor is the best possible for any order-preserving rule, even one that ignores incentives and computation, so truthfulness and computational efficiency incur no additional worst-case loss.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.