Making Google Richer: Optimal Algorithms for the AdWords Auction

Google's phenomenal success may be ascribed as much to a revolution in advertising as to its superior search results. The key to this online advertising model is an innovative auction run by the search engine companies. Advertisers' 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 on-line computational problem. I will describe a simple on-line algorithm that achieves optimal performance for this problem. The proof of performance of this algorithm relies 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.