A Retrospective on “Implementing Sponsored Search in Web Search Engines: Computational Evaluation of Alternative Mechanisms”

Juan Feng, Hemant K. Bhargava, David Pennock

March 6, 2020

In the early 2000s, as we started this collaboration, Internet search engines were only a few years young but had become a vital piece of the Internet and our life more generally. We puzzled over how free search engines like Google could make money, never imagining today’s annual revenues well over $100 billion. The initial answer came from a startup called Overture, spun off from an incubator in Pasadena and later acquired by Yahoo.

Overture pioneered text-based ads that were priced, sold, and implemented much differently than the “banners” in newspapers, magazines, and early websites, and Google perfected the practice. Instead of negotiating bulk sales, Google and Overture allocated ad slots one at a time using large-scale continuous real-time auctions. The setting allowed instantaneous measurement of the relevance and performance of ads, enabling search engines to collect money only when users actually clicked, about 40 cents per click on average in 2003. Our paper focused on a few key issues needed to make auction-based pay-per-click advertising work well.

First, we discussed the game-theoretic nature of the problem involving three players: the search engine, advertisers, and users. Our model captured essential features of the setting while acknowledging plenty of missing complexities like equilibrium play, affiliate partnerships, inexact query matching, budgets, click fraud, pay per conversion, and more. Our ability to formulate a reasonable model and delineate its caveats benefitted from our interdisciplinary backgrounds in business, information science, and computer science, and our experience in the search advertising industry.

Second, observing that the two key companies employed quite different approaches, we sought to compare the performance of different ranking methods. Overture ranked ads in decreasing order of bids after editorial filtering, while Google ranked ads by bids times estimated click probabilities: effectively per-impression bids. Our paper explored the implications of picking one approach (rules that range over actual bids) versus the other (rules that combine bid and relevance). We showed that the correlation between relevance and bids was a crucial factor, where positive correlation is most natural.

Third, we recognized the tension in employing relevance scores in this extremely dynamic growth phase of the industry, where search engines were continuously faced with new bidders for whom they had no information to compute relevance. Some of these bidders may well be a great fit for the end-user, but how would a search engine know until it experimented with these new bidders? Frequently giving new bidders top billing would enable faster learning, but risked losing revenue and user satisfaction if they proved to be less relevant, setting up a multi-arm bandit problem. This part of our paper explored the implications of alternate methods for experimenting with new bidders, including a method for dynamically determining the number of trials to give to new participants. We modeled click probability with a relevance factor and a position factor, a crucial “separability” assumption that became standard in the literature.

A surprising fraction of the discussion in the paper remains relevant today. For example, reinforcement learning with stochastic rewards and utility functions that incorporate long-term metrics, including user satisfaction in advertising, remains an important and unsolved challenge. Still, the online advertising industry, and more broadly the online market design community, has progressed and expanded dramatically on many dimensions since our paper was published (and “plasma televisions”, one of our example queries, are extinct). Search engines today feature product listings, custom display features, reserve prices, and actions beyond clicks, including downloads, submits, likes, views, and purchases, initiated from GPS-enabled phones and digital assistants in our homes. Ads on social media and recommendation systems face related challenges.

We would like to thank the editors of the INFORMS Journal on Computing and the members of the 2020 IJOC Test of Time Paper Award committee for selecting our paper for this award. We feel lucky to have found a rich problem area with practical implications and academic value in its infancy, and honored to be recognized. Almost twenty years and multiple jobs later, we remain excited as ever about the promise of market design as an engineering discipline.