Maintaining Equilibria During Exploration in Sponsored Search Auctions

作者：Langford John; Li Lihong; Vorobeychik Yevgeniy; Wortman Jennifer^*

来源：Algorithmica, 2010, 58(4): 990-1021.

DOI：10.1007/s00453-009-9318-z

• Sponsored search auctions
• Equilibrium analysis
• Exploration

We introduce an exploration scheme aimed at learning advertiser click-through rates in sponsored search auctions with minimal effect on advertiser incentives. The scheme preserves both the current ranking and pricing policies of the search engine and only introduces one set of parameters which control the rate of exploration. These parameters can be set so as to allow enough exploration to learn advertiser click-through rates over time, but also eliminate incentives for advertisers to alter their currently submitted bids. When advertisers have much more information than the search engine, we show that although this goal is not achievable, incentives to deviate can be made arbitrarily small by appropriately setting the exploration rate. Given that advertisers do not alter their bids, we bound revenue loss due to exploration.

• 出版日期2010-12