CATS-May-16-2014
Title[edit]
Multiplicative Bidding
Speaker[edit]
Mohammad Hossein Bateni, Google Research
Abstract[edit]
In this paper, we initiate the study of the multiplicative bidding language adopted by major Internet search companies. In multiplicative bidding, the effective bid on a particular search term is the product of a base bid and bid adjustments that are dependent on features of the search term (for example, the geographic location of the user, or the platform on which the search is conducted). We consider the task faced by the advertiser when setting these bid adjustments, and establish a foundational optimization problem that captures the core difficulty of bidding under this language. We give matching algorithmic and approximation hardness results for this problem. Inspired by empirical studies of search engine price data, we then study certain restrictions of the problem, giving further algorithmic and hardness results. Our main technical contribution is an O(logn)-approximation for the case of multiplicative prices and monotone values. We then test our algorithms on real data against natural benchmarks.
