Ad auctions are the principal source of (multi-billion dollar) revenues of search engine companies, such as Google, and sit at the heart of the online economy. The key computational issue underlying this marketplace is: how to match keyword queries from millions of users of Google with thousands of advertisers (businesses) so as to maximize economic efficiency (and in turn Google's revenue). A key requirement is that these decisions need to be made very fast as soon as a keyword query arrives, since results need to be displayed almost instantaneously. Furthermore, this needs to be done without any knowledge of the rest of the queries that will come later in the day.

Vazirani will talk about an optimal online algorithm for this problem, obtained over a decade ago, when the gorithmic and economic/game-theoretic issues of this market place were just being understood. Over the years, the simple heuristic of bid scaling, that is suggested by our algorithm, has been widely adopted by Google and other search engine companies. Vazirani will also allude to the game theoretic issues that have arisen in this marketplace. For algorithms designers, this a very satisfying story of practical impact from rich theory.