A Look Back: How Web Search Ads Emerged, Transformed Business
Professor Hemant Bhargava blogs about his landmark 2007 study on the early days of search advertising, recently honored with INFORMS' Test of Time Paper Award.
(Editors’ Note: Bhargava, Feng and Pennock’s 2007 landmark paper “Implementing Sponsored Search in Web Search Engines: Computational Evaluation of Alternative Mechanisms” has been selected as the INFORMS Journal of Computing’s Test of Time Paper Award for 2003-2007.)
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.
Monetizing Search Ad Marketplace
Our paper, published in winter 2007, 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, 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.
Global Search Ad Spend: $140 Billion Today
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 (for example, “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 Test of Time Paper Award committee for recognizing our paper and research impact.
We feel fortunate to have found a rich problem area with practical implications and academic value in its infancy, and honored to be recognized.
Professor Bhargava has continued working in market design for Internet platforms. For example, a recent paper, "On Optimal Auctions for Mixing Exclusive and Shared Matching in Platforms," looks at how to design an auction mechanism for a platform that seeks to conduct both one-to-one matches and one-to-many matches, choosing dynamically based on preferences of bidders.
Almost 20 years and multiple jobs later, we remain excited as ever about the promise of market design as an engineering discipline.