PaperlayerView exact revision on arXiv

Source-linked AI summary

Truthful by Omission: Click Thinning for LLM-Native Advertising

Junhua Liu, Zhicheng Liang, Zejun Zhang, Langzhou He, Feng Qian

arXiv:2610.30999v1cs.GTcs.AIcs.DS

TL;DR

LLM-native advertising makes truthful allocation difficult because passage-specific click rates and first-click competition let bids alter which ads receive clicks. The paper uses randomized omission to make click service order-invariant and optimizes over a fixed range. Its truthful mechanism achieves at least half the freely ordered optimum, with a sharper best-possible factor under a click-probability bound.

  • Problem

    With passage-specific click rates and first-click competition, existing cascade mechanisms do not provide both a constant welfare approximation and monotonicity under fixed editorial order.

    Source: §1 · p. 1

  • Method

    Click thinning randomly omits selected ads to make their click service independent of position, then exactly optimizes welfare over the resulting bid-independent range.

    Source: §1 · p. 2, §1.1 · p. 2

  • Results

    At truthful reports, the mechanism is truthful in expectation and achieves at least OPT(v)/2 welfare; with cap K and probabilities at most δ, the factor sharpens to 2 − (1 − δ)^(K−1).

    Source: §1 · p. 2, §7 · p. 9

  • Takeaways & Limitations

    The factor 2 − (1 − δ)^(K−1) is best possible among order-preserving rules, so truthfulness and computational efficiency add no worst-case loss beyond fixing the order.

    Source: §7 · p. 9

    The guarantees assume standalone click probabilities are known and unaffected by omitting other ads.

    Source: §1 · p. 1

Abstract

from arXiv · show

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.

1 Introduction

LLM-native ads combine passage-specific click rates with a first-click cascade, making truthful allocation difficult when bids can change which ads precede others. The paper uses randomized omission to make click service order-invariant and gives truthful mechanisms with welfare guarantees under a fixed editorial order.

1.2 Related Work

  • Prior cascade mechanisms [3] offer either a 4/(1 − ε) approximation without monotonicity or a randomized monotone O(log m)-approximation, leaving a constant monotone guarantee open.The paper's mechanism answers this question under fixed editorial order.Source: §1 · p. 1

1 Introduction

  • The model assumes omission leaves the answer and other ads’ standalone click probabilities unchanged; the authors note that randomized omission can test this assumption.The answer and its editorial order are fixed before bidding.Source: §1 · p. 1
  • At truthful reports, the computationally efficient mechanism is truthful in expectation and achieves at least OPT(v)/2 welfare, even with a fixed editorial order.It charges only on clicks and keeps truthful utility nonnegative in every realization.Source: §1 · p. 2

1.1 Contributions and Techniques

  • Click thinning omits earlier ads more often so every matched ad receives service p_e/(1 + sum of matched probabilities), independent of its position.This makes welfare a linear-fractional matching objective that can be maximized exactly in polynomial time.Source: §1 · p. 2
  • For cap K and standalone probabilities at most δ, the odds mechanism guarantees a 2 − (1 − δ)^(K−1) approximation, and this is best possible for order-preserving rules.Without a probability bound, two is the optimal uniform factor.Source: §1.1 · p. 2

2 Model

The model assigns advertisers private values per click and contexts public standalone click probabilities, while fixing the editorial order before bids arrive. The platform chooses a capped advertiser-context matching and may randomly omit ads before rendering them in that order.

2 Model

  • A feasible allocation is a bipartite matching of at most K allowed advertiser-context pairs, with one private nonnegative per-click value per advertiser and public standalone probabilities.The editorial order, allowed pairs, probabilities, cap, and tie rule are fixed before reports arrive.Source: §2 · p. 3
  • Under the first-click cascade, each rendered ad is clicked with its standalone probability if reached, and the user stops at the first click.Omitting other ads is assumed not to change the answer or remaining standalone probabilities; empty contexts do not reset the cascade.Source: §2 · p. 3
  • The welfare benchmark OPT(v) is maximum expected advertiser click value over feasible matchings and all rendering orders.For a fixed matching, decreasing-value order is optimal [3, Lemma 5.2].Source: §2 · p. 3
  • In the two-advertiser example, the diagonal matching in value order yields OPT(v) = 187/50, while the second ad's actual service is 9/50 despite a standalone probability of 9/10.The example illustrates that actual service can differ substantially from standalone click probability.Source: §2 · p. 3

