Robust Mechanisms for Sponsored Search

Sponsored search auctions sell ad positions (impressions) to advertisers on the event of a user query. The value of an advertiser for an ad position (impression), is the product of a private value per click, and a predicted click-through rate (PCTR) known to the auctioneer. A common mechanism for sponsored search auctions is to rank advertisers by their value. Lahaie and Pennock proposed a different ranking scheme based on "squashing'' the PCTRs by raising them to a power less than 1, and used numerical experiments to show that this method leads to increased revenue. In this paper, we prove that a modified form of squashing (called linear squashing) is approximately optimal for maximizing revenue in a model of sponsored search auctions that captures the fact that bid distributions are hard to estimate in a non-manipulable way.