Concise Bid Optimization Strategies with Multiple Budget Constraints

A major challenge laced by marketers attempting to optimize their advertising campaigns is to deal with budget constraints. The problem is even harder in the face of multidimensional budget constraints, particularly in the presence of many decision variables involved and the interplay among the decision variables through such constraints. Concise bidding strategies help advertisers deal with this challenge by introducing fewer variables upon which to act. In this paper, we study the problem of finding optimal concise bidding strategies for advertising campaigns with multiple budget constraints. Given bid landscapes-that is, the predicted value (e.g., number of clicks) and the cost per click for any bid-that are typically provided by ad-serving systems, we optimize the value of an advertising campaign given its budget constraints. In particular, we consider bidding strategies that consist of no more than k different bids for all keywords. For constant k, we provide a polynomial-time approximation scheme to optimize the profit, whereas for arbitrary k we show how a constant-factor approximation algorithm can be obtained via a combination of solution enumeration and dependent LP rounding techniques, which can be of independent interest. In addition to being able to deal with multidimensional budget constraints, our results do not assume any specific payment scheme and can be applied on pay-per-click, pay-per-impression, or pay-per-conversion models. Also, no assumption about the concavity of value or cost functions is made. Finally, we evaluate the performance of our algorithms on real data sets in regimes with up to six-dimensional budget constraints. In the case of a single budget constraint, in which uniform bidding (currently used in practice) has a provable performance guarantee, our algorithm beats the state of the art by an increase of 1%-6% in the expected number of clicks. This is achieved by only two or three clusters in contrast with the single cluster permitted in uniform bidding. With multiple budget constraints, the gap between the performance of our algorithm and an enhanced version of uniform bidding grows to an average of 5%-6% (and as high as 35% in higher dimensions).