Ads on the Auction Block

Cell phone as sensor

Cool Alumni

Dean's Digest

Printer-friendly version

Umesh Vazirani is also involved in a large UC Berkeley effort to explore quantum computing, future systems that would harness the unusual properties of quantum physics.

Every day, the hammer goes down on millions of online auctions. And not just at eBay.com. Search engines like Google and Yahoo! have become billion-dollar businesses by auctioning off popular search terms to the highest bidder. Advertisers pay top dollar to link their ads to certain keywords. For example, search the word refinance on Google, and you'll see a list of mortgage brokers on the right side of the page. The top spot almost always goes to advertisers who are willing to pay the most each time someone clicks their ad. But, according UC Berkeley professor Umesh Vazirani that approach has plenty of room for improvement. He and his colleagues developed a novel computer algorithm that could optimize the advertising auction model, bringing in even bigger bucks for the search engines.

"There's an incredible premium on targeting an ad to what a consumer has in his or her mind," Vazirani says. "The important thing is not the page he is looking at, but what he's looking for. So auctioning off the search term makes perfect sense."

In the current Google ad model, advertisers identify the keywords they want to associate with their ads and determine how much they'll pay per click. If an ad isn't clicked, Google doesn't earn a dime. As a result, the "clickthrough" rate -- how often an ad is clicked when it's linked to a certain keyword - is also taken into account when determining how far up an ad is ranked on the page. Each day, advertisers specify their budget for the automated auctions. Once their budget is drained, the ad drops completely off the page.

Vazirani says he had never noticed the ads on Google until last year when he became involved in the research. The idea was seeded when Georgia Institute of Technology graduate student Amin Saberi visited Google and was asked how the company might optimize ad-ranking algorithm. Saberi brought the problem to graduate student Aranyak Mehta and their thesis adviser, Vijay Vazirani, Umesh's brother and a Berkeley alum. The three quickly determined that putting the highest bidder in the top spot on the page isn't the best way to optimize Google's income. Often, the top bidders rapidly hemorrhage their budget on a high rank, knocking themselves all out of competition and lowering the price of the keyword as a result. The ideal algorithm would take into account when ranking the advertisers how much budget each advertiser has left. That would not only boost Google's income but keep competition fierce. The question was how to write an algorithm that did this.

"You want the best ranking algorithm, not just one that keeps advertisers in the auction because it suits the search engine's purposes," says Umesh Vazirani, who is also a researcher with the Center for Information Technology Research in the Interest of Society (CITRIS).

Vijay Vazirani was reminded of a research paper he had written nearly 15 years ago with his brother and UC Berkeley computer scientist Richard Karp. In the theoretical problem they studied, called "online bipartite matching," a group of boys sit in a room waiting for girls to come in one at a time. A "matchmaker" matches each girl to a boy she's compatible with. The aim is to maximize the number and quality of the matches in real time. The Vaziranis and the students revisited the solution described in the paper and reframed the problem in ad auction terms.

"The boys are the advertisements and the girls are the keywords," Umesh says. "But in this case, the aim is not just to maximize the number of matches but also the revenue. So it's a much more complicated problem."

Delving deeply into the mathematics, the four researchers devised an algorithm that balances two trade-offs -- bids and remaining budget. The novel algorithm also foils common methods to "game" the auction. In one approach, an advertiser strategically lets a competitor win the highest rank for a keyword so they exhaust their budget quickly. Then, the second place bidder gets the keyword at a much lower price for the rest of the day.

"The mechanism that we have is much more resilient than traditional methods to this kind of gaming," Umesh Vazirani says. "For example, if a person has a higher bid but has spent most of his budget, the top ranking may go to the lower bidder."

Do you have a comment or question regarding this research? We want to hear from you...

Currently, the researchers are fine tuning their algorithm and putting it through its paces in online tests. They've filed for a patent on the work but hope that the research remains in the public domain for others to build upon.

Of course, the search engines are still eager to hear more. Indeed, Umesh Vazirani recently visited Yahoo! to discuss how their ad auction algorithms might be improved with a bit of mathematical magic.

"When you're talking about billions of dollars, an algorithm that could help a company earn even one percent more from the auctions is huge," he says.

Umesh Vazirani's home page

Vijay V. Vazirani's home page

"Google's Thriving Advetising Model Has Math Roots" (Georgia Tech, Institute Communications and Public Affairs)

Lab Notes is published online by the Marketing and Communications Office of the UC Berkeley College of Engineering. The Lab Notes mission is to illuminate groundbreaking research underway today at the College of Engineering that will dramatically change our lives tomorrow.

Media contact: Teresa Moore, Lab Notes editor, Director of Marketing and Communications
Writer, Researcher: David Pescovitz
Web Manager: Michele Foley

Subscribe or send comments to the Engineering Marketing and Communications Office: lab-notes@coe.berkeley.edu.

© 2005 UC Regents. Updated 7/1/05.