Algorithms and Complexity Seminar
*Note Unusual time and location* (not to mention the refreshments)
Wednesday February 21, 2007, 4:15-5:15pm in 32-G449 (Patil Conf.
Room); Refreshments at 4:00pm.
Algorithmic Issues in Internet Search Advertising
We present an overview of areas where algorithmic research issues arise
for an Internet search company such as Google. We then focus on one
area: search-based advertising 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.
Host: David Karger
(The Algorithms
and Complexity Seminar series talks are usually held Thursdays from
4-5:15pm in 32-G575.)