PaperlayerView exact revision on arXiv

Source-linked AI summary

A Factor-6 Truthful-in-Expectation Mechanism for Cascade Position Auctions

Qiuyu Chen, Baao Xie

arXiv:2610.33707v1cs.GTcs.DS

TL;DR

Cascade attention couples click-through rates across positions, while existing approaches had not combined constant-factor welfare approximation with monotonicity. This paper uses a reach-weighted relaxation and a randomized realization with uniformly scaled click coordinates to obtain both guarantees, along with truthfulness in expectation.

  • Problem

    For arbitrary public advertiser–position click probabilities, prior work separately achieved constant-factor welfare approximation and monotone O(log m) approximation, leaving their simultaneous achievement open.

    Source: §1 · p. 2

  • Method

    A randomized mechanism optimizes a reach-weighted relaxation and rounds its solution into feasible ordered allocations with each expected click rate uniformly scaled.

    Source: §10 · p. 14

  • Results

    Expected welfare is at least OPT(b)/6, each advertiser’s expected click-through rate is nondecreasing in its own bid, and exact nonnegative expected payments make truthful reporting dominant in expectation.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Exact control of expected click coordinates lets the same optimization support both welfare approximation and incentive-compatible payments despite preceding ads’ effects on later clicks.

    Source: §10 · p. 14

    Further work could seek sharper constants and extend the construction to heterogeneous display constraints or more general sequential attention models.

    Source: §10 · p. 14

Abstract

from arXiv · show

Position auctions require assigning advertisers to positions and determining their display order. Under cascade behavior, earlier clicks prevent users from reaching later placements, coupling the click probabilities of selected advertisements. Existing methods achieve constant-factor welfare approximation and monotone logarithmic-factor approximation separately, leaving open whether both guarantees can be attained simultaneously. The difficulty is that welfare-preserving rounding need not maintain the monotonicity of individual click-through rates required for truthful bidding. We resolve this problem by developing a polynomial-time randomized mechanism that achieves a factor-6 welfare approximation and truthfulness in expectation for arbitrary public advertiser-position click probabilities. The mechanism optimizes a reach-weighted linear relaxation and converts its solution into feasible ordered allocations through matching decomposition, probability-bounded grouping, and calibrated attenuation. This construction compensates for cascade dependence and ensures that each advertiser's expected click-through rate equals exactly one sixth of its fractional click coordinate. The resulting identity transfers the monotonicity of the fractional allocation to the implemented mechanism, enabling exact incentive-compatible payments while preserving the welfare guarantee. The allocation lottery and payments are computable in polynomial bit time, with exact sampling in expected polynomial time.

1 Introduction

Cascade position auctions couple advertisers’ click rates because earlier clicks can prevent users from reaching later ads. The paper gives a randomized mechanism that combines a factor-6 welfare approximation with truthfulness in expectation for arbitrary public advertiser–position click probabilities.

1 Introduction

  • Earlier clicks affect whether users reach later ads, so both the selected matching and its rendering order affect welfare and advertisers’ click-through rates.Source: §1 · pp. 1–2
  • Prior work achieved a constant-factor welfare approximation and, separately, an O(log m) approximation with a monotone allocation rule; combining constant welfare and monotonicity remained open.Welfare-preserving randomized rounding need not preserve monotonicity of actual expected click-through rates.Source: §1 · p. 2
  • Expected welfare is at least OPT(b)/6, while every realized allocation is an ordered matching of size at most K.The result covers every public rational click-probability matrix and every allowed capacity.Source: §1 · p. 2
  • Each advertiser’s expected click-through rate is nondecreasing in its own bid, and exact nonnegative expected payments make truthful reporting a dominant strategy in expectation.A per-click payment implementation also gives nonnegative utility for every realized click outcome under truthful reporting.Source: §1 · p. 2
  • Matching decomposition, probability-bounded grouping, and calibrated thinning make each advertiser’s expected click-through rate exactly one sixth of its fractional click coordinate.The mechanism and payments are computable in deterministic polynomial bit time, and the allocation lottery can be sampled exactly in expected polynomial bit time.Source: §1 · p. 2
  • The guarantee applies to arbitrary public click-probability matrices, including zero and unit entries, and to any allowed capacity with an unrestricted ordering benchmark.Source: §1 · p. 2

