Source-linked AI summary
Sponsored Search Auctions with Markovian Users
Gagan Aggarwal, Jon Feldman, S. Muthukrishnan, Martin Pal
TL;DR
The paper addresses the limited modeling of search-engine users in sponsored-search auctions, where prior work often assumes click probabilities are independent of other displayed ads. It introduces a Markovian scanning model, computes an efficient assignment, and applies VCG pricing; the resulting mechanism differs from GSP while retaining bid-monotonic position and click probabilities. The paper also identifies parameter-estimation and comparative-efficiency questions as open issues.
Problem
Prior work often fixes GSP’s ranking and assumes an ad’s click probability is independent of the other displayed ads, despite user behavior defining the advertisers’ commodity and its value.
Method
The paper models users as scanning ads sequentially, derives structural properties of optimal assignments, designs an efficient assignment algorithm, and combines it with VCG pricing.
Results
The optimal assignment differs from GSP, while position and click probability remain monotonic in an ad’s bid with other bids fixed.
Takeaways & Limitations
Modeling user behavior jointly with mechanism design links the assignment rule to user interactions while preserving an intuitive higher-bid, higher-position-and-click relationship.
Takeaways & Limitations
Implementing the mechanism requires estimating continuation parameters qi, which the authors identify as a challenging statistical and machine-learning problem.
Abstract
from arXiv · showhide
Sponsored search involves running an auction among advertisers who bid in order to have their ad shown next to search results for specific keywords. Currently, the most popular auction for sponsored search is the "Generalized Second Price" (GSP) auction in which advertisers are assigned to slots in the decreasing order of their "score," which is defined as the product of their bid and click-through rate. In the past few years, there has been significant research on the game-theoretic issues that arise in an advertiser's interaction with the mechanism as well as possible redesigns of the mechanism, but this ranking order has remained standard. From a search engine's perspective, the fundamental question is: what is the best assignment of advertisers to slots? Here "best" could mean "maximizing user satisfaction," "most efficient," "revenue-maximizing," "simplest to interact with," or a combination of these. To answer this question we need to understand the behavior of a search engine user when she sees the displayed ads, since that defines the commodity the advertisers are bidding on, and its value. Most prior work has assumed that the probability of a user clicking on an ad is independent of the other ads shown on the page. We propose a simple Markovian user model that does not make this assumption. We then present an algorithm to determine the most efficient assignment under this model, which turns out to be different than that of GSP. A truthful auction then follows from an application of the Vickrey-Clarke-Groves (VCG) mechanism. Further, we show that our assignment has many of the desirable properties of GSP that makes bidding intuitive. At the technical core of our result are a number of insights about the structure of the optimal assignment.
1 Introduction
The paper replaces the standard independence-based view of sponsored-search users with a Markovian scanning model, then derives an efficient assignment and truthful auction while preserving intuitive bidding.
- Motivation: Prior sponsored-search work largely fixed GSP’s bid-times-click-through-rate ranking while focusing on pricing, equilibria, and advertiser strategy.This leaves user behavior exogenized even though it defines the commodity and its value.
- Markovian user model: The proposed user model scans ads from top to bottom and makes click, continuation, or abandonment decisions based on the ads encountered.Each ad can affect both its own click probability and whether lower ads are viewed.
- Markovian user model: The model makes position factors decrease naturally and removes separability because each factor depends on the ads placed above.For position j, the factor is αj = Πi′∈Aqi′.
- Auction design: The optimal assignment differs from GSP because it trades off an ad’s click probability against its effect on slots below.The authors identify structural properties that yield an efficient algorithm and use VCG pricing for truthfulness.
- Intuitive bidding: Under the efficient assignment, an advertiser’s position and click probability are monotonic in its bid when other bids remain fixed.This preserves the intuitive bidding property that higher bids produce higher positions and more clicks.
2 Markov User Click Model
The model assigns each advertiser a click-through rate, a continuation probability, and a bid, then evaluates assignments through sequential user scanning and continuation.
- Bidder and user parameters: Each bidder has a click-through rate pi and continuation probability qi.pi is the probability of clicking after viewing ad i; qi is the probability of looking at the next ad.
- Bids and values: Each bidder’s bid bi represents the value of a click, and pibi is the advertiser’s value for an impression.The paper denotes this impression value by ei.
- Sequential user process: The user examines the assigned ads from the first position downward, clicking each viewed ad with its click-through rate.Scanning stops at the last ad or when a continuation test fails.
- Assignment and pricing: The auctioneer chooses the assignment maximizing total expected advertiser value, then computes VCG prices from each bidder’s effect on others’ value.The resulting pricing rule assures truthful bid reporting under profit-maximizing utility.
3 Properties of Optimal Assignments
The optimal assignment under the Markovian click model sorts selected ads by adjusted ecpm, but selecting the ads requires accounting for their effects on later positions. Structural properties of optimal assignments support efficient computation and bid-monotone position and click probabilities.
- Adjusted ECPM: The adjusted ecpm ai = ei/(1−qi) captures an ad’s impression value adjusted for its negative effect on ads below it.Here, ei is the ad’s impression value and qi its continuation probability.
- Adjusted ECPM: In every most efficient assignment, the selected ads are sorted in decreasing order of adjusted ecpm.This determines the order of selected ads, but not which k ads should be selected.
- Selecting Ads: Selecting the top k ads by adjusted ecpm is not generally optimal because ad selection must account for continuation effects.In the example, the optimal assignment is (1, 2) with efficiency $2.50, while simple ecpm ranking gives $2.20 and adjusted-ecpm ranking gives $1.65.
- Bidder Dominance: If an unassigned bidder has both higher ecpm and higher adjusted ecpm than an assigned bidder, substituting the former is no worse.This dominance relation helps characterize optimal assignments, although higher ecpm or adjusted ecpm alone does not suffice.
- Subset Structure: Optimal assignments across different slot counts have a subset structure: every optimal solution for j−1 positions is contained in some optimal solution for j positions.This property is used to establish position monotonicity and supports the assignment algorithm.
- Bid Monotonicity: With other bids fixed, both a bidder’s optimal click probability and position are nondecreasing in her bid.This is the main monotonicity theorem supporting intuitive bidding.
- Bid Monotonicity: As one bidder’s bid increases, the sequence of optimal solutions changes only toward solutions giving that bidder higher click probability.Each solution’s value increases linearly with the bidder’s bid at a slope equal to that solution’s click probability.
4 Computing the Optimal Assignment
The paper develops algorithms for computing the efficiency-maximizing assignment of Markovian bidders to slots, first via dynamic programming and then via structural improvements. The resulting optimal assignment can be found in O(n log n + k^2 log^2 n) time and combined with VCG pricing to obtain truthfulness.
- Dynamic Programming: A dynamic program computes the optimal assignment by sorting ads by a-ecpm and using a recurrence over bidders and slots.The recurrence chooses between assigning bidder i to slot j, gaining q_i plus e_i, or skipping that bidder.
- Dynamic Programming: Solving the recurrence for F(1, 1) yields the optimal assignment in O(nk) time.
- Near-linear Time Algorithm: The faster algorithm exploits structural properties of optimal solutions and an oracle for maximizing linear functions over bidder intervals.It constructs nested optimal sets and searches possible a-ecpm ranks for each newly added bidder.
- Near-linear Time Algorithm: Dyadic intervals and convex-hull data structures implement the oracle, allowing linear-function maximization over intervals in O(log n) time.The preprocessing constructs convex hulls for O(n) dyadic intervals in O(n log n) time.
- Result: An optimal assignment can be determined in O(n log n + k^2 log^2 n) time.Using this optimal assignment with VCG pricing yields a truthful mechanism for sponsored search with Markovian users.
5 Concluding Remarks
The paper frames sponsored search as a three-party process that models users before designing mechanisms for advertisers and the search engine. It identifies parameter estimation and broader model extensions as open issues.
- Three-party framework: The approach models user behavior first and then designs mechanisms governing interactions between advertisers and the search engine.
- Open issues: Implementing the mechanism requires estimating model parameters, particularly the continuation probabilities q_i, which is a challenging statistical and machine-learning problem.
- Open issues: The paper leaves open how much efficiency or revenue improvement its model provides compared with VCG without the user model.
- Extensions: Future work includes location-dependent continuation probabilities, arbitrary webpage ad configurations, additional user states, and bid-dependent page layouts.