Friday, July 17, 2009

Bid optimization for Broad Match Ad Auctions

Can you bid on an ad network for a query q and have an automatic broad match for a set of queries T somehow related to q? Note that both q and all the queries in T have a cost and an associated utility. What you can potentially gain from one side can be lost on the other side. In addition, you --the advertiser -- have no control on what are the queries in T. You just select q and the engine will create T for you. This interesting question is answered by the Google's paper Bid optimization for Broad Match Ad Auctions.

Two models are presented. In the query language model, the advertiser can bet on all the queries with broad match. In this case, a Linear Programming solution is proposed. In the language model, the advertiser can bet on a subset of keywords as an exact or broad match. In this case, the problem is NP-Hard for any reasonable approximation factor. A constant factor approximation is then presented, when the profit exceed the cost.

The paper is a seminal ones. I expect to see more good models and algorithms exploring the "broadness" of a bid auction. For instance, I think that an interesting variant could be when an advertiser bid on an ad network. In this case the bid can be distributed to different places (engines), with different values of v(q) and (q). Even the q can be broad in the sense that different places can have a different matching strategies for q (e.g. maybe drop some word and similar stuff).

No comments:

Post a Comment