Making Google richer: optimal algorithms for the AdWords auction

Instead of my usual focus on AdSense, today I'm going to talk about a related topic, AdWords. On September 29, I attended a talk by Professor Umesh Vazirani, a well-known computer scientist from UC Berkeley. He was the opening speaker for this year's Distinguished Lecture Series sponsored by the University of Waterloo's School of Computer Science. The talk was titled Making Google Richer: Optimal Algorithms for the AdWords Auction. It wasn't specifically about AdWords per se, but about advertisement auctions in general.

As most of you know, AdWords uses a competitive bidding system that lets advertisers choose how much they're willing to pay to have their ads displayed in conjunction with specific keywords. I wrote about this briefly in Make
Easy Money with Google, but I didn't spend a lot of time on it other than mention that Google had to license some of the technology from Yahoo!, who acquired it when they bought Overture. Prof. Vazirani briefly went over some of this history and also explained in general how AdWords works for the benefit of the audience members (mostly computer science students and professors) who aren't as familiar with these concepts as those of you reading this article.

The problem faced by Google and other companies that implement bid-for-placement systems is to devise a bidding algorithm that generates the maximum revenue for the auctioneer. (Prof. Vazirani mentioned that Yahoo! was looking to redesign its algorithms because they felt they were leaving money on the table.) As it turns out, the “obvious” answer of ranking the ads by bid price (or some variation of bid price, such as Google's early attempts at using bid price multiplied by the clickthrough ratio) is not optimal. In many cases, this so-called “greedy” algorithm can in fact prove quite detrimental.

The key to all of this is the advertiser's budget, the total amount of money they're willing to spend on their bids within a certain time period. (For AdWords advertisers, the budget is calculated on a daily basis.) Using some complicated mathematical analysis, Prof. Vazirani and his colleagues were able to come up with an optimal algorithm for ranking bids by factoring in each advertiser's remaining budget into the equation. In other words, the more an advertiser spends its budget, the less likely it becomes to have its ads chosen. In the greedy algorithm, the advertisers who bid the highest end up dominating the auction until their budget is spent. In the optimal algorithm, that domination doesn't happen and other advertisers get to spend their budget. The end result is more revenue for the auctioneer, because most of the advertisers are spending all or most of their budgets.

It's certainly an interesting topic and a neat mathematical problem. If you want more details, see the article Computer Scientists Optimize Innovative Ad Auction (PDF), which goes over the problem and the solution in more detail. (As an amusing note, the article uses Vioxx as an example of a high-paying keyword. Readers of my book know how well Vioxx did for me as an AdSense publisher!)

Of course, we may never know if companies like Google or Yahoo! actually incorporate this work into their own algorithms. They're definitely following the research with some interest, though, as Prof. Vazirani has presented it to both companies.

P.S.: Today's the last day this month to join my mailing list and get a chance at winning a signed copy of my book.

Comments