2 Related Work

The related work establishes separate foundations in cascade attention, truthful approximation, and other advertising externalities. This paper’s construction addresses the additional interaction between matching feasibility and sequential attention.

Sequential attention and position auctions

  • Balseiro et al. [5] study arbitrary advertiser–position click probabilities with endogenous display order, obtaining a 4/(1 −ε) welfare approximation and an O(log m) monotone approximation.The paper presents its factor-6 truthful mechanism as improving these bounds in the incentive-compatible setting.Source: §2 · p. 3

Truthful approximation and rounding

  • Under cascade attention, an advertiser’s actual click-through rate depends on retained earlier ads, unlike ordinary matching where assignment marginals directly control allocation.The construction uses probability-bounded grouping and independent retention so prefix factors telescope and every click coordinate is preserved at a common scale.Source: §2 · p. 3

Other advertising externalities

  • Other advertising settings study spatial interactions, heterogeneous ad sizes, and capacity constraints; this mechanism handles arbitrary advertiser–position probabilities alongside matching, cardinality, and sequential attention.Source: §2 · p. 3

3 Model and Preliminaries

The model has advertisers with private nonnegative values per click, public position-specific conditional click probabilities, and a capacity limit on displayed ads. A feasible allocation is an ordered matching, and randomized mechanisms are evaluated through expected click rates, payments, and truthful reporting.

3 Model and Preliminaries

  • Each advertiser has a private nonnegative value per click, while the platform knows public conditional click probabilities for advertiser–position pairs.The display capacity K is between zero and min(n, m).Source: §3 · p. 3
  • A feasible allocation is an ordered list of advertiser–position pairs with no repeated advertiser or position and length at most K.The displayed list is selected before users interact; under the cascade model, a click ends the sequential scan.Source: §3 · pp. 3–4
  • The platform may choose any rendering order for selected pairs, and the welfare benchmark includes every ordering.Source: §3 · p. 4
  • Truthfulness in expectation compares expected utility from truthful and alternative reports for every advertiser, value, report, and fixed vector of others’ reports.Computational results use binary-rational inputs; the stated expected-utility inequalities are proved for nonnegative rational values and bids.Source: §3 · p. 4
  • A public lexicographic convention fixes edge order and resolves ties; when K = 0, the mechanism outputs the empty allocation with zero payments.Source: §3 · p. 4

4 Overview of the Mechanism

The overview uses a public reach-weighted linear relaxation to upper-bound the best welfare over all orderings. It rounds a fractional solution into feasible ordered matchings while scaling every advertiser’s expected click coordinate uniformly, supporting both welfare and incentive guarantees.

4 Overview of the Mechanism

  • The relaxation’s linear optimum upper-bounds OPT(b), even when the benchmark may choose any rendering order.Its feasible arrays satisfy advertiser, position, cardinality, and total weighted-click-budget constraints.Source: §4 · p. 4
  • Matching decomposition expresses a fractional solution as a convex combination of matchings, then probability-bounded groups are sampled and independently thinned according to prefix click probabilities.The resulting cascade survival factors telescope, yielding a common scale for actual click coordinates.Source: §4 · p. 4
  • Sampling the lottery from a bid-selected LP maximizer gives a 1/6 welfare guarantee and monotone implemented expected click rates; scaled externality payments establish truthfulness in expectation.Source: §4 · pp. 4–5
  • Exact rational LP optimization, integral-flow decomposition, and fair-bit sampling provide polynomial bit-complexity guarantees.Source: §4 · p. 5

5 A Reach-Weighted Linear Relaxation

Section 5 formulates a reach-weighted linear benchmark for cascade welfare. Its optimum upper-bounds welfare over every feasible ordered matching.

