Mechanisms and Strategies in Sponsored Search Auctions

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 per-click prices
are set.  We present two specific results related to these auctions.

- We study a natural extension of current "second-price" 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 "envy-free" Nash equilibrium with
the same outcome as the well-known truthful Vickrey-Clarke-Groves
(VCG) auction. This generalizes known results for second-price
auctions.  (Joint work with Gagan Aggarwal and S. Muthukrishnan.)

- For the current second-price 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 (1-1/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.