arXiv preprint ·
A Factor-6 Truthful-in-Expectation Mechanism for Cascade Position Auctions
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
Jointly Modeling Preferences and Imperfect Decision-Making in Large Language Models
Weighted Fairness in Multi-User Earth Observation Satellite Scheduling
Online Fair Division with Frequency Predictions
Strategic Calibration in LLM Multi-Agent Systems: Audited Pivot Scoring for Truthful Elicitation
Order-selection Prophet Inequality (Almost) Goes I.I.D
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.