5 A Reach-Weighted Linear Relaxation

  • The polytope imposes matching and cardinality feasibility plus an aggregate click-probability budget, and depends only on public probabilities and capacity.Its variables can represent reach probabilities for a deterministic allocation.Source: §5 · p. 5
  • The relaxation’s optimum V(b) upper-bounds OPT(b), because every feasible ordered matching has a representation in P preserving each advertiser’s click-through rate.The matching’s click-through rates equal its fractional click coordinates.Source: §5 · p. 5
  • Reach weighting yields a linear upper bound without restricting rendering order, even though standalone click probabilities need not sum to one.The reach-weighted sum always equals one.Source: §5 · p. 5

6 Capacity-Preserving Matching Decomposition

Section 6 decomposes rational points of the matching polytope into feasible matchings while preserving advertiser, position, and capacity constraints in every outcome.

6 Capacity-Preserving Matching Decomposition

  • The explicit rational decomposition preserves advertiser, position, and capacity constraints in every integral outcome.Its rational encoding has polynomial bit length, and the algorithm uses polynomial-size circulation tests and rational arithmetic.Source: §6 · pp. 6–7
  • Every rational x in Q admits a computable convex decomposition into at most d+n+m+2 matchings with positive rational weights.The decomposition and its coefficients are computable in deterministic polynomial bit time.Source: §6 · p. 6
  • An integral circulation network represents points of Q, and its integral feasible circulations correspond to matchings of cardinality at most K.The construction uses advertiser, position, and source/sink nodes with capacity K on the return arc.Source: §6 · p. 6

7 Exact Cascade Click-Rate Realization

Section 7 turns fractional allocations into feasible ordered-match lotteries with calibrated cascade click rates. Its coordinatewise identity yields an exact one-sixth scaling of each fractional click coordinate.

7 Exact Cascade Click-Rate Realization

  • The construction first splits each matching into bounded-probability groups, then applies calibrated independent thinning to implement a common click-rate scale for the randomized map R(x).For every matching Mt, next-fit partitioning satisfies Bt ≤ 2Tt + 1; an indexed group Ct,k is selected with probability λt/3.Source: §7 · p. 7, §7.1 · pp. 7–8

7.1 Probability-bounded groups

  • Next-fit partitions each matching into probability-bounded groups; the group-count bound makes the probability-group selection distribution well defined.Each selected group has total standalone click probability at most one.Source: §7.1 · pp. 7–8

7.2 Independent thinning

  • Independent thinning uses prefix click probabilities so cascade survival factors telescope, giving every retained edge conditional expected click probability pe/2.The calibrated thinning also yields feasible cascade allocations when decisions are made before clicks.Source: §7.2 · p. 9

7.3 The coordinatewise rounding identity

  • Each advertiser’s expected click-through rate equals exactly one sixth of its fractional click coordinate, combining group-selection probability xe/3 with conditional click probability pe/2.The resulting identity supplies the information used to derive incentives from linear optimization.Source: §7.3 · pp. 9–10

8 Welfare and Incentive Guarantees

The section connects the mechanism’s welfare and incentive guarantees through an exact click-rate identity: each advertiser’s expected click rate is one sixth of its fractional coordinate. It uses this relationship to establish monotonicity, truthful payments, and optimization over a bid-independent range of lottery distributions.

8 Welfare and Incentive Guarantees

  • Each advertiser’s expected click probability is nondecreasing in its own report because the fractional click coordinate is monotone and the realized rate equals that coordinate divided by 6.With equal bids, fixed tie-breaking selects the same point and lottery.Source: §8 · p. 10

8.1 Exact externality payments

  • Exact externality payments make truthful reporting a dominant strategy in expectation, and per-click charging gives nonnegative utility for every realized click outcome under truthful reporting.The payment scales the loss imposed on other advertisers in the relaxation by the allocation lottery’s factor.Source: §8.1 · p. 11