3 Click Thinning and the Basic Mechanism

Click thinning gives ads order-invariant click service, enabling exact welfare optimization over a bid-independent range. The resulting basic mechanism is truthful in expectation and guarantees at least half the freely ordered optimum, with exact polynomial-time selection and payment computation.

3.1 Exact Click Service

  • Click thinning retains selected ads independently before interaction and renders the retained subsequence in editorial order, giving each edge service q_e(M) = p_e/(1 + sum of matched probabilities).Every realization is a feasible subset of the matching; with two ads of probability 1/2, retention probabilities 1/2 and 2/3 give both service 1/4.Source: §3.1 · pp. 3–4

3.2 Truthfulness and Welfare Guarantees

  • The service identity makes reported click welfare a linear-fractional matching objective, and exact maximization over the fixed range makes each advertiser’s service nondecreasing in its bid.Click-contingent pivot payments implement truthfulness in expectation and charge only on clicks.Source: §3.2 · pp. 4–5
  • At truthful reports, the basic mechanism is feasible, truthful in expectation, individually rational in every realization, and achieves at least OPT(v)/2 welfare.It never transfers money to an advertiser or charges without an actual click; matching selection and payment parameters are computable in deterministic polynomial time.Source: §3.2 · p. 4
  • The welfare proof bounds the freely ordered optimum by twice the mechanism’s expected welfare using a threshold comparison on a feasible subset.The proof relies on downward feasibility and independence for the service identity and representation of the benchmark.Source: §3.2 · p. 4

3.3 Exact Computation

  • The linear-fractional objective over capped matchings has an exact polynomial-time solution, including recovery of a lexicographically least maximizing matching.The capped bipartite matching polytope is integral, and the ratio optimization is equivalent to a linear program.Source: §3.3 · p. 5

4 Characterizing and Optimizing Click Service

The section characterizes which click-service targets omission can realize and uses the targets attainable in every order to construct an exactly optimized, truthful mechanism. Its odds-based range achieves at least half of optimal welfare while preserving editorial order.

4.1 The Attainable Service Region

  • For a fixed matching, the section characterizes attainable click-probability vectors and shows that independent retention implements every attainable vector.The target is achieved by choosing each ad’s retention probability based on its reach probability and standalone click probability.Source: §4.1 · p. 5
  • Targets attainable in every order have a fractional representation using per-ad weights bounded by the odds p_e/(1 − p_e).Optimizing over sub-matchings permits raising weights to their odds bounds without losing welfare.Source: §4.1 · p. 6, §4.2 · p. 6

4.2 Optimal Order-Invariant Service

  • The odds range combines odds lotteries on matchings with unthinned certain-click singletons, then selects a welfare-maximizing entry and computes pivots over that same range.The range covers targets with total click probability one through certain-click singletons.Source: §4.2 · p. 6
  • The odds mechanism is truthful in expectation and achieves at least OPT(v)/2, with exact selection over its public range and at most one allocation plus K pivot optimizations.For K = 1, it achieves optimal welfare.Source: §4.2 · pp. 6–7
  • Aggregate order-invariant service can permit more than mixtures whose component matching targets are individually order-invariant: the example yields welfare 3/4 versus 2/3 for the best odds matching.Each component matching in the example has order-dependent edge services.Source: §4.2 · p. 7

5 The Sharp Cost of Editorial Order

The section bounds the welfare cost of preserving editorial order and shows that the bound is sharp under stated click-probability limits. It also contrasts thinning with direct rendering, which can lose monotonicity when bids change the selected matching.

