Mechanism achieves truthful bidding and strong welfare in cascade auctions
A Factor-6 Truthful-in-Expectation Mechanism for Cascade Position Auctions
Computer Science and Game TheoryData Structures and Algorithms
Summary
Online ads are often shown in a sequence where people click less on ads further down the list because earlier ads get their attention first. The paper deals with the problem of assigning ads to slots so the total value is high while making sure advertisers truthfully reveal their willingness to pay. The authors create a new randomized method that guarantees the overall value is at least one-sixth of the best possible, while also encouraging honest bidding, unlike previous methods that couldn’t do both at the same time. Their approach carefully balances expected clicks for each advertiser so the payment system encourages truthful behavior.
What this means in practice
- •For online advertising platforms: Implement ad slot assignments that ensure truthful advertiser bidding with provable efficiency in user click behavior cascading down the positions.$Commercial implications: Enables ad platforms to sell advertising slots with guaranteed truthful bids and predictable efficiency gains in auctions.
- •For marketplace auction designers: Use the factor-6 truthful-in-expectation mechanism when building auctions for products with position-dependent user attention models that cascade.
Authors
Qiuyu Chen, Baao Xie
Abstract
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.