8.2 Optimization over a fixed lottery range

  • Each lottery’s expected welfare is the reported-bid-weighted sum of fractional click coordinates scaled by 1/6, and the mechanism selects an optimizer over the fixed lottery range.The range is bid-independent even though the displayed-list distribution may change with bids.Source: §8.2 · p. 12

9 Exact Computation and Bit Complexity

The section establishes exact polynomial-bit construction of the mechanism and its payments for binary-rational inputs, then gives an exact fair-bit sampler for its allocation lottery with expected polynomial running time.

9 Exact Computation and Bit Complexity

  • For binary-rational inputs, the optimizer, lottery description, expected payments, and per-click charges can all be computed exactly in deterministic polynomial bit time.The rational outputs have polynomial numerator and denominator bit lengths.Source: §9 · p. 12
  • The exact construction uses rational LP optimization, lexicographic tie-breaking, and an integral-circulation decomposition, with polynomially bounded descriptions for the resulting values and probabilities.The decomposition uses at most N steps and matching-finding calls on a polynomial-size network.Source: §9 · pp. 12–13

9.1 Exact sampling of the allocation lottery

  • The lottery can be sampled using independent fair bits with at most K + 1 rational-probability sampling operations, terminating almost surely in expected polynomial bit time.Rejection sampling avoids rounding the probabilities; each trial is accepted with probability greater than 1/2.Source: §9.1 · p. 13
  • Together, the results establish deterministic polynomial-time construction and expected polynomial-time exact sampling alongside the welfare and incentive guarantees.The proof combines the LP welfare bound, the 1/6 click-rate realization, and the two computation propositions.Source: §9.1 · p. 14

10 Conclusion and Discussion

The paper presents a polynomial-time factor-6 welfare approximation that is truthful in expectation for cascade position auctions with arbitrary public advertiser–position click probabilities. Its worked example illustrates how grouping and thinning yield equal-scale expected click rates despite cascade dependence.

10 Conclusion and Discussion

  • The mechanism achieves a factor-6 welfare approximation and truthfulness in expectation for cascade position auctions with arbitrary public advertiser–position click probabilities.It realizes fractional click coordinates at a common scale in actual ordered allocations.Source: §10 · p. 14
  • Matching decomposition enforces assignment feasibility, while probability-bounded grouping and calibrated thinning control click mass and equalize expected click-rate scale across placements.The construction separates assignment feasibility from sequential attention.Source: §10 · p. 14
  • Further work can seek sharper constants through more efficient grouping or alternative attenuation rules, and extend the analysis to other click-matrix structures and sequential-attention models.The discussion also names heterogeneous display constraints as a direction for future work.Source: §10 · p. 14

A A Worked Example

  • In the three-advertiser example, grouping and thinning produce E[CTR_i] = q_i(x)/6, whereas displaying the full matching without attenuation yields position-dependent survival factors.The example distinguishes matching feasibility from the click budget’s role in bounding the weighted number of groups.Source: A A Worked Example · p. 16

B Additional Encoding Details

The encoding analysis bounds the bit lengths used by the LP optimizer, matching decomposition, and sampling probabilities, supporting exact polynomial-time computation for the mechanism.

B Additional Encoding Details

  • For an active nonsingular d×d system, Hadamard’s inequality and Cramer’s rule bound LP vertex numerators and denominators in magnitude by 2^(O(L + d log(d+2))); the budget row is cleared using probability denominators with log2 Dp ≤ L.Source: B Additional Encoding Details · p. 16
  • The decomposition’s common denominator grows by at most a factor of K per step, giving a polynomial bit-length bound over at most N steps.Residual coordinates and weights remain in [0, 1], and each matching is computed using lower-bounded integral circulation.Source: B Additional Encoding Details · p. 16
  • Categorical group masses and retention probabilities have polynomial bit-length, and every Bernoulli parameter lies in [0, 1].The group masses include the remaining empty-outcome probability; retention parameters use a denominator derived from the prefix sum.Source: B Additional Encoding Details · p. 17
Loading 2610.33707v1…