Papers for

marketplace auction designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Mechanism achieves truthful bidding and strong welfare in cascade auctions

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

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.

Sat 24 OctComputer Science and Game TheoryData Structures and Algorithms
The gist
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.
Open → 2610.33707v1