Sigecom Test of Time Award 2024 for AdWords and generalized online matching by Mehta, Saberi, Vazirani, and Vazirani

 The SIGecom Test of Time Award recognizes the author or authors of an influential paper or series of papers published between ten and twenty-five years ago that has significantly impacted research or applications exemplifying the interplay of economics and computation. More details and nomination procedure…

The Test of Time Award Winners for 2024 are Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani  

They are cited for "introducing and solving a model of online matching with budgets that has seen many practical applications to online markets and broad and continuing impact in the literature."

in their paper

AdWords and generalized online matching, Journal of the ACM 54(5), 2007, Article 22

Abstract: How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a trade-off revealing LP and use it to derive an optimal algorithm achieving a competitive ratio of 1−1/e for this problem.

From the introduction:

"Internet search engine companies, such as Google, Yahoo and MSN, have revolutionized not only the use of the Internet by individuals but also the way businesses advertise to consumers. Typical search engine queries are short and reveal a great deal of information about user preferences. This gives search engine companies a unique opportunity to display highly targeted ads to the user.

"The online advertising mechanisms used by search engines, including Google’s AdWords, are essentially large auctions where businesses place bids for individual keywords, together with limits specifying their maximum daily budget. The search engine company earns revenue when it displays their ads in response to a relevant search query (if the user actually clicks on the ad). Indeed, most of the revenues of search engine companies are derived in this manner [Battelle 2005]. One factor in their dramatic success is that, unlike conventional advertising, search engine companies are able to cater to low-budget advertisers (who occupy the fat tail of the power law distribution governing advertising budgets of companies and organizations).

"The following computational problem, which we call the adwords problem, is a formalization of a question posed to us by M. Henzinger: There are (private communication, 2004). N bidders, each with a specified daily budget bi . Q is a set of query words. Each bidder i specifies a bid ciq for query word q ∈ Q. A sequence q1q2 · · · q M of query words q j ∈ Q arrive online during the day, and each query q j must be assigned to some bidder i (for a revenue of ciq j ). The objective is to maximize the total revenue at the end of the day while respecting the daily budgets of the bidders.

"In this article, we present a deterministic algorithm achieving a competitive ratio of 1 − 1/e for this problem, under the assumption that bids are small compared to budgets."

###########

Last year's award:

Monday, April 3, 2023

Test of Time Award 2023 to Immorlica & Mahdian, and Ashlagi, Kanoria & Leshno

#######

"Past and Present Members of the Test of Time Award Committee: Yeon-Koo Che, Yiling Chen, Nikhil Devanur, Joan Feigenbaum, Jason Hartline, Bobby Kleinberg, Paul Milgrom, Noam Nisan, Asu Ozdaglar, David Parkes, David Pennock, Alvin Roth, Tim Roughgarden, Larry Samuelson, Tuomas Sandholm, Yoav Shoham, Éva Tardos, Moshe Tennenholtz"