Going Broad in Ad Auctions

Between two extremes of algorithms theory and algorithm engineering, one is some times in the middle doing applied algorithms research. Then you don't want to be too close to reality, eg., think about cache misses, or too far, eg., optimize over the entire parameter space. Algorithms researchers have discovered the fun and challenge of walking this divide: formulate problems tastefully, find new algorithmic techniques, and push the solutions into psyche of practitioners and hope for impact.

My coauthors (Eyal Even-Dar, Yishay Mansour, Vahab Mirrokni and Uri Nadav) and I study how advertisers bid in sponsored search auctions. Advertisers have a set of keywords in their mind and have to figure out how much to bid on each, given constraints such as their budget, goals such as maximizing their profit or the clicks, and statistics such as what each bid will yield in expectation.

Close to reality, applied algorithms research kicks in. Auctioneers --- Google, Yahoo! and Microsoft --- let advertisers bid "broad" on keywords so their ads will qualify automatically for auctions even when users type variations of keywords. Advertisers can not cover every keyword variation in their bidding set explicitly, and find the broad match feature essential in practice. The difficulty is that a single bid now applies implicitly to several auctions, each with different value to the advertiser. Biding decisions now become nontrivial. We formulate associated problems and provide exact/approximate solutions in a forthcoming WWW09 paper.

Those who are interested in this topic may also want to look at this paper that studies the dual view of an auctioneer, ie., revenue, efficiency and equilibrium properties of broad match auctions (paper appeared in Workshop on Ad Auctions 08).