Implementing sponsored search in web search engines: Computational evaluation of alternative mechanisms

The practice of sponsored search advertising-where advertisers pay a fee to appear alongside particular Web search results-is now one of the largest and fastest growing source of revenue for Web search engines. We model and compare several mechanisms for allocating sponsored slots, including stylized versions of those used by Overture and Google, the two biggest brokers of sponsored search. The performance of these mechanisms depends on the degree of correlation between providers' willingness to pay and their relevance to the search term. Ranking providers based on the product of relevance and bid price performs well and is robust across varying degrees of correlation. Ranking purely based on bid price fares nearly as well when bids and relevance are positively correlated (the expected regime), and is further enhanced by adding an editorial filter. Regardless of the allocation mechanism, sponsored search revenues are lower when users' attention decays quickly at lower ranks, emphasizing the need to develop better user interfaces and control features. The search engine can address initial inscience of relevance scores by modifying rank allocations over time as it observes clickthroughs at each rank. We propose a rank-revision strategy that weights clicks on lower ranked items more than clicks on higher ranked items. This method is shown to converge to the optimal (maximum revenue) ordering faster and more consistently than other methods.