  We analyze the problem of how to optimally bid for ad spaces in online ad
auctions. For this we consider the general case of multiple ad campaigns with
overlapping targeting criteria. In our analysis we first characterize the
structure of an optimal bidding strategy. In particular, we show that an
optimal bidding strategies decomposes the problem into disjoint sets of
campaigns and targeting groups. In addition, we show that pure bidding
strategies that use only a single bid value for each campaign are not optimal
when the supply curves are not continuous. For this case, we derive a
lower-bound on the optimal cost of any bidding strategy, as well as mixed
bidding strategies that either achieve the lower-bound, or can get arbitrarily
close to it.