5.1 Tight Dependence on Cap and Probability

  • For every K ≥ 1 and 0 < δ < 1, no order-preserving allocation rule achieves a better worst-case factor against OPT than the sharp cap-and-probability guarantee, even without incentive or computational restrictions.The bound is tight as a supremum on disjoint edges.Source: §5.1 · p. 7
  • The optimal uniform worst-case factor against the freely ordered optimum among all editorial-order-preserving rules is two.The lower-bound instance approaches a freely ordered welfare of two while fixed-order welfare remains one.Source: §5.1 · p. 7

5.2 Thinning versus Direct Rendering

  • Selecting an odds-range entry and rendering its matching without omission in decreasing value order achieves expected welfare at least OPT(v)/2, or the stronger sharp factor when p_e ≤ δ.This is a deterministic free-order allocation; its guarantee follows by comparing full value-ordered welfare with odds welfare.Source: §5.2 · pp. 7–8
  • Directly rendering the odds-selected matching in editorial order need not preserve monotone actual click service, so no payment rule makes that allocation rule truthful in expectation.In the example, raising A’s bid changes the selected pair and lowers A’s service from 4/5 to 14/25.Source: §5.2 · p. 8

6 Evaluation

The evaluation uses synthetic instances to separate welfare loss from editorial order and from the mechanism’s range, compare against bucket allocation, and measure computational cost. The reported comparisons show small mean order loss, range loss as the larger component in the sample, and faster odds timings at one tested setting than exact free-order optimization.

6 Evaluation

  • The study enumerates 144 four-advertiser, four-context instances across three structures, K ∈ {1, 2, 4}, and δ ∈ {0.1, 0.8}.The evaluation defines W as odds welfare, F as exact fixed-order optimum, and O as freely ordered OPT.Source: §6.1 · p. 8, §6 · p. 8

6.1 Order Loss and Range Loss

  • For multiple-ad instances, mean F/O is 0.970–0.992 and mean W/F is 0.908–0.970; the range restriction accounts for most mean loss in this sample.The minimum individual W/O is 0.6427.Source: §6.1 · p. 8, Table 1 · p. 8

6.2 Comparison with Bucket Allocation

  • At δ = 0.8, mean welfare/free-order OPT is 0.403 for the published bucket allocation, 0.441 for its nonempty-bucket variant, and 0.916 for odds.At δ = 0.1, the respective means are 0.247, 0.988, and 0.931; both bucket variants allow reordering, while odds preserves editorial order.Source: §6.2 · p. 8

6.3 Computational Cost

  • At m = 12 and K = 4, median allocation/pivot times are 747/2831 ms for DP and 24/112 ms for odds.DP-VCG attains the freely ordered optimum, whereas odds preserves editorial order.Source: §6.3 · p. 8

7 Conclusion

The conclusion presents click thinning as a way to preserve editorial order while obtaining truthful, efficient allocation. The appendix also describes exact optimization and gives an example certifying an optimal matching.

7 Conclusion

  • The mechanism turns implemented click welfare into a linear-fractional matching objective optimized exactly over a bid-independent range.The conclusion states that it has monotone click service.Source: §7 · pp. 8–9
  • Table 2 compares rules by mean welfare relative to free-order OPT; all preserve editorial order, while Raw and Stand. lack incentive guarantees.Source: Table 2 · p. 9
  • The mechanism attains at least half the freely ordered optimum, and the sharper factor 2 − (1 − δ)^(K−1) is best possible for order-preserving rules.The conclusion says truthfulness and computational efficiency add no further worst-case loss.Source: §7 · p. 9

A Exact Computation and Sampling

  • The exact optimizer uses repeated linear-optimization queries to recover a lexicographically least ratio-optimal allocation in polynomially many queries.Coordinate restrictions preserve an integral optimum; the queries are weighted-matching optimizations or exact LPs, depending on the setting.Source: A Exact Computation and Sampling · p. 9
  • For the example with weights p, bids (4, 3), and ratio 59/27, the diagonal matching is certified optimal over all feasible matchings.Its diagonal coefficient sum is 59/27, while the off-diagonal sum is 23/27 and every singleton coefficient is at most 59/27.Source: A Exact Computation and Sampling · p. 9

