ABSTRACT


Current auctions at Google and Yahoo! allow an advertiser to specify a bid for a particular keyword. When a search query arrives, the ads that have bid on a matching keyword are ranked, and perclick prices are set. We present two specific results related to these auctions.  We study a natural extension of current "secondprice" auctions called "prefix position auctions" where an advertiser can specify the number of top positions of interest. We design a simple auction mechanism and prove that it has an "envyfree" Nash equilibrium with the same outcome as the wellknown truthful VickreyClarkeGroves (VCG) auction. This generalizes known results for secondprice auctions. (Joint work with Gagan Aggarwal and S. Muthukrishnan.)  For the current secondprice auction, we study how to place bids on the keywords to maximize the return (the number of user clicks) for a given budget. While most variants of this budget optimization problem are NP hard, we show, perhaps surprisingly, that simply randomizing between two uniform strategies that bid equally on all the keywords gets at least a (11/e) fraction of the maximum clicks possible. (Joint work with S. Muthukrishnan, Cliff Stein and Martin Pal.) Both results are quite useful in practice. Many other interesting optimization and mechanism design problems related to search advertising remain open. Return to DMTCS home page. 