University of California, Berkeley
Making Google Richer: Optimal Algorithms for the AdWords Auction
Abstract: This year the combined advertising revenues of Google and Yahoo is expected to rival the combined prime-time ad revenues of America's three big television networks, ABC, CBS, and NBC. The key to this revolution in advertising is an innovative auction run by the search engine companies. Companies' bids for search keywords determine which ads are displayed during Internet searches. There are a number of algorithmic and game theoretic issues that arise in this context. In particular, the problem of maximizing revenue in such keyword auctions can be formulated as an online computational problem. I will describe two simple algorithms that achieve optimal performance. The proofs of performance of these algorithms rely on a new linear programming based technique called tradeoff revealing family of LPs, which I will briefly touch upon.
The talk is based on joint work with Aranyak Mehta, Amin Saberi and Vijay Vazirani.
Biography: Umesh Vazirani is a Professor in the Computer Science Division of the Department of Electrical Engineering and Computer Science at UC Berkeley. He received an NSF Presidential Young Investigator Award in 1987 and the Friedman Mathematics Prize in 1985. He has written the book, An Introduction of Computational Learning Theory (with Michael Kearns), and currently is at the forefront of research in the area of quantum computing.
Professor Vazirani is a Director of the Berkeley Quantum Information and Computation Center (BQIC).