A.1 Rational Encoding and Exact Sampling

The appendix bounds the rational encoding of mechanism quantities and describes exact rational-coin sampling. It also contrasts thinning with related constructions for contention and cascade reach.

A.1 Rational Encoding and Exact Sampling

  • Rational inputs yield polynomial-bit retention probabilities, services, pivot values, expected payments, and charges.The passage states that charges satisfy c_i ≤ b_i, including when the service probability is small.Source: §A.1 · pp. 9–10
  • For two half-probability ads, unequal retention probabilities of 1/2 and 2/3 yield equal click service in the thinning example.Source: Table 3 · p. 10
  • Exact rational-coin sampling by rejection has polynomial expected bit use and time, but no deterministic bit bound for arbitrary rational coins.Acceptance probability exceeds 1/2 and termination is almost sure.Source: §A.1 · p. 10

B Comparison with Related Constructions

  • Unlike random-order contention resolution, thinning addresses cascade reach for an already feasible fixed capped matching.Showing both ads halves the second ad’s click probability to 1/4, although the matching is feasible.Source: B Comparison with Related Constructions · p. 10
  • An empty context does not reset attention: two half-probability ads separated by one still have total first-click probability 3/4, not one.The related reset model restores attention through empty slots.Source: B Comparison with Related Constructions · p. 10

C.1 Public Weights and Welfare Monotonicity

The appendix extends welfare and incentive results to public weight tables and broader feasibility families, while identifying settings where complexity or feasibility is constrained.

C.1 Public Weights and Welfare Monotonicity

  • For public weights satisfying the stated bounds, retention realizes service w_e/(1 + Σ w_f), and the factor-two welfare bound continues to hold.The exact computation and incentive arguments are unchanged.Source: §C.1 · p. 10
  • The optimized ratio objective is coordinatewise nondecreasing in public weights, and the coordinatewise maximum of finitely many admissible tables remains admissible and weakly improves optimized welfare.Source: §C.1 · p. 10

C.2 Augmenting the Public Range

  • Exact fixed-order optimization with pivots is polynomial for fixed K, but its complexity for general contexts is left open.For pairwise disjoint edges, a dynamic program computes fixed-order optimum in O(mK) arithmetic operations.Source: §C.2 · p. 10
  • A public list of unthinned renderings can augment the odds range while preserving truthfulness and realized individual rationality; for two unit-valued half-probability edges, welfare rises from 2/3 to 3/4.Each allocation or pivot call adds O(LK) arithmetic operations after preprocessing.Source: §C.2 · p. 10

C.3 Downward-Closed Feasibility Constraints

  • The factor-two truthful mechanism extends to finite downward-closed families with at most one edge per advertiser, given exact optimization over that family.Polynomial-time computation additionally requires a polynomial-size integral polyhedral description and exact LP optimization.Source: §C.3 · p. 11
  • Without downward closure, omission can violate feasibility under an exactly-K requirement: even for K=1, thinning may produce an empty rendering.Source: §C.3 · p. 11

D The Running Example

The running example traces the mechanism’s matching choices, click services, and payments as one advertiser’s report changes. The experimental appendix specifies evaluation settings and reports tight-family checks.

D The Running Example

  • The selected diagonal matching yields welfare 59/27, about 58.4% of the freely ordered optimum 187/50.Its click services are 8/27 for A and 1/3 for B.Source: D The Running Example · p. 11
  • At truthful bids, expected payments are 8/19 for A and 16/27 for B, with click charges 27/19 and 16/9, respectively.Only the advertiser receiving the click pays.Source: D The Running Example · p. 11
  • As A’s report x varies, matching-welfare lines form an upper envelope with intersections at 27/19 and 27/4.Table 4 varies A’s report while holding B’s bid at 3 and A’s value at 4.Source: D The Running Example · p. 11, Table 4 · p. 11
  • A’s truthful report lies in the diagonal interval, where utility is constant; a sufficiently high report raises service from 8/27 to 4/9 but reduces true utility from 392/513 to 61/171.The expected payment rises from 8/19 to 27/19.Source: D The Running Example · p. 11

