Learning and pricing models for repeated generalized second-price auction in search advertising

In search advertising how much an advertiser is willing to pay for a click or tap on his search ad is private information, which hampers an ad seller’s ability to set the best reserve price to increase the revenue for the generalized second-price (GSP) auctions used to allocate ad slots. We present a series of learning and pricing models for repeated GSP auctions selling multiple heterogeneous items. This paper contributes to the literature in dynamic pricing with learning and complements the existing off-line studies on impact of the reserve price in the multi-billion dollar online advertising business. With few restrictions on the distribution function of the unknown parameter, algorithms are developed to estimate the empirical distribution function and determine the best reserve price to reduce the revenue loss (regret) over time. When bidders bid in the locally envy-free equilibrium, we present an algorithm that has the best attainable regret upper bound. When bidders do not bid in the locally envy-free equilibrium, we propose a GSP auction with position-specific reserve prices and develop an algorithm with the same regret bound to mitigate the risk of strategic bidding. With a high volatility involved, learning becomes more active while earning is more effective. When bidders coordinate bidding, the properly selected starting reserve prices can substantially reduce the revenue loss from possible collusive bidding behaviors.