E Experimental Details and Additional Results

  • The experiments use uniform values from {1/4, 1, 4, 16}, increasing context-index editorial order, and separable or contextual click probabilities.The largest sampled probability may be below δ.Source: E Experimental Details and Additional… · p. 11
  • In the tight-family checks, odds welfare is one in both orientations, while augmentation attains fixed-order OPT.The checks use K ∈ {2, 3, 4}, δ ∈ {0.1, 0.5, 0.8}, and ε ∈ {δ/10, δ/100}.Source: E Experimental Details and Additional… · p. 11

E.1 Implementation and Welfare Certificates

The appendices certify welfare and compare the odds mechanism with free-order DP-VCG, report welfare across instance families, and describe a subset-state dynamic program for free-order OPT.

E.1 Implementation and Welfare Certificates

  • Across six (n, density) groups, minimum certified W/U ranges from 0.722 to 0.938; exact rational dual checks make the welfare upper bound conservative.At n=128, median allocation times are 7.9 ms at density 0.25 and 22.3 ms at density one.Source: §E.1 · p. 12

E.2 Runtime versus Free-Order DP-VCG

  • Across 24 low-probability inputs, mean W/O is 0.958, its minimum is 0.938, and every instance satisfies bound (14).The comparison uses identical inputs and exact rational arithmetic for odds and free-order DP-VCG.Source: §E.2 · p. 12

E.3 Welfare across Instance Families

  • For contextual inputs, odds attains 0.952 versus fixed-order OPT’s 0.964; at δ=0.8 and K=4, standalone-weight welfare ratios are 0.872, 0.280, and 0.775.The standalone-weight ratios correspond respectively to separable, contextual, and bottleneck inputs.Source: §E.3 · p. 12
  • Across 96 instances, median W/F is 0.951 (interquartile range 0.909–0.982), and the single-matching augmentation has median paired gain zero.Its mean paired gain is 0.0165 and maximum is 0.1203.Source: §E.3 · p. 12

F Dynamic Program for Free-Order OPT

  • The free-order DP chooses whether to omit each advertiser or assign an available context, updating suffix welfare by the probability the earlier ad is not clicked.It recovers a matching and rendering order; its subset-state dependence is exponential when both m and K grow, though it is polynomial for fixed K and fixed-parameter tractable in m.Source: F Dynamic Program for Free-Order OPT · p. 12
  • For each positive-service winner, the free-order VCG baseline reruns the DP with that bidder’s bid zero and divides the pivot by actual click service.Other bidders pay zero.Source: F Dynamic Program for Free-Order OPT · p. 12

G Robustness to Calibration Error

Calibration error bounds the mechanism’s welfare relative to the true-probability optimum, while the result depends on a uniform error bound between estimated and actual click probabilities.

G Robustness to Calibration Error

  • The calibration guarantee assumes each actual click probability differs from its estimate by at most ε, and truthful realized individual rationality still holds.The proof couples the two models and bounds the probability of differing first clicks by Δ.Source: G Robustness to Calibration Error · pp. 12–13
  • With maximum probability error ε, welfare satisfies W_p ≥ OPT_p/2 − 3VΔ/2, where Δ = min{1, Kε}.The result assumes values and allowed reports lie in [0,V].Source: G Robustness to Calibration Error · pp. 12–13
  • In the two-ad example, bidder B gains 2/75 in expected utility by reporting three instead of truthfully reporting 3/2.The example uses estimated probabilities 1/2 and actual probabilities 4/5 for both ads.Source: G Robustness to Calibration Error · p. 13

Related papers

Loading 2610.30999v1…